2020/06/05 by Rixon Crane, Crane, Rixon, Fred Roosta +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2006.03694
openalex publication_date 2020/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a novel communication-efficient Newton-type algorithm for finite-sum optimization over a distributed computing environment. Our method, named DINO, overcomes both theoretical and practical shortcomings of similar existing methods. Under minimal assumptions, we guarantee global sub-linear convergence of DINO to a first-order stationary point for general non-convex functions and arbitrary data distribution over the network. Furthermore, for functions satisfying Polyak-Lojasiewicz (PL) inequality, we show that DINO enjoys a linear convergence rate. Our proposed algorithm is practically parameter free, in that it will converge regardless of the selected hyper-parameters, which are easy to tune. Additionally, its sub-problems are simple linear least-squares, for which efficient solvers exist. Numerical simulations demonstrate the efficiency of DINO as compared with similar alternatives.