TL;DR
This paper introduces homotopic initialization, a strategy to significantly speed up the training of dual optimization problems. By first solving a heavily regularized version of the problem and using that solution as a starting point, models can reach near-optimal performance much faster than with standard zero-initialization.
The Problem: Primal vs. Dual Optimization
In machine learning, the speed at which an algorithm finds a "good enough" solution is often more critical than its ultimate asymptotic convergence. While standard techniques like gradient descent are well-understood, their behavior in the early "transient" phase of training varies significantly between primal and dual formulations.
The authors identify a specific imbalance: in primal optimization (optimizing weights directly), a natural property of many datasets—where features with low variance are also less correlated with the target—allows for fast initial progress even with zero initialization. This is known as the "Primal Free Lunch."
However, dual formulations (often used for kernel methods or distributed learning) do not inherit this benefit. Initializing the dual problem at zero often leads to a slow start because the algorithm gets bogged down in directions that contribute little to reducing the overall error.
Methods: Homotopic Initialization
To address the dual bottleneck, the authors propose Homotopic Initialization. Instead of starting from zero, the algorithm follows these steps:
- Pre-train: Solve the optimization problem using an artificially high regularization parameter $\nu$ (e.g., $\nu = 0.25\sqrt{\mu}$).
- Initialize: Use this solution as the starting point for the target optimization with regularization $\mu$.
- Optimize: Run standard algorithms like Gradient Descent (GD) or Random Coordinate Descent (RCDM).
This approach effectively identifies the "coarse" or most important features of the data first, providing a "warm start" that bypasses the slow initial phase of the original dual problem.
Key Insights
The success of this method rests on the concept of $\tau$-bounded response correlation. This mathematical regularity condition explains why certain datasets are easier to optimize: features that are "hard" to learn (those with small eigenvalues) often have low correlation with the labels.
- The Dual Bottleneck: In the dual space, zero-initialization puts the optimizer in a subspace where it must deal with many directions of very low variance simultaneously.
- Deep Learning Connection: The authors suggest that layer-wise pre-training in deep learning works on a similar principle: earlier layers provide a representation that simplifies the final optimization task.
Key Results
Experiments on dual ridge regression and dual SVMs using benchmarks like A9A, COVTYPE, and GISETTE show that homotopic initialization leads to much faster drops in both primal and dual suboptimality compared to zero-initialization. In deep learning contexts, initializing deeper networks with weights from shallower "proxy" versions significantly accelerates initial convergence.
Limitations and Future Work
While effective, the choice of the homotopic parameter $\nu$ remains an empirical heuristic. Additionally, while the theoretical proofs for Generalized Linear Models (GLMs) are robust under certain distributional assumptions, extending these to non-convex deep learning architectures requires further exploration.
Summary updated