DiSCO: Distributed optimization for self-concordant empirical loss

Yuchen Zhang, Lin Xiao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

91 Scopus citations

Abstract

We propose a new distributed algorithm for empirical risk minimization in machine learning. The algorithm is based on an inexact damped Newton method, where the inexact Newton steps are computed by a distributed preconditioned conjugate gradient method. We analyze its iteration complexity and communication efficiency for minimizing self-concordant empirical loss functions, and discuss the results for distributed ridge regression, logistic regression and binary classification with a smoothed hinge loss. In a standard setting for supervised learning, where the n data points are i.i.d. sampled and when the regularization parameter scales as 1√n, we show that the proposed algorithm is communication efficient: the required round of communication does not increase with the sample size n, and only grows slowly with the number of machines.

Original languageEnglish
Title of host publication32nd International Conference on Machine Learning, ICML 2015
EditorsFrancis Bach, David Blei
PublisherInternational Machine Learning Society (IMLS)
Pages362-370
Number of pages9
ISBN (Electronic)9781510810587
StatePublished - 2015
Externally publishedYes
Event32nd International Conference on Machine Learning, ICML 2015 - Lile, France
Duration: Jul 6 2015Jul 11 2015

Publication series

Name32nd International Conference on Machine Learning, ICML 2015
Volume1

Conference

Conference32nd International Conference on Machine Learning, ICML 2015
Country/TerritoryFrance
CityLile
Period07/6/1507/11/15

Fingerprint

Dive into the research topics of 'DiSCO: Distributed optimization for self-concordant empirical loss'. Together they form a unique fingerprint.

Cite this