Coordinate descent with arbitrary sampling II: expected separable overapproximation

Zheng Qu*, Peter Richtárik

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


The design and complexity analysis of randomized coordinate descent methods, and in particular of variants which update a random subset (sampling) of coordinates in each iteration, depend on the notion of expected separable overapproximation (ESO). This refers to an inequality involving the objective function and the sampling, capturing in a compact way certain smoothness properties of the function in a random subspace spanned by the sampled coordinates. ESO inequalities were previously established for special classes of samplings only, almost invariably for uniform samplings. In this paper we develop a systematic technique for deriving these inequalities for a large class of functions and for arbitrary samplings. We demonstrate that one can recover existing ESO results using our general approach, which is based on the study of eigenvalues associated with samplings and the data describing the function.

Original languageEnglish (US)
Pages (from-to)858-884
Number of pages27
JournalOptimization Methods and Software
Issue number5
StatePublished - Sep 2 2016
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2016 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group.


  • arbitrary sampling
  • coordinate descent
  • expected separable overapproximation
  • parallel and distributed coordinate descent
  • randomized methods

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Coordinate descent with arbitrary sampling II: expected separable overapproximation'. Together they form a unique fingerprint.

Cite this