Homotopy Smoothing for Non-Smooth Optimization

29 concepts24 papers1 proposal

Many core problems in machine learning and optimization involve functions that are non-smooth—meaning they have sharp kinks, corners, or discontinuous gradients. Examples abound: the $\ell_1$-norm used for sparse recovery, the hinge loss in Support Vector Machines, Total Variation penalties in image processing, and indicator functions that represent hard constraints.

Optimizing these functions directly is notoriously slow. While smooth functions can be minimized rapidly using accelerated gradient methods at a rate of $\mathcal{O}(1/\sqrt{\varepsilon})$, non-smooth functions typically force us to rely on subgradient methods, which crawl at a rate of $\mathcal{O}(1/\varepsilon^2)$, or standard proximal methods operating at $\mathcal{O}(1/\varepsilon)$.

To bridge this gap, researchers often turn to smoothing techniques (such as Nesterov smoothing or Moreau envelopes) to approximate the jagged function with a differentiable surrogate. However, smoothing introduces a frustrating Catch-22. Homotopy smoothing—also known as the continuation method—resolves this paradox by dynamically shifting the optimization landscape during training.

The Catch-22 of Fixed Smoothing

To understand why homotopy smoothing is necessary, consider what happens when we apply a fixed smoothing parameter, $\mu > 0$, to a non-smooth function like an absolute value corner. The parameter $\mu$ controls the window of deformation: a large $\mu$ creates a wide, gentle curve, while a small $\mu$ keeps the approximation tight and accurate.

   Fixed Large μ (Blunt)              Fixed Small μ (Sharp)
       \           /                      \       |       /
        \         /                        \     / \     /
         \_______/                          \___/   \___/
     Easy to optimize,                      Accurate, but tiny
     but high residual error.               steps cause stagnation.

If we want our final solution to be within $\varepsilon$ accuracy of the true non-smooth optimum, we are forced to choose a very small $\mu = \mathcal{O}(\varepsilon)$. But as $\mu$ approaches zero, the derivative of our smooth approximation changes more and more abruptly near the kink. Mathematically, the Lipschitz constant of the gradient explodes at a rate of $L_\mu = \mathcal{O}(1/\mu)$.

Because the maximum stable step size for gradient descent is inversely proportional to this Lipschitz constant ($\eta \le 1/L_\mu$), a tiny $\mu$ forces the algorithm to take infinitesimally small steps. If we plug an exploding $L_\mu = \mathcal{O}(1/\varepsilon)$ into an accelerated gradient method, the overall iteration complexity degrades back to $\mathcal{O}(1/\varepsilon)$. We have gone through the trouble of smoothing our function, yet we are no faster than traditional non-smooth methods.

The Homotopy Solution: Stage-Wise Refinement

Homotopy smoothing breaks this barrier by refusing to settle on a single value for $\mu$. Instead, it solves a continuous sequence of optimization problems, gradually morphing a highly smoothed, easily optimized objective into the true, sharp target function.

The optimization process is divided into stages:

  1. Start Coarse: Begin with a large smoothing parameter $\mu_0$. The landscape is blunt, meaning the Lipschitz constant $L_{\mu_0}$ is small. The optimizer can take massive, aggressive steps to rapidly find the neighborhood of the minimum.
  2. Sharpen: Once progress slows, decrease the parameter to $\mu_1 < \mu_0$. The landscape becomes sharper and more accurate, but the Lipschitz constant increases.
  3. Warm-Start: Crucially, do not restart the optimization from scratch. Instead, initialize the new stage using the final solution of the previous stage as a warm start.

By repeating this cycle, the algorithm tracks the moving optimum across a sequence of increasingly precise approximations. As shown by Yi Xu et al. in Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/\epsilon), this strategy breaks the traditional complexity barrier, achieving faster convergence rates by exploiting the local sharpness of the objective function.

Why Warm-Starts Neutralize the Penalty

The core reason this strategy works lies in the geometry of the warm start.

When we transition from a coarse stage to a sharper stage, the Lipschitz constant $L_\mu$ increases, which dictates that our step size must shrink. In a naive optimization run, a smaller step size means taking more iterations to cover the distance to the goal.

However, because the previous stage already brought us to the approximate minimum of a very similar function, the distance from our warm-start initialization to the new stage's optimum is incredibly small. The shrinking distance to travel perfectly counterbalances the shrinking step size.

The authors of Fast Nonsmooth Regularized Risk Minimization with Continuation and Tianyi Zhou et al. in NESVM: a Fast Gradient Method for Support Vector Machines demonstrate that this sequence of warm starts minimizes the total computational effort. The penalty of an exploding smoothness constant is effectively neutralized because the optimizer only needs to perform minor local adjustments in the later, sharper stages.

This principle applies equally well to dual variables. For instance, Xiaohan Wei et al. in Solving Non-smooth Constrained Programs with Lower Complexity than \mathcal{O}(1/\varepsilon): A Primal-Dual Homotopy Smoothing Approach utilize a multi-stage framework where dual variables are passed forward. This allows the algorithm to exploit local dual structure and achieve faster convergence for distributed non-smooth problems.

Handling Constraints as Smooth Penalties

The utility of homotopy smoothing extends far beyond loss functions like the structural hinge loss (Krishna Pillutla et al., A Smoother Way to Train Structured Prediction Models) or structured sparsity penalties (Fouad Hadj-Selem et al., Continuation of Nesterov's Smoothing for Regression With Structured Sparsity in High-Dimensional Neuroimaging). It serves as a powerful mechanism for solving heavily constrained optimization problems.

In large-scale optimization, enforcing hard constraints at every iteration can be computationally prohibitive, often requiring expensive projections. Homotopy smoothing allows researchers to convert hard constraints into differentiable penalty functions that are gradually tightened over time.

   Stage 1: Soft Penalty             Stage 2: Moderate Penalty           Stage 3: Hard Constraint
      _..---''---.._                         _..---''---.._                         |
    /                \                     /       |        \                       |
   /                  \                   /        |         \                      |
  |     Feasible       |                 |     Feasible       |            Feasible |
  \   (Loose Bound)    /                 \   (Tighter Bound)  /                     |
   ^.._            _..^                   ^.._            _..^                      |
       ''---..---''                           ''---..---''                          |

This approach is highly effective in projection-free frameworks like the Frank-Wolfe (Conditional Gradient) method:

By pairing this dynamic tightening with coordinate descent (Ahmet Alacaoglu et al., Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization) or Augmented Lagrangian methods (Peixuan Zhang et al., A Smoothed Augmented Lagrangian Framework for Convex Optimization with Nonsmooth Constraints), the homotopy strategy maintains numerical stability in early iterations while enforcing exact constraint satisfaction at convergence.

Generalizing Beyond Convexity

While primarily leveraged to accelerate convex optimization, the intuition behind homotopy smoothing extends to non-convex landscapes and physical systems. Here, the smoothing parameter acts as a regularizer that filters out high-frequency local minima, creating a simplified landscape that guides the optimizer toward a high-quality global region.

For example, Axel Böhm in Variable Smoothing for Weakly Convex Composite Functions applies variable smoothing via Moreau envelopes to non-convex, non-smooth functions, finding a complexity sweet spot between smooth and subgradient methods. Similarly, Miguel Simões et al. in Lasry-Lions Envelopes and Nonconvex Optimization: A Homotopy Approach utilize Lasry-Lions double envelopes to transform highly jagged, non-convex functions into smooth surrogates, gradually sharpening them to find superior local or global optima.

This philosophy is mirrored in classical continuation methods for physical systems. Amritanshu Pandey et al. in Incremental Model Building Homotopy Approach for Solving Exact AC-Constrained Optimal Power Flow solve highly non-convex power grid equations by starting from a trivial, easily solvable grid model and incrementally tracing a continuous path to the true, complex system state. Even in classical matrix decomposition, as shown by John Wright et al. in Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization, solving a sequence of problems with decreasing regularization parameters accelerates convergence and preserves numerical stability.

Ultimately, homotopy smoothing works because it aligns the computational effort with the difficulty of the problem. It expends cheap, large-step iterations on a blunt approximation to get close to the answer, saving the expensive, fine-grained adjustments for the very end.

Key Foundational Work

A smoothing heuristic for a bilevel pricing problem (2005) — contributed 1 concept elements to this direction.
Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization (2009) — 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_homotopy_smoothing_e0028135,
  title = {homotopy smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/homotopy-smoothing/rdr_e0028135435541bca7494a32dde15095},
  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_homotopy_smoothing_e0028135_v1,
  title = {homotopy smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/homotopy-smoothing/rdr_e0028135435541bca7494a32dde15095/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake