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