Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization

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.

arXiv commentPhD thesis, University of Edinburgh, 2017

References in corpus (18)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• No More Pesky Learning Rates
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Proximal Stochastic Dual Coordinate Ascent
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• Importance Sampling for Minibatches
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
• On the Łojasiewicz Exponent of the Quadratic Sphere Constrained Optimization Problem
• Coordinate Descent Face-Off: Primal or Dual?
• Robust Block Coordinate Descent
• Online optimization and regret guarantees for non-additive long-term constraints

Cited by in corpus (1)

• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time