Stephen Becker, Department of Applied Mathematics, University of Colorado Boulder
Stochastic Subspace Descent: Stochastic gradient-free optimization, with applications to PDE-constrained optimization
We describe and analyze a family of algorithms that generalize block-coordinate descent, where we assume one can take directional derivatives (for low-precision optimization, this can be approximated with finite differences, hence this is similar to a 0th order method). The method generalizes randomized block coordinate descent. We prove almost-sure convergence of the algorithm at a linear rate (under strong convexity) and convergence (with convexity). Furthermore, we analyze a variant similar to SVRG but that does not require the finite-sum structure in the objective, and for isotropic random sampling, we use Johnson-Lindenstrauss style arguments to provide non-asymptotic, probabilistic convergence results. Numerical examples are provided for selecting landmark points in Gaussian process regression, and in PDE-constrained optimization (shape optimization). This is joint work with Luis Tenorio and David Kozak from the Colorado School of Mines Applied Math & Stat Dept, and Alireza Doostan from CU Boulder's Smead Aerospace Engineering Dept.