Statistical Seminar: Every Monday at 2:00 pm.
Time: 2:00 pm – 3:00 pm
Date: 9th March
Place: 3001

Aymeric DIEULEVEUT (Ecole Polytechnique)  “Will computers replace optimization researchers? Computer-aided proofs in first-order optimization, a case study on error feedback.”

 Abstract: First-order methods are widely used in optimization and machine learning, and their behavior often analyzed through the spectrum of worst case convergence rates. Obtaining such guarantees is often difficult and both time consuming and error-prone. Starting with the work of Drori and Teboulle (2014), novel techniques have been used to gain numerical insights, leading to the release of various performance estimation (PE) software.

In this talk, I will show how various computer-aided techniques can be used to study first-order optimization methods in a systematic way. From performance estimation problems with automated Lyapunov discovery, to symbolic regression and computer algebra systems, novel tools completely reshape the way we approach theory of optimization.

As a main example, I will focus on error feedback methods used with compressed communication in distributed optimization. While error feedback has been widely studied, existing theory often provides untight (thus unreliable) bounds. I will present tight analyses with matching lower bounds that allow a fair comparison between error feedback schemes and standard compressed gradient descent, and help explain when error feedback is useful and when it is not.

Organizers:

Anna KORBA (CREST), Vincent DIVOL (CREST) , Jaouad MOURTADA (CREST)

Sponsors:
CREST-CMAP