Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting

Abstract

We propose mS2GD: a method incorporating a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent (S2GD). We consider the problem of minimizing a strongly convex function represented as the sum of an average of a large number of smooth convex functions, and a simple nonsmooth convex regularizer. Our method first performs a deterministic step (computation of the gradient of the objective function at the starting point), followed by a large number of stochastic steps. The process is repeated a few times with the last iterate becoming the new starting point. The novelty of our method is in introduction of mini-batching into the computation of stochastic steps. In each step, instead of choosing a single function, we sample $b$ functions, compute their gradients, and compute the direction based on this. We analyze the complexity of the method and show that it benefits from two speedup effects. First, we prove that as long as $b$ is below a certain threshold, we can reach any predefined accuracy with less overall work than without mini-batching. Second, our mini-batching scheme admits a simple parallel implementation, and hence is suitable for further acceleration by parallelization.

References in corpus (10)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Randomized Iterative Methods for Linear Systems
• Sparse Online Learning via Truncated Gradient
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Communication-Efficient Distributed Dual Coordinate Ascent
• Mini-Batch Primal and Dual Methods for SVMs
• Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity

Cited by in corpus (59)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Revolutionizing Future Connectivity: A Contemporary Survey on AI-empowered Satellite-based Non-Terrestrial Networks in 6G
• Stochastic Variance Reduction for Nonconvex Optimization
• A Review on Deep Learning in Medical Image Reconstruction
• D${}^2$: Decentralized Training over Decentralized Data
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
• Stop Wasting My Gradients: Practical SVRG
• Stochastic Dual Ascent for Solving Linear Systems
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Kalman-based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning
• Distributed Mini-Batch SDCA
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Randomized Block Coordinate Descent for Online and Stochastic Optimization
• Linearly convergent stochastic heavy ball method for minimizing generalization error
• Accelerated Variance Reduced Stochastic ADMM
• AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Dynamic Mini-batch SGD for Elastic Distributed Training: Learning in the Limbo of Resources
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Towards closing the gap between the theory and practice of SVRG
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition
• Trading-off variance and complexity in stochastic gradient descent
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• About accelerated randomized methods
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Variance Reduction for Distributed Stochastic Gradient Descent
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• SAAGs: Biased Stochastic Variance Reduction Methods for Large-scale Learning
• Accelerating Mini-batch SARAH by Step Size Rules
• Searching equillibriums in large transport networks
• SAGA with Arbitrary Sampling
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Convergence in quadratic mean of averaged stochastic gradient algorithms without strong convexity nor bounded gradient
• Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization
• Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications
• Non accelerated efficient numerical methods for sparse quadratic optimization problems and its generalizations
• SGD with Variance Reduction beyond Empirical Risk Minimization