Abstract
Many empirical questions about machine learning systems are best answered through the eigenvalues of associated matrices. For example, the Hessian of the loss function for a large deep network gives us insight into the difficulty of optimization and sensitivity to parameters. The spectra of adjacency and Laplacian matrices of large graphs helps us understand the global structure between vertices. Unfortunately, in the most interesting situations, these matrices are too large to be explicitly instantiated, to say nothing of diagonalizingthem directly; rather they are implicit matrices, which can only be interrogatedvia matrix-vector products. In this work I will discuss how several differentrandomized estimation tricks can be assembled to construct unbiased estimatorsof the spectra of large implicit matrices via generalized traces.