Rennes Statistics Seminar
Time: 2:00 pm
Date: 29th of January 2021
Place: ENSAI-Campus de Ker Lann-35172 Bruz-France

Roberto Oliveira IMPA (Brésil) – “Sample average approximation with heavier tails”

Abstract: Consider an “ideal” optimization problem where constraints and objective function are defined in terms of expectations over some distribution P. The sample average approximation (SAA) — a fundamental idea in stochastic optimization — consists of replacing the expectations by an average over a sample from P. A key question is how much the solutions of the SAA differ from those of the original problem. Results by Shapiro from many years ago consider what happens asymptotically when the sample size diverges, especially when the solution of the ideal problem lies on the boundary of the feasible set. In joint work with Philip Thompson, we consider what happens with finite samples. As we will see, our results improve upon the nonasymptotic state of the art in various ways: we allow for heavier tails, unbounded feasible sets, and obtain bounds that (in favorable cases) only depend on the geometry of the feasible set around the optimal solution. Our results combine “localization” and “fixed-point” type arguments by Mendelson with chaining-type inequalities. One of our contributions is showing what can be said when the SAA constraints are random.

Organizers:
Adrien SAUMARD (CREST – ENSAI)
Sponsors:
CREST