Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
arXiv:1810.11507
Abstract
In this paper, we propose a Distributed Accumulated Newton Conjugate gradiEnt (DANCE) method in which sample size is gradually increasing to quickly obtain a solution whose empirical loss is under satisfactory statistical accuracy. Our proposed method is multistage in which the solution of a stage serves as a warm start for the next stage which contains more samples (including the samples in the previous stage). The proposed multistage algorithm reduces the number of passes over data to achieve the statistical accuracy of the full training set. Moreover, our algorithm in nature is easy to be distributed and shares the strong scaling property indicating that acceleration is always expected by using more computing nodes. Various iteration complexity results regarding descent direction computation, communication efficiency and stopping criteria are analyzed under convex setting. Our numerical results illustrate that the proposed method outperforms other comparable methods for solving learning problems including neural networks.
Updated numerical results
References in corpus (6)
- Adam: A Method for Stochastic Optimization
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- Global Convergence of Online Limited Memory BFGS
- Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
Cited by in corpus (6)
- Distributed Learning with Compressed Gradient Differences
- rTop-k: A Statistical Estimation Approach to Distributed SGD
- LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
- SONIA: A Symmetric Blockwise Truncated Optimization Algorithm
- Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
- Newton Method over Networks is Fast up to the Statistical Precision