Faster Margin Maximization Rates for Generic Optimization Methods

Guanghui Wang, Zihao Hu, Vidya Muthukumar, Jacob D. Abernethy

In the world of deep learning, we often train models that are "overparameterized"—meaning they have far more parameters than data points. This leads to a curious problem: there are infinitely many ways to perfectly fit the training data. Yet, simple algorithms like Gradient Descent (GD) consistently find solutions that generalize well to new data.

This "magic" is known as implicit bias. The optimization algorithm itself nudges the model toward specific, high-quality solutions—usually those that maximize the "margin" between classes. While we’ve understood this well for standard Gradient Descent, other powerful methods like Mirror Descent and Adversarial Training have lagged behind in theoretical speed. A new paper from researchers at Georgia Tech and Google Research changes that, offering a unified framework that significantly accelerates our understanding of these methods.

TL;DR

The authors introduce a unified game-theoretic framework that treats optimization as a regularized bilinear game between a "weight player" and a "data player." By leveraging regret bounds from online learning, they derive state-of-the-art (and often much faster) convergence rates for the implicit bias of Mirror Descent, Steepest Descent, and Adversarial Training.

What Problem Does This Paper Address?

When training a linear classifier on separable data using a loss function like the logistic loss, the weights don't just stop at a solution; they keep growing in magnitude while their direction converges to a "max-margin" solution.

For standard Gradient Descent, we know this happens relatively quickly. However, for "generic" optimization methods—like Mirror Descent (which adapts to different geometries) or Steepest Descent (which uses non-Euclidean norms)—the known theoretical rates of convergence were much slower. Similarly, in Adversarial Training (AT), where we train models to be robust against small perturbations, the convergence to a "robust" max-margin solution was thought to be painfully slow (logarithmic in time).

The gap was clear: do these algorithms actually converge slowly, or is our math just not sharp enough yet?

Methods

The "secret sauce" of this paper is a shift in perspective. Instead of analyzing the optimization trajectory directly, the authors frame Empirical Risk Minimization (ERM) as a two-player zero-sum game:

  1. The w-player (Weights): Tries to maximize the margin.
  2. The p-player (Data): Tries to find the "hardest" examples that minimize that margin.

By showing that standard algorithms like Mirror Descent are mathematically equivalent to specific Online Learning strategies (like Follow-the-Regularized-Leader) playing this game, the authors can use "regret bounds"—a well-studied concept in online learning—to prove how fast the players reach equilibrium.

For Adversarial Training, they extend this to a multi-player game, adding $n$ additional players who control the adversarial perturbations for each data point.

Datasets

As a theoretical paper, the authors do not use standard image benchmarks like ImageNet. Instead, they focus on a basic setting involving a linearly separable dataset $S$ with $n$ examples in $d$ dimensions. Their results are proven mathematically for any such dataset that satisfies standard assumptions (like bounded feature vectors).

Key Insights and Ideas

  • Regret = Rate: The most elegant insight is that the convergence rate of the optimization algorithm is directly determined by the "regret" of the players in the game. Better online learning strategies lead to faster margin maximization.
  • Acceleration is Universal: The authors show that Nesterov-style acceleration isn't just for Gradient Descent. By using accelerated online learning dynamics, they achieve $O(1/T^2)$ rates for Mirror Descent and even Adversarial Training.
  • AT isn't inherently slow: Perhaps the most surprising finding is that Adversarial Training can converge to its robust max-margin solution just as fast as standard training on clean data. The previous "slow" rates in the literature were a limitation of the analysis, not the algorithm.

Key Results

The paper provides a significant "speedup" in our theoretical understanding (summarized in their Table 1):

Algorithm Previous Rate New Rate (This Paper)
Mirror Descent $O(1/T^{1/4})$ $O(\log T / T)$
Steepest Descent $O(1/\sqrt{T})$ $O(1/T)$
Adversarial Training $O(1/\log T)$ $O(1/T)$
Accelerated Methods N/A $O(1/T^2)$

Note: $T$ represents the number of iterations.

They also provide bounds on directional error—how quickly the direction of the weight vector aligns with the optimal max-margin direction—showing it is typically a square-root factor slower than the margin convergence itself.

Limitations and Future Work

While the framework is powerful, the authors acknowledge a few boundaries:

  • Loss Functions: The current analysis is tailored to exponentially-tailed losses (like logistic or exponential loss). Extending this to a broader class of losses is a key next step.
  • Linearity: The results are currently limited to linear classification. While linear models are the standard "proving ground" for implicit bias, extending these fast rates to deep neural networks remains a grand challenge.
  • Last-Iterate Convergence: Some results focus on the average of the iterates; proving these same fast rates for the very last step of Mirror Descent remains an open theoretical question.

Reference: Wang, G., Hu, Z., Gentile, C., Muthukumar, V., & Abernethy, J. (2024). Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods. arXiv:2305.17544v2 [cs.LG].

Summary updated

Abstract

First-order optimization methods tend to inherently favor certain solutions over others when minimizing a given training objective with multiple local optima. This phenomenon, known as \emph{implicit bias}, plays a critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that gradient-descent-based methods exhibit an implicit bias for the $\ell_2$-maximal margin classifier in the context of separable binary classification. In contrast, generic optimization methods, such as mirror descent and steepest descent, have been shown to converge to maximal margin classifiers defined by alternative geometries. However, while gradient-descent-based algorithms demonstrate fast implicit bias rates, the implicit bias rates of generic optimization methods have been relatively slow. To address this limitation, in this paper, we present a series of state-of-the-art implicit bias rates for mirror descent and steepest descent algorithms. Our primary technique involves transforming a generic optimization algorithm into an online learning dynamic that solves a regularized bilinear game, providing a unified framework for analyzing the implicit bias of various optimization methods. The accelerated rates are derived leveraging the regret bounds of online learning algorithms within this game framework.
BibTeX
@inproceedings{wang2025faster,
  author = {Guanghui Wang and Zihao Hu and Vidya Muthukumar and Jacob D. Abernethy},
  title = {{Faster Margin Maximization Rates for Generic Optimization Methods}},
  booktitle = {Mathematical},
  year = {2025},
  doi = {10.1007/s10107-025-02283-4},
}

Loading related content...

Figure