Accelerating Optimization for Non-Smooth and Non-Convex Objectives

This direction is split into other directions: non-smooth optimization complexity. Its last version stays readable and citable here.

Version 1 of 1134 papers134 conceptsfrozen 2026-10-04

In the ideal world of convex optimization, we have a "speed limit" that is remarkably fast. If a function is smooth and strongly convex, algorithms like Nesterov’s Accelerated Gradient Descent (AGD) can converge to the global optimum at a linear rate. However, modern machine learning rarely lives in this ideal world. We often face "kinky" (non-smooth) loss functions like SVM hinges or L1 penalties, and "treacherous" (non-convex) landscapes like those found in deep neural networks or matrix factorization.

For years, the standard wisdom was that these difficulties imposed a heavy tax: non-smooth problems were relegated to slow subgradient methods, and non-convex problems were stuck with a $O(1/\epsilon^2)$ convergence rate to find even a simple stationary point. A growing body of research is now breaking these barriers, finding ways to "borrow" the speed of convex optimization for the messy reality of non-convex and non-smooth functions.

The Smoothing Strategy: Softening the Kinks

The primary challenge with non-smooth functions—such as the hinge loss in Support Vector Machines—is that they lack a defined gradient at certain points. Standard subgradient methods are notoriously slow, often requiring $O(1/\epsilon^2)$ iterations to reach high precision.

To bridge this gap, researchers like Alexander G. Gray and Hua Ouyang in Stochastic Smoothing for Nonsmooth Minimizations propose a "smoothing" approach. By approximating a non-smooth function with a smooth surrogate that gradually becomes more precise over time, they can apply acceleration techniques. This allows them to achieve the theoretically optimal $O(1/t)$ rate for strongly convex problems, significantly outperforming standard Stochastic Gradient Descent.

This concept extends to complex structural problems as well. Stephen Gould and Vladimir Jojic applied Nesterov’s smoothing to dual decomposition in Accelerated dual decomposition for MAP inference, turning a non-smooth inference problem into a smooth one. This transformation yielded a quadratic speedup, moving from $O(1/\epsilon^2)$ to $O(1/\epsilon)$ guarantees.

Convex Until Proven Guilty: Navigating Non-Convexity

In non-convex landscapes, the fear is getting stuck in local minima or wandering aimlessly in flat regions. Traditional gradient descent is "blind" to the underlying curvature, leading to slow convergence.

The "Convex Until Proven Guilty" framework, introduced by Yair Carmon, John C. Duchi, and colleagues in their 2017 paper, offers a clever workaround. Their algorithm runs accelerated gradient descent as if the function were convex. If the algorithm makes progress, it continues; if it fails to progress, it has effectively found a "certificate of non-convexity" (negative curvature). The algorithm then uses this information to take a massive leap toward a local minimum, effectively accelerating past the bottlenecks that slow down standard methods.

Similarly, Naman Agarwal, Brian Bullins, and Tengyu Ma developed FastCubic in Finding Approximate Local Minima Faster than Gradient Descent. By approximating second-order "Cubic Regularization" using only Hessian-vector products, they broke the $1/\epsilon^2$ efficiency barrier for high-dimensional problems without the prohibitive cost of computing a full Hessian matrix.

Variance Reduction: Cleaning the Stochastic Signal

When optimization is stochastic (using minibatches of data), "noise" becomes a major bottleneck. Even if the underlying function is smooth, the variance in gradient estimates forces the algorithm to use smaller step sizes, slowing convergence.

The PAGE algorithm, introduced by Zhize Li, Peter Richtárik, and others in PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization, solves this using a probabilistic switch. It occasionally computes a full gradient but mostly performs cheap, recursive adjustments to previous gradients. This simple mechanism achieves the theoretical "speed limit" for non-convex optimization, matching optimal convergence rates while remaining practical for deep learning.

For non-smooth finite-sum problems, Chaobing Song proposed VRPDA$^2$ in Variance Reduction via Primal-Dual Accelerated Dual Averaging. By combining variance reduction with a primal-dual framework, the algorithm makes the optimization cost independent of the dataset size ($n$) once a certain accuracy is reached, a feat previously thought difficult for non-smooth objectives.

Structure as an Accelerator: Initialization and Decoupling

Sometimes, the secret to speed isn't just the update rule, but how we frame the problem or start the search.

In the realm of matrix factorization, Bingcong Li, Niao He, and colleagues demonstrated in On the Crucial Role of Initialization for Matrix Factorization that Nyström initialization allows Scaled Gradient Descent to achieve quadratic convergence. This is a massive leap over the linear rates typically expected in non-convex settings.

Furthermore, the success of Batch Normalization (BN) was theoretically illuminated by Hadi Daneshmand and Thomas Hofmann in Exponential convergence rates for Batch Normalization. They proved that BN accelerates training by decoupling the length and direction of weight vectors. This structural change allows gradient descent to achieve exponential (linear) convergence rates even in non-convex landscapes where standard methods would struggle with sub-linear progress.

Summary of the Shift

The research direction across these 117 papers signals a fundamental shift in optimization:

  1. From Sub-linear to Linear/Quadratic: Moving past the $O(1/\epsilon^2)$ and $O(1/\sqrt{k})$ barriers by exploiting local structure.
  2. From First-Order to "First-Order Plus": Using Hessian-vector products or momentum-based "certificates" to gain second-order benefits without second-order costs.
  3. From Smoothness as a Requirement to Smoothing as a Tool: Treating non-smoothness not as a dead end, but as a temporary state to be managed via surrogates.

By combining these techniques, the field is moving toward a unified framework where the "difficulty" of an optimization problem is defined less by its non-convexity or non-smoothness and more by our ability to exploit its underlying geometric structure.

Papers in this version

Showing 60 of 134 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_accelerating_optimization_for_non_smooth_989c93f3,
  title = {Accelerating Optimization for Non-Smooth and Non-Convex Objectives},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-optimization-for-non-smooth-and-non-convex-objectives/rdr_989c93f38db64ce18e46738a82eb3ddc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_accelerating_optimization_for_non_smooth_989c93f3_v1,
  title = {Accelerating Optimization for Non-Smooth and Non-Convex Objectives},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-optimization-for-non-smooth-and-non-convex-objectives/rdr_989c93f38db64ce18e46738a82eb3ddc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}