Journal article
A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization
Optimization letters, Vol.17(7), pp.1595-1611
09/2023
DOI: 10.1007/s11590-022-01951-0
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.
Details
- Title: Subtitle
- A generalized Frank–Wolfe method with “dual averaging” for strongly convex composite optimization
- Creators
- Renbo Zhao - IIT@MITQiuyun Zhu - Boston University
- Resource Type
- Journal article
- Publication Details
- Optimization letters, Vol.17(7), pp.1595-1611
- DOI
- 10.1007/s11590-022-01951-0
- ISSN
- 1862-4472
- eISSN
- 1862-4480
- Publisher
- Springer Berlin Heidelberg
- Grant note
- AFOSR Grant No. FA9550-19-1-0240 / U.S. Air Force (http://dx.doi.org/10.13039/100006831) Massachusetts Institute of Technology (MIT)
- Language
- English
- Date published
- 09/2023
- Academic Unit
- Statistics and Actuarial Science; Business Analytics
- Record Identifier
- 9984446412002771
Metrics
18 Record Views