Timezone: »

Online Non-Convex Optimization with Imperfect Feedback
Amélie Héliou · Matthieu Martin · Panayotis Mertikopoulos · Thibaud Rahier

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1030

We consider the problem of online learning with non-convex losses. In terms of feedback, we assume that the learner observes – or otherwise constructs – an inexact model for the loss function encountered at each stage, and we propose a mixed-strategy learning policy based on dual averaging. In this general context, we derive a series of tight regret minimization guarantees, both for the learner’s static (external) regret, as well as the regret incurred against the best dynamic policy in hindsight. Subsequently, we apply this general template to the case where the learner only has access to the actual loss incurred at each stage of the process. This is achieved by means of a kernel-based estimator which generates an inexact model for each round’s loss function using only the learner’s realized losses as input.

Author Information

Amélie Héliou (Criteo AI Lab)
Matthieu Martin (Criteo)

Senior researcher at Criteo

Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research))
Thibaud Rahier (Criteo AI Lab)

Ecole polytechnique graduate (Diplome d'ingenieur polytechnicien). Major: Applied Mathematics, Minors: Mathematics and Computer Science UC Berkeley graduate (M.A. in Statistics) PhD in Machine Learning (cifre) between INRIA and Schneider Electric in Grenoble, France Researcher at Criteo AI Lab in Grenoble, France

More from the Same Authors