Accelerating Non-Smooth Optimization via Dual Smoothing

This direction is split into other directions: accelerated dual optimization. Its last version stays readable and citable here.

Version 1 of 168 papers88 conceptsfrozen 2026-10-04

In mathematical optimization, "non-smooth" functions are the jagged peaks and sharp valleys of the landscape. Common tools like the $\ell_1$-norm for sparsity or Total Variation (TV) for image processing are non-differentiable at their "corners." This lack of smoothness is a major bottleneck: while smooth functions can be navigated quickly using accelerated gradient methods, non-smooth functions typically force us into a slow, iterative crawl.

A recurring strategy across recent research is to bypass this jaggedness not by smoothing the problem directly, but by stepping into the Dual Space. By reformulating a non-smooth primal problem into a smooth dual counterpart, researchers can unlock Nesterov-style acceleration, turning slow $O(1/\epsilon)$ or $O(1/\sqrt{T})$ convergence into much faster $O(1/\sqrt{\epsilon})$ or $O(1/T)$ rates.

The Geometry of the Dual Mirror

To understand why this works, we must look at the relationship between a function and its Fenchel conjugate (the dual). There is a fundamental mathematical symmetry at play: strong convexity in the primal space creates smoothness in the dual space.

If a primal objective function is "strongly convex"—meaning it has a minimum curvature and doesn't flatten out—its dual function is guaranteed to have a Lipschitz-continuous gradient. As Ankan Saha, Xinhua Zhang, and S. V. N. Vishwanathan demonstrate in Lower Bounds for BMRM and Faster Rates for Training SVMs, exploiting this Lipschitz continuity allows us to apply accelerated gradient techniques to problems that appear non-smooth in their original form. This transformation shifts the optimization to a smooth dual space, fundamentally changing the complexity class of the solver.

Smoothing via Primal Augmentation

What if the primal problem isn't strongly convex? This is common in sparse recovery, where the $\ell_1$-norm is convex but "flat" in many directions. The solution, as explored by Ming‐Jun Lai and Wotao Yin in Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm, is to add a tiny amount of "augmentation"—usually a squared $\ell_2$ or Frobenius norm.

This "aggressive smoothing" (a term used by John J. Bruer and Volkan Cevher in Time-Data Tradeoffs by Aggressive Smoothing) forces the primal to be strongly convex. Consequently, the dual becomes differentiable and smooth. This allows first-order methods to achieve high-precision solutions much more efficiently than primal-space methods that must struggle with non-differentiable points directly.

Bridging the Primal-Dual Gap

The challenge of dual methods is that we ultimately care about the primal solution (the actual image, the model weights, or the robot trajectory). Quoc Tran-Dinh and Volkan Cevher have developed several frameworks, such as ASGARD and SAMA, to manage this transition.

In A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, they introduce a "homotopy" approach. Instead of picking a single smoothing parameter, the algorithm dynamically updates the smoothing and step-size parameters. This drives the "primal-dual gap"—the difference between the upper bound of the primal and the lower bound of the dual—to zero at the best possible theoretical rate.

Scaling to Trillions of Variables

This dual-smoothing approach isn't just a theoretical curiosity; it is a necessity for "extreme-scale" problems. In ECLIPSE: An Extreme-Scale Linear Program Solver for Web-Applications, Kinjal Basu and colleagues show that for web-scale linear programs with trillions of variables, traditional second-order solvers (like interior-point methods) fail because they cannot handle the massive matrix factorizations required.

By applying a quadratic perturbation to the linear program, they transform the dual into a smooth objective. This allows them to use simple, parallelizable first-order gradient methods that avoid memory-intensive operations, making it possible to solve problems that were previously computationally impossible.

Broad Applications: From RL to Vision

The versatility of this mechanism is evident in its wide range of applications:

By treating non-smoothness as a representational hurdle rather than an inherent limitation, this research direction provides a unified path toward faster, more scalable optimization across the machine learning landscape.

Papers in this version

Showing 60 of 68 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_non_smooth_optimization_via_9c1856f7,
  title = {Accelerating Non-Smooth Optimization via Dual Smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-non-smooth-optimization-via-dual-smoothing/rdr_9c1856f77d804183b9c2339717082c6d},
  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_non_smooth_optimization_via_9c1856f7_v1,
  title = {Accelerating Non-Smooth Optimization via Dual Smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-non-smooth-optimization-via-dual-smoothing/rdr_9c1856f77d804183b9c2339717082c6d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}