Generalizing Fast Stochastic Optimization Beyond Quadratic Losses

28 concepts26 papers1 proposal

In machine learning theory, the squared loss function (or least-squares regression) is the ultimate comfort zone. When an optimization landscape is quadratic, it behaves like a perfectly symmetrical, predictable bowl. The curvature (the Hessian matrix) is constant everywhere, meaning that no matter where you stand, the landscape looks structurally identical.

This mathematical predictability has allowed theorists to design incredibly fast, aggressive optimization algorithms. We can accelerate gradients to forget initial conditions rapidly, compress datasets using random projections, and update parameters one coordinate at a time with rigorous convergence guarantees.

However, real-world machine learning rarely lives inside this perfect bowl. Modern classification tasks rely on non-quadratic loss functions—such as logistic loss, cross-entropy, and softmax—where the curvature changes dynamically with every step. When we try to deploy our fastest algorithms in these non-quadratic landscapes, the theoretical guarantees often vanish. Bridging this gap—extending the gold-standard convergence rates of quadratic optimization to general smooth, non-quadratic losses—is one of the most active frontiers in optimization theory.

The Algorithmic Breakthroughs Locked in Least Squares

To understand why non-quadratic losses pose such a challenge, we must first look at the powerful algorithmic mechanisms that are currently "locked" within the quadratic regime.

1. Nesterov-Style Acceleration

Standard Stochastic Gradient Descent (SGD) is statistically robust but notoriously slow at forgetting its starting point. To fix this, researchers use acceleration techniques (like momentum) to speed up convergence. In the quadratic setting, Prateek Jain et al. demonstrated in Accelerating Stochastic Gradient Descent for Least Squares Regression. that accelerated SGD can be made highly robust to stochastic noise, achieving minimax optimal risk much faster than standard SGD.

Similarly, Aditya Vardhan Varre et al. showed in Accelerated SGD for Non-Strongly-Convex Least Squares how acceleration eliminates initial bias at an optimal rate. Yet, both frameworks explicitly note that these proofs break down when moving to smooth, non-quadratic functions like logistic regression, because the changing curvature introduces unstable interactions with the stochastic noise.

2. Randomized Sketching and Preconditioning

When datasets are massive, we often use "sketching"—multiplying the data matrix by a random projection matrix to compress its dimensionality. Mert Pilanci et al. provided sharp geometric guarantees for this technique in Randomized Sketches of Convex Programs with Sharp Guarantees, but the analysis relies heavily on the objective being quadratic.

When sketching is used to precondition stochastic variance-reduced gradients—as explored by Alon Gonen et al. in Solving Ridge Regression using Sketched Preconditioned SVRG—the speedups are massive, but the mathematical machinery remains bound to the structural properties of ridge regression.

3. Coordinate and Row-Based Sampling

Instead of computing gradients for the entire dataset, algorithms like Randomized Coordinate Descent (RCD) or Randomized Kaczmarz (RK) update models by looking at single coordinates or rows. Aaditya Ramdas provided a unified perspective on these solvers in Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?, showing their complementary strengths in solving linear systems.

Furthermore, Donghwa Kim et al. proved in Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent that sampling coordinates without replacement (random permutations) is strictly faster than uniform sampling. However, proving this benefit requires the exact, rigid geometry of positive-definite quadratics; how these ordering strategies behave on a shifting logistic landscape remains an open question.

Why Shifting Curvature Breaks the Machinery

Why does changing curvature cause such a profound theoretical breakdown? The core issue boils down to how algorithms control error and step sizes.

In a quadratic loss function, the gradient is a linear function of the parameters. If you take a step, the change in the gradient is perfectly proportional to the step size, scaled by the fixed Hessian. This linearity allows researchers to derive tight, fast convergence rates. For instance, Nicolas Flammarion et al. proved a fast $O(1/n)$ convergence rate for unregularized stochastic composite optimization in Stochastic Composite Least-Squares Regression with Convergence Rate O(1/n), but the proof relies entirely on the constant curvature of least squares to bound the distance to the optimum.

When the loss is non-quadratic, the Hessian becomes state-dependent. As the algorithm moves, the landscape can flatten out (losing strong convexity) or become suddenly steep. This introduces several complications:

  • Uncontrolled Variance in Second-Order Methods: In distributed optimization, Newton-type methods can suffer from "Hessian inversion bias" when local estimates of the curvature are averaged. While Fangzhao Zhang et al. developed an elegant shrinkage correction to fix this in Optimal Shrinkage for Distributed Second-Order Optimization, they noted that in highly non-linear landscapes, the variance increases, requiring further tuning for non-quadratic objectives.
  • Step-Size Instability: Algorithms that use large, aggressive step sizes to achieve fast learning rates without explicit regularization—such as the nonparametric stochastic approximation analyzed by Aymeric Dieuleveut et al. in Nonparametric stochastic approximation with large step-sizes—rely on the squared loss to ensure that large steps don't cause the iterates to diverge. For non-quadratic losses, maintaining these optimal rates typically requires complex, computationally expensive second-order updates.
  • Last-Iterate Convergence: Most stochastic optimization theory bounds the average of all visited models, but practitioners care about the last iterate. While Amit Attia et al. established near-optimal last-iterate convergence rates for greedy step sizes in Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime, their framework is restricted to linear regression due to the lack of unified tools for handling changing curvature in stochastic settings.

This limitation echoes across many other specialized domains, including low-rank matrix estimation (Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation), atomic norm regularization (Fast column generation for atomic norm regularization), and stochastic AUC maximization (Fast Stochastic AUC Maximization with O(1/n)-Convergence Rate).

Pathways to Generalization

To break out of the quadratic cage, researchers are developing new mathematical frameworks that can handle variable curvature without sacrificing fast convergence rates.

Quadratic Loss (Least Squares)          Self-Concordant Loss (Logistic/Softmax)
       Hessian is Constant                      Hessian varies, but changes predictably
         |                                            |
         v                                            v
  [Standard Acceleration]                     [Iterative Regularization]
  (Breaks if curvature changes)               (Controls curvature locally)

One of the most successful approaches leverages the property of self-concordance. A function is self-concordant if its third derivative is bounded by its second derivative. This means that while the curvature changes, it changes predictably and smoothly.

In Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization, Gaspard Beugnot et al. utilized this property to break through traditional learning rate limits. Standard ridge regularization suffers from a "saturation effect" that prevents it from achieving fast convergence on easy tasks. The authors proved that by using Iterative Tikhonov regularization (essentially a proximal point algorithm), one can achieve optimal, fast learning rates for a broad class of non-quadratic, self-concordant losses—including logistic and softmax functions. By solving a sequence of localized problems, the algorithm prevents the changing curvature from destabilizing the optimization process.

Another path involves generalizing structural properties like "restricted strong convexity" to non-quadratic settings. For example, Reza Eghbali et al. demonstrated in Decomposable norm minimization with proximal-gradient homotopy algorithm that a homotopy algorithm can achieve global linear convergence for structured recovery problems without strong convexity, laying the groundwork for extending norm-minimization proofs beyond the squared loss.

Ultimately, the goal of this research direction is to ensure that the algorithmic tools we rely on in practice—whether they are multi-pass SGD schemes (Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes) or conservative online updates (Efficient Online Learning for Large-Scale Sparse Kernel Logistic Regression)—can be deployed on any smooth objective function with the same mathematical confidence we have enjoyed for decades in least-squares regression.

Key Foundational Work

Unifying Framework for Fast Learning Rate of Non-Sparse Multiple Kernel Learning (2011) — contributed 1 concept elements to this direction.
Efficient Online Learning for Large-Scale Sparse Kernel Logistic Regression (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_loss_function_specificity_52e0e3c8,
  title = {loss function specificity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/loss-function-specificity/rdr_52e0e3c8ef87419a882acf268b704237},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_loss_function_specificity_52e0e3c8_v1,
  title = {loss function specificity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/loss-function-specificity/rdr_52e0e3c8ef87419a882acf268b704237/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake