Timezone: »

Learning Online Algorithms with Distributional Advice
Ilias Diakonikolas · Vasilis Kontonis · Christos Tzamos · Ali Vakilian · Nikos Zarifis

Thu Jul 22 08:30 PM -- 08:35 PM (PDT) @
We study the problem of designing online algorithms given advice about the input. While prior work had focused on deterministic advice, we only assume distributional access to the instances of interest, and the goal is to learn a competitive algorithm given access to i.i.d. samples. We aim to be competitive against an adversary with prior knowledge of the distribution, while also performing well against worst-case inputs. We focus on the classical online problems of ski-rental and prophet-inequalities, and provide sample complexity bounds for the underlying learning tasks. First, we point out that for general distributions it is information-theoretically impossible to beat the worst-case competitive-ratio with any finite sample size. As our main contribution, we establish strong positive results for well-behaved distributions. Specifically, for the broad class of log-concave distributions, we show that $\mathrm{poly}(1/\epsilon)$ samples suffice to obtain $(1+\epsilon)$-competitive ratio. Finally, we show that this sample upper bound is close to best possible, even for very simple classes of distributions.

Author Information

Ilias Diakonikolas (University of Wisconsin-Madison)
Ilias Diakonikolas

Ilias Diakonikolas is a faculty member in the CS Department at UW Madison. He obtained a Diploma in electrical and computer engineering from the National Technical University of Athens and a Ph.D. in computer science from Columbia University. Before moving to UW, Ilias was Andrew and Erna Viterbi Early Career Chair at USC, and prior to that he spent two years at UC Berkeley as a Simons fellow in theoretical computer science. His research focuses on designing efficient algorithms for various fundamental problems in machine learning. Ilias is a recipient of a Sloan Fellowship, an NSF CAREER Award, a Google Faculty Research Award, a Marie Curie Fellowship, the best paper award at NeurIPS 2019, the IBM Research Pat Goldberg best paper award, and an honorable mention in the George Nicholson competition from the INFORMS society.

Vasilis Kontonis (University of Wisconsin-Madison)
Christos Tzamos (UW-Madison)

Christos Tzamos is an Assistant Professor in the Department of Computer Sciences at University of Wisconsin-Madison. His research interests lie in the interface of Theoretical Computer Science with Economics and Game Theory, Machine Learning, Statistics and Probability Theory. He obtained his PhD from the Theory of Computation group of MIT advised by Costis Daskalakis. He holds a bachelors degree from NTUA, and was a postdoctoral researcher at Microsoft Research (New England) working on Mechanism Design, Algorithms and Machine Learning. He is the recipient of a Simons Foundation award, the George M. Sprowls award, the best paper and the best student paper award in EC 2013 and the outstanding paper award in NeurIPS 2019.

Ali Vakilian (Toyota Technological Institute at Chicago)
Nikos Zarifis (UW Madison)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors