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

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...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2021-06, Vol.79 (2), p.339-368
Main Authors: Kozak, David, Becker, Stephen, Doostan, Alireza, Tenorio, Luis
Format: Article
Language:English
Subjects:
Algorithms
Convergence
Convex and Discrete Geometry
Convexity
Derivatives
Differentiation
Image processing
Iterative methods
Machine learning
Management Science
Mathematical analysis
Mathematics
Mathematics and Statistics
Operations Research
Operations Research & Management Science
Operations Research/Decision Theory
Optimization
Shape optimization
Smoothing
Statistics
Subspaces
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ℓ 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 ℓ 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 provides a novel extension to 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.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-021-00271-w