Never Go Full Batch (in Stochastic Convex Optimization)

2021/06/29 by Idan Amir, Amir, Idan, Yair Carmon +5
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.2107.00469

arxiv created 2021/06/29 · openalex publication_date 2021/06/29 · arxiv updated 2021/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the generalization performance of full-batch optimization algorithms for stochastic convex optimization: these are first-order methods that only access the exact gradient of the empirical risk (rather than gradients with respect to individual data points), that include a wide range of algorithms such as gradient descent, mirror descent, and their regularized and/or accelerated variants. We provide a new separation result showing that, while algorithms such as stochastic gradient descent can generalize and optimize the population risk to within ε after O(1/ε²) iterations, full-batch methods either need at least Ω(1/ε⁴) iterations or exhibit a dimension-dependent sample complexity.

Related

• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
• The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Mini-batch stochastic gradient descent with dynamic sample sizes
• Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD