Research map / Optimization / Implicit bias and generalization
Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling
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 Progressive Rescaling Gradient Descent (PRGD), which periodically rescales parameter norm while running normalized GD, to achieve exponential margin maximization on linear separable data, versus polynomial rates for GD/NGD.
Problem
Gradient-based methods (GD, NGD) maximize the ℓ2 margin on linearly separable data only at slow rates (O(1/log t) for GD, O(1/t) for NGD); the paper asks whether margin maximization can be accelerated.
Approach
Analyze the centripetal velocity of normalized gradients; show that norm rescaling can move iterates into a region (a semi-infinite hollow cylinder) where the centripetal velocity is uniformly bounded below, and alternate rescaling with projected NGD steps (PRGD) with progressively increasing radii to get exponential directional convergence and margin maximization.
Key results
- On the toy dataset, NGD gives Θ(1/t) directional and margin error while PRGD gives e^{-Θ(t)} (proved).
- PRGD(exp) on synthetic data maximizes the margin (super-)exponentially fast, while GD and NGD decrease the margin gap much more slowly.
- On real digits datasets and in homogenized VGG-16 on CIFAR-10, PRGD achieves better generalization than GD and NGD (improvement magnitudes not given in the extracted text).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add progressive norm rescaling to normalized gradient descent | Linear classification on linearly separable data · Linearly separable data (under stated assumptions) | margin error: \mathcal{O}(1/ t) -> e^{-\Omega(t)} | Helped |
| Add progressive norm rescaling to normalized gradient descent | Linear classification on linearly separable data · Linearly separable data (under stated assumptions) | directional error: \mathcal{O}(1/ t) -> e^{-\Omega(t)} | Helped |
| Add progressive norm rescaling to normalized gradient descent | Three-point synthetic dataset · Three-point synthetic dataset | margin error: \Theta\left({1}/{t}\right) -> e^{-\Theta\left(t\right)} | Helped |
| Use polynomially increasing rather than exponentially increasing progressive radii (ablation) | PRGD · Synthetic linearly separable datasets | margin gap | Mixed |
| Use polynomially increasing rather than exponentially increasing progressive radii (ablation) | PRGD · digit datasets | margin gap | Helped |
| Add progressive norm rescaling | Linear classifier · digit datasets | margin gap | Helped |
| Add progressive norm rescaling | Linear classifier · Cancer | generalization performance | Helped |
| Add progressive norm rescaling | Homogenized VGG-16 · CIFAR-10 | generalization performance | Helped |
Surprising findings
- PRGD with polynomially growing radii (PRGD(poly)) also performs well, in contrast to the exponential radius prescribed by theory.
- Lower bounds Θ(1/log t) for GD and Θ(1/t) for NGD hold under mild conditions, showing these rates are tight for those algorithms.
Limitations
- Theory requires the support vectors to span the whole data span (Assumption on non-degenerate data), which real datasets violate.
- Theoretical guarantees hold only for a specific family of hyperparameters; real experiments use modified/tuned radii.
- Deep network experiments use homogenized VGG-16 without a theoretical guarantee.
Experimental setup
Datasets: synthetic linearly separable datasets sklearn digits sklearn Cancer CIFAR-10
Benchmarks: sklearn digits sklearn Cancer CIFAR-10
Metrics: margin gap gamma* - gamma(w(t)) directional error test performance
Baselines: GD NGD Nesterov dual acceleration PRGD(poly)
Builds on: Soudry et al. implicit bias of GD normalized gradient descent margin analysis dual Nesterov acceleration for margin maximization
Closest papers by meaning
- Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (ICLR 2020 · similarity 0.90)
- Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions (NeurIPS 2019 · similarity 0.89)
- Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks (ICLR 2025 · similarity 0.87)
- Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization (NeurIPS 2024 · similarity 0.86)
- Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares (ICML 2024 · similarity 0.86)
- Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness (NeurIPS 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.