When training classifiers on separable data, we don't just want any solution that separates the classes; we want the "maximum margin" solution. This solution, famously championed by Support Vector Machines, offers the best generalization by staying as far from the data points as possible. While standard Gradient Descent (GD) eventually converges to this margin, it does so at a glacial, logarithmic pace.
Recent research reveals that this "speed limit" is not a property of the optimization problem itself, but a consequence of using fixed or poorly scaled learning rates. By employing time-varying learning rate schedules—specifically those that grow or adapt over time—we can accelerate convergence from logarithmic to polynomial or even exponential rates.
The Logarithmic Speed Limit
For many loss functions like cross-entropy, the gradient vanishes as the model becomes more confident. In the late stages of training on separable data, the weights grow in magnitude to push the loss toward zero, but their direction—which determines the margin—changes very slowly.
Subutai Ahmad, Gerald Tesauro, and Yu He observed in Asymptotic Convergence of Backpropagation: Numerical Experiments that backpropagation typically settles into a $1/t$ error decay. They noted that this limit is tied to the fixed learning rate; by increasing the learning rate linearly over time, they could shift the convergence rate to $1/t^2$. This early insight suggested that the "asymptotic regime" of a neural network is highly sensitive to the step-size schedule.
Breaking the Limit with Aggressive Steps
To reach the maximum margin faster, the optimizer must counteract the vanishing gradient. One way to do this is to use "aggressive" step sizes that grow over time.
Matus Telgarsky demonstrated in Characterizing the implicit bias via a primal-dual analysis that while constant step sizes lead to slow convergence, schedules that grow over time accelerate the alignment of the weight direction with the optimal margin. Building on this, Guanghui Wang and colleagues in Faster Margin Maximization Rates for Generic Optimization Methods showed that using step sizes proportional to the iteration count $t$ can achieve quadratic convergence rates toward the margin.
The intuition is simple: as the gradient gets smaller, the step size gets larger to compensate. This keeps the "velocity" of the weight direction updates high enough to reach the optimal hyperplane in polynomial time rather than exponential time.
Why Adaptive Optimizers Win
This theoretical framework helps explain the empirical success of adaptive optimizers like Adam. In The Implicit Bias of Adam on Separable Data, Chenyang Zhang and Difan Zou prove that Adam's update mechanism naturally facilitates polynomial-time convergence to the maximum margin. Unlike standard GD, which requires an exponentially increasing number of iterations to refine the margin, Adam’s adaptive scaling allows it to navigate the loss landscape more efficiently, reaching high-precision solutions much faster.
Similarly, Tuo Zhao and Yan Li showed in Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data that aggressive step-size schemes in proximal algorithms provide an exponential speedup in loss convergence. They linked the quality of the resulting margin directly to the "condition number" of the divergence function used, suggesting that the geometry of the optimizer is just as important as the schedule.
Proximal Perspectives and Stability
If increasing step sizes is so effective, why don't they cause the algorithm to diverge? The answer lies in how these schedules interact with the underlying optimization geometry.
Kwangjun Ahn provides a unifying view in Understanding Nesterov's Acceleration via Proximal Point Method. Ahn shows that Nesterov’s acceleration can be seen as an approximation of the Proximal Point Method. This perspective justifies using step sizes that grow linearly with $t$: the algorithm is essentially balancing a lower-function approximation (to move fast) with an upper-function approximation (to stay stable).
This balance is also evident in CRAMMA, a family of algorithms introduced by John Shawe-Taylor and Petroula Tsampouka. CRAMMA keeps an "effective" learning rate constant but gradually relaxes the misclassification criteria (the margin threshold). This relaxation acts as a proxy for a time-varying schedule, allowing the algorithm to converge to the optimal hyperplane significantly faster than traditional iterative methods like the Perceptron.
Designing the Optimal Schedule
The goal of these schedules is often to reach the "asymptotic regime"—the phase where the model has identified the correct neighborhood of the solution and is just refining it—as quickly as possible.
In the context of large-scale learning, Wei Xu proposed in Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent a specific polynomial learning rate schedule: $\eta_t = \eta_0(1 + a\eta_0t)^{-c}$. By carefully choosing the exponent $c$ (e.g., $2/3$ or $3/4$), Xu showed that Averaged SGD can reach its optimal region in just a single pass over the data.
Similarly, Chung-En Tsai and Yen-Huan Li found in Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging that starting with high initial learning rates and decaying them over time allows for rapid initial progress across the search space, which is critical for complex losses like the logarithmic loss used in quantum computing and medical imaging.
By moving away from fixed learning rates and toward schedules that account for the evolving geometry of the loss surface, these researchers have turned margin maximization from a slow, asymptotic process into a fast, predictable one.