CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016-11-01T00:00:00.000000Z)

TL;DR

This work presents a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing, and extends the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso.

Abstract

The scale of modern datasets necessitates the development of efficient distributed optimization methods for machine learning. We present a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing. We extend the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso, sparse logistic regression, and elastic net regularization, and show how earlier work can be derived as a special case. We provide convergence guarantees for the class of convex regularized loss minimization objectives, leveraging a novel approach in handling non-strongly-convex regularizers and non-smooth loss functions. The resulting framework has markedly improved performance over state-of-the-art methods, as we illustrate with an extensive set of experiments on real distributed datasets.

Authors

Martin Jaggi

9 papers

Michael I. Jordan

14 papers

Virginia Smith

6 papers

TL;DR

Abstract

Authors

References78 items

A Distributed Second-Order Algorithm You Can Trust

Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients

Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems

A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization

AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods

Distributed block-diagonal approximation methods for regularized empirical risk minimization

Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems

Federated Multi-Task Learning

Distributed coordinate descent for generalized linear models with regularization

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition

A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization

Primal-Dual Rates and Certificates

Distributed optimization with arbitrary local solvers

L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework

A Dual Augmented Block Minimization Framework for Learning with Limited Memory

Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling

Distributed Mini-Batch SDCA

Distributed Box-Constrained Quadratic Optimization for Dual Linear SVM

Blitz: A Principled Meta-Algorithm for Scaling Sparse Optimization

DUAL-LOCO: Distributing Statistical Estimation Using Random Projections

Communication Complexity of Distributed Convex Learning and Optimization

MLlib: Machine Learning in Apache Spark

Linear convergence of first order methods under weak nondegeneracy assumptions for convex programming

Coordinate descent algorithms

Adding vs. Averaging in Distributed Primal-Dual Optimization

SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization

Distributed Coordinate Descent for L1-regularized Logistic Regression

Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

Communication-Efficient Distributed Dual Coordinate Ascent

Distributed stochastic optimization and learning

LOCO: Distributing Ridge Regression with Random Projections

Distributed Block Coordinate Descent for Minimizing Partially Separable Functions

A distributed block coordinate descent method for training $l_1$ regularized linear classifiers

Distributed dual gradient methods and error bound conditions

Communication-Efficient Distributed Optimization using an Approximate Newton-type Method

Accelerated, Parallel, and Proximal Coordinate Descent

Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

Estimation, Optimization, and Parallelism when Data is Sparse

On Theoretical Analysis of Distributed Stochastic Dual Coordinate Ascent

Analysis of Distributed Stochastic Dual Coordinate Ascent

Distributed Coordinate Descent Method for Learning with Big Data

Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization

Parallel Coordinate Descent Newton Method for Efficient $\ell_1$-Regularized Minimization

On the complexity analysis of randomized block-coordinate descent methods

Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

Mini-Batch Primal and Dual Methods for SVMs

Communication-efficient algorithms for statistical optimization

Efficient Distributed Linear Classification Algorithms via the Alternating Direction Method of Multipliers

D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization

An improved GLMNET for l1-regularized logistic regression

Stochastic Methods for l1-regularized Loss Minimization

Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Parallel Coordinate Descent for L1-Regularized Loss Minimization

Convex Analysis and Monotone Operator Theory in Hilbert Spaces

Optimal Distributed Online Prediction Using Mini-Batches

Parallelized Stochastic Gradient Descent

A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification

Regularization Paths for Generalized Linear Models via Coordinate Descent.

Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models

Stochastic methods for l1 regularized loss minimization

LIBLINEAR: A Library for Large Linear Classification

A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning

Scalable training of L1-regularized log-linear models

Smooth minimization of non-smooth functions

Hessian-CoCoA : a general parallel and distributed framework for non-strongly convex regularizers

An accelerated communicationefficient primal-dual optimization framework for structured machine learning. arXiv.org, 2017a

Techniques Of Variational Analysis

Fundamentals Of Convex Analysis

Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption

Distributed Optimization for Non-Strongly Convex Regularizers

CoCoA: A General Framework for Communication-Efficient Distributed Optimization

Iteration complexity of feasible descent methods for convex optimization

Solving Large Scale Linear SVM with Distributed Block Minimization

Partial Solutions Manual Parallel and Distributed Computation : Numerical Methods

Journal of Machine Learning Research () Submitted 9/12; Published Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization

Edinburgh Research Explorer On the Complexity of Parallel Coordinate Descent