Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Data-driven algorithm design, that is, choosing the best algorithm for a specific application, is a crucial problem in modern data science. Practitioners often optimize over a parameterized algorithm family, tuning parameters based on problems from their domain. These procedures have historically come with no guarantees, though a recent line of work studies algorithm selection from a theoretical perspective. We advance the foundations of this field in several directions: we analyze online algorithm selection, where problems arrive one-by-one and the goal is to minimize regret, and private algorithm selection, where the goal is to find good parameters over a set of problems without revealing sensitive information contained therein. We study important algorithm families, including SDP-rounding schemes for problems formulated as integer quadratic programs, and greedy techniques for canonical subset selection problems. In these cases, the algorithm's performance is a volatile and piecewise Lipschitz function of its parameters, since tweaking the parameters can completely change the algorithm's behavior. We give a sufficient and general condition, dispersion, defining a family of piecewise Lipschitz functions that can be optimized online and privately, which includes the functions measuring the performance of the algorithms we study. Intuitively, a set of piecewise Lipschitz functions is dispersed if no small region contains many of the functions' discontinuities. We present general techniques for online and private optimization of the sum of dispersed piecewise Lipschitz functions. We improve over the best-known regret bounds for a variety of problems, prove regret bounds for problems not previously studied, and give matching lower bounds. We also give matching upper and lower bounds on the utility loss due to privacy. Moreover, we uncover dispersion in auction design and pricing problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Machine Learning Assisted Inverse Design of Microresonators
The high demand for fabricating microresonators with desired optical properties has led to various techniques to optimize geometries, mode structures, nonlinearities and dispersion. Depending on applications, the dispers…
Data-driven peakon and periodic peakon travelling wave solutions of some nonlinear dispersive equations via deep learning
In the field of mathematical physics, there exist many physically interesting nonlinear dispersive equations with peakon solutions, which are solitary waves with discontinuous first-order derivative at the wave peak. In …
Experimental DesignRAR-PINN algorithm for the data-driven vector-soliton solutions and parameter discovery of coupled nonlinear equations
This work aims to provide an effective deep learning framework to predict the vector-soliton solutions of the coupled nonlinear equations and their interactions. The method we propose here is a physics-informed neural ne…
A Machine Learning-Based Detection Technique for Optical Fiber Nonlinearity Mitigation
We investigate the performance of a machine learning classification technique, called the Parzen window, to mitigate the fiber nonlinearity in the context of dispersion managed and dispersion unmanaged systems. The techn…
BIG-bench Machine LearningGeneral ClassificationEnd-to-end data-driven prediction of urban airflow and pollutant dispersion
Climate change and the rapid growth of urban populations are intensifying environmental stresses within cities, making the behavior of urban atmospheric flows a critical factor in public health, energy use, and overall l…