2017/11/08 by Maria-Florina Balcan, Travis Dick, Balcan, Maria-Florina +3 · 5 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1711.03091
Data-driven algorithm design, that is, choosing the best algorithm for a\nspecific application, is a crucial problem in modern data science.\nPractitioners often optimize over a parameterized algorithm family, tuning\nparameters based on problems from their domain. These procedures have\nhistorically come with no guarantees, though a recent line of work studies\nalgorithm selection from a theoretical perspective. We advance the foundations\nof this field in several directions: we analyze online algorithm selection,\nwhere problems arrive one-by-one and the goal is to minimize regret, and\nprivate algorithm selection, where the goal is to find good parameters over a\nset of problems without revealing sensitive information contained therein. We\nstudy important algorithm families, including SDP-rounding schemes for problems\nformulated as integer quadratic programs, and greedy techniques for canonical\nsubset selection problems. In these cases, the algorithm's performance is a\nvolatile and piecewise Lipschitz function of its parameters, since tweaking the\nparameters can completely change the algorithm's behavior. We give a sufficient\nand general condition, dispersion, defining a family of piecewise Lipschitz\nfunctions that can be optimized online and privately, which includes the\nfunctions measuring the performance of the algorithms we study. Intuitively, a\nset of piecewise Lipschitz functions is dispersed if no small region contains\nmany of the functions' discontinuities. We present general techniques for\nonline and private optimization of the sum of dispersed piecewise Lipschitz\nfunctions. We improve over the best-known regret bounds for a variety of\nproblems, prove regret bounds for problems not previously studied, and give\nmatching lower bounds. We also give matching upper and lower bounds on the\nutility loss due to privacy. Moreover, we uncover dispersion in auction design\nand pricing problems.\n