Latest issueUW-Madison picks Rashid Bashir as its next chancellorRead now

Classes & TalksFriday, December 4

ISyE Colloquia Series

Friday, December 4 · 12-1 p.m. · 1163 Mechanical Engineering

12-1 p.m.
When
  • Friday, December 4 · 12-1 p.m.
Where
1163 Mechanical Engineering1513 University Ave. · Madison, WI · 53706
Good to know
Free

The event’s page Add to my calendarOpen in Maps

About this event

@

UW-ISyE looks forward to welcoming Professor Amitabh Basu from John’s Hopkins University.

Sample Complexity of Stochastic Optimization with Integer Variables

We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuous optimization problem. We show that integer optimization can sometimes require strictly more samples and sometimes strictly smaller number of samples, depending on the structure of the objective and constraints.

• For Lipschitz objectives over subsets of \ell_\infty balls, the statistical complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization is exactly the same as stochastic linear optimization with just bound constraints.

• For Lipschitz objectives over subsets of \ell_2 balls, we show that integer optimization can require strictly smaller sample size compared to the continuous setting in a certain regime. To get to this result, we also establish tight sample complexity results for nonconvex continuous stochastic optimization which, to the best of our knowledge, do not appear in prior work.

• For strongly convex, smooth objectives, integer optimization has high statistical complexity compared to the continuous setting. In particular, we show that integer optimization requires \Omega(1/\epsilon^2) samples to report an \epsilon-approximate solution, compared to the well-known O(1/\epsilon) sample complexity from the continuous optimization literature.

In all three settings, sample average approximation (SAA) or empirical risk minimization (ERM), is optimal up to constants: the lower bounds hold for every data-driven algorithm. We also extend our results to \ell_p balls beyond p=2, \infty, and over finite precision grids.

Bio : Amitabh Basu is Professor of Applied Mathematics and Statistics at Johns Hopkins University. He received his Ph.D. from Carnegie Mellon University in 2010 and did postdoctoral work in the Dept. of Mathematics at the University of California, Davis from 2010-2013. His main research interests are in mathematical optimization and its applications, with an emphasis on problems with a combinatorial or discrete flavor. He serves on the editorial boards of Mathematics of Operations Research, Discrete Optimization, MOS-SIAM Series on Optimization, Mathematical Programming, and SIAM Journal on Optimization. His work has been recognized by the NSF Career award and the Egon Balas Prize from the INFORMS Optimization Society.

Add to calendar

•

Google Calendar

•

iCalendar

•

Outlook 365

•

Outlook Live

Listed by engineering.wisc.edu (The Events Calendar), gathered by the Madison events calendar.

Does something look wrong?

Promote

Location

1163 Mechanical Engineering1513 University Ave. · Madison, WI 53706

Get directions