A TWO-TIMESCALE STOCHASTIC ALGORITHM FRAMEWORK FOR BILEVEL OPTIMIZATION: COMPLEXITY ANALYSIS AND APPLICATION TO ACTOR-CRITIC

Mingyi Hong; Hoi To Wai; Zhaoran Wang; Zhuoran Yang

doi:10.1137/20M1387341

A TWO-TIMESCALE STOCHASTIC ALGORITHM FRAMEWORK FOR BILEVEL OPTIMIZATION: COMPLEXITY ANALYSIS AND APPLICATION TO ACTOR-CRITIC

Mingyi Hong, Hoi To Wai, Zhaoran Wang, Zhuoran Yang

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

43 Scopus citations

Abstract

This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization. Bilevel optimization is a class of problems which exhibits a two-level structure, and its goal is to minimize an outer objective function with variables which are constrained to be the optimal solution to an (inner) optimization problem. We consider the case when the inner problem is unconstrained and strongly convex, while the outer problem is constrained and has a smooth objective function. We propose a two-timescale stochastic approximation (TTSA) algorithm for tackling such a bilevel problem. In the algorithm, a stochastic gradient update with a larger step size is used for the inner problem, while a projected stochastic gradient update with a smaller step size is used for the outer problem. We analyze the convergence rates for the TTSA algorithm under various settings: when the outer problem is strongly convex (resp. weakly convex), the TTSA algorithm finds an O (K_max^-²^/³)-optimal (resp. O (K_max^-²^/⁵)-stationary) solution, where Kmax is the total iteration number. As an application, we show that a two-timescale natural actor-critic proximal policy optimization algorithm can be viewed as a special case of our TTSA framework. Importantly, the natural actor-critic algorithm is shown to converge at a rate of O (K_max^-^1/⁴) in terms of the gap in expected discounted reward compared to a global optimal policy.

Original language	English (US)
Pages (from-to)	147-180
Number of pages	34
Journal	SIAM Journal on Optimization
Volume	33
Issue number	1
DOIs	https://doi.org/10.1137/20M1387341
State	Published - 2023

Funding

\ast Received by the editors December 21, 2020; accepted for publication (in revised form) August 16, 2022; published electronically January 27, 2023. Authors listed in alphabetical order. https://doi.org/10.1137/20M1387341 Funding: The work of the first author was supported by NSF CIF-1910385 and CMMI-1727757. \dagger Department of ECE, University of Minnesota, Minneapolis, MN 55455 USA ([email protected]). \ddagger Department of SEEM, The Chinese University of Hong Kong, Hong Kong (htwai@ se.cuhk.edu.hk). \S Department of IEMS, Northwestern University, Evanston, IL 60208 USA (zhaoranwang@ gmail.com). \P Department of Statistics and Data Science, Yale University, New Haven, CT 06520 USA ([email protected]).

ASJC Scopus subject areas

Software
Theoretical Computer Science
Applied Mathematics

Access to Document

10.1137/20M1387341

Cite this

@article{0eca97d4cbfb4c9e94ed11e2971ed8e2,

title = "A TWO-TIMESCALE STOCHASTIC ALGORITHM FRAMEWORK FOR BILEVEL OPTIMIZATION: COMPLEXITY ANALYSIS AND APPLICATION TO ACTOR-CRITIC",

abstract = "This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization. Bilevel optimization is a class of problems which exhibits a two-level structure, and its goal is to minimize an outer objective function with variables which are constrained to be the optimal solution to an (inner) optimization problem. We consider the case when the inner problem is unconstrained and strongly convex, while the outer problem is constrained and has a smooth objective function. We propose a two-timescale stochastic approximation (TTSA) algorithm for tackling such a bilevel problem. In the algorithm, a stochastic gradient update with a larger step size is used for the inner problem, while a projected stochastic gradient update with a smaller step size is used for the outer problem. We analyze the convergence rates for the TTSA algorithm under various settings: when the outer problem is strongly convex (resp. weakly convex), the TTSA algorithm finds an O (Kmax-2/3)-optimal (resp. O (Kmax-2/5)-stationary) solution, where Kmax is the total iteration number. As an application, we show that a two-timescale natural actor-critic proximal policy optimization algorithm can be viewed as a special case of our TTSA framework. Importantly, the natural actor-critic algorithm is shown to converge at a rate of O (Kmax-1/4) in terms of the gap in expected discounted reward compared to a global optimal policy.",

author = "Mingyi Hong and Wai, {Hoi To} and Zhaoran Wang and Zhuoran Yang",

note = "Publisher Copyright: {\textcopyright} 2023 Society for Industrial and Applied Mathematics.",

year = "2023",

doi = "10.1137/20M1387341",

language = "English (US)",

volume = "33",

pages = "147--180",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - A TWO-TIMESCALE STOCHASTIC ALGORITHM FRAMEWORK FOR BILEVEL OPTIMIZATION

T2 - COMPLEXITY ANALYSIS AND APPLICATION TO ACTOR-CRITIC

AU - Hong, Mingyi

AU - Wai, Hoi To

AU - Wang, Zhaoran

AU - Yang, Zhuoran

PY - 2023

Y1 - 2023

N2 - This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization. Bilevel optimization is a class of problems which exhibits a two-level structure, and its goal is to minimize an outer objective function with variables which are constrained to be the optimal solution to an (inner) optimization problem. We consider the case when the inner problem is unconstrained and strongly convex, while the outer problem is constrained and has a smooth objective function. We propose a two-timescale stochastic approximation (TTSA) algorithm for tackling such a bilevel problem. In the algorithm, a stochastic gradient update with a larger step size is used for the inner problem, while a projected stochastic gradient update with a smaller step size is used for the outer problem. We analyze the convergence rates for the TTSA algorithm under various settings: when the outer problem is strongly convex (resp. weakly convex), the TTSA algorithm finds an O (Kmax-2/3)-optimal (resp. O (Kmax-2/5)-stationary) solution, where Kmax is the total iteration number. As an application, we show that a two-timescale natural actor-critic proximal policy optimization algorithm can be viewed as a special case of our TTSA framework. Importantly, the natural actor-critic algorithm is shown to converge at a rate of O (Kmax-1/4) in terms of the gap in expected discounted reward compared to a global optimal policy.

AB - This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization. Bilevel optimization is a class of problems which exhibits a two-level structure, and its goal is to minimize an outer objective function with variables which are constrained to be the optimal solution to an (inner) optimization problem. We consider the case when the inner problem is unconstrained and strongly convex, while the outer problem is constrained and has a smooth objective function. We propose a two-timescale stochastic approximation (TTSA) algorithm for tackling such a bilevel problem. In the algorithm, a stochastic gradient update with a larger step size is used for the inner problem, while a projected stochastic gradient update with a smaller step size is used for the outer problem. We analyze the convergence rates for the TTSA algorithm under various settings: when the outer problem is strongly convex (resp. weakly convex), the TTSA algorithm finds an O (Kmax-2/3)-optimal (resp. O (Kmax-2/5)-stationary) solution, where Kmax is the total iteration number. As an application, we show that a two-timescale natural actor-critic proximal policy optimization algorithm can be viewed as a special case of our TTSA framework. Importantly, the natural actor-critic algorithm is shown to converge at a rate of O (Kmax-1/4) in terms of the gap in expected discounted reward compared to a global optimal policy.

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

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

U2 - 10.1137/20M1387341

DO - 10.1137/20M1387341

M3 - Article

AN - SCOPUS:85148719018

SN - 1052-6234

VL - 33

SP - 147

EP - 180

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -

A TWO-TIMESCALE STOCHASTIC ALGORITHM FRAMEWORK FOR BILEVEL OPTIMIZATION: COMPLEXITY ANALYSIS AND APPLICATION TO ACTOR-CRITIC

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this