Research map / Optimization / Nonconvex and smooth optimization
Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum
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.
Proposes normalized error feedback variants of EF21 (||EF21||) and EF21-SGDM (||EF21-SGDM||) with convergence guarantees under (L0,L1)-generalized smoothness in distributed settings without data heterogeneity assumptions, and shows larger stepsizes help on polynomial, logistic regression, and ResNet-20 tasks.
Problem
Distributed communication-efficient (compressed) nonconvex optimization under generalized (L0,L1)-smoothness, where classical smoothness-based error feedback analyses do not apply and prior generalized-smooth distributed analyses need data heterogeneity or bounded-variance assumptions.
Approach
Apply gradient normalization to the EF21 and EF21-SGDM error feedback updates so that the step length is independent of the gradient scale, giving O(1/sqrt K) (deterministic) and O(1/K^{1/4}) (stochastic) gradient-norm rates under generalized smoothness, with stepsizes not requiring L0 or L1 knowledge in the deterministic case.
Key results
- On ResNet-20 training with CIFAR-10 (5 clients, top-k with k=0.1d, stepsize 5), ||EF21|| achieved accuracy gains of up to 10% over EF21 relative to communicated bits.
- Theory: ||EF21|| achieves O(1/sqrt K) min expected gradient norm under generalized smoothness with stepsize gamma0/sqrt(K+1) without knowing L0 or L1, and is slower than EF21 under L-smoothness only by a factor of 2*sqrt(2).
- ||EF21-SGDM|| attains O(1/K^{1/4}) rate in expectation, matching EF21-SGDM, with no data heterogeneity assumption and no bounded-variance-almost-surely assumption.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add normalization to EF21 | EF21 · Polynomial-function minimization | convergence speed | Helped |
| Add normalization to EF21 | EF21 · Logistic regression with nonconvex regularizer; Breast Cancer, a1a, and synthetic data | convergence speed | Helped |
| Add normalization to EF21 | EF21 · CIFAR-10 test set, ResNet-20 | accuracy: up to 10% | Helped |
| Add normalization to EF21 | EF21 · Nonconvex L-smooth problems | convergence factor: 2\sqrt{2} | Hurt |
| Add normalization to EF21 | EF21 · Nonconvex generalized-smooth deterministic optimization | iteration complexity: \mathcal{O}(1/\epsilon^2) -> \mathcal{O}(1/\epsilon^2) | No clear effect |
| Add normalization to EF21-SGDM | EF21-SGDM · Nonconvex generalized-smooth stochastic optimization | iteration complexity: \mathcal{O}(1/\epsilon^4) -> \mathcal{O}(1/\epsilon^4) | No clear effect |
Limitations
- Deterministic analysis uses constant stepsizes that can become impractically small for large K; no decreasing or adaptive schedules analyzed.
- Stochastic rate O(1/K^{1/4}) stepsize depends on L1 and compression parameter alpha.
- Experiments are small-scale (polynomials, logistic regression, ResNet-20 on CIFAR-10) and use a fixed hand-chosen gamma.
Experimental setup
Datasets: CIFAR-10 LIBSVM Breast Cancer LIBSVM a1a synthetic logistic regression data
Benchmarks: CIFAR-10 LIBSVM Breast Cancer LIBSVM a1a
Metrics: gradient norm loss test accuracy bits communicated
Baselines: EF21 EF21-SGDM
Builds on: EF21 EF21-SGDM (L0,L1)-smoothness normalized SGD with momentum
Closest papers by meaning
- EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback (NeurIPS 2021 · similarity 0.89)
- Momentum Provably Improves Error Feedback! (NeurIPS 2023 · similarity 0.88)
- Convergence Rates of Non-Convex Stochastic Gradient Descent Under a Generic Lojasiewicz Condition and Local Smoothness (ICML 2022 · similarity 0.88)
- Error Feedback Reloaded: From Quadratic to Arithmetic Mean of Smoothness Constants (ICLR 2024 · similarity 0.87)
- Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness (AAAI 2024 · similarity 0.86)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.86)
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.