results for au:Dick_T in:cs
Nov 09 2017 cs.LG
In this work, we present online and differentially private optimization algorithms for a large family of nonconvex functions. This family consists of piecewise Lipschitz functions, which are ubiquitous across diverse domains. For example, problems in computational economics and algorithm configuration (also known as parameter tuning) often reduce to maximizing piecewise Lipschitz functions. These functions are challenging to optimize privately and online since a small error can push an optimal point into a nonoptimal region. We introduce a sufficient and general dispersion condition on these functions that ensures well-known private and online algorithms have strong utility guarantees. We show that several important problems from computational economics and algorithm configuration reduce to optimizing functions that satisfy this condition. We apply our results to obtain private and online algorithms for these problems. We thus answer several open questions: Cohen-Addad and Kanade ['17] asked how to optimize piecewise Lipschitz functions online and Gupta and Roughgarden ['17] asked what algorithm configuration problems can be solved online with no regret algorithms. In algorithm configuration, the goal is to tune an algorithm's parameters to optimize its performance over a specific application domain. We analyze greedy techniques for subset selection problems and SDP-rounding schemes for problems that can be formulated as integer quadratic programs. In mechanism design and other pricing problems, the goal is to use information about past consumers to design auctions and set prices that extract high profit from future consumers. We analyze the classic classes of second price auctions with reserves and posted price mechanisms. For all of these settings, our general technique implies strong utility bounds in the private setting and strong regret bounds in the online learning setting.
In distributed machine learning, data is dispatched to multiple machines for processing. Motivated by the fact that similar data points often belong to the same or similar classes, and more generally, classification rules of high accuracy tend to be "locally simple but globally complex" (Vapnik & Bottou 1993), we propose data dependent dispatching that takes advantage of such structure. We present an in-depth analysis of this model, providing new algorithms with provable worst-case guarantees, analysis proving existing scalable heuristics perform well in natural non worst-case conditions, and techniques for extending a dispatching rule from a small sample to the entire distribution. We overcome novel technical challenges to satisfy important conditions for accurate distributed learning, including fault tolerance and balancedness. We empirically compare our approach with baselines based on random partitioning, balanced partition trees, and locality sensitive hashing, showing that we achieve significantly higher accuracy on both synthetic and real world image and advertising datasets. We also demonstrate that our technique strongly scales with the available computing power.
Nov 11 2015 cs.LG
We present a new perspective on the popular multi-class algorithmic techniques of one-vs-all and error correcting output codes. Rather than studying the behavior of these techniques for supervised learning, we establish a connection between the success of these methods and the existence of label-efficient learning procedures. We show that in both the realizable and agnostic cases, if output codes are successful at learning from labeled data, they implicitly assume structure on how the classes are related. By making that structure explicit, we design learning algorithms to recover the classes with low label complexity. We provide results for the commonly studied cases of one-vs-all learning and when the codewords of the classes are well separated. We additionally consider the more challenging case where the codewords are not well separated, but satisfy a boundary features condition that captures the natural intuition that every bit of the codewords should be significant.