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 a fast rate or global convergence with a very slow rate. This paper bridges that gap for the fundamental problem of computing a matrix square root, proving that vanilla gradient descent converges at a geometric rate to the global optimum and remains robust even when the calculations are noisy.
Introduction
Computing the square root of a positive definite (PD) matrix $M$—finding a matrix $U$ such that $U^2 = M$—is a cornerstone of numerical linear algebra, used in applications ranging from data whitening to signal processing. Despite its ubiquity, the optimization objective $\min \|M - U^2\|_F^2$ is inherently non-convex.
Historically, researchers in non-convex optimization have faced a trade-off:
- Local Convergence: Fast algorithms (like Newton's method) that require an initial guess very close to the solution.
- Global Convergence: Algorithms that work from any starting point but often suffer from suboptimal, slow convergence rates.
This work addresses the "best of both worlds" challenge, proving that vanilla gradient descent (GD) converges to the global solution from any positive definite starting point at a fast, geometric rate.
The Gradient Descent Approach
The authors analyze a surprisingly simple approach: Vanilla Gradient Descent. Unlike Newton’s method, it avoids complex second-order information or matrix inversions, simply updating the estimate $U$ along the negative gradient. The core contribution lies in a sophisticated global convergence analysis.
The proof demonstrates that if the starting point $U_0$ is positive definite, the iterates remain within a well-behaved region of the search space characterized by:
- Smoothness: The gradient changes predictably.
- Gradient Dominance: A PL-like inequality ensures the gradient magnitude is sufficient to drive the algorithm toward the global minimum, preventing it from stalling near saddle points.
Key Insights: Navigating the Non-Convex Landscape
A primary challenge in non-convex optimization is the presence of saddle points. The authors show that for the matrix square root problem, there are no "spurious" local minima. The only problematic points are saddle points located where the matrix becomes rank-degenerate.
Crucially, starting with a positive definite matrix creates a "buffer zone" that naturally steers the gradient descent path away from these saddle surfaces. This geometric property allows the algorithm to behave as if it were optimizing a convex function. Furthermore, this inherent "gradient dominance" provides robustness; small numerical or stochastic errors do not derail convergence, a significant advantage over traditional methods like Newton’s iteration.
Main Results and Comparative Performance
The theoretical analysis yields several key results regarding the efficiency and reliability of GD for this problem:
- Geometric Convergence: GD finds an $\epsilon$-accurate square root in $O(\alpha \log(1/\epsilon))$ iterations, meaning the error decays exponentially.
- Total Runtime: The complexity is $O(n^\omega \alpha \log(1/\epsilon))$, where $n^\omega$ is the cost of matrix multiplication. This is significantly faster than previous global bounds for non-convex problems.
- Lower Bound: The authors established a lower bound of $\Omega(\kappa)$ iterations, where $\kappa$ is the condition number, indicating that the dependence on matrix conditioning is fundamental.
As shown in the table above, the proposed GD approach is the only iterative method that simultaneously offers global convergence and provable robustness with a competitive runtime.
Limitations and Future Work
While the paper marks a significant advancement, some gaps remain. The current convergence rate depends on $\alpha \approx \kappa^{3/2}$, leaving a small gap relative to the $\Omega(\kappa)$ lower bound. Additionally, the analysis assumes the target matrix $M$ is strictly full-rank (positive definite). Extending these proofs to low-rank (PSD) matrices, where saddle points are harder to avoid, is a key area for future research. Finally, whether this "saddle avoidance" framework can be generalized to more complex non-convex problems like deep learning remains an open question.
Summary updated