^October November – 2009 ^December

In the classical theory of social choice, a theory developed by game-theorists and theoretical economists, we consider a set of agents (voters) and a set of alternatives. Each agent ranks the alternatives, and the major aim is to find a good way to aggregate the individual preferences into a social preference. The major tool offered in this theory is the axiomatic approach: study properties (termed axioms) that characterize particular aggregation rules, and analyze whether particular desired properties can be simultaneously satisfied. In a ranking system the set of voters and the set of alternatives coincide, e.g. they are both the pages in the web; in this case the links among pages are interpreted as votes: pages that page p links to are preferable by page p to pages it does not link to; the problem of preference aggregation becomes the problem of page ranking. Trust systems are personalized ranking systems where the ranking is done for (and from the perspective of) each individual agent. Here the idea is to see how to rank agents from the perspective of a particular agent/user, based on the trust network generated by the votes. In a trust-based recommendation system the agents also express opinions about external topics, and a user who has not expressed an opinion should be recommended one based on the opinions of others and the trust network. Hence, we get a sequence of very interesting settings, extending upon classical social choice, where the axiomatic approach can be used.

On the practical side, ranking, reputation, recommendation, and trust systems have become essential ingredients of web-based multi-agent systems. These systems aggregate agents’ reviews of products and services, and of each other, into valuable information. Notable commercial examples include Amazon and E-Bay’s recommendation and reputation systems, Google’s page ranking system, and the Epinions web of trust/reputation system. Our work shows that an extremely powerful way for the study and design of such systems is the axiomatic approach, extending upon the classical theory of social choice. In this talk we discuss some representative results of our work.

Decision-making in the face of uncertainty over future outcomes is a fundamental machine learning problem, with roots in statistics and information theory, and applications to signal processing, network routing and finance. In this talk I'll describe recent algorithmic advances, both in terms of accuracy as well as computational efficiency. We describe the first efficient algorithm for the problem of online linear optimization in the limited-feedback (bandit) setting which achieves the optimal regret bound. This resolves an open question since the work of Awerbuch and Kleinberg in 2004, and is made possible via a new technique for controlling the exploration-exploitation tradeoff, inspired by convex optimization. Next we describe new online learning algorithms which attain optimal regret bounds in both worst case and stochastic scenarios. Tight performance bounds for decision making which interpolate between the worst-case and stochastic approaches were considered a fundamental open question. Based on work with Jacob Abetnethy, Satyen Kale and Alexander Rakhlin.

In numerous areas of science and engineering, we seek to extract information from linearly derived measurements in a computationally feasible manner. Linear measurement systems include medical imaging, financial prediction, seismic imaging in the oil industry, multiuser communication among cellphones, etc. Much of my discussion will focus on compressed sensing, an emerging area based on the revelation that optimization routines can reconstruct a sparse signal from a small number of linear projections of the signal - but the results are far more general. I will describe recent investigations into the ultimate performance limits that can be achieved in linear measurement systems, and describe an algorithm that achieves asymptotically optimal performance when the system is large and the measurement process can be modeled by a sparse matrix. An overview of potential future directions will be provided.