Timezone: »

 
Spotlight
Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach
Nadav Hallak · Panayotis Mertikopoulos · Volkan Cevher

Wed Jul 21 05:30 AM -- 05:35 AM (PDT) @
in Optimization (Nonconvex) »

This paper develops a methodology for regret minimization with stochastic first-order oracle feedback in online, constrained, non-smooth, non-convex problems. In this setting, the minimization of external regret is beyond reach for first-order methods, and there are no gradient-based algorithmic frameworks capable of providing a solution. On that account, we propose a conceptual approach that leverages non-convex optimality measures, leading to a suitable generalization of the learner's local regret. We focus on a local regret measure defined via a proximal-gradient mapping, that also encompasses the original notion proposed by Hazan et al. (2017). To achieve no local regret in this setting, we develop a proximal-gradient method based on stochastic first-order feedback, and a simpler method for when access to a perfect first-order oracle is possible. Both methods are order-optimal (in the min-max sense), and we also establish a bound on the number of proximal-gradient queries these methods require. As an important application of our results, we also obtain a link between online and offline non-convex stochastic optimization manifested as a new proximal-gradient scheme with complexity guarantees matching those obtained via variance reduction techniques.

Keywords: Non-convex Optimization

Author Information

Nadav Hallak (The Technion)
Panayotis Mertikopoulos (CNRS and Criteo AI Lab)
Volkan Cevher (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors