{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/109433"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/109433","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Bregman Augmented Lagrangian Method: Convergence, acceleration, and applications in 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.","abstract_html":"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 <span class=\"etd-inline-math\">\\cO(1/\\sum<sub>k=0</sub><sup>T-1</sup>\\eta<sub>k</sub>)</span> to <span class=\"etd-inline-math\">\\cO(1/(\\sum<sub>k=0</sub><sup>T-1</sup>\\sqrt{\\eta<sub>k</sub>})<sup>2</sup>)</span>, where <span class=\"etd-inline-math\">\\{\\eta<sub>k</sub>\\}<sub>k=0</sub><sup>T-1</sup></span> 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.","abstract_has_math":true,"creators":["Yan, Shen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["He, Niao"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-03-05T21:38:20Z","date_published":"2021-03-05T21:38:20Z","updated_at":"2026-07-22T22:24:50Z","subjects":["Bregman Augmented Lagrangian Method (BALM)","Bregman Proximal Point Method (BPP)","Acceleration (acc-BPP, acc-BALM)","Reinforcement Learning"],"languages":["en"],"rights":["Copyright 2020 Shen Yan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/109433","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["He, Niao"]},{"key":"dc:creator","label":"Author","values":["Yan, Shen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-03-05T21:38:20Z","2020-12-07","2020-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Bregman Augmented Lagrangian Method (BALM)","Bregman Proximal Point Method (BPP)","Acceleration (acc-BPP, acc-BALM)","Reinforcement Learning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Shen Yan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/109433"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-03-04 without embargo terms","The student, Shen Yan, accepted the attached license on 2020-12-03 at 09:06.","The student, Shen Yan, submitted this Thesis for approval on 2020-12-03 at 09:13.","This Thesis was approved for publication on 2020-12-07 at 10:34.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16051 on 2021-03-04 at 15:36:04","Made available in DSpace on 2021-03-05T21:38:20Z (GMT). No. of bitstreams: 2 YAN-THESIS-2020.pdf: 536235 bytes, checksum: 9d790f6a5e6b4b70bb2cec0465659a90 (MD5) LICENSE.txt: 4205 bytes, checksum: 3b205868bb08ad1ffb1e36781f2a5b17 (MD5) Previous issue date: 2020-12-07"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Bregman Augmented Lagrangian Method: Convergence, acceleration, and applications in reinforcement learning"]}]}],"canonical_facts":{"dc:contributor":["He, Niao"],"dc:creator":["Yan, Shen"],"dc:date":["2021-03-05T21:38:20Z","2020-12-07","2020-12"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-03-04 without embargo terms","The student, Shen Yan, accepted the attached license on 2020-12-03 at 09:06.","The student, Shen Yan, submitted this Thesis for approval on 2020-12-03 at 09:13.","This Thesis was approved for publication on 2020-12-07 at 10:34.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16051 on 2021-03-04 at 15:36:04","Made available in DSpace on 2021-03-05T21:38:20Z (GMT). No. of bitstreams: 2 YAN-THESIS-2020.pdf: 536235 bytes, checksum: 9d790f6a5e6b4b70bb2cec0465659a90 (MD5) LICENSE.txt: 4205 bytes, checksum: 3b205868bb08ad1ffb1e36781f2a5b17 (MD5) Previous issue date: 2020-12-07"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/109433"],"dc:language":["en"],"dc:rights":["Copyright 2020 Shen Yan"],"dc:subject":["Bregman Augmented Lagrangian Method (BALM)","Bregman Proximal Point Method (BPP)","Acceleration (acc-BPP, acc-BALM)","Reinforcement Learning"],"dc:title":["Bregman Augmented Lagrangian Method: Convergence, acceleration, and applications in reinforcement learning"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:50Z"}