Spectral Smoothing via Random Matrix Perturbations
This work addresses optimization and learning challenges in semidefinite programming and online settings, offering improved efficiency with concrete regret bounds, though it appears incremental as it builds on existing smoothing and random matrix theory.
The paper tackles the problem of smoothing spectral functions of matrices using random matrix perturbations, specifically deriving state-of-the-art bounds for the maximum eigenvalue function with the Gaussian Orthogonal Ensemble (GOE). As a result, it achieves an O((N log N)^{1/4} sqrt(T)) expected regret bound for online variance minimization and O(k (N log N)^{1/4} sqrt(T)) for online PCA, requiring only single or k maximum eigenvector computations per time step.
We consider stochastic smoothing of spectral functions of matrices using perturbations commonly studied in random matrix theory. We show that a spectral function remains spectral when smoothed using a unitarily invariant perturbation distribution. We then derive state-of-the-art smoothing bounds for the maximum eigenvalue function using the Gaussian Orthogonal Ensemble (GOE). Smoothing the maximum eigenvalue function is important for applications in semidefinite optimization and online learning. As a direct consequence of our GOE smoothing results, we obtain an $O((N \log N)^{1/4} \sqrt{T})$ expected regret bound for the online variance minimization problem using an algorithm that performs only a single maximum eigenvector computation per time step. Here $T$ is the number of rounds and $N$ is the matrix dimension. Our algorithm and its analysis also extend to the more general online PCA problem where the learner has to output a rank $k$ subspace. The algorithm just requires computing $k$ maximum eigenvectors per step and enjoys an $O(k (N \log N)^{1/4} \sqrt{T})$ expected regret bound.