We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine learning where the datasets are large and have to be stored on different machines. We design a distributed stochastic variance reduced gradient algorithm that, under certain conditions on the condition number, simultaneously achieves the optimal parallel runtime, amount of communication and rounds of communication among all distributed first-order methods up to constant factors. Our method and its accelerated extension also outperform existing distributed algorithms in terms of the rounds of communication as long as the condition number is not too large compared to the size of data in each machine. We also prove a lower bound for the number of rounds of communication for a broad class of distributed first-order methods including the proposed algorithms in this paper. We show that our accelerated distributed stochastic variance reduced gradient algorithm achieves this lower bound so that it uses the fewest rounds of communication among all distributed first-order algorithms.
We also make the connection to the recent lower bounds @cite_19 for the rounds of communication needed by distributed optimization. Arjevani and Shamir @cite_19 prove that, for a class of @math -related functions (see @cite_19 for the definition) and, for a class of algorithms, the rounds of communication achieved by DISCO is optimal. However, as mentioned above, DASVRG needs fewer rounds than DISCO. This is not a contradiction since DASVRG does not fall into the class of algorithms subject to the lower bound in @cite_19 . In particular, the algorithms concerned by @cite_19 can only use the @math local data points from the initial partition to update the local solutions while DASVRG samples and utilizes a second set of data points in each machine in addition to those @math data points.
@cite_19
1518479949
We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math .