Laboratoire d'Informatique de Grenoble

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.