SGD and Hogwild! Convergence Without the Bounded Gradients Assumption

Abstract

Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime, which results in more relaxed conditions than those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate.

Cited by in corpus (36)

• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Distributed learning with compressed gradients
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Quantization for decentralized learning under subspace constraints
• Random Reshuffling: Simple Analysis with Vast Improvements
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Recent theoretical advances in decentralized distributed convex optimization
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• New Convergence Aspects of Stochastic Gradient Algorithms
• Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness
• Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions
• Instrumental Variable Value Iteration for Causal Offline Reinforcement Learning
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes
• SMG: A Shuffling Gradient-Based Method with Momentum
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• SGD with Coordinate Sampling: Theory and Practice
• On Adaptive Stochastic Optimization for Streaming Data: A Newton's Method with O(dN) Operations
• Robust learning with anytime-guaranteed feedback
• Local Methods with Adaptivity via Scaling
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• Better scalability under potentially heavy-tailed gradients
• Accelerated Almost-Sure Convergence Rates for Nonconvex Stochastic Gradient Descent using Stochastic Learning Rates
• The duality structure gradient descent algorithm: analysis and applications to neural networks
• New nonasymptotic convergence rates of stochastic proximal pointalgorithm for convex optimization problems
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models