Stochastic Chebyshev Gradient Descent for Spectral Optimization

Insu Han, Haim Avron, Jinwoo Shin

Many modern machine learning tasks rely heavily on "spectral functions"—functions that depend on the eigenvalues of a matrix. Common examples include the log-determinant used in Gaussian Processes and the nuclear norm used in matrix completion.

The primary challenge with these functions is computational. Calculating their exact gradients typically requires an eigenvalue decomposition or a Cholesky factorization, both of which scale with a cubic complexity ($O(d^3)$) relative to the matrix dimension $d$. This makes exact computation impractical for large datasets. While stochastic gradient methods are the standard workaround for scaling up, computing unbiased stochastic gradients for these spectral functions has historically lacked a straightforward solution. Previous attempts often relied on biased estimators, which can cause optimization to plateau prematurely or even diverge.

This paper introduces a novel method to compute unbiased stochastic gradients for spectral functions. By combining randomized trace estimators with a "variance-optimal" stochastic truncation of Chebyshev expansions, the authors enable fast, stable optimization for large-scale problems.

Unbiased Gradients via Stochastic Truncation

The authors focus on spectral-sums, a critical subclass of spectral functions expressed as $\text{tr}(f(A))$. Their approach to generating unbiased gradients involves three key components:

  1. Chebyshev Expansion: The function $f(A)$ is approximated using Chebyshev polynomials. In standard practice, this series is truncated at a fixed degree $n$, which inherently introduces a deterministic bias into the gradient.
  2. Stochastic Truncation: To eliminate this bias, the authors treat the truncation degree $n$ as a random variable. By carefully re-weighting the coefficients of the expansion, they ensure that the expected value of the stochastic approximation perfectly matches the true spectral sum.
  3. Variance-Optimal Distribution: The most significant theoretical contribution of the paper (Theorem 3) is the derivation of a specific probability distribution for the random degree $n$ that minimizes the variance of the gradient estimate.
Variance comparison of different truncation distributions

Minimizing variance is crucial because high variance in stochastic gradients leads to slow and unstable convergence. As demonstrated, not all random samplings are equal. The authors' "optimal" distribution for the polynomial degree yields an order-of-magnitude smaller variance compared to naive choices like Poisson or Negative Binomial distributions.

These unbiased gradients are then integrated into two standard optimization frameworks: Stochastic Gradient Descent (SGD) and Stochastic Variance Reduced Gradient (SVRG). Notably, they successfully adapted the SVRG algorithm—typically used for sums of data points—to spectral sums by sharing the randomness (the probing vectors and the random degree) between the inner and outer loops of the algorithm.

Experimental Results and Key Insights

The authors evaluated their methods on several real-world datasets, including MovieLens 1M and 10M for matrix completion, as well as the Natural Sound and Szeged Humid datasets for Gaussian Process (GP) regression.

Unbiasedness Matters

The experiments clearly demonstrate that biased stochastic gradients (such as those using a fixed polynomial degree, labeled SGD-DET) often plateau or fail to reach the global optimum. Randomizing the degree effectively "de-biases" the process, allowing the model to achieve true convergence.

Test RMSE convergence comparing GD, SGD, and SVRG methods

Speed and Scalability

  • Matrix Completion: On the MovieLens 10M dataset, the proposed SVRG approach was up to 6x faster than standard Gradient Descent to reach a target Root Mean Square Error (RMSE) of 1.8.
  • Superiority over Lanczos: In Gaussian Process regression, their SGD method was 2x faster than the state-of-the-art "Stochastic Lanczos Quadrature" method. Furthermore, the Lanczos-based method often got stuck in local optima, a pitfall the proposed unbiased SGD successfully avoided.
  • Scalability: The complexity of their gradient estimation reduces to $O(d)$ for structured matrices (like those found in GP regression), making it highly scalable compared to the $O(d^3)$ exact computation.

Limitations and Future Work

While highly effective, the method does have a few limitations. First, the Chebyshev expansion requires knowing (or estimating) the interval $[a, b]$ containing all eigenvalues of the matrix. The authors use power methods to estimate these bounds, but this adds a necessary preprocessing step.

Second, the function $f$ must be analytic on the interval containing the eigenvalues. While this covers most common machine learning functions (log, square root, exp), it may not apply to non-smooth spectral functions. Finally, the efficiency of the method relies heavily on the speed of matrix-vector multiplications. If the matrix $A$ is dense and lacks structure, the computational gains over exact methods might be less pronounced.

Summary updated

Abstract

A large class of machine learning techniques requires the solution of optimization problems involving spectral functions of parametric matrices, e.g. log-determinant and nuclear norm. Unfortunately, computing the gradient of a spectral function is generally of cubic complexity, as such gradient descent methods are rather expensive for optimizing objectives involving the spectral function. Thus, one naturally turns to stochastic gradient methods in hope that they will provide a way to reduce or altogether avoid the computation of full gradients. However, here a new challenge appears: there is no straightforward way to compute unbiased stochastic gradients for spectral functions. In this paper, we develop unbiased stochastic gradients for spectral-sums, an important subclass of spectral functions. Our unbiased stochastic gradients are based on combining randomized trace estimators with stochastic truncation of the Chebyshev expansions. A careful design of the truncation distribution allows us to offer distributions that are variance-optimal, which is crucial for fast and stable convergence of stochastic gradient methods. We further leverage our proposed stochastic gradients to devise stochastic methods for objective functions involving spectral-sums, and rigorously analyze their convergence rate. The utility of our methods is demonstrated in numerical experiments.
BibTeX
@inproceedings{han2018stochastic,
  author = {Insu Han and Haim Avron and Jinwoo Shin},
  title = {{Stochastic Chebyshev Gradient Descent for Spectral Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HymNYdbuWB},
}
Figure