This work appears as: Smoothed Analysis of the Perceptron Algorithm. Avrim Blum and John Dunagan. SODA '02, pages 905--914.
This work appears as: Static Optimality and Dynamic Search-Optimality in Lists and Trees. Avrim Blum, Shuchi Chawla and Adam Kalai. SODA '02, pages 1-8.
An interesting feature of this clustering formulation is that one does not need to specify the number of clusters k as a separate parameter, as in measures such as k-median or min-sum or min-max clustering. Instead, in our formulation, the optimal number of clusters could be any value between 1 and n, depending on the edge labels. We look at approximation algorithms for both minimizing disagreements and for maximizing agreements. For minimizing disagreements, we give a constant factor approximation. For maximizing agreements we give a PTAS, building on ideas of [GGR98] and [Vega95]. We also show how to extend some of these results to graphs with edge labels in [-1,+1], and give some results for the case of random noise.
This work appears as: Correlation Clustering. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. FOCS'02, pages 238--247.
This work uses online learning tools to develop a polynomial-time algorithm for performing nearly as well as the best fixed routing in hindsight, in a repeated "oblivious routing game". In this setting the algorithm is allowed to choose a new routing each night, but is still oblivious to the demands that will occur the next day. This result is a strengthening of a recent result of Azar et al., who gave a polynomial time algorithm to find the minimax optimal strategy in this game. It is a strengthening in that it achieves a competitive ratio arbitrarily to close to that of Azar et al., while at the same time performing nearly as well as the optimal static routing for the sequence of demands that actually occurred.
The call-control problem has the interesting property that algorithms designed to achieve a good competitive ratio in terms of fraction of calls accepted can often be quite different from algorithms designed to achieve a good ratio in terms of the fraction rejected. We consider the problem: given an algorithm A with competitive ratio c_A for fraction accepted, and an algorithm R with ratio c_R in terms of fraction rejected, can we combine them into a single algorithm that does well under both measures? We do this achieving ratio O(c_A^2) for acceptance and O(c_A c_R) for rejection.
We introduce a problem called Statistical Query Sampling that models an issue that arises in NMR quantum computing. We give a number of lower bounds for this problem, based on techniques developed for the (more standard) problem of Statistical Query Learning.
This work shows how known results on Membership query learning can be used to provide efficient algorithms for the important problem of preference elicitation in combinatorial auctions. This work also gives a number of (positive and negative) results for the subsequent allocation problem.
Continuing on the above work, this paper explores at the model level what the similarities and differences are between preference elicitation and membership query learning. When is one easier than the other, when are they equivalent, etc. Preference elicitation is much like MQ learning in the presence of multiple real-valued functions, except the final goal is not so much to learn the functions but rather to determine an optimal allocation of goods.
This work looks at fast algorithms for finding "minimax optimal plans" in a certain adversarial MDP setting. Includes some experimental results on a robot navigation domain.
Attempts to unify a number of bounds (including VC-dimension and PAC-Bayes) in a single MDL framework. In this setting, Alice has a set of labeled examples, Bob has the same examples but without labels, and Alice's job is to communicate the labels to Bob using only a small number of bits. The standard Occam's razor results say that if Alice can do this by sending a hypothesis (a function h(x) over single examples that Bob would then run m times) then she can be confident in the predictive ability of that hypothesis. But what about other methods of communicating labels? Extending Occam's razor to generic communication schemes requires a bit of "definition design" but can then encompass the more powerful VC-dimension and PAC-Bayes bounds.
Considers the problem of job scheduling to minimize flow time, when the server is allowed to reject jobs at some penalty. This can be thought of the problem of managing your to-do list, when your cost function is the total amount of time that jobs are sitting on your stack plus a cost for each job that you say "no" to. These are added, so if you initially agree to a task (like refereeing a paper) and then six months later you realize you cannot do it and say no, you pay both for the "no" and for the six months it has been sitting on your desk. We give 2-competitive online algorithms for the case of unweighted flow time and uniform costs, and extend some of our results to the case of weighted flow time and machines with varying speeds. We also give a resource augmentation result for the case of arbitrary penalties achieving a competitive ratio of $O(\frac 1\epsilon(\log{W}+\log{C})^2)$ using a $(1+\epsilon)$ speed processor. Finally, we present a number of lower bounds for both the case of uniform and arbitrary penalties.
Gives the first known constant-factor approximation algorithm for the rooted Orienteering problem in general metric spaces, and for a new problem that we call the Discounted-Reward TSP. Given a weighted undirected graph with rewards on nodes, and a start node s, the goal in the Orienteering Problem is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor gamma, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by gamma^t. This is similar to the objective in MDPs except we only receive a reward the first time a node is visited.
Consider a version of the metric TSP problem in which each node has a value and the goal is to collect as much value as possible, *but* each node also has a deadline and only counts if it is reached by its deadline. (More generally, nodes might have release dates too.) We give an O(log n) apx for deadlines, O(min[log^2 n, log D_max]) for time-windows, and a bicriteria approximation with the interesting property that it can achieve an O(k)-approximation while violating the deadlines by only a (1 + 1/2^k) factor. We do not know if one can achieve a true constant-factor approximation (i.e., without violating deadlines).
We show how the recent, elegant result of Kalai and Vempala for online geometric optimization can be extended to the "bandit" version of the problem, in which one is only told of the cost incurred and not the full cost vector, even in the repeated-game setting (an adaptive adversary).
Kernel functions are typically viewed as implicit mappings to a high-dimensional space that allow one to "magically" get the power of that space without having to pay for it, if data is separable in that space by a large margin. In this paper we show that in the presence of a large margin, a kernel can instead be efficiently converted into a mapping to a low dimensional space. In particular, we give an efficient procedure that, given black-box access to the kernel and unlabeled data, generates a small number of features that approximately preserve both separability and margin.
We consider a randomized version of the mincut approach to learning from labeled and unlabeled data (see paper with Shuchi Chawla from 2001), and motivate it from both a sample-complexity perspective and from the goal of approximating Markov Random Field per-node probabilities.
Use analysis of random walks to detect stepping-stone attacks under the "maximum delay bound" assumption. Gives learning-style bounds on number of packets that need to be observed to perform detection at a desired confidence level.