Mercredi 12 janvier 2022
- Imprimer
- Partager
- Partager sur Facebook
- Share on X
- Partager sur LinkedIn
Adaptive Methods for Optimization without Lipschitz Requirements
Résumé:
Several important problems in learning theory and data science involve high-dimensional optimization objectives that transcend the Lipschitz regularity conditions that are standard in the field. This absence of regularity poses significant obstacles to the convergence analysis of most optimization algorithms and, in many cases, it requires the introduction of novel analytical and algorithmic tools. In this thesis, we aim to partially fill this gap via the design and analysis of universal first-order methods in two general optimization frameworks: (a) online convex optimization (which contains as special cases deterministic and stochastic convex optimization problems); and (b) abstract variational inequalities (which contain as special cases min-max problems and games), both without global Lipschitz continuity/smoothness conditions.
In this "NoLips" setting, we take a geometric approach – Riemannian, Finslerian, or Bregman-based – that allows us to handle vector fields and functions whose norm or variation becomes infinite at the boundary of the problem’s domain. Using these non-Euclidean surrogates for Lipschitz continuity and smoothness, we propose a range of adaptive first-order methods that concurrently achieve order-optimal convergence rates in different problem classes, without any prior knowledge of the problem's regularity class or parameters. These methods are based on a judiciously chosen mirror descent or mirror-prox template (for convex minimization and monotone variational inequalities respectively), and they revolve around adaptive step-size policies that exploit the geometry of the gradient data observed at earlier iterations. Our results do not always coincide with what one would expect in standard Lipschitz problems, and serve to further highlight the differences between the "Lipschitz" and "noLips" frameworks.
Date et Lieu
Mercredi 12 Janvier 2022 à 14h
A distance : https://cnrs.zoom.us/j/95314227028?pwd=RGk3L2xSSFRucWNQbm1qSUhYZWVtZz09
Composition du Jury
E. Veronica BELMEGA
Associate Professor, ETIS / ENSEA, Cergy Paris University (co-supervisor)
Roberto COMINETTI
Professor, Universidad Adolfo Ibañez (examiner)
Walid HACHEM
Research Director, CNRS (reviewer)
Niao HE
Professor, ETHZ (examiner)
Jérôme MALICK
Research Director, CNRS (president of the jury)
Panayotis MERTIKOPOULOS
Research Scientist, CNRS (co-supervisor)
Marc TEBOULLE
Professor, Tel Aviv University (reviewer)
- Imprimer
- Partager
- Partager sur Facebook
- Share on X
- Partager sur LinkedIn