Abstract
We study constrained nonconvex optimization problems in machine learning, signal processing, and stochastic control. It is well-known that these problems can be rewritten to a minimax problem in a Lagrangian form. However, due to the lack of convexity, their landscape is not well understood and how to find the stable equilibria of the Lagrangian function is still unknown. To bridge the gap, we study the landscape of the Lagrangian function. Further, we define a special class of Lagrangian functions. They enjoy two properties:
- Equilibria are either stable or unstable;
- Stable equilibria correspond to the global optima of the original problem. We show that a generalized eigenvalue (GEV) problem, including canonical correlation analysis and other problems, belongs to the class. Specifically, we characterize its stable and unstable equilibria by leveraging an invariant group and symmetric property. Motivated by these neat geometric structures, we propose a simple, efficient, and stochastic primal-dual algorithm solving the online GEV problem. Theoretically, we provide sufficient conditions, based on which we establish an asymptotic convergence rate and obtain the first sample complexity result for the online GEV problem by diffusion approximations, which are widely used in applied probability and stochastic control. Numerical results are provided to support our theory.
Introduction
Many critical tasks in machine learning and signal processing—such as Canonical Correlation Analysis (CCA) or Principal Component Analysis (PCA)—are constrained nonconvex optimization problems. Traditionally, these are solved by converting them into a "minimax" problem using a Lagrangian form. However, when the problem lacks convexity, the "landscape" of this Lagrangian function becomes a mystery. It is often unclear if finding a stable point actually yields the global optimum or if the search might get trapped in sub-optimal local minima.
This paper addresses these challenges by characterizing a specific class of nonconvex Lagrangian functions where every stable equilibrium is a global optimum. The authors introduce a fully stochastic, inversion-free algorithm (SGHA) for online Generalized Eigenvalue (GEV) problems and provide the first rigorous sample complexity analysis for this approach using diffusion approximations.
Landscape Characterization
The researchers focus on the Generalized Eigenvalue (GEV) problem, defining a class of Lagrangian functions where equilibria are strictly categorized as either "stable" or "unstable." They prove that for GEV, all stable equilibria correspond exactly to the global optima of the original problem. By leveraging group theory (specifically orthogonal groups), they demonstrate that the equilibria have a neat geometric structure, making the landscape easier to analyze.
A key insight is that negative curvature is a friend: at any "bad" (unstable) equilibrium, the Lagrangian function exhibits negative curvature. This implies that a stochastic algorithm will naturally experience a "push" to escape these points and move toward the global optimum.
The Stochastic Generalized Hebbian Algorithm (SGHA)
To solve the online GEV problem, the authors propose the Stochastic Generalized Hebbian Algorithm (SGHA). This primal-dual algorithm is "fully stochastic" and "inversion-free." Unlike traditional GEV solvers that require expensive matrix inversions ($O(d^3)$ complexity), SGHA updates variables based on noisy, unbiased samples of the data, making it significantly more scalable for high-dimensional streaming data.
Theoretical Analysis and Convergence
To prove the algorithm's effectiveness, the authors model its path as a Stochastic Differential Equation (SDE) using diffusion approximations. This allows them to track how the algorithm escapes saddle points and converges to the global solution through three distinct phases:
- Phase I: Escaping the unstable saddle points.
- Phase II: Rapidly following a deterministic path toward the optimum.
- Phase III: Fluctuating within a small, predictable neighborhood of the global optimum.
This analysis yields the first sample complexity result for the online GEV problem, providing a concrete formula for the number of samples ($N$) needed to reach a target accuracy ($\epsilon$) based on the eigenvalue gap and the condition number of the constraint matrix.
Experimental Results
The SGHA algorithm was evaluated using synthetic datasets across three settings: basic eigenvalue gaps, commutative matrices, and non-commutative matrices. In all scenarios, the algorithm consistently converged to the global optimum regardless of the starting point, supporting the theory that there are no "spurious" stable equilibria for GEV problems.
Conclusion and Future Work
While the algorithm performs well in general settings, the current rigorous mathematical proof for sample complexity assumes that the involved matrices are commutative. The authors suggest this is a limitation of the proof technique rather than the algorithm itself. Future research will focus on extending these geometric insights to more complex, non-linear constraints and addressing the sensitivity of stochastic gradient methods to step size selection.
Summary updated