Dear AC,
> Can the authors comment on whether there are any connections between their FTXL method and the "linear coupling" method of Allen-Zhu and Orecchia [1], which also aims to combine mirror descent/FTRL and acceleration? The technique I mention is not analyzed in the context of games, but I am curious of there are connections nonetheless.
Excellent question, thanks for bringing it up! It's a complex issue, so we're giving two answers, one shorter and one (much) longer.
---
### **Short answer**
The linear coupling approach of [1] is related to the momentum-based approach of Su, Boyd and Candès which forms the basis of (FTXL), but the two are not equivalent. In essence, they are both different approaches to acceleration – and, in turn, both different than the original "estimate sequences" approach of Nesterov – and we do not see a way of directly applying the techniques of [1] to our setting.
---
### **Long answer**
Because [1] is not taking a momentum-based approach (see e.g., footnote 5 in p. 4 of the arxiv version of the paper), it is difficult to accurately translate the coupling approach of [1] to our setting and provide a direct comparison between the two methods.
One of the main reasons for this is that [1] is essentially using two step-sizes: the first is taken equal to the inverse Lipschitz modulus of the function being minimized and is used to take a gradient step; the second step-size sequence is much more aggressive, and it is used to generate an ancillary, exploration sequence which "scouts ahead". These two sequences are then "coupled" with a mixing coefficient which plays a role "similar" - but *not equivalent* - to the friction coefficient in the (HBVF) formulation of (NAG) by Su, Boyd, and Candès.
The above is the best high-level description and analogy we can make between the coupling approach of [1] and the momentum-driven analysis of Su, Boyd, and Candès and/or momentum analysis in Nesterov's 2004 textbook (which is itself quite different from Nesterov's original 1983 paper).
At a low level (and omitting certain technical details and distinctions that are not central to this discussion), the linear coupling approach of [1] applied to our setting would correspond to the update scheme:
\begin{align}
x_t &= Q(y_t)
\\\\
w_t &= \lambda_t z_t + (1-\lambda_t) x_t
\\\\
y_{t+1} &= y_t + (1-\lambda_t) \eta_t \hat v_t
\\\\
z_{t+1} &= \lambda_t z_t + (1-\lambda_t) x_{t+1}
\end{align}
with $\hat v_t$ obtained by querying a first-order oracle at $w_t$ – that is, $\hat v_t$ is an estimate, possibly imperfect, of $v(w_t)$.
The first and third lines of this update scheme are similar to the corresponding update structure of (FTXL). However, whereas (FTXL) builds momentum by the aggregation of gradient information via the momentum variables $p_t$, the linear coupling method above achieves acceleration through the coupling of the sequences $w_t$, $z_t$ and $x_t$, and by taking an increasing step-size sequence $\eta_t$ that grows roughly as $\Theta(t)$, and a mixing coefficient $\lambda_t$ that evolves as $\lambda_t = 1 - 1/(L\eta_t)$, where $L$ is the Lipschitz modulus of $v$.
Beyond this comparison, we cannot provide a term-by-term correspondence between the momentum-based and coupling-based approaches, because the two methors are not equivalent (even though they give the same value convergence rates). In particular, we do not see a way of linking the parameters $\eta_t$ and $\lambda_t$ of the coupling approach to the friction and step-size parameters of the momentum approach.
In the context of convex minimization problems, the coupling-based approach of [1] is more amenable to a regret-based analysis – this is the "unification" that [1] referred to – while the momentum-based approach of Su, Boyd, and Candès facilitates a Lyapunov-based analysis. Ultimately, these are all different - though, of course, equally valid - approaches to acceleration. From a game-theoretic standpoint, the momentum-based approach seems to be more fruitful and easier to implement, but studying the linear coupling approach of [1] could also be very relevant.
---
We will be happy to include a version of the above discussion at the first possible revision opportunity. In the meantime, please let us know if you have any follow-up questions on the above, and thanks again for your question and for handling our submission!
Kind regards,
The authors