Stochastic Subspace Descent

Abstract

We present two stochastic descent algorithms that apply to unconstrained optimization and are 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 basic algorithm projects the gradient onto a random subspace at each iteration, similar to coordinate descent but without restricting directional derivatives to be along the axes. This algorithm is previously known but we provide new analysis. We also extend the popular SVRG method to this framework but without requiring that the objective function be written as a finite sum. We provide proofs of convergence for our methods under various convexity assumptions and show favorable results when compared to gradient descent and BFGS on non-convex problems from the machine learning and shape optimization literature. We also note that our analysis gives a proof that the iterates of SVRG and several other popular first-order stochastic methods, in their original formulation, converge almost surely to the optimum; to our knowledge, prior to this work the iterates of SVRG had only been known to converge in expectation.

34 pages, 7 figures, submitted on 4/1/19 Update: Main document: 24 Pages, Supplementary Material 9 pages

References in corpus (17)

• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Universal Catalyst for First-Order Optimization
• RES: Regularized Stochastic BFGS Algorithm
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Likelihood-informed dimension reduction for nonlinear inverse problems
• Barzilai-Borwein Step Size for Stochastic Gradient Descent
• Global Convergence of Online Limited Memory BFGS
• Optimization with First-Order Surrogate Functions
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Randomized Truncated SVD Levenberg-Marquardt Approach to Geothermal Natural State and History Matching
• Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches
• Randomized Derivative-Free Optimization of Noisy Convex Functions

Cited by in corpus (3)

• Constrained global optimization of functions with low effective dimensionality using multiple random embeddings
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters