2020

A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic

Hong, Mingyi, Wai, Hoi-To, Wang, Zhaoran et al.

Understand

This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization.

Bilevel optimization is a class of problems which exhibit 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.

Built on

The theory of market economy
H. Van Stackelberg · 1952
Earlier work this paper cites.
Mathematical programs with optimization problems in the constraints
Jerome Bracken and James T. McGill · 1973
Earlier work this paper cites.
Technical note—the equivalence of two mathematical programs with optimization problems in the constraints
Jerome Bracken, James E. Falk, and James T. McGill · 1974
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
Richard S Sutton · 1988
Earlier work this paper cites.
Double penalty method for bilevel optimization problems
Y. Ishizuka and E. Aiyoshi · 1992
Earlier work this paper cites.
A penalty function approach for solving bi-level linear programs
D. J. White and G. Anandalingam · 1993
Earlier work this paper cites.
Descent approaches for quadratic bilevel programming
L. Vicente, G. Savard, and J. Judice · 1994
Earlier work this paper cites.
On bilevel programming, part I: General nonlinear cases
James E. Falk and Jiming Liu · 1995
Earlier work this paper cites.
Mathematical Programs with Equilibrium Constraints
Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph · 1996
Earlier work this paper cites.
Stochastic approximation with two time scales
Vivek S Borkar · 1997
Earlier work this paper cites.
Actor-critic algorithms
Vijay R Konda and John N Tsitsiklis · 2000
Earlier work this paper cites.
Approximately optimal approximate reinforcement learning
Sham Kakade and John Langford · 2002
Earlier work this paper cites.
A natural policy gradient
Sham M Kakade · 2002
Earlier work this paper cites.
Convergence rate of linear two-time-scale stochastic approximation
Vijay R Konda, John N Tsitsiklis, et al · 2004
Earlier work this paper cites.
Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
Abdelkader Mokkadem, Mariane Pelletier, et al · 2006
Earlier work this paper cites.
An overview of bilevel optimization
Benoît Colson, Patrice Marcotte, and Gilles Savard · 2007
Earlier work this paper cites.
Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path
András Antos, Csaba Szepesvári, and Rémi Munos · 2008
Earlier work this paper cites.
Incremental natural actor-critic algorithms
Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton · 2008
Earlier work this paper cites.
Finite-time bounds for fitted value iteration
Rémi Munos and Csaba Szepesvári · 2008
Earlier work this paper cites.
Natural actor-critic
Jan Peters and Stefan Schaal · 2008
Earlier work this paper cites.
Convergent temporal-difference learning with arbitrary smooth function approximation
Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid R Maei, and Csaba Szepesvári · 2009
Earlier work this paper cites.

Similar

Fast gradient-descent methods for temporal-difference learning with linear function approximation
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora · 2009
Cited alongside, same era.
Toward off-policy learning control with function approximation
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton · 2010
Cited alongside, same era.
Algorithms for reinforcement learning
Csaba Szepesvári · 2010
Cited alongside, same era.
Policy evaluation with temporal differences: A survey and comparison
Christoph Dann, Gerhard Neumann, Jan Peters, et al · 2014
Cited alongside, same era.
On the convergence of stochastic bi-level gradient methods
Nicolas Couellan and Wenjuan Wang · 2016
Cited alongside, same era.
Hyperparameter optimization with approximate gradient
Fabian Pedregosa · 2016
Cited alongside, same era.
First-order methods in optimization
Amir Beck · 2017
Cited alongside, same era.
Model-agnostic meta-learning for fast adaptation of deep networks
Chelsea Finn, Pieter Abbeel, and Sergey Levine · 2017
Cited alongside, same era.
A first order method for solving convex bilevel optimization problems
Shoham Sabach and Shimrit Shtern · 2017
Cited alongside, same era.
Proximal policy optimization algorithms
Original
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov · 2017
Cited alongside, same era.
Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
Mengdi Wang, Ethan X Fang, and Han Liu · 2017
Cited alongside, same era.
Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms
Original
Han Xiao, Kashif Rasul, and Roland Vollgraf · 2017
Cited alongside, same era.

Then

A tale of two-timescale reinforcement learning with the tightest finite-time bound
Original
Gal Dalal, Balazs Szorenyi, and Gugan Thoppe · 2019
Later among the works it cites.
Online meta-learning
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine · 2019
Later among the works it cites.
Penalty method for inversion-free deep bilevel optimization
Akshay Mehra and Jihun Hamm · 2019
Later among the works it cites.
Rapid learning or feature reuse? towards understanding the effectiveness of MAML
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals · 2019
Later among the works it cites.
Meta-learning with implicit gradients
Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine · 2019
Later among the works it cites.
Truncated back-propagation for bilevel optimization
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots · 2019
Later among the works it cites.
Sample-optimal parametric q-learning using linearly additive features
Lin Yang and Mengdi Wang · 2019
Later among the works it cites.
Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance
Original
Thinh T Doan · 2020
Closest in time.
A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic
Original
M. Hong, H. Wai, Z. Wang, and Z. Yang · 2020
Closest in time.
Provably faster algorithms for bilevel optimization and applications to meta-learning
Original
Kaiyi Ji, Junjie Yang, and Yingbin Liang · 2020
Closest in time.
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan · 2020
Closest in time.
Finite time analysis of linear two-timescale stochastic approximation with Markovian noise
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai · 2020
Closest in time.
Improved bilevel model: Fast and optimal algorithm with theoretical guarantee
Original
Junyi Li, Bin Gu, and Heng Huang · 2020
Closest in time.
Ufo-blo: Unbiased first-order bilevel optimization
Original
Valerii Likhosherstov, Xingyou Song, Krzysztof Choromanski, Jared Davis, and Adrian Weller · 2020
Closest in time.
A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton
Original
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang · 2020
Closest in time.
A finite time analysis of two time-scale actor-critic methods
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu · 2020
Closest in time.
Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms
Original
Tengyu Xu, Zhe Wang, and Yingbin Liang · 2020
Closest in time.
On the theory of policy gradient methods: Optimality, approximation, and distribution shift
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan · 2021
Closest in time.
Tight high probability bounds for linear stochastic approximation with fixed stepsize
Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai · 2021
Closest in time.
Matrix concentration for products
De Huang, Jonathan Niles-Weed, Joel A Tropp, and Rachel Ward · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…