# Unavoidable patterns in locally balanced colourings

Nina Kamčev Department of Mathematics, Faculty of Science, University of
Zagreb<EMAIL_ADDRESS>Research supported by the European Union’s
Horizon 2020 research and innovation programme [MSCA GA No 101038085]. Alp
Müyesser  University College London<EMAIL_ADDRESS>
###### Abstract

Which patterns must a two-colouring of $K_{n}$ contain if each vertex has at
least $\varepsilon n$ red and $\varepsilon n$ blue neighbours? In this paper,
we investigate this question and its multicolour variant. For instance, we
show that any such graph contains a $t$-blow-up of an alternating 4-cycle with
$t=\Omega(\log n)$.

##  1 Introduction

Ramsey’s theorem guarantees that any $r$-edge-colouring of a large complete
graph yields a large monochromatic complete subgraph. In general, we cannot
guarantee the existence of anything but monochromatic subgraphs. Indeed,
nothing prevents the host graph from being monochromatic itself. However, in
recent years, there have been many results stating that in colourings where
each colour is well-represented, a richer family of patterns can be
guaranteed. The following, initially suggested by Bollobás [4], is a
prototypical result of this form. Here, $\mathcal{F}_{t}$ denotes the family
of $2$-edge-coloured complete graphs on $2t$ vertices in which one colour
forms either a complete bipartite graph with $t$ vertices on each side
$(K_{t,t})$ or a clique of order $t$ $(K_{t})$. See Figure 1 for a depiction
of the four colourings in $\mathcal{F}_{t}$ (up to isomorphism).

Figure 1: The $4$ types of colourings in $\mathcal{F}_{t}$. The circles denote
cliques of size $t$, whereas the lines connecting the circles denote complete
bipartite graphs. In the first row, one colour class forms a $K_{t,t}$,
whereas on the second row, one colour class forms a $K_{t}$.

######  Theorem 1.1 (Fox-Sudakov, Cutler-Montágh [8, 4]).

Let $G$ be a $2$-edge-coloured $K_{n}$ where each colour class has at least
$\varepsilon n^{2}$ edges, and suppose $n\geq(1/\varepsilon)^{16t}$. Then, $G$
contains a member of $\mathcal{F}_{t}$.

A probabilistic construction shows that the above is asymptotically tight up
to the constant factor in the exponent. The theorem is also optimal from a
structural standpoint. Namely, $2$-edge-colourings of $K_{n}$ where one colour
class forms two disjoint cliques of size $\lfloor n/2\rfloor$ and $\lceil
n/2\rceil$ or one colour class forms a $K_{cn}$ (with $c\sim\sqrt{2}/2$)
satisfy the hypothesis of Theorem 1.1 with $\varepsilon\sim 1/2$, and thus
certify that one cannot hope to find patterns which are more complex then
those in Figure 1. Similarly, Theorem 1.1 becomes false if we delete any of
the four patterns contained in $\mathcal{F}_{t}$.

There are numerous extensions of Theorem 1.1, including multi-colour and
infinite variants [1], variants where $K_{n}$ is replaced by another dense
host subgraph [13], and variants where $\varepsilon$ is allowed to depend on
$n$ [11, 2, 10]. In this paper, we are concerned with the following question,
initially raised by Wesley Pegden (personal communication).

######  Question 1.2.

Let $\varepsilon>0$. Suppose that $K_{n}$ is $2$-edge-coloured so that each
vertex is incident to at least $\varepsilon n$ edges in each colour. Which
subgraphs must $K_{n}$ necessarily contain?

We call $2$-coloured $K_{n}$ as in Question 1.2 locally
$\varepsilon$-balanced. Of course, this is a stronger hypothesis on the
colouring compared to Theorem 1.1. Hence, any locally $\varepsilon$-balanced
$K_{n}$ must contain a complete subgraph on $2t$ vertices where one colour
forms a $K_{t,t}$ or a $K_{t}$, where $t=\Omega(\log n)$. However, this is not
necessarily a complete answer to Question 1.2 as it cannot be the case that in
a locally $\varepsilon$-balanced $K_{n}$ one colour class consists entirely of
a clique. This motivates the following question: does any locally
$\varepsilon$-balanced $K_{n}$ contain a complete $2t$-vertex subgraph in
which one colour class forms a $K_{t,t}$?

The answer turns out to be negative for any value of $\varepsilon\leq 1/4$ and
$t\geq 2$. To see this, consider the following $2$-colouring of $K_{4k}$,
where each vertex is adjacent to at least $k$ red and blue edges, illustrated
in Figure 2 (labelled $P_{3}$). Partition $V(K_{4k})$ into four equal-sized
sets as $V_{1},V_{2},V_{3}$ and $V_{4}$. Colour all edges with both endpoints
in $V_{1}\cup V_{4}$ red, colour all edges with both endpoints in $V_{2}\cup
V_{3}$ blue, and colour edges between $V_{1}$, $V_{3}$, and between $V_{2}$,
$V_{4}$ red, and colour the remaining edges (between $V_{1}$, $V_{2}$ and
between $V_{3}$,$V_{4}$) blue. Denote by $\mathcal{P}_{k}$ the resulting
$2$-coloured $K_{4k}$ (so the number of vertices is $n=4k$). It is easy to see
that $\mathcal{P}_{k}$ contains no complete subgraph with $4$ vertices in
which one colour class form two disjoint cliques of size $2$ each. One can
also check that $\mathcal{P}_{k}$ is locally $1/4$-balanced.

Perhaps surprisingly, $\mathcal{P}_{k}$ is an optimal construction in the
following sense. For any $\varepsilon>0$, a locally
$(1/4+\varepsilon)$-balanced $K_{n}$ must contain large complete subgraphs
where one colour class forms a complete bipartite graph. Our first result
makes this precise, thereby answering Question 1.2 when $\varepsilon>1/4$.

######  Theorem 1.3.

Let $G$ be a $2$-coloured locally $(1/4+\varepsilon)$-balanced $K_{n}$, and
suppose $n\geq 2^{t\cdot 2^{-C\log(1/\varepsilon)^{8}}}$ for some absolute
constant $C$. Then, $G$ contains a complete subgraph on $2t$ vertices where
one colour class forms a $K_{t,t}$.

The earlier construction ($\mathcal{P}_{k}$) shows that Theorem 1.3 does not
hold when $1/4+\varepsilon$ is replaced by $1/4$. Moreover, $n$ has to be
exponentially large in $t$ for the conclusion to hold (e.g. by considering a
random colouring), but we believe that the dependence of $n$ on $\varepsilon$
should be far from optimal. We discuss this further in Section 5.

$P_{1}$$\overline{P_{1}}$$P_{2}$$P_{3}$$C_{4}$$M_{1}$$P_{3}^{\circ}$${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}1}$${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}2}$${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}3}$${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}4}$
Figure 2: An illustration of the relevant two-coloured and totally two-
coloured graphs

We now turn our attention to answering Question 1.2 when $\varepsilon\leq
1/4$. In light of the earlier construction ($\mathcal{P}_{k}$), it is not
clear at all if anything interesting can be said about this case. One might
guess there exists a $2$-colouring of $K_{n}$, say $\mathcal{P}^{\prime}_{k}$,
that is locally $1/8$-balanced, but $\mathcal{P}^{\prime}_{k}$ does not
contain a complete subgraph isomorphic to $\mathcal{P}_{2}$, or a complete
graph on $4$ vertices where one colour class forms two disjoint cliques of
size $2$. And perhaps, there exists another colouring which is locally
$1/16$-balanced, which does not contain $\mathcal{P}_{2}^{\prime}$ or any of
the former patterns. Hence, maybe, the answer to Question 1.2 is a family of
patterns $\mathcal{F}_{\varepsilon}$ which increases with $\varepsilon^{-1}$.
Indeed, Theorem 1.3 could feasibly be interpreted as evidence towards such a
phenomenon. Our next result rules out any such possibility in a strong sense,
demonstrating that the answer to Question 1.2 depends only on whether
$\varepsilon\leq 1/4$ or not.

######  Theorem 1.4.

Let $G$ be a $2$-coloured locally $\varepsilon$-balanced $K_{n}$, and suppose
$n\geq 2^{Ct/\varepsilon^{16}}$ for some absolute constant $C$. Then, $G$
contains a complete subgraph on $2t$ vertices where one colour class forms a
$K_{t,t}$, or a complete subgraph isomorphic to a $\mathcal{P}_{t}$.

Obtaining a better quantitative dependence between $n$ and $\varepsilon$
remains an intriguing challenge. We discuss this further in Section 5. We
remark also that the assertion in the abstract is a consequence of the above
result.

In [1], Theorem 1.1 was generalised to $r$-edge-colourings of $K_{n}$, and we
refer the reader to that paper to see what kind of patterns can be guaranteed
in the multicolour version of the problem. It is also natural to investigate a
locally balanced version of the multicolour problem. The situation here is
unexpectedly more difficult, as already for locally $\varepsilon$-balanced
$3$-colourings there is no straightforward analogue of Theorem 1.4. We
formalise this negative statement in Section 4, and obtain some complementary
positive results.

Organisation of the paper. In Section 3.2, we introduce a general tool to find
patterns (such as those depicted in Figure 3) efficiently in edge-coloured
complete graphs. Our main tool is a technique of Nikiforov which uses subgraph
count estimates to find large blow-ups of small subgraphs. This is in contrast
to many of the related results in this area for which the main tool is the
dependent random choice method. In Section 2.2, we compare these two
approaches and give an overview of the proofs of Theorems 1.3 and Theorems
1.4. Section 3 contains formal proofs of both of these results. In Section 4,
we treat the multicolour version of the problem.

##  2 Preliminaries and proof outline

###  2.1 Notation

In this subsection, in preparation to give an overview of the proofs, we
introduce and recall some notation. An $r$-edge-coloured (or just an
$r$-coloured) graph is a graph together with a labelled partition of its edge-
set into $r$ parts. We view the parts of this partition as being labelled by
different colours. We say that one coloured graph $G$ contains another
coloured graph $H$ if there exists an injection $\phi\colon V(H)\to V(G)$ such
that $(a,b)\in E(H)$ implies that $(\phi(a),\phi(b))\in E(G)$ and
$(\phi(a),\phi(b))$ has the same colour as $(a,b)$.

We say that a coloured graph $G$ is a homogeneous $t$-blow-up of another
coloured graph $H$ if $V(G)$ can be partitioned into $t$-sized sets
$V_{1},\cdots,V_{|V(H)|}$, each $G[V_{i}]$ is a monochromatic clique (in some
colour), and for each $(i,j)\in E(H)$ of colour $c$, $G[V_{i},V_{j}]$ is a
complete bipartite graph where each edge gets colour $c$.

An $r$-totally-coloured graph is a graph whose vertices as well as its edges
are given an $r$-colouring. A coloured graph $G$ is a $t$-blow-up of a
totally-coloured graph $H$ if $G$ is a $t$-blow-up of $H$ with respect to the
edge-colouring of $H$, and $G[V_{i}]$ is a monochromatic clique in the same
colour as the vertex $i\in H$.

If $G$ is $2$-coloured, $\overline{G}$ is used to denote the coloured graph
with the two colours interchanged.

We say that an $r$-coloured $G$ is locally $\varepsilon$-balanced if each
vertex of $G$ is incident to at least $\varepsilon|V(G)|$ edges in each of the
$r$ colours. We say that an $r$-coloured graph $G$ is globally
$\varepsilon$-balanced if each colour class has size at least
$\varepsilon\binom{n}{2}$.

For the convenience of the reader, in the following paragraph we collect every
coloured and totally coloured graph we make reference to throughout the paper.
For further clarity, in Figure 2, we provide an illustration of each of these
graphs.

Let $P_{1}$ be the totally-coloured $K_{2}$ with vertices receiving colour
red, and the unique edge receiving colour blue. Note that the $t$-blow-up of
$P_{1}$ is a blue induced $K_{t,t}$. Let $P_{2}$ be the totally-coloured
$K_{2}$ with one vertex receiving colour red, the other receiving colour blue,
and the edge receiving colour red. Let $P_{3}$ be the totally-coloured $K_{4}$
with edges $(1,2),(2,3),(3,4)$ and vertices $2$ and $3$ coloured blue, and all
other edges and vertices coloured red. Note that a $t$-blow-up of $P_{3}$ is
locally $1/4$-balanced. Moreover, let $P_{3}^{\circ}$ be the (not totally)
coloured graph obtained from $P_{3}$ by discarding the vertex colours. Let
$C_{4}$ be a $2$-edge-coloured $K_{4}$ with the red edges forming a $4$-cycle.
Let $M_{1}$ be the properly $2$-edge-coloured $K_{2,2}$.

With our notation, the aforementioned theorems can be stated as follows.

######  Theorem 1.1 (Fox-Sudakov, Cutler-Montágh).

Suppose $n\geq(1/\varepsilon)^{16t}$. Then, any globally
$\varepsilon$-balanced $2$-coloured $K_{n}$ contains a $t$-blow-up of one of
$P_{1}$, $P_{2}$, $\overline{P_{1}}$, $\overline{P_{2}}$.

######  Theorem 1.3.

Suppose $n\geq 2^{t\cdot 2^{-C\log(1/\varepsilon)^{8}}}$ for a sufficiently
large absolute constant $C$. Then, any locally $(1/4+\varepsilon)$-balanced
$2$-coloured $K_{n}$ contains a $t$-blow-up of $P_{1}$ or $\overline{P_{1}}$.

######  Theorem 1.4.

Suppose $n\geq 2^{Ct/\varepsilon^{16}}$ for a sufficiently large absolute
constant $C$. Then, any locally $\varepsilon$-balanced $2$-coloured $K_{n}$
contains a $t$-blow-up of $P_{1}$, $\overline{P_{1}}$, $P_{3}$.

Note that $\overline{P_{3}}$ is not included in the above list as
$\overline{P_{3}}=P_{3}$.

###  2.2 Proof overview

Although our proofs are short, the method is quite different from the other
papers in the area. In this section, we aim to motivate our approach and give
heuristic explanations for why Theorems 1.3 and 1.4 are true, at least
qualitatively (i.e. with some finite $n=n(t,\varepsilon)$). We begin with a
brief discussion of Theorem 1.1 in order to compare the different approaches.
It is rather straightforward to obtain a proof of Theorem 1.1 if one is only
concerned with obtaining $t$-blow-ups where $t$ tends to infinity with $n$.
Indeed, applying the well-known Kővari-Sós-Turán Theorem to both red and blue
colour classes, we can obtain one red and one blue $K_{s,s}$, say $T_{1}$ and
$T_{2}$, respectively, where $s\sim\log n$ (we can ensure that $T_{1}$ and
$T_{2}$ are vertex-disjoint). Apply Ramsey’s theorem to the four parts coming
from $T_{1}$ and $T_{2}$, and delete all vertices outside of the monochromatic
cliques guaranteed by this application. Similarly, for each pair of the $4$
parts, in turn, apply the Kővari-Sós-Turán theorem to the majority colour
class in the bipartite graph between the pair of parts to guarantee a
monochromatic complete bipartite subgraph, at each iteration reducing the size
of the parts logarithmically. This produces a $t$-blow-up of a totally-
coloured $K_{4}$ (where $t\to\infty$ as $n\to\infty$) where we do not have
precise control over the colouring; however, we know that the colouring is not
monochromatic (there exists at least one blue and one red edge). It is easy to
see that this implies that the totally-coloured $K_{4}$ must contain one of
$P_{1}$, $P_{2}$, $\overline{P_{1}}$, $\overline{P_{2}}$, as desired.

In [8], the dependent random choice method (see, e.g. [9]) is employed to
obtain optimal bounds for Theorem 1.1, eliminating the need for nested
applications of the Theorems of Ramsey and Kővari-Sós-Turán. However, the
argument still boils down to finding a blow-up of a totally-coloured graph
which is not monochromatic, thereby producing a structure which necessarily
contains one of the desired patterns. To prove Theorems 1.3 and 1.4, we find
blow-ups of totally-coloured graphs where each vertex is adjacent to edges of
both colours. The argument given in the previous paragraph is too weak to
achieve this, since it does not make use of the assumption that our colouring
is locally-balanced. The dependent random choice is quantitatively much
stronger, but does not give any additional structural information.

Hence, we need an argument which will make use of the global structure of the
colouring. Specifically, our main tool (Lemma 2.4), a strengthening of a
theorem due to Nikiforov [15], reduces the problem to finding certain small
subgraphs appearing in $G$ with a positive density. Using Lemma 2.4, the
statements of Theorem 1.3 and 1.4 reduce to the following two statements,
respectively.

######  Proposition 2.1.

There exists a constant $C_{1}$ such that the following holds. Any locally
$(1/4+\varepsilon)$-balanced 2-coloured $K_{n}$ contains
$2^{-C_{1}\log(1/\varepsilon)^{8}}n^{4}$ copies of $C_{4}$ or
$\overline{C_{4}}$.

######  Proposition 2.2.

Any locally $\varepsilon$-balanced $2$-coloured $K_{n}$ contains
$\varepsilon^{4}n^{4}/10^{5}$ copies of $P_{3}^{\circ},C_{4}$ or
$\overline{C_{4}}$.

A natural tool for proving statements such as Proposition 2.1 and 2.2 is the
Szemerédi Regularity Lemma and closely related removal lemmas (see, e.g.,
[3]). For the sake of obtaining better bounds and more cogent proofs, we do
not use the regularity method. However, the regularity method does provide a
shorter proof of a quantitatively weaker version of Proposition 2.1, and thus
Theorem 1.3. Indeed, using the Regularity Lemma, it is not hard to show that
the vertex set of a $2$-coloured $K_{n}$ with a vanishing density of both
$C_{4}$ and $\overline{C}_{4}$ can essentially (that is, after recolouring
$o(n^{2})$ edges)), be partitioned into a red and a blue clique. Such a
$2$-coloured $K_{n}$ can at best be locally $(1/4+o(1))$-balanced, by an easy
optimisation argument (see Proposition 3.5), implying Proposition 2.2.

Proposition 2.2 is, however, more subtle, since even finding a single copy of
the desired small subgraphs is a non-obvious extremal problem. To give some
intuition on why the statement holds, let us prove an idealised version of it.

######  Proposition 2.3.

Let $(A,B)$ be a $2$-coloured complete bipartite graph with $|A|,|B|>2$ so
that each vertex of $A$ has at least one blue neighbour, and each vertex of
$B$ has at least one red neighbour. Then, $(A,B)$ contains a cycle of length
$4$ whose edges are alternating red and blue.

###### Proof.

Suppose without loss of generality that $|A|>|B|$. Let $v,w\in A$. Suppose
there exists no alternating red and blue $4$-cycle. Observe that the blue
neighbourhood of $v$ must be contained in that of $w$, or vice versa,
otherwise we immediately obtain an alternating $4$-cycle. Hence, the
collection of blue neighbourhoods of vertices in $A$ forms a chain where the
smallest subset has at least one element, say $q\in B$, by assumption. Hence,
$q$ is in the blue neighbourhood of every vertex of $A$, meaning $q$ has no
red neighbours, a contradiction. ∎

To clarify the connection between Proposition 2.3 and Proposition 2.2, notice
that completing a colouring of an alternating red-blue 4-cycle to an edge-
colouring of $K_{4}$ yields a $C_{4},\overline{C_{4}}$ or a $P_{3}^{\circ}$.

Finally, we state our main technical tool, which allows us to deduce Theorems
1.3 and 1.4 from the aforementioned Propositions. Nikiforov [15] showed that
any graph with a positive density of $K_{\ell}$-copies contains a large
complete $\ell$-partite subgraph. We strengthen this statement to find
homogeneous blow-ups in $r$-coloured graphs. Recall that our definition of a
homogeneous blow-up in a coloured graph requires that the parts of the blow-up
induce monochromatic cliques, but the colours of the cliques are not
specified.

######  Lemma 2.4.

Let $H$ be an $\ell$-vertex $r$-coloured graph. Let $G$ be an $n$-vertex
$r$-coloured graph $G$ containing at least $cn^{\ell}$ copies of $H$. Then $G$
contains a homogeneous $t$-blow-up of $H$ with
$t\geq\min\left\\{\frac{c}{2\ell},\frac{1}{2r\log r}\right\\}^{\ell}\log n$.

Lemma 2.4 is proved in Section 3.2. We remark that the Lemma also gives a
short proof of Theorem 1.1 with the stronger hypothesis that $n\geq
2^{100t/\varepsilon}$. Indeed, an easy counting argument implies that any
globally $\varepsilon$-balanced 2-colouring of $K_{n}$ contains
$\Omega(\varepsilon n^{3})$ properly coloured two-edge paths (that is,
$K_{1,2}$-copies), so Lemma 2.4 yields a homogeneous $t$-blow-up of the non-
monochromatic edge-colouring of $K_{1,2}$. A simple case distinction then
gives a blow-up of $P_{1}$, $P_{2}$ or one of their complements. A similar
argument gives a concise proof (with a weaker dependence between $n$ and
$\varepsilon$) of Theorem 1.4 from [1] , which is a generalisation of Theorem
1.1 to an arbitrary number of colours, originally proved via nested
applications of the dependent random choice method.

##  3 Proofs for patterns in two-colourings

###  3.1 Proofs of the main theorems

We now show how the main theorems follow easily from the two propositions on
subgraph counts and Lemma 2.4.

###### Proof of Theorem 1.3.

By Proposition 2.1, we may assume (without loss of generality) that $G$
contains at least $2^{-C_{1}\log(1/\epsilon)^{8}}n^{4}$ copies of $C_{4}$. By
Lemma 2.4 applied with $c=2^{-C_{1}\log(1/\epsilon)^{8}}$, $G$ contains a
homogeneous $2^{-C\log(1/\epsilon)^{8}}\log n)$-blow-up of $C_{4}$ for some
absolute constant $C$. Note that by assumption on $n$,
$2^{-C\log(1/\epsilon)^{8}}\log n\geq t$. Let $V_{1},\ldots,V_{4}$ be the
parts of this blow-up, and recall that $G[V_{i}]$ are monochromatic cliques.

We claim that $G[V_{1}\cup V_{2}\cup V_{3}\cup V_{4}]$ contains a $t$-blow-up
of $P_{1}$ or $\overline{P_{1}}$. Assume the opposite. At least one vertex
part has to be blue, so assume that $G[V_{1}]$ is blue. Then $G[V_{2}]$ and
$G[V_{4}]$ are red, so they form a blow-up of $P_{1}$, which is a
contradiction. ∎

###### Proof of Theorem 1.4.

Proposition 2.2 implies that $G$ contains $\varepsilon^{4}n^{4}/10^{5}$ copies
of $C_{4}$, $\overline{C_{4}}$ or $P_{3}^{\circ}$ in $G$. Let
$t=\left(\varepsilon^{4}\cdot 10^{-6}\right)^{4}\log n$, noting that this
satisfies the claimed bound on $n(t,\varepsilon)$. In the cases with many
copies of $C_{4}$ or $\overline{C_{4}}$, the above argument from the proof of
Theorem 1.3 yields a $t$-blow-up of $P_{1}$ or $\overline{P_{1}}$. In the
latter case, applying Lemma 2.4, we obtain that $G$ contains a homogeneous
$(\varepsilon^{16}10^{-7}\log n)$-blow-up of $P_{3}^{\circ}$ on the vertex
parts $V_{1},V_{2},V_{3}$ and $V_{4}$. Suppose that this structure does not
contain the $t$-blow-up of a $P_{1}$ or $\overline{P}_{1}$, otherwise we are
done. Suppose that $G[V_{1}]$ is blue. Then $G[V_{3}]$ and $G[V_{4}]$ are red,
and hence they form a blow-up of $P_{1}$, contradiction. Hence $G[V_{1}]$ is
red, and consequently, $G[V_{2}]$ is blue, so $G[V_{4}]$ is red, and finally,
$G[V_{3}]$ is blue. This yields a $t$-blow-up of $P_{3}$, as required. ∎

###  3.2 Finding homogeneous blow-ups of small patterns

In this subsection, we prove Lemma 2.4, a variant of a result due to Nikiforov
[15]. The main ingredient is Lemma 3.1, which is about dense $\ell$-uniform
hypergraphs. Before stating and proving Lemma 3.1, we give the following
definitions which are central due to the inductive nature of the proof.

Let $\mathcal{H}$ be an $\ell$-partite $\ell$-uniform hypergraph $\mathcal{H}$
on parts $V_{1},\ldots,V_{\ell}$. We usually specify the members of
$E(\mathcal{H})$ as $\ell$-tuples $(v_{1},\ldots v_{\ell})$ (where $v_{i}\in
V_{i}$), but we also abuse notation by saying that $(v_{1},\ldots,v_{\ell})$
contains $v_{1}$, or by writing $(v_{1},\ldots
v_{\ell})=(v_{1},\ldots,v_{\ell-1})+v_{\ell}$. Let $K_{2}(\mathcal{H})$ be the
vertex pairs contained in edges of $\mathcal{H}$. Moreover, we write
$\partial\mathcal{H}$ for the collection of $(\ell-1)$-tuples
$(v_{1},\ldots,v_{\ell-1})$ which are contained in some edge
$(v_{1},\ldots,v_{\ell})$ of $\mathcal{H}$, with $v_{i}\in V_{i}$ for
$i\in[\ell]$. We emphasise that this notation is not standard since
$\partial\mathcal{H}$ only contains $(\ell-1)$-tuples from
$V_{1}\times\dots\times V_{\ell-1}$. Given a graph $G$ isomorphic to a
$K_{\ell}(m)$ (the complete $\ell$-partite graph with vertex parts of size
$m$), we say that $\mathcal{H}$ _covers_ $G$ if $E(G)\subset
K_{2}(\mathcal{H})$ and there are $m$ disjoint $S\in\mathcal{H}$ with
$S\subset V(G)$ (in other words, $\mathcal{H}$ contains a matching of size $m$
on $V(G)$).

######  Lemma 3.1.

Let $\mathcal{H}$ be an $\ell$-partite $\ell$-uniform hypergraph on parts
$V_{1},\ldots,V_{\ell}$ of size $n$ with least $\ell cn^{\ell}$ edges. Let
$\varphi$ be an $r$-colouring of the complete ($2$-uniform) graphs on
$V_{1},\ldots,V_{\ell}$. Then, there are vertex sets $S_{1},\ldots,S_{\ell}$
with $|S_{i}|\geq\left(\min\\{\frac{c}{2},\frac{1}{2r\log
r}\\}\right)^{\ell}\log n$ such that $\varphi$ is constant on each $S_{i}$,
and $\mathcal{H}$ covers the complete $\ell$-partite graph on
$S_{1},\ldots,S_{\ell}$.

To prove Lemma 3.1, we need the following lemma for finding unbalanced
complete bipartite graphs, which can be proved using the classical double
counting argument of Kővari, Sós and Turán [12].

######  Lemma 3.2 (Lemma 2 from [15]).

Let $F$ be a bipartite graph with parts $A$ and $B$. Let $|A|=m$, $|B|=n$ and
$c,\alpha\in(0,1/2)$. If $\alpha\log n\leq\frac{cm}{2}+1$ and $e(F)\geq cmn$,
then $F$ contains a complete bipartite graph with parts $S\subset A$ and
$T\subset B$ of size $|S|=\alpha\log n$ and $|T|>n^{1-\alpha/c}$.

We also need a standard upper bound on the $r$-colour Ramsey number due to
Erdős and Szekeres [5]. Namely, any $r$-colouring of $K_{n}$ contains a
monochromatic clique on $\frac{\log n}{r\log r}$ vertices. We emphasise that
we are mostly concerned with the case $r=2$. We can now proceed with the
proof.

###### Proof of Lemma 3.1.

Assume that $c\leq(r\log r)^{-1}$, since the statement for larger values of
$c$ then follows. We prove the statement by induction on $\ell$. The case
$\ell=1$ follows from Ramsey’s Theorem – a colouring of $K_{cn}$ contains a
monochromatic clique of size $(r\log r)^{-1}\log(cn)\geq(2r\log
r)^{-1}\log(n)\geq\frac{c}{2}\log n$. Assume that the statement holds for
$\ell-1$, and let $\mathcal{H}$ be as in the statement.

For a hypergraph $\mathcal{L}$ and $R=(v_{1},\ldots,v_{\ell-1})$, we write
$d_{\mathcal{L}}(R)$ for the number of edges of $\mathcal{L}$ containing $R$.
A standard deletion argument shows that there is
$\mathcal{L}\subset\mathcal{H}$ with $|\mathcal{L}|\geq(\ell-1)cn^{\ell}$ such
that

$\text{for any }R\in V_{1}\times\dots\times V_{\ell-1},\quad
d_{\mathcal{L}}(R)\geq cn\text{\ \ or \ \ }d_{\mathcal{L}}(R)=0;$ (1)

indeed, one can iteratively remove all edges containing $R$ for any $R$
violating (1), removing at most $cn\cdot n^{\ell-1}$ edges in total.

We have $|\partial\mathcal{L}|\geq|\mathcal{L}|/n\geq(\ell-1)cn^{\ell-1}$,
since each $R\in\partial\mathcal{L}$ is contained in at most $n$ edges of
$\mathcal{L}$. Applying the induction hypothesis to $\partial\mathcal{L}$, we
obtain sets $U_{1},\ldots U_{\ell-1}\subseteq V_{1},\ldots,V_{\ell-1}$ with
$|U_{i}|=m=\left(\frac{c}{2}\right)^{\ell-1}\log n$ such that
$\partial\mathcal{L}$ covers the complete $(\ell-1)$-partite graph on
$U_{1}\cup\ldots\cup U_{\ell-1}$, and $\varphi[U_{i}]$ is constant for each
$i\in[\ell-1]$.

Let $\mathcal{A}$ be a set of $m$ disjoint $(\ell-1)$-tuples in
$\partial\mathcal{L}$, which exists by the definition of a _covering_. The
graph structure of $K_{2}(\mathcal{L})$ will now be used by noticing that it
suffices to find a _large_ subset of vertices $T\subset V_{\ell}$ such that
$R+v_{\ell}\in\mathcal{L}$ for all $R\in\mathcal{A}$ and $v_{\ell}\in T$. To
this end, consider the bipartite graph $F$ with parts $\mathcal{A}$ and
$V_{\ell}$ such that $(R,v_{\ell})\in F$ whenever $R+v_{\ell}$ lies in
$\mathcal{L}$. Since $d_{\mathcal{L}}(R)>cn$ for all
$R\in\mathcal{A}\subset\partial\mathcal{L}$, we have $|F|\geq cmn$.

We can apply Lemma 3.2 with $s=\left(\frac{c}{2}\right)^{\ell}\log
n\leq\frac{c}{2}m+1$ and $t=n^{1-2^{-\ell}c^{\ell-1}}$. It follows that $F$
contains a complete bipartite graph with parts $\mathcal{A}^{\prime}$ and $T$
such that $|\mathcal{A}^{\prime}|=s$ and $|T|=t$. Let $G=K_{2}(\mathcal{L})$.
Let $S_{1},\ldots,S_{\ell-1}$ be the vertex sets of the edges of
$\mathcal{A}^{\prime}$, and recall that they induce a $K_{\ell-1}(s)$ in $G$
since $S_{i}\subset U_{i}$. Moreover, we claim that $wv_{\ell}$ is in $G$ for
any $v_{\ell}\in T$ and $w\in S_{i}$ with $i\in[\ell-1]$. This follows from
the fact that there is an $R\in\mathcal{A}^{\prime}$ containing $w$, and
$R+v_{\ell}\in\mathcal{L}$.

Finally, by Ramsey’s theorem, there is a subset $S_{\ell}\subset T$ with
$|S_{\ell}|=s=\left(\frac{c}{2}\right)^{\ell}\log n\leq\frac{1}{r\log
r}\log|T|$ on which $\varphi$ is constant. Recalling that $\varphi[S_{i}]$ is
constant for $i\in[\ell-1]$ by induction hypothesis, we obtain our desired
sets $S_{1},\ldots,S_{\ell}$. To verify that $\mathcal{L}$ covers
$S_{1},\ldots,S_{\ell}$, note that the edges of $\mathcal{A}^{\prime}$ with
the vertices of $S_{\ell}$ (in an arbitrary order) form a matching of size $s$
in $\mathcal{L}$. ∎

We now give the proof of Lemma 2.4.

###### Proof that Lemma 2.4 follows from Lemma 3.1.

Let $V_{1},\ldots,V_{\ell}$ be a uniformly random partition of the vertex set
of $G$ with parts of size at least $n^{\prime}=\lfloor\frac{n}{\ell}\rfloor$,
and associate $V_{1},\ldots,V_{\ell}$ to the vertices of
$v_{1},v_{2},\ldots,v_{\ell}$ of $H$. We say that a copy of $H$ in $G$ is
canonical with respect to this partition if $v_{i}$ is embedded to $V_{i}$ for
each $i\in[\ell]$. We claim that a copy of $H$ in $G$ is canonical with
probability at least $(n^{\prime}/n)^{\ell}$. Indeed, each vertex $v_{i}$ of
this $H$-copy is placed into $V_{i}$ with probability at least
$\frac{n^{\prime}}{n}$. Moreover, the events that the vertices of this
$H$-copy are placed into the corresponding parts are positively correlated,
which implies the lower bound $(n^{\prime}/n)^{\ell}$.

Hence, using linearity of expectation, we may assume that the number of
$H$-copies respecting our partition is at least
$\left(\frac{n^{\prime}}{n}\right)^{\ell}cn^{\ell}=cn^{\prime\ell}$. Let
$\mathcal{H}$ be the hypergraph corresponding to those copies. We may apply
Lemma 3.1 with $c^{\prime}=\frac{c}{\ell}$, to obtain the desired sets
$S_{1},\ldots S_{\ell}$ with
$|S_{i}|=\min\left\\{\frac{c}{2\ell},\frac{1}{2r\log r}\right\\}^{\ell}\log
n$. ∎

###  3.3 Small subgraphs in locally balanced colourings

We now prove Proposition 2.1, which follows immediately from Lemma 3.4 and
Proposition 3.5. As discussed above, in Lemma 3.4 we actually describe the
structure of colourings with a vanishing density of $C_{4}$ and
$\overline{C_{4}}$. We call a $2$-coloured $K_{n}$ split if its vertex set can
be partitioned into a red clique and a blue clique. We call two $2$-coloured
$K_{n}$ $\delta$-close if the first can be made isomorphic to the second after
flipping the colours of at most $\delta n^{2}$ many edges. The following
result can be thought of as a substitute for the regularity method which is
sufficient for our purposes.

######  Lemma 3.3 (Fox-Sudakov, [7] (Theorem 4.4)).

There exists an absolute constant $c$ such that for each $\varepsilon\in(0,1)$
and graph $H$ on $k$ vertices, there are constants
$\kappa:=(\varepsilon/4)^{k}2^{-c(k\log(1/\varepsilon))^{2}}$ and
$C=4/(\varepsilon 2^{-ck(\log(1/\varepsilon))^{2}})$ such the following holds.
For any $n$-vertex graph $G$ with fewer than $\kappa n^{k}$ induced copies of
$H$, there is an equitable partition of $V(G)$ into at most $C$ parts such
that each part induces a subgraph of density at most $\varepsilon$ or at least
$1-\varepsilon$.

We now use the above lemma to show that a $2$-coloured graph with a vanishing
density of $C_{4}$ and $\overline{C_{4}}$ is $o(1)$-close to being split.

######  Lemma 3.4.

There exists an absolute constant $C_{2}$ so that the following holds for any
$n$ and $\delta$. Let $G$ be a $2$-coloured $K_{n}$. Then, at least one of the
following is true.

  1. 1.

$G$ contains at least $2^{-C_{2}\log(1/\delta)^{8}}n^{4}$ many distinct copies
of $C_{4}$ or $\overline{C_{4}}$

  2. 2.

$G$ is $\delta$-close to being split.

###### Proof.

Suppose that $(1)$ does not hold. Then, by Lemma 3.3 applied with $\delta^{5}$
in place of $\varepsilon$, we have that there is an equitable partition of $G$
into at most

$C=4/(\delta^{5}2^{-4c(\log(1/\delta^{5}))^{2}})$

parts, each of which has either red or blue density above $1-\delta^{5}$. Let
us refer to the parts with high red density as red parts, and label them by
$V_{1},\ldots,V_{\ell}$.

We claim that $G[V_{1}\cup\dots\cup V_{\ell}]$ contains at most $\delta
n^{2}/2$ blue edges. If $\ell=1$, this is trivial, and otherwise it follows
from the following claim.

######  Claim 1.

Let $V_{i}$ and $V_{j}$ be two parts with density $\geq 1-\delta^{5}$ in red.
Then the bipartite graph $G[V_{i},V_{j}]$ has red density at least $1-\delta$.

###### Proof.

Suppose that the blue density between $V_{i}$ and $V_{j}$ is at least
$\delta$. It follows that the blue subgraph of $G[V_{i}\cup V_{j}]$ must
contain at least $2^{-10}\delta^{4}(n/C)^{4}$ copies of a cycle on $4$
vertices (see, for example, Theorem 1.9(iv) from [14]). At most
$2\delta^{5}(n/C)^{4}$ such $4$-cycles can contain a blue edge from $G[V_{i}]$
or $G[V_{j}]$, by the density assumption. The remaining $4$-cycles must
correspond to a copy of $\overline{C_{4}}$ in $G[V_{i}\cup V_{j}]$. Note that
for some absolute constant $C_{2}$, we have that $\delta^{4}(n/C)^{4}\geq
2^{-C_{2}\log(1/\delta)^{8}}n^{4}$, so as we assumed that $(1)$ does not hold,
we conclude that $G[V_{i},V_{j}]$ has red density at least $1-\delta$. ∎

The same argument implies that the union of blue parts contains at most
$\delta n^{2}/2$ blue edges. Hence, combining the red parts as well as the
blue parts gives a partition certifying that $G$ is $\delta$-close to a split
graph, as required. ∎

We now show that graphs which are $\delta$-close to being split cannot be
$(1/4+2\delta)$-balanced. When combined with Lemma 3.4, this immediately
implies Proposition 2.1.

######  Proposition 3.5.

If a $2$-coloured $K_{n}$ is $\delta$-close to being split, then it has a
vertex with at most $(1/4+3\delta)n$ red or at most $(1/4+3\delta)n$ blue
neighbours.

###### Proof.

Assume for the sake of a contradiction that $G$ is a $2$-coloured $K_{n}$ in
which all vertices have more than $(1/4+3\delta)n$ red and more than
$(1/4+3\delta)n$ blue neighbours. Consider a split graph $G^{\prime}$ which is
$\delta$-close to $G$. The vertex set of $G^{\prime}$ is the union of a red
clique $X$ and a blue clique $Y$. In $G$, the sum of the blue degrees of the
vertices in $X$ is $>(1/4+3\delta)n|X|$. Since $X$ contains at most $\delta
n^{2}$ blue edges by the $\delta$-closeness assumption between $G$ and
$G^{\prime}$, the edges inside $X$ contribute at most $2\delta n^{2}$ to the
previous sum. This implies that in $G$, between $X$ and $Y$, there are at
least $(1/4+\delta)n|X|$ blue edges. Similarly, we can derive that between $X$
and $Y$, there are at least $(1/4+\delta)n|Y|$ red edges, giving in total
$(1/4+\delta)n^{2}>n^{2}/4$ edges between two disjoint subsets of $G$. This is
a contradiction. ∎

Now we move on to Proposition 2.2. Recall that $M_{1}$ denotes a properly
$2$-edge-coloured $K_{2,2}$. The following lemma is a robust version of
Proposition 2.3. For a graph $G$, let $\delta_{G}(S)$ denote the minimum
degree of a vertex (in $G$) in $S\subset V(G)$.

######  Lemma 3.6.

Let $\varepsilon>0$, and consider a two-colouring $R\cup B$ of $K_{n,n}$ with
vertex parts $X,Y$ of order $n$ such that
$\delta_{R}(X),\delta_{B}(Y)\geq\varepsilon n$. Then, this two-colouring of
$K_{n,n}$ contains at least $\varepsilon^{4}n^{4}/150$ many distinct copies of
$M_{1}$.

###### Proof.

Let $A$ be the set of vertices in $X$ contained in at least
$\varepsilon^{3}n^{3}/72$ copies of $M_{1}$. We will show that
$|A|\geq\frac{\varepsilon n}{2}$. This implies the lemma, since the number of
copies of $M_{1}$ is at least $|A|\varepsilon^{3}n^{4}/150$.

Assume that $|A|<\frac{\varepsilon n}{2}$, and let $A^{\prime}=X\setminus A$.
Note that $\delta_{R}(A^{\prime}),\delta_{B}(Y)\geq\varepsilon n/2$ by the
assumption on the size of $A^{\prime}$. Let $v$ be a vertex of $A^{\prime}$
with minimum red degree, and let $S\subseteq Y$ be the red neighbourhood of
$v$. In $A^{\prime}\setminus\\{v\\}\times S$, there are at least $\varepsilon
n^{2}/3$ blue edges. It is well-known that every graph with density $\mu$
contains a subgraph with minimum degree $\mu n/2$. So,
$A^{\prime}\setminus\\{v\\}\times S$ has a subgraph $(C,D)$ with minimum blue
degree at least $\varepsilon n/6$ (in particular, $|C|,|D|\geq\varepsilon
n/6$). Observe now that for each element $d$ of $D$, each blue neighbour of
$d$ in $C$, say $c$, and each red neighbour of $c$ in $Y\setminus S$, say $b$,
$\\{v,d,c,b\\}$ induce a copy of $M_{1}$. This is because $(v,b)$ must be blue
by the assumption that $b\notin S$. There are $|D|\varepsilon n/6$ choices for
such $d$ and $c$, and we claim that any $c\in C$ has at least $\varepsilon
n/6$ red neighbours in $Y\setminus S$, all of which can play the role of $b$.
To see this, note that by minimality of $v$, $c$ must have at least $|S|$ red
neighbours in $Y$, and that at most $|S|-\varepsilon n/6$ of these neighbours
are contained in $S$ (since $c$ has at least $\varepsilon n/6$ blue neighbours
in $D\subset S$). Hence, we can find at least $\varepsilon^{3}n^{3}/72$
distinct triples $(d,c,b)$ giving rise to distinct $M_{1}$ containing $v$.
This contradicts the definition of $A$, so we conclude that
$|A|\geq\varepsilon n/2$. ∎

Proposition 2.2 follows easily from the previous result.

###### Proof of Proposition 2.2.

Let $G$ be locally $\varepsilon$-balanced 2-coloured $K_{n}$. By a standard
random sampling argument, we can deduce that $G$ contains some
$G^{\prime}=(X,Y)$ which satisfies the hypotheses of Lemma 3.6 with $n:=n/2$
and $\varepsilon:=\varepsilon/2$ (for example, Chernoff’s bound is sufficient
here). It follows by Lemma 3.6 that $G$ contains $\varepsilon^{4}n^{4}/10^{5}$
many distinct copies of $M_{1}$. Note that each edge is present in $M_{1}$, so
each copy of $M_{1}$ yields at least one copy of
$P_{3},\overline{P_{3}},C_{4}$ or $\overline{C_{4}}$ depending on the colour
of the edges not given by the $M_{1}$. This implies the proposition. ∎

##  4 Multiple colours

In this section, we investigate the $r$-colour variant of Question 1.2. To
allow for a more precise discussion, we give the following two definitions.
Given a totally-coloured graph $H$, the $t$-blow-up of $H$ is denoted by
$H[t]$. A totally $r$-coloured graph $H$ is called unibalanced if each vertex
of $H[2]$ is incident to an edge in each of the $r$ colours.111In other words,
$H$ is unibalanced if every vertex $v$ of $H$ is incident to each of the
available $r$ colours (the value of $r$ will be clear from context), where a
vertex $v$ is also considered incident to $c$ if it is coloured $c$. For
instance, the patterns $P_{1}$ and $P_{3}$ are unibalanced, but $P_{2}$ is
not. Observe that for a totally-coloured graph $H$, $H[t]$ is locally
$\varepsilon$-balanced for some value of $\varepsilon>0$ if and only if $H$ is
unibalanced. We call a family $\mathcal{F}$ of $r$-colourings of $K_{n}$
locally $(r,\varepsilon)$-unavoidable if every locally $\varepsilon$-balanced
colouring of $K_{n}$ where $n$ is sufficiently large contains a copy of some
$F\in\mathcal{F}$.

######  Question 4.1.

Suppose $K_{n}$ is given a locally $\varepsilon$-balanced $r$-edge-colouring.
Which subgraphs must $K_{n}$ necessarily contain?

Obviously, colourings as in Question 4.1 are globally $\varepsilon$-balanced
as well. In [1], a multicolour version of Theorem 1.1 is provided (see Theorem
4). This result guarantees, just using a global balancedness assumption, the
existence of a rich family of patterns, say $\mathcal{F}^{(r)}$, where each
pattern in the family uses all $r$ colours (see Figure 1 in [1] for a
depiction of patterns guaranteed when $r=3$). In particular,
$\mathcal{F}^{(r)}$ is locally $(r,\varepsilon)$-unavoidable for every
$\varepsilon>0$. Yet, $\mathcal{F}^{(r)}$ does not give a satisfying answer to
Question 1.2, for the same reason the family $\mathcal{F}_{t}$ (see Figure 1)
does not give a satisfying answer to Question 1.2. That is, elements of
$\mathcal{F}^{(r)}$ are not locally balanced, leaving open the possibility
that there exists either a smaller (as in Theorem 1.3) or more complex (as in
Theorem 1.4) family of unavoidable patterns. On the other hand, as in the two-
colour case, any $(r,\varepsilon)$-unavoidable family $\mathcal{F}$ consisting
of blow-ups of a finite family of unibalanced totally-coloured graphs
$\mathcal{F}^{\prime}$ (assuming that no member of $\mathcal{F}^{\prime}$
contains another member) would give a structurally optimal answer to Question
1.2). Indeed, members of such $\mathcal{F}$ would be themselves locally
$\varepsilon$-balanced for some $\varepsilon>0$, making it impossible for a
smaller, or more complex family of $(r,\varepsilon)$-unavoidable graphs to
exist (for $\varepsilon$ sufficiently small).

We can now explain why already for $r\geq 3$, the problem is rather different.
A consequence of Theorem 1.4 is that for any $\varepsilon>0$ and $t\geq 1$,
the family $\\{P_{1}[t],\bar{P_{1}}[t],P_{3}[t]\\}$ is
$(2,\varepsilon)$-unavoidable. For $r=3$, if $\mathcal{F}$ is a finite family
consisting of unibalanced totally-coloured graphs whose blow-ups are
$(3,\varepsilon)$-unavoidable, then the following proposition shows that
$|\mathcal{F}|$ has to have size at least $1/\varepsilon$.

Figure 3: A three-colouring of $K_{n}$ in which any locally balanced subgraph
has at least $6$ vertices, where $6$ is the number of parts. This colouring is
locally $(1/6)$-balanced. Colourings of this type (where two colour classes
form a blow-up of an alternating cycle) show that there is no analogue of
Theorem 1.4 for more than two colours.

######  Proposition 4.2.

There exists a locally $\varepsilon$-balanced $3$-colouring of $K_{n}$ in
which any unibalanced subgraph has at least $\lfloor\varepsilon^{-1}\rfloor-1$
vertices.

###### Proof.

Partition the vertex set into parts $V_{1},\ldots,V_{\ell}$ of order at least
$\varepsilon n$, where $\ell\geq\lfloor\varepsilon^{-1}\rfloor-1$ is an even
number. Colour the bipartite graphs between $V_{i}$ and $V_{i+1}$ red and blue
alternatingly (with indices modulo $\ell$). Colour the remaining edges green.
For an illustration of the case when $\ell=6$, see Figure 3. This colouring is
locally $\varepsilon$-balanced and any non-empty unibalanced subgraph of this
colouring must contain a vertex from each of $V_{1},\ldots,V_{\ell}$, as
required. ∎

Proposition 4.2 implies that there can be no straightforward generalisation of
Theorem 1.4 for more than two colours. That is, there is no single finite
family of unibalanced totally-coloured (with $r$ colours) graphs whose blow-
ups are $(r,\varepsilon)$-unavoidable for every $\varepsilon>0$. However, we
can still prove a version of Theorem 1.4, with the caveat that the size of the
family of unavoidable patterns depends on $\varepsilon$.

######  Theorem 4.3.

Given $\varepsilon>0$, an integer $r$, and
$C=\frac{80}{\varepsilon}\log\frac{1}{\varepsilon}$, there is a constant
$\alpha$ such that the following holds for sufficiently large $n$. Any locally
$\varepsilon$-balanced $r$-colouring of an $n$-vertex graph $G$ contains a
homogeneous $\alpha\log n$-blow-up of some unibalanced graph on at most $C$
vertices.

###### Proof.

Let $\varepsilon\gg\eta\gg\alpha\gg 1/n$. We have the following claim.

######  Claim 2.

There exists $k\leq C$ such that there are at least $\frac{1}{4}\binom{n}{k}$
vertex subsets $S$ of order $k$ inducing a unibalanced $r$-coloured subgraph.

###### Proof.

Denote the family of subsets $S\subset[n]$ which induce a unibalanced subgraph
by $\mathcal{U}$. Let $S$ be a random set of vertices where each vertex is
sampled independently with probability $\frac{\zeta}{n}$, with
$\zeta=\frac{20}{\varepsilon}\left(\log
r+\log\frac{1}{\varepsilon}\right)\leq\frac{C}{2}$. We will show that the
probability that $S\notin\mathcal{U}$ is at most $\frac{1}{2}$.

For $v\in V(G)$, let $A_{i}(v)$ be the event that there is a vertex $u\in S$
such that $uv$ has colour $i$ (note that this event does not depend on whether
$v$ is in $S$), and let $A(v)=\bigcap_{i\in[r]}A_{i}(v)$.

Since $A_{i}(v)$ are mutually independent for $i\in[r]$, we have

$\mathbb{P}\left[A(v)\right]=\prod_{i\in[r]}\mathbb{P}\left[A_{i}(v)\right].$

Moreover, by the locally $\varepsilon$-balancedness assumption, we have that
$\mathbb{P}\left[A_{i}(v)\right]\geq
1-\left(1-\frac{\zeta}{n}\right)^{\varepsilon n}\geq
1-e^{-\zeta\varepsilon/2}$ for $n$ sufficiently large, so

$\mathbb{P}\left[A(v)\right]\geq 1-re^{-\zeta\varepsilon/2}.$

Since $A(v)$ and $v\in S$ are independent events, we have, for any $v\in[n]$,

$\mathbb{P}\left[\overline{A(v)}\land v\in S\right]\leq\frac{\zeta}{n}\cdot
re^{-\zeta\varepsilon/2}$

Denoting the random variable counting the vertices $v\in S$ for which $A(v)$
does not occur by $X$ and substituting for $\zeta$, we have

$\displaystyle\mathbb{E}\left[X\right]$ $\displaystyle\leq\zeta
re^{-\zeta\varepsilon/2}\leq\frac{20}{\varepsilon}\left(\log
r+\log\frac{1}{\varepsilon}\right)re^{-10\log r+10\log\frac{1}{\varepsilon}}$
$\displaystyle\leq 40r^{2}\varepsilon^{-2}\cdot
r^{-10}\varepsilon^{10}<40\left(\varepsilon r^{-1}\right)^{8}<40\cdot
4^{-8}<\frac{1}{2}.$

Clearly, $S\notin\mathcal{U}$ only if $X\geq 1$. By Markov’s inequality, the
probability that $X\geq 1$ is at most $1/2$, so
$\mathbb{P}\left[S\notin\mathcal{U}\right]\leq\frac{1}{2}$, as claimed.

To complete the proof of the claim, assume that

$\left|\mathcal{U}\cap\binom{[n]}{k}\right|\leq\frac{1}{4}\binom{n}{k}\text{
\quad for all \quad}k\leq C.$ (2)

It follows that

$\mathbb{P}\left[S\in\mathcal{U}\right]\leq\sum_{k=0}^{C}\mathbb{P}\left[S\in\mathcal{U}\;\middle|\;|S|=k\right]+\mathbb{P}\left[|S|>C\right]\leq\sum_{k=0}^{C}\frac{1}{4}\cdot\mathbb{P}\left[|S|=k\right]+\frac{1}{8}\leq\frac{3}{8},$

where the second inequality follows from (2) and the Chernoff bound. We
reached a contradiction, completing the proof of the Claim. ∎

Hence, for some $k$-vertex unibalanced graph $H$, $G$ contains at least
$\frac{1}{4}r^{-C^{2}}\binom{n}{k}$ copies of $H$; to see this, note that
there are at most $r^{C^{2}}$ options for $H$. Applying Lemma 2.4, we obtain a
homogeneous $\alpha\log n$-blow-up of $H$, as required. ∎

##  5 Concluding remarks

Asymptotics. It remains an interesting open problem to improve the
quantitative estimates from Theorem 1.3 and Theorem 1.4. There is more room
for improvement in Theorem 1.3 compared to Theorem 1.4, but we believe both
estimates should be quite far away from the truth. In particular, we don’t see
an inherent reason why the asymptotics of the locally balanced Ramsey problem
should be different from the globally balanced Ramsey problem. That is, we
believe that there should be an absolute constant $C$ so that when
$n\geq(1/\varepsilon)^{Ct}$, the conclusions of Theorems 1.3 and 1.4 hold.
Such a bound would be of the same order of magnitude as the bound from Theorem
1.1. This bound would also be tight up to the value of $C$, as can be
justified with a simple probabilistic construction.

The main obstacle to proving a bound of this form comes from our reliance on
Lemma 2.4. Fox, Luo, and Wigderson [6] have recently combined the method of
Nikiforov with ideas from graph regularity to obtain better estimates for a
version of Lemma 2.4 where the blow-up guaranteed is not necessarily
homogeneous. Their ideas could quite possibly be modified to guarantee
homogeneous blow-ups, but the resulting bound would still be rather far from
being able to prove optimal bounds for Theorems 1.3 and 1.4.

The extremal aspect. A fruitful direction of research in the globally balanced
version of the problem has been finding patterns in globally
$\varepsilon$-balanced $K_{n}$ where $\varepsilon$ is a function of $n$. This
seems to be an intriguing direction in the locally balanced setting as well,
especially in the setting of Theorem 1.4. Namely, we raise the following
problem. Let $t\geq 1$ be some integer. What is the smallest function
$\varepsilon:=\varepsilon(n,t)$ as $n\to\infty$ such that any locally
$\varepsilon$-balanced $2$-coloured $K_{n}$ contains a $t$-blow-up of $P_{1}$,
$\overline{P_{1}}$ or $P_{3}$? It already seems like an interesting challenge
to prove $\varepsilon\leq n^{C/t^{2}}$ for some absolute constant $C$.

## Acknowledgements

We are grateful to Kyriakos Katsamaktsis for stimulating discussions at the
early stages of this project, especially for the formulation of Lemma 3.6, and
to Shoham Letzter for helpful comments on the manuscript.

## References

  * [1] Matthew Bowen, Ander Lamaison, and Alp Müyesser.  Finding unavoidable colorful patterns in multicolored graphs.  The Electronic Journal of Combinatorics, 27, 2020.
  * [2] Yair Caro, Adriana Hansberg, and Amanda Montejano.  Unavoidable chromatic patterns in 2-colorings of the complete graph.  Journal of Graph Theory, 97(1):123–147, 2021.
  * [3] David Conlon and Jacob Fox.  Graph removal lemmas.  In Surveys in combinatorics 2013, volume 409 of London Math. Soc. Lecture Note Ser., pages 1–49. Cambridge Univ. Press, Cambridge, 2013\.
  * [4] Jonathan Cutler and Balázs Montágh.  Unavoidable subgraphs of colored graphs.  Discrete Mathematics, 308(19):4396–4413, 2008.
  * [5] Paul Erdős and George Szekeres.  A combinatorial problem in geometry.  Compositio Math., 2:463–470, 1935.
  * [6] Jacob Fox, Sammy Luo, and Yuval Wigderson.  Extremal and Ramsey results on graph blowups.  J. Comb., 12(1):1–15, 2021.
  * [7] Jacob Fox and Benny Sudakov.  Induced Ramsey-type theorems.  Advances in Mathematics, 219(6):1771–1800, 2008.
  * [8] Jacob Fox and Benny Sudakov.  Unavoidable patterns.  Journal of Combinatorial Theory, Series A, 115(8):1561–1569, 2008\.
  * [9] Jacob Fox and Benny Sudakov.  Dependent random choice.  Random Structures Algorithms, 38(1-2):68–99, 2011.
  * [10] António Girão and Robert Hancock.  Two Ramsey problems in blowups of graphs.  arXiv preprint arXiv:2205.12826, 2022.
  * [11] António Girão and Bhargav Narayanan.  Turán theorems for unavoidable patterns.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 172, pages 423–442. Cambridge University Press, 2022.
  * [12] Thomas Kővari, Vera Sós, and Pál Turán.  On a problem of K. Zarankiewicz.  Colloq. Math., 3:50–57, 1954.
  * [13] Alp Müyesser and Michael Tait.  Turán-and Ramsey-type results for unavoidable subgraphs.  Journal of Graph Theory, 2020.
  * [14] Zoltán Lóránt Nagy.  Supersaturation of $C_{4}$: from Zarankiewicz towards Erdős-Simonovits-Sidorenko.  European J. Combin., 75:19–31, 2019.
  * [15] Vladimir Nikiforov.  Graphs with many $r$-cliques have large complete $r$-partite subgraphs.  Bull. Lond. Math. Soc., 40(1):23–25, 2008.


# Tight Convergence Rate in Subgradient Norm of the Proximal Point Algorithm

Guoyong Gu Department of Mathematics, Nanjing University, Nanjing, 210093,
China.Email<EMAIL_ADDRESS>This author was supported by the NSFC grant
11671195. Junfeng Yang11footnotemark: 1 Email<EMAIL_ADDRESS>This author
was supported by the NSFC grant 11771208.

###### Abstract

Proximal point algorithm has found many applications, and it has been playing
fundamental roles in the understanding, design, and analysis of many first-
order methods. In this paper, we derive the tight convergence rate in
subgradient norm of the proximal point algorithm, which was conjectured by
Taylor, Hendrickx and Glineur [SIAM J. Optim., 27 (2017), pp. 1283–1313]. This
sort of convergence results in terms of the residual (sub)gradient norm is
particularly interesting when considering dual methods, where the dual
residual gradient norm corresponds to the primal distance to feasibility.

Keywords: proximal point algorithm, performance estimation framework,
subgradient norm, tight convergence rate.

##  1 Introduction

Consider the unconstrained minimization problem

$\min_{x\in\mathbb{R}^{n}}f(x).$ (1.1)

Here, the objective function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ is a convex, closed
and proper (not necessarily differentiable) function, which is denoted by
$\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$ in the sequel. Since the objective
function $f$ is extended real valued, constraints such as nonnegativity, box
and/or ball constraints, can simply be absorbed into the objective function
via the indicator functions. Therefore, model (1.1) encompasses a broad class
of convex optimization problems.

Let $\langle\cdot,\cdot\rangle$ be the standard dot inner product and $B$ any
symmetric positive definite matrix of order $n$. Assume that $\mathbb{R}^{n}$
is endowed with the weighted inner product $\langle x,y\rangle_{B}:=\langle
Bx,y\rangle$ for $x,y\in\mathbb{R}^{n}$. Then, the induced Euclidean norm and
its dual norm are, respectively, given by

$\displaystyle\|x\|_{B}=\sqrt{\langle
Bx,x\rangle}\text{~{}~{}and~{}~{}}\|u\|_{B^{-1}}$ $\displaystyle=\sqrt{\langle
u,B^{-1}u\rangle},\quad x,u\in\mathbb{R}^{n}.$

Particularly, when $B$ equals to an identity matrix, both the Euclidean norm
and its dual will be denoted as $\|\cdot\|$ for simplicity. The proximal
mapping of $f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$ is defined by

$\operatorname{prox}_{\alpha
f}(x)=\operatorname{argmin}_{y\in\mathbb{R}^{n}}\Bigl{\\{}\alpha
f(y)+\frac{1}{2}\|y-x\|_{B}^{2}\Bigr{\\}},\ \text{for
}\alpha>0\text{~{}and~{}}x\in\mathbb{R}^{n}.$ (1.2)

The proximal mapping is uniquely well defined for any $x\in\mathbb{R}^{n}$ as
the objective function in (1.2) is strongly convex with respect to $y$. In
this paper, we focus on the proximal point algorithm (PPA, Algotithm 1) for
solving the aforementioned minimization problem (1.1).

input : Objective function: $f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$,
starting point: $x_{0}\in\mathbb{R}^{n}$,number of steps: $N$ (a positive
integer),and step lengths: $\\{\alpha_{i}\\}_{i=1}^{N}$ with $\alpha_{i}>0$.

for  _$i=1:N$_ do

$x_{i}=\operatorname{prox}_{\alpha_{i}f}(x_{i-1}).$ (1.3)

end for

Algorithm 1 Proximal point algorithm (PPA)

It then follows from (1.2), (1.3) and the Fermat’s rule that

$0\in\alpha_{i}\partial f(x_{i})+B(x_{i}-x_{i-1}),\text{ i.e.,
}\frac{B(x_{i-1}-x_{i})}{\alpha_{i}}\in\partial f(x_{i}).$ (1.4)

PPA dates back to [14]. It was firstly introduced to the optimization
community in [12], and later analyzed and refined by Rockafellar [17] and
Güler [6, 7]. For some recent surveys, we refer to the works of Combettes and
Pesquet [1], Parikh and Boyd [16], and so on.

###  1.1 Convergences in function and subgradient values

The standard convergence result in terms of the function value for the PPA is
provided by Güler [6, Theorem 2.1]:

$f(x_{N})-f(x_{*})\leq\frac{R^{2}}{2\sum_{i=1}^{N}\alpha_{i}},$

for any starting point $x_{0}\in\mathbb{R}^{n}$ satisfying
$\|x_{0}-x_{*}\|_{B}\leq R$, where $R>0$ is a constant and
$x_{*}\in\mathbb{R}^{n}$ is an optimal solution. Recently, by using the
performance estimation framework, this upper bound was improved by a factor of
2 by Taylor et al.:

######  Theorem 1.1 ([20, Theorem 4.1]).

Let $\\{\alpha_{i}\\}_{i\geq 1}$ be a sequence of positive step sizes and
$x_{0}\in\mathbb{R}^{n}$ some initial iterate satisfying
$\|x_{0}-x_{*}\|_{B}\leq R$ for some optimal point $x_{*}$. Any sequence
$\\{x_{i}\\}_{i\geq 1}$ generated by the PPA with step sizes
$\\{\alpha_{i}\\}_{i\geq 1}$ applied to a function
$f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$ satisfies

$f(x_{N})-f(x_{*})\leq\frac{R^{2}}{4\sum_{i=1}^{N}\alpha_{i}},$

and this bound cannot be improved, even in dimension one.

The tightness of the bound provided in Theorem 1.1 is illustrated by the
$l_{1}$-shaped one dimensional function

$f(x)=\frac{\sqrt{B}R|x|}{2\sum_{i=1}^{N}\alpha_{i}}=\frac{R\|x\|_{B}}{2\sum_{i=1}^{N}\alpha_{i}}\in\mathcal{F}_{0,\infty}(\mathbb{R}),$

for which $x_{*}=0$. Here, $B>0$ is a constant and the starting point
$x_{0}=-R/\sqrt{B}$ is used in the PPA.

If the residual (sub)gradient norm is used as the convergence measure, strong
numerical evidence based on performance estimation suggests the following
conjecture.

######  Conjecture 1.2 ([20, Conjecture 4.2]).

Let $\\{\alpha_{i}\\}_{i\geq 1}$ be a sequence of positive step sizes and
$x_{0}\in\mathbb{R}^{n}$ some initial iterate satisfying
$\|x_{0}-x_{*}\|_{B}\leq R$ for some optimal point $x_{*}$. For any sequence
$\\{x_{i}\\}_{i\geq 1}$ generated by the PPA with step sizes
$\\{\alpha_{i}\\}_{i\geq 1}$ on a function
$f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$, there exists for every iterate
$x_{N}$ a subgradient $g_{N}\in\partial f(x_{N})$ such that

$\|g_{N}\|_{B^{-1}}\leq\frac{R}{\sum_{i=1}^{N}\alpha_{i}}.$

In particular, the choice $g_{N}=\frac{x_{N-1}-x_{N}}{\alpha_{N}}$ is a
subgradient satisfying the inequality.

This bound cannot be improved, as it is attained by the one-dimensional
$l_{1}$-shaped function

$f(x)=\frac{\sqrt{B}R|x|}{\sum_{i=1}^{N}\alpha_{i}}\in\mathcal{F}_{0,\infty}(\mathbb{R})$
(1.5)

started from $x_{0}=-R/\sqrt{B}$.

###  1.2 The contribution and organization of the paper

PPA has been playing fundamental roles both theoretically and algorithmically
in the optimization area [17, 6, 7, 23, 13, 11]. Even the convergence rate of
the famous alternating direction method of multipliers can be established
within the framework of PPA, see, e.g., [8].

Convergence rate in terms of the residual (sub)gradient norm is particularly
interesting when considering dual methods. In that case, the dual residual
gradient norm corresponds to the primal distance to feasibility [2]. Moreover,
the (sub)gradient norm is more amenable than function value in nonconvex
optimization.

By using performance estimation framework [3, 20, 21], Conjecture 1.2, i.e.,
Conjecture 4.2 of [20] is proved in this paper, which gives the first direct
proof of the convergence rate in terms of the residual (sub)gradient norm for
PPA. In addition, this convergence rate for PPA is tight, which means it is
the best bound one can derive. Note that the convergence rate in terms of the
residual (sub)gradient norm can be proved by combing the convergence rate in
terms of $f(x_{N})-f(x_{*})$ or $\|x_{N}-x_{*}\|$ with the $L$-smoothness of
$f$ [20, 15], and this kind of proof is considered to be indirect. We want to
add that the $L$-smoothness of $f$ is not required in our setting.

At first, our analysis will be restricted to the case when $B$ is the identity
matrix, i.e., under the norm $\|\cdot\|$. After that, we will show that the
analysis can easily be extended to the case using a more general norm
$\|\cdot\|_{B}$. The rest of this paper is organized as follows. In the next
section, the performance estimation framework is briefly recalled and the
worst-case complexity bound is computed numerically via solving a semidefinite
programming (SDP) reformulation. In Section 3, the analytical optimal Lagrange
multipliers is constructed based on the numerical solutions of the SDP. In
Section 4, Conjecture 1.2, i.e., Conjecture 4.2 of [20] is proved under the
norm $\|\cdot\|$, which is then extended to the case with the more general
norm $\|\cdot\|_{B}$. Finally, some concluding remarks are drawn in Section 5.

##  2 Performance estimation and numerical results

Performance estimation was originally developed by Drori and Teboulle [3].
Their approach is based on semidefinite relaxations, and was taken further by
Kim and Fessler [10], who derived analytically the optimized gradient method.
By using convex interpolation and smooth (strongly) convex interpolation, the
performance estimation problems can be transformed into SDP problems without
any relaxation by Taylor et al. [21, 20, 22]. Recently, the performance
estimation was extended by Ryu et al. [18] to study operator splitting methods
for monotone inclusion problems. In [5], the authors established tight
nonergodic sublinear convergence rate of the PPA for solving maximal monotone
inclusion problems. More recently, an accelerated proximal point type
algorithm for maximal monotone operator inclusion problems has been derived in
[9].

###  2.1 Performance estimation and SDP reformulation

Under the Euclidean norm $\|\cdot\|$, the worst case performance of the PPA
(as given in Algorithm 1) with residual subgradient norm as performance
measure can be formulated as the optimal value of the following performance
estimation problem:

$\displaystyle\sup_{f,x_{*},x_{0},x_{1},\ldots,x_{N},g_{N}}$
$\displaystyle\|g_{N}\|$ (PEP) s.t. $\displaystyle
f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n}),$ $\displaystyle\|x_{0}-x_{*}\|\leq
R,$ $\displaystyle x_{*}\in\arg\min_{x}f(x),$ $\displaystyle x_{i}\text{ is
determined by \eqref{ppa} for }1\leq i\leq N,$ $\displaystyle
g_{N}=\frac{x_{N-1}-x_{N}}{\alpha_{N}}\in\partial f(x_{N}).$

Suppose that $\|g_{N}\|$ attains some value at a
$\tilde{f}\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$ with optimal solution
$x_{*}$ and initial iterate $x_{0}$, then the same value of the subgradient
norm can be attained at $f(\cdot)=\tilde{f}(\cdot+x_{*})-\tilde{f}(x_{*})$
with optimal solution $0$ and initial iterate $x_{0}-x_{*}$. This implies that
we may assume that $x_{*}=0$ and $f(x_{*})=0$ without affecting the optimal
value of the (PEP).

Due to the black-box property, the PPA is determined only by the function
values and the subgradients at its iterates. According to the definition of
$\mathcal{F}_{\mu,L}$-interpolation [21, Definition 2] or [20, Definition
1.1], the iterates of the PPA, along with the function values and subgradients
at these iterates, can be considered as optimization variables instead of
function $f$ itself. As a result, the optimization problem (PEP) can be
rewritten as

$\displaystyle\sup_{f_{1},\ldots,f_{N},x_{0},x_{1},\ldots,x_{N},g_{1},\ldots,g_{N}}$
$\displaystyle\|g_{N}\|$ s.t. $\displaystyle\|x_{0}\|\leq R,$ $\displaystyle
x_{i}\text{ is determined by \eqref{ppa} for }1\leq i\leq N,$
$\displaystyle\bigl{\\{}(0,0,0),(x_{1},g_{1},f_{1}),\ldots,(x_{N},g_{N},f_{N})\bigr{\\}}\text{
is }\mathcal{F}_{0,\infty}\text{-interpolable,}$ $\displaystyle\text{where
}f_{i}=f(x_{i}),\ g_{i}=\frac{x_{i-1}-x_{i}}{\alpha_{i}},\text{ for }1\leq
i\leq N.$

Remember that $(0,0,0)$ in the interpolation set
$\bigl{\\{}(0,0,0),(x_{1},g_{1},f_{1}),\ldots,(x_{N},g_{N},f_{N})\bigr{\\}}$
corresponds to the optimal solution $x_{*}=0$, $0\in\partial f(0)$, and the
optimal value $f(0)=0$. In view of [20, Theorem 3.3],
$\bigl{\\{}(0,0,0),(x_{1},g_{1},f_{1}),\ldots,(x_{N},g_{N},f_{N})\bigr{\\}}$
is $\mathcal{F}_{0,\infty}$-interpolable if and only if

$\displaystyle f_{i}$ $\displaystyle\geq 0+\langle 0,x_{i}-0\rangle,\ 1\leq
i\leq N,$ $\displaystyle 0$ $\displaystyle\geq f_{i}+\langle
g_{i},0-x_{i}\rangle,\ 1\leq i\leq N,$ $\displaystyle f_{j}$
$\displaystyle\geq f_{i}+\langle g_{i},x_{j}-x_{i}\rangle,\ 1\leq i,j\leq N,\
i\neq j.$

By replacing the $\mathcal{F}_{0,\infty}$-interpolable condition with the last
inequalities and eliminating $g_{i}$, the optimization problem (PEP) may
further be rewritten as

$\displaystyle\sup_{f_{1},\ldots,f_{N},x_{0},x_{1},\ldots,x_{N}}$
$\displaystyle\|x_{N-1}-x_{N}\|^{2}/\alpha_{N}^{2}$ (2.1) s.t.
$\displaystyle\|x_{0}\|^{2}\leq R^{2},$ $\displaystyle f_{i}\geq 0,\ 1\leq
i\leq N,$ $\displaystyle 0\geq
f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},-x_{i}\bigr{\rangle},\
1\leq i\leq N,$ $\displaystyle f_{j}\geq
f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},x_{j}-x_{i}\bigr{\rangle},\
1\leq i,j\leq N,\ i\neq j.$

Here, both the objective function and the constraint $\|x_{0}\|\leq R$ are
squared. These changes make the objective function and all the constraints
simple quadratic functions over the iterates, while neither one affects the
optimal solution.

We gather the iterates of the PPA and the function values at these iterates in
the following matrices

$\displaystyle P$
$\displaystyle=\bigl{[}x_{0},x_{1},\ldots,x_{N}\bigr{]}\in\mathbb{R}^{n\times(N+1)},$
$\displaystyle F$
$\displaystyle=\bigl{[}f_{1},f_{2},\ldots,f_{N}\bigr{]}\in\mathbb{R}^{1\times
N}.$

In addition, we introduce the Gram matrix $G=P^{T}P\in\mathbb{S}^{N+1}_{+}$.
Notice that the rank of the Gram matrix $G$ is less than or equal to $n$. On
the other side, to reconstruct the matrix $P$ from $G$, we need that the
dimension $n$ is greater than or equal to the rank of $G$, which is upper
bounded by $N+1$. By replacing the optimization variables with $F$ and $G$, we
obtain an equivalent SDP problem, linear in $F$ and $G$, with rank constraint
rank$(G)\leq n$. Since the worst case iteration bound is considered, the
dimension $n$ can be chosen freely. Hence, dropping the rank constraint does
not incur any relaxation.

Similar reformulations have been adopted in [20, 21, 4, 18]. Below, the SDP,
with the rank constraint being dropped, is referred to as the primal SDP, and
it shares the same optimal objective function value and the Lagrange
multipliers with the optimization problem (2.1).

###  2.2 Numerical results

SeDuMi [19] is utilized to solve the primal SDP, i.e., the SDP reformulation
of the (PEP). For $R=1$, $N=20$, and the sequence of positive step lengths
$\\{\alpha_{i}\\}_{i=1}^{N}$ being randomly drawn from the uniform
distribution between $0$ and $1$, the absolute difference between the
numerically computed optimal value of $\|g_{N}\|$ and the upper bound in
Conjecture 1.2, namely $1/{\sum_{i=1}^{N}\alpha_{i}}$, is around $10^{-8}$. In
addition, the Gram matrix $G$ computed is of rank one. The same phenomenon has
been observed for many tests on other values of $N$. This implies that there
is a $f\in\mathcal{F}_{0,\infty}(\mathbb{R})$ in one-dimensional space, which
attains this bound.

In fact, if the upper bound of the subgradient norm $\|g_{N}\|$ can be
expressed as the quotient of two linear functions of
$\\{\alpha_{i}\\}_{i=1}^{N}$, the coefficients to these
$\\{\alpha_{i}\\}_{i=1}^{N}$ can be found by solving a system of linear
equations. First, by multiplying both sides with the denominator, a linear
equation over the coefficients of these $\\{\alpha_{i}\\}_{i=1}^{N}$ can be
derived for each fixed sequence $\\{\alpha_{i}\\}_{i=1}^{N}$. Then, by
choosing different sequence of positive step lengths
$\\{\alpha_{i}\\}_{i=1}^{N}$, a system of linear equations over these
coefficients can be constructed, and from which these coefficients can be
recovered numerically.

##  3 The analytical Lagrange multipliers

The optimization problem (2.1) and the primal SDP share the same Lagrange
multipliers. These Lagrange multipliers correspond to the analytical solutions
of the dual SDP, which play a key role in our proof of the conjecture.
Numerical solvers such as SeDuMi [19] only provide numerical solutions. To
find an analytical one, much more effort needs to be taken.

###  3.1 Heuristics

To begin with, we remove the constraints that are always inactive in the
primal SDP, as the dual variables corresponding to these constraints are $0$.
For randomly chosen step lengths, we numerically solve the primal SDP with or
without certain constraints, respectively. If the optimal values of the two
corresponding SDPs always keep the same, then these certain constraints are
considered to be inactive. As such, our experiments indicate that the
constraints corresponding to

$\displaystyle f_{i}$ $\displaystyle\geq 0,\ 1\leq i\leq N-1,$ $\displaystyle
f_{j}$ $\displaystyle\geq
f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},x_{j}-x_{i}\bigr{\rangle},\text{
for all }|i-j|\geq 2,\ 1\leq i,j\leq N,$

in (2.1) can be removed from the primal SDP, which implies that these
constraints are not supposed to play any role in the primal SDP.

Recall that the bound of the Conjecture 1.2 is attained by the (one-
dimensional) $l_{1}$-shaped function
$f(x)=\frac{R|x|}{\sum_{k=1}^{N}\alpha_{k}}$ started from $x_{0}=-R$. By
setting $R=1$, the iterations of the PPA (as given in Algorithm 1) suggest
that

$\displaystyle P$ $\displaystyle=\Bigl{[}-1,\
-\frac{\alpha_{2:N}}{\alpha_{1:N}},\ -\frac{\alpha_{3:N}}{\alpha_{1:N}},\
\ldots,\ -\frac{\alpha_{N:N}}{\alpha_{1:N}},\
0\Bigr{]}\in\mathbb{R}^{1\times(N+1)},$ $\displaystyle F$
$\displaystyle=\Bigl{[}\frac{\alpha_{2:N}}{(\alpha_{1:N})^{2}},\
\frac{\alpha_{3:N}}{(\alpha_{1:N})^{2}},\ \ldots,\
\frac{\alpha_{N:N}}{(\alpha_{1:N})^{2}},\ 0\Bigr{]}\in\mathbb{R}^{1\times N},$

from which the analytical optimal solutions for (2.1) and the primal SDP can
be recovered. Here and in the following, to simplify the notation, we denote

$\alpha_{i:j}:=\begin{cases}\sum_{k=i}^{j}\alpha_{k},&i\leq j,\\\
0,&i>j.\end{cases}$ (3.1)

The activeness of the remaining constraints in (2.1) and the primal SDP can be
verified at the aforementioned optimal solution.

The Lagrange multiplier to the inequality constraint $f_{N}\geq 0$ in (2.1) or
the corresponding constraint in the primal SDP can be computed numerically via
the method proposed in paragraph 2 of Subsection 2.2. Furthermore, by assuming
that the multiplier is the quotient of two quadratic functions of
$\\{\alpha_{i}\\}_{i=1}^{N}$, the method can be generalized to compute the
Lagrange multipliers corresponding to

$\displaystyle\|x_{0}\|^{2}$ $\displaystyle\leq 1,\ \text{(recall that
}R\text{ is set to }1\text{)},$ $\displaystyle f_{N-1}$ $\displaystyle\geq
f_{N}+\bigl{\langle}\frac{x_{N-1}-x_{N}}{\alpha_{N}},x_{N-1}-x_{N}\bigr{\rangle}.$

However, Lagrange multipliers to the other constraints cannot be computed this
way.

With the inactive constraints being removed, there are totally $3N$ active
constraints left in the reduced (2.1) or the primal SDP. As a consequence, the
number of Lagrangian multipliers in the Lagrangian of the reduced (2.1) is
also $3N$. On the other hand, by setting the partial derivatives of the
Lagrangian for the reduced (2.1) to $0$, we have $2N+1$ equations over
Lagrangian multipliers. This gap implies that some Lagrangian multipliers are
not unique, which prevents us from computing them numerically.

In the Lagrangian of the reduced (2.1), for $i=2,\ldots,N$, by setting the
partial derivative with respect to $f_{i}$ to $0$, we have that the difference
between the Lagrangian multipliers associated with

$\displaystyle 0$ $\displaystyle\geq
f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},-x_{i}\bigr{\rangle},$
$\displaystyle f_{i}$ $\displaystyle\geq
f_{i-1}+\bigl{\langle}\frac{x_{i-2}-x_{i-1}}{\alpha_{i-1}},x_{i}-x_{i-1}\bigr{\rangle},$

appears in the resulting dual constraint. Moreover, by setting the partial
derivative with respect to $x_{N}$ to $0$, we have the last difference, i.e.,
the difference between the Lagrangian multipliers associate with

$\displaystyle 0$ $\displaystyle\geq
f_{N}+\bigl{\langle}\frac{x_{N-1}-x_{N}}{\alpha_{N}},-x_{N}\bigr{\rangle},$
$\displaystyle f_{N}$ $\displaystyle\geq
f_{N-1}+\bigl{\langle}\frac{x_{N-2}-x_{N-1}}{\alpha_{N-1}},x_{N}-x_{N-1}\bigr{\rangle},$

equals to $(\alpha_{N}-\alpha_{1:N-1})/(\alpha_{1:N}\alpha_{N})$. This
equation motivates us to fix one of the Lagrangian multipliers to $0$ with the
other one being kept greater than or equal to $0$, depending on the sign of
$(\alpha_{N}-\alpha_{1:N-1})/(\alpha_{1:N}\alpha_{N})$. Similar treatments can
be applied to the pair of multipliers involved in the differences for
$i=2,\ldots,N-1$. Thus, among the Lagrange multipliers of the reduced (2.1),
$N-1$ of them are fixed to $0$.

###  3.2 The Lagrange multipliers

The Lagrange multipliers depend on the step lengths
$\\{\alpha_{i}\\}_{i=1}^{N}$. In order to write down all the nonzero Lagrange
multipliers, we need to introduce a separator.

######  Definition 3.1 (Separator).

Let $\\{\alpha_{i}\\}_{i=1}^{N}$ be a sequence of positive step sizes, then
there exists a unique positive integer $s$ such that

$\displaystyle\alpha_{1:s}$ $\displaystyle>\alpha_{s+1:N},$
$\displaystyle\alpha_{1:s-1}$ $\displaystyle\leq\alpha_{s:N}.$

This positive integer $s$ is defined as the separator.

Note that notation (3.1) is used here. Trivially, the separator $s$ satisfies
$1\leq s\leq N$ and

$\displaystyle\alpha_{1:i}$ $\displaystyle>\alpha_{i+1:N},\ i\geq s,$
$\displaystyle\alpha_{1:i}$ $\displaystyle\leq\alpha_{i+1:N},\ i<s.$

All the nonzero Lagrange multipliers and their corresponding constraints are
summarized below.

$\displaystyle\frac{1}{(\alpha_{1:N})^{2}}\quad$ $\displaystyle:$
$\displaystyle\quad\|x_{0}\|^{2}$ $\displaystyle\leq 1,$
$\displaystyle\frac{2\alpha_{i}}{\alpha_{i:N}\alpha_{i+1:N}}$ $\displaystyle:$
$\displaystyle\quad 0$ $\displaystyle\geq
f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},-x_{i}\bigr{\rangle},\
1\leq i\leq s-1,$
$\displaystyle\frac{2\alpha_{1:i}}{\alpha_{1:N}\alpha_{i+1:N}}\quad$
$\displaystyle:$ $\displaystyle\quad f_{i}$ $\displaystyle\geq
f_{i+1}+\bigl{\langle}\frac{x_{i}-x_{i+1}}{\alpha_{i+1}},x_{i}-x_{i+1}\bigr{\rangle},\
1\leq i\leq s-1,$
$\displaystyle\frac{2(\alpha_{s:N}-\alpha_{1:s-1})}{\alpha_{1:N}\alpha_{s:N}}\quad$
$\displaystyle:$ $\displaystyle\quad 0$ $\displaystyle\geq
f_{s}+\bigl{\langle}\frac{x_{s-1}-x_{s}}{\alpha_{s}},-x_{s}\bigr{\rangle},$
$\displaystyle\frac{2(\alpha_{1:i}-\alpha_{i+2:N})}{\alpha_{1:N}\alpha_{i+1}}\quad$
$\displaystyle:$ $\displaystyle\quad f_{i}$ $\displaystyle\geq
f_{i+1}+\bigl{\langle}\frac{x_{i}-x_{i+1}}{\alpha_{i+1}},x_{i}-x_{i+1}\bigr{\rangle},\
s\leq i\leq N-1,$
$\displaystyle\frac{2(\alpha_{1:i}-\alpha_{i+1:N})}{\alpha_{1:N}\alpha_{i+1}}\quad$
$\displaystyle:$ $\displaystyle\quad f_{i+1}$ $\displaystyle\geq
f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},x_{i+1}-x_{i}\bigr{\rangle},\
s\leq i\leq N-1,$ $\displaystyle\frac{2}{\alpha_{1:N}}\qquad$ $\displaystyle:$
$\displaystyle\quad f_{N}$ $\displaystyle\geq 0.$

Here, each Lagrange multiplier and its corresponding constraint are separated
by a colon. These nonzero Lagrange multipliers together with the zero valued
ones form an optimal solution to the dual SDP. According to Definition 3.1,
i.e., the definition of the separator $s$, all the multipliers are
nonnegative.

##  4 Proof of the conjecture

In a similar way as in [20, 21, 5], we prove the Conjecture 1.2 in this
section. The Lagrange multipliers and their corresponding constraints
summarized in the last section imply

$\displaystyle\Bigl{\|}\frac{x_{N-1}-x_{N}}{\alpha_{N}}\Bigr{\|}^{2}$
$\displaystyle\leq\Bigl{\|}\frac{x_{N-1}-x_{N}}{\alpha_{N}}\Bigr{\|}^{2}-\frac{1}{(\alpha_{1:N})^{2}}\bigl{(}\|x_{0}\|^{2}-1\bigr{)}-A_{1}$
(4.1)
$\displaystyle\quad-\frac{2(\alpha_{s:N}-\alpha_{1:s-1})}{\alpha_{1:N}\alpha_{s:N}}\Bigl{(}f_{s}+\bigl{\langle}\frac{x_{s-1}-x_{s}}{\alpha_{s}},-x_{s}\bigr{\rangle}\Bigr{)}-A_{2}+\frac{2}{\alpha_{1:N}}f_{N},$

where

$\displaystyle A_{1}$
$\displaystyle=\sum_{i=1}^{s-1}\biggl{[}\frac{2\alpha_{i}}{\alpha_{i:N}\alpha_{i+1:N}}\Bigl{(}f_{i}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},-x_{i}\bigr{\rangle}\Bigr{)}$
$\displaystyle\qquad\qquad+\frac{2\alpha_{1:i}}{\alpha_{1:N}\alpha_{i+1:N}}\Bigl{(}f_{i+1}-f_{i}+\bigl{\langle}\frac{x_{i}-x_{i+1}}{\alpha_{i+1}},x_{i}-x_{i+1}\bigr{\rangle}\Bigr{)}\biggr{]},$
$\displaystyle A_{2}$
$\displaystyle=\sum_{i=s}^{N-1}\biggl{[}\frac{2(\alpha_{1:i}-\alpha_{i+2:N})}{\alpha_{1:N}\alpha_{i+1}}\Bigl{(}f_{i+1}-f_{i}+\bigl{\langle}\frac{x_{i}-x_{i+1}}{\alpha_{i+1}},x_{i}-x_{i+1}\bigr{\rangle}\Bigr{)}$
$\displaystyle\qquad\qquad+\frac{2(\alpha_{1:i}-\alpha_{i+1:N})}{\alpha_{1:N}\alpha_{i+1}}\Bigl{(}f_{i}-f_{i+1}+\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},x_{i+1}-x_{i}\bigr{\rangle}\Bigr{)}\biggr{]}.$

By combining like terms, each $f_{i}$ cancels out in the right hand side of
the inequality (4.1), and together with some rearrangement, we have

$\displaystyle\Bigl{\|}\frac{x_{N-1}-x_{N}}{\alpha_{N}}\Bigr{\|}^{2}\leq\frac{1}{(\alpha_{1:N})^{2}}-A_{3},$
(4.2)

where

$\displaystyle A_{3}$
$\displaystyle=-\Bigl{\|}\frac{x_{N-1}-x_{N}}{\alpha_{N}}\Bigr{\|}^{2}+\frac{1}{(\alpha_{1:N})^{2}}\|x_{0}\|^{2}+\frac{2(\alpha_{s:N}-\alpha_{1:s-1})}{\alpha_{1:N}\alpha_{s:N}}\bigl{\langle}\frac{x_{s-1}-x_{s}}{\alpha_{s}},-x_{s}\bigr{\rangle}$
$\displaystyle\
+2\sum_{i=1}^{s-1}\Bigl{[}\frac{\alpha_{i}}{\alpha_{i:N}\alpha_{i+1:N}}\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},-x_{i}\bigr{\rangle}+\frac{\alpha_{1:i}}{\alpha_{1:N}\alpha_{i+1:N}}\bigl{\langle}\frac{x_{i}-x_{i+1}}{\alpha_{i+1}},x_{i}-x_{i+1}\bigr{\rangle}\Bigr{]}$
$\displaystyle\
+2\sum_{i=s}^{N-1}\Bigl{[}\frac{\alpha_{1:i}-\alpha_{i+2:N}}{\alpha_{1:N}\alpha_{i+1}}\bigl{\langle}\frac{x_{i}-x_{i+1}}{\alpha_{i+1}},x_{i}-x_{i+1}\bigr{\rangle}+\frac{\alpha_{1:i}-\alpha_{i+1:N}}{\alpha_{1:N}\alpha_{i+1}}\bigl{\langle}\frac{x_{i-1}-x_{i}}{\alpha_{i}},x_{i+1}-x_{i}\bigr{\rangle}\Bigr{]}.$

Next, we reformulate $A_{3}$ as the sum of positive weighted squares. This
will imply that $A_{3}$ is always nonnegative. According to the value of the
separator $s$, the proof is divided into the following three categories.

(i) For $s=1$,

$\displaystyle A_{3}$
$\displaystyle=\Bigl{\|}\frac{x_{0}}{\alpha_{1:N}}-\frac{\alpha_{1}-\alpha_{3:N}}{\alpha_{1}\alpha_{2}}x_{1}+\frac{\alpha_{1}-\alpha_{2:N}}{\alpha_{1}\alpha_{2}}x_{2}\Bigr{\|}^{2}+\frac{\alpha_{1}-\alpha_{2:N}}{\alpha_{1:N}\alpha_{1}^{2}\alpha_{2}^{2}}\|\alpha_{3:N}x_{1}-\alpha_{2:N}x_{2}\|^{2}$
$\displaystyle\quad+\sum_{i=s+1}^{N-1}\frac{\alpha_{1:i}-\alpha_{i+1:N}}{\alpha_{1:N}}\Bigl{\|}\frac{x_{i-1}}{\alpha_{i}}-\frac{\alpha_{i}+\alpha_{i+1}}{\alpha_{i}\alpha_{i+1}}x_{i}+\frac{x_{i+1}}{\alpha_{i+1}}\Bigr{\|}^{2}.$

(ii) For $2\leq s\leq N-1$,

$\displaystyle A_{3}$
$\displaystyle=\Bigl{\|}\frac{x_{0}}{\alpha_{1:N}}-\frac{x_{1}}{\alpha_{2:N}}\Bigr{\|}^{2}+\sum_{i=1}^{s-2}\frac{\alpha_{i+1}\alpha_{1:N}+2\alpha_{1:i}\alpha_{i+2:N}}{\alpha_{1:N}\alpha_{i+1}}\Bigl{\|}\frac{x_{i}}{\alpha_{i+1:N}}-\frac{x_{i+1}}{\alpha_{i+2:N}}\Bigr{\|}^{2}$
$\displaystyle\quad+\frac{\alpha_{s}\alpha_{1:N}+2\alpha_{1:s-1}\alpha_{s+1:N}}{\alpha_{1:N}\alpha_{s}}A_{4}$
$\displaystyle\quad+\frac{(\alpha_{1:s}-\alpha_{s+1:N})(\alpha_{s:N}-\alpha_{1:s-1})}{\alpha_{1:N}\alpha_{s}\alpha_{s+1}^{2}(\alpha_{s}\alpha_{1:N}+2\alpha_{1:s-1}\alpha_{s+1:N})}\Bigl{\|}\alpha_{k+2:N}x_{k}-\alpha_{k+1:N}x_{k+1}\Bigr{\|}^{2}$
$\displaystyle\quad+\sum_{i=s+1}^{N-1}\frac{\alpha_{1:i}-\alpha_{i+1:N}}{\alpha_{1:N}}\Bigl{\|}\frac{x_{i-1}}{\alpha_{i}}-\frac{\alpha_{i}+\alpha_{i+1}}{\alpha_{i}\alpha_{i+1}}x_{i}+\frac{x_{i+1}}{\alpha_{i+1}}\Bigr{\|}^{2},$

with

$\displaystyle
A_{4}=\Bigl{\|}\frac{x_{s-1}}{\alpha_{s:N}}-\frac{\alpha_{s+1}\alpha_{1:N}+\alpha_{s:N}(\alpha_{1:s}-\alpha_{s+1:N})}{\alpha_{s+1}(\alpha_{s}\alpha_{1:N}+2\alpha_{1:s-1}\alpha_{s+1:N})}x_{s}+\frac{\alpha_{s:N}(\alpha_{1:s}-\alpha_{s+1:N})}{\alpha_{s+1}(\alpha_{s}\alpha_{1:N}+2\alpha_{1:s-1}\alpha_{s+1:N})}x_{s+1}\Bigr{\|}^{2}.$

(iii) For $s=N$,

$\displaystyle A_{3}$
$\displaystyle=\Bigl{\|}\frac{x_{0}}{\alpha_{1:N}}-\frac{x_{1}}{\alpha_{2:N}}\Bigr{\|}^{2}+\sum_{i=1}^{N-2}\frac{\alpha_{i+1}\alpha_{1:N}+2\alpha_{1:i}\alpha_{i+2:N}}{\alpha_{1:N}\alpha_{i+1}}\Bigl{\|}\frac{x_{i}}{\alpha_{i+1:N}}-\frac{x_{i+1}}{\alpha_{i+2:N}}\Bigr{\|}^{2}$
$\displaystyle\quad+\frac{\alpha_{N}-\alpha_{1:N-1}}{\alpha_{1:N}\alpha_{N}^{2}}\|x_{N}\|^{2}.$

The reformulation may be verified by comparing the coefficients to $\langle
x_{i},x_{j}\rangle$ for $i,j=0,1,\ldots,N$, and according to Definition 3.1,
the coefficients to the norm squares in the reformulations of $A_{3}$ are
always nonnegative.

By combining the nonnegativity of $A_{3}$, the equation (1.4) and the
inequality (4.2), we derive that for $R=1$,

$\|g_{N}\|^{2}=\Bigl{\|}\frac{x_{N-1}-x_{N}}{\alpha_{N}}\Bigr{\|}^{2}\leq\frac{1}{(\alpha_{1:N})^{2}}.$

For $R\neq 1$, if we scale all the $\\{x_{i}\\}_{i=0,1,\ldots,N}$ by $R$ and
all the $\\{f_{i}\\}_{i=1,\ldots,N}$ by $R^{2}$, respectively, we notice that
the objective function value is scaled by $R^{2}$. Hence, the following
theorem is proved.

######  Theorem 4.1.

Let $\\{\alpha_{i}\\}_{i\geq 1}$ be a sequence of positive step sizes and
$x_{0}$ some initial iterate satisfying $\|x_{0}-x_{*}\|\leq R$ for some
optimal point $x_{*}$. For any sequence $\\{x_{i}\\}_{i\geq 1}$ generated by
the PPA with step sizes $\\{\alpha_{i}\\}_{i\geq 1}$ on any function
$f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$, there exists for every iterate
$x_{N}$ a subgradient $g_{N}\in\partial f(x_{N})$ such that

$\|g_{N}\|\leq\frac{R}{\sum_{i=1}^{N}\alpha_{i}}.$

In particular, the choice $g_{N}=\frac{x_{N-1}-x_{N}}{\alpha_{N}}$ is a
subgradient satisfying the inequality.

Note that though there are some kind of heuristics in our construction of the
Lagrange multipliers, our proof of Theorem 4.1 is free of these heuristics.

Up till now, our analysis is limited to the case of Euclidean norm
$\|\cdot\|$. For the more general norm $\|\cdot\|_{B}$, a one to one
correspondence can be formed between the feasible solutions of the Euclidean
norm $\|\cdot\|$ case and the general Euclidean norm $\|\cdot\|_{B}$ case.
Suppose that $(f_{1},\ldots,f_{N},x_{0},x_{1},\ldots,x_{N})$ is a feasible
solution to (2.1), then $\tilde{f}_{1}=f_{1},\ldots,\tilde{f}_{N}=f_{N}$, and
$\tilde{x}_{0}=B^{-1/2}x_{0},\
\tilde{x}_{1}=B^{-1/2}x_{1},\ldots,\tilde{x}_{N}=B^{-1/2}x_{N}$ is a feasible
solution to

$\displaystyle\sup_{\tilde{f}_{1},\ldots,\tilde{f}_{N},\tilde{x}_{0},\tilde{x}_{1},\ldots,\tilde{x}_{N}}$
$\displaystyle\Bigl{\|}\frac{B(\tilde{x}_{N-1}-\tilde{x}_{N})}{\alpha_{N}}\Bigr{\|}_{B^{-1}}^{2}$
(4.3) s.t. $\displaystyle\|\tilde{x}_{0}\|_{B}^{2}\leq R^{2},$
$\displaystyle\tilde{f}_{i}\geq 0,\ 1\leq i\leq N,$ $\displaystyle
0\geq\tilde{f}_{i}+\Bigl{\langle}\frac{B(\tilde{x}_{i-1}-\tilde{x}_{i})}{\alpha_{i}},-\tilde{x}_{i}\Bigr{\rangle},\
1\leq i\leq N,$
$\displaystyle\tilde{f}_{j}\geq\tilde{f}_{i}+\Bigl{\langle}\frac{B(\tilde{x}_{i-1}-\tilde{x}_{i})}{\alpha_{i}},\tilde{x}_{j}-\tilde{x}_{i}\Bigr{\rangle},\
1\leq i,j\leq N,\ i\neq j,$

and vice versa. The optimization problem (4.3) is just a reformulation of the
performance estimation problem under the general norm $\|\cdot\|_{B}$. Notice
that the two optimization problems (2.1) and (4.3) have the same objective
function value at these one to one correspondent feasible solutions. As a
consequence, they also have the same optimal value. Hence, we have the
following corollary.

######  Corollary 4.2 ([20, Conjecture 4.2]).

Let $\\{\alpha_{i}\\}_{i\geq 1}$ be a sequence of positive step sizes and
$x_{0}$ some initial iterate satisfying $\|x_{0}-x_{*}\|_{B}\leq R$ for some
optimal point $x_{*}$. For any sequence $\\{x_{i}\\}_{i\geq 1}$ generated by
the PPA (based on the general norm $\|\cdot\|_{B}$) with step sizes
$\\{\alpha_{i}\\}_{i\geq 1}$ on a function
$f\in\mathcal{F}_{0,\infty}(\mathbb{R}^{n})$, there exists for every iterate
$x_{N}$ a subgradient $g_{N}\in\partial f(x_{N})$ such that

$\|g_{N}\|_{B^{-1}}\leq\frac{R}{\sum_{i=1}^{N}\alpha_{i}}.$

In particular, the choice $g_{N}=\frac{B(x_{N-1}-x_{N})}{\alpha_{N}}$ is a
subgradient satisfying the inequality.

Note that this bound cannot be improved, as it is attained on the (one
dimensional) $l_{1}$-shaped function (1.5).

##  5 Concluding remarks

PPA has been playing fundamental roles both theoretically and algorithmically
in the optimization area. The convergence results in terms of the residual
(sub)gradient norm are particularly interesting when considering dual methods
[2]. Moreover, the (sub)gradient norm is more amenable than function value in
nonconvex optimization.

By using performance estimation framework, Conjecture 4.2 in [20] is proved,
which gives the first direct proof of the convergence rate in terms of the
residual (sub)gradient norm for PPA. To the best of our knowledge, even for
PPA with universal step length, i.e., freezing all step lengths at the same
positive constant, a direct proof of the convergence rate in terms of the
residual (sub)gradient norm is not known before. In addition, this convergence
rate is tight, which means it is the best bound one can derive.

## References

  * [1] P. L. Combettes and J.-C. Pesquet.  Proximal splitting methods in signal processing.  In Fixed-point algorithms for inverse problems in science and engineering, volume 49 of Springer Optim. Appl., pages 185–212. Springer, New York, 2011.
  * [2] O. Devolder, F. Glineur, and Y. Nesterov.  Double smoothing technique for large-scale linearly constrained convex optimization.  SIAM J. Optim., 22(2):702–727, 2012.
  * [3] Y. Drori and M. Teboulle.  Performance of first-order methods for smooth convex minimization: a novel approach.  Math. Program., 145(1-2, Ser. A):451–482, 2014.
  * [4] Y. Drori and M. Teboulle.  An optimal variant of Kelley’s cutting-plane method.  Math. Program., 160(1-2, Ser. A):321–351, 2016.
  * [5] G. Gu and J. Yang.  Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems.  SIAM J. Optim., 30(3):1905–1921, 2020.
  * [6] O. Güler.  On the convergence of the proximal point algorithm for convex minimization.  SIAM J. Control Optim., 29(2):403–419, 1991.
  * [7] O. Güler.  New proximal point algorithms for convex minimization.  SIAM J. Optim., 2(4):649–664, 1992.
  * [8] B. He and X. Yuan.  On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method.  SIAM J. Numer. Anal., 50(2):700–709, 2012.
  * [9] D. Kim.  Accelerated proximal point method for maximally monotone operators.  Math. Program., 190(1-2, Ser. A):57–87, 2021.
  * [10] D. Kim and J. A. Fessler.  Optimized first-order methods for smooth convex minimization.  Math. Program., 159(1-2, Ser. A):81–107, 2016.
  * [11] F. Lieder.  On the convergence rate of the Halpern-iteration.  Optim. Lett., 15(2):405–418, 2021.
  * [12] B. Martinet.  Régularisation d’inéquations variationnelles par approximations successives.  Rev. Française Informat. Recherche Opérationnelle, 4(Ser. R-3):154–158, 1970.
  * [13] R. D. C. Monteiro and B. F. Svaiter.  Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers.  SIAM J. Optim., 23(1):475–507, 2013.
  * [14] J.-J. Moreau.  Proximité et dualité dans un espace hilbertien.  Bull. Soc. Math. France, 93:273–299, 1965.
  * [15] Y. Nesterov.  Lectures on convex optimization, volume 137 of Springer Optimization and Its Applications.  Springer, Cham, 2018.  Second edition of [ MR2142598].
  * [16] N. Parikh and S. Boyd.  Proximal algorithms.  Foundations and Trends® in Optimization, 1(3):127–239, 2014.
  * [17] R. T. Rockafellar.  Monotone operators and the proximal point algorithm.  SIAM J. Control Optim., 14(5):877–898, 1976.
  * [18] E. K. Ryu, A. B. Taylor, C. Bergeling, and P. Giselsson.  Operator splitting performance estimation: tight contraction factors and optimal parameter selection.  SIAM J. Optim., 30(3):2251–2271, 2020.
  * [19] J. F. Sturm.  Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones.  Optim. Methods Softw., 11/12(1-4):625–653, 1999.  Interior point methods.
  * [20] A. B. Taylor, J. M. Hendrickx, and F. Glineur.  Exact worst-case performance of first-order methods for composite convex optimization.  SIAM J. Optim., 27(3):1283–1313, 2017.
  * [21] A. B. Taylor, J. M. Hendrickx, and F. Glineur.  Smooth strongly convex interpolation and exact worst-case performance of first-order methods.  Math. Program., 161(1-2, Ser. A):307–345, 2017.
  * [22] A. B. Taylor, J. M. Hendrickx, and F. Glineur.  Exact worst-case convergence rates of the proximal gradient method for composite convex minimization.  J. Optim. Theory Appl., 178(2):455–476, 2018.
  * [23] N. Yamashita and M. Fukushima.  The proximal point algorithm with genuine superlinear convergence for the monotone complementarity problem.  SIAM J. Optim., 11(2):364–379, 2000.