Title: Bandit algorithms for nonstationary online nonconvex optimization
Authors: Krishnakumar Balasubramanian - University of California, Davis (United States) [presenting]
Abstract: Bandit algorithms have been predominantly analyzed in the convex setting with function value based stationary regret as the performance measure. We propose and analyze bandit algorithms for nonconvex problems with nonstationary regret as the performance measure. Specifically, we consider nonstationary regret measures in terms of function-values, first-order and second-order stationary solutions. We provide regret bounds for the Gaussian Steins identity based bandit algorithm for two classes of nonconvex functions, in both the low and high-dimensional settings, in terms of function-value and first-order stationary solutions based regret measures. We also propose online and bandit versions of the cubic regularized Newtons method. The bandit version is based on estimating the Hessian matrices in the bandit setting, based on second-order Gaussian Steins identity. We provide nonstationary regret bounds in terms of second-order stationary solutions, that have interesting consequences for avoiding saddle points in the bandit setting.