Distributed Fault-Tolerant Optimization KEC 1003 ** Note the different time ** Fri, 02/12/2016 - 4:00pm
Nitin Vaidya Professor, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign Abstract: Consider a network of agents 1 to N, wherein each agent i has a local convex cost function Fi(x). For instance, the agents may be robots and each robot’s local cost function may represent its cost of moving to location x for a rendezvous with other robots. The objective here is to identify argument x that minimizes the total cost over all the agents. Similar problems arise in the context of machine learning as well where the goal is to determine the optima of a sum of many cost functions. This is a special case of convex optimization that has received significant attention over the past three decades. In particular, many distributed algorithms have been developed to determine the optima without requiring any single agent to be aware of all the cost functions. Our work addresses a fault-tolerant version of the problem, allowing for some of the agents to crash during the computation, or suffer from Byzantine failures (which can result in malicious behavior). For brevity, this talk will focus on the case when up to f agents may suffer Byzantine failures. The ideal goal then is to determine the optima of the sum of local cost functions of just the fault-free agents. It is easy to show that this problem is not solvable unless the local cost functions exhibit some form of redundancy. The talk will consider the irredundant case, and show that despite the failure of f agents, it is possible to determine the optima of a global cost function obtained as the weighted average of the cost functions of just the fault-free agents, wherein all-but-f fault-free agents are assigned non-trivial weights. The talk will provide the intuition behind our results, and discuss some algorithms. Joint work with Lili Su, a Ph.D. candidate at the University of Illinois at Urbana-Champaign. Bio: URL: http://eecs.oregonstate.edu/colloquium/distributed-fault-tolerant-optimization _______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
