A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization
Abstract We propose a simple variant of the generalized Frank–Wolfe method for solving strongly convex composite optimization problems, by introducing an additional averaging step on the dual variables. We show that in this variant, one can choose a simple constant step-size and obtain...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2022
|
| Online Access: | https://hdl.handle.net/1721.1/146364 |
| _version_ | 1811083697718296576 |
|---|---|
| author | Zhao, Renbo Zhu, Qiuyun |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Zhao, Renbo Zhu, Qiuyun |
| author_sort | Zhao, Renbo |
| collection | MIT |
| description | Abstract
We propose a simple variant of the generalized Frank–Wolfe method for solving strongly convex composite optimization problems, by introducing an additional averaging step on the dual variables. We show that in this variant, one can choose a simple constant step-size and obtain a linear convergence rate on the duality gaps. By leveraging the convergence analysis of this variant, we then analyze the local convergence rate of the logistic fictitious play algorithm, which is well-established in game theory but lacks any form of convergence rate guarantees. We show that, with high probability, this algorithm converges locally at rate O(1/t), in terms of certain expected duality gap. |
| first_indexed | 2024-09-23T12:37:41Z |
| format | Article |
| id | mit-1721.1/146364 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:37:41Z |
| publishDate | 2022 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1463642023-01-27T20:08:56Z A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization Zhao, Renbo Zhu, Qiuyun Massachusetts Institute of Technology. Operations Research Center Abstract We propose a simple variant of the generalized Frank–Wolfe method for solving strongly convex composite optimization problems, by introducing an additional averaging step on the dual variables. We show that in this variant, one can choose a simple constant step-size and obtain a linear convergence rate on the duality gaps. By leveraging the convergence analysis of this variant, we then analyze the local convergence rate of the logistic fictitious play algorithm, which is well-established in game theory but lacks any form of convergence rate guarantees. We show that, with high probability, this algorithm converges locally at rate O(1/t), in terms of certain expected duality gap. 2022-11-14T12:40:26Z 2022-11-14T12:40:26Z 2022-11-07 2022-11-13T04:15:50Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/146364 Zhao, Renbo and Zhu, Qiuyun. 2022. "A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization." PUBLISHER_CC en https://doi.org/10.1007/s11590-022-01951-0 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Zhao, Renbo Zhu, Qiuyun A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization |
| title | A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization |
| title_full | A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization |
| title_fullStr | A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization |
| title_full_unstemmed | A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization |
| title_short | A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization |
| title_sort | generalized frank wolfe method with dual averaging for strongly convex composite optimization |
| url | https://hdl.handle.net/1721.1/146364 |
| work_keys_str_mv | AT zhaorenbo ageneralizedfrankwolfemethodwithdualaveragingforstronglyconvexcompositeoptimization AT zhuqiuyun ageneralizedfrankwolfemethodwithdualaveragingforstronglyconvexcompositeoptimization AT zhaorenbo generalizedfrankwolfemethodwithdualaveragingforstronglyconvexcompositeoptimization AT zhuqiuyun generalizedfrankwolfemethodwithdualaveragingforstronglyconvexcompositeoptimization |