^October November – 2009 ^December

Distributed Constraint Satisfaction and Optimization problems provide a widely accepted framework for many multi agent tasks in AI and Operation Research. In this talk I will give a very brief introduction to Distributed Constraint Satisfaction Problems (DCSPs) and Distributed Constraint Optimization Problem (DCOPs) and mention some of the research being done in our DisCSP group. I will then move on to describe my work which involves the introduction of self interested agents into a cooperative framework. While most researchers of self interested agents apply game theoretic tools and ideas when dealing with such agents, in my work I attempt to examine the implication of selfishness on the inherently cooperative DCOP framework. My work revolves around three main aspects: the problem formulation, the notion of global optimality and the quality of a solution for each participant.

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.

I will survey my lines of work in the fields of theoretic machine learning, automata learning, and statistical estimation. I will present some interesting recent results, and mention some open problems and topics I would like to look into further. The talk is intended to a relatively wide audience of CS graduate students, and not to machine learning professionals.

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.