检索结果-内蒙古大学图书馆

MindTheStep-AsyncPSGD: Adaptive asynchronous parallel stochastic gradient descent

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bäckström, Karl Papatriantafilou, Marina Tsigas, Philippas Dept. of Computer Science and Engineering Chalmers University of Technology Gothenburg Sweden

Stochastic Gradient Descent (SGD) is very useful in optimization problems with high-dimensional non-convex target functions, and hence constitutes an important component of several Machine Learning and Data Analytics methods. Recently there have been significant works on understanding the parallelism inherent to SGD, and its convergence properties. Asynchronous, parallel SGD (AsyncPSGD) has received particular attention, due to observed performance benefits. On the other hand, asynchrony implies inherent challenges in understanding the execution of the algorithm and its convergence, stemming from the fact that the contribution of a thread might be based on an old (stale) view of the state. In this work we aim to deepen the understanding of AsyncPSGD in order to increase the statistical efficiency in the presence of stale gradients. We propose new models for capturing the nature of the staleness distribution in a practical setting. Using the proposed models, we derive a staleness-adaptive SGD framework, MindTheStep-AsyncPSGD, for adapting the step size in an online-fashion, which provably reduces the negative impact of asynchrony. Moreover, we provide general convergence time bounds for a wide class of staleness-adaptive step size strategies for convex target functions. We also provide a detailed empirical study, showing how our approach implies faster convergence for deep learning applications. Copyright © 2019, The Authors. All rights reserved.

关键词： Gradient methods

MindTheStep-AsyncPSGD: Adaptive Asynchronous Parallel Stochastic Gradient Descent

学校读者我要写书评

暂无评论

MindTheStep-AsyncPSGD: Adaptive Asynchronous Parallel Stocha...

IEEE International Conference on Big Data

作者： Karl Bäckström Marina Papatriantafilou Philippas Tsigas Dept. of Computer Science and Engineering Chalmers University of Technology Gothenburg Sweden

ISBN: (数字)9781728108582

ISBN: (纸本)9781728108599

关键词： Convergence Stochastic processes Optimization Instruction sets Computational modeling Scalability Delays

Near-optimal optimistic reinforcement learning using empirical bernstein inequalities

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Tossou, Aristide Basu, Debabrota Dimitrakakis, Christos Department of Computer Science and Engineering Chalmers University of Technology Göteborg Sweden

We study model-based reinforcement learning in an unknown finite communicating Markov decision process. We propose a simple algorithm that leverages a variance based confidence interval. We show that the proposed algorithm, UCRL-V, achieves the optimal regret Õ(√DSAT) up to logarithmic factors, and so our work closes a gap with the lower bound without additional assumptions on the MDP. We perform experiments in a variety of environments that validates the theoretical bounds as well as prove UCRL-V to be better than the state-of-the-art algorithms. Copyright © 2019, The Authors. All rights reserved.

关键词： Markov processes

Differential privacy for multi-armed bandits: What is it and what is its cost?

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Basu, Debabrota Dimitrakakis, Christos Tossou, Aristide Department of Computer Science and Engineering Chalmers University of Technology Göteborg Sweden

We introduce a number of privacy definitions for the multi-armed bandit problem, based on differential privacy. We relate them through a unifying graphical model representation and connect them to existing definitions. We then derive and contrast lower bounds on the regret of bandit algorithms satisfying these definitions. We show that for all of them, the learner’s regret is increased by a multiplicative factor dependent on the privacy level ǫ, but that the dependency is weaker when we do not require local differential privacy for the rewards. Copyright © 2019, The Authors. All rights reserved.

关键词： Machine learning

Differential privacy at risk: Bridging randomness and privacy budget

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Dandekar, Ashish Basu, Debabrota Bressan, Stéphane Département d’informatique École Normale Supérieure Paris France Data Science and AI Division Department of Computer Science and Engineering Chalmers University of Technology Göteborg Sweden School of Computing National University of Singapore Singapore

The calibration of noise for a privacy-preserving mechanism depends on the sensitivity of the query and the prescribed privacy level. A data steward must make the non-trivial choice of a privacy level that balances the requirements of users and the monetary constraints of the business entity. We analyse roles of the sources of randomness, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution, that are involved in the design of a privacy-preserving mechanism. The finer analysis enables us to provide stronger privacy guarantees with quantifiable risks. Thus, we propose privacy at risk that is a probabilistic calibration of privacy-preserving mechanisms. We provide a composition theorem that leverages privacy at risk. We instantiate the probabilistic calibration for the Laplace mechanism by providing analytical results. We also propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. The convexity of the proposed cost model leads to a unique fine-tuning of privacy level that minimises the compensation budget. We show its effectiveness by illustrating a realistic scenario that avoids overestimation of the compensation budget by using privacy at risk for the Laplace mechanism. We quantitatively show that composition using the cost optimal privacy at risk provides stronger privacy guarantee than the classical advanced *** Codes 65C20 Copyright © 2020, The Authors. All rights reserved.

关键词： Random processes

Near-optimal bayesian solution for unknown discrete markov decision process

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Tossou, Aristide Dimitrakakis, Christos Basu, Debabrota Department of Computer Science and Engineering Chalmers University of Technology Göteborg Sweden

We tackle the problem of acting in an unknown finite and discrete Markov Decision Process (MDP) for which the expected shortest path from any state to any other state is bounded by a finite number D. An MDP consists of S states and A possible actions per state. Upon choosing an action at at state st, one receives a real value reward rt, then one transits to a next state st+1. The reward rt is generated from a fixed reward distribution depending only on (st;at) and similarly, the next state st+1 is generated from a fixed transition distribution depending only on (st;at). The objective is to maximize the accumulated rewards after T interactions. In this paper, we consider the case where the reward distributions, the transitions, T and D are all unknown. We derive the first polynomial time Bayesian algorithm, BUCRL that achieves up to logarithm factors, a regret (i.e the difference between the accumulated rewards of the optimal policy and our algorithm) of the optimal order ~O( √DSAT). Importantly, our result holds with high probability for the worst-case (frequentist) regret and not the weaker notion of Bayesian regret. We perform experiments in a variety of environments that demonstrate the superiority of our algorithm over previous techniques. Our work also illustrates several results that will be of independent interest. In particular, we derive a sharper upper bound for the KL-divergence of Bernoulli random variables. We also derive sharper upper and lower bounds for Beta and Binomial quantiles. All the bound are very simple and only use elementary functions. Copyright © 2019, The Authors. All rights reserved.

关键词： Markov processes

The capacity of single-server weakly-private information retrieval

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Lin, Hsuan-Yin Kumar, Siddhartha Rosnes, Eirik Graell i Amat, Alexandre Yaakobi, Eitan Simula UiB BergenN-5006 Norway The Department of Electrical Engineering Chalmers University of Technology Simula UiB GothenburgSE-41296 Sweden The Department of Computer Science Technion - Israel Institute of Technology Haifa3200003 Israel

A private information retrieval (PIR) protocol guarantees that a user can privately retrieve files stored in a database without revealing any information about the identity of the requested file. Existing information-theoretic PIR protocols ensure perfect privacy, i.e., zero information leakage to the servers storing the database, but at the cost of high download. In this work, we present weakly-private information retrieval (WPIR) schemes that trade off perfect privacy to improve the download cost when the database is stored on a single server. We study the tradeoff between the download cost and information leakage in terms of mutual information (MI) and maximal leakage (MaxL) privacy metrics. By relating the WPIR problem to rate-distortion theory, the download-leakage function, which is defined as the minimum required download cost of all single-server WPIR schemes for a given level of information leakage and a fixed file size, is introduced. By characterizing the download-leakage function for the MI and MaxL metrics, the capacity of single-server WPIR is fully described. Copyright © 2020, The Authors. All rights reserved.

关键词： Database systems

Multi-server weakly-private information retrieval

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Lin, Hsuan-Yin Kumar, Siddhartha Rosnes, Eirik Graell i Amat, Alexandre Yaakobi, Eitan Simula UiB BergenN-5006 Norway The Department of Electrical Engineering Chalmers University of Technology GothenburgSE-41296 Sweden Simula UiB The Department of Computer Science Technion - Israel Institute of Technology Haifa3200003 Israel

Private information retrieval (PIR) protocols ensure that a user can download a file from a database without revealing any information on the identity of the requested file to the servers storing the database. While existing protocols strictly impose that no information is leaked on the file's identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the perfect privacy requirement. We refer to such protocols as weakly-private information retrieval (WPIR) protocols. In particular, for the case of multiple noncolluding replicated servers, we study how the download rate, the upload cost, and the access complexity can be improved when relaxing the perfect privacy constraint. To quantify the information leakage on the requested file's identity we consider mutual information (MI), worst-case information leakage, and maximal leakage (MaxL). We present two WPIR schemes, denoted by Scheme A and Scheme B, based on two recent PIR protocols and show that the download rate of the former can be optimized by solving a convex optimization problem. We also show that Scheme A achieves an improved download rate compared to the recently proposed scheme by Samy et al. under the so-called ǫ-privacy metric. Additionally, a family of schemes based on partitioning is presented. Moreover, we provide an information-theoretic converse bound for the maximum possible download rate for the MI and MaxL privacy metrics under a practical restriction on the alphabet size of queries and answers. For two servers and two files, the bound is tight under the MaxL metric, which settles the WPIR capacity in this particular case. Finally, we compare the performance of the proposed schemes and their gap to the converse bound. Copyright © 2020, The Authors. All rights reserved.

关键词： Convex optimization

A Flipped Classroom Approach to Teaching Empirical Software engineering

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Gren, Lucas Department of Computer Science and Engineering Chalmers University of Technology University of Gothenburg Gothenburg Sweden

Contribution: A flipped classroom approach to teaching empirical software engineering increases student learning by providing more time for active learning in class. Background: There is a need for longitudinal studies of the flipped classroom approach in general. Although a few cross-sectional studies show that a flipped classroom approach can increase student learning by providing more time for other in-class activities, such as active learning, such studies are also rare in the context of teaching software engineering. Intended outcomes: To assess the usefulness of a flipped classroom approach in teaching software engineering. Application design: The study was conducted at an international Master’s program in Sweden, given in English, and partially replicated at a university in Africa. Findings: The results suggest that students’ academic success, as measured by their exam grades, can be improved by introducing a flipped classroom to teach software engineering topics, but this may not extend to their subjective liking of the material, as measured by student evaluations. Furthermore, the effect of the change in teaching methodology was not replicated when changing the teaching team. Copyright © 2019, The Authors. All rights reserved.

关键词： Students