Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Efficient and Resilient Algorithms for Asynchronous Mixed Models and Decentralized Optimization
event speaker icon
Noa Schiller (M.Sc. Thesis Seminar)
event date icon
Thursday, 16.03.2023, 10:30
event location icon
Taub 301
event speaker icon
Advisor: Prof. Hagit Attiya
We study a hybrid distributed model, which combines message-passing and shared-memory communication layers, and investigate the minimal number of failures that can partition such systems. We prove that this number precisely captures the resilience that can be achieved by algorithms that implement a variety of shared objects and solve common tasks, like approximate agreement. In the cluster-based model, processes are partitioned into disjoint clusters. We solve the approximate agreement problem in this model, and its generalization to higher dimensions, multidimensional approximate agreement. Then, we turn our attention to Stochastic Gradient Decent (SGD) algorithms. SGD is widely used for approximating the minimum of a cost function Q, a core part of optimization and learning algorithms. For a strongly convex Q, our algorithm can withstand partitions of the system, and provides convergence rate that is the maximal distributed acceleration over the optimal convergence rate of sequential SGD. For arbitrary smooth functions, the algorithm obtains the same convergence rate as sequential SGD, up to a logarithmic factor. This is achieved by using, at each iteration, a multidimensional approximate agreement algorithm. We complement this result with a lower bound showing that under system partition, some non-convex functions cannot be optimized using a distributed algorithm.