Global convergence rate of proximal incremental aggregated gradient methods

N. D. Vanli, Mert Gurbuzbalaban, A. Ozdaglar

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a nonsmooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and takes a proximal step with respect to the nonsmooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number and gradient delay bound dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.

Original languageEnglish (US)
Pages (from-to)1282-1300
Number of pages19
JournalSIAM Journal on Optimization
Volume28
Issue number2
DOIs
StatePublished - Jan 1 2018

Fingerprint

Gradient methods
Gradient Method
Global Convergence
Convergence Rate
Gradient
Nonsmooth Function
Updating
Rate of Convergence
Distributed Optimization
Smart Grid
Incremental Algorithm
Gradient Algorithm
Constrained Optimization
Condition number
Smooth function
Convergence Properties
Convex function
Wireless Sensor Networks
Machine Learning
Constrained optimization

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Convex optimization
  • Nonsmooth optimization
  • Proximal incremental aggregated gradient method

Cite this

@article{e8f85a404f164bf494686f1a5d82f196,
title = "Global convergence rate of proximal incremental aggregated gradient methods",
abstract = "We focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a nonsmooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and takes a proximal step with respect to the nonsmooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number and gradient delay bound dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.",
keywords = "Convex optimization, Nonsmooth optimization, Proximal incremental aggregated gradient method",
author = "Vanli, {N. D.} and Mert Gurbuzbalaban and A. Ozdaglar",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/16M1094415",
language = "English (US)",
volume = "28",
pages = "1282--1300",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

Global convergence rate of proximal incremental aggregated gradient methods. / Vanli, N. D.; Gurbuzbalaban, Mert; Ozdaglar, A.

In: SIAM Journal on Optimization, Vol. 28, No. 2, 01.01.2018, p. 1282-1300.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Global convergence rate of proximal incremental aggregated gradient methods

AU - Vanli, N. D.

AU - Gurbuzbalaban, Mert

AU - Ozdaglar, A.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a nonsmooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and takes a proximal step with respect to the nonsmooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number and gradient delay bound dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.

AB - We focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a nonsmooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and takes a proximal step with respect to the nonsmooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number and gradient delay bound dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.

KW - Convex optimization

KW - Nonsmooth optimization

KW - Proximal incremental aggregated gradient method

UR - http://www.scopus.com/inward/record.url?scp=85049679887&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049679887&partnerID=8YFLogxK

U2 - 10.1137/16M1094415

DO - 10.1137/16M1094415

M3 - Article

VL - 28

SP - 1282

EP - 1300

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 2

ER -