Abstract

We consider matrices A(t) that depend, possibly nonlinearly, on a parameter t. We present a randomized algorithm for minimizing trace(A(t)) over all t with bounded two-norm, and determine the number of samples so that the excess risk is bounded with high probability. The derivation of the bound relies on concentration of measure, uniform convergence, and discretization by epsilon nets. This is joint work with Arvind Saibaba.

Video Recording