Timezone: »
We propose a hierarchical version of dual averaging for zeroth-order online non-convex optimization – i.e., learning processes where, at each stage, the optimizer is facing an unknown non-convex loss function and only receives the incurred loss as feedback. The proposed class of policies relies on the construction of an online model that aggregates loss information as it arrives, and it consists of two principal components: (a) a regularizer adapted to the Fisher information metric (as opposed to the metric norm of the ambient space); and (b) a principled exploration of the problem’s state space based on an adapted hierarchical schedule. This construction enables sharper control of the model’s bias and variance, and allows us to derive tight bounds for both the learner’s static and dynamic regret – i.e., the regret incurred against the best dynamic policy in hindsight over the horizon of play.
Author Information
Amélie Héliou (Criteo)
Matthieu Martin (Criteo AI Lab)
Panayotis Mertikopoulos (CNRS and Criteo AI Lab)
Thibaud J Rahier (INRIA)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Zeroth-Order Non-Convex Learning via Hierarchical Dual Averaging »
Tue. Jul 20th 12:35 -- 12:40 PM Room
More from the Same Authors
-
2022 : A Bias-Variance Analysis of Weight Averaging for OOD Generalization »
Alexandre Ramé · Matthieu Kirchmeyer · Thibaud J Rahier · Alain Rakotomamonjy · Patrick Gallinari · Matthieu Cord -
2023 Poster: Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism »
Yu-Guan Hsieh · Franck Iutzeler · Jérôme Malick · Panayotis Mertikopoulos -
2022 Poster: Nested Bandits »
Matthieu Martin · Panayotis Mertikopoulos · Thibaud J Rahier · Houssam Zenati -
2022 Poster: UnderGrad: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees »
Kimon Antonakopoulos · Dong Quan Vu · Volkan Cevher · Kfir Levy · Panayotis Mertikopoulos -
2022 Oral: UnderGrad: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees »
Kimon Antonakopoulos · Dong Quan Vu · Volkan Cevher · Kfir Levy · Panayotis Mertikopoulos -
2022 Spotlight: Nested Bandits »
Matthieu Martin · Panayotis Mertikopoulos · Thibaud J Rahier · Houssam Zenati -
2022 Poster: AdaGrad Avoids Saddle Points »
Kimon Antonakopoulos · Panayotis Mertikopoulos · Georgios Piliouras · Xiao Wang -
2022 Spotlight: AdaGrad Avoids Saddle Points »
Kimon Antonakopoulos · Panayotis Mertikopoulos · Georgios Piliouras · Xiao Wang -
2021 Poster: The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets »
Ya-Ping Hsieh · Panayotis Mertikopoulos · Volkan Cevher -
2021 Poster: Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach »
Nadav Hallak · Panayotis Mertikopoulos · Volkan Cevher -
2021 Spotlight: Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach »
Nadav Hallak · Panayotis Mertikopoulos · Volkan Cevher -
2021 Oral: The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets »
Ya-Ping Hsieh · Panayotis Mertikopoulos · Volkan Cevher -
2020 Poster: Gradient-free Online Learning in Continuous Games with Delayed Rewards »
Amélie Héliou · Panayotis Mertikopoulos · Zhengyuan Zhou -
2020 Poster: A new regret analysis for Adam-type algorithms »
Ahmet Alacaoglu · Yura Malitsky · Panayotis Mertikopoulos · Volkan Cevher -
2020 Poster: Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games »
Tianyi Lin · Zhengyuan Zhou · Panayotis Mertikopoulos · Michael Jordan -
2019 Poster: Cautious Regret Minimization: Online Optimization with Long-Term Budget Constraints »
Nikolaos Liakopoulos · Apostolos Destounis · Georgios Paschos · Thrasyvoulos Spyropoulos · Panayotis Mertikopoulos -
2019 Oral: Cautious Regret Minimization: Online Optimization with Long-Term Budget Constraints »
Nikolaos Liakopoulos · Apostolos Destounis · Georgios Paschos · Thrasyvoulos Spyropoulos · Panayotis Mertikopoulos -
2018 Poster: Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? »
Zhengyuan Zhou · Panayotis Mertikopoulos · Nicholas Bambos · Peter Glynn · Yinyu Ye · Li-Jia Li · Li Fei-Fei -
2018 Oral: Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? »
Zhengyuan Zhou · Panayotis Mertikopoulos · Nicholas Bambos · Peter Glynn · Yinyu Ye · Li-Jia Li · Li Fei-Fei