Poster
Zeroth-order (Non)-Convex Stochastic Optimization via Conditional Gradient and Gradient Updates
Krishnakumar Balasubramanian · Saeed Ghadimi
Room 210 #27
Keywords: [ Convex Optimization ] [ Optimization ] [ Non-Convex Optimization ] [ Regularization ]
In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization. Specifically, we propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. Furthermore, under a structural sparsity assumption, we first illustrate 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. Next, we propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality.
Live content is unavailable. Log in and register to view live content