Zeroth-order stochastic projected gradient descent for nonconvex optimization

Sijia Liu; Xingguo Li; Pin Yu Chen; Jarvis D Haupt; Lisa Amini

doi:10.1109/GlobalSIP.2018.8646618

Zeroth-order stochastic projected gradient descent for nonconvex optimization

Sijia Liu, Xingguo Li, Pin Yu Chen, Jarvis D Haupt, Lisa Amini

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

20 Scopus citations

Abstract

In this paper, we analyze the convergence of the zeroth-order stochastic projected gradient descent (ZO-SPGD) method for constrained convex and nonconvex optimization scenarios where only objective function values (not gradients) are directly available. We show statistical properties of a new random gradient estimator, constructed through random direction samples drawn from a bounded uniform distribution. We prove that ZO-SPGD yields a O( fracdbqsqrt T + frac1sqrt T right) convergence rate for convex but non-smooth optimization, where d is the number of optimization variables, b is the minibatch size, q is the number of random direction samples for gradient estimation, and T is the number of iterations. For nonconvex optimization, we show that ZO-SPGD achieves O( frac1sqrt T right) convergence rate but suffers an additional O( fracd + qbq right) error. Our the oretical investigation on ZO-SPGD provides a general framework to study the convergence rate of zeroth-order algorithms.

Original language	English (US)
Title of host publication	2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1179-1183
Number of pages	5
ISBN (Electronic)	9781728112954
DOIs	https://doi.org/10.1109/GlobalSIP.2018.8646618
State	Published - Jul 2 2018
Event	2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Anaheim, United States Duration: Nov 26 2018 → Nov 29 2018

Publication series

Name	2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings

Conference

Conference	2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018
Country/Territory	United States
City	Anaheim
Period	11/26/18 → 11/29/18

Bibliographical note

Funding Information:
The authors graciously acknowledge support from the DARPA YFA, Grant N66001-14-1-4047.

Publisher Copyright:
© 2018 IEEE.

Keywords

Nonconvex optimization
Projected gradient descent
Zeroth-order optimization

Publisher link

10.1109/GlobalSIP.2018.8646618

Find It

Find It at U of M Libraries

Cite this

Liu, S., Li, X., Chen, P. Y., Haupt, J. D., & Amini, L. (2018). Zeroth-order stochastic projected gradient descent for nonconvex optimization. In 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings (pp. 1179-1183). Article 8646618 (2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/GlobalSIP.2018.8646618

Zeroth-order stochastic projected gradient descent for nonconvex optimization. / Liu, Sijia; Li, Xingguo; Chen, Pin Yu et al.
2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. p. 1179-1183 8646618 (2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Liu, S, Li, X, Chen, PY, Haupt, JD & Amini, L 2018, Zeroth-order stochastic projected gradient descent for nonconvex optimization. in 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings., 8646618, 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1179-1183, 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018, Anaheim, United States, 11/26/18. https://doi.org/10.1109/GlobalSIP.2018.8646618

Liu S, Li X, Chen PY, Haupt JD, Amini L. Zeroth-order stochastic projected gradient descent for nonconvex optimization. In 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2018. p. 1179-1183. 8646618. (2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings). doi: 10.1109/GlobalSIP.2018.8646618

Liu, Sijia ; Li, Xingguo ; Chen, Pin Yu et al. / Zeroth-order stochastic projected gradient descent for nonconvex optimization. 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 1179-1183 (2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings).

@inproceedings{5eb9b3b3717f44d09992737c6a42c172,

title = "Zeroth-order stochastic projected gradient descent for nonconvex optimization",

abstract = "In this paper, we analyze the convergence of the zeroth-order stochastic projected gradient descent (ZO-SPGD) method for constrained convex and nonconvex optimization scenarios where only objective function values (not gradients) are directly available. We show statistical properties of a new random gradient estimator, constructed through random direction samples drawn from a bounded uniform distribution. We prove that ZO-SPGD yields a O( fracdbqsqrt T + frac1sqrt T right) convergence rate for convex but non-smooth optimization, where d is the number of optimization variables, b is the minibatch size, q is the number of random direction samples for gradient estimation, and T is the number of iterations. For nonconvex optimization, we show that ZO-SPGD achieves O( frac1sqrt T right) convergence rate but suffers an additional O( fracd + qbq right) error. Our the oretical investigation on ZO-SPGD provides a general framework to study the convergence rate of zeroth-order algorithms.",

keywords = "Nonconvex optimization, Projected gradient descent, Zeroth-order optimization",

author = "Sijia Liu and Xingguo Li and Chen, {Pin Yu} and Haupt, {Jarvis D} and Lisa Amini",

note = "Funding Information: The authors graciously acknowledge support from the DARPA YFA, Grant N66001-14-1-4047. Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 ; Conference date: 26-11-2018 Through 29-11-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1109/GlobalSIP.2018.8646618",

language = "English (US)",

series = "2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1179--1183",

booktitle = "2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings",

}

TY - GEN

T1 - Zeroth-order stochastic projected gradient descent for nonconvex optimization

AU - Liu, Sijia

AU - Li, Xingguo

AU - Chen, Pin Yu

AU - Haupt, Jarvis D

AU - Amini, Lisa

PY - 2018/7/2

Y1 - 2018/7/2

N2 - In this paper, we analyze the convergence of the zeroth-order stochastic projected gradient descent (ZO-SPGD) method for constrained convex and nonconvex optimization scenarios where only objective function values (not gradients) are directly available. We show statistical properties of a new random gradient estimator, constructed through random direction samples drawn from a bounded uniform distribution. We prove that ZO-SPGD yields a O( fracdbqsqrt T + frac1sqrt T right) convergence rate for convex but non-smooth optimization, where d is the number of optimization variables, b is the minibatch size, q is the number of random direction samples for gradient estimation, and T is the number of iterations. For nonconvex optimization, we show that ZO-SPGD achieves O( frac1sqrt T right) convergence rate but suffers an additional O( fracd + qbq right) error. Our the oretical investigation on ZO-SPGD provides a general framework to study the convergence rate of zeroth-order algorithms.

AB - In this paper, we analyze the convergence of the zeroth-order stochastic projected gradient descent (ZO-SPGD) method for constrained convex and nonconvex optimization scenarios where only objective function values (not gradients) are directly available. We show statistical properties of a new random gradient estimator, constructed through random direction samples drawn from a bounded uniform distribution. We prove that ZO-SPGD yields a O( fracdbqsqrt T + frac1sqrt T right) convergence rate for convex but non-smooth optimization, where d is the number of optimization variables, b is the minibatch size, q is the number of random direction samples for gradient estimation, and T is the number of iterations. For nonconvex optimization, we show that ZO-SPGD achieves O( frac1sqrt T right) convergence rate but suffers an additional O( fracd + qbq right) error. Our the oretical investigation on ZO-SPGD provides a general framework to study the convergence rate of zeroth-order algorithms.

KW - Nonconvex optimization

KW - Projected gradient descent

KW - Zeroth-order optimization

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

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

U2 - 10.1109/GlobalSIP.2018.8646618

DO - 10.1109/GlobalSIP.2018.8646618

M3 - Conference contribution

AN - SCOPUS:85063079419

T3 - 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings

SP - 1179

EP - 1183

BT - 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018

Y2 - 26 November 2018 through 29 November 2018

ER -

Zeroth-order stochastic projected gradient descent for nonconvex optimization

Abstract

Publication series

Conference

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this