REVIEW 24 cited by
Handbook of Convergence Theorems for (Stochastic) Gradient Methods
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
This is a handbook of simple proofs of the convergence of gradient and stochastic gradient descent type methods. We consider functions that are Lipschitz, smooth, convex, strongly convex, and/or Polyak-{\L}ojasiewicz functions. Our focus is on ``good proofs'' that are also simple. Each section can be consulted separately. We start with proofs of gradient descent, then on stochastic variants, including minibatching and momentum. Then move on to nonsmooth problems with the subgradient method, the proximal gradient descent and their stochastic variants. Our focus is on global convergence rates and complexity rates. Some slightly less common proofs found here include that of SGD (Stochastic gradient descent) with a proximal step, with momentum, and with mini-batching without replacement.
Forward citations
Cited by 24 Pith papers
-
Optimized methods for composite optimization: a reduction perspective
A reduction framework converts unconstrained optimized first-order methods into composite-setting methods with analogous rates, yielding new proximal OGM and proximal OGM-G guarantees.
-
Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
Incremental Gradient Descent has worst-case convergence gaps in the small epoch regime that become exponentially bad with nonconvex components, though a carefully chosen fixed permutation can still outperform with-rep...
-
Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks
Bounded trajectories of a broad class of GD optimizers (Adam, RMSprop, NAG, Adan, etc.) converge with polynomial rates to critical points of KL objectives with locally Lipschitz gradients, covering analytic-activation...
-
Convergence Rates for Distribution Matching with Sliced Optimal Transport
For Gaussian distributions, slice-matching to an isotropic target with decaying step sizes converges at rate O(k^{-(2α-1)}) in expectation.
-
Transformative or Conservative? Conservation laws for ResNets and Transformers
Conservation laws for gradient-flow training of conv ResNets and Transformers are characterized for several building blocks, and deep network block laws reduce to laws of isolated blocks.
-
Step-Size Stability in Stochastic Optimization: A Theoretical Perspective
The stability index δ_t, the variance term in a two-term suboptimality bound, is provably smaller and saturates in the step-size cap for SPS, NGN, and proximal point, explaining their observed learning-rate robustness...
-
Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation
D-Byz-SGDM aggregates cached momentum from non-sampled clients together with fresh momentum from sampled clients, preserving Byzantine robustness under partial participation and achieving an optimal O(cδζ²/p) stationa...
-
A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms
For linear least squares, SNGD and SPRING are proved equivalent to accelerated regularized Kaczmarz methods, yielding the first fast rates and first SPRING guarantee; the general quadratic analysis holds under strong ...
-
Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms
All regular linearly convergent algorithms to a fixed point set can be written as a baseline optimizer plus an exponentially decaying learned perturbation, and any such perturbation preserves linear convergence.
-
Stochastic Quantum Hamiltonian Descent
SQHD is a gate-based quantum algorithm that approximates a Lindblad dynamics blending Hamiltonian descent with stochastic component noise, giving an order-2 weak approximation and an O(1/t + eta sigma*) convergence bo...
-
Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
SGD's last iterate reaches an O(log T / sqrt(T)) expected optimality gap for convex smooth stochastic problems under only convexity, smoothness, and finite gradient variance at a minimizer.
-
Data Depth as a Risk
Halfspace depth equals the minimal 0-1 classification risk of a linear classifier on Q plus a single negative point, and replacing the loss or classifier yields new 'loss depths' that perform competitively in anomaly ...
-
On the boundedness of the sequence generated by minibatch stochastic gradient descent
Minibatch SGD with decreasing stochastic Polyak stepsizes keeps iterates bounded under a sublevel-set condition that includes coercive convex objectives, and specific unbounded cases are constructed.
-
Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming
A non-Euclidean dual gradient ascent for entropically regularized SDPs is shown to converge with dimension-independent rates, achieving Sinkhorn-like complexity for optimal transport and optimal-scaling results for pe...
-
GORACS: Group-level Optimal Transport-guided Coreset Selection for LLM-based Recommender Systems
GORACS selects small groups of fine-tuning examples via an optimal-transport and gradient-norm proxy objective, outperforming prior coreset methods for LLM-based recommendation.
-
On the Convergence Analysis of Muon
Muon's convergence rate depends on an average Hessian curvature along its update directions, which can be much smaller than the worst-case Lipschitz constant when Hessians are low-rank.
-
AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descent
AutoSGD runs three parallel SGD streams at nearby learning rates, uses paired noisy objective estimates to pick the winner, and is claimed to converge with little user tuning.
-
Accelerated optimization of measured relative entropies
Measured relative entropies can be computed by Nesterov accelerated gradient descent/ascent because their variational objective functions are smooth and strongly convex/concave.
-
Balancing Utility and Privacy: Dynamically Private SGD with Random Projection
D2P2-SGD combines time-decreasing privacy noise with random projection to improve the accuracy of differentially private SGD, with convergence rates matching ordinary SGD.
-
Memory Savings at What Cost? A Study of Alternatives to Backpropagation
Checkpointed backpropagation beats forward-mode AD and zero-order optimization in accuracy, convergence speed, and compute for LLM fine-tuning, undermining claims that the alternatives are practical memory savers.
-
Efficient Stochastic Optimisation via Sequential Monte Carlo
Sequential Monte Carlo samplers can approximate intractable gradients inside a first-order optimizer, yielding a general SOSMC framework that speeds up reward tuning of energy-based models in the reported settings.
-
Scalable Parameter and Memory Efficient Pretraining for LLM: Recent Algorithmic Advances and Benchmarking
A benchmark and two low-cost tricks (weight refactorization and momentum reset) that make low-rank LLM pre-training competitive with GaLore and Fira at about 25% lower memory.
-
Design Criteria for SGD Preconditioners: Local Conditioning, Noise Floors, and Basin Stability
The late-stage noise floor of preconditioned SGD is the product of the M-metric condition number and the preconditioned noise level, so the design goal is to improve conditioning while dampening noise.
-
Introduction to optimization methods for training SciML models
A tutorial review of optimization for SciML that explains PDE-induced stiffness through the NTK/Hessian spectrum and surveys adaptive sampling, second-order, and preconditioning methods.
Discussion (0). Continue with ORCID to comment.