Timezone: »

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

Thu Jul 22 09:00 PM -- 11:00 PM (PDT) @ Virtual
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 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.