Research map / Optimization / Distributed and compressed
Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction
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 sign-based stochastic variance reduction (SSVR) and its finite-sum and distributed majority-vote variants, improving signSGD convergence rates in T for stochastic, finite-sum, and heterogeneous majority-vote settings.
Problem
signSGD converges at O(d^{1/2}T^{-1/4}) for stochastic non-convex optimization, and existing heterogeneous majority-vote sign methods have poor rates (O(dT^{-1/4}+dn^{-1/2}) or O(d^{3/8}T^{-1/8})), with sub-optimal dependence on m for finite-sum sign methods.
Approach
Combines STORM-style variance-reduced gradient tracking with sign-based updates (and SVRG-style periodic full gradients with an error-correction term for finite-sum), and in distributed settings replaces deterministic sign with an unbiased stochastic sign operation so that 1-bit messages remain unbiased.
Key results
- SSVR achieves convergence rate O(d^{1/2}T^{-1/3}) versus O(d^{1/2}T^{-1/4}) for signSGD under average smoothness.
- SSVR-FS improves finite-sum rate to O(m^{1/4}d^{1/2}T^{-1/2}), versus O(m^{1/2}d^{1/2}T^{-1/2}) for SignSVRG.
- SSVR-MV (Option 2) achieves O(d^{1/4}T^{-1/4}) in heterogeneous majority vote, improving on O(d^{3/8}T^{-1/8}); experiments show higher test accuracy than baselines on CIFAR-100 with 4 and 8 nodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add variance reduction to signSGD updates | signSGD · Stochastic non-convex optimization | convergence rate (l1-norm): \(\mathcal{O}(d^{1/2}T^{-1/4})\) -> \(\mathcal{O}(d^{1/2}T^{-1/3})\) | Helped |
| Add periodic full-gradient computation and an error-correction term | SignSVRG · Finite-sum non-convex optimization | convergence rate (l1-norm): \(\mathcal{O}(m^{1/2}d^{1/2}T^{-1/2})\) -> \(\mathcal{O}(m^{1/4}d^{1/2}T^{-1/2})\) | Helped |
| Use unbiased stochastic sign mapping on workers | Sign-based majority vote under heterogeneous data · Heterogeneous majority vote | convergence rate (l1-norm): \(\mathcal{O}(dT^{-1/4} + dn^{-1/2})\) -> \(\mathcal{O}(d^{1/2}T^{-1/2} + dn^{-1/2})\) | Helped |
| Replace the server-side sign operation with an unbiased stochastic sign mapping (ablation) | SSVR-MV Option 1 · Heterogeneous majority vote | convergence rate (l2-norm): \(\mathcal{O}(d^{3/8}T^{-1/8})\) -> \(\mathcal{O}(d^{1/4}T^{-1/4})\) | Helped |
| Use SSVR for CIFAR-10 image classification | ResNet18 · CIFAR-10 | testing accuracy | Helped |
| Use SSVR-FS for CIFAR-10 image classification | ResNet18 · CIFAR-10 | testing accuracy | Helped |
| Use SSVR-MV for distributed CIFAR-100 image classification | ResNet50 · CIFAR-100, 4 and 8 nodes | testing accuracy | Helped |
Surprising findings
- The majority-vote variant with deterministic sign on the server does not converge to zero gradient as T grows; the unbiased stochastic sign at the server is needed for convergence to zero.
Limitations
- Requires average smoothness (stronger than standard smoothness) and bounded variance assumptions.
- The O(d^{1/4}T^{-1/4}) distributed rate requires bounded gradient assumptions and a projection step.
- Experiments are limited to CIFAR-10/100 with ResNet models; no large-scale language or vision experiments.
Experimental setup
Datasets: CIFAR-10 CIFAR-100
Benchmarks: CIFAR-10 CIFAR-100
Metrics: training loss gradient norm testing accuracy
Baselines: signSGD signSGD-SIM SignSVRG Signum SSDM Sto-signSGD MV-signSGD-SIM
Builds on: signSGD STORM SVRG signSVRG MV-signSGD-SIM
Closest papers by meaning
- Stochastic Sign Descent Methods: New Algorithms and Better Theory (ICML 2021 · similarity 0.93)
- Momentum Ensures Convergence of SIGNSGD under Weaker Assumptions (ICML 2023 · similarity 0.91)
- When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds (NeurIPS 2026 · similarity 0.91)
- Sign-Based Optimizers Are Effective Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
- z-SignFedAvg: A Unified Stochastic Sign-Based Compression for Federated Learning (AAAI 2024 · similarity 0.86)
- Investigating the Role of Weight Decay in Enhancing Nonconvex SGD (CVPR 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.