B(0,\varepsilon)}yu_{\varepsilon}(y)\mathrm{dy}=\nabla\psi(x_{k}^{\circ}).$

$\hfill\blacksquare$

##### Proof of Theorem 6.2 (Item 1).

Item 1 of Theorem 6.2 is a direct consequence of 6.3: we use
$\varphi:=\varphi_{\varepsilon}$ for any $\varepsilon\leqslant r_{\max}$, as
$r_{\max}>0$ for
$(\gamma,\beta)\in\mathrm{Int}(\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L}))$.
$\blacksquare$

###  6.2 Proof of Item 2 of Theorem 6.2

As for Item 2 of Theorem 6.2, it can be obtained from a scaling argument
provided by the following lemma.

###### Lemma 6.4

Let $0<\mu<L$, $K\geqslant 2$ and
$(\gamma,\beta)\in\mathrm{Int}(\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L}))$.
Let $\varphi\in\mathcal{F}^{\tau}_{\mu,L}$ be a function that cycles over
$\leavevmode\hbox to9.9pt{\vbox to9.9pt{\pgfpicture\makeatletter\hbox{\hskip
4.95244pt\lower-4.95244pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$ obtained by
Theorem 6.2. Define $\varphi_{\varepsilon}^{(\lambda)}$ as

$\varphi_{\varepsilon}^{(\lambda)}(x):=\lambda^{2}\varphi_{\varepsilon}\left(\frac{1}{\lambda}x\right).$

Then:

  1. 1.

$\varphi_{\varepsilon}^{(\lambda)}\in C^{\infty}$ and
$\varphi_{\varepsilon}^{(\lambda)}\in\mathcal{F}_{\mu,L}^{\tau/\lambda}$.

  2. 2.

$\eqref{eq:hb}_{\gamma,\beta}(\varphi_{\varepsilon}^{(\lambda)})$ cycles on
the scaled roots of unity cycle $\lambda\times\leavevmode\hbox to9.9pt{\vbox
to9.9pt{\pgfpicture\makeatletter\hbox{\hskip 4.95244pt\lower-4.95244pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$.

The function $\varphi_{\varepsilon}^{(\lambda)}$ is chosen such that the
gradients scale proportionally with $\lambda$, (as the cycle
$\lambda\times\leavevmode\hbox to9.9pt{\vbox
to9.9pt{\pgfpicture\makeatletter\hbox{\hskip 4.95244pt\lower-4.95244pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$), the Hessian is
un-scaled, and the third-order derivative scales with $1/\lambda$.
Proof. First, $\varphi_{\varepsilon}\in C^{\infty}$,
$\varphi_{\varepsilon}^{(\lambda)}\in C^{\infty}$. Second,
$\varphi_{\varepsilon}^{(\lambda)}\in\mathcal{F}_{\mu,L}$ as
$\nabla^{2}\varphi_{\varepsilon}^{(\lambda)}(x)=\nabla^{2}\varphi_{\varepsilon}\left(\frac{1}{\lambda}x\right)$
and $\varphi_{\varepsilon}\in\mathcal{F}_{\mu,L}$. Third, for any $r\geqslant
3$,
$\nabla^{r}\varphi_{\varepsilon}^{(\lambda)}(x)=\frac{1}{\lambda^{r-2}}\nabla^{r}\varphi_{\varepsilon}\left(\frac{1}{\lambda}x\right)$.

Furthermore,
$\nabla\varphi_{\varepsilon}^{(\lambda)}(x)=\lambda\nabla\varphi_{\varepsilon}\left(\frac{1}{\lambda}x\right)$,
hence $\nabla\varphi_{\varepsilon}^{(\lambda)}(\lambda
x)=\lambda\nabla\varphi_{\varepsilon}\left(x\right)$. Therefore,
(HB)$\,{}_{\gamma,\beta}\leavevmode\nobreak\
$$(\varphi_{\varepsilon}^{(\lambda)})$ cycles on $\lambda\leavevmode\hbox
to9.9pt{\vbox to9.9pt{\pgfpicture\makeatletter\hbox{\hskip
4.95244pt\lower-4.95244pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$. Indeed,
(HB)$\,{}_{\gamma,\beta}\leavevmode\nobreak\ $$(\varphi_{\varepsilon})$ cycles
on $\leavevmode\hbox to9.9pt{\vbox
to9.9pt{\pgfpicture\makeatletter\hbox{\hskip 4.95244pt\lower-4.95244pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$, i.e. $\forall
t\in\llbracket
0,K-1\rrbracket,x_{t+1}^{\circ}=x_{t}^{\circ}-\gamma\nabla\varphi_{\varepsilon}(x_{t}^{\circ})+\beta(x_{t}^{\circ}-x_{t-1}^{\circ})$.
Multiplying by $\lambda$, we get $\forall t\in\llbracket
0,K-1\rrbracket,\lambda x_{t+1}^{\circ}=\lambda
x_{t}^{\circ}-\gamma\lambda\nabla\varphi_{\varepsilon}(x_{t}^{\circ})+\beta(\lambda
x_{t}^{\circ}-\lambda x_{t-1}^{\circ})=\lambda
x_{t}^{\circ}-\gamma\nabla\varphi_{\varepsilon}^{(\lambda)}(\lambda
x_{t}^{\circ})+\beta(\lambda x_{t}^{\circ}-\lambda x_{t-1}^{\circ})$, that is
(HB)$\,{}_{\gamma,\beta}\leavevmode\nobreak\
$$(\varphi_{\varepsilon}^{(\lambda)})$ cycles on $\lambda\leavevmode\hbox
to9.9pt{\vbox to9.9pt{\pgfpicture\makeatletter\hbox{\hskip
4.95244pt\lower-4.95244pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$.
$\hfill\blacksquare$

##### Proof of Theorem 6.2 (Item 2).

It is a direct consequence of 6.4, by choosing $\lambda$ large enough, it
shows that for all $\tau>0$, $\eqref{eq:hb}_{\gamma,\beta}$ has a cycle on
$\mathcal{F}^{\tau}_{\mu,L}$. $\blacksquare$

###  6.3 Beyond third-order regularity

As a conclusion of this section, we showed that Hessian-Lipschitz continuity
does not help to obtain acceleration of (HB). It turns out that the arguments
work beyond third-order regularity, and that no Lipschitz argument on higher-
order derivative can help improving the situation.

In short, the arguments used for controlling the third-order derivative in
this section can be extended to impose any bound on higher-order derivatives
of the function. In particular, the scaling argument made in 6.4 enables to
arbitrarily reduce all derivatives of order higher than 2 of the
$\mathcal{C}^{\infty}$ function obtained in 6.3, whose derivatives are all
uniformly bounded. This extension is thus for free: we choose to focus on the
third-order derivative in this section for simplicity of exposition, but the
generalization follows naturally.

##  7 Concluding remarks

As a brief summary, this work provides a definitive and negative answer to the
question of obtaining accelerated convergence rate by using the heavy-ball
($\operatorname{HB}$) method on all smooth strongly convex functions beyond
quadratics. In other words, for smooth strongly convex minimization, the
complexity of $\operatorname{HB}$ is the same as the one of GD, up to at most
a constant $50/3\simeq 17$. Further, we show that this result is stable to
reasonable additional assumptions, including that of Lipschitz conditions on
the Hessian of the problem, or to functions in the set
$\mathcal{C}^{\infty}\cap\mathcal{F}_{\mu,L}$, and also robust to
perturbations to the initial conditions, as well as to parameter and gradient
noise.

Furthermore, we propose two constructive approaches, based on the construction
of cyclic trajectories, for disproving convergence of (stationary)
optimization methods. The first one consists in constructing a two-dimensional
cycles (namely _roots-of-unity cycles_), and the second one provides a linear
program for testing the existence of higher-dimensional cycles.

##### Future work and open questions.

There remain a few open questions related to the convergence of
$\operatorname{HB}$, or that are raised by our work. In particular, we
highlight the following points.

First, we now have an upper bound and a lower bound on (HB)’s convergence
rate, both in $1-\Theta(\kappa)$. However, those bounds do not match
perfectly, as they differ by a constant $\simeq 17$. The theoretical question
of the exact rate of $\eqref{eq:hb}$ thus remains open.

Second, our non-acceleration result of (HB) holds in any dimension larger than
or equal to 2, as our roots-of-unity cycles and counter examples construction
only hold in dimension 2 at least. The potential acceleration of (HB) in a
one-dimensional space is thus left open.

Lastly, although we proved that acceleration cannot be achieved by assuming
higher-order Lipschitz-type regularity, it remains an open question to see if
acceleration can be obtained (a) on another intermediary functional class
between $\mathcal{Q}_{\mu,L}$ and $\mathcal{F}_{\mu,L}$, (b) under additional
information on $f\in\mathcal{F}_{\mu,L}$ – such refined information should go
beyond the knowledge of $\mu$ and $L$ and could potentially be based on
adaptive tunings (e.g., based on online information) of the method.

##### Conjecture.

Finally, we mention the following open conjecture, echoing 4.15: for any
stationary first-order method, if there exists a cyclic trajectory, there
exists a roots-of-unity two-dimensional cycle on the function (3) (where $M$
depends on the stationary first-order method under consideration).

Proving such a conjecture only requires to show that the (Symmetric Cycle)
shape obtained in 4.11, can always be reduced to roots-of-unity cycles for any
first-order method, as this is the case numerically for $\operatorname{HB}$.
While open, this conjecture, if proven, constitutes a promising direction.
Indeed, a practical consequence of this conjecture is that testing existence
of a cyclic trajectory of a stationary algorithm would only require testing it
on the functions of the form (3), making the exploration of cyclical behavior
of stationary first-order algorithms straightforward.

##### Acknowledgements.

The authors thank Margaux Zaffran for her feedback and her insights on the
plots. A. Taylor acknowledges support from the European Research Council
(grant SEQUOIA 724063). This work was partly funded by the French government
under management of Agence Nationale de la Recherche as part of the
“Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA
Institute). The work of B. Goujaud and A. Dieuleveut is partly supported by
ANR-19-CHIA-0002-01/chaire SCAI, and Hi!Paris FLAG project.

## References

  * Berthier et al. [2020] Raphaël Berthier, Francis Bach, and Pierre Gaillard.  Accelerated gossip in networks of given dimension using Jacobi polynomial iterations.  _SIAM Journal on Mathematics of Data Science_ , 2(1):24–47, 2020.
  * Bottou and Bousquet [2007] Léon Bottou and Olivier Bousquet.  The tradeoffs of large scale learning.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2007\.
  * Brézis [2011] Haim Brézis.  _Functional analysis, Sobolev spaces and partial differential equations_ , volume 2.  Springer, 2011.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Found. and Trends in Machine Learning_ , 8(3-4):231–357, 2015.
  * Dobson et al. [2023] Paul Dobson, Jesus Maria Sanz-Serna, and Konstantinos Zygalakis.  On the connections between optimization algorithms, lyapunov functions, and differential equations: theory and insights.  _arXiv preprint arXiv:2305.08658_ , 2023.
  * Drori and Taylor [2022] Yoel Drori and Adrien Taylor.  On the oracle complexity of smooth strongly convex minimization.  _Journal of Complexity_ , 68:101590, 2022.
  * Drori and Teboulle [2014] Yoel Drori and Marc Teboulle.  Performance of first-order methods for smooth convex minimization: a novel approach.  _Math. Programming_ , 145(1):451–482, 2014.
  * d’Aspremont et al. [2021] Alexandre d’Aspremont, Damien Scieur, and Adrien Taylor.  Acceleration methods.  _Found. and Trends in Optimization_ , 5(1-2), 2021.
  * Fischer [2011] Bernd Fischer.  _Polynomial based iteration methods for symmetric linear systems_.  SIAM, 2011.
  * Ghadimi et al. [2015] Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson.  Global convergence of the heavy-ball method for convex optimization.  In _European control conference (ECC)_ , 2015.
  * Goujaud et al. [2022a] Baptiste Goujaud, Céline Moucer, François Glineur, Julien Hendrickx, Adrien Taylor, and Aymeric Dieuleveut.  PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python.  _preprint arXiv:2201.04040_ , 2022a.
  * Goujaud et al. [2022b] Baptiste Goujaud, Damien Scieur, Aymeric Dieuleveut, Adrien B Taylor, and Fabian Pedregosa.  Super-acceleration with cyclical step-sizes.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2022b.
  * Goujaud et al. [2022c] Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut.  Optimal first-order methods for convex functions with a quadratic upper bound.  _arXiv preprint arXiv:2205.15033_ , 2022c.
  * Goujaud et al. [2022d] Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut.  Quadratic minimization: from conjugate gradient to an adaptive heavy-ball method with Polyak step-sizes.  _arXiv preprint arXiv:2210.06367_ , 2022d.
  * Goujaud et al. [2023] Baptiste Goujaud, Aymeric Dieuleveut, and Adrien Taylor.  Counter-examples in first-order optimization: a constructive approach.  _IEEE Control Systems Letters_ , 2023.  (See arXiv 2303 10503 for complete version with appendices).
  * Gray [2006] Robert M. Gray.  Toeplitz and circulant matrices: A review.  _Foundations and Trends® in Communications and Information Theory_ , 2(3):155–239, 2006.  Original publication 1971.
  * Gupta et al. [2021] Chirag Gupta, Sivaraman Balakrishnan, and Aaditya Ramdas.  Path length bounds for gradient descent and flow.  _The Journal of Machine Learning Research_ , 22(1):3154–3216, 2021.
  * Hagedorn and Jarre [2023] Melinda Hagedorn and Florian Jarre.  Iteration complexity of fixed-step methods by nesterov and polyak for convex quadratic functions.  _Journal of Optimization Theory and Applications_ , pages 1–19, 2023\.
  * Kim et al. [2022] Junhyung Lyle Kim, Gauthier Gidel, Anastasios Kyrillidis, and Fabian Pedregosa.  Extragradient with positive momentum is optimal for games with cross-shaped jacobian spectrum.  _arXiv preprint arXiv:2211.04659_ , 2022.
  * Lessard et al. [2016] Laurent Lessard, Benjamin Recht, and Andrew Packard.  Analysis and design of optimization algorithms via integral quadratic constraints.  _SIAM Journal on Optimization_ , 26(1):57–95, 2016.
  * MOSEK [2019] ApS MOSEK.  _MOSEK Optimizer API for C 9.3.6_ , 2019.  URL https://docs.mosek.com/latest/capi/index.html.
  * Nemirovskii [1994] Arkadi S. Nemirovskii.  Information-based complexity of convex programming.  Lecture notes (link), 1994.
  * Nemirovskii and Nesterov [1985] Arkadi S. Nemirovskii and Yurii Nesterov.  Optimal methods of smooth convex minimization.  _USSR Computational Mathematics and Mathematical Physics_ , 25(2):21–30, 1985.
  * Nesterov [1983] Yurii Nesterov.  A method of solving a convex programming problem with convergence rate ${O}(1/k^{2})$.  _Soviet Mathematics Doklady_ , 27(2):372–376, 1983.
  * Nesterov [2003] Yurii Nesterov.  _Introductory Lectures on Convex Optimization_.  Springer, 2003.
  * Pedregosa and Scieur [2020] Fabian Pedregosa and Damien Scieur.  Acceleration through spectral density estimation.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Polyak [1964] Boris T. Polyak.  Some methods of speeding up the convergence of iteration methods.  _USSR computational mathematics and mathematical physics_ , 1964\.
  * Polyak [1987] Boris T. Polyak.  _Introduction to optimization_.  Optimization Software New York, 1987.
  * Rockafellar [1997] R Tyrrell Rockafellar.  _Convex analysis_ , volume 11.  Princeton university press, 1997.
  * Taylor and Drori [2023] Adrien Taylor and Yoel Drori.  An optimal gradient method for smooth strongly convex minimization.  _Mathematical Programming_ , 199(1-2):557–594, 2023.
  * Taylor et al. [2018] Adrien Taylor, Bryan Van Scoy, and Laurent Lessard.  Lyapunov functions for first-order methods: Tight automated convergence guarantees.  In _International Conference on Machine Learning (ICML)_ , 2018.
  * Taylor et al. [2017a] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur.  Exact worst-case performance of first-order methods for composite convex optimization.  _SIAM Journal on Optimization_ , 27(3):1283–1313, 2017a.
  * Taylor et al. [2017b] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur.  Performance estimation toolbox (PESTO): automated worst-case analysis of first-order optimization methods.  In _56th Annual Conference on Decision and Control (CDC)_ , pages 1278–1283, 2017b.
  * Taylor et al. [2017c] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur.  Smooth strongly convex interpolation and exact worst-case performance of first-order methods.  _Math. Programming_ , 161(1-2):307–345, 2017c.
  * Van Scoy et al. [2017] Bryan Van Scoy, Randy A Freeman, and Kevin M Lynch.  The fastest known globally convergent first-order method for minimizing strongly convex functions.  _IEEE Control Systems Letters_ , 2(1):49–54, 2017\.
  * Vandenberghe and Boyd [1996] Lieven Vandenberghe and Stephen Boyd.  Semidefinite programming.  _SIAM review_ , 38(1):49–95, 1996.
  * Wang et al. [2022] Jun-Kun Wang, Chi-Heng Lin, Andre Wibisono, and Bin Hu.  Provable acceleration of heavy ball beyond quadratics for a class of Oolyak-Lojasiewicz functions when the non-convexity is averaged-out.  In _International Conference on Machine Learning (ICML)_ , 2022.

Appendix

This appendix is organized in six sections: Appendix A to E respectively
contain complementary proof results to Section 2 to 6, and Appendix F a
summary table of convergence rates on $\mathcal{Q}_{\mu,L}$ and
$\mathcal{F}_{\mu,L}$ for several first-order methods of interest.

######

  1. 1 Introduction
  2. 2 Preliminary results on heavy-ball
  3. 3 Non-acceleration of heavy-ball on $\mathcal{F}_{\mu,L}$ via simple two-dimensional cycles
  4. 4 General study of cycles for stationary first-order methods
  5. 5 Robustness of the roots-of-unity cycle
  6. 6 No acceleration of (HB) under higher-order regularity assumptions
  7. 7 Concluding remarks
  8. A Auxiliary proofs from Section 2: Proof of 2.1
  9. B Auxiliary proofs from Section 3
  10. C Auxiliary proofs from Section 4: Proof of 4.12
  11. D Auxiliary proofs from Section 5
  12. E Auxiliary proofs from Section 6
  13. F A summary of convergence rates on $\mathcal{F}_{\mu,L}$ and $\mathcal{Q}_{\mu,L}$

##  Appendix A Auxiliary proofs from Section 2: Proof of 2.1

In this section, we give a complete proof of the asymptotic convergence rate
of (HB) on sets of quadratic functions.

See 2.1

Since, this recursion is of second-order, a classical and convenient trick is
to consider the variable
$X_{t}\leavevmode\nobreak\ :=\leavevmode\nobreak\
\begin{pmatrix}x_{t}-x_{\star}\\\
x_{t-1}-x_{\star}\end{pmatrix}\leavevmode\nobreak\ \in\leavevmode\nobreak\
\left(\mathbb{R}^{d}\right)^{2}$. It follows the simplified recursion

$X_{t+1}=\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma H&-\beta\mathrm{I}\\\
\mathrm{I}&0\end{pmatrix}X_{t},$ (10)

that can be enrolled to obtain

$X_{T}=\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma H&-\beta\mathrm{I}\\\
\mathrm{I}&0\end{pmatrix}^{T}X_{0},$

hence the result

$\|x_{t}-x_{\star}\|\leqslant\|X_{t}\|\leqslant\left\|\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma
H&-\beta\mathrm{I}\\\
\mathrm{I}&0\end{pmatrix}^{T}\right\|_{\mathrm{op}}\|X_{0}\|.$

Finally,

$\|x_{t}-x_{\star}\|^{1/T}\leqslant\left\|\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma
H&-\beta\mathrm{I}\\\
\mathrm{I}&0\end{pmatrix}^{T}\right\|_{\mathrm{op}}^{1/T}\|X_{0}\|^{1/T}\underset{T\rightarrow\infty}{\longrightarrow}\rho\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma
H&-\beta\mathrm{I}\\\ \mathrm{I}&0\end{pmatrix}$

where $\rho$ here denotes the spectral radius of the matrix, i.e. the largest
complex module of its eigenvalues. Since $H$ is diagonalizable (as self-
adjoint operator, or symmetric matrix), we can block-diagonalize the previous
matrix as

$\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma H&-\beta\mathrm{I}\\\
\mathrm{I}&0\end{pmatrix}\sim\left(\begin{pmatrix}1+\beta-\gamma\lambda&-\beta\\\
1&0\end{pmatrix}_{\lambda\in\mathrm{Sp}(H)}\right),$

and then the worst-case asymptotic convergence rate is upper bounded by

$\rho\begin{pmatrix}(1+\beta)\mathrm{I}-\gamma H&-\beta\mathrm{I}\\\
\mathrm{I}&0\end{pmatrix}=\max_{\lambda\in[\mu,L]}\rho\begin{pmatrix}1+\beta-\gamma\lambda&-\beta\\\
1&0\end{pmatrix}.$

The first thing to notice is that the determinant of
$\begin{pmatrix}1+\beta-\gamma\lambda&-\beta\\\ 1&0\end{pmatrix}$ is $\beta$.
Therefore, when $\beta\geqslant 1$, at least one eigenvalue has a module
larger than or equal to 1 and (HB) provably diverges on some function of
$\mathcal{Q}_{\mu,L}$. Then, from now, we only consider $\beta\in(-1,1)$.

Note that, when $\beta=0$, we recover (GD) and its convergence rate
$\max_{\lambda\in[\mu,L]}|1-\gamma\lambda|$. As for (GD), (HB)’s asymptotic
convergence rate is given by the extreme eigenvalue $\mu$ or $L$, depending on
the value of $\tilde{\gamma}:=\tfrac{\gamma}{1+\beta}$. Indeed,

  * •

when $\tilde{\gamma}=\tfrac{\gamma}{1+\beta}\leqslant\frac{2}{L+\mu}$, then
$\max_{\lambda\in[\mu,L]}\rho\begin{pmatrix}1+\beta-\gamma\lambda&-\beta\\\
1&0\end{pmatrix}=\rho\begin{pmatrix}1+\beta-\gamma\mu&-\beta\\\
1&0\end{pmatrix}$,

  * •

and when $\tilde{\gamma}=\tfrac{\gamma}{1+\beta}\geqslant\frac{2}{L+\mu}$,
then
$\max_{\lambda\in[\mu,L]}\rho\begin{pmatrix}1+\beta-\gamma\lambda&-\beta\\\
1&0\end{pmatrix}=\rho\begin{pmatrix}1+\beta-\gamma L&-\beta\\\
1&0\end{pmatrix}$.

Moreover, when $\tilde{\gamma}=\tfrac{\gamma}{1+\beta}\geqslant\frac{2}{L}$,
then $\rho\begin{pmatrix}1+\beta-\gamma L&-\beta\\\ 1&0\end{pmatrix}\geqslant
1$, which cannot guarantee convergence.

Table 2: Classification of (HB)’s behavior in three regions, see Figure 1 for a graphical description. Region’s name | Range of $\gamma$’s values | Asymptotic convergence rate
---|---|---
Lazy region | $0<\gamma\leqslant\min\left(\frac{2(1+\beta)}{L+\mu},\frac{\left(1-\sqrt{\beta}\right)^{2}}{\mu}\right)$ | $\frac{1+\beta-\mu\gamma}{2}+\sqrt{\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}-\beta}$
Robust region | $\frac{\left(1-\sqrt{\beta}\right)^{2}}{\mu}\leqslant\gamma\leqslant\frac{\left(1+\sqrt{\beta}\right)^{2}}{L}$ | $\sqrt{\beta}$
Knife’s edge | $\max\left(\frac{2(1+\beta)}{L+\mu},\frac{\left(1+\sqrt{\beta}\right)^{2}}{L}\right)\leqslant\gamma<\frac{2(1+\beta)}{L}$ | $\frac{L\gamma-(1+\beta)}{2}+\sqrt{\left(\frac{L\gamma-(1+\beta)}{2}\right)^{2}-\beta}$

###### Remark A.1

This proof is based on linear algebra, relying on writing the system as (10).
Another classical approach to the analysis of (HB) on $\mathcal{Q}_{\mu,L}$
consists in exploiting links between first-order methods and polynomials (see
e.g. [9, 22] or [Chapter 2 of 8] for a recent introduction.

##  Appendix B Auxiliary proofs from Section 3

###  B.1 Proof of Theorem 3.5

See 3.5

Proof. Let $(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})$. First
we prove the expression of
$\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$. Then we
will prove that for all
$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$,
(HB)$\,{}_{\gamma,\beta}(\psi)$ cycles.

##### Expression of
$\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$:

We have
$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$

$\displaystyle\overset{(\text{\lx@cref{creftypecap~refnum}{lem:gt_def}})}{\Longleftrightarrow}$
$\displaystyle\exists f\in\mathcal{F}_{\mu,L}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall t\in\llbracket 0,K-1\rrbracket,\nabla
f(x_{t}^{\circ})=\frac{(1+\beta)I_{2}-R-\beta R^{-1}}{\gamma}x_{t}^{\circ},$
$\displaystyle\overset{\left(\bar{f}(x):=\frac{f(x)-\tfrac{\mu}{2}\|x\|^{2}}{L-\mu}\right)}{\Longleftrightarrow}$
$\displaystyle\exists\bar{f}\in\mathcal{F}_{0,1}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall t\in\llbracket
0,K-1\rrbracket,\nabla\bar{f}(x_{t}^{\circ})=\frac{(1+\beta-\mu\gamma)I_{2}-R-\beta
R^{-1}}{(L-\mu)\gamma}x_{t}^{\circ},$ $\displaystyle\overset{(\text{By
definition of }M)}{\Longleftrightarrow}$
$\displaystyle\exists\bar{f}\in\mathcal{F}_{0,1}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall t\in\llbracket
0,K-1\rrbracket,\nabla\bar{f}(x_{t}^{\circ})=Mx_{t}^{\circ},$
$\displaystyle\overset{\begin{subarray}{c}\text{(By properties of the Fenchel
transform}\\\
\text{\cite[citep]{[\@@bibref{Number}{rockafellar1997convex}{}{}, Theorem
23.5]}})\end{subarray}}{\Longleftrightarrow}$
$\displaystyle\exists\bar{f}^{*}\in\mathcal{F}_{1,\infty}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall t\in\llbracket
0,K-1\rrbracket,\nabla\bar{f}^{*}(Mx_{t}^{\circ})=x_{t}^{\circ},$
$\displaystyle\overset{\left(\hat{f}(x)=\bar{f}^{*}(x)-\tfrac{1}{2}\|x\|^{2}\right)}{\Longleftrightarrow}$
$\displaystyle\exists\hat{f}\in\mathcal{F}_{0,\infty}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall t\in\llbracket
0,K-1\rrbracket,\nabla\hat{f}(Mx_{t}^{\circ})=(I-M)x_{t}^{\circ}.$

Applying the interpolation theorem [34, theorem 1], the latest assertion is
equivalent to

$\exists(\hat{f}_{t})_{t\in\llbracket 0,K-1\rrbracket}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall i\neq j\in\llbracket
0,K-1\rrbracket,\hat{f}_{i}\geqslant\hat{f}_{j}+\left<(I-M)x_{j}^{\circ},M(x_{i}^{\circ}-x_{j}^{\circ})\right>.$

Note the inner product
$\left<(I-M)x_{j}^{\circ},M(x_{i}^{\circ}-x_{j}^{\circ})\right>$ is also equal
to $\left<(I-M)x_{0}^{\circ},M(x_{i-j}^{\circ}-x_{0}^{\circ})\right>$. Hence
we can conclude
$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$

$\displaystyle\Longleftrightarrow$
$\displaystyle\exists(\hat{f}_{t})_{t\in\llbracket
0,K-1\rrbracket}\leavevmode\nobreak\ |\leavevmode\nobreak\ \forall i\neq
j\in\llbracket
0,K-1\rrbracket,\hat{f}_{i}\geqslant\hat{f}_{j}+\left<(I-M)x_{0}^{\circ},M(x_{i-j}^{\circ}-x_{0}^{\circ})\right>,$
$\displaystyle\Longleftrightarrow$
$\displaystyle\exists(\hat{f}_{t})_{t\in\llbracket
0,K-1\rrbracket}\leavevmode\nobreak\ |\leavevmode\nobreak\ \forall
j\in\llbracket 0,K-1\rrbracket,\forall\Delta\in\llbracket
1,K-1\rrbracket,\hat{f}_{j+\Delta}\geqslant\hat{f}_{j}+\left<(I-M)x_{0}^{\circ},M(x_{\Delta}^{\circ}-x_{0}^{\circ})\right>.$

Summing up the latest over $j$ implies $\forall\Delta\in\llbracket
1,K-1\rrbracket,0\geqslant\left<(I-M)x_{0}^{\circ},M(x_{\Delta}^{\circ}-x_{0}^{\circ})\right>.$

Reciprocally, this assertion implies the previous one with $\hat{f}_{t}=0$ for
all $t$. Hence555Note that this result might be surprising (no function value
appears) to the readers familiar with _cyclic monotonicity_ (see, e.g., [29]).
In our case, function values naturally disappear as we can arbitrarily set
them to zero, which is different than simply not taking function values into
account (see, e.g., discussion in [34, Remark 1]).,

$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})\Longleftrightarrow\forall\Delta\in\llbracket
1,K-1\rrbracket,\left<M^{T}(I-M)x_{0}^{\circ},x_{\Delta}^{\circ}-x_{0}^{\circ}\right>\leqslant
0.$ (12)

This can be written

$\displaystyle\left(\frac{1+\beta-\gamma\mu-(1+\beta)\cos{\theta_{K}}}{(L-\mu)\gamma}-\left(\frac{1+\beta-\gamma\mu-(1+\beta)\cos{\theta_{K}}}{(L-\mu)\gamma}\right)^{2}-\left(\frac{(1-\beta)\sin{\theta_{K}}}{(L-\mu)\gamma}\right)^{2}\right)\left(\cos{\Delta\theta_{K}}-1\right)$
$\displaystyle+\frac{(1-\beta)\sin{\theta_{K}}}{(L-\mu)\gamma}\sin{\Delta\theta_{K}}\leqslant
0,$

or dividing by $1-\cos{\Delta\theta_{K}}$,

$\displaystyle-\left(\frac{1+\beta-\gamma\mu-(1+\beta)\cos{\theta_{K}}}{(L-\mu)\gamma}-\left(\frac{1+\beta-\gamma\mu-(1+\beta)\cos{\theta_{K}}}{(L-\mu)\gamma}\right)^{2}-\left(\frac{(1-\beta)\sin{\theta_{K}}}{(L-\mu)\gamma}\right)^{2}\right)$
$\displaystyle+\frac{(1-\beta)\sin{\theta_{K}}}{(L-\mu)\gamma}\frac{\sin{\Delta\theta_{K}}}{1-\cos{\Delta\theta_{K}}}\leqslant
0.$

This inequality must hold for any $\Delta\in\llbracket 1,K-1\rrbracket$ and
the LHS expression is maximized for $\Delta=1$. We conclude

$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})\Longleftrightarrow\left<M^{T}(I-M)x_{0}^{\circ},x_{1}^{\circ}-x_{0}^{\circ}\right>\leqslant
0.$

Or equivalently,
$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$
if and only if

$\displaystyle\left(\frac{1+\beta-\gamma\mu-(1+\beta)\cos{\theta_{K}}}{(L-\mu)\gamma}-\left(\frac{1+\beta-\gamma\mu-(1+\beta)\cos{\theta_{K}}}{(L-\mu)\gamma}\right)^{2}-\left(\frac{(1-\beta)\sin{\theta_{K}}}{(L-\mu)\gamma}\right)^{2}\right)\left(\cos{\theta_{K}}-1\right)$
$\displaystyle+\frac{(1-\beta)\sin{\theta_{K}}}{(L-\mu)\gamma}\sin{\theta_{K}}\leqslant
0.$

After multiplying the above inequality by
$\kappa\tfrac{((L-\mu)\gamma)^{2}}{1-\cos\theta_{K}}$ and rearranging the
terms, we obtain equivalence with

$(\mu\gamma)^{2}-2\left[\beta-\cos\theta_{K}+\kappa(1-\beta\cos\theta_{K})\right](\mu\gamma)+2\kappa(1-\cos\theta_{K})(1+\beta^{2}-2\beta\cos\theta_{K})\leqslant
0.$

##### Cycle on $\psi$:

Recall the function $\psi$ is defined as

$\psi:x\mapsto\frac{L}{2}\|x\|^{2}-\frac{L-\mu}{2}d(x,\operatorname*{{convh}}\left\\{Mx_{t},t\in\llbracket
0,K-1\rrbracket\right\\})^{2}.$

We define $\bar{\psi}$ as

$\bar{\psi}:x\mapsto\frac{\psi(x)-\frac{\mu}{2}\|x\|^{2}}{L-\mu}=\frac{1}{2}\|x\|^{2}-\frac{1}{2}d(x,\operatorname*{{convh}}\left\\{Mx_{t},t\in\llbracket
0,K-1\rrbracket\right\\})^{2},$

and then we have

$\nabla\bar{\psi}(x)=\mathrm{proj}_{\operatorname*{{convh}}\left\\{Mx_{t},t\in\llbracket
0,K-1\rrbracket\right\\}}(x).$

Using the same normalization as (B.1), we know that
(HB)$\,{}_{\gamma,\beta}\leavevmode\nobreak\ $$(f)$ cycles on
$\leavevmode\hbox to9.9pt{\vbox to9.9pt{\pgfpicture\makeatletter\hbox{\hskip
4.95244pt\lower-4.95244pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$ if and only if
$\forall t\in\llbracket 0,K-1\rrbracket,\nabla\bar{\psi}(x_{t})=Mx_{t}$, i.e.

$\forall t\in\llbracket
0,K-1\rrbracket,\mathrm{proj}_{\operatorname*{{convh}}\left\\{Mx_{t},t\in\llbracket
0,K-1\rrbracket\right\\}}(x_{t})=Mx_{t}.$

The projection on a convex set
$\mathrm{proj}_{\operatorname*{{convh}}\left\\{Mx_{t},t\in\llbracket
0,K-1\rrbracket\right\\}}(x_{t})=Mx_{t}$ can be characterized by the following
set of inequalities $\left\\{\left<x_{t}-Mx_{t},Mx_{s}-Mx_{t}\right>\leqslant
0,s\neq t\right\\}$. We conclude with (12) that

$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})\Longleftrightarrow\text{\eqref{eq:hb}$\,{}_{\gamma,\beta}\leavevmode\nobreak\
$}(\psi)\text{ cycles on }\leavevmode\hbox to9.9pt{\vbox
to9.9pt{\pgfpicture\makeatletter\hbox{\hskip 4.95244pt\lower-4.95244pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$

##### Construction of $\psi$:

Using (B.1), we search for a function
$\bar{f}\in\mathcal{F}_{0,1}\leavevmode\nobreak\ |\leavevmode\nobreak\ \forall
t\in\llbracket 0,K-1\rrbracket,\nabla\bar{f}(x_{t}^{\circ})=Mx_{t}^{\circ}.$
The functions $h:x\mapsto\max_{t\in\llbracket
0,K-1\rrbracket}\left<Mx_{t},x\right>$ is a natural convex function verifying
$\forall t\in\llbracket
0,K-1\rrbracket,\nabla\bar{f}(x_{t}^{\circ})=Mx_{t}^{\circ}$. However, the
latter is not smooth. We therefore compute $M_{h}$ its Moreau envelope with
smoothing parameter 1, defined as

$\displaystyle M_{h}(x)$ $\displaystyle:=\min_{y}f(y)+\frac{1}{2}\|x-y\|^{2}$
$\displaystyle=\min_{y}\max_{t\in\llbracket
0,K-1\rrbracket}\left<Mx_{t},y\right>+\frac{1}{2}\|x-y\|^{2}$
$\displaystyle=\min_{y}\max_{(\lambda_{t})_{t\in\llbracket
0,K-1\rrbracket}\geqslant 0\leavevmode\nobreak\ |\leavevmode\nobreak\
\sum_{t=0}^{K-1}\lambda_{t}=1}\left<\sum_{t=0}^{K-1}\lambda_{t}Mx_{t},y\right>+\frac{1}{2}\|x-y\|^{2}$
$\displaystyle=\max_{(\lambda_{t})_{t\in\llbracket 0,K-1\rrbracket}\geqslant
0\leavevmode\nobreak\ |\leavevmode\nobreak\
\sum_{t=0}^{K-1}\lambda_{t}=1}\left<\sum_{t=0}^{K-1}\lambda_{t}Mx_{t},x\right>-\frac{1}{2}\|\sum_{t=0}^{K-1}\lambda_{t}Mx_{t}\|^{2}$
$\displaystyle=\max_{z\in\operatorname*{{convh}}\left\\{Mx_{t}\right\\}}\left<z,x\right>-\frac{1}{2}\|z\|^{2}$
$\displaystyle=\frac{1}{2}\|x\|^{2}-\frac{1}{2}d(x,\operatorname*{{convh}}\left\\{Mx_{t}\right\\})^{2}.$

This function is $\bar{\psi}$ and by renormalization we obtain $\psi$.

$\hfill\blacksquare$

###  B.2 Analysis of
$\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$

In this section, we aim at proving that the roots-of-unity cycling region
$\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$ can be written as
$\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\left\\{(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma\geqslant\gamma_{\min}(\beta,\mu,L)\right\\}$ for
some values of $\gamma_{\min}(\beta,\mu,L)$ to be determined. Theorem 3.5
states that, for any
$(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})$,
$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$
if and only if

$\displaystyle P_{\beta,K,\mu,L}(\gamma)\leqslant 0$ (13)

with

$\displaystyle
P_{\beta,K,\mu,L}:\gamma\mapsto(\mu\gamma)^{2}-2\left[\beta-\cos\theta_{K}+\kappa(1-\beta\cos\theta_{K})\right](\mu\gamma)+2\kappa(1-\cos\theta_{K})(1+\beta^{2}-2\beta\cos\theta_{K}).$
(14)

The polynomial $P_{\beta,K,\mu,L}$ has two roots for $\beta$ larger than a
value $\beta_{-}(K,\mu,L)$, we thus use the following notations.

###### Notation B.1

For any $\mu,L$, $K\geqslant 2$, we denote

$\displaystyle\beta_{-}(K,\mu,L)$
$\displaystyle:=\frac{\kappa\cos{\theta_{K}}^{2}+(1-\kappa)^{2}\cos{\theta_{K}}-\kappa+(1-\kappa)(1-\cos{\theta_{K}})\sqrt{2\kappa(1+\cos{\theta_{K}})}}{1-2\kappa+\kappa^{2}\cos{\theta_{K}}^{2}},$

For any $\beta\geqslant\beta_{-}(K,\mu,L)$, we denote

$\displaystyle A_{K}(\beta,\mu,L)$
$\displaystyle:=\left[\beta-\cos\theta_{K}+\kappa(1-\beta\cos\theta_{K})\right],$
(15) $\displaystyle B_{K}(\beta,\mu,L)$
$\displaystyle:=\sqrt{\left[\beta-\cos\theta_{K}+\kappa(1-\beta\cos\theta_{K})\right]^{2}-2\kappa(1-\cos\theta_{K})(1+\beta^{2}-2\beta\cos\theta_{K})},$
(16)

Finally, we introduce the roots
$(\gamma_{-}(\beta,K,\mu,L),\gamma_{\max}(\beta,K,\mu,L))$ of
$P_{\beta,K,\mu,L}$:

$\displaystyle\gamma_{-}(\beta,K,\mu,L)$
$\displaystyle:=\frac{A_{K}(\beta,\mu,L)-B_{K}(\beta,\mu,L)}{\mu},$
$\displaystyle\gamma_{+}(\beta,K,\mu,L)$
$\displaystyle:=\frac{A_{K}(\beta,\mu,L)+B_{K}(\beta,\mu,L)}{\mu}.$

We underline that we can obtain an alternative expression of
$\beta_{-}(K,\mu,L)$, that intuitively provides an approximation of
$\beta_{-}(K,\mu,L)$ as $\kappa\to 0$

###### Lemma B.2

For any $K$, $\mu,L$, it holds that:

$\displaystyle\beta_{-}(K,\mu,L)-\cos{\theta_{K+1}}=$
$\displaystyle\sqrt{\kappa}(1-\cos{\theta_{K}})\frac{(1+\cos{\theta_{K}})\sqrt{\kappa}+\sqrt{2(1+\cos{\theta_{K}})}}{1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}.$

Proof. The proof consists in algebraic manipulations.

$\displaystyle\beta_{-}(K,\mu,L)-\cos{\theta_{K}}$
$\displaystyle=\frac{\kappa\cos{\theta_{K}}^{2}+(1-\kappa)^{2}\cos{\theta_{K}}-\kappa+(1-\kappa)(1-\cos{\theta_{K}})\sqrt{2\kappa(1+\cos{\theta_{K}})}}{1-2\kappa+\kappa^{2}\cos{\theta_{K}}^{2}}$
$\displaystyle-\frac{(1-2\kappa)\cos{\theta_{K}}+\kappa^{2}\cos{\theta_{K}}^{3}}{1-2\kappa+\kappa^{2}\cos{\theta_{K}}^{2}}$
$\displaystyle=$
$\displaystyle\frac{\kappa(\kappa\cos{\theta_{K}}-1)(1-\cos^{2}{\theta_{K}})+(1-\kappa)(1-\cos{\theta_{K}})\sqrt{2\kappa(1+\cos{\theta_{K}})}}{1-2\kappa+\kappa^{2}\cos{\theta_{K}}^{2}}$
$\displaystyle=$
$\displaystyle(1-\cos{\theta_{K}})\sqrt{\kappa(1+\cos{\theta_{K})}}\cdot\frac{\sqrt{2}(1-\kappa)+(\kappa\cos{\theta_{K}}-1)\sqrt{\kappa(1+\cos{\theta_{K}})}}{1-2\kappa+\kappa^{2}\cos{\theta_{K}}^{2}}$
$\displaystyle=$
$\displaystyle\sqrt{\kappa}(1-\cos{\theta_{K}})\sqrt{1+\cos{\theta_{K}}}$
$\displaystyle\times\frac{(1+\kappa\cos{\theta_{K}}-\sqrt{2\kappa(1+\cos{\theta_{K}})})(\sqrt{2}+\sqrt{\kappa(1+\cos{\theta_{K}})})}{(1+\kappa\cos{\theta_{K}}-\sqrt{2\kappa(1+\cos{\theta_{K}})})(1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})})}$
$\displaystyle=$
$\displaystyle\sqrt{\kappa}(1-\cos{\theta_{K}})\frac{(1+\cos{\theta_{K}})\sqrt{\kappa}+\sqrt{2(1+\cos{\theta_{K}})}}{1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}.$

$\hfill\blacksquare$

Using those notations, we can restate the condition (13) as follows.

###### Fact B.3

$P_{\beta,K,\mu,L}(\gamma)\leqslant 0$ if and only if
$\beta\geqslant\beta_{-}(K,\mu,L)$ and

$\gamma_{-}(\beta,K,\mu,L)\leqslant\gamma\leqslant\gamma_{+}(\beta,K,\mu,L),$
(17)

i.e.:

$\displaystyle\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=$
$\displaystyle\Bigl{\\{}(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})\leavevmode\nobreak\
|\leavevmode\nobreak\ $ $\displaystyle\exists K\geqslant 3\text{ such that
}\beta\geqslant\beta_{-}(K,\mu,L)\text{ and
}\gamma_{-}(\beta,K,\mu,L)\leqslant\gamma\leqslant\gamma_{+}(\beta,K,\mu,L)\Bigl{\\}}.$
(18)

In words, for any $\beta\geqslant 0$, the set of all $\gamma$ such that
$(\gamma,\beta)\in\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$
is a union of intervals given by (18), non-necessarily connected. The next
theorem states that this set of $\gamma$ is actually a single interval as soon
as $\kappa$ is sufficiently small.

######  Theorem B.4 (Analytical form of Roots-of-unity cycle region)

If $\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}$, the roots-of-unity
cycling region is:

$\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\Bigl{\\{}(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})\leavevmode\nobreak\
|\leavevmode\nobreak\ \exists K\geqslant 3\text{ such that
}\beta\geqslant\beta_{-}(K,\mu,L)\text{ and
}\gamma\geqslant\gamma_{-}(\beta,K,\mu,L)\Bigl{\\}}.$

This theorem means that we can ignore, the condition
$\gamma\leqslant\gamma_{+}(\beta,K,\mu,L)$ in the parametric description of
$\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$ in (17). Note that
$\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})\neq\bigl{\\{}(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})\leavevmode\nobreak\
|\leavevmode\nobreak\ \beta\geqslant\beta_{-}(K,\mu,L)\text{ and
}\gamma\geqslant\gamma_{-}(\beta,K,\mu,L)\bigl{\\}}$: the theorem states that
the union (over $K\geqslant 2$) of those sets can be written without an upper
bound on $\gamma$, not each set individually. That is, when
$(\gamma,\beta)\notin\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$
because $\gamma\geqslant\gamma_{+}(\beta,K,\mu,L)$,
$(\gamma,\beta)\in\Omega_{K^{\prime}\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$
for some $K^{\prime}\leqslant K$.

######  Remark B.5 ($K=2$)

Plugging $K=2$ into (17) leads to
$\gamma\in\left[\frac{2(1+\beta)}{L},\frac{2(1+\beta)}{\mu}\right]$ whose
intersection with $\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})$ is empty. Hence,
$\Omega_{2\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\emptyset$,
which explains why Theorem B.4 does not consider cycles of length 2.

In order to prove Theorem B.4, we first state B.6.

###### Lemma B.6

We assume $\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}$. For any
$K\geqslant 2$, and any $\beta\geqslant\beta_{-}(K+1,\mu,L)$, we have

$\gamma_{-}(\beta,K,\mu,L)\leqslant\gamma_{+}(\beta,K+1,\mu,L).$

First, we show that thanks to B.6, we can establish Theorem B.4.

Proof. [Theorem B.4] We denote $\Omega_{\leqslant
K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\bigcup_{3\leqslant\bar{K}\leqslant
K}\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$ the set
of $(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})$ such that
there exists $\bar{K}\leqslant K$ with
$(\gamma,\beta)\in\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$.
We prove by induction over $K$ that

$\Omega_{\leqslant
K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\Bigl{\\{}(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})\leavevmode\nobreak\
|\leavevmode\nobreak\ \exists\bar{K}\leqslant K\text{ such that
}\beta\geqslant\beta_{-}(\bar{K},\mu,L)\text{ and
}\gamma\geqslant\gamma_{-}(\beta,\bar{K},\mu,L)\Bigl{\\}}.$ (19)

initialization $(K=3)$: From B.6,
$\gamma_{+}(\beta,3,\mu,L)\geqslant\gamma_{-}(\beta,2,\mu,L)$, and from Remark
B.5, $\gamma_{-}(\beta,2,\mu,L)=\frac{2(1+\beta)}{L}$. Thus

$\Omega_{\leqslant
3\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\Omega_{3\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})=\left\\{(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})\leavevmode\nobreak\
|\leavevmode\nobreak\ \beta\geqslant\beta_{-}(3,\mu,L)\text{ and
}\mu\gamma\geqslant\mu\gamma_{-}(\beta,3,\mu,L)\right\\}.$

Indeed, the additional assumption that
$\gamma\leqslant\gamma_{+}(\beta,3,\mu,L)$ is useless as
$\gamma_{+}(\beta,3,\mu,L)$ is larger than $\frac{2(1+\beta)}{L}$, which
corresponds to the right-hand side border of
$\Omega_{\mathrm{cv}}(\mathcal{F}_{\mu,L})$.

Induction: Let us assume that (19) holds for some $K$. We prove it still holds
for $K+1$. Indeed, $(\gamma,\beta)\in\Omega_{\leqslant
K+1\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$ if and only if
$(\gamma,\beta)\in\Omega_{\leqslant
K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$ or
$(\gamma,\beta)\in\Omega_{K+1\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$,
i.e. if, by our induction hypothesis
$\gamma\geqslant\gamma_{-}(\beta,\bar{K},\mu,L)$ for some $\bar{K}\leqslant
K$, or
$\gamma_{-}(\beta,K+1,\mu,L)\leqslant\gamma\leqslant\gamma_{+}(\beta,K+1,\mu,L)$.

Then by B.6, if $\gamma\geqslant\gamma_{+}(\beta,K+1,\mu,L)$, we have
$\gamma\geqslant\gamma_{-}(\beta,K,\mu,L)$, thus
$(\gamma,\beta)\in\Omega_{\leqslant
K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$. Finally,
$(\gamma,\beta)\in\Omega_{\leqslant
K+1\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L})$ if and only if
$\gamma\geqslant\gamma_{-}(\beta,\bar{K},\mu,L)$ for some $\bar{K}\leqslant
K$, or $\gamma\geqslant\gamma_{-}(\beta,K+1,\mu,L)$, i.e. if and only if
$\gamma\geqslant\gamma_{-}(\beta,\bar{K},\mu,L)$ for some $\bar{K}\leqslant
K+1$, which concludes the proof. $\hfill\blacksquare$

We now prove B.6.
Proof. [B.6] Since for any $K$, $\gamma_{-}(\beta,K,\mu,L)$ is defined as
$\frac{A_{K}(\beta,\mu,L)-B_{K}(\beta,\mu,L)}{\mu}$, we show the equivalent
formulation

$A_{K}(\beta,\mu,L)-B_{K}(\beta,\mu,L)\leqslant
A_{K+1}(\beta,\mu,L)+B_{K+1}(\beta,\mu,L).$ (20)

First, we rely on the following sequence of implication, that shows that
proving (21) hereafter is sufficient to establish (20).

$\displaystyle\left(A_{K}(\beta,\mu,L)-A_{K+1}(\beta,\mu,L)\right)^{2}\leqslant
B_{K}(\beta,\mu,L)^{2}-B_{K+1}(\beta,\mu,L)^{2}$ (21)
$\displaystyle\quad\overset{B_{K+1}(\beta,\mu,L)^{2}\geqslant
0}{\Longrightarrow}\left(A_{K}(\beta,\mu,L)-A_{K+1}(\beta,\mu,L)\right)^{2}\leqslant
B_{K}(\beta,\mu,L)^{2}$ (22)
$\displaystyle\quad\overset{B_{K}(\beta,\mu,L)\geqslant
0}{\Longrightarrow}A_{K}(\beta,\mu,L)-A_{K+1}(\beta,\mu,L)\leqslant
B_{K}(\beta,\mu,L)$ $\displaystyle\quad\overset{\text{Reordering
terms}}{\Longleftrightarrow}A_{K}(\beta,\mu,L)-B_{K}(\beta,\mu,L)\leqslant
A_{K+1}(\beta,\mu,L)$
$\displaystyle\quad\overset{B_{K+1}(\beta,\mu,L)\geqslant
0}{\Longrightarrow}A_{K}(\beta,\mu,L)-B_{K}(\beta,\mu,L)\leqslant
A_{K+1}(\beta,\mu,L)+B_{K+1}(\beta,\mu,L).$

Equation 22 has the advantage of isolating $B_{K}(\beta,\mu,L)$ so that we get
rid of the square-root appearing in its definition. Equation 21 has the
additional advantage of getting rid of the terms that are independent of the
cosines and of making a factor $\cos{\theta_{K+1}}-\cos{\theta_{K}}$ appear on
both sides of the inequality. Indeed, first we have

$\displaystyle A_{K}(\beta,\mu,L)-A_{K+1}(\beta,\mu,L)$
$\displaystyle\overset{\eqref{eq:a_def}}{=}\left[\beta-\cos\theta_{K}+\kappa(1-\beta\cos\theta_{K})\right]-\left[\beta-\cos\theta_{K+1}+\kappa(1-\beta\cos\theta_{K+1})\right]$
$\displaystyle=(1+\beta\kappa)(\cos{\theta_{K+1}}-\cos{\theta_{K}})$
$\displaystyle(A_{K}(\beta,\mu,L)-A_{K+1}(\beta,\mu,L))^{2}$
$\displaystyle=(1+\beta\kappa)^{2}(\cos{\theta_{K+1}}-\cos{\theta_{K}})^{2}.$
(23)

Also, $B_{K}(\beta,\mu,L)^{2}$ can be simplified, expanding and reordering
terms, as

$\displaystyle B_{K}(\beta,\mu,L)^{2}\overset{\eqref{eq:b_def}}{=}$
$\displaystyle\left[\beta-\cos\theta_{K}+\kappa(1-\beta\cos\theta_{K})\right]^{2}-2\kappa(1-\cos\theta_{K})(1+\beta^{2}-2\beta\cos\theta_{K})$
$\displaystyle=$
$\displaystyle\left[\beta+\kappa-(1+\beta\kappa)\cos\theta_{K}\right]^{2}-2\kappa(1-\cos\theta_{K})(1+\beta^{2}-2\beta\cos\theta_{K})$
$\displaystyle=$
$\displaystyle(\beta+\kappa)^{2}-2(\beta+\kappa)(1+\beta\kappa)\cos\theta_{K}+(1+\beta\kappa)^{2}\cos^{2}\theta_{K}$
$\displaystyle-2\kappa(1+\beta^{2}-2\beta\cos\theta_{K}-(1+\beta^{2})\cos\theta_{K}+2\beta\cos^{2}\theta_{K})$
$\displaystyle=$
$\displaystyle\left[(\beta+\kappa)^{2}-2\kappa(1+\beta^{2})\right]-2\left[(\beta+\kappa)(1+\beta\kappa)-\kappa(1+\beta)^{2}\right]\cos\theta_{K}$
$\displaystyle+\left[(1+\beta\kappa)^{2}-4\beta\kappa\right]\cos^{2}\theta_{K}$
$\displaystyle=$
$\displaystyle\underbrace{\left[(\beta+\kappa)^{2}-2\kappa(1+\beta^{2})\right]}_{\text{independent
of
$K$}}-2\beta(1-\kappa)^{2}\cos\theta_{K}+(1-\beta\kappa)^{2}\cos^{2}\theta_{K}.$

While inequality (22) thus writes

$(1+\beta\kappa)^{2}(\cos{\theta_{K+1}}-\cos{\theta_{K}})^{2}\leqslant\left[(\beta+\kappa)^{2}-2\kappa(1+\beta^{2})\right]-2\beta(1-\kappa)^{2}\cos\theta_{K}+(1-\beta\kappa)^{2}\cos^{2}\theta_{K},$

and is thus not easy to handle,
$B_{K}(\beta,\mu,L)^{2}-B_{K+1}(\beta,\mu,L)^{2}$ simplifies as

$\displaystyle B_{K}(\beta,\mu,L)^{2}-B_{K+1}(\beta,\mu,L)^{2}=$
$\displaystyle-2\beta(1-\kappa)^{2}(\cos\theta_{K}-\cos\theta_{K+1})+(1-\beta\kappa)^{2}(\cos^{2}\theta_{K}-\cos^{2}\theta_{K+1}),$
(24)

and using (23) and (24), inequality (21) thus writes

$\displaystyle(1+\beta\kappa)^{2}(\cos{\theta_{K+1}}-\cos{\theta_{K}})^{2}$
$\displaystyle\leqslant
2\beta(1-\kappa)^{2}(\cos{\theta_{K+1}}-\cos{\theta_{K}})-(1-\beta\kappa)^{2}(\cos^{2}\theta_{K+1}-\cos^{2}\theta_{K})$
$\displaystyle=\left[2\beta(1-\kappa)^{2}-(1-\beta\kappa)^{2}(\cos\theta_{K+1}+\cos\theta_{K})\right](\cos{\theta_{K+1}}-\cos{\theta_{K}}).$

Dividing by the positive term $\cos{\theta_{K+1}}-\cos{\theta_{K}}$666This
simplification was the motivation to prove the relaxation (21) instead of
(22). Interestingly, this relaxation is tight when $B_{K+1}(\beta,\mu,L)=0$,
i.e. for $\beta=\beta_{-}(K+1,\mu,L)$. As we will see later, this value of
$\beta$ is the only one that actually matters (if $K\neq 3$)., we get that
(21) is equivalent to

$(1+\beta\kappa)^{2}(\cos{\theta_{K+1}}-\cos{\theta_{K}})\leqslant\left[2\beta(1-\kappa)^{2}-(1-\beta\kappa)^{2}(\cos\theta_{K+1}+\cos\theta_{K})\right].$

By ordering terms, this is also equivalent to

$(1+\beta\kappa)^{2}(\cos{\theta_{K+1}}-\cos{\theta_{K}})+(1-\beta\kappa)^{2}(\cos\theta_{K+1}+\cos\theta_{K})\leqslant
2\beta(1-\kappa)^{2},$

or again, dividing by $4\beta\kappa$,

$\frac{1}{2}\left(\frac{1}{\beta\kappa}+\beta\kappa\right)\cos{\theta_{K+1}}\leqslant\frac{(1-\kappa)^{2}}{2\kappa}+\cos{\theta_{K}}.$
(25)

Note that we need this last equation to hold for all
$\beta\geqslant\beta_{-}(K+1,\mu,L)$. Moreover, while the RHS does not depend
on $\beta$, the LHS increases or decreases with respect to $\beta$, according
to the sign of $\cos{\theta_{K+1}}$. We thus have to distinguish several
cases.

  * •

When $K=2$, $\cos{\theta_{K+1}}=\cos{\theta_{3}}=-1/2<0$. Then the LHS
increases and it is sufficient to verify (25) for $\beta=1$. We have: if
$-\frac{1}{4}\left(\frac{1}{\kappa}+\kappa\right)\leqslant\frac{(1-\kappa)^{2}}{2\kappa}-1$,
then (20) holds for $K=2$. A simple technical computation gives that this
condition holds if and only if $\kappa\leqslant\frac{4-\sqrt{7}}{3}$.

  * •

When $K=3$, $\cos{\theta_{K+1}}=\cos{\theta_{4}}=0$. Then the LHS does not
depend on $\beta$ neither. Equation 25 is independent of $\beta$ and is
written $0\leqslant\frac{(1-\kappa)^{2}}{2\kappa}-\frac{1}{2}$. We conclude
that, if $\kappa\leqslant\frac{3-\sqrt{5}}{2}$, then (B.6) holds for $K=3$.

  * •

When $K\geqslant 4$, $\cos{\theta_{K+1}}\geqslant\cos{\theta_{5}}>0$, hence
the LHS decreases with respect to $\beta$. It is sufficient to verify (25) for
$\beta=\beta_{-}(K+1,\mu,L)$, or even for any value smaller than
$\beta_{-}(K+1,\mu,L)$ to prove the lemma.

We use the following lower bound on $\beta_{-}(K+1,\mu,L)$, obtained from B.2

$\displaystyle\beta_{-}(K+1,\mu,L)-\cos{\theta_{K+1}}\overset{\text{\ref{lem:otherexprbeta}}}{=}$
$\displaystyle\sqrt{\kappa}(1-\cos{\theta_{K+1}})\frac{(1+\cos{\theta_{K+1}})\sqrt{\kappa}+\sqrt{2(1+\cos{\theta_{K+1}})}}{1+\kappa\cos{\theta_{K+1}}+\sqrt{2\kappa(1+\cos{\theta_{K+1}})}}$
$\displaystyle\geqslant$ $\displaystyle\sqrt{\kappa}(1-\cos{\theta_{K+1}}).$
$\displaystyle=$ $\displaystyle\cos{\theta_{K+1}}(1+\sqrt{\kappa}\xi_{K+1}),$

with $\xi_{K+1}:=\frac{1}{\cos{\theta_{K+1}}}-1$. Overall, for $K\geqslant 4$,
(25) is valid for all $\beta\geqslant\beta_{-}(K+1,\mu,L)$ if it is valid at
$\cos{\theta_{K+1}}(1+\sqrt{\kappa}\xi_{K+1})$. Plugging this value into (25)
it is thus sufficient to prove that

$\frac{1}{2}\left(\frac{1}{\kappa(1+\sqrt{\kappa}\xi_{K+1})}+\kappa\cos^{2}{\theta_{K+1}}(1+\sqrt{\kappa}\xi_{K+1})\right)\leqslant\frac{(1-\kappa)^{2}}{2\kappa}+\cos{\theta_{K}}.$

Multiplying by $2\kappa$ and reordering terms, the latter is equivalent to

$\frac{1}{1+\sqrt{\kappa}\xi_{K+1}}-(1-\kappa)^{2}\leqslant
2\kappa\cos{\theta_{K}}-\kappa^{2}\underbrace{\cos^{2}{\theta_{K+1}}}_{\leqslant\cos{\theta_{K+1}}}\underbrace{(1+\sqrt{\kappa}\xi_{K+1})}_{\leqslant
1+\xi_{K+1}}.$ (26)

First, as for any $\tau\geqslant 0$, $\frac{1}{1+\tau}\leqslant
1-\tau+\tau^{2}$, the LHS of (26) is upper bounded by
$1-\sqrt{\kappa}\xi_{K+1}+\kappa\xi_{K+1}^{2}-(1-\kappa)^{2}$. Second, the RHS
of (26) is lower bounded by $2\kappa\cos{\theta_{K}}-\kappa^{2}$. It is thus
sufficient to prove

$1-\sqrt{\kappa}\xi_{K+1}+\kappa\xi_{K+1}^{2}-(1-2\kappa+\kappa^{2})\leqslant
2\kappa\cos{\theta_{K}}-\kappa^{2}.$

Simplifying and reordering terms, this is equivalent to

$\sqrt{\kappa}\xi_{K+1}\geqslant\kappa(\xi_{K+1}^{2}+2-2\cos{\theta_{K}}),$

or again

$\frac{1}{\sqrt{\kappa}}\geqslant\left(\xi_{K+1}+\frac{2(1-\cos{\theta_{K}})}{\xi_{K+1}}\right)=\left(\frac{1}{\cos{\theta_{K+1}}}-1+\frac{2\cos{\theta_{K+1}}(1-\cos{\theta_{K}})}{(1-\cos{\theta_{K+1}})}\right).$

Finally,

$\displaystyle\frac{1}{\cos{\theta_{K+1}}}-1+\frac{2\cos{\theta_{K+1}}(1-\cos{\theta_{K}})}{(1-\cos{\theta_{K+1}})}$
$\displaystyle\overset{\text{\lx@cref{creftypecap~refnum}{lem:techn1}}}{\leqslant}$
$\displaystyle\frac{1}{\cos{\theta_{K+1}}}-1+2\times
1\times\frac{3}{2}=\frac{1}{\cos{\theta_{K+1}}}+2$
$\displaystyle\overset{K\geqslant 4}{\leqslant}$
$\displaystyle\frac{1}{\cos{\theta_{5}}}+2=\frac{1}{\cos{\frac{2\pi}{5}}}+2$
$\displaystyle=$ $\displaystyle 3+\sqrt{5}.$

Ultimately,
$\kappa\leqslant\left(\frac{1}{3+\sqrt{5}}\right)^{2}=\left(\frac{3-\sqrt{5}}{4}\right)^{2}$
is a sufficient condition for Equation 20 to hold for any $K\geqslant 4$. As a
summary, we proved the following sufficient conditions so that (20) holds:

  * •

For $K=2$, (20) holds as soon as $\kappa\leqslant\frac{4-\sqrt{7}}{3}$.

  * •

For $K=3$, (20) holds as soon as $\kappa\leqslant\frac{3-\sqrt{5}}{2}$.

  * •

For $K\geqslant 4$, (20) holds as soon as
$\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}$.

Among those 3 values, $\left(\frac{3-\sqrt{5}}{4}\right)^{2}$ is the smallest.
Hence, we conclude that (20) holds for any $K\geqslant 2$ if
$\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}$.

$\hfill\blacksquare$

###  B.3 Proof of Theorem 3.6

In order to prove Theorem 3.6, we first establish technical results in Section
B.3.1, then prove the result in Section B.3.2

####  B.3.1 Technical lemmas

We start by proving the following technical lemmas.

###### Lemma B.7

For any integer $K\geqslant 2,\leavevmode\nobreak\
1\leqslant\frac{1-\cos\theta_{K}}{1-\cos\theta_{K+1}}\leqslant\frac{3}{2}$.

Proof. First of all, let’s note that

$\frac{1-\cos\frac{2\pi}{K}}{1-\cos\frac{2\pi}{K+1}}=\frac{\sin^{2}\frac{\pi}{K}}{\sin^{2}\frac{\pi}{K+1}}.$

Since $\sin$ is positive and increasing on $[0,\pi/2]$,
$\sin^{2}\frac{\pi}{K}\geqslant\sin^{2}\frac{\pi}{K+1}$, hence for all
$K\geqslant 2,$ $\leavevmode\nobreak\
1\leqslant\frac{1-\cos\frac{2\pi}{K}}{1-\cos\frac{2\pi}{K+1}}$. Note moreover
this bound is tight as
$\frac{1-\cos\frac{2\pi}{K}}{1-\cos\frac{2\pi}{K+1}}\underset{K\rightarrow\infty}{\rightarrow}1$.
It remains to show that for all integer $K\geqslant
2,\frac{\sin\frac{\pi}{K}}{\sin\frac{\pi}{K+1}}\leqslant\sqrt{\frac{3}{2}}$.
We study the four following cases:

  * •

for $K=2$,
$\frac{\sin\frac{\pi}{K}}{\sin\frac{\pi}{K+1}}=\frac{1}{\sqrt{3}/2}<\sqrt{\frac{3}{2}}$,

  * •

for $K=3$,
$\frac{\sin\frac{\pi}{K}}{\sin\frac{\pi}{K+1}}=\frac{\sqrt{3}/2}{\sqrt{2}/2}=\sqrt{\frac{3}{2}}$,

  * •

for $K=4$,
$\frac{\sin\frac{\pi}{K}}{\sin\frac{\pi}{K+1}}=\frac{\sqrt{2}/2}{\sqrt{10-2\sqrt{5}}/4}<\sqrt{\frac{3}{2}}$,

  * •

for $K\geqslant 5$,

$\displaystyle\frac{\sin\frac{\pi}{K}}{\sin\frac{\pi}{K+1}}$
$\displaystyle\leavevmode\nobreak\
=\frac{\sin(\frac{\pi}{K+1}+\frac{\pi}{K(K+1)})}{\sin\frac{\pi}{K+1}}=\frac{\sin\frac{\pi}{K+1}\cos\frac{\pi}{K(K+1)}+\cos\frac{\pi}{K+1}\sin\frac{\pi}{K(K+1)}}{\sin\frac{\pi}{K+1}}$
$\displaystyle\leavevmode\nobreak\
=\cos\frac{\pi}{K(K+1)}+\rm{cotan}\frac{\pi}{K+1}\sin\frac{\pi}{K(K+1)}$
$\displaystyle\leavevmode\nobreak\ \leqslant
1+\frac{K+1}{\pi}\frac{\pi}{K(K+1)}=1+\frac{1}{K}\leqslant\frac{6}{5}<\sqrt{\frac{3}{2}}.$

This shows that

$\forall\text{ integer }K\geqslant 2,\leavevmode\nobreak\
\frac{1-\cos\frac{2\pi}{K}}{1-\cos\frac{2\pi}{K+1}}\leqslant\frac{3}{2}.$

Note furthermore that this bound is also tight as reached for $K=3$.

$\hfill\blacksquare$

Next, we establish a second technical result.

###### Lemma B.8

For any $\beta\in[0,1],$ there exists $K\geqslant 2$ such that
$\frac{2}{3}\leqslant\frac{\beta-\cos\theta{K}}{1-\beta}\leqslant\frac{3}{2}$.

Proof. Let $\beta\in[0,1]$. And let $Z\geqslant 2$ a real number such that
$\beta=\frac{1+\cos\frac{2\pi}{Z}}{2}$. We note that
$\frac{1+\cos\frac{2\pi}{\left\lfloor{Z}\right\rfloor}}{2}\leqslant\beta<\frac{1+\cos\frac{2\pi}{\left\lfloor{Z}\right\rfloor+1}}{2}$.
Besides, from B.7,
$1\leqslant\frac{1-\cos\frac{2\pi}{\left\lfloor{Z}\right\rfloor}}{1-\cos\frac{2\pi}{\left\lfloor{Z}+1\right\rfloor}}\leqslant\frac{3}{2}$,
which implies

$1\leqslant\frac{1-\cos\frac{2\pi}{\left\lfloor{Z}\right\rfloor}}{1-\cos\frac{2\pi}{Z}}\leqslant\frac{5}{4}\quad\text{
or }\quad
1\leqslant\frac{1-\cos\frac{2\pi}{Z}}{1-\cos\frac{2\pi}{\left\lfloor{Z}+1\right\rfloor}}\leqslant\frac{6}{5}.$

In the first case, we define $K=\left\lfloor{Z}\right\rfloor$ while in the
second case, we define $K=\left\lfloor{Z}+1\right\rfloor$. In any case,
$\frac{5}{6}\leqslant\frac{1-\cos\frac{2\pi}{K}}{1-\cos\frac{2\pi}{Z}}\leqslant\frac{5}{4}$.
Moreover, we have
$\frac{\beta-\cos\frac{2\pi}{K}}{1-\beta}=-1+2\frac{1-\cos\frac{2\pi}{K}}{1-\cos\frac{2\pi}{Z}}$,
and we conclude
$\frac{2}{3}\leqslant\frac{\beta-\cos\frac{2\pi}{K}}{1-\beta}\leqslant\frac{3}{2}$.
$\hfill\blacksquare$

Third, we establish a final technical result.

###### Lemma B.9

Assume that $\kappa\leqslant\frac{1}{16}$. For any $\beta\in[0,1],$ for any
$K\geqslant 2$ such that
$\frac{2}{3}\leqslant\frac{\beta-\cos\theta_{K}}{1-\beta}\leqslant\frac{3}{2},$
we have $\beta\geqslant\beta_{-}(K,\mu,L)$.

Proof. The proof consists in proving that

$\frac{1-\beta_{-}(K,\mu,L)}{1-\cos{\theta_{K}}}\geqslant\frac{3}{5}.$

Then, since $\frac{\beta-\cos{\theta_{K}}}{1-\beta}\geqslant\frac{2}{3}$, we
have $\frac{1-\cos{\theta_{K}}}{1-\beta}\geqslant\frac{5}{3}$, and finally
$\frac{1-\beta}{1-\cos{\theta_{K}}}\leqslant\frac{3}{5}\leqslant\frac{1-\beta_{-}(K,\mu,L)}{1-\cos{\theta_{K}}}$,
concluding that $\beta\geqslant\beta_{-}(K,\mu,L)$.

By B.2, we have

$\frac{\beta_{-}(K,\mu,L)-\cos{\theta_{K}}}{1-\cos{\theta_{K}}}=\frac{\kappa+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}{1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}.$

Applying the mapping $x\mapsto 1-x$ to the previous equation, we get

$\frac{1-\beta_{-}(K,\mu,L)}{1-\cos{\theta_{K}}}=\frac{1-\kappa}{1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}.$

We now need to prove that whatever $\theta_{K}$ is,
$\frac{1-\kappa}{1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}\geqslant\frac{3}{5}$.
We note that the LHS converges to 1 when $\kappa$ goes to 0, hence we know
that this inequality holds for $\kappa$ small enough. We make the precise
computation below.

$\displaystyle\frac{1-\kappa}{1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})}}\geqslant\frac{3}{5}$
$\displaystyle\Longleftrightarrow$ $\displaystyle
3(1+\kappa\cos{\theta_{K}}+\sqrt{2\kappa(1+\cos{\theta_{K}})})\leqslant
5(1-\kappa)$ $\displaystyle\Longleftrightarrow$ $\displaystyle
3\sqrt{2\kappa(1+\cos{\theta_{K}})}+\kappa(5+3\cos{\theta_{K}})\leqslant 2$
$\displaystyle\Longleftarrow$ $\displaystyle 6\sqrt{\kappa}+8\kappa\leqslant
2$ $\displaystyle\Longleftrightarrow$ $\displaystyle
1-3\sqrt{\kappa}-4\kappa\geqslant 0$ $\displaystyle\Longleftrightarrow$
$\displaystyle(1-4\sqrt{\kappa})(1+\sqrt{\kappa})\geqslant 0$
$\displaystyle\Longleftrightarrow$
$\displaystyle\sqrt{\kappa}\leqslant\frac{1}{4}.$

Hence, the desired result.

$\hfill\blacksquare$

####  B.3.2 Proof of Theorem 3.6

Finally, we prove Theorem 3.6 : See 3.6

Proof. First, we assume that
$\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}$. Note that in the
opposite case,
$\sqrt{\kappa}\leqslant(3+\sqrt{5})\kappa\leqslant\frac{50}{3}\kappa$, hence
the result would still hold.

Let
$(\gamma,\beta)\in(\Omega_{\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L}))^{c}=(\bigcup_{K=2}^{\infty}\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L}))^{c}=\bigcap_{K=2}^{\infty}(\Omega_{K\text{-}\circ\text{-}\mathrm{Cycle}}(\mathcal{F}_{\mu,L}))^{c}$.
By Theorem B.4 (since $\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}$),
for all $K\geqslant 2$, if $\beta\geqslant\beta_{-}(K,\mu,L)$ (see B.1),

$\displaystyle\mu\gamma$ $\displaystyle\leqslant\mu\gamma_{-}(\beta,K,\mu,L)$
$\displaystyle=\left[\beta-\cos{\theta_{K}}+\kappa(1-\beta\cos{\theta_{K}})\right]\left(1-\sqrt{1-\frac{2\kappa(1-\cos{\theta_{K}})(1+\beta^{2}-2\beta\cos{\theta_{K}})}{\left[\beta-\cos{\theta_{K}}+\kappa(1-\beta\cos{\theta_{K}})\right]^{2}}}\right)$
$\displaystyle\leqslant\left[\beta-\cos{\theta_{K}}+\kappa(1-\beta\cos{\theta_{K}})\right]\left(1-\left(1-\frac{2\kappa(1-\cos{\theta_{K}})(1+\beta^{2}-2\beta\cos{\theta_{K}})}{\left[\beta-\cos{\theta_{K}}+\kappa(1-\beta\cos{\theta_{K}})\right]^{2}}\right)\right)$
$\displaystyle=\left(\frac{2\kappa(1-\cos{\theta_{K}})(1+\beta^{2}-2\beta\cos{\theta_{K}})}{\beta-\cos{\theta_{K}}+\kappa(1-\beta\cos{\theta_{K}})}\right)$
$\displaystyle\leqslant\left(\frac{2\kappa(1-\cos{\theta_{K}})(1+\beta^{2}-2\beta\cos{\theta_{K}})}{\beta-\cos{\theta_{K}}}\right).$

Finally,

$\mu\gamma\leqslant\min_{K\geqslant
2}\left(\frac{2\kappa(1-\cos{\theta_{K}})(1+\beta^{2}-2\beta\cos{\theta_{K}})}{\beta-\cos{\theta_{K}}}\right).$

We introduce $C_{\beta}:=\frac{\beta-\cos\tfrac{2\pi}{K_{\beta}}}{1-\beta}$
with $K$ chosen so that B.8 holds. First we know by B.9 (since
$\kappa\leqslant\left(\frac{3-\sqrt{5}}{4}\right)^{2}\leqslant\frac{1}{16}$)
that $\beta\geqslant\beta_{-}(K_{\beta},\mu,L)$ and then that the previous
calculus is valid. Second, we have

$\displaystyle\mu\gamma$ $\displaystyle\leqslant\left(2\left(2\beta
C_{\beta}+1+3\beta+\tfrac{1+\beta}{C_{\beta}}\right)\right)\kappa(1-\beta)$
$\displaystyle\leqslant
4\left(C_{\beta}+\frac{1}{C_{\beta}}+2\right)\kappa(1-\beta)$
$\displaystyle\leqslant
4\left(\frac{3}{2}+\frac{2}{3}+2\right)\kappa(1-\beta)$
$\displaystyle=\frac{50}{3}\kappa(1-\beta)$ (27)

which proves that $\mu\gamma\leqslant\frac{50}{3}\kappa(1-\beta)$. Set
$C=50/3$. By contradiction, we assume that $\rho<\frac{1-C\kappa}{1+C\kappa}$,
and additionally $(\gamma,\beta)\in\mathrm{SLS}_{\mu,L}\left(\rho\right)$,
From 2.4 we know

$\displaystyle\frac{\tfrac{1-\kappa}{1+\kappa}-\rho}{\tfrac{1}{\rho}-\tfrac{1-\kappa}{1+\kappa}}\leqslant\beta\leqslant\rho^{2}$
$\displaystyle\mu\gamma\geqslant(1-\rho)(1-\tfrac{\beta}{\rho}).$

And from (27), we know that

$\mu\gamma\leqslant C\kappa(1-\beta).$

Combining those inequalities, we get $(1-\rho)(1-\tfrac{\beta}{\rho})\leqslant
C\kappa(1-\beta)$. Rearanging the terms leads to

$\left(\frac{1-\rho}{\rho}-C\kappa\right)\beta\geqslant 1-\rho-C\kappa.$

Besides, $\frac{1-\rho}{\rho}-C\kappa\geqslant 0$ (since
$\rho<\tfrac{1-C\kappa}{1+C\kappa}\leqslant\tfrac{1}{1+C\kappa}$) and moreover
$\beta\in\left[\frac{\tfrac{1-\kappa}{1+\kappa}-\rho}{\tfrac{1}{\rho}-\tfrac{1-\kappa}{1+\kappa}},\rho^{2}\right]$,
thus $\beta<\rho^{2}$ we get:

$\left(\frac{1-\rho}{\rho}-C\kappa\right)\rho^{2}\geqslant 1-\rho-C\kappa.$

Equivalently $(1-\rho)^{2}\leqslant C\kappa(1-\rho^{2})$, that is
$\rho\geqslant\tfrac{1-C\kappa}{1+C\kappa}$. Which is in contradiction with
our initial assumption $\rho<\frac{1-C\kappa}{1+C\kappa}$. As a conclusion,

$\rho_{\operatorname{HB}_{\gamma,\beta}}\leqslant\rho\Longrightarrow\rho\geqslant\tfrac{1-C\kappa}{1+C\kappa}.$

$\hfill\blacksquare$

##  Appendix C Auxiliary proofs from Section 4: Proof of 4.12

See 4.12

Proof. 4.12 The minimal polynomial of $J_{K}$ is $X^{K}-1$, a split polynomial
with simple roots in $\mathbb{C}$. Therefore, $J_{K}$ diagonalizes on
$\mathbb{C}$ with eigenvalues $\omega^{\ell}=e^{2i\pi\ell/K}$,
$\ell\in\llbracket 0,K-1\rrbracket$, and $G$ diagonalizes in the same basis
with eigenvalues $\nu_{\ell}:=\sum_{j=0}^{K-1}c_{j}\omega^{j\ell}$. The
sequence $(\nu_{\ell})_{\ell\in\llbracket 0,K-1\rrbracket}$ is the discrete
Fourier transform of $(c_{j})_{j\in\llbracket 0,K-1\rrbracket}$. Therefore,
$(c_{j})_{j\in\llbracket 0,K-1\rrbracket}$ is the inverse discrete Fourier
transform of $(\nu_{\ell})_{\ell\in\llbracket 0,K-1\rrbracket}$:

$\forall j\in\llbracket
0,K-1\rrbracket,c_{j}=\frac{1}{K}\sum_{\ell=0}^{K-1}\nu_{\ell}\omega^{-j\ell}.$
(28)

Moreover,

$\nu_{K-\ell}=\sum_{j=0}^{K-1}c_{j}\omega^{j(K-\ell)}=\sum_{j=0}^{K-1}c_{j}\omega^{-j\ell}=\bar{\nu_{\ell}},$

and by symmetry of $G$, $\bar{\nu_{\ell}}=\nu_{\ell}$. Hence, the eigenvalues
almost all have an even multiplicity. This excludes $\nu_{0}$ and $\nu_{K/2}$
if $K$ is even. We can therefore reorder and group terms in (28) as

$\displaystyle\forall j\in\llbracket 0,K-1\rrbracket,c_{j}$
$\displaystyle=\frac{1}{K}\left[\nu_{0}+\sum_{\ell=1}^{\lfloor\frac{K-1}{2}\rfloor}\nu_{\ell}(\omega^{-j\ell}+\omega^{j\ell})+\nu_{\frac{K}{2}}\omega^{-j\frac{K}{2}}\right]$
(where the last term drops if $K=1\;(\mathrm{mod}\;2)$)
$\displaystyle=\frac{1}{K}\left[\nu_{0}+\sum_{\ell=1}^{\lfloor\frac{K-1}{2}\rfloor}2\nu_{\ell}\cos\left(\frac{2\pi
jl}{K}\right)+\nu_{\frac{K}{2}}(-1)^{j}\right]$

Finally, $G$ is symmetric positive semi-definite and circulant if and only if
there exists non-negative $(\nu_{l})_{l\in\llbracket
0,\lfloor\frac{K}{2}\rfloor\rrbracket}$ such that

$\displaystyle G=$
$\displaystyle\sum_{j=0}^{K-1}\frac{1}{K}\left[\nu_{0}+\sum_{\ell=1}^{\lfloor\frac{K-1}{2}\rfloor}2\nu_{\ell}\cos\left(\frac{2\pi
jl}{K}\right)+\nu_{\frac{K}{2}}(-1)^{j}\right]J_{K}^{j}$ $\displaystyle=$
$\displaystyle\frac{\nu_{0}}{K}\underbrace{\sum_{j=0}^{K-1}J_{K}^{j}}_{\text{Matrix
full of
1s}}+\frac{\nu_{\frac{K}{2}}}{K}\underbrace{\sum_{j=0}^{K-1}(-1)^{j}J_{K}^{j}}_{\text{Checkerboard
$\left((-1)^{|i-j|}\right)_{i,j}$}}+\sum_{\ell=1}^{\lfloor\frac{K-1}{2}\rfloor}\frac{2\nu_{\ell}}{K}\underbrace{\sum_{j=0}^{K-1}\cos\left(\frac{2\pi
jl}{K}\right)J_{K}^{j}}_{\left(\cos\left(\frac{2\pi\ell}{K}|i-j|\right)\right)_{i,j}}.$

The condition $G\mathbf{1}_{K}=0$ implies $\nu_{0}=0$. $\hfill\blacksquare$

##  Appendix D Auxiliary proofs from Section 5

###  D.1 Proof of Theorem 5.3

See 5.3

Proof. We introduce matrices $P$ and $D$ verifying
$PDP^{-1}=\begin{pmatrix}(1+\beta)\mathrm{I}_{2}-\mu\gamma\mathrm{I}_{2}&-\beta\mathrm{I}_{2}\\\
\mathrm{I}_{2}&0\end{pmatrix}$, and such that the operator norm $\rho_{D}$ of
the matrix $D$, $\rho_{D}=\|D\|_{\text{op}}$ is smaller than 1, and set
$\kappa_{P}=\frac{1}{\|P\|_{\text{op}}\|P^{-1}\|_{\text{op}}}\leqslant 1$. The
existence of such matrices is guaranteed as
$(\gamma,\beta)\in\Omega_{\mathrm{cv}}(\mathcal{Q}_{\mu,L})$, and we discuss
the choice of this reduction in Section D.2.

We prove by induction that $\forall t\geqslant
1,\left\|P^{-1}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}\right\|\leqslant\frac{r_{\max}}{\|P\|_{\text{op}}}$.
which implies that $\forall t\geqslant 1,\left\|\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}\right\|\leqslant{r_{\max}}$, thus the result of the
theorem, i.e., $z_{t}\in
B(x^{\circ}_{t\;(\mathrm{mod}\;K)},r_{\max})\subseteq\mathcal{V}_{t\;(\mathrm{mod}\;K)}$.

In the proof, we extend again $(x^{\circ}_{k})$ to $k\in\mathbb{N}$ by
periodicity, i.e., $(x^{\circ}_{k})=(x^{\circ}_{k\;(\mathrm{mod}\;K)})$.

##### initialization:

$\left\|\begin{pmatrix}\delta_{1}\\\
\delta_{0}\end{pmatrix}\right\|=\sqrt{\|\delta_{0}\|^{2}+\|\delta_{1}\|^{2}}\leqslant\kappa_{P}r_{\max}=\frac{r_{\max}}{\|P\|_{\text{op}}\|P^{-1}\|_{\text{op}}}$
implies $\left\|P^{-1}\begin{pmatrix}\delta_{1}\\\
\delta_{0}\end{pmatrix}\right\|\leqslant\frac{r_{\max}}{\|P\|_{\text{op}}}$.

##### Induction:

By induction hypothesis $\left\|P^{-1}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}\right\|\leqslant\frac{r_{\max}}{\|P\|_{\text{op}}}$,
thus $z_{t}\in\mathcal{V}_{t\;(\mathrm{mod}\;K)}$. We now write (HB)’s
$(t+1)^{\mathrm{th}}$ step:

$\displaystyle z_{t+1}$
$\displaystyle=z_{t}-\gamma_{t}\hat{g}_{t}(x^{\circ}_{t}+\delta_{t})+\beta_{t}(z_{t}-z_{t-1})=z_{t}-\gamma_{t}(\nabla\psi(x^{\circ}_{t}+\delta_{t})+\delta_{g_{t}})+\beta_{t}(z_{t}-z_{t-1}).$

Using that for all $t\geqslant 0$, $z_{t+1}=x^{\circ}_{t+1}+\delta_{t+1}$.

$\displaystyle x^{\circ}_{t+1}+\delta_{t+1}$
$\displaystyle=x^{\circ}_{t}+\delta_{t}+(\beta+\delta_{\beta_{t}})(x^{\circ}_{t}+\delta_{t}-x^{\circ}_{t-1}-\delta_{t-1})-(\gamma+\delta_{\gamma_{t}})\nabla\psi(x^{\circ}_{t}+\delta_{t})-\gamma_{t}\delta_{g_{t}}.$

And as $\eqref{eq:hb}_{\gamma,\beta}(\psi)$ cycles on $\leavevmode\hbox
to9.9pt{\vbox to9.9pt{\pgfpicture\makeatletter\hbox{\hskip
4.95244pt\lower-4.95244pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{{{}} {}{}{}{}{}{}{}{}
}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{4.55244pt}{0.0pt}\pgfsys@curveto{4.55244pt}{2.51427pt}{2.51427pt}{4.55244pt}{0.0pt}{4.55244pt}\pgfsys@curveto{-2.51427pt}{4.55244pt}{-4.55244pt}{2.51427pt}{-4.55244pt}{0.0pt}\pgfsys@curveto{-4.55244pt}{-2.51427pt}{-2.51427pt}{-4.55244pt}{0.0pt}{-4.55244pt}\pgfsys@curveto{2.51427pt}{-4.55244pt}{4.55244pt}{-2.51427pt}{4.55244pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{K}$, we have that
$x^{\circ}_{t+1}={x^{\circ}_{t}}+{\beta}(x^{\circ}_{t}-x^{\circ}_{t-1})-{\gamma}\nabla\psi(x^{\circ}_{t})$,
thus

$\displaystyle\delta_{t+1}$
$\displaystyle=\delta_{t}+\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1})+(\beta+\delta_{\beta_{t}})(\delta_{t}-\delta_{t-1})-(\delta_{\gamma_{t}})\nabla\psi(x^{\circ}_{t})-(\gamma+\delta_{\gamma_{t}})\mu\delta_{t}-\gamma_{t}\delta_{g_{t}},$
$\displaystyle\delta_{t+1}$
$\displaystyle=\delta_{t}+\beta(\delta_{t}-\delta_{t-1})-\gamma\mu\delta_{t}+\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})-\gamma_{t}\delta_{g_{t}}.$

This can be written in an augmented space as

$\begin{pmatrix}\delta_{t+1}\\\
\delta_{t}\end{pmatrix}=\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\
1&0\end{pmatrix}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}+\begin{pmatrix}\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})-\gamma_{t}\delta_{g_{t}}\\\
0\end{pmatrix}.$

The second and third assumptions corresponds on the perturbations enable to
write that

$\displaystyle\left\|\begin{pmatrix}\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t}-\gamma_{t}\delta_{g_{t}})\\\
0\end{pmatrix}\right\|$
$\displaystyle\qquad=\|\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})-\gamma_{t}\delta_{g_{t}}\|$
$\displaystyle\qquad\leqslant|\delta_{\beta_{t}}|\|x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1}\|+|\delta_{\gamma_{t}}|\|\nabla\psi(x^{\circ}_{t})+\mu\delta_{t}\|+\gamma_{t}\|\delta_{g_{t}}\|$
$\displaystyle\qquad=\left(\frac{\sqrt{(1+\beta)^{2}(1-\cos(\theta_{K}))^{2}+(1-\beta)^{2}\sin(\theta_{K})^{2}}}{\gamma}+\mu\kappa_{P}r_{\max}\right)|\delta_{\gamma_{t}}|$
$\displaystyle\qquad\qquad+\left(\sqrt{(1-\cos(\theta_{K}))^{2}+\sin(\theta_{K})^{2}}+2\kappa_{P}r_{\max}\right)|\delta_{\beta_{t}}|+\frac{4}{L}\|\delta_{g_{t}}\|$
$\displaystyle\qquad\leqslant\left(\frac{4}{\gamma}+\mu\kappa_{P}r_{\max}\right)|\delta_{\gamma_{t}}|+\left({2}+2\kappa_{P}r_{\max}\right)|\delta_{\beta_{t}}|+\frac{4}{L}\|\delta_{g_{t}}\|$
$\displaystyle\qquad\leqslant\frac{1}{2}(1-\rho_{D})\kappa_{P}r_{\max}+\frac{1}{2}(1-\rho_{D})\kappa_{P}r_{\max}=(1-\rho_{D})\kappa_{P}r_{\max}.$

We now have

$\displaystyle\begin{pmatrix}\delta_{t+1}\\\ \delta_{t}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\
1&0\end{pmatrix}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}+\begin{pmatrix}\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})\\\
0\end{pmatrix}$ $\displaystyle=PDP^{-1}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}+\begin{pmatrix}\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})\\\
0\end{pmatrix}$ $\displaystyle P^{-1}\begin{pmatrix}\delta_{t+1}\\\
\delta_{t}\end{pmatrix}$ $\displaystyle=DP^{-1}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}+P^{-1}\begin{pmatrix}\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})\\\
0\end{pmatrix}$ $\displaystyle\left\|P^{-1}\begin{pmatrix}\delta_{t+1}\\\
\delta_{t}\end{pmatrix}\right\|$
$\displaystyle\leqslant\|D\|\left\|P^{-1}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}\right\|+\left\|P^{-1}\begin{pmatrix}\delta_{\beta_{t}}(x^{\circ}_{t}-x^{\circ}_{t-1}+\delta_{t}-\delta_{t-1})-\delta_{\gamma_{t}}(\nabla\psi(x^{\circ}_{t})+\mu\delta_{t})\\\
0\end{pmatrix}\right\|$
$\displaystyle\leqslant\rho_{D}\left\|P^{-1}\begin{pmatrix}\delta_{t}\\\
\delta_{t-1}\end{pmatrix}\right\|+\|P^{-1}\|_{\text{op}}(1-\rho_{D})\kappa_{P}r_{\max}$
$\displaystyle\overset{\text{by
induction}}{\leqslant}\rho_{D}\frac{r_{\max}}{\|P\|_{\text{op}}}+(1-\rho_{D})\frac{r_{\max}}{\|P\|_{\text{op}}}$
$\displaystyle=\frac{r_{\max}}{\|P\|_{\text{op}}},$

thereby reaching the desired claim. $\hfill\blacksquare$

###  D.2 Discussion about the reduction made in the proof of Theorem 5.3

In Theorem 5.3, we decompose the matrix
$\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\ 1&0\end{pmatrix}$ into the form
$PDP^{-1}$ with $\|D\|<1$. In this section, we discuss a possible way to do it
depending on the region in which $(\gamma,\beta)$ lies (see 2.1). In the 3
possible cases, we provide a decomposition $PDP^{-1}$ and $\rho_{D}=\|D\|<1$.
To compute $\kappa_{P}=\frac{1}{\|P\|_{\text{op}}\|P^{-1}\|_{\text{op}}}$, we
can use the fact that $\kappa_{P}^{2}$ is the ratio of the 2 eigenvalues of
the matrix $P^{T}P$:

$\displaystyle\kappa_{P}$
$\displaystyle=\left(\frac{\frac{\mathrm{Tr}(P^{T}P)}{2}-\sqrt{\left(\frac{\mathrm{Tr}(P^{T}P)}{2}\right)^{2}-\mathrm{Det}(P^{T}P)}}{\frac{\mathrm{Tr}(P^{T}P)}{2}+\sqrt{\left(\frac{\mathrm{Tr}(P^{T}P)}{2}\right)^{2}-\mathrm{Det}(P^{T}P)}}\right)^{1/2}=\left(\frac{\left(\frac{\mathrm{Tr}(P^{T}P)}{2}-\sqrt{\left(\frac{\mathrm{Tr}(P^{T}P)}{2}\right)^{2}-\mathrm{Det}(P^{T}P)}\right)^{2}}{\mathrm{Det}(P^{T}P)}\right)^{1/2}$
$\displaystyle=\frac{\frac{\mathrm{Tr}(P^{T}P)}{2}-\sqrt{\left(\frac{\mathrm{Tr}(P^{T}P)}{2}\right)^{2}-\mathrm{Det}(P)^{2}}}{|\mathrm{Det}(P)|}=\frac{\mathrm{Tr}(P^{T}P)}{2|\mathrm{Det}(P)|}-\sqrt{\left(\frac{\mathrm{Tr}(P^{T}P)}{2|\mathrm{Det}(P)|}\right)^{2}-1}.$

##### Lazy region ($\gamma<\frac{(1-\sqrt{\beta})^{2}}{\mu}$).

In this region,

$\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\ 1&0\end{pmatrix}\sim
D=\begin{pmatrix}\frac{1+\beta-\mu\gamma}{2}+\sqrt{\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}-\beta}&0\\\
0&\frac{1+\beta-\mu\gamma}{2}-\sqrt{\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}-\beta}\end{pmatrix}$

with the transition matrix
$P=\begin{pmatrix}\frac{1+\beta-\mu\gamma}{2}+\sqrt{\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}-\beta}\quad&\frac{1+\beta-\mu\gamma}{2}-\sqrt{\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}-\beta}\\\
1&1\end{pmatrix}$.

We then obtain
$\rho_{D}=\|D\|_{\mathrm{op}}=\frac{1+\beta-\mu\gamma}{2}+\sqrt{\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}-\beta}<1$.

##### Robust region ($\gamma>\frac{(1-\sqrt{\beta})^{2}}{\mu}$).

In this region,

$\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\ 1&0\end{pmatrix}\sim
D=\begin{pmatrix}\frac{1+\beta-\mu\gamma}{2}+i\sqrt{\beta-\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}}&0\\\
0&\frac{1+\beta-\mu\gamma}{2}-i\sqrt{\beta-\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}}\end{pmatrix}$

with the transition matrix
$P=\begin{pmatrix}\frac{1+\beta-\mu\gamma}{2}+i\sqrt{\beta-\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}}\quad&\frac{1+\beta-\mu\gamma}{2}-i\sqrt{\beta-\left(\frac{1+\beta-\mu\gamma}{2}\right)^{2}}\\\
1&1\end{pmatrix}$.

We then obtain $\rho_{D}=\|D\|_{\mathrm{op}}=\sqrt{\beta}<1$.

##### Boundary ($\gamma=\frac{(1-\sqrt{\beta})^{2}}{\mu}$).

On the boundary between the lazy and the robust regions,
$\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\ 1&0\end{pmatrix}$ is not
diagonalisable.

However, we can write $\begin{pmatrix}1+\beta-\mu\gamma&-\beta\\\
1&0\end{pmatrix}\sim D=\sqrt{\beta}\begin{pmatrix}1&\varepsilon\\\
0&1\end{pmatrix}$, with any $\varepsilon>0$ using the transition matrix
$P=\begin{pmatrix}\sqrt{\beta}&\frac{\varepsilon\sqrt{\beta}}{1+\beta}\\\
1&-\frac{\beta\varepsilon}{1+\beta}\end{pmatrix}$. We then obtain
$\rho_{D}=\|D\|=\sqrt{\beta}\sqrt{1+\frac{\varepsilon^{2}}{2}+\sqrt{\left(1+\frac{\varepsilon^{2}}{2}\right)^{2}-1}}=\sqrt{\beta}\left(\frac{\varepsilon}{2}+\sqrt{1+\frac{\varepsilon^{2}}{4}}\right)$.
Note $\rho_{D}<1$ if and only if $\varepsilon<\frac{1-\beta}{\sqrt{\beta}}$.

##  Appendix E Auxiliary proofs from Section 6

######  Definition E.1 (Mollifier $u_{\varepsilon}$, $\varepsilon>0$)

We define, for any $\varepsilon>0.$

$\displaystyle u(x)$
$\displaystyle:=\frac{1}{Z}e^{-\frac{1}{1-\|x\|^{2}}}\mathbf{1}_{\|x\|<1},$
$\displaystyle\text{with }Z:=\int_{\|x\|\leqslant
1}e^{-\frac{1}{1-\|x\|^{2}}}\mathrm{dx},\quad
u_{\varepsilon}(x):=\frac{1}{\varepsilon^{2}}u\left(\frac{1}{\varepsilon}x\right).$

We first recall some classical properties of $u_{\varepsilon}$, see for
example [Section 4.4 of 3, on mollifiers].

###### Lemma E.2

$\forall\varepsilon>0,u_{\varepsilon}$ is the probability density function
(pdf) of an $L^{\infty}$ and centered random variable.

######  Lemma E.3 ($C^{\infty}$ with compact support)

For any $\varepsilon>0$, $u_{\varepsilon}\in C^{\infty}$ and its support is
$B(0,\varepsilon)$.

######  Lemma E.4 (Bounded derivatives)

For any $\varepsilon>0$ and any $r\geqslant 0$,

$M^{(r)}_{\varepsilon}:=\sup_{x\in\mathbb{R}^{2}}\left\|\nabla^{r}u_{\varepsilon}(x)\right\|=\sup_{x\in
B(0,\varepsilon)}\left\|\nabla^{r}u_{\varepsilon}(x)\right\|<\infty.$

Let $\psi\in\mathcal{F}_{\mu,L}$. We consider $\varphi_{\varepsilon}=\psi\ast
u_{\varepsilon}$. We recall the following properties of
$\varphi_{\varepsilon}$.

######  Lemma E.5 (Higher-order derivatives are bounded)

Let $\psi\in\mathcal{F}_{\mu,L}$ and $\varphi_{\varepsilon}=\psi\ast
u_{\varepsilon}$. Then for any $\varepsilon>0$,

  1. 1.

$\varphi_{\varepsilon}\in C^{\infty}$

  2. 2.

for any $r\geqslant 2$ $\left\|\nabla^{r}(\varphi_{\varepsilon})\right\|$ is
bounded.

  3. 3.

$\varphi_{\varepsilon}\in\mathcal{F}_{\mu,L}$.

The proof of point 1 is standard, the one of point 2 uses that $\forall
x,\|\nabla^{2}\psi(x)\|\leqslant L$ and the properties of the convolution, and
finally, the proof of point 3 relies on the fact that $\forall\
x,\mu\leqslant\|\nabla^{2}\psi(x)\|\leqslant L$ and that $u_{\varepsilon}$ is
a probability density function.

##  Appendix F A summary of convergence rates on $\mathcal{F}_{\mu,L}$ and
$\mathcal{Q}_{\mu,L}$

For completeness and reference purposes, we summarize the convergence rates of
the algorithms under consideration of this work, on the functional classes
$\mathcal{F}_{\mu,L}$ and $\mathcal{Q}_{\mu,L}$. Table 3 provides the
algorithms and their respective worst-case converge rates in the sense of
Definition 1.3 expressed uniformly over $\kappa$, and approximately as
$\kappa\to 0$.

Table 3: Asymptotic convergence rates (on $\|x_{t}-x_{\star}\|$) for standard algorithms. Optimal convergence rates (lower and upper complexity bounds) are highlighted in boxes. Algorithm | Known convergence rate |  Approximate rate as $\kappa\rightarrow 0$
---|---|---
|  on $\mathcal{F}_{\mu,L}$ |  on $\mathcal{Q}_{\mu,L}$ |  on $\mathcal{F}_{\mu,L}$ |  on $\mathcal{Q}_{\mu,L}$
GD$(\gamma=1/L)$ |  $1-\kappa$
(see [25]) |  $1-\kappa$
(see [25]) |  $1-\kappa$ |  $1-\kappa$
GD$(\gamma=2/(L+\mu))$ |  $\frac{1-\kappa}{1+\kappa}$
(see [25]) |  $\frac{1-\kappa}{1+\kappa}$
(see [25]) |  $1-2\kappa$ |  $1-2\kappa$
Chebyshev’s method |  ? |  ${\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}}}$ (see [22]) |  ? |  ${1-2\sqrt{\kappa}}$
$\operatorname{HB}(\gamma^{\star}(\mathcal{Q}_{\mu,L}),\beta^{\star}(\mathcal{Q}_{\mu,L}))$ |  none (cycles)
(see [20]) |  ${\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}}}$ (see [22]) |  none (cycles) |  ${1-2\sqrt{\kappa}}$
$\operatorname{HB}(\gamma^{\star}(\mathcal{F}_{\mu,L}),\beta^{\star}(\mathcal{F}_{\mu,L}))$ |  $1-\Theta(\kappa)$
(3.7) |  $1-\Theta(\kappa)$
(Theorem 3.6) |  $1-\Theta(\kappa)$ |  $1-\Theta(\kappa)$
NAG $(\gamma=1/L,\beta=\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}})$ |  $(1-\sqrt{\kappa})^{1/2}$ (see [25]) |  $1-\sqrt{\kappa}$
(see [18]) |  $1-\tfrac{1}{2}\sqrt{\kappa}$ |  $1-\sqrt{\kappa}$
Information-theoretic exact method |  ${1-\sqrt{\kappa}}$
(see [30]) |  $1-\sqrt{\kappa}$
(see [30]) |  ${1-\sqrt{\kappa}}$ |  $1-\sqrt{\kappa}$
Triple momentum method |  ${1-\sqrt{\kappa}}$
(see [35]) |  $1-\sqrt{\kappa}$
(see [35]) |  ${1-\sqrt{\kappa}}$ |  $1-\sqrt{\kappa}$
Lower complexity bounds |  ${1-\sqrt{\kappa}}$ (see [6]) |  ${\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}}}$ (see [22]) |  ${1-\sqrt{\kappa}}$ |  ${1-2\sqrt{\kappa}}$