Seminar

Past

A gradient estimator via L1-randomization for onlinezero-order optimization with two point feedback

Evgenii Chzhen

  • Date13 October 2022
  • Time 11h00 - 12h15
  • Room Auditorium 3

Résumé

This work studies online zero-order optimization of convex and Lipschitz functions. We present a novel gradient estimator based on two function evaluations and randomization on the `1-sphere. Considering different geometries of feasible sets and Lipschitz assumptions we analyse online dual averaging algorithm with our estimator in place of the usual gradient. We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem. In the case of canceling noise that was previously studied in the literature, our guarantees are either comparable or better than stateof- the-art bounds obtained by Duchi et al. [14] and Shamir [33] for non-adaptive algorithms. Our analysis is based on deriving a new weighted Poincaré type inequality for the uniform measure on the `1-sphere with explicit constants, which may be of independent interest.

Related document(s)

Other seminars

To be announced

  • Seminar

  • MAD-Stat. Seminar

  • Date 4 March 2027

  • Place Auditorium JJ Laffont

  • Speaker or organiser Agnes Lagnoux (Ecole Normale Supérieure - Université Paris Sciences & Lettres)

Détails

Convergence Rates for Distribution Matching with Sliced Optimal Transport

  • Seminar

  • MAD-Stat. Seminar

  • Date 10 December 2026

  • Place Auditorium 6

  • Speaker or organiser Gauthier Louis Thurin (Université de Bordeaux)

Détails

Limits of uniform spanning trees and forests

  • Seminar

  • MAD-Stat. Seminar

  • Date 3 December 2026

  • Place Auditorium JJ Laffont

  • Speaker or organiser Eleanor Archer (Université Paris-Dauphine)

Détails