Research map / Optimization / Nonconvex and smooth optimization
Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares
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.
Derives closed-form optimal stepsizes for two-block cyclic block gradient descent on least-squares under block-wise orthogonality, showing it converges twice as fast as heavy ball and yields improved rates for generalized alternating projection (GAP++).
Problem
Block gradient descent (cyclic) with the conventional stepsize 1/L per block has no theoretical justification for its empirical advantage over gradient descent; its deterministic convergence bounds have worse constants than GD. The paper asks what optimal stepsizes for BGD on least-squares would ach
Approach
Under block-wise orthogonality (A1^T A1 = I, A2^T A2 = I), the paper finds closed-form optimal per-block stepsizes for two-block cyclic BGD by minimizing the spectral radius of the iteration matrix, showing acceleration without momentum; applying these to generalized alternating projection yields improved rates (GAP++).
Key results
- Under block-wise orthogonality, optimal BGD stepsizes achieve spectral radius rho_BGD* <= (rho_HB*)^2, i.e., asymptotically twice as fast as heavy ball.
- In the rank-deficient case the optimal stepsizes gamma1 = gamma2 = 2/(1+sqrt(1-lambda_1(CC^T))) coincide with the optimal heavy ball stepsize alpha*.
- GAP++ stepsizes yield asymptotic linear rate (sin θr - sin θ1)/(sin θr + sin θ1), always at least as good as prior generalized alternating projection rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Tune the two cyclic block stepsizes optimally instead of using momentum | BGD on least-squares with two orthogonal blocks · Least-squares | asymptotic convergence rate: ρ_BGD* ≤ (ρ_HB*)^2 | Helped |
| Use GAP++ stepsizes instead of prior generalized alternating-projection stepsizes | Generalized alternating projection · All possible choices of θ1 and θr | linear rate factor: \frac{\sin (\theta_{r}) - \sin (\theta_{1 }) }{\sin (\theta_{r}) + \sin (\theta_{1 }) } | Helped |
| Set γ1=γ2=1 (block exact minimization) instead of optimal BGD stepsizes (ablation) | BGD on least-squares with orthogonal blocks · Least-squares | spectral radius: ρ(M(1, 1)) = λ1(C Cᵀ) | Hurt |
| Set γ1=γ2=1 instead of optimal stepsizes (ablation) | BGD on least-squares with orthogonal blocks · Least-squares | spectral radius: ρ(M(1, 1)) = λ1(C Cᵀ) < √λ1(C Cᵀ) = ρ_GD* | Hurt |
| Use the earlier GAP stepsizes γ=1, γ1=γ2=\frac{2}{1+\sin(\theta_1)} instead of GAP++ stepsizes (ablation) | Generalized alternating projection · Generalized alternating projection | linear rate factor: \frac{1 - \sin (\theta_{1 }) }{1 + \sin (\theta_{1 }) } | Mixed |
| Use the partial-relaxation stepsize instead of GAP++ stepsizes (ablation) | Generalized alternating projection · Generalized alternating projection | linear rate factor: \frac{\sin^2 (\theta_{r }) - \sin^2 (\theta_{1 }) }{\sin^2 (\theta_{r }) + \sin^2 (\theta_{1 }) } | Mixed |
| Set γ=1 in generalized Douglas–Rachford (ablation) | Generalized Douglas–Rachford · Generalized alternating projection | linear rate factor: \cos (\theta_1) | No clear effect |
Surprising findings
- Plain BGD without momentum, with tuned stepsizes, beats heavy ball with optimal parameters, despite the rate being twice as fast only asymptotically.
- The prior claim of optimality for generalized alternating projection rates is inaccurate; the paper revises it.
Limitations
- Results hold only for two blocks and under block-wise orthogonality (A_j^T A_j = I).
- Asymptotic rates only; the optimal stepsizes are not shown to be optimal for finite iterations.
- Experiments are small synthetic MATLAB simulations.
Experimental setup
Metrics: spectral radius distance to optimum ||x^t - x*||
Baselines: gradient descent with optimal stepsize heavy ball method alternating projection Douglas-Rachford generalized alternating projection (Badea/Pierra-style stepsizes)
Builds on: heavy ball method generalized alternating projection Nesterov lower bound analysis
Closest papers by meaning
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.88)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.87)
- Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization (ICLR 2024 · similarity 0.87)
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.87)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.87)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · similarity 0.87)
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.