Optimization Online


Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality, and Saddle-Points

Krishnakumar Balasubramanian (kbala***at***ucdavis.edu)
Saeed Ghadimi (sghadimi***at***princeton.edu)

Abstract: In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To facilitate zeroth-order optimization in high-dimensions, we explore the advantages of structural sparsity assumptions. Specifically, (i) we highlight an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step-size and (ii) propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only polylogarithmically on the dimensionality. We next focus on avoiding saddle-points in non-convex setting. Towards that, we interpret the Gaussian smoothing technique for estimating gradient based on zeroth-order information as an instantiation of first-order Steinís identity. Based on this, we provide a novel linear-(in dimension) time estimator of the Hessian matrix of a function using only zeroth-order information, which is based on second-order Steinís identity. We then provide an algorithm for avoiding saddle-points, which is based on a zeroth-order cubic regularization Newtonís method and discuss its convergence rates.

Keywords: Nonconvex optimization, Stochastic optimization, Zeroth-order algorithms, Complexity, Newton method, Conditional gradient

Category 1: Nonlinear Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 01/14/2019
Entry Accepted: 01/14/2019
Entry Last Modified: 01/15/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society