Timezone: »

 
Poster
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
Kevin Scaman · Francis Bach · Sebastien Bubeck · Laurent Massoulié · Yin Tat Lee

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #10
in Thu Poster Session B »
In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.
Keywords: Convex Optimization · Network Analysis · Communication- or Memory-Bounded Learning
[ Paper]  [ Poster] 

Author Information

Kevin Scaman (Huawei Technologies, Noah's Ark)
Francis Bach (INRIA - Ecole Normale Superieure)
Sebastien Bubeck (Microsoft Research)
Laurent Massoulié (Inria)
Yin Tat Lee (UW)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors