Avrim Blum

AAAI Conference 2026 Conference Paper

A Theoretical Model for Grit in Pursuing Ambitious Ends

• Avrim Blum
• Emily Diana
• Kavya Ravichandran
• Alexander Williams Tolbert

Ambition and risk-taking have been heralded as important ways for marginalized communities to get out of cycles of poverty. As a result, educational messaging often encourages individuals to strengthen their personal resolve and develop characteristics such as discipline and grit to succeed in ambitious ends. However, recent work in philosophy and sociology highlights that this messaging often does more harm than good for students in these situations. We study similar questions using a different epistemic approach and in simple theoretical models -- we provide a quantitative model of decision-making between stable and risky choices in the improving multi-armed bandits framework. We use this model to first study how individuals' "strategies" are affected by their level of grittiness and how this affects their accrued rewards. Then, we study the impact of various interventions, such as increasing grit or providing a financial safety net. Our investigation of rational decision making studies the competitive ratio between the accrued reward and the optimal reward.

SODA Conference 2025 Conference Paper

Competitive strategies to use "warm start" algorithms with predictions

• Avrim Blum
• Vaidehi Srinivas

TMLR Journal 2025 Journal Article

Learning Actionable Counterfactual Explanations in Large State Spaces

• Keziah Naggita
• Matthew Walter
• Avrim Blum

Recourse generators provide actionable insights, often through feature-based counterfactual explanations (CFEs), to help negatively classified individuals understand how to adjust their input features to achieve a positive classification. These feature-based CFEs, which we refer to as \emph{low-level} CFEs, are overly specific (e.g., coding experience: \(4 \to 5+\) years) and often recommended in a feature space that doesn't straightforwardly align with real-world actions. To bridge this gap, we introduce three novel recourse types grounded in real-world actions: high-level continuous (\emph{hl-continuous}), high-level discrete (\emph{hl-discrete}), and high-level ID (\emph{hl-id}) CFEs. We formulate single-agent CFE generation methods for hl-discrete and hl-continuous CFEs. For the hl-discrete CFE, we cast the task as a weighted set cover problem that selects the least cost set of hl-discrete actions that satisfy the eligibility of features, and model the hl-continuous CFE as a solution to an integer linear program that identifies the least cost set of hl-continuous actions capable of favorably altering the prediction of a linear classifier. Since these methods require costly optimization per agent, we propose data-driven CFE generation approaches that, given instances of agents and their optimal CFEs, learn a CFE generator that quickly provides optimal CFEs for new agents. This approach, also viewed as one of learning an optimal policy in a family of large but deterministic MDPs, considers several problem formulations, including formulations in which the actions and their effects are unknown, and therefore addresses informational and computational challenges. We conduct extensive empirical evaluations using publicly available healthcare datasets (BRFSS, Foods, and NHANES) and fully-synthetic data. For negatively classified agents identified by linear and threshold-based binary classifiers, we compare the proposed forms of recourse to low-level CFEs, which suggest how the agent can transition from state \(\mathbf{x}\) to a new state \(\mathbf{x}'\) where the model prediction is desirable. We also extensively evaluate the effectiveness of our neural network-based, data-driven CFE generation approaches. Empirical results show that the proposed data-driven CFE generators are accurate and resource-efficient, and the proposed forms of recourse offer various advantages over the low-level CFEs.

NeurIPS Conference 2025 Conference Paper

On Learning Verifiers and Implications to Chain-of-Thought Reasoning

• Maria-Florina Balcan
• Avrim Blum
• Zhiyuan Li
• Dravyansh Sharma

Chain-of-Thought reasoning has emerged as a powerful approach for solving complex mathematical and logical problems. However, it can often veer off track through incorrect or unsubstantiated inferences. Formal mathematical reasoning, which can be checked with a formal verifier, is one approach to addressing this issue. However, currently LLMs are simply not good enough to solve complex problems in a formal way, and even just formalizing an informal problem statement can be challenging. Motivated by this fact, in this work we consider the problem of learning reliable verifiers for sequential reasoning, including natural language Chain-of-Thought reasoning. That is, given a problem statement and step-by-step solution in natural language, the aim of the verifier is to output [Yes] if the reasoning steps in the solution are all valid, and [No] otherwise. In this work we give a formal PAC-learning framework for studying this problem. We propose and analyze several natural verification goals, at different levels of strength, in this framework. We provide sample complexity upper-bounds for learning verifiers satisfying these goals, as well as lower-bound and impossibility results for learning other natural verification objectives without additional assumptions.

ICML Conference 2025 Conference Paper

PAC Learning with Improvements

• Idan Attias
• Avrim Blum
• Keziah Naggita
• Donya Saless
• Dravyansh Sharma
• Matthew R. Walter

One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes at least $1/\epsilon$ samples to learn to error $\epsilon$ (and more, if the classifier being learned is complex). However, suppose that data points are agents who have the ability to improve by a small amount if doing so will allow them to receive a (desired) positive classification. In that case, we may actually be able to achieve zero error by just being "close enough". For example, imagine a hiring test used to measure an agent’s skill at some job such that for some threshold $\theta$, agents who score above $\theta$ will be successful and those who score below $\theta$ will not (i. e. , learning a threshold on the line). Suppose also that by putting in effort, agents can improve their skill level by some small amount $r$. In that case, if we learn an approximation $\hat{\theta}$ of $\theta$ such that $\theta \leq \hat{\theta} \leq \theta + r$ and use it for hiring, we can actually achieve error zero, in the sense that (a) any agent classified as positive is truly qualified, and (b) any agent who truly is qualified can be classified as positive by putting in effort. Thus, the ability for agents to improve has the potential to allow for a goal one could not hope to achieve in standard models, namely zero error. In this paper, we explore this phenomenon more broadly, giving general results and examining under what conditions the ability of agents to improve can allow for a reduction in the sample complexity of learning, or alternatively, can make learning harder. We also examine both theoretically and empirically what kinds of improvement-aware algorithms can take into account agents who have the ability to improve to a limited extent when it is in their interest to do so.

NeurIPS Conference 2025 Conference Paper

Replicable Online Learning

• Saba Ahmadi
• Siddharth Bhandari
• Avrim Blum

We investigate the concept of algorithmic replicability introduced by Impagliazzo et al. (2022) in an online setting. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that, with high probability, produce the \emph{exact same sequence} of actions when run on two independently sampled input sequences generated as described above. We refer to such algorithms as adversarially replicable. Previous works explored replicability in the online setting under inputs generated independently from a fixed distribution; we term this notion as iid-replicability. Our model generalizes to capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. We demonstrate adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret. Additionally, we propose a general framework for converting an online learner into an adversarially replicable one within our setting, bounding the new regret in terms of the original algorithm’s regret. We also present a nearly optimal (in terms of regret) iid-replicable online algorithm for the experts problem, highlighting the distinction between the iid and adversarial notions of replicability. Finally, we establish lower bounds on the regret (in terms of the replicability parameter and time) that any replicable online algorithm must incur.

JMLR Journal 2023 Journal Article

An Analysis of Robustness of Non-Lipschitz Networks

• Maria-Florina Balcan
• Avrim Blum
• Dravyansh Sharma
• Hongyang Zhang

Despite significant advances, deep networks remain highly susceptible to adversarial attack. One fundamental challenge is that small input perturbations can often produce large movements in the network’s final-layer feature space. In this paper, we define an attack model that abstracts this challenge, to help understand its intrinsic properties. In our model, the adversary may move data an arbitrary distance in feature space but only in random low-dimensional subspaces. We prove such adversaries can be quite powerful: defeating any algorithm that must classify any input it is given. However, by allowing the algorithm to abstain on unusual inputs, we show such adversaries can be overcome when classes are reasonably well-separated in feature space. We further provide strong theoretical guarantees for setting algorithm parameters to optimize over accuracy-abstention trade-offs using data-driven methods. Our results provide new robustness guarantees for nearest-neighbor style algorithms, and also have application to contrastive learning, where we empirically demonstrate the ability of such algorithms to obtain high robust accuracy with low abstention rates. Our model is also motivated by strategic classification, where entities being classified aim to manipulate their observable features to produce a preferred classification, and we provide new insights into that area as well. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

NeurIPS Conference 2023 Conference Paper

Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback

• Han Shao
• Lee Cohen
• Avrim Blum
• Yishay Mansour
• Aadirupa Saha
• Matthew Walter

In this work, we propose a multi-objective decision making framework that accommodates different user preferences over objectives, where preferences are learned via policy comparisons. Our model consists of a known Markov decision process with a vector-valued reward function, with each user having an unknown preference vector that expresses the relative importance of each objective. The goal is to efficiently compute a near-optimal policy for a given user. We consider two user feedback models. We first address the case where a user is provided with two policies and returns their preferred policy as feedback. We then move to a different user feedback model, where a user is instead provided with two small weighted sets of representative trajectories and selects the preferred one. In both cases, we suggest an algorithm that finds a nearly optimal policy for the user using a number of comparison queries that scales quasilinearly in the number of objectives.

NeurIPS Conference 2023 Conference Paper

Strategic Classification under Unknown Personalized Manipulation

• Han Shao
• Avrim Blum
• Omar Montasser

We study the fundamental mistake bound and sample complexity in the strategic classification, where agents can strategically manipulate their feature vector up to an extent in order to be predicted as positive. For example, given a classifier determining college admission, student candidates may try to take easier classes to improve their GPA, retake SAT and change schools in an effort to fool the classifier. *Ball manipulations* are a widely studied class of manipulations in the literature, where agents can modify their feature vector within a bounded radius ball. Unlike most prior work, our work consider manipulations to be *personalized*, meaning that agents can have different levels of manipulation abilities (e. g. , varying radii for ball manipulations), and *unknown* to the learner. We formalize the learning problem in an interaction model where the learner first deploys a classifier and the agent manipulates the feature vector within their manipulation set to game the deployed classifier. We investigate various scenarios in terms of the information available to the learner during the interaction, such as observing the original feature vector before or after deployment, observing the manipulated feature vector, or not seeing either the original or the manipulated feature vector. We begin by providing online mistake bounds and PAC sample complexity in these scenarios for ball manipulations. We also explore non-ball manipulations and show that, even in the simplest scenario where both the original and the manipulated feature vectors are revealed, the mistake bounds and sample complexity are lower bounded by $\Omega(|\mathcal H|)$ when the target function belongs to a known class $\mathcal H$.

NeurIPS Conference 2022 Conference Paper

A Theory of PAC Learnability under Transformation Invariances

• Han Shao
• Omar Montasser
• Avrim Blum

Transformation invariances are present in many real-world problems. For example, image classification is usually invariant to rotation and color transformation: a rotated car in a different color is still identified as a car. Data augmentation, which adds the transformed data into the training set and trains a model on the augmented data, is one commonly used technique to build these invariances into the learning process. However, it is unclear how data augmentation performs theoretically and what the optimal algorithm is in presence of transformation invariances. In this paper, we study PAC learnability under transformation invariances in three settings according to different levels of realizability: (i) A hypothesis fits the augmented data; (ii) A hypothesis fits only the original data and the transformed data lying in the support of the data distribution; (iii) Agnostic case. One interesting observation is that distinguishing between the original data and the transformed data is necessary to achieve optimal accuracy in setting (ii) and (iii), which implies that any algorithm not differentiating between the original and transformed data (including data augmentation) is not optimal. Furthermore, this type of algorithms can even ``harm'' the accuracy. In setting (i), although it is unnecessary to distinguish between the two data sets, data augmentation still does not perform optimally. Due to such a difference, we propose two combinatorial measures characterizing the optimal sample complexity in setting (i) and (ii)(iii) and provide the optimal algorithms.

NeurIPS Conference 2022 Conference Paper

Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness

• Avrim Blum
• Omar Montasser
• Greg Shakhnarovich
• Hongyang Zhang

We present an oracle-efficient algorithm for boosting the adversarial robustness of barely robust learners. Barely robust learning algorithms learn predictors that are adversarially robust only on a small fraction $\beta \ll 1$ of the data distribution. Our proposed notion of barely robust learning requires robustness with respect to a ``larger'' perturbation set; which we show is necessary for strongly robust learning, and that weaker relaxations are not sufficient for strongly robust learning. Our results reveal a qualitative and quantitative equivalence between two seemingly unrelated problems: strongly robust learning and barely robust learning.

SODA Conference 2022 Conference Paper

Stochastic Vertex Cover with Few Queries

• Soheil Behnezhad
• Avrim Blum
• Mahsa Derakhshan

We study the minimum vertex cover problem in the following stochastic setting. Let G be an arbitrary given graph, p ∊ (0, 1] a parameter of the problem, and let G p be a random subgraph that includes each edge of G independently with probability p. We are unaware of the realization G p, but can learn if an edge e exists in G p by querying it. The goal is to find an approximate minimum vertex cover (MVC) of G p by querying few edges of G non-adaptively. This stochastic setting has been studied extensively for various problems such as minimum spanning trees, matroids, shortest paths, and matchings. To our knowledge, however, no non-trivial bound was known for MVC prior to our work. In this work, we present a: (2 + ∊ )-approximation for general graphs which queries edges per vertex, and a 1. 367-approximation for bipartite graphs which queries poly(1/ p ) edges per vertex. Additionally, we show that at the expense of a triple-exponential dependence on p –1 in the number of queries, the approximation ratio can be improved down to (1 + ∊ ) for bipartite graphs. Our techniques also lead to improved bounds for bipartite stochastic matching. We obtain a 0. 731-approximation with nearly-linear in 1/ p per-vertex queries. This is the first result to break the prevalent (2/3∼ 0. 66)-approximation barrier in the poly(1/ p ) query regime, improving algorithms of [Behnezhad et al. , SODA'19] and [Assadi and Bernstein, SOSA'19].

AAAI Conference 2021 Conference Paper

Communication-Aware Collaborative Learning

• Avrim Blum
• Shelby Heinecke
• Lev Reyzin

Algorithms for noiseless collaborative PAC learning have been analyzed and optimized in recent years with respect to sample complexity. In this paper, we study collaborative PAC learning with the goal of reducing communication cost at essentially no penalty to the sample complexity. We develop communication efficient collaborative PAC learning algorithms using distributed boosting. We then consider the communication cost of collaborative learning in the presence of classification noise. As an intermediate step, we show how collaborative PAC learning algorithms can be adapted to handle classification noise. With this insight, we develop communication efficient algorithms for collaborative PAC learning robust to classification noise.

NeurIPS Conference 2021 Conference Paper

Excess Capacity and Backdoor Poisoning

• Naren Manoj
• Avrim Blum

A backdoor data poisoning attack is an adversarial attack wherein the attacker injects several watermarked, mislabeled training examples into a training set. The watermark does not impact the test-time performance of the model on typical data; however, the model reliably errs on watermarked examples. To gain a better foundational understanding of backdoor data poisoning attacks, we present a formal theoretical framework within which one can discuss backdoor data poisoning attacks for classification problems. We then use this to analyze important statistical and computational issues surrounding these attacks. On the statistical front, we identify a parameter we call the memorization capacity that captures the intrinsic vulnerability of a learning problem to a backdoor attack. This allows us to argue about the robustness of several natural learning problems to backdoor attacks. Our results favoring the attacker involve presenting explicit constructions of backdoor attacks, and our robustness results show that some natural problem settings cannot yield successful backdoor attacks. From a computational standpoint, we show that under certain assumptions, adversarial training can detect the presence of backdoors in a training set. We then show that under similar assumptions, two closely related problems we call backdoor filtering and robust generalization are nearly equivalent. This implies that it is both asymptotically necessary and sufficient to design algorithms that can identify watermarked examples in the training set in order to obtain a learning algorithm that both generalizes well to unseen data and is robust to backdoors.

ICML Conference 2021 Conference Paper

One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning

• Avrim Blum
• Nika Haghtalab
• Richard Lanas Phillips
• Han Shao

In recent years, federated learning has been embraced as an approach for bringing about collaboration across large populations of learning agents. However, little is known about how collaboration protocols should take agents’ incentives into account when allocating individual resources for communal learning in order to maintain such collaborations. Inspired by game theoretic notions, this paper introduces a framework for incentive-aware learning and data sharing in federated learning. Our stable and envy-free equilibria capture notions of collaboration in the presence of agents interested in meeting their learning objectives while keeping their own sample collection burden low. For example, in an envy-free equilibrium, no agent would wish to swap their sampling burden with any other agent and in a stable equilibrium, no agent would wish to unilaterally reduce their sampling burden. In addition to formalizing this framework, our contributions include characterizing the structural properties of such equilibria, proving when they exist, and showing how they can be computed. Furthermore, we compare the sample complexity of incentive-aware collaboration with that of optimal collaboration when one ignores agents’ incentives.

TCS Journal 2020 Journal Article

Lifelong learning in costly feature spaces

• Maria-Florina Balcan
• Avrim Blum
• Vaishnavh Nagarajan

An important long-term goal in machine learning systems is to build learning agents that, like humans, can learn many tasks over their lifetime, and moreover use information from these tasks to improve their ability to do so efficiently. In this work, our goal is to provide new theoretical insights into the potential of this paradigm. In particular, we propose a lifelong learning framework that adheres to a novel notion of resource efficiency that is critical in many real-world domains where feature evaluations are costly. That is, our learner aims to reuse information from previously learned related tasks to learn future tasks in a feature-efficient manner. Furthermore, we consider novel combinatorial ways in which learning tasks can relate. Specifically, we design lifelong learning algorithms for two structurally different and widely used families of target functions: decision trees/lists and monomials/polynomials. We also provide strong feature-efficiency guarantees for these algorithms; in fact, we show that in order to learn future targets, we need only slightly more feature evaluations per training example than what is needed to predict on an arbitrary example using those targets. We also provide algorithms with guarantees in an agnostic model where not all the targets are related to each other. Finally, we also provide lower bounds on the performance of a lifelong learner in these models, which are in fact tight under some conditions.

NeurIPS Conference 2020 Conference Paper

Online Learning with Primary and Secondary Losses

• Avrim Blum
• Han Shao

We study the problem of online learning with primary and secondary losses. For example, a recruiter making decisions of which job applicants to hire might weigh false positives and false negatives equally (the primary loss) but the applicants might weigh false negatives much higher (the secondary loss). We consider the following question: Can we combine ``expert advice'' to achieve low regret with respect to the primary loss, while at the same time performing {\em not much worse than the worst expert} with respect to the secondary loss? Unfortunately, we show that this goal is unachievable without any bounded variance assumption on the secondary loss. More generally, we consider the goal of minimizing the regret with respect to the primary loss and bounding the secondary loss by a linear threshold. On the positive side, we show that running any switching-limited algorithm can achieve this goal if all experts satisfy the assumption that the secondary loss does not exceed the linear threshold by $o(T)$ for any time interval. If not all experts satisfy this assumption, our algorithms can achieve this goal given access to some external oracles which determine when to deactivate and reactivate experts.

JMLR Journal 2020 Journal Article

Random Smoothing Might be Unable to Certify $\ell_\infty$ Robustness for High-Dimensional Images

• Avrim Blum
• Travis Dick
• Naren Manoj
• Hongyang Zhang

We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the $\ell_p$ ball of radius $\epsilon$ when $p>2$. Although random smoothing has been well understood for the $\ell_2$ case using the Gaussian distribution, much remains unknown concerning the existence of a noise distribution that works for the case of $p>2$. This has been posed as an open problem by Cohen et al. (2019) and includes many significant paradigms such as the $\ell_\infty$ threat model. In this work, we show that any noise distribution $\mathcal{D}$ over $\mathbb{R}^d$ that provides $\ell_p$ robustness for all base classifiers with $p>2$ must satisfy $\mathbb{E} \eta_i^2=\Omega(d^{1-2/p}\epsilon^2(1-\delta)/\delta^2)$ for 99% of the features (pixels) of vector $\eta\sim\mathcal{D}$, where $\epsilon$ is the robust radius and $\delta$ is the score gap between the highest-scored class and the runner-up. Therefore, for high-dimensional images with pixel values bounded in $[0,255]$, the required noise will eventually dominate the useful information in the images, leading to trivial smoothed classifiers. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2020. ( edit, beta )

AAAI Conference 2018 Conference Paper

Algorithms for Generalized Topic Modeling

• Avrim Blum
• Nika Haghtalab

Recently there has been significant activity in developing algorithms with provable guarantees for topic modeling. In this work we consider a broad generalization of the traditional topic modeling framework, where we no longer assume that words are drawn i. i. d. and instead view a topic as a complex distribution over sequences of paragraphs. Since one could not hope to even represent such a distribution in general (even if paragraphs are given using some natural feature representation), we aim instead to directly learn a predictor that given a new document, accurately predicts its topic mixture, without learning the distributions explicitly. We present several natural conditions under which one can do this from unlabeled data only, and give efficient algorithms to do so, also discussing issues such as noise tolerance and sample complexity. More generally, our model can be viewed as a generalization of the multi-view or co-training setting in machine learning.

AAMAS Conference 2018 Conference Paper

Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems

• Maria-Florina Balcan
• Avrim Blum
• Shang-Tse Chen

In this work we consider online decision-making in settings where players want to guard against possible adversarial attacks or other catastrophic failures. To address this, we propose a solution concept in which players have an additional constraint that at each time step they must play a diversified mixed strategy: one that does not put too much weight on any one action. This constraint is motivated by applications such as finance, routing, and resource allocation, where one would like to limit one’s exposure to adversarial or catastrophic events while still performing well in typical cases. We explore properties of diversified strategies in both zero-sum and general-sum games, and provide algorithms for minimizing regret within the family of diversified strategies as well as methods for using taxes or fees to guide standard regret-minimizing players towards diversified strategies. We also analyze equilibria produced by diversified strategies in general-sum games. We show that surprisingly, requiring diversification can actually lead to higher-welfare equilibria, and give strong guarantees on both price of anarchy and the social welfare produced by regret-minimizing diversified agents. We additionally give algorithms for finding optimal diversified strategies in distributed settings where one must limit communication overhead.

SODA Conference 2018 Conference Paper

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

• Soheil Behnezhad
• Avrim Blum
• Mahsa Derakhshan
• MohammadTaghi Hajiaghayi
• Mohammad Mahdian
• Christos H. Papadimitriou
• Ronald L. Rivest
• Saeed Seddighin

Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a ( u, p )-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a ( u, p )-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding ( u, p )-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for ( u, p )-maxmin strategies.

NeurIPS Conference 2018 Conference Paper

On preserving non-discrimination when combining expert advice

• Avrim Blum
• Suriya Gunasekar
• Thodoris Lykouris
• Nati Srebro

We study the interplay between sequential decision making and avoiding discrimination against protected groups, when examples arrive online and do not follow distributional assumptions. We consider the most basic extension of classical online learning: Given a class of predictors that are individually non-discriminatory with respect to a particular metric, how can we combine them to perform as well as the best predictor, while preserving non-discrimination? Surprisingly we show that this task is unachievable for the prevalent notion of "equalized odds" that requires equal false negative rates and equal false positive rates across groups. On the positive side, for another notion of non-discrimination, "equalized error rates", we show that running separate instances of the classical multiplicative weights algorithm for each group achieves this guarantee. Interestingly, even for this notion, we show that algorithms with stronger performance guarantees than multiplicative weights cannot preserve non-discrimination.

NeurIPS Conference 2017 Conference Paper

Collaborative PAC Learning

• Avrim Blum
• Nika Haghtalab
• Ariel Procaccia
• Mingda Qiao

We introduce a collaborative PAC learning model, in which k players attempt to learn the same underlying concept. We ask how much more information is required to learn an accurate classifier for all players simultaneously. We refer to the ratio between the sample complexity of collaborative PAC learning and its non-collaborative (single-player) counterpart as the overhead. We design learning algorithms with O(ln(k)) and O(ln^2(k)) overhead in the personalized and centralized variants our model. This gives an exponential improvement upon the naive algorithm that does not share information among players. We complement our upper bounds with an Omega(ln(k)) overhead lower bound, showing that our results are tight up to a logarithmic factor.

SODA Conference 2017 Conference Paper

Opting Into Optimal Matchings

• Avrim Blum
• Ioannis Caragiannis
• Nika Haghtalab
• Ariel D. Procaccia
• Eviatar B. Procaccia
• Rohit Vaish

We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player—who is associated with a subset of vertices—matches as many of his own vertices when he opts into the matching mechanism as when he opts out. We offer a new perspective on this problem by considering an arbitrary graph, but assuming that vertices are associated with players at random. Our main result asserts that, under certain conditions, any fixed optimal matching is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms. We discuss the implications of our results for market design in general, and kidney exchange in particular.

AAMAS Conference 2016 Conference Paper

On the Computational Hardness of Manipulating Pairwise Voting Rules

• Rohit Vaish
• Neeldhara Misra
• Shivani Agarwal
• Avrim Blum

Standard voting rules usually assume that the preferences of voters are provided in the form of complete rankings over a fixed set of alternatives. This assumption does not hold in applications like recommendation systems where the set of alternatives is extremely large and only partial preferences can be elicited. In this paper, we study the problem of strategic manipulation of voting rules that aggregate voter preferences provided in the form of pairwise comparisons between alternatives. Our contributions are twofold: first, we show that any onto pairwise voting rule is manipulable in principle. Next, we analyze how the computational complexity of manipulation of such rules varies with the structure of the graph induced by the pairs of alternatives that the manipulator is allowed to vote over and the type of the preference relation. Building on natural connections between the pairwise manipulation and sports elimination problems (including a mixed-elimination variant that we introduce in this paper), we show that manipulating pairwise voting rules can be computationally hard even in the single-manipulator setting, a setting where most standard voting rules are known to be easy to manipulate. General Terms Algorithms, Economics, Theory

SODA Conference 2016 Conference Paper

Sparse Approximation via Generating Point Sets

• Avrim Blum
• Sariel Har-Peled
• Benjamin Adam Raichel

For a set P of n points in the unit ball b ⊆ ℝ d, consider the problem of finding a small subset T ⊆ P such that its convex-hull ∊ -approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most ∊. We present an efficient algorithm to compute such an ∊ ′-approximation of size k alg, where ∊ ′ is a function of ∊, and k alg is a function of the minimum size k opt of such an ∊ -approximation. Surprisingly, there is no dependence on the dimension d in either of the bounds. Furthermore, every point of P can be ∊ -approximated by a convex-combination of points of T that is O (1/ ∊ 2 )-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset T of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.

AAAI Conference 2015 Conference Paper

Learning Valuation Distributions from Partial Observation

• Avrim Blum
• Yishay Mansour
• Jame Morgenstern

Auction theory traditionally assumes that bidders’ valuation distributions are known to the auctioneer, such as in the celebrated, revenue-optimal Myerson auction (Myerson 1981). However, this theory does not describe how the auctioneer comes to possess this information. Recently work (Cole and Roughgarden 2014) showed that an approximation based on a finite sample of independent draws from each bidder’s distribution is sufficient to produce a near-optimal auction. In this work, we consider the problem of learning bidders’ valuation distributions from much weaker forms of observations. Specifically, we consider a setting where there is a repeated, sealed-bid auction with n bidders, but all we observe for each round is who won, but not how much they bid or paid. We can also participate (i. e. , submit a bid) ourselves, and observe when we win. From this information, our goal is to (approximately) recover the inherently recoverable part of the underlying bid distributions. We also consider extensions where different subsets of bidders participate in each round, and where bidders’ valuations have a common-value component added to their independent private values.

ICML Conference 2015 Conference Paper

The Ladder: A Reliable Leaderboard for Machine Learning Competitions

• Avrim Blum
• Moritz Hardt

The organizer of a machine learning competition faces the problem of maintaining an accurate leaderboard that faithfully represents the quality of the best submission of each competing team. What makes this estimation problem particularly challenging is its sequential and adaptive nature. As participants are allowed to repeatedly evaluate their submissions on the leaderboard, they may begin to overfit to the holdout data that supports the leaderboard. Few theoretical results give actionable advice on how to design a reliable leaderboard. Existing approaches therefore often resort to poorly understood heuristics such as limiting the bit precision of answers and the rate of re-submission. In this work, we introduce a notion of leaderboard accuracy tailored to the format of a competition. We introduce a natural algorithm called the Ladder and demonstrate that it simultaneously supports strong theoretical guarantees in a fully adaptive model of estimation, withstands practical adversarial attacks, and achieves high utility on real submission files from a Kaggle competition. Notably, we are able to sidestep a powerful recent hardness result for adaptive risk estimation that rules out algorithms such as ours under a seemingly very similar notion of accuracy. On a practical note, we provide a completely parameter-free variant of our algorithm that can be deployed in a real competition with no tuning required whatsoever.

NeurIPS Conference 2014 Conference Paper

Active Learning and Best-Response Dynamics

• Maria-Florina Balcan
• Christopher Berlind
• Avrim Blum
• Emma Cohen
• Kaushik Patnaik
• Le Song

We consider a setting in which low-power distributed sensors are each making highly noisy measurements of some unknown target function. A center wants to accurately learn this function by querying a small number of sensors, which ordinarily would be impossible due to the high noise rate. The question we address is whether local communication among sensors, together with natural best-response dynamics in an appropriately-defined game, can denoise the system without destroying the true signal and allow the center to succeed from only a small number of active queries. We prove positive (and negative) results on the denoising power of several natural dynamics, and also show experimentally that when combined with recent agnostic active learning algorithms, this process can achieve low error from very few queries, performing substantially better than active or passive learning without these denoising dynamics as well as passive learning with denoising.

UAI Conference 2014 Conference Paper

Estimating Accuracy from Unlabeled Data

• Emmanouil Antonios Platanios
• Avrim Blum
• Tom M. Mitchell

We consider the question of how unlabeled data can be used to estimate the true accuracy of learned classifiers. This is an important question for any autonomous learning system that must estimate its accuracy without supervision, and also when classifiers trained from one data distribution must be applied to a new distribution (e. g. , document classifiers trained on one text corpus are to be applied to a second corpus). We first show how to estimate error rates exactly from unlabeled data when given a collection of competing classifiers that make independent errors, based on the agreement rates between subsets of these classifiers. We further show that even when the competing classifiers do not make independent errors, both their accuracies and error dependencies can be estimated by making certain relaxed assumptions. Experiments on two data real-world data sets produce estimates within a few percent of the true accuracy, using solely unlabeled data. These results are of practical significance in situations where labeled data is scarce and shed light on the more general question of how the consistency among multiple functions is related to their true accuracies.

AAAI Conference 2014 Conference Paper

Lazy Defenders Are Almost Optimal against Diligent Attackers

• Avrim Blum
• Nika Haghtalab
• Ariel Procaccia

Most work building on the Stackelberg security games model assumes that the attacker can perfectly observe the defender’s randomized assignment of resources to targets. This assumption has been challenged by recent papers, which designed tailor-made algorithms that compute optimal defender strategies for security games with limited surveillance. We analytically demonstrate that in zero-sum security games, lazy defenders, who simply keep optimizing against perfectly informed attackers, are almost optimal against diligent attackers, who go to the effort of gathering a reasonable number of observations. This result implies that, in some realistic situations, limited surveillance may not need to be explicitly addressed.

NeurIPS Conference 2014 Conference Paper

Learning Mixtures of Ranking Models

• Pranjal Awasthi
• Avrim Blum
• Or Sheffet
• Aravindan Vijayaraghavan

This work concerns learning probabilistic models for ranking data in a heterogeneous population. The specific problem we study is learning the parameters of a {\em Mallows Mixture Model}. Despite being widely studied, current heuristics for this problem do not have theoretical guarantees and can get stuck in bad local optima. We present the first polynomial time algorithm which provably learns the parameters of a mixture of two Mallows models. A key component of our algorithm is a novel use of tensor decomposition techniques to learn the top-$k$ prefix in both the rankings. Before this work, even the question of {\em identifiability} in the case of a mixture of two Mallows models was unresolved.

NeurIPS Conference 2014 Conference Paper

Learning Optimal Commitment to Overcome Insecurity

• Avrim Blum
• Nika Haghtalab
• Ariel Procaccia

Game-theoretic algorithms for physical security have made an impressive real-world impact. These algorithms compute an optimal strategy for the defender to commit to in a Stackelberg game, where the attacker observes the defender's strategy and best-responds. In order to build the game model, though, the payoffs of potential attackers for various outcomes must be estimated; inaccurate estimates can lead to significant inefficiencies. We design an algorithm that optimizes the defender's strategy with no prior information, by observing the attacker's responses to randomized deployments of resources and learning his priorities. In contrast to previous work, our algorithm requires a number of queries that is polynomial in the representation of the game.

ICML Conference 2013 Conference Paper

Exploiting Ontology Structures and Unlabeled Data for Learning

• Maria-Florina Balcan
• Avrim Blum
• Yishay Mansour

We present and analyze a theoretical model designed to understand and explain the effectiveness of ontologies for learning multiple related tasks from primarily unlabeled data. We present both information-theoretic results as well as efficient algorithms. We show in this model that an ontology, which specifies the relationships between multiple outputs, in some cases is sufficient to completely learn a classification using a large unlabeled data source.

FOCS Conference 2012 Conference Paper

Active Property Testing

• Maria-Florina Balcan
• Eric Blais
• Avrim Blum
• Liu Yang 0001

One motivation for property testing of boolean functions is the idea that testing can provide a fast preprocessing step before learning. However, in most machine learning applications, it is not possible to request for labels of arbitrary examples constructed by an algorithm. Instead, the dominant query paradigm in applied machine learning, called active learning, is one where the algorithm may query for labels, but only on points in a given (polynomial-sized) unlabeled sample, drawn from some underlying distribution D. In this work, we bring this well-studied model to the domain of testing. We develop both general results for this active testing model as well as efficient testing algorithms for several important properties for learning, demonstrating that testing can still yield substantial benefits in this restricted setting. For example, we show that testing unions of d intervals can be done with O(1) label requests in our setting, whereas it is known to √ require Ω(d) labeled examples for learning (and Ω(√d) for passive testing [22] where the algorithm must pay for every example drawn from D). In fact, our results for testing unions of intervals also yield improvements on prior work in both the classic query model (where any point in the domain can be queried) and the passive testing model as well. For the problem of testing linear separators in Rn over the Gaussian distribution, we show that both active and passive testing can be done with O(√n) queries, substantially less than the Ω(n) needed for learning, with near-matching lower bounds. We also present a general combination result in this model for building testable properties out of others, which we then use to provide testers for a number of assumptions used in semi-supervised learning. In addition to the above results, we also develop a general notion of the testing dimension of a given property with respect to a given distribution, that we show characterizes (up to constant factors) the intrinsic number of label requests needed to test that property. We develop such notions for both the active and passive testing models. We then use these dimensions to prove a number of lower bounds, including for linear separators and the class of dictator functions.

FOCS Conference 2012 Conference Paper

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

• Jeremiah Blocki
• Avrim Blum
• Anupam Datta
• Or Sheffet

This paper proves that an "old dog", namely - the classical Johnson-Lindenstrauss transform, "performs new tricks" - it gives a novel way of preserving differential privacy. We show that if we take two databases, D and D', such that (i) D'-D is a rank-1 matrix of bounded norm and (ii) all singular values of D and D' are sufficiently large, then multiplying either D or D' with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and public alteration of the input is enough to assert that all singular values of D are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a (S, S)-cut in a graph. We show that the JL transform allows us to publish a sanitized graph that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only O(|S|ϵ) random noise to any given query (w. h. p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts (|S| = o(n)). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to publish a sanitized covariance matrix that preserves differential privacy w. r. t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w. h. p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions.

FOCS Conference 2011 Conference Paper

Welfare and Profit Maximization with Production Costs

• Avrim Blum
• Anupam Gupta 0001
• Yishay Mansour
• Ankit Sharma 0001

Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e. g. , social welfare, revenue, or profit). The problem has been well-studied in the case of limited supply (one copy of each item), and in the case of digital goods (the seller can produce additional copies at no cost). Yet in the case of resources -- oil, labor, computing cycles, etc. -- neither of these abstractions is just right: additional supplies of these resources can be found, but at increasing difficulty (marginal cost) as resources are depleted. In this work, we initiate the study of the algorithmic mechanism design problem of combinatorial pricing under increasing marginal cost. The goal is to sell these goods to buyers with unknown and arbitrary combinatorial valuation functions to maximize either the social welfare, or the seller's profit, specifically we focus on the setting of posted item prices with buyers arriving online. We give algorithms that achieve constant factor approximations for a class of natural cost functions - linear, low-degree polynomial, logarithmic - and that give logarithmic approximations for more general increasing marginal cost functions (along with a necessary additive loss). We show that these bounds are essentially best possible for these settings.

FOCS Conference 2010 Conference Paper

Stability Yields a PTAS for k-Median and k-Means Clustering

• Pranjal Awasthi
• Avrim Blum
• Or Sheffet

We consider fc-median clustering in finite metric spaces and fc-means clustering in Euclidean spaces, in the setting where k is part of the input (not a constant). For the fc-means problem, Ostrovsky et al. show that if the optimal (k - 1)-means clustering of the input is more expensive than the optimal fc-means clustering by a factor of 1/∈2, then one can achieve a (1 + f(∈))-approximation to the fc-means optimal in time polynomial in n and k by using a variant of Lloyd's algorithm. In this work we substantially improve this approximation guarantee. We show that given only the condition that the (k - 1)-means optimal is more expensive than the fc-means optimal by a factor 1 + α for some constant α > 0, we can obtain a PTAS. In particular, under this assumption, for any ∈ > 0 we achieve a (1 + ∈)-approximation to the fc-means optimal in time polynomial in n and k, and exponential in 1/e and 1/α. We thus decouple the strength of the assumption from the quality of the approximation ratio. We also give a PTAS for the fc-median problem in finite metrics under the analogous assumption as well. For fc-means, we in addition give a randomized algorithm with improved running time of n o(1) (k log n) poly(1/∈, 1/α) Our technique also obtains a PTAS under the assumption of Balcan et al. that all (1 + α) approximations are δ-close to a desired target clustering, in the case that all target clusters have size greater than δn and α > 0 is constant. Note that the motivation of Balcan et al. is that for many clustering problems, the objective function is only a proxy for the true goal of getting close to the target. From this perspective, our improvement is that for fc-means in Euclidean spaces we reduce the distance of the clustering found to the target from O(δ) to δ when all target clusters are large, and for fc-median we improve the "largeness" condition needed in to get exactly δ-close from O(δn) to δn. Our results are based on a new notion of clustering stability.

NeurIPS Conference 2010 Conference Paper

Trading off Mistakes and Don't-Know Predictions

• Amin Sayedi
• Morteza Zadimoghaddam
• Avrim Blum

We discuss an online learning framework in which the agent is allowed to say I don't know'' as well as making incorrect predictions on given examples. We analyze the trade off between saying I don't know'' and making mistakes. If the number of don't know predictions is forced to be zero, the model reduces to the well-known mistake-bound model introduced by Littlestone [Lit88]. On the other hand, if no mistakes are allowed, the model reduces to KWIK framework introduced by Li et. al. [LLW08]. We propose a general, though inefficient, algorithm for general finite concept classes that minimizes the number of don't-know predictions if a certain number of mistakes are allowed. We then present specific polynomial-time algorithms for the concept classes of monotone disjunctions and linear separators.

SODA Conference 2009 Conference Paper

Approximate clustering without the approximation

• Maria-Florina Balcan
• Avrim Blum
• Anupam Gupta 0001

Approximation algorithms for clustering points in metric spaces is a flourishing area of research, with much research effort spent on getting a better understanding of the approximation guarantees possible for many objective functions such as k -median, k -means, and min-sum clustering. This quest for better approximation algorithms is further fueled by the implicit hope that these better approximations also yield more accurate clusterings. E. g. , for many problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct “target” clustering and the implicit hope is that approximately optimizing these objective functions will in fact produce a clustering that is close pointwise to the truth. 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 Φ is ∊ -close to the target—then we can produce clusterings that are O ( ∊ )-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 the min-sum objective we can do this for any constant c > 2. Our results also highlight a surprising conceptual difference between assuming that the optimal solution to, say, the k -median objective is ∊ -close to the target, and assuming that any approximately optimal solution is ∊ -close to the target, even for approximation factor say c = 1. 01. In the former case, the problem of finding a solution that is O ( ∊ )-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.

SODA Conference 2009 Conference Paper

Improved equilibria via public service advertising

• Maria-Florina Balcan
• Avrim Blum
• Yishay Mansour

NeurIPS Conference 2009 Conference Paper

Tracking Dynamic Sources of Malicious Activity at Internet Scale

• Shobha Venkataraman
• Avrim Blum
• Dawn Song
• Subhabrata Sen
• Oliver Spatscheck

We formulate and address the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision 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 putting together a number of different ``experts algorithms and online paging algorithms. We prove guarantees on our algorithms 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, with significant improvements over existing approaches.

STOC Conference 2008 Conference Paper

A discriminative framework for clustering via similarity functions

• Maria-Florina Balcan
• Avrim Blum
• Santosh S. Vempala

Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments 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 ground truth is really the unknown correct clustering of the data points and the real goal is to achieve low error on the data. In this work, we develop a theoretical approach to clustering from this perspective. In particular, motivated by recent 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?"

STOC Conference 2008 Conference Paper

A learning theory approach to non-interactive database privacy

• Avrim Blum
• Katrina Ligett
• Aaron Roth 0001

We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. 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 the prevailing privacy notion, differential privacy.

STOC Conference 2008 Conference Paper

Regret minimization and the price of total anarchy

• Avrim Blum
• MohammadTaghi Hajiaghayi
• Katrina Ligett
• Aaron Roth 0001

We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be computationally hard to find), 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. In contrast to the price of anarchy and the recently introduced price of sinking, which require all players to behave in a prescribed manner, we show that the price of total anarchy is in many cases resilient to the presence of Byzantine players, about whom we make no assumptions. Finally, because the price of total anarchy is an upper bound on the price of anarchy even in mixed strategies, for some games our results yield as corollaries previously unknown bounds on the price of anarchy in mixed strategies.

JMLR Journal 2007 Journal Article

From External to Internal Regret

• Avrim Blum
• Yishay Mansour

External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an online algorithm to the loss of a modified online algorithm, which consistently replaces one action by another. In this paper we give a simple generic reduction that, given an algorithm for the external regret problem, converts it to an efficient online algorithm for the internal regret problem. We provide methods that work both in the full information model, in which the loss of every action is observed at each time step, and the partial information (bandit) model, where at each time step only the loss of the selected action is observed. The importance of internal regret in game theory is due to the fact that in a general game, if each player has sublinear internal regret, then the empirical frequencies converge to a correlated equilibrium. For external regret we also derive a quantitative regret bound for a very general setting of regret, which includes an arbitrary set of modification rules (that possibly modify the online algorithm) and an arbitrary set of time selection functions (each giving different weight to each time step). The regret for a given time selection and modification rule is the difference between the cost of the online algorithm and the cost of the modified online algorithm, where the costs are weighted by the time selection function. This can be viewed as a generalization of the previously-studied sleeping experts setting. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

ICML Conference 2006 Conference Paper

On a theory of learning with similarity functions

• Maria-Florina Balcan
• Avrim Blum

FOCS Conference 2005 Conference Paper

Mechanism Design via Machine Learning

• Maria-Florina Balcan
• Avrim Blum
• Jason D. Hartline
• Yishay Mansour

We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or /spl beta/-approximation) algorithm for the standard algorithmic problem, we can convert it into a (1 + /spl epsi/)-approximation (or /spl beta/(1 +/spl epsi/)-approximation) for the incentive-compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the comparison class of solutions. We apply these results to the problem of auctioning a digital good, the attribute auction problem, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a learning perspective, these settings present several challenges: in particular the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large.

SODA Conference 2005 Conference Paper

Near-optimal online auctions

• Avrim Blum
• Jason D. Hartline

STOC Conference 2004 Conference Paper

Approximation algorithms for deadline-TSP and vehicle routing with time-windows

• Nikhil Bansal 0001
• Avrim Blum
• Shuchi Chawla 0001
• Adam Meyerson

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v , we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [ R(v) , D(v) ]. No good approximations were known previously for these problems on general metric spaces. We give an O (log n ) approximation algorithm for Deadline-TSP, and extend this algorithm to an O (log 2 n ) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].

NeurIPS Conference 2004 Conference Paper

Co-Training and Expansion: Towards Bridging Theory and Practice

• Maria-Florina Balcan
• Avrim Blum
• Ke Yang

Ke Yang Computer Science Dept. Carnegie Mellon Univ. Pittsburgh, PA 15213

TCS Journal 2004 Journal Article

Online learning in online auctions

• Avrim Blum
• Vijay Kumar
• Atri Rudra
• Felix Wu

We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this paper, we demonstrate that results from online learning can be usefully applied in this context, and we derive a new auction for digital goods that achieves a constant competitive ratio with respect to the optimal (offline) fixed price revenue. This substantially improves upon the best previously known competitive ratio for this problem of O(exp( loglog h )). We also apply our techniques to the related problem of designing online posted price mechanisms, in which the seller declares a price for each of a series of buyers, and each buyer either accepts or rejects the good at that price. Despite the relative lack of information in this setting, we show that online learning techniques can be used to obtain results for online posted price mechanisms which are similar to those obtained for online auctions.

JMLR Journal 2004 Journal Article

Preference Elicitation and Query Learning (Special Topic on Learning Theory)

• Avrim Blum
• Jeffrey Jackson
• Tuomas Sandholm
• Martin Zinkevich

In this paper we explore the relationship between "preference elicitation", a learning-style problem that arises in combinatorial auctions, and the problem of learning via queries studied in computational learning theory. Preference elicitation is the process of asking questions about the preferences of bidders so as to best divide some set of goods. As a learning problem, it can be thought of as a setting in which there are multiple target concepts that can each be queried separately, but where the goal is not so much to learn each concept as it is to produce an "optimal example". In this work, we prove a number of similarities and differences between two-bidder preference elicitation and query learning, giving both separation results and proving some connections between these problems. [abs] [ pdf ][ ps.gz ][ ps ]

ICML Conference 2004 Conference Paper

Semi-supervised learning using randomized mincuts

• Avrim Blum
• John D. Lafferty
• Mugizi Robert Rwebangira
• Rajashekar Reddy

FOCS Conference 2003 Conference Paper

Approximation Algorithms for Orienteering and Discounted-Reward TSP

• Avrim Blum
• Shuchi Chawla 0001
• David R. Karger
• Terran Lane
• Adam Meyerson
• Maria Minkoff

In this paper, we give the first constant-factor approximation algorithm for the rooted orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the orienteering problem, the goal 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 /spl gamma/, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by /spl gamma//sup t/. This is similar to the objective considered in Markov decision processes (MDPs) except we only receive a reward the first time a node is visited. We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem based on B. Awerbuch et al. (1999) and E. M. Arkin (1998).

FOCS Conference 2003 Conference Paper

Machine Learning: My Favorite Results, Directions, and Open Problems

• Avrim Blum

SODA Conference 2003 Conference Paper

Online learning in online auctions

• Avrim Blum
• Vijay Kumar
• Atri Rudra
• Felix Wu

ICML Conference 2003 Conference Paper

Planning in the Presence of Cost Functions Controlled by an Adversary

• H. Brendan McMahan
• Geoffrey J. Gordon
• Avrim Blum

FOCS Conference 2002 Conference Paper

Correlation Clustering

• Nikhil Bansal 0001
• Avrim Blum
• Shuchi Chawla 0001

We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u, /spl upsi/) is labeled either + or - depending on whether a and /spl upsi/ have been deemed to be similar or different. The goal is to produce a partition of the vertices (a clustering) that agrees as much as possible with the edge labels. That is, we want a clustering that maximizes the number of + edges within clusters, plus the number of - edges between clusters (equivalently, minimizes the number of disagreements: the number of - edges inside clusters plus the number of + edges between clusters). This formulation is motivated from a document clustering problem in which one has a pairwise similarity function f learned from past data, and the goal is to partition the current set of documents in a way that correlates with f as much as possible; it can also be viewed as a kind of "agnostic learning" problem. 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. 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.

SODA Conference 2002 Conference Paper

Online algorithms for market clearing

• Avrim Blum
• Tuomas Sandholm
• Martin Zinkevich

SODA Conference 2002 Conference Paper

Smoothed analysis of the perceptron algorithm for linear programming

• Avrim Blum
• John Dunagan

SODA Conference 2002 Conference Paper

Static optimality and dynamic search-optimality in lists and trees

• Avrim Blum
• Shuchi Chawla 0001
• Adam Tauman Kalai

ICML Conference 2001 Conference Paper

Learning from Labeled and Unlabeled Data using Graph Mincuts

• Avrim Blum
• Shuchi Chawla 0001

ICML Conference 2000 Conference Paper

FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness

• Joseph O'Sullivan
• John Langford 0001
• Rich Caruana
• Avrim Blum

STOC Conference 2000 Conference Paper

Noise-tolerant learning, the parity problem, and the statistical query model

• Avrim Blum
• Adam Tauman Kalai
• Hal Wasserman

TCS Journal 2000 Journal Article

Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

• Avrim Blum
• Goran Konjevod
• R. Ravi
• Santosh Vempala

We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural way (via random projection) to obtain approximation guarantees for both of these vertex-ordering problems.

FOCS Conference 1999 Conference Paper

Finely-Competitive Paging

• Avrim Blum
• Carl Burch
• Adam Tauman Kalai

We construct an online algorithm for paging that achieves an O(r+log k) competitive ratio when compared to an offline strategy that is allowed the additional ability to "rent" pages at a cost of 1/r. In contrast, the competitive ratio of the Marking algorithm for this scenario is O(r log k). Our algorithm can be thought of in the standard setting as having a "fine-grained" competitive ratio, achieving an O(1) ratio when the request sequence consists of a small number of working sets, gracefully decaying to O(log k) as this number increases. Our result is a generalization of the result by Y. Bartal et al. (1997) that one can achieve an O(r+log n) ratio for the unfair n-state uniform-space Metrical Task System problem. That result was a key component of the polylog(n) competitive randomized algorithm given in that paper for the general Metrical Task System problem. One motivation of this work is that it may be a first step toward achieving a polylog(k) randomized competitive ratio for the much more difficult k-server problem.

FOCS Conference 1998 Conference Paper

On Learning Monotone Boolean Functions

• Avrim Blum
• Carl Burch
• John Langford 0001

We consider the problem of learning monotone Boolean functions over {0, 1}/sup n/ under the uniform distribution. Specifically, given a polynomial number of uniform random samples for an unknown monotone Boolean function f, and given polynomial completing time, we would like to approximate f as well as possible. We describe a simple algorithm that we prove achieves error at most 1/2-/spl Omega/(1//spl radic/n), improving on the previous best bound of 1/2-/spl Omega/((log/sup 2/ n)/n). We also prove that no algorithm, given a polynomial number of samples, can guarantee error 1/2-/spl omega/((log n)//spl radic/n), improving on the previous best hardness bound of O(1//spl radic/n). These lower bounds hold even if the learning algorithm is allowed membership queries. Thus this paper settles to an O(log n) factor the question of the best achievable error for learning the class of monotone Boolean functions with respect to the uniform distribution.

STOC Conference 1998 Conference Paper

Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems

• Avrim Blum
• Goran Konjevod
• R. Ravi 0001
• Santosh S. Vempala

STOC Conference 1997 Conference Paper

A polylog( n )-Competitive Algorithm for Metrical Task Systems

• Yair Bartal
• Avrim Blum
• Carl Burch
• Andrew Tomkins

STOC Conference 1996 Conference Paper

A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract)

• Avrim Blum
• R. Ravi 0001
• Santosh S. Vempala

FOCS Conference 1996 Conference Paper

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions

• Avrim Blum
• Alan M. Frieze
• Ravindran Kannan
• Santosh S. Vempala

The authors consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear program and solved in polynomial time with the ellipsoid algorithm (or interior point methods). On the other hand, simple greedy algorithms such as the perceptron algorithm seem to work well in practice and can be made noise tolerant; but, their running time depends on a separation parameter (which quantifies the amount of "wiggle room" available) and can be exponential in the description length of the input. They show how simple greedy methods can be used to find weak hypotheses (hypotheses that classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. This results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. The algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in R/sup n/, each given to b bits of precision, they show that one can remove only a small fraction of S so that in the remaining set T, for every vector v, max/sub x/spl epsiv/T/(v/spl middot/x)/sup 2//spl les/poly(n, b)|T|/sup -1//spl Sigma//sub x/spl epsiv/T/(v/spl middot/x)/sup 2/. After removing these outliers, they are able to show that a modified version of the perceptron learning algorithm works in polynomial time, even in the presence of random classification noise.

SODA Conference 1996 Conference Paper

Randomized Robot Navigation Algorithms

• Piotr Berman
• Avrim Blum
• Amos Fiat
• Howard J. Karloff
• Adi Rosén
• Michael E. Saks

STOC Conference 1995 Conference Paper

A constant-factor approximation for the k -MST problem in the plane

• Avrim Blum
• Prasad Chalasani
• Santosh S. Vempala

ICML Conference 1995 Conference Paper

Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain

• Avrim Blum

STOC Conference 1995 Conference Paper

Improved approximation guarantees for minimum-weight k -trees and prize-collecting salesmen

• Baruch Awerbuch
• Yossi Azar
• Avrim Blum
• Santosh S. Vempala

STOC Conference 1994 Conference Paper

The minimum latency problem

• Avrim Blum
• Prasad Chalasani
• Don Coppersmith
• William R. Pulleyblank
• Prabhakar Raghavan
• Madhu Sudan 0001

STOC Conference 1994 Conference Paper

Weakly learning DNF and characterizing statistical query learning using Fourier analysis

• Avrim Blum
• Merrick L. Furst
• Jeffrey C. Jackson
• Michael J. Kearns
• Yishay Mansour
• Steven Rudich

FOCS Conference 1993 Conference Paper

An On-Line Algorithm for Improving Performance in Navigation

• Avrim Blum
• Prasad Chalasani

Recent papers have shown optimally-competitive on-line strategies for a robot traveling from a point s to a point t in certain unknown geometric environments. We consider the question: Having gained some partial information about the scene on its first trip from s to t, can the robot improve its performance on subsequent trips it might make? This is a type of on-line problem where a strategy must exploit partial information about the future (e. g. , about obstacles that lie ahead). For scenes with axis-parallel rectangular obstacles where the Euclidean distance between s and t is n, we present a deterministic algorithm whose average trip length after t trips, k/spl les/n, is O(/spl radic/n/k) times the length of the shortest s-t path in the scene. We also show that this is the best a deterministic strategy can do. This algorithm can be thought of as performing an optimal tradeoff between search effort and the goodness of the path found. We improve this algorithm so that for every i/spl les/n, the robot's ith trip length is O(/spl radic/n/t) times the shortest s-t path length. A key idea of the paper is that a tree structure can be defined in the scene, where the nodes are portions of certain obstacles and the edges are "short" paths from a node to its children. The core of our algorithms is an on-line strategy for traversing this tree optimally. >

FOCS Conference 1993 Conference Paper

Learning an Intersection of k Halfspaces over a Uniform Distribution

• Avrim Blum
• Ravindran Kannan

We present a polynomial-time algorithm to learn an intersection of a constant number of halfspaces in n dimensions, over the uniform distribution on an n-dimensional ball. The algorithm we present in fact can learn an intersection of an arbitrary (polynomial) number of halfspaces over this distribution, if the subspace spanned by the normal vectors to the bounding hyperplanes has constant dimension. This generalizes previous results for this distribution, in particular a result of E. B. Baum (1990) who showed how to learn an intersection of 2 halfspaces defined by hyperplanes that pass through the origin (his results in fact held for a variety of symmetric distributions). Our algorithm uses estimates of second moments to find vectors in a low-dimensional "relevant subspace". We believe that the algorithmic techniques studied here may be useful in other geometric learning applications. >

FOCS Conference 1992 Conference Paper

A Decomposition Theorem and Bounds for Randomized Server Problems

• Avrim Blum
• Howard J. Karloff
• Yuval Rabani
• Michael E. Saks

The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems. >

STOC Conference 1992 Conference Paper

Fast Learning of k-Term DNF Formulas with Queries

• Avrim Blum
• Steven Rudich

STOC Conference 1991 Conference Paper

Linear Approximation of Shortest Superstrings

• Avrim Blum
• Tao Jiang 0001
• Ming Li 0001
• John Tromp
• Mihalis Yannakakis

STOC Conference 1991 Conference Paper

Navigating in Unfamiliar Geometric Terrain (Preliminary Version)

• Avrim Blum
• Prabhakar Raghavan
• Baruch Schieber

STOC Conference 1990 Conference Paper

Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract)

• Avrim Blum

FOCS Conference 1990 Conference Paper

Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain

• Avrim Blum

Two of the most commonly used models in computational learning theory are the distribution-free model, in which examples are chosen from a fixed but arbitrary distribution, and the absolute mistake-bound model, in which examples are presented in order by an adversary. Over the Boolean domain

FOCS Conference 1990 Conference Paper

Some Tools for Approximate 3-Coloring (Extended Abstract)

• Avrim Blum

Several tools for use in approximation algorithms to color 3-chromatic graphs are presented. The techniques are used in an algorithm that colors any 3-chromatic graph with O(n/sup 3/8/)+O(n/sup 3/8+O(1)/) colors (or more precisely) O(n/sup 3/8/log/sup 5/8/ n) colors, which improves the previous best bound of O(n/sup 0. 4+0(1)/) colors. The techniques are illustrated by considering a problem in which the 3-chromatic graph is created not by a worst-case adversary, but by an adversary each of whose decisions (whether or not to include an edge) is reversed with some small probability or noise rate p. This type of adversary is equivalent to the semirandom source of M. Santha and U. V. Vazirani (1986). An algorithm that will actually 3-color such a graph with high probability even for quite low noise rates (p>or=n/sup -1/2+ epsilon / for constant epsilon >0), is presented. >

STOC Conference 1989 Conference Paper

An \tildeO(n^0. 4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)

• Avrim Blum

NeurIPS Conference 1988 Conference Paper

Training a 3-Node Neural Network is NP-Complete

• Avrim Blum
• Ronald Rivest

We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and thresholds for the three nodes of this network so that it will produce output con(cid: 173) sistent with a given set of training examples. We extend the result to other simple networks. This result suggests that those looking for perfect training algorithms cannot escape inherent computational difficulties just by considering only simple or very regular networks. It also suggests the importance, given a training problem, of finding an appropriate network and input encoding for that problem. It is left as an open problem to extend our result to nodes with non-linear functions such as sigmoids.