Avrim Blum

Avrim Blum


Office: 8111 Gates & Hillman Centers

Email: avrim@cs.cmu.edu

Phone: (412) 268-6452

Administrative Support Person:
Research Interests:

My main research interests are in machine learning theory, algorithmic game theory and mechanism design, approximation algorithms, and non-worst-case analysis of algorithms, as well as topics that combine several of these areas.

Machine Learning TheoryThe goals of machine learning theory are to provide a mathematical understanding of the issues involved in getting programs to learn from experience. This involves designing models that capture fundamental tradeoffs, as well as producing new analyzable algorithms. One of my current interests is in representation learning: given a collection of objects represented in one way, aiming to learn a better representation for those objects with respect to some goal or class of goals. For example, given a collection of data items represented as points in some feature space, perhaps one can identify a small subset of "landmark" items to be remembered explicitly, with the rest represented as sparse combinations of these landmarks. Or given a collection of related tasks that have been previously learned by an algorithm, perhaps one can identify commonalities among those tasks that allow new related tasks to be represented more compactly, and therefore learned more quickly. I am also interested in semi-supervised learning, distributed learning, staged curricular learning, privacy-preserving learning and data release, and connections between learning and property testing.

Algorithmic game theory and mechanism designMany large systems involve multiple entities, interacting with each other but with their own interests in mind. The area of algorithmic game theory and mechanism design has developed around understanding the behavior of systems of this type, and around designing systems for such interaction that produce desirable outcomes. My interests in this area include the design of auction and allocation mechanisms with various kinds of quality guarantees, tackling algorithmic and incentive issues in the design of kidney exchange programs, designing algorithms for security games, and developing tools for the analysis of social welfare in settings where agents are adapting their behavior in natural ways. I am also interested in machine learning problems that arise in economic and multi-agent settings, including problems of learning about agents' preferences from observing how they interact, and learning about the workings of an interaction mechanism via observations of input-output behavior. Additionally, I am interested in privacy-preserving mechanisms in multi-agent contexts, such as mechanisms for revealing approximations to the current state of some economic system that allow for agents to make better decisions while at the same time maintaining the privacy of the other agents involved.

Approximation algorithmsMany important problems turn out to be NP-hard, implying that it is unlikely there will be algorithms for them that are both efficient and optimal in the worst case. One approach in such cases is to find algorithms that produce approximately-optimal solutions in the worst case. Another approach is to identify properties of "reasonable" inputs, and aim to develop algorithms with strong performance guarantees on inputs of that type. I am interested in both of these directions, especially in the context of problems in clustering, data analysis, learning, and mechanism design.