A Saddle Point Remedy: Power of Variable Elimination in Non-convex Optimization
This work addresses a foundational bottleneck in large-scale ML optimization, offering a principled explanation that could lead to more robust algorithms, though it is incremental as it builds on existing variable elimination methods.
The paper tackled the problem of saddle points hindering non-convex optimization in machine learning by analyzing variable elimination algorithms, proving they transform saddle points into local maxima to improve convergence, with validation on deep Residual Networks showing dramatic stability and performance gains.
The proliferation of saddle points, rather than poor local minima, is increasingly understood to be a primary obstacle in large-scale non-convex optimization for machine learning. Variable elimination algorithms, like Variable Projection (VarPro), have long been observed to exhibit superior convergence and robustness in practice, yet a principled understanding of why they so effectively navigate these complex energy landscapes has remained elusive. In this work, we provide a rigorous geometric explanation by comparing the optimization landscapes of the original and reduced formulations. Through a rigorous analysis based on Hessian inertia and the Schur complement, we prove that variable elimination fundamentally reshapes the critical point structure of the objective function, revealing that local maxima in the reduced landscape are created from, and correspond directly to, saddle points in the original formulation. Our findings are illustrated on the canonical problem of non-convex matrix factorization, visualized directly on two-parameter neural networks, and finally validated in training deep Residual Networks, where our approach yields dramatic improvements in stability and convergence to superior minima. This work goes beyond explaining an existing method; it establishes landscape simplification via saddle point transformation as a powerful principle that can guide the design of a new generation of more robust and efficient optimization algorithms.