CoChat

Harnessing smoothness to accelerate distributed optimization

Qu, Guannan, Li, Na · 2016 · 2016 IEEE 55th Conference on Decision and Control (CDC)

The DOI matches its Crossref record; 36 of the 37 references it cites were found in a registry or an index.

Abstract

There has been a growing effort in studying the distributed optimization problem over a network. The objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. Literature has developed consensus-based distributed (sub)gradient descent (DGD) methods and has shown that they have the same convergence rate O(log t/√t) as the centralized (sub)gradient methods (CGD) when the function is convex but possibly nonsmooth. However, when the function is convex and smooth, under the framework of DGD, it is unclear how to harness the smoothness to obtain a faster convergence rate comparable to CGD's convergence rate. In this paper, we propose a distributed algorithm that, despite using the same amount of communication per iteration as DGD, can effectively harnesses the function smoothness and converge to the optimum with a rate of O(1/t). If the objective function is further strongly convex, our algorithm has a linear convergence rate. Both rates match the convergence rate of CGD. The key step in our algorithm is a novel gradient estimation scheme that uses history information to achieve fast and accurate estimation of the average gradient. To motivate the necessity of history information, we also show that it is impossible for a class of distributed algorithms like DGD to achieve a linear convergence rate without using history information even if the objective function is strongly convex and smooth.

Overview

Integrity signals

Registry

Crossref · 10.1109/cdc.2016.7798263

Cites

36 of 36 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

Research works printed but not linked: 1

  1. 2012, Logistic Regression

Cited by

See all 81

Metadata

Authors
Qu, G., & Li, N.
Affiliations
Harvard University (US)
Venue
2016 IEEE 55th Conference on Decision and Control (CDC)
Publisher
IEEE
Published
2016-12
Pages
159-166
ISSN
0191-2216 (ISSN-L)
OpenAlex
W2400034325
Cited by
72
References
37
Citations by year
2025: 4 · 2024: 5 · 2023: 4 · 2022: 7 · 2021: 3 · 2020: 5 · 2019: 10 · 2018: 22 · 2017: 9 · 2016: 3
FWCI
12.53
Type
conference paper
Language
en
Open access
closed
Locations
IEEE Conference on Decision and Control (CDC) (publishedVersion)
Topics
  • Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
Keywords
distributed optimization, smoothness, linear convergence, strongly convex functions, gradient estimation, history information, convergence rate, nonsmooth optimization, communication complexity

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.