Speaker: Saeed Ghadimi, Princeton University

Abstract

In this talk, we propose and analyze derivative-free stochastic approximation algorithms for nonconvex optimization. We first propose generalization of the conditional gradient algorithm achieving a similar rate to the standard stochastic gradient algorithm (SGD) using only noisy function evaluations (zeroth-order information). For the high-dimensional setting, we explore the advantage of structural sparsity assumption and highlight an implicit regularization phenomenon where the SGD algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step-size. We next focus on avoiding saddle-points by utilizing Gaussian smoothing technique for estimating the gradient 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 using only noisy function evaluations, which is based on second-order Stein’s identity. We then provide a zeroth-order variant of cubic regularized Newton method for avoiding saddle-points and discuss its rate of convergence to local minima.

Finally, we will briefly discuss a new approach to solve inventory related problems, namely, an energy storage problem, under the presence of rolling forecasts and show how our proposed algorithms can be used to efficiently solve this kind of problem.

Room: BA1220