PhD Dissertation Defense: Shuo Liu

Title: “Redundancy in Resilient Distributed Optimization and Related Problems”

In this dissertation, we study various resilient distributed optimization and related problems, focusing on the importance of redundancy in the inputs for solving the problems. We examine resilience against two types of faults: Byzantine failures where faulty agents may behave arbitrarily; and stragglers, or slow agents that can derail synchronous algorithms.

We begin with the existing work on Byzantine aggregate optimization under a server-based architecture that highlights redundancy as a necessity under certain conditions. We first consider the exact Byzantine set intersection problem in various settings and translate the results on set intersection to the Byzantine aggregate optimization problem under decentralized architecture. Under server-based architecture, we also propose and analyze the approximate Byzantine aggregate optimization problem. We further extend this problem to the approximate resilient aggregate optimization problem against both Byzantine agents and stragglers. Lastly, we propose and examine the Byzantine min-max optimization problem.

For the problems discussed, we utilize redundancy in both showing solvabilities and analyzing proposed algorithms.

Committee members:
Nitin Vaidya (adviser)
Cal Newport
Lisa Singh
Thinh Doan (Univ. of Texas)