Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization

2018/04/02 by Dominik Csiba, Csiba, Dominik
Computer Science · Decision Sciences · Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1804.00437

PhD thesis, University of Edinburgh, 2017

arxiv created 2018/04/02 · openalex publication_date 2018/04/02 · arxiv updated 2018/04/03 · openalex created_date 2018/04/13 · openalex updated_date 2026/07/28

Abstract

Gradient descent methods and especially their stochastic variants have become highly popular in the last decade due to their efficiency on big data optimization problems. In this thesis we present the development of data sampling strategies for these methods. In the first four chapters we focus on four views on the sampling for convex problems, developing and analyzing new state-of-the-art methods using non-standard data sampling strategies. Finally, in the last chapter we present a more flexible framework, which generalizes to more problems as well as more sampling rules.

Citations

• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• A Stochastic Approximation Method
• Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Related

• Nonconvex Variance Reduced Optimization with Arbitrary Sampling
• Carathéodory Sampling for Stochastic Gradient Descent
• Adaptive Sampling Strategies for Stochastic Optimization
• Stochastic dual averaging methods using variance reduction techniques for regularized empirical risk minimization problems
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods