home | research interests | favorite links | survey talks

Working papers

• Clustering under Natural Stability Assumptions. With Pranjal Awasthi and Or Sheffet.
  In this paper we give algorithms for k-median and other center-based clustering objectives, under two natural stability assumptions. We first consider an assumption analyzed by Bilu and Linial [BL10] in the context of max-cut, that the optimal solution is stable to perturbations in the metric space. Here, we show that for any center-based clustering objective, we can efficiently find the optimal solution assuming stability to constant-sized perturbations (for max-cut, [BL10] require stability to perturbations of size sqrt(n)). We next consider an assumption analyzed by Balcan et al [BBG09] that the solution is stable with respect to approximations in the objective. Here, we relax the condition to require good behavior only for approximations in which each point is assigned to its nearest center, which now allows for clusters in the optimum solution to be quite close together. Nonetheless, we show that for the k-median objective, for any alpha>0, under the assumption that all such approximations yield the same partitioning, it is possible to obtain an optimal solution in polynomial time.

Publications

2010

• Circumventing the Price of Anarchy: Leading Dynamics to Good behavior. With Nina Balcan and Yishay Mansour. ICS 2010.
  We explore the problem of how self-interested agents with some knowledge of the game might be able to quickly find their way to states of quality close to the best equilibrium in games with high price of anarchy but low price of stability. We consider two natural learning models in which players adaptively decide between greedy behavior and following a proposed good but untrusted strategy and analyze two important classes of games in this context, fair cost-sharing and consensus games. These games both have very high Price of Anarchy and yet we show that behavior in these models can efficiently reach low-cost states.

2009

• Tracking Dynamic Sources of Malicious Activity at Internet-Scale. With Shobha Venkataraman, Dawn Song, Subhabrata Sen, and Oliver Spatscheck. NIPS 2009.
  We consider the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision tree (in particular, the IP address-space tree), but with additional challenges: (1) severe space requirements, since the underlying decision tree has over 4 billion leaves, and (2) a changing target function, since malicious activity on the Internet is dynamic. We present a novel algorithm that addresses this problem, by combining "experts" and online paging algorithms. We prove guarantees on our algorithm's performance as a function of the best possible pruning of a similar size, and our experiments show that our algorithm achieves high accuracy on large real-world data sets, improving over existing approaches.

• The Price of Uncertainty. With Nina Balcan and Yishay Mansour. ACM-EC 2009. [slides]
  We study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We consider a wide variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations can cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation. We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show that in certain cases (e.g., fair cost-sharing, set-covering, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition to states of substantially higher cost, whereas in others (e.g., the class of beta-nice games which includes routing, market-sharing and many others) these dynamics are much more resilient.

• Approximate Clustering without the Approximation. With Nina Balcan and Anupam Gupta. SODA 2009.
  For most clustering problems, our true goal is to classify the points correctly, and commonly studied objectives such as k-median, k-means, and min-sum are really only a proxy. That is, there is some unknown correct clustering (grouping proteins by their function or grouping images by who is in them) and the implicit hope is that approximately optimizing these objectives will in fact produce a clustering that is close pointwise to the correct answer. In this paper, we show that if we make this implicit assumption explicit---that is, if we assume that any c-approximation to the given clustering objective F is epsilon-close to the target---then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for k-median and k-means objectives, we show that we can achieve this guarantee for any constant c > 1, and for min-sum objective we can do this for any constant c > 2. Our results also highlight a difference between assuming that the optimal solution to, say, the k-median objective is epsilon-close to the target, and assuming that any approximately optimal solution is epsilon-close to the target. In the former case, the problem of finding a solution that is O(epsilon)-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.

• Improved Equilibria via Public Service Advertising. With Nina Balcan and Yishay Mansour. SODA 2009.
  Many natural games have both good and bad Nash equilibria. In such cases, one could hope to improve poor behavior by a "public service advertising campaign" encouraging players to follow a good equilibrium, and if every player follows the advice then we are done. However, it is a bit much to assume that everyone will follow along. In this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. Unlike in the ``value of altruism'' model, we assume everyone will ultimately act in their own interest. We analyze this question for several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, and party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random alpha fraction of the population following the given advice is sufficient to get a guarantee within an O(1/alpha) factor of the price of stability for any alpha > 0. However, for some games (such as party affiliation games), there is a strict threshold (in this case, alpha < 1/2 yields almost no benefit, yet alpha > 1/2 is enough to reach near-optimal behavior), and for some games, such as scheduling, no value alpha < 1 is sufficient.

2008

• Clustering with Interactive Feedback. With Nina Balcan. ALT 2008.
  We initiate a theoretical study of the problem of clustering data under interactive feedback. We introduce a query-based model in which users can provide feedback to a clustering algorithm in a natural way via split and merge requests. We then analyze the ``clusterability'' of different concept classes in this framework --- the ability to cluster correctly with a bounded number of requests under only the assumption that each cluster can be described by a concept in the class --- and provide efficient algorithms as well as information-theoretic upper and lower bounds.

• Improved Guarantees for Learning via Similarity Functions. With Nina Balcan and Nati Srebro. COLT 2008.
  We provide a new broader notion of a "good similarity function" that improves in two important ways upon the notion in [BB06]. First, as before, any large-margin kernel is also a good similarity function in our sense, but now with a much milder degradation of the parameters. Second, we can show that for distribution-specific PAC learning, the new notion is strictly more powerful that the traditional notion of a large-margin kernel: although any concept class that can be learned with some kernel function can also be learned using our new similarity based approach, the reverse is not true. (In contrast, the [BB06] definition is no more powerful than kernels for distribution-specific learning.) Our new notion of similarity relies upon L_1 regularized learning, and our separation result is related to a separation result between what is learnable with L_1 vs. L_2 regularization.

• Item Pricing for Revenue Maximization. With Nina Balcan and Yishay Mansour. ACM-EC 2008.
  This paper considers the problem of pricing items to maximize revenue from buyers with unknown complex preferences over bundles, and presents two main results. (1) for the case of unlimited supply, a random single price achieves a logarithmic approximation for buyers with general valuation functions (not just single-minded or unit-demand as was previously known). (2) for the case of limited supply, a random single price (with buyers arriving in an arbitrary order) achieves an exp(sqrt(log(n)loglog(n))) approximation, with a near-matching lower bound. Also includes results for multi-unit auctions and "simple submodular" valuations. An earlier tech report with just the first result appears here.

• A Discriminative Framework for Clustering via Similarity Functions. With Nina Balcan and Santosh Vempala. STOC 2008. [journal submission (2009)]
  Theoretical treatments of clustering from pairwise similarity information typically view the similarity information as ground-truth and then design algorithms to (approximately) optimize various graph-based objective functions. However, in most applications, this similarity information is merely based on some heuristic: the true goal is to cluster the points correctly rather than to optimize any specific graph property. In this work, we develop a theoretical framework for clustering from this perspective. In particular, motivated by work in learning theory that asks ``what natural properties of a similarity (or kernel) function are sufficient to be able to learn well?'' we ask ``what natural properties of a similarity function are sufficient to be able to cluster well?'' Our approach can be viewed as developing a PAC model for clustering, where the natural object of study, rather than being a concept class, is more like a class of (concept, distribution) pairs.

• Regret Minimization and the Price of Total Anarchy. With MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. STOC 2008.
  This paper proposes weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium, we assume only that selfish players play so as to minimize their own regret. Regret minimization can be done via simple, efficient algorithms even in many settings where the number of action choices for each player is exponential in the natural parameters of the problem. We prove that despite our weakened assumptions, in several broad classes of games, this ``price of total anarchy'' matches the Nash price of anarchy, even though play may never converge to Nash equilibrium. We also show that the price of total anarchy is in many cases resilient to the presence of Byzantine players, about whom we make no assumptions.

• A Learning Theory Approach to Non-Interactive Database Privacy. With Katrina Ligett and Aaron Roth. STOC 2008.
  We demonstrate that, ignoring computational constraints, it is possible to release databases preserving differential privacy that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We also present an efficient algorithm for "large margin halfspace" queries. In addition, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than differential privacy.

• Veritas: Combining expert opinions without labeled data.. With Sharath Cholleti (lead author), Sally Goldman, David Politte, and Steven Don. IEEE International Conference on Tools with Artificial Intelligence, 2008.
  Looks at a boosting-based method for combining expert opinions when only unlabeled data is present, motivated by the problem of segmenting lung nodules in CT scans.

2007

• Mechanism Design, Machine Learning, and Pricing Problems. With Nina Balcan. SIGecom Exchanges 2007, special issue on Combinatorial Auctions.
  Short survey article on machine learning techniques for mechanism design.

• A Theory of Loss-Leaders: Making Money by Pricing Below Cost. With Nina Balcan, T-H. Hubert Chan and MohammadTaghi Hajiaghayi. WINE 2007.

• Separating Populations with Wide Data: a Spectral Analysis. With Amin Coja-Oghlan, Alan Frieze, and Shuheng Zhou. 18th International Symposium on Algorithms and Computation (ISAAC 2007). LNCS 4835, pp. 439-451.
  We consider the problem of partitioning a small data sample drawn from a mixture of k product distributions. We are interested in the case that individual features are of low average quality gamma, and we want to use as few of them as possible to correctly partition the sample. We analyze a spectral technique that is able to approximately optimize the total data size---the product of number of data points n and the number of features K---needed to correctly perform this partitioning as a function of 1/gamma for K>n. Our goal is motivated by an application in clustering individuals according to their population of origin using markers, when the divergence between any two of the populations is small.

• Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. With David Abraham and Tuomas Sandholm. ACM-EC 2007.
  Shows how MIP techniques can be used to get a more scalable and robust algorithm for solving optimization problems involved in clearing paired-donation kidney exchanges. Algorithm is currently in use by the Alliance for Paired Donation.

• Learning, Regret Minimization, and Equilibria [ps]. With Yishay Mansour. Book chapter in Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani, eds. [Slides for related talk]
  Book chapter describing connections between online learning and game theory. Includes description of algorithms for combining expert advice (minimizing external regret), algorithms for the stronger goal of minimizing internal regret, algorithms for the limited-feedback (multi-arm bandit) setting, and connections between these and minimax optimality (for zero-sum games) and correlated equilibria (for general-sum games). Also discusses how such algorithms will approach Nash equilibrium in non-atomic routing games.

• FiG: Automatic Fingerprint Generation. With Juan Caballero, Shobha Venkataraman, Pongsin Poosankam, Min Gyung Kang, and Dawn Song. In NDSS 2007.

• Open Problems in Efficient Semi-Supervised PAC Learning. With Nina Balcan. COLT'07 Open Problems List.
  Open problems about computationally-efficient semi-supervised learning that I would love to see solved (small monetary rewards offered).

2006

• On a Theory of Learning with Similarity Functions. With Nina Balcan. International Conference on Machine Learning (ICML), pp. 73-80, 2006. Journal version combines this conference paper with subsequent paper of Nati Srebro from COLT 2007: Machine Learning Journal 72(1-2):89-112, August, 2008. DOI 10.1007/s10994-008-5059-5. [NIPS'05 workshop talk] [Cornell'07 colloquium talk (broader)]
  Kernel functions have become an extremely popular tool in machine learning. They have an attractive theory that describes a kernel function as being good for a given learning problem if data is separable by a large margin in a (possibly very high-dimensional) implicit space defined by the kernel. This theory, however, has a bit of a disconnect with the intuition of a good kernel as a good similarity function. In this work we develop an alternative theory of learning with similarity functions more generally (i.e., sufficient conditions for a similarity function to allow one to learn well) that does not require reference to implicit spaces, and does not require the function to be positive semi-definite. Our results also generalize the standard theory in the sense that any good kernel function under the usual definition can be shown to also be a good similarity function under our definition (though with some loss in the parameters). In this way, we provide the first steps towards a theory of kernels that describes the effectiveness of a given kernel function in terms of natural similarity-based properties.

• Routing without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games. With Eyal Even-Dar and Katrina Ligett. PODC, pp. 45-52, 2006. [Slides for related talk]
  A number of no-regret algorithms have been developed in the game-theory and online learning literature. This paper considers the question: if each player in a routing game uses a no-regret strategy to choose their route on day t+1 based on their experience on days 1,...,t, what can we say about the overall behavior of the system? The main result of this paper is that in the Roughgarden-Tardos setting of multicommodity flow and infinitesimal agents, if each player uses a no-regret strategy then a 1-epsilon fraction of the daily flows will be epsilon-Nash (almost all users having only a small incentive to deviate) where epsilon approaches 0 at a rate that depends polynomially on the players' regret bounds and the maximum slope of any latency function.

• Approximation Algorithms and Online Mechanisms for Item Pricing. With Nina Balcan. Theory of Computing, 3/9:179-195, 2007. Originally appeared in ACM Conference on Electronic Commerce, pp. 29-35, 2006. [Slides for talk given at Spencer06-60]
  Presents approximation and online algorithms for a number of problems of pricing items so as to maximize a seller's revenue in an unlimited supply setting. Our main result is an O(k)-approximation for pricing items to single-minded bidders who each want at most k items. For the case k=2 (where we get a 4-approximation) this can be viewed as the following graph vertex pricing problem: given a graph G with valuations v_e on the edges, find prices p_i for the vertices to maximize sum_{e=(i,j): v_e >= p_i+p_j} p_i + p_j. We also show how these algorithms can be applied to the online setting, in which customers arrive over time and must be presented with prices that depend only on information gained from customers seen in the past.

• A Random-Surfer Web-Graph Model With Hubert Chan and Mugizi Rwebangira. ANALCO '06.
  This paper gives theoretical and experimental results on a random-surfer model for construction of a random graph. In this model, a new node connects to the existing graph by choosing a start node at random and then performing a short random walk, flipping a coin at each node visited to decide whether or not to stop and connect there. Our understanding of this model is still quite preliminary, though. Many open questions.

• Random Projection, Margins, Kernels, and Feature-Selection [ps]. LNCS 3940, pp. 52-68, 2006. Survey article based on an invited talk given at the 2005 PASCAL Workshop on Subspace, Latent Structure and Feature selection techniques.
  Random projection is a simple technique that has had a number of applications in algorithm design. In the context of machine learning, it can provide insight into questions such as ``why is a learning problem easier if data is separable by a large margin?'' and ``in what sense is choosing a kernel much like choosing a set of features?'' This article is intended to provide an introduction to random projection and to survey some simple learning algorithms and other applications to learning based on it. Portions of this article are based on work in [BB05,BBV04] joint with Nina Balcan and Santosh Vempala.

2005

• Reducing Mechanism Design to Algorithm Design via Machine Learning [short version, long version]. With Nina Balcan, Jason Hartline, and Yishay Mansour. JCSS 74:1245-1270, 2008 (JCSS special issue on Learning Theory). Originally appeared as "Mechanism Design via Machine Learning", FOCS 2005. [slides]
  Examines how sample-complexity arguments in machine learning can be used to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide class of revenue-maximizing pricing problems.

• From External to Internal Regret [local ps] [local pdf]. With Yishay Mansour. JMLR 8(Jun):1307--1324, 2007. Originally appeared in COLT 2005.
  Gives a generic method for converting external-regret algorithms to internal-regret algorithms, along with a specific algorithm for the bandit setting. Also gives a new simple method for a generalized "sleeping experts" setting. If you are interested in this paper you should definitely also check out Stoltz and Lugosi, "Internal Regret in On-Line Portfolio Selection", MLJ 59 (1/2), 2005. Their paper gives a different conversion procedure and has a number of other results. See also Gilles Stoltz's PhD thesis.

• A Discriminative Model for Semi-Supervised Learning. With Nina Balcan. To appear in JACM. (Original COLT '05 paper titled "A PAC-style Model for Learning from Labeled and Unlabeled Data")
  This paper gives an extension to the PAC model that allows one to discuss ways of using unlabeled data to help with learning. The basic idea is that rather than "learning a class C", one instead talks of "learning a class C under compatibility notion χ", where χ(h,D) tells how a-priori compatible a proposed hypothesis h is with respect to a given distribution D. E.g., if you believe there should be a large-margin separator then your χ would give a low score to h's with large probability mass near the separating hyperplane. Or in co-training, χ would penalize hypotheses (h_1,h_2) such that Pr_x(h_1(x) ≠ h_2(x)) is large. If χ is "legal" (in a sense defined in the paper) then we can use this model to give sample-complexity bounds for both labeled and unlabeled data, and talk about conditions under which unlabeled data can significantly reduce the number of labeled examples needed. We also talk about well-justified ways of performing regularization in this setting and give a number of algorithmic results as well.

• Practical Privacy: The SuLQ Framework. With Cynthia Dwork, Frank McSherry, and Kobbi Nissim. PODS 2005.

• New Streaming Algorithms for Fast Detection of Superspreaders. With Shobha Venkataraman, Dawn Song, and Phillip Gibbons. NDSS 2005.
  Experimental and theoretical work on streaming algorithms (one pass, logarithmic memory) for detecting sources that send to many distinct destinations. That is, given a sequence of (x,y) pairs, you want to identify those x's that have appeared paired with many different y's.

• Near-Optimal Online Auctions. With Jason Hartline. SODA 2005, pages 1156--1163.
  Uses an approach based on an online learning algorithm of Kalai to get improved bounds for the problem of adaptive pricing of a digital good. We consider both the online auction and posted price settings.

2004

• Co-Training and Expansion: Towards Bridging Theory and Practice. With Nina Balcan and Ke Yang. NIPS 2004.
  This paper looks at conditions needed for co-training to succeed in terms of expansion properties of the underlying distribution. Proves bounds for the case that we have base learning algorithms able to make only one-sided error (i.e., learn from positive data only). Expansion is a much weaker condition than those considered previously, such as independence given the label, and appears to be the "right" condition on the distribution needed in order for co-training to work well.

• Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings [local copy]. With Nina Balcan and Santosh Vempala. Machine Learning, 65:79-94, 2006, DOI: 10.1007/s10994-006-7550-1. Extended abstract in 15th International Conference on Algorithmic Learning Theory (ALT '04). Springer LNAI 3244, pp. 194-205, 2004. [talk ppt] Here is a related survey article.
  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.

• Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds. With Dawn Song and Shobha Venkataraman. 7th International Symposium on Recent Advances in Intrusion Detection (RAID '04). Springer LNCS 3224, pp. 258-277, 2004.
  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.

• Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. With Brendan McMahan. COLT '04, pages 109-123.
  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).

• Semi-Supervised Learning Using Randomized Mincuts. With John Lafferty, Mugizi Robert Rwebangira, and Rajashekar Reddy. ICML '04.
  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.

• Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. With Nikhil Bansal, Shuchi Chawla, and Adam Meyerson. STOC '04, pages 166-174.
  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. Big open question: can you get a constant factor apx?

2003

• Approximation Algorithms for Orienteering and Discounted-Reward TSP [local copy]. With Shuchi Chawla, David Karger, Adam Meyerson, Maria Minkoff, and Terran Lane. SIAM J. Computing 37(2):653-670, 2007. An earlier version appears in FOCS'03, pages 46-55. Also available as Tech report CMU-CS-03-121.
  We give a constant-factor approximation algorithm for the rooted Orienteering problem on general graphs, and for a new problem that we call the Discounted-Reward TSP. Given a weighted 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.

• Scheduling for Flow-Time with Admission Control. With Nikhil Bansal, Shuchi Chawla, and Kedar Dhamdhere. ESA '03, pages 43-54.
  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. E.g., 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 and present a number of lower bounds.

• Preference Elicitation and Query Learning. With Jeffrey Jackson, Tuomas Sandholm, and Martin Zinkevich. Journal of Machine Learning Research 5:649--667, 2004 (special issue on Learning Theory). Extended abstract appears in COLT '03.
  Explores the connection between "preference elicitation", a problem that arises in combinatorial auctions, and the problem of learning via queries. Preference elicitation can be thought of as a kind of learning problem with multiple target concepts, but where the goal is not to identify the concepts so much as it is to produce an "optimal example".

• PAC-MDL Bounds. With John Langford. COLT '03.
  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.

• Planning in the Presence of Cost Functions Controlled by an Adversary. With Brendan McMahan and Geoff Gordon. ICML '03.
  Looks at fast algorithms for finding "minimax optimal plans" in a certain adversarial MDP setting. Includes some experimental results on a robot navigation domain.

• On Statistical Query Sampling and NMR Quantum Computing. With Ke Yang. 18th IEEE Conference on Computational Complexity (CCC '03).
  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, and relate it to the (more standard) problem of Statistical Query Learning.

• On Polynomial-Time Preference Elicitation with Value Queries. With Martin Zinkevich and Tuomas Sandholm. ACM Conference on Electronic Commerce, 2003.
  We consider the question of whether interesting classes of preferences can be elicited in polynomial time using value queries. Building on known results on Membership Query learning, we show that read-once formulas over a set of gates motivated from a shopping-agent scenario can be elicited in polynomial time, as well as a class of preferences we call "toolbox DNF". We also give a number of (positive and negative) results for the subsequent allocation problem. For instance, we show how network flow can be used to do allocation efficiently with two bidders with toolbox-DNF preferences.

• Combining Online Algorithms for Rejection and Acceptance. With Yossi Azar and Yishay Mansour. SPAA '03, pages 159-163. Combined with subsequent paper by David Bunde and Yishay Mansour in journal version appearing in Theory of Computing, 1:105-117, 2005.
  The call-control problem has the interesting property that in some versions one can design online algorithms with good competitive ratio in terms of fraction of calls accepted, in some versions one can design algorithms with good C.R. in terms of the fraction rejected, and in some versions one can do both, but in the last case, the algorithms tend to be very different. 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 is good under both measures? We do this achieving ratio O(c_A^2) [improved in journal version to O(c_A)] for acceptance and O(c_A c_R) for rejection.

• Online Oblivious Routing. With Nikhil Bansal, Shuchi Chawla, and Adam Meyerson. 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA '03), pages 44-49.
  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. Our 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.

• Online Learning in Online Auctions. With Vijay Kumar, Atri Rudra, and Felix Wu. SODA '03, pages 202-204. The link points to a somewhat longer version.
  Describes how the Weighted-Majority algorithm can be used to get improved bounds for online auctions of digital goods, as well as for the posted price setting (that corresponds to a "bandit" version of the problem: the auctioneer has to pick a price first, and then only gets the single bit back indicating whether or not the buyer purchased). Also gives some lower bounds.

2002

• Correlation Clustering [local copy]. With Nikhil Bansal and Shuchi Chawla. Machine Learning 56(1-3):89-113, 2004 (Special Issue on Theoretical Advances in Data Clustering). An earlier version appears in FOCS '02, pages 238--247.
  Considers a clustering problem motivated by machine-learning style applications, from the perspective of approximation algorithms. We give a constant-factor approximation under a cost measure and a PTAS under a benefit measure. A nice feature of this clustering formulation is that one does not need to specify the desired number of clusters in advance.

• Smoothed Analysis of the Perceptron Algorithm for Linear Programming. With John Dunagan. SODA '02, pages 905--914.
  This paper shows that the simple Perceptron algorithm has good behavior for linear programming (polynomial-time whp) in the smoothed analysis model of Spielman-Teng. Spielman-Teng had shown this for a specific version of the Simplex algorithm. It is interesting that the bounds for the Perceptron algorithm are better than those known for Simplex in this model, as a function of most of the parameters. The one exception is the "epsilon" term (e.g., if you are interested in a bound that holds on 99% of the instances, then the Perceptron bounds are better, but Perceptron has an epsilon chance of taking time Omega(1/epsilon^2), so does badly in expectation). However, I think the real difference is that Perceptron solves only the feasibility problem, and not the optimization problem. Normally, these are equivalent by simple reduction, but it is not clear that reduction makes sense in the smoothed-analysis model, because it involves a binary-search that will surely create ill-conditioned instances. So, it could well be that feasibility is a strictly easier problem than optimization in this model.

• Online Algorithms for Market Clearing. With Tuomas Sandholm and Martin Zinkevich. JACM 53(5): 845-879, 2006. Extended abstract in SODA '02, pages 971-980.
  We consider the problem of market clearing in a double auction (exchange) where buyers and sellers arrive and depart online. We give algorithms with optimal competitive ratios for several natural objectives and also give a few results having to do with learning and incentive-compatibility.

• Static Optimality and Dynamic Search-Optimality in Lists and Trees. With Shuchi Chawla and Adam Kalai. Algorithmica 36(3):249-260, 2003 (special issue on online algorithms). Originally appeared in Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA), pages 1--8, 2002.
  This paper uses notions from online learning to attack several problems in adaptive data-structures.

2001

• Admission Control to Minimize Rejections. With Adam Kalai and Jon Kleinberg. Internet Mathematics 1(2):165--176, 2004. Originally appeared in Proceedings of WADS'01 (LNCS 2125, pp.155-164, 2001).
  Studies admission control from the perspective of approximately minimizing rejections, getting a factor of 2 for a collection of natural problems. This can make more sense than the usual perspective (apx maximizing the number of acceptances) if we are not highly overloaded (e.g., if optimal can accept 99% of requests).

• Learning from Labeled and Unlabeled Data using Graph Mincuts. With Shuchi Chawla. ICML '01, pp. 19-26.
  A natural extension of nearest-neighbor algorithms, when you add in unlabeled data, leads to viewing learning as a mincut problem. This paper explores this connection and gives some empirical results.

2000

• FeatureBoost: A Meta Learning Algorithm that Improves Model Robustness. With Joseph O'Sullivan, John Langford, and Rich Caruana. ICML '00, pp. 703--710.
  How can you make learning algorithms less "lazy", so that they search for multiple "really-different" prediction rules, in case we are later faced with data in which features are corrupted or obscured?

• Noise-tolerant Learning, the Parity problem, and the Statistical Query model. With Adam Kalai and Hal Wasserman. JACM 50(4): 506-519 (2003). Extended abstract in STOC'00, pp. 435--440.
  This paper gives a slightly sub-exponential algorithm for learning parity in the presence of random noise. Scaling the problem down gives the first known example of a problem that can be learned in polynomial time from noisy data but cannot be learned in polynomial time in the Statistical Query model of Kearns.

1999

• Finely-competitive Paging. With Carl Burch and Adam Kalai. FOCS'99, pp. 450--458.
  Using ideas from online learning, we give a paging algorithm with especially good behavior under a fine-grained notion of competitive ratio. For instance, the algorithm gives near-optimal performance when the request stream can be partitioned unto a small number of working sets. Unfortunately, the algorithm itself is not computationally efficient.

• Probabilistic Planning in the Graphplan Framework. With John Langford. 5th European Conference on Planning (ECP'99). See the PGP web page.
  Approaches probabilistic planning from the Graphplan perspective. The result ends up looking at lot like a game-tree search, but using the planning graph to quickly prune states that can be guaranteed not to reach the goals in time.

• Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation. With Adam Kalai and John Langford. Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT '99), pp. 203--208.
  We show that for k>2, k-fold CV is at least slightly better than simply using a hold-out set of 1/k of the examples, in terms of the quality of the error estimate. We also analyze a "progressive validation" approach (similar to a method used by Littlestone for converting online algorithms to batch) that we show is in many ways as good as the hold-out, while using on average half as many examples for testing.

• Microchoice Bounds and Self Bounding Learning Algorithms. With John Langford. Machine Learning 51(2): 165-179 (2003). Originally appeared in Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT '99), pp. 209--214.
  Gives adaptive sample-complexity bounds for learning algorithms that work by making a sequence of small choices. These allow for a computationally-efficient version of Freund's Query-Trees.

• On-line Algorithms for Combining Language Models. With Stan Chen, Adam Kalai, and Roni Rosenfeld. In Proceedings of the International Conference on Accoustics, Speech, and Signal Processing (ICASSP '99).  [postscript] [gzipped postscript]
  Uses online portfolio-selection algorithms in the context of combining language models, with experimental comparisons.

1998

• On Learning Monotone Boolean Functions. With Carl Burch and John Langford. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS '98).
  For learning an arbitrary monotone Boolean function over the uniform distribution, we give a simple algorithm that achieves error rate at most 1/2 - Omega(1/sqrt(n)), and show that no algorithm can do better than 1/2 - omega(log(n)/sqrt(n)) from a polynomial size sample. These improve over the previous best upper and lower bounds.

• Combining Labeled and Unlabeled Data with Co-Training [pdf]. With Tom Mitchell. Proceedings of the 11th Annual Conference on Computational Learning Theory, pages 92--100, 1998. (The document linked to here is newer than the COLT version).
  Introduces and studies Co-Training, a natural approach to using unlabeled data when we have two different sources of information about each example. The idea is to train two classifiers, one using each type of information. We can then search over the unlabeled data to find examples where one classifier is confident and the other is not, and then use the label given by the confident classifier as training data for the other. In the process of analyzing this setting, we also give new results (see lemma 1) on PAC learning with noise when the positive and negative noise rates are different.

• On a Theory of Computing Symposia. With Prabhakar Raghavan. International Conference on Fun with Algorithms (FUN '98). Also appeared in SIGACT News, September 1998.
  How can you get the advantages of parallel sessions while still allowing attendees to see all the talks they wanted? The answer is to have four sessions, with each talk given twice! This paper explores a number of properties of this approach, along with connections to flows and expanders.

• Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems. With Goran Konjevod, R. Ravi, and Santosh Vempala. Theoretical Computer Science, 235(1):25--42, 2000. (Special issue in honor of Manuel Blum's 60th Birthday!) Extended abstract in Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC '98).

• A Note on Learning from Multiple-Instance Examples. With Adam Kalai. Machine Learning, 30:23--29, 1998.

1997

• Universal Portfolios With and Without Transaction Costs. With Adam Kalai. Machine Learning, 35: 193--205, 1999 (special issue for COLT '97). Originally appeared in Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 309--313, July 1997.

• On-line Learning and the Metrical Task System Problem. With Carl Burch. Machine Learning, 39: 35--58, 2000. Originally appeared in Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT '97), pages 45--53.

• A polylog(n)-competitive algorithm for metrical task systems. With Yair Bartal, Carl Burch, and Andrew Tomkins. Proceedings of the 29th Annual Symposium on the Theory of Computing (STOC '97), pages 711--719.

• An O~(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs. With David Karger. Information Processing Letters, 61(1):49--53, January 1997.

1996

• On-Line Algorithms in Machine Learning (a survey). This is a survey paper for a talk given at the Dagstuhl workshop on On-Line algorithms (June '96). Appears as Chapter 14 in "Online Algorithms: The State of the Art", LNCS # 1442, Fiat and Woeginger eds., 1998.

• A Polynomial-time Algorithm for Learning Noisy Linear Threshold Functions. With Alan Frieze, Ravi Kannan, and Santosh Vempala. Algorithmica, 22:35--52, 1998. An extended abstract appears in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96), pages 330--338.

• A Constant-factor Approximation Algorithm for the k-MST Problem. With R. Ravi and Santosh Vempala. JCSS, 58:101--108 (1999). An extended abstract appears in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC '96), pages 442--448.

• Randomized Robot Navigation Algorithms. With Piotr Berman, Amos Fiat, Howard Karloff, Adi Rosen, and Michael Saks. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 75--84, January 1996.

1995

• Fast Planning Through Planning Graph Analysis . With Merrick Furst. Artificial Intelligence 90:281--300, 1997. An extended abstract appears in Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), pages 1636--1642, August 1995. See also the Graphplan home page .

• Empirical support for Winnow and Weighted-Majority based algorithms: results on a calendar scheduling domain . Machine Learning 26:5--23, 1997. An earlier version is in Proceedings of the Twelfth International Conference on Machine Learning, pages 64--72, July 1995. Click here for more information and source code.

• Learning with Unreliable Boundary Queries . With Prasad Chalasani, Sally Goldman, and Donna Slonim. Journal of Computer and System Sciences,56(2):209-222, 1998. Originally appeared in Proceedings of the Eighth Annual Conference on Computational Learning Theory (COLT), pages 98---107, July 1995.

• New Approximation Guarantees for Minimum Weight k-Trees and Prize-Collecting Salesmen. With Baruch Awerbuch, Yossi Azar, and Santosh Vempala. SIAM J. Computing, 28(1):254--262, 1999. Originally published in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 277--283, 1995. A tech report version appears as CMU-CS-94-173, August, 1994.

• A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane. With J.S.B. Mitchell, Prasad Chalasani, and Santosh Vempala. SIAM J. Computing 28(3): 771-781 (1998). This paper combines two conference papers: J.S.B. Mitchell, "Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem", SODA '96, pp. 402--408, and Blum, Chalasani, and Vempala, "A constant-factor approximation for the k-MST problem in the plane", STOC '95, pp. 294--302.

• Coloring Random and Semi-Random k-Colorable Graphs. With Joel Spencer. Journal of Algorithms 19:204--234, 1995. This paper extends the semi-random model results in "Some Tools for Approximate 3-Coloring", Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 554-562, October 1990.

1994

• Relevant Examples and Relevant Features: Thoughts from Computational Learning Theory . This is a survey paper presented at the 1994 AAAI Fall Symposium. Here is a longer article with a broader perspective, joint with Pat Langley, that appears in Artificial Intelligence, 97:245--272, 1997.

• On learning read-k-satisfy-j DNF. With Howard Aizenstein, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, and Dan Roth. SIAM J. Computing, 27(6):1515--1530, 1998. Originally published in Proceedings of the Seventh Annual Conference on Computational Learning Theory, pages 110--117, July 1994.

• The Minimum Latency Problem. With Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 163--171, 1994.

• Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. With Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 253--262, 1994. [notes and clarifications]

1993

• Cryptographic Primitives Based on Hard Learning Problems. With Merrick Furst, Michael Kearns, and Richard Lipton. In Advances in Cryptology --- CRYPTO 93, Lecture Notes in Computer Science #773, pages 278-291, Springer-Verlag, 1994.

• Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution. With Ravi Kannan. Journal of Computer and System Sciences 54(2):371--380, 1997 (JCSS special issue for FOCS '93). Originally appeared in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 312--320, November 1993. Also published as Chapter 9 in Theoretical Advances in Neural Computation and Learning , Roychowdhury, Siu and Orlitsky, eds. Kluwer, 1994.

• An On-Line Algorithm for Improving Performance in Navigation. With Prasad Chalasani. SIAM J. Comput. 29(6): 1907-1938 (2000). Originally appeared in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 2--11, November 1993.

• On Learning Embedded Symmetric Concepts. With Prasad Chalasani and Jeffrey Jackson. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, pages 337--346, July 1993.

• Generalized Degree Sums and Hamiltonian Graphs. With Ronald Gould. ARS Combinatoria, 35:35--54, 1993.

1992

• A Decomposition Theorem and Bounds for Randomized Server Problems. With Howard Karloff, Yuval Rabani, and Michael Saks. SIAM J. Computing, 30(5): 1624--1661, 2000. Originally appeared un Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 197--207, October 1992.

• Learning Switching Concepts. With Prasad Chalasani. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 231--242, July 1992.

• Fast Learning of k-Term DNF Formulas with Queries. With Steven Rudich. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 382-389, May 1992.

• Rank-r Decision Trees are a Subclass of r-Decision Lists. Information Processing Letters, 42:183--185, 1992.

1991

• Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes. With Lisa Hellerstein and Nick Littlestone. JCSS 50(1):32--40, February 1995. An earlier version appears in Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pages 157-166, August 1991.

• Algorithms for Approximate Graph Coloring. Ph.D. thesis, MIT Laboratory for Computer Science MIT/LCS/TR-506, May 1991.

• Linear Approximation of Shortest Superstrings. With Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. JACM 41(4):630--647, 1994. An earlier version appears in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 328-336, May 1991.

• Navigating in Unfamiliar Geometric Terrain. With Prabhakar Raghavan and Baruch Schieber. Siam J. Comp 26(1):110-137, February 1997. An earlier version appears in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 494-504, May 1991.

1990

• Learning Boolean Functions in an Infinite Attribute Space. Machine Learning, 9(4):373--386, 1992. Also in Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 64-72, May 1990.

• New Approximation Algorithms for Graph Coloring. JACM 41(3):470--516, May 1994. This paper combines the worst-case approximation results in "Some Tools for Approximate 3-Coloring", FOCS 1990 (pp 554-562), and those in "An O(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithms for k-Coloring)", STOC 1989 (pp 535-542). See 1995 paper with Joel Spencer for results on Semi-Random model.

• Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain. [pdf] SIAM J. Computing, Vol 23, No. 5, 1994. Also in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 211-218, October 1990.

• Learning Functions of k Terms. With Mona Singh. In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 144-153, August 1990.

1989

• On the Computational Complexity of Training Simple Neural Networks. Master's thesis, MIT Laboratory for Computer Science, MIT/LCS/TR-445, May 1989.

• An O(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithms for k-Coloring). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 535-542, May 1989.

• Training a 3-Node Neural Network is NP-Complete. With Ron Rivest. Neural Networks, 5(1):117-127, 1992. Also in Advances in Neural Information Processing Systems 1 (proceedings of the 1988 NIPS conference), pp. 494-501, 1989.

Last updated: July 2007