Title: On Stein's identity and derivate- and Hessian-free stochastic optimization
Authors: Krishnakumar Balasubramanian - University of California, Davis (United States) [presenting]
Abstract: Gaussian smoothing based techniques for zeroth-order stochastic optimization are common in the optimization literature. It will be shown that such techniques are essentially instantiations of Stein's identity, popular in the statistics literature. Based on this relationship, the following three results will be discussed. First, under a structural sparsity assumption on the optimization problem, we will illustrate an implicit regularization phenomenon where a derivative-free stochastic gradient algorithm adapts to the sparsity of the problem at hand by just varying the step-size. Next, we will discuss a truncated derivative-free stochastic gradient algorithm, whose rate of convergence depends only poly-logarithmically on the dimensionality under the sparsity assumption. Finally, leveraging the second-order Stein's identity, we will introduce a Hessian-free Newton method with zeroth-order information and discuss its convergence rates.