Learning Robust Algorithms for Online Allocation Problems Using
  Adversarial Training
  We address the challenge of finding algorithms for online allocation (i.e.
bipartite matching) using a machine learning approach. In this paper, we focus
on the AdWords problem, which is a classical online budgeted matching problem
of both theoretical and practical significance. In contrast to existing work,
our goal is to accomplish algorithm design {\em tabula rasa}, i.e., without any
human-provided insights or expert-tuned training data beyond specifying the
objective and constraints of the optimization problem. We construct a framework
based on insights and ideas from game theory, adversarial training and GANs Key
to our approach is to generate adversarial examples that expose the weakness of
any given algorithm. A unique challenge in our context is to generate complete
examples from scratch rather than perturbing given examples and we demonstrate
this can be accomplished for the Adwords problem. We use this framework to
co-train an algorithm network and an adversarial network against each other
until they converge to an equilibrium. This approach finds algorithms and
adversarial examples that are consistent with known optimal results. Secondly,
we address the question of robustness of the algorithm, namely can we design
algorithms that are both strong under practical distributions, as well as
exhibit robust performance against adversarial instances. To accomplish this,
we train algorithm networks using a mixture of adversarial and practical
distributions like power-laws; the resulting networks exhibit a smooth
trade-off between the two input regimes.
