\section{Introduction} \label{sec:intro}

\neurips{\vspace{-0.3cm}}
Online learning has a long history that is intimately related to the development of game theory, convex optimization, and machine learning. One of its earliest instantiations can be traced to~Brown's proposal \cite{Brown1949} of fictitious play as a method to solve two-player zero-sum games. Indeed, as  shown by~\cite{robinson1951iterative}, when the players of (zero-sum) matrix game
use fictitious play to iteratively update their actions in response to each other's history of play, the resulting dynamics converge in the following sense: the product of the empirical distributions of strategies for each player converges to the set of Nash equilibria in the game, 
though the rate of convergence is now known to be exponentially slow~\cite{daskalakis2014counter}. %
Moreover, such convergence to Nash equilibria fails in non-zero-sum games \cite{shapley_topics_1963}.

The slow convergence of fictitious play to Nash equilibria in zero-sum matrix games and non-convergence in general-sum games can be mitigated by appealing to the pioneering works \cite{blackwell1954controlled,hannan1957approximation} and the ensuing literature on no-regret learning~\cite{cesa2006prediction}.
It is known that if both players of a zero-sum matrix game experience regret that is at most $\varepsilon(T)$, the product of the players' empirical distributions of strategies is an $O(\varepsilon(T)/T)$-approximate Nash equilibrium. 
More generally, if each player of a general-sum, multi-player game experiences regret that is at most~$ \varepsilon(T)$,  the empirical distribution of joint strategies  converges to a coarse correlated equilibrium\footnote{In general-sum games, it is typical to focus on proving convergence rates for weaker types of equilibrium than Nash, such as coarse correlated equilibria, since finding Nash equilibria is PPAD-complete \cite{daskalakis_complexity_2006,chen_settling_2009}.} of the game, at a rate of~$O(\varepsilon(T)/{T})$. Importantly, a multitude of online learning algorithms, such as the celebrated Hedge and Follow-The-Perturbed-Leader algorithms, guarantee adversarial %
regret $O(\sqrt{T})$~\cite{cesa2006prediction}. Thus, when such algorithms are employed by all players in a game, their $O(\sqrt{T})$ regret  implies convergence to coarse correlated equilibria (and Nash equilibria of matrix games) at a rate of $O(1/\sqrt{T})$.

While standard no-regret learners guarantee $O(\sqrt{T})$ regret for each player in a game, the players can do better by employing specialized no-regret learning procedures. Indeed, it was established by~\cite{daskalakis_near-optimal_2013} 
that there exists a somewhat complex no-regret learner based on Nesterov's excessive gap technique \cite{nesterov2005excessive}, which guarantees $O(\log T)$ regret to each player of a two-player zero-sum game. This represents an exponential improvement over the regret guaranteed by standard no-regret learners. More generally, \cite{syrgkanis_fast_2015} established that if players of a multi-player, general-sum game use any algorithm from the family of Optimistic Mirror Descent (MD) or Optimistic Follow-the-Regularized-Leader (FTRL) algorithms (which are analogoues of the MD and FTRL algorithms, respectively, with recency bias), each player enjoys regret that is $O(T^{1/4})$. This was recently improved by~\cite{chen_hedging_2020} to $O(T^{1/6})$ in the special case of two-player games in which the players use \Opthedge, a particularly simple representative from both the Optimistic MD and Optimistic FTRL families.

The above results for general-sum games represent significant improvements over the $O(\sqrt{T})$ regret attainable by standard no-regret learners, but are not as dramatic as the logarithmic regret that has been shown attainable by no-regret learners, albeit more complex ones, in 2-player zero-sum games (e.g., \cite{daskalakis_near-optimal_2013}). {Indeed, despite extensive work on no-regret learning, understanding the optimal regret that can be guaranteed by no-regret learning algorithms in general-sum games has remained elusive. This question is especially intruiging in light of experiments suggesting that polylogarithmic regret should be attainable \cite{syrgkanis_fast_2015,hsieh_adaptive_2021}. %
}
In this paper we settle this question by showing that no-regret learners can guarantee polylogarithmic regret to each player in general-sum multi-player games. %
Moreover, this regret is attainable by a particularly simple algorithm -- Optimistic Hedge: %

\begin{table}
  \centering
  \caption{Overview of prior work on fast rates for learning in games. $m$ denotes the number of players, and $n$ denotes the number of actions per player (assumed to be the same for all players). %
    For \Opthedge, the adversarial regret bounds in the right-hand column are obtained via a choice of adaptive step-sizes. The $\tilde O(\cdot)$ notation hides factors that are polynomial in $\log T$.}
  \label{tab:prior-work}
  \begin{adjustbox}{center}
  \begin{tabular}{lccc}
    \toprule
    Algorithm & Setting & Regret in games & Adversarial regret \\
    \midrule
    \makecell[l]{Hedge   (\& many\\ other algs.)} & \makecell[c]{multi-player,\\ general-sum} & \makecell[c]{$O(\sqrt{T \log n})$   \cite{cesa2006prediction}} & \makecell[c]{$O(\sqrt{T \log n})$  \cite{cesa2006prediction}} \\ 
    \midrule 
    \makecell[l]{Excessive Gap \\ Technique } &\makecell[c]{ 2-player,\\ 0-sum} & \makecell[c]{$O(\log n(\log T + \log^{3/2} n))$ \\ \cite{daskalakis_near-optimal_2013}} & \makecell[c]{$O(\sqrt{T \log n})$ \\ \cite{daskalakis_near-optimal_2013}} \\
     \midrule
    \makecell[l]{ DS-OptMD, OptDA} & \makecell[c]{2-player, 0-sum} &  \makecell[c]{$\log^{O(1)} (n)$  \cite{hsieh_adaptive_2021}} & \makecell[c]{$\sqrt{T \log^{O(1)} (n)}$  \cite{hsieh_adaptive_2021}} \\
    \midrule
   \Opthedge & \makecell[c]{multi-player,\\ general-sum} 
               & \makecell[c]{$O(\log n \cdot \sqrt{m} \cdot T^{1/4})$ \\  \cite{rakhlin_optimization_2013,syrgkanis_fast_2015}}
              & \makecell[c]{$\tilde O(\sqrt{T \log n})$  \\  \cite{rakhlin_optimization_2013,syrgkanis_fast_2015}} \\
    \midrule
   \Opthedge & \makecell[c]{2-player,\\ general-sum} 
               & \makecell[c]{$O(\log^{5/6}n \cdot T^{1/6})$  \cite{chen_hedging_2020} }
              & \makecell[c]{$\tilde O(\sqrt{T \log n})$ } \\
    \midrule
   \Opthedge & \makecell[c]{multi-player,\\ general-sum} 
               & \makecell[c]{$O(\log n \cdot m \cdot \log^4 T)$ \\ {\bf (Theorem \ref{thm:polylog-main}) }}
              & \makecell[c]{$\tilde O(\sqrt{T \log n})$ \\ {\bf (Corollary \ref{cor:polylog-adv})}} \\    
    \bottomrule
  \end{tabular}
  \end{adjustbox}
\end{table}
\begin{theorem}[Abbreviated version of Theorem \ref{thm:polylog-main}] \label{thm:main}
  Suppose that $m$ players play a general-sum multi-player game, with a finite set of $n$ strategies per player, over $T$ rounds. Suppose also that each player uses Optimistic Hedge to update her strategy in every round, as a function of the history of play so far. Then each player experiences $O(m \cdot \log n \cdot \log^4 T)$
  regret. 
\end{theorem}
An immediate corollary of Theorem \ref{thm:main} is that the empirical distribution of play is a $O\left(\frac{m \log n \log^4 T}{T}\right)$-approximate coarse correlated equilibrium (CCE) of the game. 
We remark that Theorem \ref{thm:main} bounds the total regret experienced by {\em each player} of the multi-player game, which is the most standard regret objective for no-regret learning in games, and which is essential to achieve convergence to CCE. For the looser objective of the {\em average} of all players' regrets, \cite{rakhlin_optimization_2013} established  a $O(\log n)$ bound for \Opthedge in two-player zero-sum games, and \cite{syrgkanis_fast_2015} generalized  this bound, to $O(m \log n)$ in $m$-player general-sum games. Note that since some players may experience \emph{negative regret} \cite{hsieh_adaptive_2021}, the average of the players' regrets cannot be used in general to bound the maximum regret experienced by any individual player. %
Finally, we remark that several results in the literature posit no-regret learning as a model of agents' rational behavior; for instance, \cite{roughgarden_intrinsic_2009,syrgkanis_composable_2013,roughgarden_price_2017} show that no-regret learners in smooth games enjoy strong Price-of-Anarchy bounds. {By showing that \emph{each agent} can obtain very small regret in games by playing \Opthedge, Theorem \ref{thm:main} strengthens the plausability of the common assumption made in this literature that each agent will choose to use such a no-regret algorithm.}
  
\subsection{Related work}

\neurips{\vspace{-0.2cm}}
Table \ref{tab:prior-work} summarizes the prior works that aim to establish optimal regret bounds for no-regret learners in games. We remark that \cite{chen_hedging_2020} shows that the regret of Hedge %
is $\Omega(\sqrt{T})$ even in 2-player games where each player has 2 actions, meaning that optimism is necessary to obtain fast rates. 
 The table also includes a recent result of \cite{hsieh_adaptive_2021} showing that when the players in a 2-player zero-sum game with $n$ actions per player use a variant of \Opthedge with adaptive step size (a special case of their algorithms DS-OptMD and OptDA), each player has $\log^{O(1)} n$ regret. %
The techniques of \cite{hsieh_adaptive_2021} differ substantially from ours: the result in \cite{hsieh_adaptive_2021} is based on showing that the joint strategies $x\^t$ rapidly converge, pointwise, to a Nash equilibrium $x^\st$. %
Such a result seems very unlikely to extend to our setting of general-sum games, since finding an approximate Nash equilibrium even in 2-player games is PPAD-complete \cite{chen_settling_2009}. %
We also remark that the earlier work \cite{kangarshahi_honest_2018} shows that each player's regret is at most  $O(\log T \cdot \log n)$ when they use a certain algorithm based on Optimistic MD in 2-player zero-sum games; their technique is heavily tailored to 2-player zero-sum games, relying on the notion of duality in such a setting.


\cite{foster_learning_2016} shows that one can obtain fast rates in games for a broader class of algorithms (e.g., including Hedge) if one adopts a relaxed (approximate) notion of optimality. \cite{wei_more_2018} uses optimism to obtain adaptive regret bounds for bandit problems. Many recent papers (e.g., \cite{daskalakis_last-iterate_2019,golowich_tight_2020,lei_last_2021,hsieh_adaptive_2021,wei_linear_2021,azizian_last-iterate_2021}) have studied the \emph{last-iterate} convergence of algorithms from the Optimistic Mirror Descent family, which includes \Opthedge. Finally, a long line of papers (e.g., \cite{hart_uncoupled_2003,daskalakis_learning_2010,kleinberg_beyond_2011,balcan_weighted_2012,papadimitriou_nash_2016,bailey_multiplicative_2018,mertikopoulos_cycles_2018,bailey_fast_2019,cheung_vortices_2019,vlatakis_no-regret_2020}) has studied the dynamics of learning algorithms in games. Essentially all of these papers do not use optimism, and many of them show \emph{non-convergence} (e.g., divergence or recurrence) of the iterates of various learning algorithms such as FTRL and Mirror Descent when used in games.

\section{Preliminaries}
\label{sec:prelim}

\neurips{\vspace{-0.3cm}}
\paragraph{Notation.} For a positive integer $n$, let $[n] := \{ 1, 2, \ldots, n\}$. For a finite set $\MS$, let $\distrs{\MS}$ denote the space of distributions on $\MS$. For $\MS = [n]$, we will write $\Delta^n := \Delta(\MS)$ and interpret elements of $\Delta^n$ as vectors in $\BR^n$. For a vector $v \in \BR^n$ and $j \in [n]$, we denote the $j$th coordinate of $v$ as $v(j)$. For vectors $v, w \in \BR^n$, write $\lng v, w \rng = \sum_{j=1}^n v(j)w(j)$.   The base-2 logarithm of $x > 0$ is denoted $\log x$.

\neurips{\vspace{-0.3cm}}
\paragraph{No-regret learning in games.} We consider a game $G$ with $m \in \BN$ players, where player $i \in [m]$ has \emph{action space} $\MA_i$ with $n_i := |\MA_i|$ actions. We may assume that $\MA_i = [n_i]$ for each player $i$. The \emph{joint action space} is $\MA := \MA_1 \times \cdots \times \MA_m$. The specification of the game $G$ is completed by a collection of \emph{loss functions} $\ML_1, \ldots, \ML_m : \MA \ra [0,1]$. For an action profile $a = (a_1, \ldots, a_m) \in \MA$ and $i \in [m]$, $\ML_i(a)$ is the loss player $i$ experiences when each player $i' \in [m]$ plays $a_{i'}$. A \emph{mixed strategy} $x_i \in \Delta(\MA_i)$ for player $i$ is a distribution over $\MA_i$, with the probability of playing action $j \in \MA_i$ given by $x_i(j)$. Given a mixed strategy profile $x = (x_1, \ldots, x_m)$ (or an action profile $a = (a_1, \ldots, a_m)$) and a player $i \in [m]$  we let $x_{-i}$ (or $a_{-i}$, respectively) denote the profile after removing the $i$th mixed strategy $x_i$ (or the $i$th action $a_i$, respectively).

The $m$ players play the game $G$ for a total of $T$ rounds. At the beginning of each round $t \in [T]$, each player $i$ chooses a mixed strategy $x_i\^t \in \distrs{\MA_i}$. The \emph{loss vector} of player $i$, denoted $\ell_i\^t \in [0,1]^{n_i}$, is defined as $\ell_i\^t(j) = \E_{a_{-i} \sim x_{-i}\^t} [\ML_i(j,a_{-i})]$. As a matter of convention, set $\ell_i\^0 = \bbzero$ to be the all-zeros vector. %
We consider the \emph{full-information setting} in this paper, meaning that player $i$ observes its full loss vector $\ell_i\^t$ for each round $t$. Finally, player $i$ experiences a loss of $\lng \ell_i\^t, x_i\^t \rng$. The goal of each player $i$ is to minimize its \emph{regret}, defined as:
$ 
\Reg{i}{T} := \sum_{t \in [T]} \lng x_i\^t, \ell_i\^t \rng - \min_{j \in [n_i]} \sum_{t \in [T]} \ell_i\^t(j).
$

\neurips{\vspace{-0.3cm}}
\paragraph{Optimistic hedge.} The \Opthedge algorithm chooses mixed strategies for player $i \in [m]$ as follows: at time $t = 1$, it sets $x_i\^1 = (1/n_i, \ldots, 1/n_i)$ to be the uniform distribution on $\MA_i$. Then for all $t < T$, player $i$'s strategy at iteration $t+1$ is defined as follows, for $j \in [n_i]$:
\begin{align}
  \label{eq:opt-hedge}
x_i\^{t+1}(j) := \frac{x_i\^t(j) \cdot \exp(-\eta \cdot (2\ell_i\^t(j) - \ell_i\^{t-1}(j)))}{\sum_{k \in [n_i]} x_i\^t(k) \cdot \exp(-\eta \cdot (2 \ell_i\^t(k) - \ell_i\^{t-1}(k)))}.
\end{align}
\Opthedge is a modification of Hedge, which performs the updates $x_i\^{t+1}(j) := \frac{x_i\^t(j) \cdot \exp(-\eta \cdot \ell_i\^t(j))}{\sum_{k \in [n_i]} x_i\^t(k) \cdot \exp(-\eta \cdot \ell_i\^t(k))}$.
The update (\ref{eq:opt-hedge}) modifies the Hedge update by replacing the loss vector $\ell_i\^t$ with a predictor of the \emph{following iteration's} loss vector, $\ell_i\^t + (\ell_i\^t - \ell_i\^{t-1})$.
Hedge corresponds to FTRL with a negative entropy regularizer (see, e.g., \cite{bubeck_convex_2015}), whereas \Opthedge corresponds to \emph{Optimistic} FTRL with a negative entropy regularizer  \cite{rakhlin_optimization_2013,rakhlin_online_2013}. 

\neurips{\vspace{-0.3cm}}
\paragraph{Distributions \& divergences.} For distributions $P,Q$ on a finite domain $[n]$, the \emph{KL divergence} between $P,Q$ is $\kld{P}{Q} = \sum_{j =1}^n P(j) \cdot \log \left( \frac{P(j)}{Q(j)} \right)$. The \emph{chi-squared divergence} between $P,Q$ is $\chisq{P}{Q} = \sum_{j=1}^n Q(j) \cdot \left( \frac{P(j)}{Q(j)} \right)^2 - 1 = \sum_{j=1}^n \frac{(P(j) - Q(j))^2}{Q(j)}$. For a distribution $P$ on $[n]$ and a vector $v \in \BR^n$, we write
$
\Var{P}{v} := \sum_{j=1}^n P(j) \cdot \left( v(j) - \sum_{k=1}^n P(k) v(k) \right)^2.
$
Also define $\norm{P}{v} := \sqrt{\sum_{j=1}^n P(j) \cdot v(j)^2}$. If further $P$ has full support, then define $\normst{P}{v} = \sqrt{\sum_{j=1}^n \frac{v(j)^2}{P(j)}}$. The above notations will often be used when $P$ is the mixed strategy profile $x_i$ for some player $i$ and $v$ is a loss vector $\ell_i$; in such a case the norms $\norm{P}{v}$ and $\normst{P}{v}$ are often called \emph{local norms}.

\section{Results}
\label{sec:results}

\neurips{\vspace{-0.3cm}}
Below we state our main theorem, which shows that when all players in a game play according to \Opthedge with appropriate step size, they all experience polylogarithmic individual regrets.
\begin{theorem}[Formal version of Theorem \ref{thm:main}]
  \label{thm:polylog-main}
  There are constants $C, C' >1$ so that the following holds. Suppose a time horizon $T \in \BN$ and a game $G$ with $m$ players and $n_i$ actions for each player $i\in [m]$ is given. Suppose all players play according to \Opthedge with any positive step size $\eta \leq \frac{1}{C \cdot m \log^4 T}$. Then for any $i \in [m]$, the regret of player $i$ satisfies
  \begin{align}
\Reg{i}{T} \leq \frac{\log n_i}{\eta} + C' \cdot \log T \label{eq:reg-eta-ub}.
  \end{align}  
  In particular, if the players' step size is chosen as $\eta = \frac{1}{C \cdot m \log^4 T}$, then the regret of player $i$ satisfies
  \begin{align}
\Reg{i}{T} \leq O \left( m \cdot \log n_i \cdot \log^4 T \right).\label{eq:reg-eta-fix}
  \end{align}
\end{theorem}
A common goal in the literature on learning in games is to obtain an algorithm that achieves fast rates whan played by all players, and so that each player $i$ still obtains the optimal rate of $O(\sqrt{T})$ in the adversarial setting (i.e., when $i$ receives an arbitrary sequence of losses $\ell_i\^1, \ldots, \ell_i\^T$). We show in Corollary \ref{cor:polylog-adv} (in the appendix) that by running \Opthedge with an adaptive step size, this is possible. Table \ref{tab:prior-work} compares our regret bounds discussed in this section to those of prior work. 

\section{Proof overview}
\label{sec:proof-overview}

\neurips{\vspace{-0.3cm}}
In this section we overview the proof of Theorem \ref{thm:polylog-main}; the full proof may be found in the appendix. %
\neurips{\vspace{-0.2cm}}
\subsection{New adversarial regret bound}

\neurips{\vspace{-0.2cm}}
\label{sec:adv-reg-bound}
The first step in the proof of Theorem \ref{thm:polylog-main} is to prove a new regret bound (Lemma \ref{lem:omwu-local} below) for \Opthedge that holds for an adversarial sequence of losses. We will show in later sections that when \emph{all} players play according to \Opthedge, the right-hand side of the regret bound (\ref{eq:adv-var-bound}) is bounded by a quantity that grows only poly-logarithmically in $T$. %
\begin{lemma}
  \label{lem:omwu-local}
  There is a constant $C > 0$ so that the following holds. 
Suppose any player $i \in [m]$ follows the \Opthedge updates (\ref{eq:opt-hedge}) with step size $\eta < 1/C$, for an arbitrary sequence of losses $\ell_i\^1, \ldots, \ell_i\^T \in [0,1]^{n_i}$. Then %
\begin{align}
  \label{eq:adv-var-bound}
  \hspace{-0.7cm}
  \Reg{i}{T} \leq \frac{\log n_i}{\eta} + \sum_{t=1}^T \left(\frac{\eta}{2} + C \eta^2\right)  \Var{x_i\^t}{\ell_i\^t - \ell_i\^{t-1}} - \sum_{t=1}^T \frac{ (1-C\eta)\eta}{2} \cdot \Var{x_i\^{t}}{\ell_i\^{t-1}}.
\end{align}
\end{lemma}
The detailed proof of Lemma~\ref{lem:omwu-local} can be found in Section~\ref{sec:adv-regbnd-proofs}, but we sketch the main steps here. The starting point is a refinement of~\cite[Lemma 3]{rakhlin_online_2013} (stated as Lemma \ref{lem:omwu-localnorm}), which gives an upper bound for $\Reg{i}{T}$ in terms of local norms corresponding to each of the iterates $x_i\^t$ of \Opthedge. The bound involves the difference between the \Opthedge iterates $x_i\^t$ and iterates $\tilde x_i\^t$ defined by %
  $\tilde x_i\^t = \frac{x_i\^{t}(j) \cdot \exp(-\eta \cdot (\ell_i\^t (j) - \ell_i\^{t-1}(j)))}{\sum_{k \in [n_i]} x_i\^{t}(k) \cdot \exp(-\eta \cdot (\ell_i\^t (k) - \ell_i\^{t-1}(k)))}$: %
  \begin{align}
     \hspace{-0.8cm}
    \Reg{i}{T} \leq & \frac{\log n_i}{\eta} + \sum_{t=1}^T \normst{x_i\^t}{ x_i\^t - \tilde x_i\^t } \sqrt{\Var{x_i\^t}{\ell_i\^t - \ell_i\^{t-1}}} %
                                 - \frac{1}{\eta} \sum_{t=1}^T \kld{\tilde x_i\^t}{x_i\^t} - \frac{1}{\eta} \sum_{t=1}^T \kld{x_i\^t}{ \tilde x_i\^{t-1}} .\label{eq:rakhlin-refinement-mainbody}
  \end{align}  
  We next show (in Lemma \ref{lem:kl-div-lb}) that $\kld{\til x_i\^t}{x_i\^t}$ and $\kld{x_i\^t}{\til x_i\^{t-1}}$ may be lower bounded by $(1/2 - O(\eta)) \cdot \chisq{\til x_i\^t}{x_i\^t}$ and $(1/2 - O(\eta)) \cdot \chisq{x_i\^t}{\til x_i\^{t-1}}$, respectively. Note it is a standard fact that the KL divergence between two distributions is upper bounded by the chi-squared distribution between them; by contrast, %
  Lemma \ref{lem:kl-div-lb} can exploit that $x_i\^t$, $\til x_i\^t$ and $\til x_i\^{t-1}$ are close to each other to show a reverse inequality. Finally, exploiting the exponential weights-style functional relationship between $x_i\^t$ and $\til x_i\^{t-1}$, we show (in Lemma \ref{lem:chi2-variance}) that the $\chi^2$-divergence $\chisq{x_i\^t}{\til x_i\^{t-1}}$ may be lower bounded by $(1 - O(\eta)) \cdot \eta^2 \cdot \Var{x_i\^t}{\ell_i\^{t-1}}$, leading to the term $\frac{(1 - C\eta) \eta}{2} \Var{x_i\^t}{\ell_i\^{t-1}}$ being subtracted in (\ref{eq:adv-var-bound}). The $\chi^2$-divergence $\chisq{\til x_i\^t}{ x_i\^{t}}$, %
  as well as the term $\normst{x_i\^t}{x_i\^t - \til x_i\^t}$ in (\ref{eq:rakhlin-refinement-mainbody}) are bounded in a similar manner to obtain (\ref{eq:adv-var-bound}).

  \subsection{Finite differences}
  \label{sec:fds}

\neurips{  \vspace{-0.2cm}}
  Given Lemma \ref{lem:omwu-local}, in order to establish Theorem \ref{thm:polylog-main}, it suffices to show Lemma \ref{lem:bound-l-dl} below. Indeed, (\ref{eq:var-l-dl-main}) %
  below implies that the right-hand side of (\ref{eq:adv-var-bound}) is bounded above by $\frac{\log n_i}{\eta} + \eta \cdot O(\log^5 T)$, which is bounded above by %
  $O(m \log n_i \log^4 T)$ for the choice $\eta = \Theta \left( \frac{1}{m \cdot \log^4 T} \right)$ of Theorem \ref{thm:polylog-main}.\footnote{Notice that the factor $\frac 12$ in (\ref{eq:var-l-dl-main}) is not important for this argument -- any constant less than 1 would suffice.} 

\begin{lemma}[Abbreviated; detailed version in Section \ref{sec:polylog-main-completing-proof}]
  \label{lem:bound-l-dl}
  Suppose all players play according to \Opthedge with step size $\eta$ satifying $1/T \leq \eta \leq \frac{1}{C m \cdot \log^4 T}$ for a sufficiently large constant $C$. Then for any $i \in [m]$, the losses $\ell_i\^1, \ldots, \ell_i\^T \in \BR^{n_i}$ for player $i$ satisfy:
\begin{align}
  \label{eq:var-l-dl-main}
\sum_{t=1}^T \Var{x_i\^t}{\ell_i\^t - \ell_i\^{t-1}} \leq \frac{1}{2} \cdot \sum_{t=1}^T \Var{x_i\^t}{\ell_i\^{t-1}} + O \left( \log^5 T\right).
  \end{align}
\end{lemma}

The  definition below allows us to streamline our notation when proving Lemma \ref{lem:bound-l-dl}.
\begin{defn}[Finite differences]
  \label{def:fd}
  Suppose $L = (L\^1, \ldots, L\^T)$ is a sequence of vectors $L\^t\in \BR^n$. For integers $h \geq 0$, the \emph{order-$h$ finite difference sequence} for the sequence $L$, denoted by $\fd{h}{L}$, is the sequence $\fd{h}{L} := (\fds{h}{L}{1}, \ldots, \fds{h}{L}{T-h})$ defined recursively as: $\fds{0}{L}{t} := L\^t$ for all $1 \leq t \leq T$, and
  \begin{equation}
    \label{eq:fd-defn}
\fds{h}{L}{t} := \fds{h-1}{L}{t+1} - \fds{h-1}{L}{t}
\end{equation}
for all $h \geq 1$, $1 \leq t \leq T-h$.\footnote{We remark that while Definition \ref{def:fd} is stated for a 1-indexed sequence $L\^1, L\^2, \ldots$, we will also occasionally consider 0-indexed sequences $L\^0, L\^1, \ldots$, in which case the same recursive definition (\ref{eq:fd-defn}) holds for the finite differences $\fds{h}{L}{t}$, $t \geq 0$.} %
\end{defn}

\begin{remark}
  \label{rem:fds-alt}
Notice that another way of writing (\ref{eq:fd-defn}) is:
$ \fd{h}{L} = \fd{1}{\fd{h-1}{L}}.$
We also remark for later use that
$ \fds{h}{L}{t} = \sum_{s=0}^h {h \choose s} (-1)^{h-s} L\^{t+s}.$
\end{remark}
Let $H = \log T$, where $T$ denotes the fixed time horizon from Theorem \ref{thm:polylog-main} (and thus Lemma \ref{lem:bound-l-dl}). In the proof of Lemma \ref{lem:bound-l-dl}, we will bound the finite differences of order $h \leq H$ for certain sequences. %
The bound (\ref{eq:var-l-dl-main}) of Lemma \ref{lem:bound-l-dl} may be rephased as upper bounding $\sum_{t=1}^T \Var{x_i\^t}{\fds{1}{\ell_i}{t-1}}$, by $\frac 12 \sum_{t=1}^T \Var{x_i}{\ell_i\^{t-1}}$; to prove this, we proceed in two steps:
\begin{enumerate}[leftmargin=12pt]
\item \label{it:upwards-ind} (\emph{Upwards induction step}) First, in Lemma \ref{lem:dh-bound} below, we find an upper bound on $\left\| \fds{h}{\ell_i}{t} \right\|_\infty$ for all $t \in [T]$, $h \geq 0$, which decays exponentially in $h$ for $h \leq H$. This is done via \emph{upwards induction} on $h$, i.e., first proving the base case $h = 0$ using boundedness of the losses $\ell_i\^t$ and then $h = 1, 2, \ldots$ inductively. The main technical tool we develop for the inductive step is a weak form of the chain rule for finite differences, Lemma \ref{lem:fd-analytic}. The inductive step uses the fact that all players are following \Opthedge to relate the $h$th order finite differences of player $i$'s loss sequence $\ell_i\^t$ to the $h$th order finite differences of the strategy sequences $x_{i'}\^t$ for players $i' \neq i$; then we use the exponential-weights style updates of \Opthedge and Lemma \ref{lem:fd-analytic} to relate the $h$th order finite differences of the strategies $x_{i'}\^t$ to the $(h-1)$th order finite differences of the losses $\ell_{i'}\^t$.
\item \label{it:downwards-ind} (\emph{Downwards induction step}) We next show that for all $0 \leq h \leq  H$, $\sum_{t=1}^T \Var{x_i\^t}{\fds{h+1}{\ell_i}{t-1}}$ is bounded above by $c_h \cdot \sum_{t=1}^T\Var{x_i\^t}{\fds{h}{\ell_i}{t-1}} + \mu_h$, for some $c_h < 1/2$ and $\mu_h < O(\log^5 T)$.
  This shown via \emph{downwards induction} on $h$, namely first establishing the base case $h = H$ by using the result of item \ref{it:upwards-ind} for $h = H$ and then treating the cases $h = H-1, H-2, \ldots, 0$. The inductive step makes use of the discrete Fourier transform (DFT) to relate the finite differences of different orders (see Lemmas \ref{lem:d210} and \ref{lem:freq-cauchy}). In particular, Parseval's equality together with a standard relationship between the DFT of the finite differences of a sequence to the DFT of that sequence allow us to first prove the inductive step in the frequency domain and then transport it back to the original (time) domain.
\end{enumerate}
In the following subsections we explain in further detail how the two steps above are completed.

\subsection{Upwards induction proof overview}
\label{sec:upwards-ind}

\neurips{\vspace{-0.2cm}}
Addressing item \ref{it:upwards-ind} in the previous subsection, the  lemma below gives a bound on the supremum norm of the $h$-th order finite differences of each player's loss vector, when all players play according to \Opthedge and experience losses according to their loss functions $\ML_1, \ldots, \ML_m : \MA \ra [0,1]$. 

\begin{lemma}[Abbreviated]
  \label{lem:dh-bound}
  Fix a step size $\eta > 0$ satisfying $\eta \leq o \left( \frac{1}{m\log T} \right)$.
  If all players follow \Opthedge updates with step size $\eta$, then for any player $i \in [m]$, integer $h$ satisfying $0 \leq h \leq H$, and time step $t \in [T-h]$, it holds that
$
\| \fds{h}{\ell_i}{t} \|_\infty \leq O( m \eta) ^h \cdot h^{O(h)}.
$ 
\end{lemma}
A detailed version of Lemma \ref{lem:dh-bound}, together with its full proof, may be found in Section \ref{sec:dh-bound-proof}. We next give a proof overview of Lemma \ref{lem:dh-bound} for the case of 2 players, i.e., $m = 2$; we show in Section \ref{sec:dh-bound-proof} how to generalize this computation to general $m$. Below we introduce the main technical tool in the proof, a ``boundedness chain rule,'' and then outline how it is used to prove Lemma \ref{lem:dh-bound}.

\neurips{\vspace{-0.3cm}}
\paragraph{Main technical tool for Lemma \ref{lem:dh-bound}: boundedness chain rule.}
We say that a function $\phi : \BR^n \ra \BR$ is a \emph{softmax-type} function  if there are real numbers $\xi_1, \ldots, \xi_n$ and some $j \in [n]$ so that for all $(z_1, \ldots, z_n) \in \BR^n$,
$ 
\phi((z_1, \ldots, z_n)) = \frac{\exp(z_j)}{\sum_{k =1}^n \xi_k \cdot \exp(z_k)}.
$ 
Lemma \ref{lem:fd-analytic} below may be interpreted as a ``boundedness chain rule'' for finite differences. To explain the context for this lemma, recall that given an infinitely differentiable vector-valued function $L : \BR \ra \BR^n$ and an infinitely differentiable function $\phi : \BR^n \ra \BR$, the higher order derivatives of the function $\phi(L(t))$ may be computed in terms of those of $L$ and $\phi$ using the chain rule. Lemma \ref{lem:fd-analytic} considers an analogous setting where the input variable $t$ to $L$ is discrete-valued, taking values in $[T]$ (and so we identify the function $L$ with the sequence $L\^1, \ldots, L\^T$). In this case, the \emph{higher order finite differences} of the sequence $L\^1, \ldots, L\^T$ (Definition \ref{def:fd}) take the place of the higher order derivatives of $L$ with respect to $t$. Though there is no generic chain rule for finite differences, Lemma \ref{lem:fd-analytic} states that, at least when $\phi$ is a softmax-type function, %
we may \emph{bound} the higher order finite differences of the sequence $\phi(L\^1), \ldots, \phi(L\^T)$. In the lemma's statement we let $\phi \circ L$ denote the sequence $\phi(L\^1), \ldots, \phi(L\^T)$. 
\begin{lemma}[``Boundedness chain rule'' for finite differences; abbreviated]
  \label{lem:fd-analytic}
  Suppose that $h,n \in \BN$,  $\phi : \BR^n \ra \BR$ is a softmax-type function, and $L = (L\^1, \ldots, L\^T)$ %
  is a sequence of vectors in $\BR^n$ satisfying $\| L\^t \|_\infty \leq 1$ for $t \in [T]$. 
 Suppose for some $\alpha \in (0,1)$, for each $0 \leq h' \leq h$ and $t \in [T-h']$, it holds that $\| \fd{h'}{L}\^t \|_\infty \leq O( {\alpha^{h'}} ) \cdot (h')^{O(h')}$. %
 Then for all $t \in [T-h]$, 
  \begin{align*}
| \fds{h}{(\phi \circ L)}{t}|\leq O( \alpha^h) \cdot h^{O(h)}. %
  \end{align*}
\end{lemma}
A detailed version of Lemma \ref{lem:fd-analytic} may be found in Section \ref{sec:bcr-proof-2}. While Lemma \ref{lem:fd-analytic} requires $\phi$ to be a softmax-type function for simplicity (and this is the only type of function $\phi$ we will need to consider for the case $m = 2$) %
we remark that the detailed version of Lemma \ref{lem:fd-analytic} allows $\phi$ to be from a more general family of analytic functions whose higher order derivatives are appropriately bounded. The proof of Lemma \ref{lem:dh-bound} for all $m \geq 2$ requires that more general form of Lemma \ref{lem:fd-analytic}.

The proof of Lemma \ref{lem:fd-analytic} proceeds by considering the Taylor expansion $P_\phi(\cdot)$ of the function $\phi$ at the origin, which we write as follows: for $z = (z_1, \ldots, z_n) \in \BR^n$, $P_\phi(z) := \sum_{k \geq 0, \gamma \in \BZ_{\geq 0}^n : \ |\gamma| = k} a_\gamma z^\gamma$, where $a_\gamma \in \BR$, $|\gamma|$ denotes the quantity $\gamma_1 + \cdots + \gamma_n$ and $z^\gamma$ denotes $z_1^{\gamma_1} \cdots z_n^{\gamma_n}$. The fact that $\phi$ is a softmax-type function ensures that the radius of convergence of its Taylor series is at least 1, i.e., $\phi(z) = P_\phi(z)$ for any $z$ satisfying $\| z \|_\infty \leq 1$. By the assumption that $\| L\^t \|_\infty \leq 1$ for each $t$, we may therefore decompose $\fds{h}{(\phi \circ L)}{t}$ as:
\begin{align}
  \fds{h}{(\phi \circ L)}{t} = \sum_{k \geq 0, \gamma \in \BZ_{\geq 0}^n: \ |\gamma| = k} a_\gamma \cdot \fds{h}{L^\gamma}{t},\label{eq:phi-informal-decompose}
\end{align}
where $L^\gamma$ denotes the sequence of scalars $(L^\gamma)\^t := (L\^t)^\gamma$ for all $t$. 
The fact that $\phi$ is a softmax-type function allows us to establish strong bounds on $|a_\gamma|$ for each $\gamma$ in Lemma \ref{lem:softmax-ak-bound}. %
The proof of Lemma \ref{lem:softmax-ak-bound} bounds the $|a_\gamma|$ by exploiting the simple form of the derivative of a softmax-type function to decompose each $a_\gamma$ into a sum of $|\gamma|!$ terms. Then we establish a bijection between the terms of this decomposition and graph structures we refer to as \emph{factorial trees}; that bijection together with the use of an appropriate generating function allow us to complete the proof of Lemma \ref{lem:softmax-ak-bound}.

Thus, to prove Lemma \ref{lem:fd-analytic}, it suffices to bound $\left| \fds{h}{L^\gamma}{t} \right|$ for all $\gamma$. We do so by using Lemma \ref{lem:expand-pow-seq}. %
\begin{lemma}[Abbreviated; detailed vesion in Section \ref{sec:bcr-proof}]
  \label{lem:expand-pow-seq}
  Fix any $h \geq 0$, a multi-index $\gamma \in \BZ_{\geq 0}^n$ and set $k = |\gamma|$. For each of the $k^h$ functions $\pi : [h] \ra [k]$, and for each $r \in [k]$, there are integers $h'_{\pi,r} \in \{0, 1, \ldots, h\}$, $t'_{\pi,r} \geq 0$, and $j'_{\pi,r} \in [n]$, so that the following holds. For any sequence $L\^1, \ldots, L\^T \in \BR^n$ of vectors, it holds that, for each $t \in [T-h]$, %
  \begin{align}
\fds{h}{L^\gamma}{t} = \sum_{\pi : [h] \ra [k]} \prod_{r=1}^k \fds{h'_{\pi,r}}{(L(j'_{\pi,r}))}{t+t'_{\pi,r}}\label{eq:prod-expand-informal}.
  \end{align}
\end{lemma}
Lemma \ref{lem:expand-pow-seq} expresses the $h$th order finite differences of the sequence $L^\gamma$ as a sum of $k^h$ terms, each of which is a product of $k$ finite order differences of a sequence $L\^t(j'_{\pi,r})$ (i.e., the $j'_{\pi,r}$th coordinate of the vectors $L\^t$). Crucially, when using Lemma \ref{lem:expand-pow-seq} to  prove Lemma \ref{lem:fd-analytic}, the assumption of Lemma \ref{lem:fd-analytic} gives that for each $j' \in [n]$, each $h' \in [h]$, and each $t' \in [T-h']$, we have the bound $\left| \fds{h'}{L(j')}{t'} \right| \leq O ( {\alpha^{h'}}) \cdot (h')^{O(h')}$. %
These assumed bounds may be used to bound the right-hand side of (\ref{eq:prod-expand-informal}), which together with Lemma \ref{lem:expand-pow-seq} and (\ref{eq:phi-informal-decompose}) lets us complete the proof of Lemma \ref{lem:fd-analytic}. %

\neurips{\vspace{-0.3cm}}
\paragraph{Proving Lemma \ref{lem:dh-bound} using the boundedness chain rule.}
Next we discuss how Lemma \ref{lem:fd-analytic} is used to prove Lemma \ref{lem:dh-bound}, namely to bound $\| \fds{h}{\ell_i}{t} \|_\infty$ for each $t \in [T-h]$, $i \in [m]$, and $0 \leq h \leq H$. Lemma \ref{lem:dh-bound} is proved using induction, with the base case $h = 0$ being a straightforward consequence of the fact that $\| \fds{0}{\ell_i}{t} \|_\infty = \| \ell_i\^t \|_\infty \leq 1$ for all $i \in [m], t \in [T]$. For the rest of this section we focus on the inductive case, i.e., we pick some $h \in [H]$ and assume Lemma \ref{lem:dh-bound} holds for all $h' < h$. %

The first step is to reduce the claim %
of Lemma \ref{lem:dh-bound} to the claim that the upper bound $\|\fds{h}{x_i}{t} \|_1 \leq O \left( m \eta \right)^h \cdot h^{O(h)}$ holds for each $t \in [T-h], i \in [m]$. Recalling that we are only sketching here the case  $m=2$ for  simplicity, this reduction proceeds as follows: for $i \in \{1,2\}$, define the matrix $A_i \in \BR^{n_1 \times n_2}$ by $(A_i)_{a_1a_2}= \ML_i(a_1, a_2)$, for $a_1 \in [n_1], a_2 \in [n_2]$. We have assumed that all players are using \Opthedge and thus $\ell_i\^t = \E_{a_{i'} \sim x_{i'}\^t,\ \forall i' \neq i} [\ML_i(a_1, \ldots, a_n)]$; for our case here ($m=2$), this may be rewritten as $\ell_1\^t = A_1 x_2\^t$, $\ell_2\^t = A_2^\t x_1\^t$. Thus
\begin{align}
\| \fds{h}{\ell_1}{t} \|_\infty = \left\|A_1 \cdot \sum_{s=0}^h {h \choose s} (-1)^{h-s}  x_2\^{t+s} \right\|_\infty \leq \left\| \sum_{s=0}^h {h \choose s} (-1)^{h-s}  x_2\^{t+s} \right\|_1 = \| \fds{h}{x_2}{t} \|_1\nonumber,
\end{align}
where the first equality is from Remark \ref{rem:fds-alt} and the inequality follows since all entries of $A_1$ have absolute value $\le 1$. A similar computation allows us to show $\| \fds{h}{\ell_2}{t} \|_\infty \leq \| \fds{h}{x_1}{t} \|_1$.

To complete the inductive step it remains to upper bound the quantities $\| \fds{h}{x_i}{t} \|_1$ for $i \in [m], t \in [T-h]$. To do so, we note that the definition of the \Opthedge updates (\ref{eq:opt-hedge}) implies that for any $i \in [m], t \in [T], j \in [n_i]$, and $t' \geq 1$, we have %
\begin{align}
  \label{eq:ttp-extrapolate}
x_i\^{t+t'}(j) = \frac{x_i\^{t}(j) \cdot \exp\left( \eta \cdot \left( \ell_i\^{t-1}(j) - \sum_{s=0}^{t'-1} \ell_i\^{t+s}(j) - \ell_i\^{t+t'-1}(j)\right) \right)}{\sum_{k=1}^{n_i} x_i\^{t}(k) \cdot \exp\left( \eta \cdot \left( \ell_i\^{t-1}(k) - \sum_{s=0}^{t'-1} \ell_i\^{t+s}(k) - \ell_i\^{t+t'-1}(k)\right) \right)}.
\end{align}
For $t \in [T]$, $t' \geq 0$, set
$
\bar \ell_{i,t}\^{t'} := \eta \cdot \left( \ell_i\^{t-1} - \sum_{s=0}^{t'-1} \ell_i\^{t+s} - \ell_i\^{t+t'-1}\right).
$ %
Also, for each $i \in [m]$, $j \in [n_i]$, $t \in [T]$, and any vector $z = (z(1), \ldots, z(n_i)) \in \BR^{n_i}$ define $
\phi_{t,i,j}(z) := \frac{ x_i\^t(j) \cdot \exp\left(  z(j)\right)}{\sum_{k=1}^{n_i} x_i\^{t}(k) \cdot \exp\left( z(k)\right)}.$ %
Thus (\ref{eq:ttp-extrapolate}) gives that for $t' \geq 1$, $x_i\^{t+t'}(j) = \phi_{t,i,j}(\bar \ell_{i,t}\^{t'})$. Viewing $t$ as a fixed parameter and letting $t'$ vary, it follows that for $h \geq 0$ and $t' \geq 1$, $\fds{h}{x_i\^{t+\cdot}(j)}{t'} = \fds{h}{(\phi_{t,i,j} \circ \bar \ell_{i,t})}{t'}$. %

Recalling that our goal is to bound $|\fds{h}{x_i(j)}{t+1}|$ for each $t$, %
we can do so by using Lemma \ref{lem:fd-analytic} with $\phi = \phi_{t,i,j}$ and $\alpha = O(m \eta)$, if we can show that its precondition is met, i.e.~that $\| \fds{h'}{\bar \ell_{i,t}}{t'} \|_\infty \leq \frac{1}{B_1} \cdot \alpha^{h'} \cdot (h')^{B_0 h'}$ for all $h' \leq h$, the appropriate $\alpha$ and appropriate constants $B_0, B_1$. Helpfully, the definition of $\bar \ell_{i,t}\^{t'}$ as a partial sum allows us to relate the $h'$-th order finite differences of the sequence $\bar \ell_{i,t}\^{t'}$ to the $(h'-1)$-th order finite differences of the sequence $\ell_i\^t$ as follows:
\begin{equation}
  \label{eq:barl-l}
\fds{h'}{\bar \ell_{i,t}}{t'} = \eta \cdot \fds{h'-1}{\ell_i}{t+t'-1} -2\eta \cdot \fds{h'-1}{\ell_i}{t+t'}.
\end{equation}
Since $h'-1 < h$ for $h' \leq h$, the inductive assumption of Lemma \ref{lem:dh-bound} gives a bound on the $\ell_\infty$-norm of the terms on the right-hand side of (\ref{eq:barl-l}), which are sufficient for us to apply Lemma \ref{lem:fd-analytic}. Note that the inductive assumption gives an upper bound on $\| \fds{h'-1}{\ell_i}{t} \|_\infty$ that only scales with $\alpha^{h'-1}$, %
whereas Lemma \ref{lem:fd-analytic} requires scaling of $\alpha^{h'}$. This discrepancy is corrected by the factor of $\eta$ on the right-hand side of (\ref{eq:barl-l}), which gives the desired scaling $\alpha^{h'}$ (since $\eta < \alpha$ for the choice $\alpha = O(m\eta)$).

\subsection{Downwards induction proof overview}
\label{sec:downwards-ind}

\neurips{\vspace{-0.3cm}}
In this section we discuss in further detail item \ref{it:downwards-ind} in Section \ref{sec:fds}; in particular, we will show that there is a parameter $\mu = \tilde \Theta(\eta m)$ so that for all integers $h$ satisfying $H-1 \geq h \geq 0$,
  \begin{equation}
    \label{eq:fds-H-ind-informal}
\sum_{t=1}^{T-h-1} \Var{x_i\^t}{\fds{h+1}{\ell_i}{t}} \leq O(1/H) \cdot \sum_{t=1}^{T-h} \Var{x_i\^t}{\fds{h}{\ell_i}{t}} +  \tilde O \left( \mu^{2h} \right), %
\end{equation}
where $\tilde O$ hides factors polynomial in $\log T$. %
The validity of (\ref{eq:fds-H-ind-informal}) for $h = 0$ implies Lemma \ref{lem:bound-l-dl}. On the other hand, as long we choose the value $\mu$ in (\ref{eq:fds-H-ind-informal}) to satisfy $\mu \geq m \eta H^{\Omega(1)}$, %
then Lemma \ref{lem:dh-bound} implies that $\sum_{t=1}^{T-H} \Var{x_i\^t}{\fds{H}{\ell_i}{t}} \leq O(\mu^{2H})$. This gives that (\ref{eq:fds-H-ind-informal}) holds for $h = H-1$. To show that (\ref{eq:fds-H-ind-informal}) holds for all $H-1 > h \geq 0$, we use downwards induction; fix any $h$, and assume that (\ref{eq:fds-H-ind-informal}) has been shown for all $h'$ satisfying $h < h' \leq H-1$. Our main tool in the inductive step is to apply Lemma \ref{lem:d210} below. To state it, %
for $\zeta > 0,\ n \in \BN$, we say that a sequence of distributions $P\^1, \ldots, P\^T \in \Delta^n$ is \emph{$\zeta$-consecutively close} if for each $1 \leq t < T$, it holds that $\max \left\{\left\| \frac{P\^t}{P\^{t+1}}\right\|_\infty, \left\| \frac{P\^{t+1}}{P\^t}\right\|_\infty\right\} \leq 1 + \zeta$.\footnote{Here, for distributions $P,Q \in \Delta^n$, $\frac{P}{Q} \in \BR^n$ denotes the vector whose $j$th entry is $P(j) / Q(j)$.} Lemma \ref{lem:d210} shows that given a sequence of vectors for which the variances of its second-order finite differences are bounded by the variances of its first-order finite differences, a similar relationship holds between its first- and zeroth-order finite differences.
\begin{lemma}
  \label{lem:d210}
  There is a sufficiently large constant $C_0 > 1$ so that the following holds. For any $M, \zeta, \alpha > 0$ and $n \in \BN$, suppose that $P\^1, \ldots, P\^T \in \Delta^n$ and $Z\^1, \ldots, Z\^T \in [-M,M]^n$ satisfy the following conditions:
  \begin{enumerate}
  \item \label{it:prec-consec-close-body} The sequence $P\^1, \ldots, P\^T$ is $\zeta$-consecutively close for some $\zeta \in [1/(2T), \alpha^4/C_0]$. %
  \item \label{it:prec-vars-body} It holds that %
$ 
      \sum_{t=1}^{T-2} \Var{P\^t}{\fds{2}{Z}{t}} \leq \alpha \cdot \sum_{t=1}^{T-1} \Var{P\^t}{\fds{1}{Z}{t}} + \mu.
$ 
\end{enumerate}
Then\ \ 
$ 
\sum_{t=1}^{T-1} \Var{P\^t}{\fds{1}{Z}{t}} \leq \alpha \cdot (1+ \alpha) \sum_{t=1}^T \Var{P\^t}{Z\^t} + \frac{\mu}{\alpha} + \frac{C_0 M^2}{\alpha^3}.
$

\end{lemma}
Given Lemma \ref{lem:d210}, the inductive step for establishing (\ref{eq:fds-H-ind-informal}) is straightforward: we apply Lemma \ref{lem:d210} with $P\^t = x_i\^t$ and $Z\^t = \fds{h}{\ell_i}{t}$ for all $t$. The fact that $x_i\^t$ are updated with \Opthedge may be used to establish that precondition \ref{it:prec-consec-close-body} of Lemma \ref{lem:d210} holds. Since $\fds{1}{Z}{t} = \fds{h+1}{\ell_i}{t}$ and $\fds{2}{Z}{t} = \fds{h+2}{\ell_i}{t}$, that the inductive hypothesis (\ref{eq:fds-H-ind-informal}) holds for $h+1$ implies that precondition \ref{it:prec-vars-body} of Lemma \ref{lem:d210} holds for appropriate $\alpha, \mu > 0$. Thus Lemma \ref{lem:d210} implies that (\ref{eq:fds-H-ind-informal}) holds for the value $h$, which completes the inductive step.

\neurips{\vspace{-0.3cm}}
\paragraph{On the proof of Lemma \ref{lem:d210}.}
Finally we discuss the proof of Lemma \ref{lem:d210}. One technical challenge is the fact that the vectors $P\^t$ are not constant functions of $t$, but rather change slowly (as constrained by being $\zeta$-consecutively close). The main tool for dealing with this difficulty is Lemma \ref{lem:covvar-close}, which shows that for a $\zeta$-consecutively close sequence $P\^t$, for any vector $Z\^t$, $\frac{\Var{P\^t}{Z\^t}}{\Var{P\^{t+1}}{Z\^t}} \in [1-\zeta, 1+\zeta]$. This fact, together with some algebraic manipulations, lets us to reduce to the case that all $P\^t$ are equal. It is also relatively straightforward to reduce to the case that $\lng P\^t, Z\^t \rng = 0$ for all $t$, i.e., so that $\Var{P\^t}{Z\^t} = \norm{P\^t}{Z\^t}^2$. We may further separate $\norm{P\^t}{Z\^t}^2 = \sum_{j=1}^n P\^t(j) \cdot (Z\^t(j))^2$ into its individual components $P\^t(j) \cdot (Z\^t(j))^2$, and treat each one separately, thus allowing us to reduce to a one-dimensional problem. Finally, we make one further reduction, which is to replace the finite differences $\fd{h}{(\cdot)}$ in Lemma \ref{lem:d210} with \emph{circular finite differences}, defined below:
\begin{defn}[Circular finite difference]
  Suppose $L = (L\^0, \ldots, L\^{S-1})$ is a sequence of vectors $L\^t \in \BR^n$. For integers $h \geq 0$, the \emph{level-$h$ circular finite difference sequence} for the sequence $L$, denoted by $\fdc{h}{L}$, is the sequence defined recursively as: $\fdcs{0}{L}{t} = L\^t$ for all $0 \leq t < S$, and
  \begin{equation}
    \fdcs{h}{L}{t} = \begin{cases}
      \fdcs{h-1}{L}{t+1} - \fdcs{h-1}{L}{t} \quad : 0 \leq t \leq S-2 \\
      \fdcs{h-1}{L}{1} - \fdcs{h-1}{L}{T} \quad : t = S-1.
    \end{cases}
  \end{equation}
\end{defn}
Circular finite differences for a sequence $L\^0, \ldots, L\^{S-1}$ are defined similarly to finite differences (Definition \ref{def:fd}) except that unlike for finite differences, where $\fds{h}{L}{S-h}, \ldots, \fds{h}{L}{S-1}$ are not defined, $\fdcs{h}{L}{S-h}, \ldots, \fdcs{h}{L}{S-1}$ are defined by ``wrapping around'' back to the beginning of the sequence. The above-described reductions, which are worked out in detail in Section \ref{sec:d210-proof}, allow us to reduce proving Lemma \ref{lem:d210} to proving the following simpler lemma:
\begin{lemma}
  \label{lem:freq-cauchy}
  Suppose $\mu \in \BR$, $\alpha > 0$, and $W\^0, \ldots, W\^{S-1} \in \BR$ is a sequence of reals satisfying
  \begin{equation}
    \label{eq:d2d1}
\sum_{t=0}^{S-1} \left( \fdcs{2}{W}{t} \right)^2 \leq \alpha \cdot \sum_{t=0}^{S-1} \left( \fdcs{1}{W}{t} \right)^2 + \mu.
\end{equation}
Then\ \ 
$
\sum_{t=0}^{S-1} \left( \fdcs{1}{W}{t} \right)^2 \leq \alpha \cdot \sum_{t=1}^{S-1} (W\^t)^2 + \mu/\alpha.
$
\end{lemma}
To prove Lemma \ref{lem:freq-cauchy}, we apply the discrete Fourier transform to both sides of (\ref{eq:d2d1}) and use the Cauchy-Schwarz inequality in frequency domain. For a sequence $W\^0, \ldots, W\^{S-1} \in \BR$, its (discrete) \emph{Fourier transform} is the sequence $\wh{W}\^0, \ldots, \wh{W}\^{S-1}$ defined by $\wh{W}\^s = \sum_{t=0}^{S-1} W\^t \cdot e^{-\frac{2\pi i st}{S}}$. %
Below we prove Lemma \ref{lem:freq-cauchy} for the special case $\mu = 0$; we defer the general case to Section \ref{sec:d210-prelim}.
\begin{proof}[Proof of Lemma \ref{lem:freq-cauchy} for special case $\mu = 0$]
  We have the following:
  \begin{align}
  \hspace{-0.6cm}    \sum_{t=1}^T \left( \fdcs{1}{W}{t} \right)^2  = \sum_{s=1}^T \left| \widehat{\fdc{1}{W}}\^s \right|^2
    = \sum_{s=1}^T \left| \widehat{W}\^s  (e^{2\pi i s /T - 1}) \right|^2 \leq
    \sqrt{\sum_{s=1}^T \left| \widehat{W}\^s \right|^2}  \sqrt{\sum_{s=1}^T \left| \widehat{W}\^s \right|^2  \left| e^{2\pi i s/T} - 1\right|^4}\nonumber,
  \end{align}
  where the first equality uses Parseval's equality, the second uses Fact \ref{fac:fourier-circ} (in the appendix) for $h=1$, and the inequality uses Cauchy-Schwarz. By Parseval's inequality and Fact \ref{fac:fourier-circ} for $h=2$, the right-hand side of the above equals $\sqrt{ \sum_{t=1}^T (W\^t)^2} \cdot \sqrt{\sum_{t=1}^T \left( \fdcs{2}{W}{t}\right)^2}$, which, by assumption, is at most $\sqrt{ \sum_{t=1}^T (W\^t)^2} \cdot \sqrt{\alpha \cdot \sum_{t=1}^T \left( \fdcs{1}{W}{t} \right)^2 }$. Rearranging terms completes the proof. 
\end{proof}



\neurips{
\begin{ack}
Use unnumbered first level headings for the acknowledgments. All acknowledgments
go at the end of the paper before the list of references. Moreover, you are required to declare
funding (financial activities supporting the submitted work) and competing interests (related financial activities outside the submitted work).
More information about this disclosure can be found at: \url{https://neurips.cc/Conferences/2021/PaperInformation/FundingDisclosure}.

Do {\bf not} include this section in the anonymized submission, only in the final paper. You can use the \texttt{ack} environment provided in the style file to autmoatically hide this section in the anonymized submission.
\end{ack}
}


{
\neurips{  \small}
  \bibliographystyle{alpha}
  
