Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

2019/02/03 by Adrien Taylor, Francis Bach, Taylor, Adrien +1 · 12 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.CC #cs.LG #cs.NA #math.NA #math.OC

paper · pdf · doi:10.48550/arxiv.1902.00947

Conference on Learning Theory (COLT) 2019; code available at https://github.com/AdrienTaylor/Potential-functions-for-first-order-methods. [V6: typos & minor improvements]

openalex publication_date 2019/02/03 · arxiv created 2021/12/21 · arxiv updated 2021/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide a novel computer-assisted technique for systematically analyzing first-order methods for optimization. In contrast with previous works, the approach is particularly suited for handling sublinear convergence rates and stochastic oracles. The technique relies on semidefinite programming and potential functions. It allows simultaneously obtaining worst-case guarantees on the behavior of those algorithms, and assisting in choosing appropriate parameters for tuning their worst-case performances. The technique also benefits from comfortable tightness guarantees, meaning that unsatisfactory results can be improved only by changing the setting. We use the approach for analyzing deterministic and stochastic first-order methods under different assumptions on the nature of the stochastic noise. Among others, we treat unstructured noise with bounded variance, different noise models arising in over-parametrized expectation minimization problems, and randomized block-coordinate descent schemes.

Citations

• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• The general problem of the stability of motion
• A Stochastic Approximation Method
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Potential-Function Proofs for First-Order Methods
• On the Properties of Convex Functions over Open Sets
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• A Robust Accelerated Optimization Algorithm for Strongly Convex\n Functions

Cited by

• Generalization of Silver Stepsize Schedule to Stochastic Optimization
• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
• On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms
• Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization
• AutoLyap: A Python package for computer-assisted Lyapunov analyses for first-order methods
• Optimized projection-free algorithms for online learning: construction and worst-case analysis
• Tight analyses of first-order methods with error feedback
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• New Tight Bounds for SGD without Variance Assumption: A Computer-Aided Lyapunov Analysis
• An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization
• Gradient Descent's Last Iterate is Often (slightly) Suboptimal

Related

• Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• A multilevel stochastic regularized first-order method with application to finite sum minimization