A stochastic subspace approach to gradient-free optimization in high dimensions

Abstract

We present a stochastic descent algorithm for unconstrained optimization that is particularly efficient when the objective function is slow to evaluate and gradients are not easily obtained, as in some PDE-constrained optimization and machine learning problems. The algorithm maps the gradient onto a low-dimensional random subspace of dimension $\ell$ at each iteration, similar to coordinate descent but without restricting directional derivatives to be along the axes. Without requiring a full gradient, this mapping can be performed by computing $\ell$ directional derivatives (e.g., via forward-mode automatic differentiation). We give proofs for convergence in expectation under various convexity assumptions as well as probabilistic convergence results under strong-convexity. Our method extends the well-known Gaussian smoothing technique to descent in subspaces of dimension greater than one, opening the doors to new analysis of Gaussian smoothing when more than one directional derivative is used at each iteration. We also provide a finite-dimensional variant of a special case of the Johnson-Lindenstrauss lemma. Experimentally, we show that our method compares favorably to coordinate descent, Gaussian smoothing, gradient descent and BFGS (when gradients are calculated via forward-mode automatic differentiation) on problems from the machine learning and shape optimization literature.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1904.01145

References in corpus (13)

• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the Antarctic ice sheet
• A Universal Catalyst for First-Order Optimization
• Likelihood-informed dimension reduction for nonlinear inverse problems
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Stochastic Dual Ascent for Solving Linear Systems
• Structured Evolution with Compact Architectures for Scalable Policy Optimization
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• On the sub-Gaussianity of the Beta and Dirichlet distributions
• Randomized Truncated SVD Levenberg-Marquardt Approach to Geothermal Natural State and History Matching
• On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables
• Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches
• Bi-fidelity Stochastic Gradient Descent for Structural Optimization under Uncertainty

Cited by in corpus (1)

• Improving Neural Network Training in Low Dimensional Random Bases