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.
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.
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