Bregman Augmented Lagrangian Method: Convergence, acceleration, and applications in reinforcement learning

Yan, Shen

Permalink

https://hdl.handle.net/2142/109433 Copy

Description

Title

Bregman Augmented Lagrangian Method: Convergence, acceleration, and applications in reinforcement learning

Author(s)

Yan, Shen

Issue Date

2020-12-07

Director of Research (if dissertation) or Advisor (if thesis)

He, Niao

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Bregman Augmented Lagrangian Method (BALM)
• Bregman Proximal Point Method (BPP)
• Acceleration (acc-BPP, acc-BALM)
• Reinforcement Learning

Abstract

In this thesis, the algorithm Bergman proximal point method (BPP), and its application to Bregman augmented Lagrangian method(BALM) is considered. Unlike classical augmented Lagrangian method (ALM ), whose convergence rate and its relation with the proximal point method is well-understood, the convergence rate for BALM has not yet been thoroughly studied in the literature. We analyze, in this thesis, the convergence rates of BALM in terms of the primal objective as well as the feasibility violation. We show that the algorithm can also be applied to variational inequality problems with convex constraints, and fully characterize the iteration complexity of the algorithm derived from the inexact version of BALM. Furthermore, we develop, for the first time, an accelerated Bregman proximal point method, that improves the convergence rate from $\cO(1/\sum_{k=0}^{T-1}\eta_k)$ to $\cO(1/(\sum_{k=0}^{T-1}\sqrt{\eta_k})^2)$, where $\{\eta_k\}_{k=0}^{T-1}$ is the sequence of proximal parameters. When applied to the dual of convex constrained convex programs, this leads to the construction of an accelerated BALM, that achieves the improved rates for both primal and dual convergences. Finally, numerical experiments comparing the performance of different Bregman divergences as well as the acceleration versions, with applications to Markov decision problems/reinforcement learning are presented at the end.

Graduation Semester

2020-12

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/109433

Copyright and License Information

Copyright 2020 Shen Yan

Owning Collections