Fast Distributed Coordinate Descent for Non-Strongly Convex Losses
We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal $O(1/k^2)$ convergence rate, where $k$ is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest supercomputer in the UK - and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Markov Chain Block Coordinate Descent
The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that successively updates a series of blocks selected according to a Mark…
Distributed OptimizationOn Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints
Mirror descent (MD) is a powerful first-order optimization technique that subsumes several optimization algorithms including gradient descent (GD). In this work, we develop a semi-definite programming (SDP) framework to …
On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
The cyclic block coordinate descent-type (CBCD-type) methods, which performs iterative updates for a few coordinates (a block) simultaneously throughout the procedure, have shown remarkable computational performance for …
regressionByzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbi…
Random extrapolation for primal-dual coordinate descent
We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. Our method updates only a subset of primal and…