Optimization in machine learning often presents a frustrating paradox. We want to solve complex, non-convex, or non-smooth problems, but our most reliable mathematical tools—such as Newton's method or gradient descent—work best when the landscape is smooth and convex. If we initialize these algorithms blindly in a rugged landscape, they quickly get trapped in poor local minima or stall due to ill-conditioning.
Homotopy continuation resolves this paradox by transforming a single, intractable optimization problem into a continuous sequence of manageable subproblems. Instead of tackling the target objective directly, we start with a simplified version of the problem whose global minimum is easy to find. By introducing a continuation parameter, we gradually deform this simple landscape into the complex target landscape, tracking the optimal solution along the way.
The Core Mechanism: Deforming the Landscape
To understand why homotopy continuation works, imagine trying to find the lowest point in a rugged mountain range shrouded in thick fog. Direct gradient descent is like walking downhill blindly; you will almost certainly get stuck in the first shallow valley you encounter.
Homotopy continuation clears the fog by changing the landscape itself. We define a path-following function controlled by a parameter $\lambda$. When $\lambda$ is large, the objective function is heavily regularized or smoothed, washing away the rugged terrain and leaving a single, easily discoverable global minimum. As we systematically decrease $\lambda$ toward our target value, the landscape gradually morphs back into the original terrain.
Crucially, the solution found at $\lambda_k$ serves as the starting point (a "warm start") for the problem at $\lambda_{k+1}$. Because the landscape changes incrementally, the optimal solution moves only a small distance. The optimizer remains trapped within the moving region of attraction of the global optimum, riding the wave all the way to the target destination.
Escaping Local Minima in Nonconvex Landscapes
In nonconvex optimization, the primary enemy is the proliferation of sub-optimal local minima. By starting with a highly regularized or smoothed state, continuation methods structurally alter the optimization landscape to eliminate these traps.
For example, in semi-supervised Support Vector Machines, the non-convexity of the loss function makes direct optimization highly sensitive to initialization. Olivier Chapelle in A continuation method for semi-supervised SVMs demonstrates that starting with a smoothed, convex approximation of the loss function allows the algorithm to find an initial global minimum. By tracking this minimum while gradually reducing the smoothing parameter, the algorithm bypasses the sub-optimal local minima that typically ensnare standard gradient-based search methods.
This mechanism is equally vital in solving ill-posed inverse problems. Tianci Liu et al. show in Optimization for Amortized Inverse Problems that following a continuous path of optimal solutions from a simple maximum likelihood estimate to a fully regularized posterior provides theoretical guarantees for reaching high-quality minima. Rather than forcing the optimizer to navigate a treacherous landscape all at once, the sequential morphing transforms a blind search into a guided path-following exercise.
Exploiting Effective Strong Convexity in Sparse Optimization
Homotopy continuation is not only useful for escaping local minima; it also provides massive computational speedups for convex but non-smooth problems, such as $\ell_1$-regularized least squares (Lasso). Standard proximal gradient methods often crawl to a halt on these problems because the global objective lacks strong convexity, leading to slow, sublinear convergence rates.
Lin Xiao et al. resolve this bottleneck in A Proximal-Gradient Homotopy Method for the L1-Regularized Least-Squares Problem. By geometrically decreasing the regularization parameter from a large initial value, they ensure that the intermediate solutions along the path remain highly sparse. This sparsity restricts the optimization to a low-dimensional subspace where the objective function exhibits restricted strong convexity. Operating within this favorable subspace unlocks global geometric convergence rates, turning a traditionally slow optimization into an exponential speedup.
To maximize this efficiency, Qihang Lin et al. introduced an adaptive restarting scheme in An Adaptive Accelerated Proximal Gradient Method and its Homotopy Continuation for Sparse Optimization. Their method automatically estimates the local strong convexity parameters along the path, achieving a "square-root" speedup in iteration complexity. The continuation path acts as a guardrail, keeping the iterates strictly within a low-complexity regime and preventing the algorithm from wandering into flat, computationally expensive regions of the search space.
Path-Following Mechanics: Predictor-Corrector Dynamics
How do we numerically trace this continuous path without the prohibitive cost of re-solving the optimization problem from scratch at hundreds of discrete steps? The answer lies in predictor-corrector numerical continuation.
As the continuation parameter varies, the optimal solution traces a continuous curve in the joint space of parameters and variables. Instead of treating each step independently, we can use the geometry of the current solution to project where the next solution will land:
- The Predictor Step: By taking the derivative of the optimality conditions with respect to the continuation parameter, we find the tangent vector of the solution path. We take a step along this tangent line to predict the next solution.
- The Corrector Step: Because the true solution path is often curved, the predictor step will inevitably drift away from the exact path. We then apply a few iterations of a second-order method (like Newton's method) to snap the predicted point back onto the true solution curve.
Saharon Rosset analyzes this behavior in Following Curved Regularized Optimization Solution Paths, demonstrating that incremental Newton-Raphson updates can track highly curved, non-linear solution trajectories while maintaining a strict theoretical bound on the tracking error. Furthermore, Bennet Gebken details this structure in On the structure of regularization paths for piecewise differentiable regularization terms, showing how the tangent space of the optimality conditions can be systematically exploited to map out the entire path efficiently, eliminating redundant computations.
From Grid Search to Continuous Path Learning
Beyond its role as an optimization accelerator, tracking the continuation path fundamentally changes how we approach hyperparameter tuning. Traditional machine learning relies on discrete grid search—evaluating a model at a handful of predefined regularization strengths—which is computationally wasteful and risks missing the optimal setting between grid lines.
Path-following algorithms solve this by mapping out the entire continuous regularization path in a single sweep. Shinya Suzumura leverages this property in Outlier Path: A Homotopy Algorithm for Robust SVM to trace model parameters across all possible hyperparameter values smoothly, preventing the erratic jumps between local minima common in discrete evaluations and ensuring the absolute best model configuration is found.
Taking this concept to its logical conclusion, Qiran Dong et al. propose in Beyond Discretization: Learning the Optimal Solution Path to parameterize the entire solution path as a global object using a linear combination of basis functions. Instead of tracking the path step-by-step, they learn the continuous function representing the path all at once. This allows every gradient update to share information globally across all hyperparameter values, completely bypassing the need for step-by-step discretization and redefining how regularized models are trained.