Abstract
While there has been a significant amount of work studying gradient descent techniques for non-convex optimization problems over the last few years, all existing results establish either local convergence with good rates or global convergence with highly suboptimal rates, for many problems of interest. In this paper, we take the first step in getting the best of both worlds -- establishing global convergence and obtaining a good rate of convergence for the problem of computing squareroot of a positive definite (PD) matrix, which is a widely studied problem in numerical linear algebra with applications in machine learning and statistics among others. Given a PD matrix $M$ and a PD starting point $U_0$, we show that gradient descent with appropriately chosen step-size finds an $\epsilon$-accurate squareroot of $M$ in $O(\alpha \log (\|M-U_0^2\|_F /\epsilon))$ iterations, where $\alpha = (\max\{\|U_0\|_2^2,\|M\|_2\} / \min \{\sigma_{\min}^2(U_0),\sigma_{\min}(M) \} )^{3/2}$. Our result is the first to establish global convergence for this problem and that it is robust to errors in each iteration. A key contribution of our work is the general proof technique which we believe should further excite research in understanding deterministic and stochastic variants of simple non-convex gradient descent algorithms with good global convergence rates for other problems in machine learning and numerical linear algebra.
Introduction
Computing the square root of a matrix $M$ (finding $U$ such that $U^2 = M$) is a fundamental task in linear algebra, essential for data whitening, signal processing, and optimization. While the problem is well-studied, it is inherently non-convex.
In the world of non-convex optimization, researchers usually face a trade-off between local convergence (fast but requires proximity to the solution) and global convergence (robust but often computationally expensive or slow). This paper bridges this gap for the matrix square root problem, proving that gradient descent can achieve the "best of both worlds": starting from any positive definite matrix and converging quickly to the global optimum.
Methodology
The authors analyze gradient descent applied to the objective function: $$f(U) = \|M - U^2\|_F^2$$ where $\|\cdot\|_F$ is the Frobenius norm. The key technical challenge in non-convex landscapes is the presence of saddle points—points where the gradient is zero, but you aren't at a minimum. For this problem, saddle points occur when the matrix $U$ loses rank (becomes "degenerate").
The Strategy
- Characterizing the Landscape: They prove that the only stationary points that aren't global minima are these rank-deficient saddle points.
- Staying in the "Safe Zone": They show that if you start with a positive definite matrix $U_0$ and use a properly tuned step-size, gradient descent stays in a region where the matrix remains well-behaved (far from the saddle points).
- Gradient Dominance: Within this "safe zone," they prove the function satisfies a "gradient dominance" property (related to the Polyak-Łojasiewicz inequality), which guarantees that the gradient is always large enough to push the iterates toward the solution at a geometric rate.
Key Insights and Ideas
- Natural Avoidance of Saddles: Unlike some recent non-convex solvers that require adding random noise to "escape" saddle points, this paper shows that for the matrix square root, standard gradient descent naturally stays away from them if initialized correctly.
- Robustness "For Free": Because the algorithm is shown to be stable within a specific region of the matrix space, it is inherently robust to small errors (like numerical rounding or stochastic noise) in each iteration.
- Purely Multiplicative: Most traditional methods (like Newton's method) require matrix inversions or solving linear systems. This gradient descent approach uses only matrix multiplications, which are highly optimized on modern hardware like GPUs.
Key Results
The algorithm finds an $\epsilon$-accurate square root in $O(\alpha \log(1/\epsilon))$ iterations with a total complexity of $O(n^\omega \alpha \log(1/\epsilon))$, where $n^\omega$ is the cost of matrix multiplication. This is significantly faster than previous general-purpose global non-convex solvers.
As shown in the table above, the proposed method is the first to establish global convergence and provable robustness for this problem with a competitive runtime. Additionally, the authors prove a lower bound of $\Omega(\kappa)$ iterations (where $\kappa$ is the condition number of $M$), showing that the dependence on the matrix's properties is a fundamental requirement.
Limitations and Future Work
- Condition Number Dependence: The convergence rate depends on $\alpha$, which is related to $\kappa^{3/2}$. While they prove a lower bound of $\kappa$, there is still a small gap between their upper bound and the theoretical limit.
- Initialization: While the convergence is "global" for any positive definite starting point, the rate still depends on how "good" that starting point is relative to the target matrix.
- Low-Rank Matrices: The current analysis assumes the target matrix $M$ is full rank. Extending this to low-rank (positive semi-definite) matrices is a promising direction for future research.
Summary updated