Homotopy Continuation for Non-Convex and Non-Smooth Optimization

This direction is split into other directions: homotopy smoothing. Its last version stays readable and citable here.

Version 1 of 1131 papers165 conceptsfrozen 2026-10-04

Optimization is the engine of modern machine learning, but the landscapes it must navigate are often treacherous. Non-convex functions are riddled with poor local minima that trap standard gradient-based solvers, while non-smooth functions create "jagged" surfaces where gradients become unreliable.

Homotopy continuation—also known as graduated optimization—provides a way to bypass these obstacles. Instead of attacking a difficult objective function directly, these methods solve a sequence of problems that start with a simplified, often convex, version of the task and gradually "morph" it into the complex target objective.

The Intuition of Blurring

The core intuition behind homotopy continuation is similar to looking at a complex map through a series of increasingly sharp lenses.

When a non-convex landscape is heavily smoothed (or "blurred"), small local pits and ridges disappear, leaving only the broad, global structure. By finding the minimum of this simplified landscape, an optimizer gains a high-quality starting point. As the smoothing is gradually removed, the algorithm tracks this minimum through a sequence of intermediate problems.

Elad Hazan and Shai Shalev-Shwartz demonstrated in On Graduated Optimization for Stochastic Non-Convex Problems that this process allows solvers to capture the global structure of a landscape before refining the solution in local regions. This mechanism effectively prevents the solver from becoming trapped in the sub-optimal basins of attraction that plague direct optimization.

Mechanisms of Transformation

Researchers employ several distinct strategies to construct these "easier" sequences:

  1. Smoothing Kernels: In tasks like graph matching, Xu Yang uses Gaussian smoothing to transform discrete, NP-complete problems into continuous landscapes. By starting with a high degree of blur and incrementally sharpening the function, the algorithm tracks the global minimum into the original complex landscape Effiecient Graph Matching by Adjacency Matrix Based Model and Gaussian Smoothing Based Optimization.
  2. Regularization Annealing: For inverse problems and matrix completion, the "difficulty" is often controlled by a regularization parameter $\lambda$. Christian Kümmerle and Claudio Mayrink Verdun show that gradually reducing this parameter allows an algorithm to avoid poor local minima by initially optimizing a highly smoothed landscape before sharpening the objective toward the true low-rank solution Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method.
  3. Functional Deformation: In robust learning, the Outlier-Path (OP) algorithm by Shinya Suzumura and Masashi Sugiyama deforms a standard convex Support Vector Machine (SVM) into a non-convex robust version. This acts as a form of simulated annealing, ensuring the solver stays within a high-quality region of the search space as the loss function becomes more sensitive to outliers Homotopy continuation approaches for robust SV classification and regression.

Why It Works: The Warm-Start Effect

The success of homotopy methods relies on the warm-start. Because each sub-problem in the sequence is only a slight perturbation of the previous one, the solution to the "easier" problem serves as an excellent initialization for the "harder" one.

This is particularly powerful for non-smooth optimization. Quoc Tran-Dinh and Volkan Cevher developed frameworks like ASGARD, which dynamically update a smoothing parameter to drive the primal-dual gap to zero. This avoids the "stiff" gradients associated with high-accuracy non-smooth approximations, allowing for faster empirical convergence A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization.

Furthermore, Yi Xu and Tianbao Yang proved that their HOPS algorithm can break the traditional $O(1/\epsilon)$ complexity barrier for non-smooth problems by using this stage-wise smoothing approach, achieving faster rates by exploiting the local "sharpness" of the objective Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/\epsilon).

Homotopy is not limited to non-convexity; it is also a tool for handling "hard" constraints. By treating constraints as penalties and gradually increasing the penalty weight, algorithms like NExOS by Shuvomoy Das Gupta and Bartolomeo Stellato can solve sparse and low-rank problems more accurately than standard convex relaxations Exterior-point Optimization for Sparse and Low-rank Optimization.

In these cases, the continuation path acts as a bridge, guiding the optimizer from a feasible but sub-optimal region into the exact, hard-constrained optimal region without the numerical instability that often accompanies large penalty parameters.

Papers in this version

Showing 60 of 131 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_homotopy_continuation_for_non_convex_and_c0529035,
  title = {Homotopy Continuation for Non-Convex and Non-Smooth Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/homotopy-continuation-for-non-convex-and-non-smooth-optimization/rdr_c0529035a4ff4d0fb045d5f76eddca28},
  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_continuation_for_non_convex_and_c0529035_v1,
  title = {Homotopy Continuation for Non-Convex and Non-Smooth Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/homotopy-continuation-for-non-convex-and-non-smooth-optimization/rdr_c0529035a4ff4d0fb045d5f76eddca28/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}