text:
\begin{document}
\title{Non-bipartite $k$-common graphs\thanks{The work of the first, second and fourth authors has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 648509). This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains. The first and the fourth were also supported by the MUNI Award in Science and Humanities of the Grant Agency of Masaryk University. The second author was also supported by the Leverhulme Trust Early Career Fellowship ECF-2018-534. The third author was supported by an NSERC Discovery grant. The fifth author was supported by IAS Founders' Circle funding provided by Cynthia and Robert Hillas.}}

\author{Daniel Kr{\'a}\v{l}\thanks{Faculty of Informatics, Masaryk University, Botanick\'a 68A, 602 00 Brno, Czech Republic, and Mathematics Institute, DIMAP and Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK. E-mail: {\tt dkral@fi.muni.cz}.}\and
        Jonathan A. Noel\thanks{Department of Mathematics and Statistics, University of Victoria, David Turpin Building A425, 3800 Finnerty Road,  Victoria, Canada V8P 5C2. Previous affiliation: Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK. E-mail: {\tt noelj@uvic.ca}.}\and
	Sergey Norin\thanks{Department of Mathematics and Statistics, McGill University, Montreal, Canada. E-mail: {\tt sergey.norin@mcgill.ca}.}\and
        Jan Volec\thanks{Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Trojanova 13, 120 00 Prague, Czech Republic. Previous affiliation: Faculty of Informatics, Masaryk University, Botanick\'a 68A, 602 00 Brno, Czech Republic. E-mail: {\tt jan@ucw.cz}.}\and
	Fan Wei\thanks{Department of Mathematics, Princeton University, Princeton, NJ, USA. Previous affiliation: School of Mathematics, Institute for Advanced Study, Princeton, USA. E-mail: {\tt fanw@princeton.edu}.}}

\date{}
\maketitle

\begin{abstract}
A graph $H$ is $k$-common if the number of monochromatic copies of $H$ in a $k$-edge-coloring of $K_n$ is
asymptotically minimized by a random coloring.
For every $k$, we construct a connected non-bipartite $k$-common graph.
This resolves a problem raised by Jagger, \v{S}\v{t}ov\'{\i}\v{c}ek and Thomason [Combinatorica 16 (1996), 123--141].
We also show that a graph $H$ is $k$-common for every $k$ if and only if $H$ is Sidorenko and that
$H$ is locally $k$-common for every $k$ if and only if $H$ is locally Sidorenko.
\end{abstract}

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

Ramsey's Theorem states that for every graph $H$ and integer $k\ge 2$,
there exists a natural number $R_k(H)$ such that if $N\geq R_k(H)$, then every $k$-edge-coloring of the complete
graph $K_N$ with $N$ vertices contains a monochromatic copy of $H$.
We study the natural quantitative extension of this question, which was first considered by Goodman~\cite{Goo59}:
\emph{What is the minimum number of monochromatic copies of $H$ in a $k$-edge-coloring of $K_N$ for large $N$?}

A prevailing theme in Ramsey Theory, dating back to an idea of Erd\H{o}s~\cite{Erd47} from the 1940s,
is that one of the best ways to avoid monochromatic substructures is by coloring randomly.
Therefore, it would be natural to expect the answer to the above question
to be the number of monochromatic copies of $H$ in a uniformly random $k$-edge-coloring of $K_N$.
Following~\cite{JagST96}, we say that a graph $H$ is \emph{$k$-common}
if the uniformly random $k$-edge-coloring of $K_N$ asymptotically minimizes the number of monochromatic copies of $H$.
In other words,
the number of monochromatic (labeled) copies of $H$ in every $k$-edge-coloring of $K_N$ is at least
\[(1-o(1))\frac{N^{|H|}}{k^{\|H\|-1}}\]
where $|H|$ and $\|H\|$ denote the number of vertices and edges of $H$, respectively.
The most well-studied case is that of $2$-common graphs, which are often referred to as \emph{common} graphs;
however, we will always say $2$-common to avoid any ambiguity.

Only a handful of graphs are known to be $2$-common and even fewer are known to be $k$-common for $k\ge 3$.
The well-known Goodman Bound~\cite{Goo59} implies that $K_3$ is $2$-common; another proof was given by Lorden~\cite{Lor62}.
This result led Erd\H{o}s~\cite{Erd62} to conjecture that every complete graph is $2$-common
and Burr and Rosta~\cite{BurR80} to extend the conjecture to all graphs.
We now know that $2$-common graphs are far more scarce than Erd\H{o}s, Burr and Rosta had anticipated,
in particular, every non-bipartite graph is a subgraph of a (connected) graph that is not $2$-common~\cite{Fox07}.
Sidorenko~\cite{Sid89} disproved the Burr--Rosta Conjecture by showing that a triangle with a pendant edge is not $2$-common.
Around the same time, Thomason~\cite{Tho89} showed that $K_p$ is not $2$-common for any $p\geq4$,
thereby disproving the original conjecture of Erd\H{o}s~\cite{Erd62}.
Additional constructions showing that $K_p$ is not $2$-common for $p\geq4$ have since been found~\cite{Tho97,FraR93,Fra02}.
Determining the asymptotics of the minimum number of monochromatic copies of $K_4$ in $2$-edge-colorings of large complete graphs
continues to attract a good amount of attention~\cite{Gir79,Nie,Spe11} and
remains one of the most mysterious problems in extremal graph theory (with no conjectured answer).

Jagger, \v{S}\v{t}ov\'{\i}\v{c}ek and Thomason~\cite[Theorem~12]{JagST96} extended the result from~\cite{Tho89} by showing that
no graph containing a copy of $K_4$ is $2$-common.
On the positive side,
Sidorenko~\cite{Sid89} showed that all odd cycles are $2$-common and
Jagger, \v{S}\v{t}ov\'{\i}\v{c}ek and Thomason~\cite[Theorem~8]{JagST96} that all even wheels are $2$-common.
Additional examples of $2$-common graphs can be obtained by certain gluing operations~\cite{JagST96,Sid96}.
However, these operations do not increase the chromatic number and,
for a long time, no examples of $2$-common graphs with chromatic number greater than three were known.
Only in 2012, the $5$-wheel, which has chromatic number four, was shown to be $2$-common~\cite{HatHKNR12} using
Razborov's flag algebra method~\cite{Raz07}; this result settled a problem of~\cite{JagST96}.

Much less is known about $k$-common graphs for $k\ge 3$.
Cummings and Young~\cite{CumY11} proved that every $3$-common graph is triangle-free, which implies that
the same is true for $k$-common graphs for any $k\ge 3$ (see Section~\ref{sec:prelim} for details).
The only known examples of $k$-common graphs for $k\ge 3$ are bipartite graphs that were known to be Sidorenko.
Jagger, S\v{t}ov\'i\v{c}ek and Thomason~\cite[Section~5]{JagST96}
asked about the existence of non-bipartite $k$-common graphs;
no examples of such graphs are known, even for $k=3$.
We resolve this by showing the following.
\begin{theorem}
\label{thm:append}
For every $k\ge 2$, there exists $n_k$ such that, for every $n\ge n_k$,
the graph obtained from $K_{2n,2n}$ by pasting a copy of $C_5$ on every
second vertex in one of the two parts of $K_{2n,2n}$ is $k$-common.
\end{theorem}
Examples of graphs described in the statement of Theorem~\ref{thm:append} can be found in Figure~\ref{fig:append}.
We remark that one of the key ingredients in the proof of Theorem~\ref{thm:append} is establishing that
such graphs are $k$-common in a certain ``local'' sense (see Lemma~\ref{lm:Kn2-local}),
which is proved using spectral arguments.

\begin{figure}
\begin{center}
\epsfbox{kcommon-1.mps}
\end{center}
\caption{Examples of graphs from the statement of Theorem~\ref{thm:append} for $n=1,2,3$.
         The three graphs are denoted by $K_{2,2,C_5}$, $K_{4,4,C_5}$ and $K_{6,6,C_5}$ in Section~\ref{sec:conn}.}
\label{fig:append}
\end{figure}

As we have already mentioned, there is a close connection between $k$-common graphs and Sidorenko graphs.
We say that a graph $H$ is \emph{Sidorenko}
if the number of copies of $H$ in a graph with edge density $d$
is asymptotically minimized by the random graph with edge density $d$.
Sidorenko's Conjecture~\cite{Sid91,Sid93} famously asserts that every bipartite graph $H$ is Sidorenko;
an equivalent conjecture was made earlier by Erd\H{o}s and Simonovits~\cite{ErdS84}.
It is easy to show that every Sidorenko graph is bipartite and $k$-common for every $k\ge 2$.
There are now many families of bipartite graphs that are known to be Sidorenko,
see, e.g.,~\cite{LiS11,ConFS10,Hat10,Sze15,ConKLL18,ConL17,ConL18};
prior to our work, these graphs were the only known examples of $k$-common graphs for any fixed $k\ge 3$.

The following simple construction of~\cite[Theorem~14]{JagST96} shows that, for
every non-bipartite graph $H$, there exists $k\geq2$ such that $H$ is not $k$-common.
Split the vertices of $K_N$ into $2^{k-1}$ sets of roughly equal size, indexed by $0,\dots,2^{k-1}-1$.
Color the edges between the $i$-th and $j$-th sets with the color corresponding to the first bit on which $i$ and $j$
differ in their binary representations and color the edges inside each set with the color $k$.
Since $H$ is non-bipartite,
the only monochromatic copies of $H$ are inside the sets and
thus their number is $(1+o(1))N^{|H|}2^{-(k-1)(|H|-c)}$,
where $c$ is the number of components of $H$.
Thus, if Sidorenko's Conjecture is true,
then Sidorenko graphs are precisely the graphs that are $k$-common for every $k\ge 2$.
We prove this without the assumption that Sidorenko's Conjecture holds.
\begin{theorem}
\label{thm:Sidorenko}
A graph $H$ is $k$-common for all $k\geq2$ if and only if it is Sidorenko.
\end{theorem}
We also establish the variant of Theorem~\ref{thm:Sidorenko} in the local setting,
i.e., when the edge-coloring is ``close'' to the random edge-coloring.
The notion of locally $k$-common graphs is formally defined in Section~\ref{sec:prelim}. Recall that the
\emph{girth} of a graph is the length of its shortest cycle.
\begin{theorem}
\label{thm:local}
The following holds for every $k\ge 3$:
if a graph $H$ has odd girth, then $H$ is not locally $k$-common.
\end{theorem}
Since a theorem of Fox and the last author~\cite{FoxW17} asserts that
all forests and graphs of even girth are locally Sidorenko,
Theorem~\ref{thm:local} implies for every $k\ge 3$ that
a graph $H$ is locally $k$-common if and only if $H$ is locally Sidorenko.
We remark that Theorem~\ref{thm:local} strengthens the result of Cummings and Young~\cite{CumY11} that
no graph containing a triangle is $3$-common by showing that such graphs are not even locally $3$-common.

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

In this section, we fix the notation used throughout the paper and present basic properties of $k$-common graphs.
We also introduce some of the terminology of the theory of graph limits.
While all our arguments can be presented for finite graphs,
the language of graph limits allows us not to discuss ``small order'' asymptotic terms.
Our notation and terminology mainly follows that of the monograph of Lov\'{a}sz~\cite{Lov12},
and we refer the reader to~\cite{Lov12} for a more thorough introduction.

We write $\NN$ for the set of all positive integers and
$[k]$ for the set of the first $k$ positive integers, i.e., $[k]=\{1,\ldots,k\}$.
We work with the Borel measures on $\RR^d$ throughout the paper and
if $A\subseteq [0,1]^d$ is a measurable subset of $\RR^d$, we write $|A|$ for its measure.
Graphs that we consider in this paper are finite and simple.
If $G$ is a graph,
then its vertex set is denoted by $V(G)$ and its edge set by $E(G)$;
the cardinalities of $V(G)$ and $E(G)$ are denoted by $|G|$ and $\|G\|$, respectively.
A \emph{homomorphism} from a graph $H$ to a graph $G$
is a function $f:V(H)\to V(G)$ such that $f(u)f(v)\in E(G)$ whenever $uv\in E(H)$.
The \emph{homomorphism density} of $H$ in $G$
is the probability that a random function from $V(H)$ to $V(G)$ is a homomorphism,
i.e., it is the number of homomorphisms from $H$ to $G$ divided by $|G|^{|H|}$.
We denote the homomorphism density of $H$ in $G$ by $t(H,G)$.

A \emph{graphon} is a measurable function $W:[0,1]^2\to [0,1]$ that is symmetric,
i.e., $W(x,y)=W(y,x)$ for all $(x,y)\in [0,1]^2$.
Intuitively, a graphon can be thought of as a continuous variant of the adjacency matrix of a graph.
The graphon that is equal to $p\in [0,1]$ everywhere is called the $p$-constant graphon;
when there will be no confusion, we will just use $p$ to denote such a graphon.
A graphon $W$ is a \emph{step graphon}
if there exist a partition of $[0,1]$ into non-null subsets $A_1,\ldots,A_m$ such that
$W$ is constant on each of the sets $A_i\times A_j$, $i,j\in [m]$.
The sets $A_i$, $i\in [m]$, are called \emph{parts} of the step graphon $W$;
the sets $A_i\times A_j$, $i,j\in [m]$, are \emph{tiles} and
those with $i=j$ are \emph{diagonal tiles}.

The notion of \emph{homomorphism density} extends to graphons by setting
\begin{equation}
t(H,W) := \int_{[0,1]^{V(H)}} \prod_{uv\in E(H)} W(x_u,x_v) \dd x_{V(H)}\label{eq:tHW}
\end{equation}
for a graph $H$ and graphon $W$.
We define the \emph{density} of a graphon $W$ to be $t(K_2,W)$.
The quantity $t(H,W)$ has a natural interpretation in terms of sampling a random graph according to $W$:
for an integer $n$, choose $n$ independent uniform random points $x_1,\ldots,x_n$ from the interval $[0,1]$ and
create a graph with the vertex set $[n]$ by joining the vertices $i$ and $j$ with probability $W(x_i,x_j)$.
The graph constructed in this way is called a \emph{$W$-random graph} and denoted by $G_{n,W}$.
It can be shown that the following holds for every graph $H$ with probability one:
\[\lim_{n\to\infty}t(H,G_{n,W})=t(H,W).\]
A sequence $(G_i)_{i\in\NN}$ of graphs is \emph{convergent}
if the sequence $(t(H,G_i))_{i\in\NN}$ converges for every graph $H$.
A simple diagonalization argument implies that every sequence of graphs has a convergent subsequence.
We say that a graphon $W$ is a \emph{limit} of a convergent sequence $(G_i)_{i\in\NN}$ of graphs if
\[\lim_{i\to\infty}t(H,G_i)=t(H,W)\]
for every graph $H$.
One of the crucial results in graph limits, due to Lov\'asz and Szegedy~\cite{LovS06}, is that
every convergent sequence of graphs has a limit.
Hence, a graph $H$ is Sidorenko if and only if $t(H,W)\ge t(K_2,W)^{\|H\|}$ for every graphon $W$.
Similarly, the property of being $k$-common translates to the language of graph limits as follows.
A graph $H$ is $k$-common if
\[t(H,W_1)+\cdots+t(H,W_k)\ge \frac{1}{k^{\|H\|-1}}\]
for any graphons $W_1,\ldots,W_k$ such that $W_1+\cdots+W_k=1$.

We pause the exposition of graph limit theory to demonstrate
how the just introduced notions are convenient for establishing some basic properties of $k$-common graphs.
Jagger, \v{S}\v{t}ov\'{\i}\v{c}ek and Thomason~\cite[Theorem~13]{JagST96} observed that
if $H$ is not $k$-common, then $H$ is not $\ell$-common for any $\ell\geq k$.
We now present their argument in the language of graph limits.
Suppose that $H$ is not $k$-common,
i.e., there exists graphons $W_1,\ldots,W_k$ such that $W_1+\cdots+W_k=1$ and
$t(H,W_1)+\cdots+t(H,W_k) < k^{-\|H\|+1}$.
Consider an integer $\ell>k$.
We set $W'_i=\frac{k}{\ell}W_i$ for $i\in [k]$ and $W'_i=1/\ell$ for $i\in [\ell]\setminus [k]$.
Observe that
\begin{align*}
t(H,W'_1)+\cdots+t(H,W'_{\ell}) &= \left(\frac{k}{\ell}\right)^{\|H\|}\left(t(H,W_1)+\cdots+t(H,W_k)\right)+\frac{\ell-k}{\ell^{\|H\|}}\\
                              &< \frac{k}{\ell^{\|H\|}}+\frac{\ell-k}{\ell^{\|H\|}}=\ell^{-\|H\|+1},
\end{align*}
which implies that $H$ is not $\ell$-common.
Hence, we can define $\kappa(H)$ to be the smallest integer $k$ such that $H$ is not $k$-common;
if no such integer exists, we set $\kappa(H)=\infty$.
That is, $H$ is $k$-common if and only if $2\leq k<\kappa(H)$.
In particular, Theorem~\ref{thm:Sidorenko} asserts that $H$ is Sidorenko if and only if $\kappa(H)=\infty$.

In Section~\ref{sec:intro},
for any non-bipartite connected graph $H$,
we exhibited a $k$-edge-coloring of $K_N$ from~\cite{JagST96} which
has $(1+o(1))N^{|H|}2^{-(k-1)(|H|-1)}$ monochromatic copies of $H$.
It follows that a non-bipartite connected graph $H$ is not $k$-common for any $k$
that satisfies $2^{-(k-1)(|H|-1)}<k^{-\|H\|+1}$.
This implies that
$\kappa(H)\le \lceil 2 d\log_2 d\rceil$
for any non-bipartite connected graph $H$ with average degree $d$.
We remark that for graphs $H$ with chromatic number larger than three,
a better upper bound on $\kappa(H)$ can be obtained by considering the edge-coloring obtained
by splitting vertices of $K_N$ to $(\chi(H)-1)^{k-1}$ roughly equal parts and
defining the edge-coloring based on the base $(\chi(H)-1)$ representations of the indices of the parts.

Let us return to our brief introduction to notions from the theory of graph limits that we use in this paper.
A graphon $W$ can be thought of as an operator on $L_2[0,1]$ where the image of a function $f\in L_2[0,1]$ is
given by
\[\int_{0}^1W(x,y)f(y)\dd y.\]
Every such operator is compact and so
its spectrum $\sigma(W)$ is either finite or countably infinite,
the only accumulation point of $\sigma(W)$ can be zero and
every non-zero element of $\sigma(W)$ is an eigenvalue of $W$~\cite[Section~7.5]{Lov12}.
In addition, all elements of $\sigma(W)$ are real and the largest is at least the density of $W$.
We define $\wsigma(W)$ to be the multiset containing all non-zero elements $\lambda$ of $\sigma(W)$,
with multiplicity equal to the dimension of the kernel of $(W-\lambda)$, which is finite.
In the graph case, the trace of the $n$-th power of the adjacency matrix of a graph $G$,
which is equal to the sum of the $n$-th powers of the eigenvalues of the matrix,
is the number of homomorphisms from $C_n$ to $G$,
i.e., it is equal to $t(C_n,G)|G|^n$~\cite[Equation~(5.31)]{Lov12}.
We will need the analogous statement for graphons,
which we now state as a proposition.
\begin{proposition}[{Lov\'asz~\cite[Equation~(7.22)]{Lov12}}]
\label{prop:spectrum}
Let $W$ be a graphon. It holds for every $n\ge 3$:
\[t(C_n,W)=\sum_{\lambda\in\wsigma(W)}\lambda^n.\]
\end{proposition}

There are several useful metrics on graphons. One of the most important
from the perspective of graph limit theory is the metric induced by the
cut norm. A \emph{kernel} is a bounded symmetric measurable function from
$[0,1]^2$ to $\mathbb{R}$; a kernel can be thought of as a continuous
variant of the adjacency matrix of an edge-weighted graph. We define the
\emph{cut norm} of a kernel $U$ to be
\[\cut{U} := \sup_{S,T\subseteq [0,1]}\left|\int_{S\times T}U(x,y)\dd x\dd y\right|,\]
where the supremum is over all measurable subsets $S$ and $T$ of $[0,1]$.
The \emph{cut distance} of graphons $W$ and $W'$, denoted by $\dcut{W}{W'}$,
is the infimum of the cut norm $\cut{W^\varphi-W'}$
taken over all measure preserving maps $\varphi:[0,1]\to [0,1]$
where $W^\varphi(x,y)=W(\varphi(x),\varphi(y))$.
If two graphons have small cut distance, then their
homomorphism densities do not differ substantially, as the next lemma shows.
\begin{lemma}[{Lov\'asz~\cite[Lemma 10.23]{Lov12}}]
\label{lm:cutdist}
Let $W$ and $W'$ be two graphons and $H$ a graph.
It holds that $|t(H,W)-t(H,W')|\le \|H\|\cdot \dcut{W}{W'}$.
\end{lemma}
Lemma~\ref{lm:cutdist} asserts that two graphons which are close in the cut distance
have similar homomorphism densities. The next lemma allows us to find a step graphon
of bounded complexity that is close in cut distance to any graphon.
\begin{lemma}[Frieze and Kannan~\cite{FriK99}; see also~{\cite[Lemma~9.3]{Lov12}}]
\label{lm:reg}
For every $\varepsilon>0$, there exists an integer $M\in\NN$ such that for every graphon $W$,
there exists a step graphon $W'$ with at most $M$ parts, all of equal sizes, such that
the densities of $W$ and $W'$ are the same and $\dcut{W}{W'}\le\varepsilon$.
\end{lemma}
The homomorphism density function extends naturally to kernels $U$ by setting $t(H,U)$
to be the integral in~\eqref{eq:tHW} with $W$ replaced by $U$.
A graphon $W$ that is close to the $p$-constant graphon
can be expressed as $p+\varepsilon U$ for some kernel $U$ and small $\varepsilon>0$.
The following proposition provides a useful expansion of $t(H,p+\varepsilon U)$,
which implicitly appeared in~\cite{Lov11,Sid89};
we use the formulation from~\cite[proof of Proposition 16.27]{Lov12}.
\begin{proposition}
\label{prop:epsU}
Let $U$ be a kernel, $H$ a graph and $p\in [0,1]$.
It holds that
\[t(H,p+\varepsilon U)=\sum_{F\subseteq E(H)}t(H[F],U)p^{\|H\|-|F|}\varepsilon^{|F|}\]
where $H[F]$ is the spanning subgraph of $H$ with the edge set $F$.
\end{proposition}

A local variant Sidorenko's Conjecture was considered in~\cite{Lov11} and in~\cite[Chapter 16]{Lov12}.
Here, we consider a stronger notion discussed in~\cite{FoxW17}:
a graph $H$ is \emph{locally Sidorenko} if there exists $\varepsilon_0>0$ such that
for every graphon $W$ with density $p$ such that $\cut{W-p}\le\varepsilon_0p$ and $\|W-p\|_{\infty}\le p$,
it holds that $t(H,W)\ge p^{\|H\|}$. The following theorem characterized locally
Sidorenko graphs.
\begin{theorem}[Fox and Wei~\cite{FoxW17}]
\label{thm:localSid}
A graph $H$ is locally Sidorenko if and only if $H$ is forest or its girth is even.
\end{theorem}
Similarly, we say that a graph $H$ is \emph{locally $k$-common}
if for every $k\ge 2$, there exists $\varepsilon_0>0$ such that
\[t(H,W_1)+\cdots+t(H,W_k)\ge k^{-\|H\|+1}\]
for all graphons $W_1,\ldots,W_k$ such that $W_1+\cdots+W_k=1$, $\cut{W_i-1/k}\le\varepsilon_0/k$
and $\|W_i-1/k\|_{\infty}\le 1/k$ for all $i\in [k]$.

Fix a graphon $W$ and a real $\delta>0$ and
consider the set $\AAA(W,\delta)$ of all measurable functions $h:[0,1]\to [0,1]$ such that
\[\int_{[0,1]^2} h(x)W(x,y)h(y)\dd x\dd y\le\delta\|h\|_1^2.\]
Intuitively, for $\|h\|_1>0$, one can think of $h$ as a weight function on $[0,1]$ with the property that,
if $x$ and $y$ are chosen independently at random according to the probability measure induced by
$h/\|h\|_1$, then the expected value of $W(x,y)$ is at most $\delta$.
We define the \emph{$\delta$-independence ratio} of $W$ to be
\[\alpha_{\delta}(W) := \sup_{h\in\AAA(W,\delta)}\|h\|_1.\]

We next define a notion of a subgraphon that
is more involved than restricting a graphon to a measurable subset of $[0,1]$ and rescaling.
This notion will be used in the proof of Theorem~\ref{thm:append}
to apply induction to a ``sparse'' part of one of the graphons $W_1,W_2,\dots,W_k$.
Let $h:[0,1]\to [0,1]$ be a measurable function such that $\|h\|_1>0$ and
let $f:[0,\|h\|_1]\to [0,1]$ be the measurable function defined by
\[f(z) := \inf \left\{t\in [0,1]\mbox{ such that }\int_{[0,t]} h(x)\dd x\ge z\right\}.\]
Observe that
\[\int_A h(x)\dd x=|f^{-1}(A)|\]
for every measurable subset $A$ of $[0,1]$.
The subgraphon of $W$ induced by $h$, which is denoted by $W[h]$, is the graphon defined by
\[W[h](x,y):=W(f(x\cdot \|h\|_1),f(y\cdot \|h\|_1))\]
for every $(x,y)\in [0,1]^2$.
The graphon $W[h]$ is associated with the following sequence of random graphs.
Choose $n$ points independently at random based on the probability with density $h/\|h\|_1$ and
form a graph $G_{n}$ with vertex set $[n]$ by joining vertices $i$ and $j$ with probability $W(x_i,x_j)$.
Then $W[h]$ is a limit of the sequence $(G_{n})_{n\in\NN}$ with probability one.
The definition of $W[h]$ implies that
\begin{equation}
t(H,W[h])=\frac{1}{\|h\|_1^{|H|}}\int_{[0,1]^{V(H)}} \prod_{u\in V(H)}h(u) \prod_{uv\in E(H)} W(x_u,x_v) \dd x_{V(H)}\label{eq:tWh}
\end{equation}
for every graph $H$.
In particular, $t(H,W)$ is at least $\|h\|_1^{|H|}\cdot t(H,W[h])$.

We conclude this section by relating certain ``reflection operations'' to homomorphism densities.
The arguments of this kind are standard in the area;
however, we have decided to provide a self-contained exposition for completeness.
Let $H$ be a graph and let $U\subseteq V(H)$ be an independent set of vertices of $H$.
For a graphon $W$, we define a function $t_W^H:[0,1]^U\to\RR$ as follows:
\[t_W^H(x_U)=\int_{[0,1]^{V(H)\setminus U}}\prod_{vv'\in E(H)}W(x_v,x_{v'})\dd x_{V(H)\setminus U};\]
note that the function $t_W^H$ depends on the choice of the set $U$.
Since the choice of the set $U$ will always be clear from the context,
we have decided not to include the set $U$ in the notation explicitly to keep the used notation simple.
Informally speaking, the function $t_W^H(x_U)$ counts the number of homomorphic copies of $H$ rooted at $x_U$.
Observe that
\[t(H,W)=\int_{[0,1]^U}t_W^H(x_U)\dd x_U.\]
We now state a proposition, which gives a lower bound on the homomorphism density of a graph obtained by reflecting $H$ along the set $U$.
\begin{proposition}
\label{prop:reflect}
Let $H$ be a graph, $n$ a positive integer and $U\subseteq V(H)$ an independent set of vertices of $H$.
Further,
let $H^n$ be the graph obtained by taking $n$ copies of $H$ and identifying the corresponding vertices of the set $U$,
i.e., the graph $H^n$ has $n|H|-(n-1)|U|$ vertices.
The following holds for every graphon $W$:
\[t(H^n,W)\ge t(H,W)^n.\]
\end{proposition}
\begin{proof}
Fix a graphon $W$.
We consider both graphs $H$ and $H^n$ with the set $U$ and note that
$t_W^{H^n}(x_U)=t_W^H(x_U)^n$ for every $x_U\in [0,1]^U$.
Hence, it follows that
\[t(H^n,W)=\int_{[0,1]^U}t_W^{H^n}(x_U)\dd x_U\ge\left(\int_{[0,1]^U}t_W^H(x_U)\dd x_U\right)^n=t(H,W)^n\]
by Jensen's Inequality.
\end{proof}
The same argument translates to the rooted setting,
which we formulate here for future reference but omit the proof as it is completely analogous to the proof of Proposition~\ref{prop:reflect}.
\begin{proposition}
\label{prop:reflect-rooted}
Let $H$ be a graph, $n$ a positive integer, $U\subseteq V(H)$ an independent set of vertices of $H$, and
$U'\subseteq V(H)$ an independent set that is a superset of $U$.
Further, let $H^n$ be the graph obtained from $H$ taking $n$ copies of $H$ and identifying the corresponding vertices of the set $U'$.
The following holds for every graphon $W$ and every $x_U\in [0,1]^U$:
\[t_W^{H^n}(x_U)\ge t_W^H(x_U)^n.\]
\end{proposition}
The following proposition is obtained by two applications of Proposition~\ref{prop:reflect},
first to the graph $K_{2,2}$ and $U$ being one of the two parts of $K_{2,2}$, and
second to the graph $K_{2,2n}$ and $U$ being the $2n$-vertex part of $K_{2,2n}$.
\begin{proposition}
\label{prop:Knn}
The following holds for every graphon $W$ and every $n\in\NN$:
\[t(K_{2n,2n},W)\ge t(K_{2,2},W)^{n^2}.\]
\end{proposition}

\section{Non-bipartite $k$-common graphs}
\label{sec:conn}

This section is devoted to the proof of Theorem~\ref{thm:append}.
For $a,b\geq1$, we let $K_{2a,2b,C_5}$ be the graph obtained from $K_{2a,2b}$ by adding
$b$ disjoint copies of $C_5$ and identifying one vertex of each of these copies with one vertex in the $2b$-vertex part of $K_{2a,2b}$ (each copy involves a different vertex of the part).
In particular, $K_{2n,2n,C_5}$ is the graph from the statement of Theorem~\ref{thm:append}.
We start with proving that $K_{2n,2,C_5}$ is locally Sidorenko in a certain strong sense;
note that the assumption on $W$ is weaker than that in the local Sidorenko property discussed in Section~\ref{sec:prelim}
since we do not require any bound on  $\|W-p\|_{\infty}$.

\begin{lemma}
\label{lm:Kn2-local}
For every $p_0\in(0,1)$, there exist $\varepsilon_0\in(0,1)$ such that the following holds.
If $W$ is a graphon with density $p\ge p_0$ such that $t(K_{2,2},W)\le p^4+\varepsilon_0$,
then $t(K_{2n,2,C_5},W)\ge p^{4n+5}$ for all $n\in\NN$.
\end{lemma}

\begin{proof}
We show that the statement of the lemma holds for $\varepsilon_0=p_0^7/16$.
Throughout the proof, fix a graphon $W$ with density $p\ge p_0$ such that $t(K_{2,2},W)-p^4=\varepsilon\le\varepsilon_0$.
If the set $\wsigma(W)$ is finite, then set $I=[|\wsigma(W)|]$ and set $I=\NN$ otherwise.
Let $\lambda_i$, $i\in I$, be the elements of $\wsigma(W)$ listed in the decreasing order of their absolute value.
Further, let $g_i:[0,1]\to \RR$ be an eigenfunction corresponding to $\lambda_i$.
Without loss of generality,
we assume that $\|g_i\|_2=1$ for all $i\in I$ and that
the eigenfunctions are orthogonal to one another, i.e.,
\[\int_{[0,1]} g_i(x)g_{i'}(x)\dd x=0\]
for any two distinct $i$ and $i'$ from $I$.
In particular, the functions $G_i$, $i\in I$, are orthonormal.
Since it holds that
\[\lambda_1=\max_{\substack{f\in L_2[0,1]\\ \|f\|_2=1}}\int_{[0,1]^2} f(x)W(x,y)f(y)\dd x\dd y,\]
it follows $\lambda_1\ge p$. In particular, $\lambda_1\ge p_0$.

For every $x\in [0,1]$, we define a measurable function $f_x:[0,1]\to [0,1]$ by setting $f_x(y)=W(x,y)$ for all $y\in[0,1]$,
i.e., $f_x$ describes the ``neighborhood'' of $x$ in the graphon $W$.
We next define functions $\beta_i$ such that
$\beta_i(x)$ would be the coordinate of $f_x$ with respect to $g_i$, $i\in I$, for an orthonormal basis
extending $g_i$, $i\in I$,
i.e.,
\[\beta_i(x)=\int_{[0,1]} g_i(y)f_x(y)\dd y.\]
Since the $L_2$-norm of $f_x$ is at most one and the functions $g_i$, $i\in I$, are orthonormal,
we obtain that
\begin{equation}
\sum_{i\in I}\beta_i(x)^2\le 1\label{eq:norm}
\end{equation}
for every $x\in [0,1]$.
Since it holds that
\[W(x,y)=\sum_{i\in I}\lambda_i g_i(x)g_i(y)\]
for almost every $(x,y)\in [0,1]^2$, it follows that $\beta_i(x)=\lambda_i g_i(x)$ for almost every $x\in [0,1]$.
In particular, it holds that
\begin{equation}
\label{eq:alpha1lambda1}
\int_{[0,1]}\beta_i(x)^2\dd x=\lambda_i^2.
\end{equation}

Next consider a cycle $C_k$ and let $U$ consist of any single vertex of $C_k$.
As the functions $g_i$, $i\in I$, are orthonormal and are eigenfunctions of $W$,
we get that
\begin{align}
t_W^{C_k}(x) &=\int_{[0,1]^{k-1}}f_x(y_1)W(y_1,y_2)W(y_2,y_3)\cdots W(y_{k-2},y_{k-1})f_x(y_{k-1})\dd y_1\cdots y_{k-1}\nonumber\\
             &=\sum_{i\in I}\lambda_i^{k-2}\beta_i(x)^2\label{eq:Ckx}
\end{align}
holds for every $k\ge 3$ and $x\in [0,1]$.
It follows that
\begin{equation}t(C_k,W)=\int_{[0,1]}t_W^{C_k}(x)\dd x=\sum_{i\in I}\lambda_i^{k-2}\int_{[0,1]}\beta_i(x)^2\dd x.\label{eq:Ckalpha}\end{equation}
On the other hand, Proposition~\ref{prop:spectrum} tells us that
\begin{equation}
t(C_{k},W)=\sum_{i\in I}\lambda_i^{k}.\label{eq:spectrum}
\end{equation}
In particular, we obtain for $k=4$ that
\[\varepsilon=t(K_{2,2},W)-p^4=\sum_{i\in I}\lambda_i^4-p^4\ge\sum_{i\in I\setminus\{1\}}\lambda_i^4,\]
which implies that $|\lambda_i|\le\varepsilon^{1/4}$ for every $i\in I\setminus\{1\}$.
In particular, $\lambda_1$ has multiplicity one.

Our aim is to estimate $t_W^{K_{2n,2,C_5}}(x)$
where $U$ is the set consisting of the vertex shared by $K_{2n,2}$ and $C_5$.
Observe that
\begin{equation}
t_W^{K_{2n,2,C_5}}(x)=t_W^{K_{2n,2}}(x)\cdot t_W^{C_5}(x).\label{eq:prodKC5}
\end{equation}
We start by rewriting the identity \eqref{eq:Ckx} for $k=4$ and $k=5$:
\begin{align}
t_W^{C_4}(x) & =\lambda_1^2\beta_1^2(x)+\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x) \label{eq:C4}\\
t_W^{C_5}(x) & =\lambda_1^3\beta_1^2(x)+\sum_{i\in I\setminus\{1\}}\lambda_i^3\beta_i^2(x). \label{eq:C5}
\end{align}
Note that all of the terms on the right sides of these two expressions are non-negative,
except for possibly the summation in \eqref{eq:C5}.
Using Proposition~\ref{prop:reflect-rooted} and the equation~\eqref{eq:C4},
we obtain that
\begin{align}
t_W^{K_{2n,2}}(x) &\ge t_W^{C_4}(x)^n\nonumber\\
                  & = \left(\lambda_1^2\beta_1^2(x)+\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)^n\nonumber\\
		  & \ge\lambda_1^{2n}\beta_1^{2n}(x)+\lambda_1^{2n-2}\beta_1^{2n-2}(x)\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\label{eq:C4n}
\end{align}
Our next goal is to show that, unless $f_x$ is almost completely orthogonal to $g_1$,
the homomorphism density of $K_{2n,2,C_5}$ rooted at $x$ is at least its expected average value.
Specifically, we will set $\pi_0=p_0^2/2$ and show that if $\beta_1^2(x)\ge\pi_0$, then
\begin{equation}
t_W^{K_{2n,2,C_5}}(x)\ge \lambda_1^{2n+3}\beta_1^{2n+2}(x).\label{eq:estimKC5}
\end{equation}
To this end, we substitute \eqref{eq:C5} and \eqref{eq:C4n} into \eqref{eq:prodKC5} to obtain
\begin{align*}
t_W^{K_{2n,2,C_5}}(x) & \ge\left(\lambda_1^{2n}\beta_1^{2n}(x)+\lambda_1^{2n-2}\beta_1^{2n-2}(x)\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right) \\
                      & \times\left(\lambda_1^3\beta_1^2(x)+\sum_{i\in I\setminus\{1\}}\lambda_i^3\beta_i^2(x)\right).
\end{align*}
Multiplying out, we obtain four terms.
One of them is the right side of \eqref{eq:estimKC5} and the remaining three terms are as follows:
\begin{align*}
& \lambda_1^{2n+1}\beta_1^{2n}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right),\\
& \lambda_1^{2n}\beta_1^{2n}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^3\beta_i^2(x)\right) \mbox{ and}\\
& \lambda_1^{2n-2}\beta_1^{2n-2}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^3\beta_i^2(x)\right).
\end{align*}
So, to establish \eqref{eq:estimKC5}, we need to show that the sum of these three terms is non-negative.
We first consider the sum of half of the first term and the whole of the second term.
Since $p_0\leq \lambda_1$ and $\lambda_i\leq \varepsilon^{1/4}$ for all $i\in I\setminus \{1\}$, we get
\begin{align*}
& \frac{1}{2}\lambda_1^{2n+1}\beta_1^{2n}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)+
  \lambda_1^{2n}\beta_1^{2n}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^3\beta_i^2(x)\right)\\
\ge &
  \left(\frac{p_0}{2}-\varepsilon^{1/4}\right)\left(\lambda_1^{2n}\beta_1^{2n}(x)\right)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)\ge 0.
\end{align*}
Next, we estimate the sum of half of the first term and the third term as follows:
\begin{align*}
& \frac{1}{2}\lambda_1^{2n+1}\beta_1^{2n}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)\\
& +
  \lambda_1^{2n-2}\beta_1^{2n-2}(x)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)\left(\sum_{i\in I\setminus\{1\}}\lambda_i^3\beta_i^2(x)\right)\\
\ge &
  \left(\frac{1}{2}\lambda_1^3\beta_1^2(x)-\sum_{i\in I\setminus\{1\}}|\lambda_i|^3\beta_i^2(x)\right)
  \lambda_1^{2n-2}\beta_1^{2n-2}(x)
  \left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)\\
\ge &
  \left(\frac{p^3\pi_0}{2}-\varepsilon^{3/4}\sum_{i\in I\setminus\{1\}}\beta_i^2(x)\right)
  \lambda_1^{2n-2}\beta_1^{2n-2}(x)
  \left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right)\\
\ge &
  \left(\frac{p_0^5}{4}-\varepsilon^{3/4}\right)
  \lambda_1^{2n-2}\beta_1^{2n-2}(x)
  \left(\sum_{i\in I\setminus\{1\}}\lambda_i^2\beta_i^2(x)\right).
\end{align*}
The last inequality follows from \eqref{eq:norm}. The final expression is non-negative (with room to spare)
by the choice of $\varepsilon_0$.

The statement would follow from \eqref{eq:alpha1lambda1} and \eqref{eq:estimKC5} by a convexity argument
if $\beta_1^2(x)\ge\pi_0$ held for almost all $x\in [0,1]$.
As this need not be the case for almost all $x\in [0,1]$, a finer argument is needed.
Let $X_1$ be the set of $x\in[0,1]$ such that $\beta_1^2(x)\ge\pi_0$ and let $\delta=1-|X_1|$.
By \eqref{eq:alpha1lambda1} for $i=1$, we have
\[\int_{X_1}\beta_1^2(x)\dd x=\int_{[0,1]}\beta_1^2(x)\dd x-\int_{[0,1]\setminus X_1}\beta_1^2(x)\dd x\ge \lambda_1^2-\delta\pi_0.\]
The equation \eqref{eq:alpha1lambda1} for $i=1$ also implies that $\delta<1$;
otherwise, the integral of $\beta_1^2(x)$, which is equal to $\lambda_1^2\ge p_0^2$, would be at most $\pi_0=p_0^2/2$.
Using Jensen's Inequality, we have
\begin{align*}
\int_{X_1}\beta_1^{2n+2}(x)\dd x & \ge \frac{(\lambda_1^2-\delta\pi_0)^{n+1}}{(1-\delta)^n}\\
  & = \left(\frac{\lambda_1^2-\delta\pi_0}{1-\delta}\right)^{n-1}\cdot\frac{\lambda_1^4-2\delta\pi_0\lambda_1^2+\delta^2\pi_0^2}{1-\delta} \\
  & \ge \lambda_1^{2n-2}\cdot\frac{\lambda_1^4-2\delta\pi_0\lambda_1^2+\delta^2\pi_0^2}{1-\delta} \\
  & = \lambda_1^{2n-2}\cdot\left(\lambda_1^4+\frac{\delta\lambda_1^4-2\delta\pi_0\lambda_1^2+\delta^2\pi_0^2}{1-\delta}\right) \\
  & \ge \lambda_1^{2n+2}+\lambda_1^{2n-2}\cdot\frac{\delta\lambda_1^2(\lambda_1^2-2\pi_0)}{1-\delta}\ge \lambda_1^{2n+2}.
\end{align*}
In the step between the second and third lines and in the last line,
we used the fact that $2\pi_0=p_0^2\leq p^2\leq \lambda_1^2$.
Since the estimate \eqref{eq:estimKC5} holds for every $x\in X_1$, we obtain that
\[
t(K_{2n,2,C_5},W) \ge\int_{X_1}t_W^{K_{2n,2,C_5}}(x)\dd x
		 \ge\int_{X_1}\lambda_1^{2n+3}\beta_1^{2n+2}(x)\dd x \ge \lambda_1^{4n+5}\ge p^{4n+5}.
\]
This concludes the proof of the lemma.
\end{proof}

The next lemma follows from Lemma~\ref{lm:Kn2-local} by applying Proposition~\ref{prop:reflect-rooted}
for the graph $H=K_{2n,2,C_5}$ and the set $U$ being the part of $K_{2n,2}$ with $2n$ vertices.

\begin{lemma}
\label{lm:Knn-local}
For every $p_0\in(0,1)$, there exists $\varepsilon_0\in (0,1)$ such that the following holds.
If $W$ is a graphon with density $p\ge p_0$ such that $t(K_{2,2},W)\le p^4+\varepsilon_0$,
then $t(K_{2n,2n,C_5},W))\ge p^{4n^2+5n}$ for all $n\in\NN$.
\end{lemma}

The second ingredient for the proof of Theorem~\ref{thm:append} is the next lemma,
which covers the case when $t(K_{2,2},W)$ is substantially larger than $t(K_2,W)^4$
unless the graphon $W$ contains a large sparse part.

\begin{lemma}
\label{lm:Knn-far}
For every $p_0\in (0,1)$ and every $\varepsilon_0\in (0,1)$,
there exist $n_0\in\NN$ and $\delta_0\in (0,1)$ such that
the following holds for every graphon $W$ with density $p\ge p_0$ such that $t(K_{2,2},W)\ge p^4+\varepsilon_0$:
\begin{itemize}
\item $t(K_{2n,2n,C_5},W)\ge p^{4n^2+5n}$ for every $n\ge n_0$, or
\item $\alpha_{p_0}(W)\ge\delta_0$.
\end{itemize}
\end{lemma}

\begin{proof}
Set $\delta_0:=p_0\varepsilon_0/16$ and set $d_0:=\delta_0$.
The reason that we let $\delta_0$ and $d_0$ to represent the same quantity is that
they play different roles in the proof; $\delta_0$ is the lower bound on the
$p_0$-independence ratio in the statement of the theorem whereas $d_0$ is the
threshold for considering a point $x\in [0,1]$ to have ``small degree'' in a
graphon $W$. Choose $n_0$ to be large enough so that
\[\left(1+\varepsilon_0/2\right)^{n_0}d_0^4p_0^3\ge 1.\]

Fix a graphon $W$ with density $p\ge p_0$ such that $t(K_{2,2},W)\ge p^4+\varepsilon_0$.
We iteratively define sets $A_i$, $i\in\NN$, such that
$A_i$ is the set of all $x\in [0,1]$ with ``small degree'' when disregarding neighbors in $A_{i-1}$.
Formally, we let $A_0=\emptyset$ and let
 $A_i$, $i\in\NN$, be the set of all $x\in [0,1]$ such that
\[\int_{[0,1]\setminus A_{i-1}}W(x,y)\dd y\le d_0.\]
Note that $A_{i-1}\subseteq A_i$ for every $i\in\NN$.
Let $A$ be the union of all sets $A_i$, $i\in\NN$, and
observe that, for every $x\in [0,1]\setminus A$,
\[\int_{[0,1]\setminus A} W(x,y)\dd y=\lim_{i\to\infty}\int_{[0,1]\setminus A_{i-1}}W(x,y)\dd y.\]
In particular, it holds that
\[\int_{[0,1]\setminus A} W(x,y)\dd y\ge d_0\]
for every $x\in [0,1]\setminus A$.

We next distinguish two cases depending on the measure of $A$, and
we first analyze the case that $|A|\ge\varepsilon_0/8$.
We start with estimating the density of $W$ on the set $A$:
\begin{align*}
\int_{A^2} W(x,y)\dd x\dd y &= \sum_{i\in\NN}\int\limits_{(A_i\setminus A_{i-1})^2}W(x,y)\dd x\dd y
                              + 2\quad\int\limits_{\mathclap{(A_i\setminus A_{i-1})\times(A\setminus A_{i})}}\quad W(x,y)\dd x\dd y\\
                            & \le \sum_{i\in\NN}\int\limits_{(A_i\setminus A_{i-1})^2}W(x,y)\dd x\dd y
			      +2\quad\int\limits_{\mathclap{(A_i\setminus A_{i-1})\times([0,1]\setminus A_i)}}\quad W(x,y)\dd x\dd y\\
                            & \le 2\sum_{i\in\NN}\int\limits_{(A_i\setminus A_{i-1})\times([0,1]\setminus A_{i-1})}W(x,y)\dd x\dd y\\
			    & \le 2\sum_{i\in\NN}\left|A_i\setminus A_{i-1}\right|d_0\le 2|A|d_0.
\end{align*}
It follows that
\[\frac{\int_{A^2} W(x,y)\dd x\dd y}{|A|^2}\le\frac{2d_0}{|A|}=\frac{p_0\varepsilon_0}{8|A|}\le p_0.\]
Thus, the characteristic function of $A$ certifies that $\alpha_{p_0}(W)\ge\varepsilon_0/8\ge\delta_0$.

In the rest of the proof, we assume that $|A|\le\varepsilon_0/8$.
We show that the homomorphism density of $K_{2n,2n,C_5}$ is large enough even if we disregard the points contained in $A$.
To do this, we set $W'$ to be the graphon defined by
\[W'(x,y)=\begin{cases}
          0 & \mbox{if $x\in A$ or $y\in A$,}\\
          W(x,y) & \mbox{otherwise.}
	  \end{cases}\]
We next estimate the homomorphism density $K_{2n,2n}$ in $W'$ using Proposition~\ref{prop:Knn} as follows:
\begin{align*}
t(K_{2n,2n},W') & \ge t(K_{2,2},W')^{n^2}\\
                & \ge \left(t(K_{2,2},W)-4|A|\right)^{n^2}\\
		& \ge \left(p^4+\varepsilon_0-\varepsilon_0/2\right)^{n^2}=\left(p^4+\varepsilon_0/2\right)^{n^2}
\end{align*}
We next combine these copies of $K_{2n,2n}$ with copies of $C_5$ rooted at $x\in [0,1]\setminus A$
unless $W$ contains a sparse part.
Consider $x\in [0,1]\setminus A$ and let $h(y)=W'(x,y)$.
Note that
\[\int_{[0,1]}h(y)\dd y=\int_{[0,1]}W'(x,y)\dd y=\int_{[0,1]\setminus A}W(x,y)\ge d_0=\delta_0.\]
Since $h(y)=0$ for $y\in A$, we obtain that
\begin{equation}
\int_{[0,1]^2}h(y)W'(y,z)h(z)\dd y\dd z=\int_{[0,1]^2}h(y)W(y,z)h(z)\dd y\dd z.\label{eq:hdens}
\end{equation}
If the integral in~\eqref{eq:hdens} is less than $p_0\|h\|_1^2$,
then $\alpha_{p_0}(W)\ge\delta_0$,
which is the second conclusion of the lemma.

Hence, we can assume that the integral in~\eqref{eq:hdens} is at least $p_0\|h\|_1^2$ for every $x\in [0,1]\setminus A$.
Since the $3$-edge path $P_4$ is Sidorenko, we conclude by considering the graphon $W[h]$ that
\[t_{W'}^{C_5}(x)\ge \|h\|_1^4\cdot t(P_4,W[h])\ge \|h\|_1^4 p_0^3\ge d_0^4p_0^3\]
for every $x\in [0,1]\setminus A$.
It follows that
\begin{align*}
t(K_{2n,2n,C_5},W) & \ge t(K_{2n,2n,C_5},W') \\
                   & \ge t(K_{2n,2n},W')\cdot\left(d_0^4p_0^3\right)^n \\
		   & \ge \left(p^4+\varepsilon_0/2\right)^{n^2}\left(d_0^4p_0^3\right)^n \\
		   & \ge p^{4n^2}\left(1+\varepsilon_0/2\right)^{n^2}\left(d_0^4p_0^3\right)^n \\
		   & \ge p^{4n^2}\left(\left(1+\varepsilon_0/2\right)^{n_0}d_0^4p_0^3\right)^n\ge p^{4n^2}\ge p^{4n^2+5n}.
\end{align*}
Hence, the first conclusion of the lemma holds.
\end{proof}

We are now ready to prove the main theorem of this section, which implies Theorem~\ref{thm:append}.
Theorem~\ref{thm:Knn-common} is a variant of Theorem~\ref{thm:append}
where a very small proportion of the edges can be left uncolored.
This additional flexibility is needed for an inductive argument used in the proof of the theorem.

\begin{theorem}
\label{thm:Knn-common}
For every $k\in\NN$, there exist $n_k\in\NN$ and $\delta_k\in (0,1)$ with the following property.
If $W_1,\ldots,W_k$ are graphons such that $t(K_2,W_1+\cdots+W_k)\ge 1-\delta_k$, then
\[\sum_{i\in [k]} t(K_{2n,2n,C_5},W_i)\ge\frac{t(K_2,W_1+\cdots+W_k)^{4n^2+5n}}{k^{4n^2+5n-1}}\]
for every $n\ge n_k$.
\end{theorem}

\begin{proof}
We proceed by induction on $k\in\NN$.
Suppose first that $k=1$.
We apply Lemma~\ref{lm:Knn-local} with $p_0=3/4$ to get $\varepsilon_0\in (0,1)$.
We show that the statement of the theorem is true for $n_1=1$ and $\delta_1=\varepsilon_0/4$.
Let $W_1$ be a graphon with density $p\ge 1-\delta_1\ge 3/4$.
Observe that
\[t(K_{2,2},W)-p^4\le 1-p^4\le 1-(1-\delta_1)^4\le 4\delta_1=\varepsilon_0.\]
Hence, Lemma~\ref{lm:Knn-local} implies that
\[t(K_{2n,2n,C_5},W_1)\ge p^{4n^2+5n}.\]
This completes the proof in the base case $k=1$.

Now, suppose that we have already established the existence of $n_1,\ldots,n_{k-1}$ and $\delta_1,\ldots,\delta_{k-1}$.
Choose $p_0=\delta_{k-1}/4k$ and apply Lemma~\ref{lm:Knn-local} to get $\varepsilon_0$.
We then apply Lemma~\ref{lm:Knn-far} with $p_0$ and $\varepsilon_0$ to obtain $n_0$ and $\delta_0$.
Set $\delta_k=\frac{\delta_{k-1}\delta_0^2}{4k}$.
Finally, choose $n_k$ such that $n_k\ge \max\{n_0, n_{k-1}\}$ and
\[\left(\frac{1}{k}+\frac{1}{2k(k-1)}\right)^{4n_k+5}\delta_0^{8}\ge\frac{k}{k-1}\left(\frac{1}{k}\right)^{4n_k+5}.\]
The choice of $n_k$ yields that the following holds for all $n\ge n_k$:
\[(k-1)\left(\frac{1}{k}+\frac{1}{2k(k-1)}\right)^{4n^2+5n}\delta_0^{8n}\ge k\left(\frac{1}{k}\right)^{4n^2+5n}.\]

Let graphons $W_1,\ldots,W_k$ satisfying the assumption of the theorem be given and let $n\ge n_k$.
Further, let $p=t(K_2,W_1+\cdots+W_k)$ be the density of the graphon $W_1+\cdots+W_k$; note that $p\ge 1-\delta_k$.

We distinguish two cases.
First suppose that there exists $i\in [k]$ such that $\alpha_{p_0}(W_i)\ge\delta_0$,
i.e., one of the graphons $W_1,\ldots,W_k$ contains a large sparse part.
Note that this case includes the case that the density of one of the graphons is at most $p_0$.
By symmetry, we can assume that $\alpha_{p_0}(W_k)\ge\delta_0$.
Let $h:[0,1]\to [0,1]$ be such that $\|h\|_1\ge\delta_0$ and
\[\int_{[0,1]^2}h(x)W_k(x,y)h(y)\dd x\dd y\le p_0\|h\|_1^2.\]
Since it holds that
\[\sum_{i\in [k]}\int_{[0,1]^2}h(x)W_i(x,y)h(y)\dd x\dd y\ge \|h\|_1^2-\delta_k,\]
we obtain that
\begin{align*}
\sum_{i\in [k-1]}\int_{[0,1]^2}h(x)W_i(x,y)h(y)\dd x\dd y & \ge \|h\|_1^2-p_0\|h\|_1^2-\delta_k\\
                                           & \ge \|h\|_1^2\left(1-\frac{\delta_{k-1}}{2k}\right)\\
		 		 	   & \ge \|h\|_1^2\left(1-\frac{1}{2k}\right).
\end{align*}
Since it holds that
\[t(K_2,W_1[h]+\cdots+W_{k-1}[h])\ge 1-\frac{\delta_{k-1}}{2k}\ge 1-\delta_{k-1},\]
we can apply induction to $W_1[h],\ldots,W_{k-1}[h]$ and arrive at the following:
\begin{align*}
\sum_{i\in [k-1]} t(K_{2n,2n,C_5},W_i) & \ge \|h\|_1^{8n}\sum_{i\in [k-1]}t(K_{2n,2n,C_5},W_i[h]) \\
     & \ge \|h\|_1^{8n}(k-1)\left(\frac{1-1/2k}{k-1}\right)^{4n^2+5n}\\
     & \ge \delta_0^{8n}(k-1)\left(\frac{1}{k}+\frac{1}{2k(k-1)}\right)^{4n^2+5n}\\
     & \ge k\left(\frac{1}{k}\right)^{4n^2+5n}\ge\frac{p^{4n^2+5n}}{k^{4n^2+5n-1}}.
\end{align*}
Hence, in the following, we assume that $\alpha_{p_0}(W_i)<\delta_0$ for every $i\in [k]$.
In particular, we assume that $t(K_2,W_i)\ge p_0$ for every $i\in [k]$
and so we can apply Lemmas~\ref{lm:Knn-local} and~\ref{lm:Knn-far} to each of $W_1,\dots,W_k$.

Based on whether it holds that $t(K_{2,2},W_i)\le t(K_2,W_i)^4+\varepsilon_0$ or not,
Lemma~\ref{lm:Knn-local} or Lemma~\ref{lm:Knn-far}, respectively, implies
\[t(K_{2n,2n,C_5},W_i)\ge t(K_2,W_i)^{4n^2+5n}\]
for every $i\in [k]$.
Therefore, we obtain that
\[\sum_{i\in [k]}t(K_{2n,2n,C_5},W_i)\ge \sum_{i\in [k]} t(K_2,W_i)^{4n^2+5n}\]
which is at least $k\left(\frac{p}{k}\right)^{4n^2+5n}$ by convexity.
This concludes the proof of the theorem.
\end{proof}

\section{Sidorenko and locally Sidorenko graphs}
\label{sec:Sidorenko}

In this section, we prove that a graph is $k$-common for all $k\geq2$ if and only if
it is Sidorenko and that
no graph of odd girth is locally $k$-common for any $k\ge 3$.
We start with the former statement.

\begin{proof}[Proof of Theorem~\ref{thm:Sidorenko}]
We first show that if a graph $H$ is Sidorenko, then it is $k$-common for every $k\in\NN$.
Fix a Sidorenko graph $H$ and an integer $k\ge 2$.
Let $W_1,\ldots,W_k$ be graphons such that $W_1+\cdots+W_k=1$ and
let $p_1,\ldots,p_k$ be their respective densities.
Note that $p_1+\cdots+p_k=1$.
Since $H$ is Sidorenko,
\[t(H,W_1)+\cdots+t(H,W_k)\ge p_1^{\|H\|}+\cdots+p_k^{\|H\|}\ge k\left(\frac{p_1+\cdots+p_k}{k}\right)^{\|H\|}=k^{-\|H\|+1}.\]
Therefore, $H$ is $k$-common.

To complete the proof, we need to show that
if a graph $H$ is not Sidorenko, then there exists $k\ge 2$ such that $H$ is not $k$-common.
Fix a graph $H$ that is not Sidorenko and
let $W$ be a graphon with density $p$ such that $t(H,W)<p^{\|H\|}$.
Set $\varepsilon=p^{\|H\|}-t(H,W)$.
By Lemma~\ref{lm:reg}, there exists a step graphon $W'$ with density $p$ such that
the cut distance between $W$ and $W'$ is at most $\varepsilon/(2\|H\|)$.
Lemma~\ref{lm:cutdist} implies that
\[t(H,W')\le t(H,W)+\varepsilon/2=p^{\|H\|}-\varepsilon/2.\]
By splitting each of the parts of $W'$ into the same number of equal size smaller parts,
we can assume that the number $m$ of parts of $W'$ satisfies
\[4\|H\|\le m\varepsilon\qquad\mbox{and}\qquad p^{\|H\|}-\varepsilon/4<(p-1/m)^{\|H\|}.\]
Let $A_1,\ldots,A_m$ be the parts of $W'$ and
let $d_{ij}$, $i,j\in [m]$ be the value of $W'$ on the tile $A_i\times A_j$.
Further, let $\delta$ be the average of $d_{ij}$ taken over all pairs $i$ and $j$ such that $1\le i<j\le m$ and
let $W''$ be the step graphon with the same $m$ parts as $W'$ obtained from $W'$
by making each of the $m$ diagonal tiles to be equal to $\delta$.
Note that the density of the whole graphon $W''$ is $\delta$ and $\delta\ge p-1/m$.
Since the cut distance between $W'$ and $W''$ is at most $m/m^2=1/m$,
Lemma~\ref{lm:cutdist} implies that
\begin{align*}
t(H,W'') & \le t(H,W')+\|H\|\cdot\dcut{W}{W'}\\
        & \le t(H,W')+\varepsilon/4\\
	& \le p^{\|H\|}-\varepsilon/4<(p-1/m)^{\|H\|}\le\delta^{\|H\|}.
\end{align*}
Next choose an integer $\ell\in\NN$ such that $1\le\delta\ell m!$ and set $k=\ell m!$.
We next define $k$ graphons that witness that $H$ is not $k$-common;
the $k$ graphons will be indexed by pairs consisting of a permutation $\sigma\in S_m$ of order $m$ and an integer $s\in [\ell]$.
The graphon $W_{\sigma,s}$ for $\sigma\in S_m$ and $s\in [\ell]$
is the step graphon with $m$ parts $A_1,\ldots,A_m$ such that
the graphon $W_{\sigma,s}$ on a tile $A_i\times A_j$, $i,j\in [m]$,
is equal to $1/k$ if $i=j$ and
is equal to $\frac{d_{\sigma(i)\sigma(j)}}{k\delta}$ if $i\neq j$ (note that $\frac{d_{\sigma(i)\sigma(j)}}{k\delta}\le\frac{1}{k\delta}\le 1$).
Note that the density of each of the graphons $W_{\sigma,s}$ is $\frac{1}{k}$.
Moreover, the average value of all the $k$ graphons on any of the tiles is $\frac{1}{k}$.
Consequently, the $k$ graphons $W_{\sigma,s}$, $\sigma\in S_m$ and $s\in [\ell]$, sum to the $1$-constant graphon.
Since the homomorphism density of $H$ in each of the graphons $W_{\sigma,s}$, $\sigma\in S_m$ and $s\in [\ell]$,
is equal to $\frac{1}{(k\delta)^{\|H\|}}t(H,W'')<k^{-\|H\|}$,
it follows that $H$ is not $k$-common.
\end{proof}

We next show that locally $k$-common graphs for any $k\ge 3$
are precisely locally Sidorenko graphs (cf.~Theorem~\ref{thm:localSid}).

\begin{proof}[Proof of Theorem~\ref{thm:local}]
Fix an integer $k\ge 3$ for the proof, and
a graph $H$ with girth $\ell$ where $\ell$ is odd.

\begin{figure}
\begin{center}
\epsfbox{kcommon-2.mps}
\end{center}
\caption{The kernel $U$ used in the proof of Theorem~\ref{thm:local} for $\ell=5$.
         The origin of the coordinate system is in the top left corner.}
\label{fig:local}
\end{figure}

Let $A_1,\ldots,A_{2\ell}$ be any partition of the interval $[0,1]$ to $2\ell$ disjoint measurable sets,
each of measure $(2\ell)^{-1}$.
Consider a kernel $U$ defined as follows (also see Figure~\ref{fig:local}):
\[U(x,y)=\begin{cases}
         +1 & \mbox{if $x\in A_i$, $y\in A_j$, $\lceil i/\ell\rceil=\lceil j/\ell\rceil$ and $i=(j\pm 1)\bmod\ell$,} \\
         -1 & \mbox{if $x\in A_i$, $y\in A_j$, $\lceil i/\ell\rceil\not=\lceil j/\ell\rceil$ and $i=(j\pm 1)\bmod\ell$,} \\
	 0  & \mbox{otherwise.}
         \end{cases}\]
Let $G$ be a graph that has a vertex $v$ of degree one and let $v'$ be the neighbor of $v$.
Note that
\begin{align*}
t(G,U) & = \int_{[0,1]^{V(G)}}\prod_{uu'\in E(G)}U(x_u,x_{u'})\dd x_{V(G)} \\
       & = \int_{[0,1]^{V(G)\setminus\{v\}}}\prod_{\substack{uu'\in E(G)\\uu'\not=vv'}}U(x_u,x_{u'})\cdot \left(\int_{[0,1]}U(x_{v'},x_v)\dd x_v\right)\dd x_{V(G)\setminus\{v\}} \\
       & = \int_{[0,1]^{V(G)\setminus\{v\}}}\prod_{\substack{uu'\in E(G)\\uu'\not=vv'}}U(x_u,x_{u'})\cdot 0\dd x_{V(G)\setminus\{v\}} = 0
\end{align*}
We conclude that $t(G,U)=0$ for every graph $G$ with a vertex of degree one.

We next compute $t(C_{\ell},U)$. Observe that the product
$\prod_{i\in [\ell]}U(x_i,x_{(i+1)\bmod\ell})$
is non-zero for $x_1,\ldots,x_{\ell}\in [0,1]$ if and only if
there exists $j\in [\ell]$ such that
either $x_i\in A_{(i+j)\bmod\ell}\cup A_{(i+j)\bmod\ell+\ell}$ for every $i\in [\ell]$ or
$x_i\in A_{(\ell-i+j)\bmod\ell}\cup A_{(\ell-i+j)\bmod\ell+\ell}$ for every $i\in [\ell]$;
if the product is non-zero, then it is equal to one.
Hence, it follows that
\[
t(C_\ell,U) = \int_{[0,1]^\ell}\prod_{i\in [\ell]}U(x_i,x_{(i+1)\bmod\ell})\dd x_{[\ell]}
            = 2\ell\cdot\prod_{i\in [\ell]}|A_i\cup A_{i+\ell}|=\frac{2}{\ell^{\ell-1}} \]

We next consider the following graphons: $W_1=W_2=1/k+\varepsilon U$, $W_3=1/k-2\varepsilon U$ and $W_4=\cdots=W_k=1/k$.
We will estimate the homomorphism density of $H$ in $W_1,\ldots,W_k$ using Proposition~\ref{prop:epsU}.
Note that if $F$ is a subset of edges of $H$ such that $1\le |F|\le\ell$,
then $H[F]$ contains a vertex of degree one unless $H[F]$ is a union of a cycle of length $\ell$ and isolated vertices.
In particular, $t(H[F],U)=0$ for a set $F$ of $\ell$ edges unless $F$ is the edge set of a cycle of length $\ell$.
Using Proposition~\ref{prop:epsU}, we obtain that
\begin{align*}
t(H,W_1)+\cdots+t(H,W_k) & = 2t(H,1/k+\varepsilon U)+t(H,1/k-2\varepsilon U)\\ &+(k-3)t(H,1/k) \\
                         & = k^{-\|H\|+1}+2\cdot\frac{2m_{\ell}}{\ell^{\ell-1}}k^{-\|H\|+\ell}\varepsilon^{\ell}-\frac{2^{\ell+1}m_{\ell}}{\ell^{\ell-1}}k^{-\|H\|+\ell}\varepsilon^{\ell}\\ &+O(\varepsilon^{\ell+1}) \\
			 & = k^{-\|H\|+1}-\frac{(2^{\ell+1}-4)m_{\ell}}{\ell^{\ell-1}}k^{-\|H\|+\ell}\varepsilon^{\ell}+O(\varepsilon^{\ell+1})
\end{align*}
where $m_{\ell}$ is the number of cycles of length $\ell$ in $H$.
Since $2^{\ell+1}-4>0$, there exists $\varepsilon_0>0$ such that
\[t(H,W_1)+\cdots+t(H,W_k)<k^{-\|H\|+1}\]
for every $\varepsilon\in(0,\varepsilon_0)$.
We conclude that $H$ is not locally $k$-common, which completes the proof of the theorem.
\end{proof}

\section{Open problems}

We conclude with two open problems.
Theorem~\ref{thm:append} provides an example of a non-bipartite $k$-common graph for every $k\geq2$.
A natural next question is whether there exist $k$-common graphs of arbitrary large chromatic number.
Currently, the only known example of a $2$-common graph of chromatic number greater than three is the
$5$-wheel~\cite{HatHKNR12} and so this question is interesting even in the case $k=2$ and
$\ell\geq5$.

\begin{problem}
\label{prob:highChi}
For every $k\ge 2$ and $\ell\ge 4$, construct a $k$-common $\ell$-chromatic graph.
\end{problem}

The second problem stems from Theorem~\ref{thm:local}
which characterizes locally $k$-common graphs for $k\ge 3$.
Interestingly, we do not have a similar characterization of locally $2$-common graphs and
we even miss a natural conjecture for such a characterization.

\begin{problem}
Characterize graphs that are locally $2$-common.
\end{problem}

Locally $2$-common graphs include forests, all graphs with even girth, the triangle and the $5$-wheel in particular,
since these graphs are locally Sidorenko or $2$-common.
On the other hand,
Cs\'oka, Hubai and Lov\'asz~\cite{CsoHL19} showed that for every graph $H$ containing $K_4$ and every $\varepsilon>0$,
there exists a kernel $U$ such that $\|U\|_{\infty}\le\varepsilon$ and
\[t(H,1/2+U)+t(H,1/2-U)<2^{-\|H\|}.\]
In particular, no graph containing $K_4$ is locally $2$-common.
We remark that the notion of locally common graphs used in~\cite{CsoHL19} is formally weaker than the notion used in this paper,
i.e., every graph locally $2$-common in the sense used in this paper is locally common in the sense used in~\cite{CsoHL19},
however, it is not obvious whether the converse holds.
For completeness, we present a simple argument that $K_4$ is not locally $2$-common,
which is based on a construction of Franek and R\"odl~\cite{FraR93} of a kernel $U$ such that
\[t(K_4,1/2+U)+t(K_4,1/2-U)\le 0.987314\times\frac{1}{32}\quad\mbox{and}\quad\int_{[0,1]}U(x,y)\dd y=0\]
for every $x\in [0,1]$.
For $z\in (0,1]$, define a kernel $U_z$ as
\[U_z(x,y)=\begin{cases}
           U(x/z,y/z) & \mbox{if $(x,y)\in [0,z]^2$,} \\
	   0 & \mbox{otherwise.}
	   \end{cases}\]
Since the cut norm of $U_z$ is at most $z^2$ and $t(K_4,1/2+U_z)+t(K_4,1/2-U_z)<1/32$ (here, we use that the kernel $U_z$
is ``$0$-regular''),
it follows that $K_4$ is not locally $2$-common.

\section*{Acknowledgement}

The authors would like to thank L\'aszl\'o Mikl\'os Lov\'asz for insightful comments on the graph limit notions discussed in this paper, and the two anonymous reviewers for preparing very detailed reports in an unusually fast way;
the comments of the reviewers helped to substantially improve the presentation of our results.

\bibliographystyle{bibstyle}
\bibliography{kcommon}

\end{document}


TITLE: Little $o$ notation in the proof of central limit theorem.
QUESTION [1 upvotes]: In the proof im reading for the CLT, they seem to be using the following claim:

If $h(t)=o(t^2)$ then if $$g(n)\stackrel{\text{def}}{=}h\Big(\frac{t}{\sigma\sqrt{n}}\Big)$$ we have that $g(n)=o(\frac{1}{n})$.

More explicitly, I have a function $h$ that satisfies $$\lim_{t \rightarrow \infty} \frac{h(t)}{t^2} = 0$$
(and I seem to know nothing else about $h$) and then they are telling me that
$$\lim_{n \rightarrow \infty} h\Big(\frac{t}{\sigma\sqrt{n}}\Big) n = 0 .$$
But I don't see how I can say anything about $\lim_{x \rightarrow 0} h(x)$ just from knowing $h(t)=o(t^2)$.
Is the claim true? How can I show it?

REPLY [1 votes]: By definition
$$o(f)=\left\{g:\exists N \in \mathbb{N}, \exists \varepsilon (n), \lim_{n \to \infty}\varepsilon (n)=0, n>N \Rightarrow \ g(n)=\varepsilon (n) f(n)\right\}$$
So $h(t)=o(t^2)$, i.e. $h(t) \in o(t^2)$, assumed you mean case $t \to 0,$ gives $ h\left(\frac{1}{n} \right)=\varepsilon \left(\frac{1}{n} \right) \left(\frac{1}{n} \right)^2$, for $n>N$.
Now we have $g(n) = h\Big(\frac{t}{\sigma\sqrt{n}}\Big) = \varepsilon\Big(\frac{t}{\sigma\sqrt{n}}\Big)\cdot \Big(\frac{t}{\sigma\sqrt{n}}\Big)^2 = \varepsilon\Big(\frac{t}{\sigma\sqrt{n}}\Big)\cdot \Big(\frac{t}{\sigma}\Big)^2 \frac{1}{n}$


text:
\begin{document}

\maketitle

\begin{abstract}
We consider the task of sampling with respect to a log concave probability distribution. The potential of the target distribution is assumed to be composite, \textit{i.e.}, written as the sum of a smooth convex term, and a nonsmooth convex term possibly taking infinite values. The target distribution can be seen as a minimizer of the Kullback-Leibler divergence defined on the Wasserstein space (\textit{i.e.}, the space of probability measures). In the first part of this paper, we establish a strong duality result for this minimization problem. In the second part of this paper, we use the duality gap arising from the first part to study the complexity of the Proximal Stochastic Gradient Langevin Algorithm (PSGLA), which can be seen as a generalization of the Projected Langevin Algorithm. Our approach relies on viewing PSGLA as a primal dual algorithm and covers many cases where the target distribution is not fully supported. In particular, we show that if the potential is strongly convex, the complexity of PSGLA is $\cO(1/\varepsilon^2)$ in terms of the 2-Wasserstein distance. In contrast, the complexity of the Projected Langevin Algorithm is $\cO(1/\varepsilon^{12})$ in terms of total variation when the potential is convex.
\end{abstract}

\section{Introduction}

Sampling from a target distribution is a fundamental task in machine learning. Consider the Euclidean space $\sX = \bR^d$ and a convex function $V : \sX \to (-\infty,+\infty]$. Assuming that $\exp(-V)$ has a positive finite integral w.r.t.\ the Lebesgue measure $\Leb$, we consider the task of sampling from the distribution $\mu^\star$ whose density is proportional to $\exp(-V(x))$ (we shall write $\mu^\star \propto \exp(-V)$).

If $V$ is smooth, Langevin algorithm produces a sequence of iterates $(x^k)$ asymptotically distributed according to a distribution close to $\mu^\star$. Langevin algorithm performs iterations of the form
\begin{equation}
    \label{eq:Langevin-vanilla}
    x^{k+1} = x^k - \gamma \nabla V(x^k) + \sqrt{2\gamma} W^{k+1},
\end{equation}
where $\gamma >0$ and $(W^k)_k$ is a sequence of i.i.d.\ standard Gaussian vectors in $\sX$. Each iteration of~\eqref{eq:Langevin-vanilla} can be seen as a gradient descent step for $V$, where the gradient of $V$ is perturbed by a Gaussian vector. Hence, the iterations of Langevin algorithm look like those of the stochastic gradient algorithm; however the noise in Langevin algorithm is scaled by $\sqrt{\gamma}$ instead of $\gamma$. Nonasymptotic bounds for Langevin algorithm have been established in~\cite{dalalyan2017theoretical,durmus2017nonasymptotic}. Moreover, Langevin algorithm can be interpreted as an inexact gradient descent method to minimize the Kullback-Leibler (KL) divergence w.r.t.\ $\mu^\star$ in the space of probability measures~\cite{cheng2018convergence,durmus2018analysis,bernton2018langevin,wibisono2018sampling,ma2019there,ambrosio2008gradient}.

In many applications, the function $V$ is naturally written as the sum of a smooth and a nonsmooth term. In Bayesian statistics for example, $\mu^\star$ typically represents some posterior distribution. In this case, $V$ is the sum of the $\log$-likelihood (which is itself a sum over the data points) and the possibly nonsmooth potential of the prior distribution~\cite{welling2011bayesian,durmus2018efficient,durmus2018analysis}, which plays the role of a regularizer. In some other applications in Bayesian learning, the support of $\mu^\star$ is not the whole space $\sX$~\cite{bubeck2018sampling,brosse2017sampling} (\textit{i.e.}, $V$ can take the value $+\infty$). In order to cover these applications, we consider the case where $V$ is written as
\begin{equation}
\label{eq:V}
V(x) \eqdef \bE_\xi(f(x,\xi)) + G(x),
\end{equation}
where $\xi$ is a random variable, $f(\cdot,s) : \sX \to \bR$ for every $s \in \Xi$, $F(x) = \bE_\xi(f(x,\xi))$ is smooth and convex and $G : \sX \to (-\infty,+\infty]$ is nonsmooth and convex. We assume to have access to the stochastic gradient $\nabla_x f(x,\xi)$ (where $\xi$ is a random variable with values in $\Xi$) and to the proximity operator $\prox_{\gamma G}$ of $G$. The template~\eqref{eq:V} covers many log concave densities\cite{Chaux2007,durmus2018efficient,durmus2018analysis,bubeck2018sampling}. In optimization, the minimization of $V$ can be efficiently tackled by the proximal stochastic gradient algorithm \cite{atc-for-mou-17}. Inspired by this optimization algorithm, the Proximal Stochastic Gradient Langevin Algorithm (PSGLA)~\cite{durmus2018analysis} is the method performing proximal stochastic gradient Langevin steps of the form
\begin{equation}
    \label{eq:psgla}
    x^{k+1} = \prox_{\gamma G}\left(x^k - \gamma \nabla_x f(x^k,\xi^{k+1}) + \sqrt{2\gamma} W^{k+1}\right),
\end{equation}
where $\gamma > 0$, $(W^k)$ is a sequence of i.i.d.\ standard Gaussian random vectors in $\sX$, and $(\xi^k)$ is a sequence of i.i.d.\ copies of $\xi$. Remarkably, the iterates $x^k$ of PSGLA remain in the domain of $G$, \textit{i.e.}, the support of $\mu^\star$, a property that is useful in many contexts. When $G$ is Lipschitz continuous, the support of $\mu^\star$ is $\sX$ and PSGLA can be interpreted as an inexact proximal gradient descent method for minimizing KL, with convergence rates  proven in terms of the KL divergence \cite{durmus2018analysis}. However, for  general $G$, the KL divergence can take infinite values along PSGLA. Therefore, a new approach is needed.

 \subsection{Related works}
\label{sec:relat}

\paragraph{First, various instances of the PSGLA algorithm have already been considered.} The only instance allowing $G(x)$ to be infinite (\textit{i.e.}, the support of $\mu^\star$  not to be $\sX$) is the Projected Langevin Algorithm~\cite{bubeck2018sampling}, which corresponds to our setting in the special case with $G = \iota_C$ (\textit{i.e.}, the indicator function of a convex body\footnote{A convex body is a compact convex set with a nonempty interior.} $C$), and $\nabla f(\cdot,s) \equiv \nabla F$ for every $s$ (\textit{i.e.}, the full gradient of $F$). In this case, $\prox_{\gamma G}$ is the orthogonal projection onto $C$ and $\mu^\star$ is supported by $C$. Bubeck et al~\cite{bubeck2018sampling} provide complexity results in terms of sufficient number of iterations to achieve $\varepsilon$ accuracy in terms of the Total Variation between the target distribution $\mu^\star$ and the current iterate distribution. Assuming that $F$ is convex and smooth, the complexity of the Projected Langevin Algorithm is $\cO(1/\varepsilon^{12})$\footnote{Our big O notation ignores logarithm factors.}, and if $F \equiv 0$, the complexity is improved to $\cO(1/\varepsilon^8)$.

Other instances of PSGLA were proposed in the case where $G$ is Lipschitz continuous or smooth (and hence finite). Wibisono~\cite{wibisono2018sampling} considered the case with $F = G$ and $\nabla f(\cdot,s) \equiv \nabla F$, proposing the  Symmetrized Langevin Algorithm (SLA),  and showed that the current iterate distribution converges linearly in Wasserstein distance to the invariant measure of the SLA, if $F$ is strongly convex and smooth.
Durmus et al~\cite{durmus2018analysis} considered the case where $G$ is Lipschitz continuous, and showed that the complexity of PSGLA is $\cO(1/\varepsilon^2)$ in terms of the KL divergence and $\cO(1/\varepsilon^4)$ in terms of the Total Variation distance if $F$ is convex and smooth. If $F$ is strongly convex, the complexity is  $\cO(1/\varepsilon^2)$ in Wasserstein distance and $\cO(1/\varepsilon)$ in KL divergence. Bernton~\cite{bernton2018langevin} studied a setting similar to~\cite{durmus2018analysis} and derived a similar result for the Proximal Langevin Algorithm (\textit{i.e.}, PSGLA without the gradient step) in the strongly convex case. The Proximal Langevin Algorithm was also studied in a recent paper of Wibisono~\cite{wibisono2019proximal}, where a rapid convergence result was proven in the case where $G$ is nonconvex but satisfies further smoothness and geometric assumptions.

\paragraph{Second, the task of sampling w.r.t.\ $\mu^\star$, where $G$ is nonsmooth and possibly takes infinite values, using Langevin algorithm, has also been considered.} When $F$ is strongly convex and $G$ an indicator function of a bounded convex set, the existence of an algorithm achieving $\cO(1/\varepsilon^2)$ in Wasserstein and Total Variation distances was proven by Hsieh et al~\cite[Theorem 3]{hsieh2018mirrored}. However, an actual algorithm is only given in a specific, although nonconvex, case. Besides, MYULA (Moreau-Yosida Unadjusted Langevin Algorithm)~\cite{durmus2018efficient,brosse2017sampling} can tackle the task of sampling from $\mu^\star$ efficiently. MYULA is equivalent to Langevin algorithm~\eqref{eq:Langevin-vanilla} applied to sampling from $\mu^\lambda \propto \exp(-F-G^\lambda)$, where $G^\lambda$ is the Moreau-Yosida approximation of $G$~\cite{atchade2015moreau}. By choosing the smoothing parameter $\lambda >0$ appropriately, and making assumptions that allow to control the distance between $\mu
^\lambda$ and $\mu^\star$ (\textit{e.g.}, $G$ Lipschitz or $G = \iota_C$), complexity results for MYULA were established in~\cite{durmus2018efficient,brosse2017sampling}. For example, if $G$ is the indicator function of a convex body, Brosse et al~\cite{brosse2017sampling} show that the complexity of MYULA is $\cO(1/\varepsilon^{6})$ in terms of the Total Variation distance (resp.\ 1-Wasserstein distance) if $F$ is convex and smooth (resp., if $F$ is strongly convex and smooth), provided that the algorithm is initialized from a minimizer of $V$. Similarly to PSGLA, MYULA involves one proximal step and one gradient step per iteration. However, the support of the smoothed distribution $\mu^\lambda$ is always $\sX$ (even if $\mu^\star$ is not fully supported), and therefore the iterates of MYULA do not remain in the support of the target distribution $\mu^\star$, contrary to PSGLA.

\paragraph{Finally, the task of sampling w.r.t.\ $\mu^\star$, where $V$ is not smooth but finite, has also been considered.} The Perturbed Langevin Algorithm proposed by Chatterji et al~\cite{chatterji2019langevin} allows to sample from $\mu^\star$ in the case when $G$ satisfies a weak form of smoothness (generalizing both Lipschitz continuity and smoothness) and without accessing its proximity operator. Finally, if $G$ is Lipschitz continuous, the Stochastic Proximal Langevin Algorithm proposed by Salim et al~\cite{salim2019stochastic}  and Schechtman et al\cite{schechtman2019passty} allows to sample from $\mu^\star$ using  cheap stochastic proximity operators only.

\subsection{Contributions}

In summary, PSGLA has complexity $\cO(1/\varepsilon^{2})$ in 2-Wasserstein distance if $F$ is strongly convex~\cite{durmus2018analysis} and $G$ is Lipschitz. The only instance of PSGLA allowing $G$ to be infinite is the Projected Langevin Algorithm. It has complexity $\cO(1/\varepsilon^{12})$ in Total Variation~\cite{bubeck2018sampling}\footnote{This result also holds if $F$ is not strongly convex.} and only applies to the case where $G$ is the indicator of a convex body. In the latter case, another Langevin algorithm called MYULA has complexity $\cO(1/\varepsilon^{6})$ in 1-Wasserstein distance~\cite{brosse2017sampling}, but allows the iterates to leave the support of $\mu^\star$. Besides, still in the case where $G$ is an indicator function, there exists a Langevin algorithm achieving $\cO(1/\varepsilon^2)$ rate in the Wasserstein distance~\cite{hsieh2018mirrored}.

{\em In this paper, we consider other (\textit{i.e.}, new) cases where $G$ can take infinite values. More precisely, we consider a general nonsmooth convex function $G$ and we assume that $\exp(-V)$ has a mild Sobolev regularity. We develop new mathematical tools (\textit{e.g.}, a Lagrangian for the minimization of KL), that have their own interest, to obtain our complexity results.  Our main result is to show that, surprisingly, PSGLA still has the complexity $\cO(1/\varepsilon^2)$ in 2-Wasserstein distance if $F$ is strongly convex, although $G$ can take infinite values. We also show that, if $F$ is just convex, PSGLA has the complexity $\cO(1/\varepsilon^2)$ in terms of a newly defined duality gap, which can be seen as the notion that replaces KL, since KL can be infinite.}

Our approach follows the line of works~\cite{cheng2018convergence,durmus2018analysis,wibisono2018sampling,bernton2018langevin,ma2019there,wibisono2019proximal,vempala2019rapid,rolland2020double} that formulate the task of sampling form $\mu^\star$ as the problem of minimizing the KL divergence w.r.t $\mu^\star$.

In summary, our contributions are the following.

$\bullet$ In the first part of the paper, we  reformulate the task of sampling from $\mu^\star$ as the resolution of a monotone inclusion defined on the space of probability measures.  We subsequently  use this reformulation to  define a duality gap for the minimization of the KL divergence, and show that  strong duality holds.

$\bullet$ In the second part of this paper,  we use this reformulation to  represent PSGLA as a primal dual stochastic Forward Backward algorithm involving monotone operators.

$\bullet$ This new representation of PSGLA, along with the strong duality result from the first part, allows us to  prove new complexity results for PSGLA that extend and improve the state of the art.

$\bullet$ Finally, we conduct some numerical experiments for sampling from a distribution supported by a set of matrices (see appendix).

In the first part we combine tools from optimization duality~\cite{condatreview} and optimal transport~\cite{ambrosio2008gradient} and in the second part we combine tools from the analysis of the Langevin algorithm~\cite{durmus2018analysis}, and the analysis of primal dual optimization algorithms~\cite{drori2015simple,chambolle2016ergodic}.

The remainder is organized as follows. In Section~\ref{sec:background} we provide some background knowledge on convex analysis and optimal transport. In Section~\ref{sec:pd-opt} we develop a primal dual optimality theory for the task of sampling from $\mu^\star$. In Section~\ref{sec:alg} we give a new representation of PSGLA using monotone operators. We use it to state our main complexity result on PSGLA in Section~\ref{sec:res}. Numerical experiments and all proofs are postponed to the appendix. Therein, we also provide further intuitions on PSGLA, namely the connection between gradient descent and Langevin algorithm~\cite{durmus2018analysis} and the connection between primal dual optimization and our approach. Finally, an extension of PSGLA for handling a third (stochastic, Lipschitz continuous and proximable) term in the definition of the potential $V$~\eqref{eq:V} is provided at the end of the appendix.

\section{Background}
\label{sec:background}
Throughout this paper, we use the conventions $\exp(-\infty) = 0$ and $1/0 = +\infty$.
\subsection{Convex analysis}
In this section, we recall some facts from convex analysis. These facts will be used in the proofs without mention. For more details, the reader is referred to~\cite{bau17}.
\subsubsection{Convex optimization}
By  $\Gamma_0(\sX)$ we denote the set of proper, convex, lower semicontinuous functions $\sX \to (-\infty,+\infty]$. A function $F \in \Gamma_0(\sX)$ is $L$-smooth if $F$ is differentiable and its gradient $\nabla F$ is $L$-Lipschitz continuous. Consider $G \in \Gamma_0(\sX)$ and denote $\dom(G) \eqdef \{x \in \sX \;: \; G(x) < \infty\}$ its domain. Given $x \in \sX$, a subgradient of $G$ at $x$ is any vector $y \in \sX$ satisfying
\begin{equation}
    G(x) + \ps{y,x' - x} \leq G(x'),
\end{equation}
for every $x' \in \sX$. If the set $\partial G(x)$ of subgradients of $G$ at $x$ is not empty, then there exists a unique element of $\partial G(x)$ with minimal norm. This particular subgradient is denoted $\partial^0 G(x)$. The set valued map $\partial G(\cdot)$ is called the subdifferential. The proximity operator of $G$, denoted $\prox_{G}$, is defined by
\begin{equation}
    \label{eq:prox}
    \prox_{G}(x) \eqdef \argmin_{x' \in \sX} \left\{G(x') + \tfrac{1}{2}\|x-x'\|^2\right\}.
\end{equation}
By $\iota_C(\cdot)$ we denote the indicator function of set $C$ given by $\iota_C(x) = 0$ if $x \in C$ and $\iota_C(x) =+\infty$ if $x \notin C$. If $G=\iota_C$, where $C$ is a closed convex set, then $\prox_{G}$ is the orthogonal projection onto $C$. Moreover, $\prox_{G}(x)$ is the only solution $x'$ to the inclusion $x \in x' + \partial G(x')$. The Fenchel transform of $G$ is the function $G^\ast \in \Gamma_0(\sX)$ defined by $G^\ast(y) \eqdef \sup_{x \in \sX} \left\{ \ps{y,x} - G(x) \right\}.$
Several properties relate $G$ to its Fenchel transform $G^\ast$. First, the Fenchel transform of $G^\ast$ is $G$. Then, the subdifferential $\partial G^\ast$ is characterized by the relation $x \in \partial G^\ast(y) \Leftrightarrow y \in \partial G(x).$ Finally, $G^\ast$ is $\lambda$-strongly convex if and only if $G$ is $1/\lambda$-smooth.

\subsubsection{Maximal monotone operators}
A set valued function $A : \sX \rightrightarrows \sX$ is {\em monotone} if $\ps{y-y',x-x'} \geq 0$ whenever $y \in A(x)$ and $y' \in A(x')$. The {\em inverse} of $A$, denoted $A^{-1}$, is defined by the relation $x \in A^{-1}(y) \Leftrightarrow y \in A(x)$, and the {\em set of zeros} of $A$ is $Z(A) \eqdef A^{-1}(0)$. If $A$ is monotone, $A$ is {\em maximal} if its {\em resolvent}, \textit{i.e.}, the map $J_{A} : x \mapsto (I+A)^{-1}(x)$, is  single valued. If $G \in \Gamma_0(\sX)$, then $\partial G$ is a maximal monotone operator and $J_{\partial G } = \prox_{G}$. Moreover, $Z(\partial G) = \argmin G$ and $(\partial G)^{-1} = \partial G^\ast$. If $S$ is a skew symmetric matrix on $\sX$, the operator $x \mapsto S x$ is maximal monotone. Finally, the sum $\partial G + S$ is also a maximal monotone operator. Many problems in optimization can be cast as the problem of finding a zero $x$ of the sum of two maximal monotone operators $0 \in (A+B)(x)$ \cite{condatreview}. For instance, $Z(\nabla F + \partial G) = \argmin F+G$. To solve this problem, the Forward Backward algorithm is given by the iteration $x^{k+1} = J_{P^{-1}A}(x^k - P^{-1}B(x^k))$, where $P$ is a symmetric positive definite matrix ($P \in \bR^{d \times d}_{++}$),\footnote{The operators $P^{-1}A$ and $P^{-1}B$ are not monotone in general, however they are monotone under the inner product induced by $P$.} and $B$ is single valued. Using the definition of the resolvent, the Forward Backward algorithm can equivalently be written as
\begin{equation}
    P(x^{k+1/2} - x^k) = -\gamma B(x^k), \quad P(x^{k+1} - x^{k+1/2}) \in -\gamma A(x^{k+1}).
\end{equation}

\subsection{Optimal transport}
In this section, we recall some facts from optimal transport theory. These facts will be used in the proofs without mention. For more details, the reader is referred to Ambrosio et al~\cite{ambrosio2008gradient}.
\subsubsection{Wasserstein distance}
By $\mcB(\sX)$ we denote the $\sigma$-field of Lesbesgue measurable subsets of $\sX$, and by $\cP_2(\sX)$ the set of probability measures $\mu$ over $(\sX,\mcB(\sX))$ with finite second moment $\int \|x\|^2 d\mu(x) < \infty$. Denote $\supp(\mu)$ the support of $\mu$. The identity map $I$ belongs to the Hilbert space $L^2(\mu;\sX)$ of $\mu$-square integrable random vectors in $\sX$. We denote $\ps{\cdot,\cdot}_\mu$ (resp.\ $\|\cdot\|_{\mu}$) the inner product (resp.\ the norm) in this space.
Given $T : \sX \to \sZ$, where $\sZ$ is some Euclidean space, the {\em pushforward measure} of $\mu$ by $T$, also called the {\em image measure}, is defined by $T \# \mu (A) \eqdef \mu(T^{-1}(A))$ for every $A \in \mcB(\sZ)$. Consider $\mu,\nu \in \cP_2(\sX)$. A {\em coupling} $\upsilon$ between $\mu$ and $\nu$ (we shall write $\upsilon \in \Gamma(\mu,\nu)$) is a probability measure over $(\sX^2,\mcB(\sX^2))$ such that $x^\star \# \upsilon = \mu$, where $x^\star : (x,y) \mapsto x$, and $y^\star \# \upsilon = \nu$, where $y^\star : (x,y) \mapsto y$. In other words, $(X,Y)$ is a random variable such that the distribution of $X$ is $\mu$ (we shall write $X \sim \mu$) and $Y \sim \nu$ if and only if the distribution of $(X,Y)$ is a coupling. The (2-){\em Wasserstein distance} is then defined by
\begin{equation}
\label{eq:wass}
    W^2(\mu,\nu) \eqdef \inf_{\upsilon \in \Gamma(\mu,\nu)} \int \|x-y\|^2 d\upsilon(x,y).
\end{equation}
Let $\cP_2^r(\sX)$ be the set of elements $\mu \in \cP_2(\sX)$ such that $\mu$ is absolutely continuous w.r.t.\ $\Leb$ (we shall write $\mu \ll \Leb$). Brenier's theorem asserts that if $\mu \in \cP_2^r(\sX)$, then the $\inf$ defining $W^2(\mu,\nu)$ is actually a $\min$ achieved by a unique minimizer $\upsilon$. Moreover, there exists a uniquely determined $\mu$-almost everywhere (a.e.) map $T_{\mu}^{\nu} : \sX \to \sX$ such that $\upsilon = (I,T_{\mu}^{\nu}) \# \mu$, where $(I,T_{\mu}^{\nu}) : x \mapsto (x,T_{\mu}^{\nu}(x))$. In this case, $T_{\mu}^{\nu}$ is called the {\em optimal pushforward} from $\mu$ to $\nu$ and satisfies
\begin{equation}
    W^2(\mu,\nu) = \int \|x-T_{\mu}^{\nu}(x)\|^2 d\mu(x).
\end{equation}

\subsubsection{Geodesically convex functionals}

We shall consider several functionals defined on the space $\cP_2(\sX)$. For every $\mu \in \cP_2^r(\sX)$ with density denoted $\mu(x)$ w.r.t.\ $\Leb$, the {\em entropy} is defined by
\begin{equation}
\label{eq:entropy}
    \cH(\mu) \eqdef \int \log(\mu(x)) d\mu(x),
\end{equation}
and if $\mu \notin \cP_2^r(\sX)$, then $\cH(\mu) \eqdef +\infty$.
Given $V \in \Gamma_0(\sX)$, the {\em potential energy} is defined for every $\mu \in \cP_2(\sX)$ by
\begin{equation}
\label{eq:potential}
    \cE_V(\mu) \eqdef \int V(x)d\mu(x).
\end{equation}

Finally, if $\mu' \in \cP_2(\sX)$ such that $\mu \ll \mu'$, the {\em Kullback-Leibler (KL) divergence} is defined by
\begin{equation}
\label{eq:kl}
    \KL(\mu|\mu') \eqdef \int \log\left(\tfrac{d\mu}{d\mu'}(x)\right) d\mu(x),
\end{equation}
where $\frac{d\mu}{d\mu'}$ denotes the density of $\mu$ w.r.t.\ $\mu'$, and $\KL(\mu|\mu') \eqdef +\infty$ if $\mu$ is not absolutely continuous w.r.t.\ $\mu'$.
The functionals $\cH$, $\cE_V$ and $\KL(\cdot|\mu^\star)$ satisfy a form of convexity over $\cP_2(\sX)$ called {\em geodesic convexity}. If $\cF : \cP_2(\sX) \to (-\infty,+\infty]$ is geodesically convex, then for every $\mu \in \cP_2^r(\sX)$, $\mu'\in\cP_2(\sX)$, and $\alpha \in [0,1]$, $\cF\left((\alpha T_{\mu}^{\mu'} + (1-\alpha) I)\#\mu\right) \leq \alpha \cF(\mu') +(1-\alpha)\cF(\mu).$
Given $\mu \in \cP_2^r(\sX)$, a {\em (Wasserstein) subgradient} of $\cF$ at $\mu$ is a random variable $Y \in L^2(\mu;\sX)$ such that for every $\mu' \in \cP_2(\sX)$,
\begin{equation}
    \label{eq:subdiff}
    \cF(\mu) + \ps{Y,T_{\mu}^{\mu'} - I}_{\mu} \leq \cF(\mu').
\end{equation}
Moreover, if $Y'$ is a subgradient of $\cF$ at $\mu'$, then the following monotonicity property holds
\begin{equation}
    \label{eq:wass-monot}
    \ps{Y'\circ T_{\mu}^{\mu'} - Y,T_{\mu}^{\mu'} - I}_{\mu} \geq 0.
\end{equation}
If the set $\partialb \cF(\mu) \subset L^2(\mu;\sX)$ of subgradients of $\cF$ at $\mu$ is not empty, then there exists a unique element of $\partialb \cF(\mu)$ with minimal norm. This particular subgradient is denoted $\partialb^0 \cF(\mu)$. However, the set $\partialb \cF(\mu)$ might be empty. A typical condition for nonemptiness requires the density $\mu(x)$ to have some Sobolev regularity. For every open set $\Omega \subset \sX$, we denote $S^{1,1}(\Omega)$ the Sobolev space of $\Leb$-integrable functions $u : \Omega \to \bR$ admitting a $\Leb$-integrable weak gradient $\nabla u : \Omega \to \sX$. We say that $u \in S_{\text{loc}}^{1,1}(\Omega)$ if $u \in S^{1,1}(K)$ for every bounded open set $K \subset \Omega$. Obviously, $S^{1,1}(\Omega) \subset S_{\text{loc}}^{1,1}(\Omega)$.

\subsection{Assumptions on $F$ and $G$}
Consider $F : \sX \to \bR$ and $G : \sX \to (-\infty,+\infty]$. We make the following assumptions.
\begin{assumption}
\label{as:smooth}
The function $F$ is convex and $L$-smooth. Moreover, $G \in \Gamma_0(\sX)$.
\end{assumption}
Note that $V \eqdef F+G \in \Gamma_0(\sX)$. We denote $\lambda_F$ (resp.\ $\lambda_{G^\ast}$) the strong convexity parameter of $F$ (resp.\ $G^\ast$), equal to zero if $F$ (resp.\ $G^\ast$) is not strongly convex.
\begin{assumption}
\label{as:int}
The integral $\int \exp(-V)d\Leb$ is positive and finite.
\end{assumption}
Assumption~\ref{as:int} is needed to define the target distribution $\mu^\star \propto \exp(-V)$, and implies that $\interior(D) \neq \emptyset$, where $D \eqdef \dom(V)$.

\begin{lemma}
\label{lem:Vint}
If Assumptions~\ref{as:smooth} and~\ref{as:int} hold, then
$$\int |V(x)|\exp(-V(x))dx < \infty,\quad \text{and} \quad \int \|x\|^2\exp(-V(x))dx < \infty.$$
\end{lemma}
Lemma~\ref{lem:Vint} implies that $\mu^\star \in \cP_2(\sX)$ and using Assumption~\ref{as:smooth}, $\|\nabla F\| \in L^2(\mu^\star;\bR)$. Since $G \in \Gamma_0(\sX)$, $G$ is differentiable $\Leb$-a.e.\ (almost everywhere) on $\interior(D)$, see~\cite[Theorem 25.5]{rockafellar1970convex}.
\begin{assumption}
\label{as:intgrad}
 The integral $\int_{\interior(D)} \|\nabla G\|^2\exp(-V)d\Leb$ is finite.
\end{assumption}
Assumption~\ref{as:intgrad} is equivalent to requiring $\|\nabla G\| \in L^2(\mu^\star; \bR)$, see below.
Moreover, we assume the following regularity property for the function $\exp(-V)$.
\begin{assumption}
\label{as:sobolev}
The function $\exp(-V)$ belongs to the space $S_{\text{loc}}^{1,1}(\sX)$.
\end{assumption}
Assumption~\ref{as:sobolev} is a necessary condition for $\partialb \cH(\mu^\star) \neq \emptyset$, see below. This assumption precludes $\mu^\star$ from being a uniform distribution. However, Assumption~\ref{as:sobolev} is quite general, \textit{e.g.}, $\exp(-V)$ need not be continuous or positive (see the numerical experiment section). Finally, we assume that the stochastic gradients of $F$ have a bounded variance. Consider an abstract measurable space $(\Xi,\mcG)$, and a random variable $\xi$ with values in $(\Xi,\mcG)$.
\begin{assumption}
\label{as:bound-var}
For every $x \in \sX$, $f(x,\xi)$ is integrable and $F(x) = \bE_\xi(f(x,\xi))$. Moreover, there exists $\sigma_F \geq 0$ such that for every $x \in \sX$, $\bV_\xi(\|\nabla f(x,\xi)\|) \leq \sigma_F^2$, where $\bV$ denotes the variance.
\end{assumption}
The last assumption implies that the stochastic gradients are unbiased: $\bE_\xi(\nabla f(x,\xi)) = \nabla F(x)$ for every $x \in \sX$.

\section{Primal dual optimality in Wasserstein space}
\label{sec:pd-opt}
Let $\cF : \cP_2(\sX) \to (-\infty,+\infty]$ be defined by
\begin{equation}
\label{eq:def-cF}
\cF(\mu) \eqdef \cH(\mu) + \cE_V(\mu) = \cH(\mu) + \cE_F(\mu) + \cE_G(\mu).
\end{equation}
Using Lemma~\ref{lem:Vint}, $\cH(\mu^\star)$ and $\cE_V(\mu^\star)$ are finite real numbers. Moreover, using~\cite[Lemma 1.b]{durmus2018analysis}, for every $\mu \in \cP_2(\sX)$ such that $\cE_V(\mu) < \infty$, we have the identity
\begin{equation}
\label{eq:KL-F}
    \cF(\mu) - \cF(\mu^\star) = \KL(\mu|\mu^\star).
\end{equation}
Equation~\eqref{eq:KL-F} says that $\mu^\star$ is the unique minimizer of $\cF$: $\mu^\star = \argmin \cF.$
\subsection{Subdifferential calculus}
The following result is a consequence of~\cite[Theorem 10.4.13]{ambrosio2008gradient}.

\begin{theorem}
\label{th:subdiff}
Let $\mu \propto \rho$ be an element of $\dom(\cF)$. Then, $\supp(\mu) \subset \overline{D}$ and $\mu(\overline{D}\setminus \interior(D)) = 0$. Moreover, $\partialb \cF(\mu) \neq \emptyset$ if and only if $\rho \in S_{\text{loc}}^{1,1}(\interior(D))$ and there exists $w \in L^2(\mu)$ such that
\begin{equation}
    w(x) \rho(x) = \nabla \rho(x) + \rho(x) \nabla V(x),
\end{equation}
for $\mu$-a.e.\ $x$. In this case, $w = \partialb^0 \cF(\mu)$.
\end{theorem}
If Assumptions~\ref{as:smooth} and~\ref{as:int} hold, then $\cF(\mu^\star) < \infty$ using Lemma~\ref{lem:Vint}. Then, Theorem~\ref{th:subdiff} implies that $\mu^\star(\interior(D)) = 1$. Therefore, using~\cite[Theorem 25.5]{rockafellar1970convex}, $G$ and $V$ are $\mu^\star$-a.s.\ differentiable.

Moreover, applying Theorem~\ref{th:subdiff} with $V \equiv 0$, we can replace $\cF$ by $\cH$ and $D$ by $\sX$. We obtain that $\partialb \cH(\mu) \neq \emptyset$ if and only if $\rho \in S_{\text{loc}}^{1,1}(\sX)$ and $w \rho = \nabla \rho$ for some $w \in L^2(\mu;\sX)$. Now, we set $\mu = \mu^\star$ and $\rho = \exp(-V)$. Using Assumption~\ref{as:sobolev} and $w = -\nabla V$, we obtain that $\partialb^0 \cH(\mu^\star) = -\nabla V$ $\mu^\star$-a.e. Therefore, using that $\nabla G$ is well defined $\mu^\star$-a.e., $\mu^\star$ satisfies
\begin{equation}
\label{eq:FOC}
    0 = \nabla F(x) + \partialb^0 \cH(\mu^\star)(x) + \nabla G(x), \text{ for } \mu^\star-\text{a.e. } x.
\end{equation}
Equation~\eqref{eq:FOC} can be seen as the first order optimality conditions associated with the minimization of the functional $\cF$. Consider the "dual" variable $Y^\star : x \mapsto \nabla G(x)$ defined $\mu^\star$ a.e. Using Assumption~\ref{as:intgrad} and $\mu^\star(\interior(D)) = 1$, $Y^\star \in L^2(\mu^\star;\sX)$. We can express the first order optimality condition~\eqref{eq:FOC} as $0 = \nabla F(x) + \partialb^0 \cH(\mu^\star)(x) + Y^\star(x)$, $\mu^\star$ a.e. Besides, $Y^\star(x) \in \partial G(x)$, therefore $0 \in - x + \partial G^\ast(Y^\star(x))$ using $\partial G^\ast = (\partial G)^{-1}.$ Denote $\nu^\star \eqdef Y^\star \# \mu^\star \in \cP_2(\sX)$ and $\pi^\star \eqdef (I,Y^\star) \# \mu^\star \in \cP_2(\sX^2)$. The relationship between $\mu^\star$ and $Y^\star$ can be summarized as

\begin{equation}
\label{eq:saddleW2}
\begin{bmatrix} 0 \\ 0\end{bmatrix} \in \begin{bmatrix} \nabla F(x) + \partialb^0 \cH(\mu^\star)(x) & + y \\ - x& + \partial G^\ast(y)\end{bmatrix} \text{ for } \pi^\star \text{ a.e. } (x,y).
\end{equation}

In the sequel, we fix the probability space $(\Omega,\mcF,\bP) = (\sX^2,\cB(\sX^2),\pi^\star)$, denote $\bE$ the mathematical expectation and $L^2$ the space $L^2(\Omega,\mcF,\bP;\sX)$. The expression "almost surely" (a.s.) will be understood w.r.t.\ $\bP$. Recall that $x^\star$ is the map $(x,y) \mapsto x$ and $y^\star : (x,y) \mapsto y$. Using Assumption~\ref{as:intgrad}, $x^\star, y^\star \in L^2$, $x^\star \sim \mu^\star$, $y^\star \sim \nu^\star$, $(x^\star,y^\star) \sim \pi^\star$ and $y^\star = \nabla G(x^\star)$ a.s.

\subsection{Lagrangian function and duality gap}

We introduce the following Lagrangian function defined for every $\mu \in \cP_2(\sX)$ and $y \in L^2$ by
\begin{equation}
    \label{eq:LagrangianW}
    \Lag(\mu,y) \eqdef \cE_F(\mu) + \cH(\mu) - \cE_{G^\ast}(\nu) + \bE \ps{x, y},
\end{equation}
where $x = T_{\mu^\star}^\mu(x^\star)$. This Lagrangian is similar to the one used in Euclidean optimization; see the appendix. We also define the duality gap by
\begin{equation}
    \label{eq:dualitygap}
    \DG(\mu,y) \eqdef \Lag(\mu,y^\star) - \Lag(\mu^\star,y).
\end{equation}
The next theorem, which is of independent interest, can be interpreted as a strong duality result for the Lagrangian function $\Lag$, see~\cite[Lemma 36.2]{rockafellar1970convex}.
\begin{theorem}[Strong duality]
\label{lem:DGbregman}
Let Assumptions~\ref{as:smooth}--\ref{as:sobolev} hold true. Then, for every $\mu \in \cP_2(\sX), y \in L^2$, $\DG(\mu,y) \geq 0$ and $\Lag(\mu,y) \leq \cF(\mu)$. Moreover, $(\mu^\star,y^\star)$ is a saddle point of $\Lag$ with saddle value $\cF(\mu^\star)$, \textit{i.e.},
\begin{equation}
\label{eq:minmax}
\Lag(\mu^\star, y) \leq \cF(\mu^\star) = \Lag(\mu^\star,y^\star) \leq \Lag(\mu,y^\star).
\end{equation}
Finally, $\Lag(\mu^\star, y) = \cF(\mu^\star)$ if and only if $y = y^\star$, and, if $F$ is strictly convex, $\cF(\mu^\star) = \Lag(\mu,y^\star)$ if and only if $\mu = \mu^\star$.

\end{theorem}
The proof of Theorem~\ref{lem:DGbregman} relies on using~\eqref{eq:saddleW2} to write the duality gap as the sum of the Bregman divergences of $F$, $G^\ast$ and $\cH$. We shall use the nonnegativity of the duality gap to derive convergence bounds for PSGLA.

\section{Forward Backward representation of PSGLA}
\label{sec:alg}
In this section, we present our viewpoint on PSGLA~\eqref{eq:psgla}. More precisely, we represent PSGLA as a (stochastic) Forward Backward algorithm involving (stochastic) monotone operators which are not necessarily subdifferentials.

\paragraph{Intuition.} Let $\pi \in \cP_2(\sX^2)$ and consider $A, B(\pi) \in L^2(\pi;\sX^2)$ the set valued maps
\begin{equation}
A : (x,y) \mapsto \begin{bmatrix} &   y \\ - x& +\partial G^\ast(y)\end{bmatrix}, \quad B(\pi) : (x,y) \mapsto \begin{bmatrix} \nabla F(x) + \partialb \cH(\mu)(x)\\ 0\end{bmatrix},
\end{equation}
where $\mu = x^\star \# \pi$. The maps $\pi \mapsto A$ and $\pi \mapsto B(\pi)$ satisfy a monotonicity property similar to~\eqref{eq:wass-monot} (note that $A$ is a maximal monotone operator as the sum of $S : (x,y) \mapsto (y,-x)$ and the subdifferential of the $\Gamma_0(\sX^2)$ function $(x,y) \mapsto G^\ast(y)$). Inclusion~\eqref{eq:saddleW2} can be rewritten as
\begin{equation}
\label{eq:zero-op-monot}
    0 \in \left(A+B(\pi^\star)\right)(x,y), \text{ for } \pi^\star \text{ a.e. } (x,y).
\end{equation}
\paragraph{Rigorous Forward Backward representation.} The ``monotone'' inclusion~\eqref{eq:zero-op-monot} intuitively suggests the following stochastic Forward Backward algorithm for obtaining samples from $\pi^\star$ (and hence from $\mu^\star$ by marginalizing):
\begin{align}
    P\begin{bmatrix} x^{k+1/2} - x^{k}\\ y^{k+1/2} - y^{k}\end{bmatrix} &= -\gamma \begin{bmatrix} \nabla f(x^k,\xi^{k+1}) - \sqrt{\frac{2}{\gamma}}W^{k+1}\\ 0 \end{bmatrix} \label{eq:forward}\\
    P\begin{bmatrix} x^{k+1} - x^{k+1/2}\\ y^{k+1} - y^{k+1/2}\end{bmatrix} &\in
    -\gamma A(x^{k+1},y^{k+1})\label{eq:backward}.
\end{align}
Above,  $P \in \bR^{d \times d}_{++}$ is an appropriately chosen matrix. Indeed, Algorithm~\eqref{eq:forward}-\eqref{eq:backward} looks like a stochastic Forward-Backward algorithm~\cite{rosasco2016stochastic,com-pes-pafa16,bia-hac-16,bia-hac-sal-jca17} where the gradient is perturbed by a Gaussian vector, as in the Langevin algorithm~\eqref{eq:Langevin-vanilla}. In Algorithm~\eqref{eq:forward}-\eqref{eq:backward}, we cannot set $P$ to be the identity map of $\sX^2$ because the inclusion~\eqref{eq:backward} is intractable in this case.
We take $P : (x,y) \mapsto x$, \textit{i.e.}, with our notations, $P = x^\star$. Although the matrix $P$ is only semi-definite positive, the next lemma shows that Algorithm~\eqref{eq:forward}-\eqref{eq:backward} is still well defined. More precisely, the next lemma shows that $x^{k+1} = \prox_{\gamma G}(x^{k+1/2})$ (by taking $z = (x^{k+1/2},y^{k+1/2})$ in the lemma) and hence the resulting algorithm~\eqref{eq:forward}-\eqref{eq:backward} is PSGLA. Based on the representation~\eqref{eq:forward}-\eqref{eq:backward} of PSGLA, the next lemma also provides an important inequality used later in the proof of Theorem~\ref{th:evi}.

\begin{lemma}
\label{lem:resolvent-LV}
Let $z = (x,y), z'=(x',y') \in \sX^2$. Then $P(z' - z) \in
    -\gamma A(z')$ if and only if $x' = \prox_{\gamma G}(x)$ and $y' = \prox_{G^\ast/\gamma}(x/\gamma)$.
Moreover, if $G \in \Gamma_0(\sX)$ is $1/\lambda_{G^\ast}$-smooth, then
\begin{align}
\label{eq:funda-lv}
   \|x' - x^\star\|^2 \leq& \|x - x^\star\|^2 -2\gamma\left(G^\ast(y') - G^\ast(y^\star) - \ps{y',x^\star}+ \ps{y^\star,x}\right)\nonumber\\ &-\gamma(\lambda_{G^\ast} + \gamma)\|y'-y^\star\|^2 + \gamma^2\|y^\star\|^2.
\end{align}
\end{lemma}

\section{Main results}
\label{sec:res}

We now provide our main result on PSGLA~\eqref{eq:psgla}. For $r \in \bN/2$, denote $\mu^r$ (resp. $\nu^r$) the distribution of $x^r$ (resp. $y^r$), defined in the previous section.

\begin{theorem}
\label{th:evi}
Let Assumptions~\ref{as:smooth},~\ref{as:int}, \ref{as:intgrad} and~\ref{as:bound-var} hold true. If $F$ is $\lambda_F$-strongly convex and $G$ is $1/\lambda_{G^\ast}$-smooth, then for every $\gamma \leq 1/L$,
\begin{align}
\label{eq:th}
    W^2(\mu^{k+1},\mu^\star)
    \leq& (1-\gamma\lambda_F)W^2(\mu^{k},\mu^\star)  -\gamma(\lambda_{G^\ast} + \gamma) W^2(\nu^{k+1},\nu^\star) \nonumber\\
    &-2\gamma \left(\Lag(\mu^{k+1/2},y^\star) - \Lag(\mu^\star,y_\star^{k+1})\right) + \gamma^2 C,
\end{align}
where $C \eqdef \int_{\interior(D)} \|\nabla G(x)\|^2 d\mu^{\star}(x) + 2 (L d+\sigma_F^2)$ and
$
y_{\star}^{k+1} \eqdef \prox_{G^\ast/\gamma}(x^{k+1/2}_{\star}/\gamma) \sim \nu^{k+1},
$ where $x^{k+1/2}_{\star} \eqdef T_{\mu^\star}^{\mu^{k+1/2}}(x^\star)$.
\end{theorem}
The proof of Theorem~\ref{th:evi} relies on using Lemma~\ref{lem:resolvent-LV} along with~\cite[Lemma 30]{durmus2018analysis}. Inspecting the proof of Theorem~\ref{th:evi}, one can see that any $\bar{\mu},\bar{y}$ can replace $\mu^\star,y^\star$\footnote{The proof does not rely on specific properties of the latter like being primal dual optimal.}. The situation is similar to primal dual algorithms in optimization~\cite{chambolle2016ergodic,drori2015simple} and Evolution Variational Inequalities in optimal transport~\cite{ambrosio2008gradient}.

The next corollary is obtained by using $\DG(\mu^{k+1/2},y_\star^{k+1}) \geq 0$ (Theorem~\ref{lem:DGbregman}) and iterating~\eqref{eq:th}.

\begin{corollary}
\label{cor:rate}
Let Assumptions~\ref{as:smooth}--\ref{as:bound-var} hold true. If $\gamma \leq 1/L$, then
\begin{equation}
\label{eq:rateDG}
    \min_{j \in \{0,\ldots,k-1\}} \DG(\mu^{j+1/2},y_\star^{j+1}) \leq \tfrac{1}{2\gamma k}W^2(\mu^{0},\mu^\star) + \tfrac{\gamma}{2} C,
\end{equation}
\begin{equation}
\label{eq:ratedual}
    \min_{j \in \{1,\ldots,k\}} W^2(\nu^{j},\nu^\star)
    \leq \tfrac{1}{\gamma(\lambda_{G^\ast} + \gamma) k} W^2(\mu^{0},\mu^\star) + \tfrac{\gamma}{\lambda_{G^\ast} + \gamma} C.
\end{equation}
Finally, if $\lambda_F >0$, then
\begin{equation}
\label{eq:ratescvx}
    W^2(\mu^{k},\mu^\star) \leq (1-\gamma \lambda_F)^k W^2(\mu^{0},\mu^\star) + \tfrac{\gamma}{\lambda_F} C.
\end{equation}

\end{corollary}
If $G$ is Lipschitz continuous (in particular if $G \equiv 0$), then our Assumptions hold true. Moreover, inequality~\eqref{eq:rateDG} recovers~\cite[Corollary 18]{durmus2018analysis} but with the duality gap instead of the KL divergence. Obtaining a result in terms of KL divergence is hopeless for PSGLA in general because the KL divergence is infinite; see the appendix. Connecting the convergence of the duality gap to zero to known modes of convergence is left for future work. Besides, obtaining an inequality like~\eqref{eq:ratedual} that holds when $F$ is just convex is rather not standard in the literature on Langevin algorithm, see~\cite{rolland2020double,zou2018stochastic}. Corollary~\ref{cor:rate} implies the following complexity results. Given $\varepsilon >0$, choosing $\gamma = \min(1/L,\varepsilon/C)$ and $k \geq \max(L/\varepsilon,C/\varepsilon^2)W^2(\mu^0,\mu^\star)$ in inequality~\eqref{eq:rateDG} leads to $\min_{j \in \{0,\ldots,k-1\}} \DG(\mu^{j+1/2},y_\star^{j+1}) \leq \varepsilon$. If $\lambda_{G^\ast} >0 $ (\textit{i.e.}, if $G$ is smooth), choosing $\gamma = \min(1/L,\frac{\lambda_{G^\ast}\varepsilon}{2C})$ and $k \geq \max(\frac{2L}{\lambda_{G^\ast}\varepsilon},\frac{4C}{\lambda_{G^\ast}^2\varepsilon^2})W^2(\mu^0,\mu^\star)$ in inequality~\eqref{eq:ratedual} leads to $\min_{j \in \{1,\ldots,k\}} W^2(\nu^{j},\nu^\star) \leq \varepsilon$. Finally, if $\lambda_{F} >0 $ (\textit{i.e.}, if $F$ is strongly convex), choosing $\gamma = \min(1/L,\frac{\lambda_{F}\varepsilon}{2C})$ and $k \geq \frac{1}{\gamma \lambda_F} \log(2 W^2(\mu^0,\mu^\star)/\varepsilon)$ \textit{i.e.},
\begin{equation}
\label{eq:k}
    k \geq \max\left(\tfrac{L}{\lambda_F},\tfrac{2 C}{\lambda_F^2 \varepsilon}\right)\log\left(\tfrac{2 W^2(\mu^0,\mu^\star)}{\varepsilon}\right), \quad C = \int_{\interior(D)} \|\nabla G(x)\|^2 d\mu^{\star}(x) + 2 (L d+\sigma_F^2)
\end{equation}
in inequality~\eqref{eq:ratescvx}, leads to $W^2(\mu^{k},\mu^\star) \leq \varepsilon$. \footnote{The dependence in $d$ of the factor $W^2(\mu^0,\mu^\star)$ can be explicited under further assumptions, see~\cite{rolland2020double,durmus2018analysis}.} In the case where $G$ is $M$-Lipschitz continuous, the complexity~\eqref{eq:k} improves~\cite[Corollary 22]{durmus2018analysis} since $\int_{\interior(D)} \|\nabla G(x)\|^2 d\mu^{\star}(x) \leq M^2$ .
\section{Conclusion}
We made a step towards theoretical understanding the properties of the Langevin algorithm in the case where the target distribution is not smooth and not fully supported. This case is known to be difficult to analyze and has many applications~\cite{brosse2017sampling,durmus2018efficient,bubeck2018sampling}. Our analysis improves and extends the state of the art.

Moreover, our approach is new. We developed a primal dual theory for a minimization problem over the Wasserstein space, which is of independent interest. A broader duality theory for minimization problems in the Wasserstein space would be of practical and theoretical interest.

\section{Acknowledgement}
We thank Laurent Condat for introducing us to the primal dual view of the proximal gradient algorithm in Hilbert spaces.

\section{Broader impact}
\label{sec:broader}
Our work contributes to the understanding of a sampling algorithm used in statistics. Our main results are of theoretical nature (convergence rates). Therefore, we do not see any immediate societal impact of our results.

\bibliographystyle{plain}
\newcommand{\noop}[1]{} \def\cprime{$'$} \def\cdprime{$''$} \def\cprime{$'$}

config: arxiv