Optimizing Spectral Sums using Randomized Chebyshev Expansions

Insu Han, Haim Avron, Jinwoo Shin

Introduction

Spectral optimization—minimizing functions that depend on the eigenvalues of a matrix—is a cornerstone of modern machine learning. Applications range from Gaussian Process regression (log-determinants) and nuclear norm regularization to quantum state tomography. However, these functions are notoriously expensive to compute. The "gold standard" for calculating gradients exactly involves eigenvalue decomposition, which has a cubic complexity of $O(d^3)$. This makes exact methods impractical for large-scale matrices with millions of dimensions.

While stochastic gradient methods (SGD) are typically used to scale optimization, spectral functions present a unique challenge: there is no straightforward way to compute unbiased stochastic gradients. Previous approaches relied on fixed-degree polynomial approximations (e.g., Chebyshev or Taylor series), but these are inherently biased due to truncation. This bias often causes optimization algorithms to stall or converge to suboptimal solutions.

Methodology: Unbiased Stochastic Chebyshev Gradients

The proposed method overcomes the bias-efficiency trade-off by combining three key components: stochastic truncation, randomized trace estimation, and a variance-optimal sampling strategy.

Stochastic Truncation and Trace Estimation

Instead of truncating a Chebyshev polynomial expansion at a fixed degree $n$, the authors treat the degree as a random variable. By re-weighting the expansion coefficients, they ensure the expected value of the approximation matches the true function value, thereby eliminating bias. To avoid the $O(d^3)$ cost of full matrix products, they employ Hutchinson’s method for randomized trace estimation, reducing the per-iteration cost to a few matrix-vector multiplications ($O(d^2)$ or better for sparse matrices).

Variance-Optimal Distribution

A critical challenge in stochastic truncation is the potential for high variance in the gradient estimator. The authors derived a specific probability distribution for the random degree $n$ that minimizes this variance. This distribution typically features a deterministic "burn-in" period followed by a geometric decay.

Figure 1: Comparison of weighted variance across different functions and distributions. The "opt" (optimal) distribution consistently achieves the lowest variance compared to negative binomial (neg) and Poisson (pois) distributions.

Experimental Results

The researchers evaluated their methods on matrix completion (MovieLens 1M/10M) and Gaussian Process regression (Natural Sound and Szeged Humid datasets).

Convergence and Stability

A key finding is the importance of unbiasedness. As shown in the experimental results, biased methods like "SGD-DET" (fixed truncation) eventually hit an error floor. In contrast, the proposed unbiased SGD continues to improve. Furthermore, the variance-optimal distribution ("opt") leads to faster and more stable convergence compared to other distributions.

Figure 4: Performance comparison across different tasks. (a, b) Elapsed time vs. test RMSE shows SVRG significantly outperforming GD. (c) The optimal distribution leads to the fastest convergence. (d) Comparison between biased (SGD-DET) and unbiased (SGD) methods highlights the error floor of biased approximations.

Speed and Scalability

On the Szeged humid dataset for Gaussian Processes, the proposed method was 6x faster than the previous state-of-the-art, Stochastic Lanczos Quadrature. For matrix completion on MovieLens 10M, the Stochastic Variance Reduced Gradient (SVRG) implementation reached target RMSE levels significantly faster than standard Gradient Descent, which is hampered by the $O(d^3)$ cost of nuclear norm gradients.

Conclusion

This work provides a robust framework for scaling spectral optimization by moving beyond the cubic complexity trap. By leveraging randomized Chebyshev expansions with variance-optimal stochastic truncation, the authors enable the use of unbiased stochastic gradients for spectral-sums. While the method requires eigenvalue bounds and is currently limited to spectral-sums, it offers a powerful tool for large-scale kernel methods and matrix factorizations.

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{han2018optimizing,
  author = {Insu Han and Haim Avron and Jinwoo Shin},
  title = {{Optimizing Spectral Sums using Randomized Chebyshev Expansions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HymNYdbuWB},
}
Figure