Research map / Optimization / Optimizers
Learning Complexity of Gradient Descent and Conjugate Gradient Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames step-size and conjugate-parameter selection for gradient descent and conjugate gradient as statistical learning, proposing a sum-of-distances cost (inspired by primal-dual integral) and deriving pseudo-dimension and sample-complexity bounds for both.
Problem
Learning complexity (sample complexity) of tuning step sizes and conjugate parameters in gradient descent and conjugate gradient for unconstrained convex optimization, where the existing iteration-count cost gives only (1+eps) guarantees and does not extend to CG.
Approach
Replace the iteration-count cost with a primal-dual-integral-inspired cost that sums distances between current iterates and the optimum over iterations, which allows arbitrary C>0 error and extends to CG by bounding iterate deviation under two step sizes via second-order linear recurrences.
Key results
- Gradient descent under the new cost admits an ERM learner achieving (C+epsilon, delta)-learning with m = Õ(H^3/epsilon^2) samples for any C > 0, improving on the (1+epsilon) guarantee from iteration-count cost.
- For conjugate gradient, an ERM learner achieves (C+epsilon, delta)-learning with Õ(H^4/epsilon^2) samples, claimed as the first learning complexity result for CG.
- Pseudo-dimension of the GD algorithm class under the new cost is bounded by [log(nu/LZ)/log(1-beta)] log|N|.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace iteration-count cost with the sum of distances to the optimum across iterations | GD learning framework · GD learning framework | learning error guarantee: (1+\epsilon, \delta) -> (C+\epsilon, \delta) | Helped |
| Replace iteration-count cost with the sum of distances to the optimum across iterations | GD learning framework · GD learning framework | sample complexity: m=\tilde{O}(H^3/\epsilon^2) -> m=\tilde{O}(H^3/\epsilon^2) | No clear effect |
Limitations
- Results are purely theoretical and rely on strong assumptions such as convexity, L-smoothness and a contraction condition (Assumption 1.4/2.4) on step sizes.
- No empirical experiments validate the bounds.
- CG analysis relies on bounds that depend on the step-size range and the constant H, with the number of iterations bounded by H.
Experimental setup
Metrics: pseudo-dimension sample complexity bound m (C+epsilon, delta)-learning guarantee
Baselines: iteration-count cost for gradient descent (Balcan et al.)
Builds on: Gupta and Roughgarden data-driven algorithm design framework Balcan et al. learning-theoretic step size tuning for gradient descent primal-dual integral for MILP
Closest papers by meaning
- The Power of Random Features and the Limits of Distribution-Free Gradient Descent (ICML 2025 · similarity 0.87)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Stochastic Spectral and Conjugate Descent Methods (NeurIPS 2018 · similarity 0.86)
- Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.86)
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.85)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.