| Title: | Algorithmic, Game Theoretic and Learning Theoretic Aspects of Distributed Optimization |
| Advisors: | Dr. Nina Balcan, School of Computer Science, Carnegie Mellon University |
| Dr. Jeff Shamma, School of Electrical and Computer Engineering | |
| Committee: | Dr. Nina Balcan, School of Computer Science, Carnegie Mellon University |
| Dr. Jeff Shamma, School of Electrical and Computer Science | |
| Dr. Greg Blekherman, School of Mathematics | |
| Dr. Lance Fortnow, School of Computer Science | |
| Dr. Yishay Mansour, Department of Combinatorics and Optimization, Hebrew University | |
| Dr. Dana Randall, School of Computer Science | |
| Reader: | Dr. Avrim Blum, School of Computer Science, Carnegie Mellon University |
Distributed systems are fundamental to today's world. Many modern problems involve multiple agents either competing or coordinating across a network, and even tasks that are not inherently distributed are often divided to accommodate today's computing resources. In this thesis we consider distributed optimization through the lens of several problems.
We first consider the fragility of distributed systems, with an investigation in game theory. The inefficiency, relative to total cooperation, of agents acting myopically in their own interest is well studied as the so called the Price of Anarchy. We assess how much further the social welfare can degrade due to repeated small disruptions. We consider two models of disruptions. In the first, agents perceive costs subject to a small adversarial perturbation; in the second a small number of Byzantine players attempt to influence the system. For both models we improve upper and lower bounds on how much social welfare can degrade for several interesting classes of games.
We next consider several problems in which agents have partial information and wish to efficiently coordinate on a solution. We measure the cost of their coordination by the amount of communication the agents must exchange. We next investigate a problem in active and semi-supervised learning. After providing a novel algorithm to learn it in the centralized case, we consider the communication cost of this algorithm when the examples are distributed amongst several agents. We then turn to the problem of clustering when the data set has been distributed among many agents. Here we devise an algorithm for coordinating on a global approximation that can be communicated efficiently by the use of coresets.
Finally we consider a problem of submodular maximization where the objective function has been distributed among agents. We adapt a centralised approximation algorithm to the distributed setting with efficient communication between the agents.
