Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot

Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli

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:

  1. Local Convergence: Fast algorithms (like Newton's method) that require an initial guess very close to the solution.
  2. 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.

Figure 1: Vector field visualization of the gradient flow for a 2x2 diagonal matrix, showing convergence to the global optimum and avoidance of saddle points.

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.
Figure 3: Comparison of runtime, global convergence, and provable robustness across different numerical methods for matrix square root computation.

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

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 conv...
BibTeX
@inproceedings{jain2017global,
  author = {Prateek Jain and Chi Jin and Sham M. Kakade and Praneeth Netrapalli},
  title = {{Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=LXPNshYAFOP},
}
Figure