Distributed Coordinate Descent Method for Learning with Big Data

Abstract

In this paper we develop and analyze Hydra: HYbriD cooRdinAte descent method for solving loss minimization problems with big data. We initially partition the coordinates (features) and assign each partition to a different node of a cluster. At every iteration, each node picks a random subset of the coordinates from those it owns, independently from the other computers, and in parallel computes and applies updates to the selected coordinates based on a simple closed-form formula. We give bounds on the number of iterations sufficient to approximately solve the problem with high probability, and show how it depends on the data and on the partitioning. We perform numerical experiments with a LASSO instance described by a 3TB matrix.

11 two-column pages, 1 algorithm, 4 figures, 4 tables

References in corpus (5)

• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Inexact Coordinate Descent: Complexity and Preconditioning
• Parallel coordinate descent for the Adaboost problem

Cited by in corpus (71)

• On the Convergence of FedAvg on Non-IID Data
• A Survey on Distributed Machine Learning
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Federated Optimization in Heterogeneous Networks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• A Field Guide to Federated Optimization
• Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks
• Communication Complexity of Distributed Convex Learning and Optimization
• Scaling Distributed Machine Learning with In-Network Aggregation
• Distributed Learning with Compressed Gradient Differences
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• FedSplit: An algorithmic framework for fast federated optimization
• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
• Federated Learning for Healthcare Informatics
• Natural Compression for Distributed Deep Learning
• Parallel Coordinate Descent Methods for Big Data Optimization
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• A Communication Efficient Collaborative Learning Framework for Distributed Features
• Stochastic Dual Ascent for Solving Linear Systems
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Accelerated, Parallel and Proximal Coordinate Descent
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Distributed Mini-Batch SDCA
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Decentralized Deep Learning with Arbitrary Communication Compression
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Importance Sampling for Minibatches
• Cross-Silo Federated Learning for Multi-Tier Networks with Vertical and Horizontal Data Partitioning
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• LOCO: Distributing Ridge Regression with Random Projections
• A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
• Large Scale Kernel Learning using Block Coordinate Descent
• Block-proximal methods with spatially adapted acceleration
• Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters
• Matrix Completion under Interval Uncertainty
• LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• Federated Learning for Commercial Image Sources
• Adaptive Sketch-and-Project Methods for Solving Linear Systems
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds
• Primal-dual block-proximal splitting for a class of non-convex problems
• Decentralized Markov Chain Gradient Descent
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
• Cooperative Coevolution for Non-Separable Large-Scale Black-Box Optimization: Convergence Analyses and Distributed Accelerations
• ParMAC: distributed optimisation of nested functions, with application to learning binary autoencoders
• Learning over inherently distributed data
• Random block coordinate descent methods for linearly constrained optimization over networks
• Parallel Stochastic Newton Method
• On Randomized Distributed Coordinate Descent with Quantized Updates
• Assisted Learning for Organizations with Limited Imbalanced Data
• Privacy-Preserving Generalized Linear Models using Distributed Block Coordinate Descent
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• A Survey on Large-scale Machine Learning
• Parallel Coordinate Descent Newton Method for Efficient ${\ell }_1$-Regularized Minimization
• Distributed Multi-Task Relationship Learning
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization
• Manifold Optimization Methods for Hybrid beamforming in mmWave Dual-Function Radar-Communication System
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• A Simple and Fast Coordinate-Descent Augmented-Lagrangian Solver for Model Predictive Control
• Random Function Iterations for Stochastic Fixed Point Problems
• $D{C}^2$: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering
• A generic coordinate descent solver for nonsmooth convex optimization
• Distributed Byzantine Tolerant Stochastic Gradient Descent in the Era of Big Data
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• Stability and Generalization for Randomized Coordinate Descent