text:
\begin{document}
\title[]{Some remarks on non-symmetric polarization}

\author{Felipe Marceca}

\address{Departamento de Matem\'{a}tica - Pab I,
	Facultad de Cs. Exactas y Naturales, Universidad de Buenos Aires,
	(1428) Buenos Aires, Argentina, and CONICET-IMAS}
\thanks{This work has been supported by CONICET-PIP 11220130100329CO, ANPCyT PICT 2015-2299, UBACyT 20020130100474BA and a CONICET doctoral fellowship.}

\begin{abstract}
Let $P:\mathbb{C}^n\rightarrow \mathbb{C}$ be an $m$-homogeneous polynomial given by
\[P(x)= \sum_{1\leq j_1\leq \ldots \leq j_m \leq n} c_{j_1 \ldots j_m} x_{j_1}\ldots x_{j_m}.\]
Defant and Schl\"uters defined a non-symmetric associated $m$-form $L_P: \left(\mathbb{C}^n \right)^m\rightarrow \mathbb{C}$ by
\[L_P \left(x^{(1)},\ldots,x^{(m)} \right)= \sum_{1\leq j_1\leq \ldots \leq j_m \leq n}  c_{j_1  \ldots j_m} x_{j_1}^{(1)}\ldots x_{j_m}^{(m)}.\]
They estimated the norm of $L_P$ on $(\mathbb{C}^n, \| \cdot\|)^m$ by  the  norm  of $P$ on $(\mathbb{C}^n, \| \cdot\|)$
times a $(c\log n)^{m^2}$ factor for every 1-unconditional norm $\|\cdot\|$ on $\mathbb{C}^n$.
A symmetrization procedure based on a card-shuffling algorithm which (together with Defant and Schl\"uters' argument)
brings the constant term down to $(c m \log n)^{m-1}$ is provided.
Regarding the lower bound, it is shown that the optimal constant is bigger than $(c \log n)^{m/2}$ when $n\gg m$.
Finally, the case of $\ell_p$-norms $\|\cdot \|_p$ with $1\leq p <2$ is addressed.
\end{abstract}

\maketitle

\thispagestyle{empty}

\section{Introduction}

Let $P:\mathbb{C}^n\rightarrow \mathbb{C}$ be an $m$-homogeneous polynomial.
It is well-known that there is a unique symmetric $m$-linear form $B:(\mathbb{C}^n)^m\rightarrow \mathbb{C}$, such that $B(x,\ldots,x)=P(x)$ for all $x\in \C$.
Moreover, the \textit{polarization formula} gives an expression for the $m$-linear form $B$ in terms of $P$ (see e.g. \cite[Section 1.1]{din}).
In fact, for every $x^{(1)},\ldots,x^{(m)}\in\C$, we have
\[B\left(x^{(1)},\ldots,x^{(m)}\right)=\frac{1}{2^m m!} \sum_{\varepsilon\in \{-1,1\}^m} P\left(\varepsilon_1 x^{(1)}+ \ldots + \varepsilon_m x^{(m)}\right).\]
It follows from this identity that
\begin{align}
\label{sim}
\sup_{\left\|x^{(k)} \right\|\leq 1} \left| B \left( x^{(1)},\ldots , x^{(m)} \right) \right| \leq e^m \sup_{\|x\|\leq 1} | P ( x ) |,
\end{align}
for any norm $\|\cdot \|$ in $\C^n$.

In \cite{nosim}, {Defant} and {Schl\"uters} defined a non-symmetric $m$-linear form $L_P$ arising from a given $m$-homogeneous polynomial $P$.
More precisely, for an $m$-homogeneous polynomial $P:\C^n\rightarrow \C$ defined by
\[P(x)= \sum_{1\leq j_1\leq \ldots \leq j_m \leq n} c_{j_1 \ldots j_m} x_{j_1}\ldots x_{j_m},\]
its associated $m$-linear form $L_P: \left(\C^n \right)^m\rightarrow \C$ is given by
\[L_P \left(x^{(1)},\ldots,x^{(m)} \right)= \sum_{1\leq j_1\leq \ldots \leq j_m \leq n}  c_{j_1  \ldots j_m} x_{j_1}^{(1)}\ldots x_{j_m}^{(m)}.\]
Assuming unconditionality of the norm $\|\cdot \|$ in $\C^n$, {Defant} and {Schl\"uters} proved that a similar estimate as in \eqref{sim} holds for $L_P$.
Before providing further details we introduce an \textit{ad hoc} definition:

\begin{definition}
 For $m,n \in \N$, we define $C(m,n)$ as the infimum of the constants $C>0$ such that for every $m$-homogeneous polynomial $P:\C^n\rightarrow \C$
 and every 1-unconditional norm $\|\cdot \|$ on $\C^n$ we have
 \[\sup_{\|x^{(k)} \|\leq 1} \left| L_P \left( x^{(1)},\ldots , x^{(m)} \right) \right| \leq C \sup_{\|x\|\leq 1} | P ( x ) |.\]
 Similarly, for $1\leq p<2$, we take $C_p(m,n)$ as the infimum of the constants $C>0$ such that for every $m$-homogeneous polynomial $P:\C^n\rightarrow \C$ we have
 \[\sup_{\|x^{(k)} \|_p\leq 1} \left| L_P \left( x^{(1)},\ldots , x^{(m)} \right) \right| \leq C \sup_{\|x\|_p\leq 1} | P ( x ) |.\]
\end{definition}

The aforementioned result of \cite{nosim} can be stated in terms of the previous definition.

\begin{theorem}[{\cite[Theorem 1.1]{nosim}}]
\label{teonosim}
There exists a universal constant $c_1\geq 1$ such that
\[C(m,n)\leq (c_1 \log n)^{m^2}.\]
Moreover, for $1\leq p<2$, there is a constant $c_2=c_2(p)\geq 1$ for which
\[C_p(m,n) \leq c_2^{m^2}.\]
\end{theorem}

Note that by the uniqueness of the symmetric $m$-linear form $B$ we have
\begin{align}
\label{sim2}
 B \left(x^{(1)},\ldots,x^{(m)} \right)=\frac{1}{m!}\sum_{\sigma\in \Sigma_m} L_P \left(x^{\sigma(1)},\ldots,x^{\sigma(m)} \right),
\end{align}
where $\Sigma_m$ is the group of permutations of $m$ elements.
The proof of Theorem \ref{teonosim} consists of bounding the norm of $L_P$ by successive partial symmetrizations starting at $L_P$
and ending at the fully symmetrized $B$. Finally, applying \eqref{sim} yields the result.
Changing only the way in which this symmetrization is carried out and using the same arguments as in \cite{nosim},
we obtain improved bounds for the constants $C(m,n)$ and $C_p(m,n)$. Additionally, we provide lower bounds for these constants. Our main result is the following.

\begin{theorem}
\label{teo1}
There exists a universal constant $c_1\geq 1$ such that
\[\left(\frac{\log\left(\frac{2n}{m}\right)-\pi}{\pi}\right)^{m/2} \leq C(m,n)\leq c_1^m m^m (\log n)^{m-1}.\]
Moreover, for $1\leq p<2$, there is a constant $c_2=c_2(p)\geq 1$ for which
\[m^{\frac{m}{p}}\leq C_p(m,n) \leq c_2^m m^m.\]
\end{theorem}

\begin{remark}
 {Defant} and {Schl\"uters} achieved similar upper bounds by refining their original calculations from \cite{nosim} as it was mentioned during a personal communication.
\end{remark}

\begin{remark}
\label{rem1}
Scrutiny of the theorem's proof suggests that the underlying reason which determines the magnitude of the constants $C(m,n)$ and $C_p(m,n)$
is the behaviour of the operator known as the main triangle projection.
Roughly speaking, the main triangle projection is the operator which given a matrix in $\C^{n\times n}$ returns the same matrix with zeroes below the diagonal.
Each norm on $\C^n$ induces an operator norm in $\C^{n\times n}$ and again this induces a norm for the main triangle projection.
Estimations of the latter norm are the ones that shape the upper and lower bounds of $C(m,n)$ and $C_p(m,n)$ that were obtained.
\end{remark}

\section{Symmetrization}
The following may be deduced from \eqref{sim2}.
\begin{align*}
 B \left(x^{(1)},\ldots,x^{(m)} \right)&=\frac{1}{m!}\sum_{\sigma\in \Sigma_m} L_P \left(x^{\sigma(1)},\ldots,x^{\sigma(m)} \right)
 \\ &=\frac{1}{m!}\sum_{\sigma\in \Sigma_m} \sum_{1\leq j_1\leq \ldots \leq j_m \leq n}  c_{j_1  \ldots j_m} x_{j_1}^{\sigma(1)}\ldots x_{j_m}^{\sigma(m)}
 \\ &=\frac{1}{m!}\sum_{\sigma\in \Sigma_m} \sum_{1\leq j_1\leq \ldots \leq j_m \leq n}  c_{j_1  \ldots j_m} x_{j_{\sigma^{-1}(1)}}^{(1)}\ldots x_{j_{\sigma^{-1}(m)}}^{(m)}
 \\ &=\frac{1}{m!}\sum_{\tau\in \Sigma_m} \sum_{1\leq j_1\leq \ldots \leq j_m \leq n}  c_{j_1  \ldots j_m} x_{j_{\tau(1)}}^{(1)}\ldots x_{j_{\tau(m)}}^{(m)}.
\end{align*}

From a probabilistic point of view, this may be restated as
\begin{align}
\label{sim3}
B \left(x^{(1)},\ldots,x^{(m)} \right)
=E \left[ \sum_{1\leq j_1\leq \ldots \leq j_m \leq n}  c_{j_1  \ldots j_m} x_{j_{\sigma(1)}}^{(1)}\ldots x_{j_{\sigma(m)}}^{(m)}\right],
\end{align}
where expectation is taken over $\sigma\in \Sigma_m$ and $\Sigma_m$ is endowed with the equiprobability measure.
In other words, $B$ is the expected value of $L_P$ when the order of the monomials' subindices is an equidistributed random variable.
Thus, a card-shuffling procedure applied to the order of the subindices will yield a symmetrization procedure for $L_P$ by taking expectation.
We will use the {Fischer-Yates} shuffle in its original version which can be found in \cite{fiya}. It goes as follows.
Choose a random card from an ordered deck and leave it on top.
Next, choose a random card between the second and the last place and leave it in the second place, and so on.
At the last step, choose between the last two cards which one will go in the penultimate place.
After applying this procedure, an ordered deck will be completely shuffled, that is, any arrangement will be equally probable.

\begin{remark}
 Note that at any given step, the $k$-th step say, the first $k-1$ cards (which have been previously selected) are completely random,
while the last cards remain completely ordered. This special structure will be crucial in the proof of Theorem \ref{teo1}.
\end{remark}

Next, we introduce the symmetrization procedure arising from the {Fischer-Yates} shuffle.
For every $1\leq k \leq m-1$ we let $\mathbb{P}_k$ be the probability distribution on $\Sigma_m$ associated to performing the first $k$ steps of the shuffling algorithm.
We define the $k$-th shuffle $S_k$ of an $m$-form $L: \left(\C^n \right)^m\rightarrow \mathbb{C}$ by
\[S_k L\left(x^{(1)},\ldots,x^{(m)} \right)
  =E \left[ \sum_{i_1,\ldots, i_m=1 }^n  c_{i_1  \ldots i_m} x_{i_{\sigma(1)}}^{(1)}\ldots x_{i_{\sigma(m)}}^{(m)}\right],\]
where $\sigma \sim \mathbb{P}_k.$

In particular, from \eqref{sim3} and the fact that the $(m-1)$-th step of the shuffle achieves equidistribution we have
\[B= S_{m-1} L_P.\] However, it should be noticed that the intermediate shuffles are not partial symmetrizations
since we are symmetrizing the monomials' subindices rather than the variables.

In order to study the structure of $S_k$, we define the $k$-th shuffling step $T_k$ of an $m$-form $L: \left(\mathbb{C}^n \right)^m\rightarrow \mathbb{C}$ by
\begin{multline*}
 T_k L  \left(x^{(1)},\ldots,x^{(m)} \right)
 \\ = \frac{1}{m-k+1} \sum_{l=k}^m L \left(x^{(1)},\ldots,x^{(k-1)},x^{(k+1)},\ldots,x^{(l)},x^{(k)},x^{(l+1)},\ldots,x^{(m)} \right).
\end{multline*}

\begin{lemma}
 For every $1\leq k \leq m-1$ we have  that $S_k= T_k \ldots T_1$.
\end{lemma}
\begin{proof}
 Since $T_k$ and $S_k$ are linear for every $1\leq k \leq m-1$, it is enough to check that the equality holds for monomials.
 Fix $1\leq i_1, \ldots, i_m \leq n$, we have to prove that
 \[S_k \left(x^{(1)}_{i_1} \ldots x^{(m)}_{i_m}\right)= T_k \ldots T_1\left(x^{(1)}_{i_1} \ldots x^{(m)}_{i_m}\right).\]
 We will proceed by induction.
 If $k=1$, the random permutation $\sigma$ is a cycle in $\Sigma_m$.
 More precisely, using the cycle notation in $\Sigma_m$ we have that $\sigma$ takes the value $(l \ l-1 \ \ldots \ 1)$ for some $1\leq l \leq m$ with probability $1/m$.
 Therefore, we get
 \begin{align*}
  S_1\left(x^{(1)}_{i_1} \ldots x^{(m)}_{i_m}\right)&=E \left[ x_{i_{\sigma(1)}}^{(1)}\ldots x_{i_{\sigma(m)}}^{(m)}\right]
  =\frac{1}{m} \sum_{l=1}^m x^{(1)}_{i_{l}} x^{(2)}_{i_{1}} \ldots  x^{(l)}_{i_{l-1}} x^{(l+1)}_{i_{l+1}} \ldots x^{(m)}_{i_{m}}
  \\ &=\frac{1}{m} \sum_{l=1}^m  x^{(2)}_{i_{1}} \ldots  x^{(l)}_{i_{l-1}} x^{(1)}_{i_{l}} x^{(l+1)}_{i_{l+1}} \ldots x^{(m)}_{i_{m}}
  =T_1\left(x^{(1)}_{i_1} \ldots x^{(m)}_{i_m}\right).
 \end{align*}

 Only the inductive step remains to be proven. Let $2\leq k \leq m-1$ and suppose the lemma holds for $k-1$.
 From the definition of the {Fischer-Yates} shuffle we may deduce that a random permutation with law $\mathbb{P}_k$ can be written
 as the composition of two independent random permutations $\tau$ and $\sigma$ where $\sigma \sim \mathbb{P}_{k-1}$
 and $\tau$ takes the value $\tau_l =(l \ l-1 \ \ldots \ k)$ for some $k\leq l \leq m$ with probability $1/{(m-k+1)}$.

For a fixed $\tau$, we may define new indices $j_1,\ldots,j_m$ such that $j_k=i_{\tau(k)}$ for every $1\leq k\leq m$.
So we obtain
\begin{align*}
S_k \left(x^{(1)}_{i_1} \ldots \right.& \left. x^{(m)}_{i_m} \right)
=E_{\tau,\sigma} \left[  x_{i_{\tau\sigma(1)}}^{(1)}\ldots x_{i_{\tau\sigma(m)}}^{(m)}\right]
=E_\tau \left[E_\sigma \left[  x_{j_{\sigma(1)}}^{(1)}\ldots x_{j_{\sigma(m)}}^{(m)}\right]\right]
\\&=E_\tau \left[S_{k-1} \left(x^{(1)}_{j_1} \ldots x^{(m)}_{j_m} \right)\right]
=E_\tau \left[S_{k-1} \left(x_{i_{\tau(1)}}^{(1)}\ldots x_{i_{\tau(m)}}^{(m)} \right)\right]
\\&=\frac{1}{m-k+1} \sum_{l=k}^m S_{k-1} \left(x^{(1)}_{i_{\tau_l(1)}} \ldots x^{(m)}_{i_{\tau_l(m)}} \right)
\\&=\frac{1}{m-k+1} \sum_{l=k}^m S_{k-1}
\left(x^{(1)}_{i_1} \ldots x^{(k-1)}_{i_{k-1}} x^{(k)}_{i_{l}} x^{(k+1)}_{i_{k}} \ldots x^{(l)}_{i_{l-1}} x^{(l+1)}_{i_{l+1}} \ldots x^{(m)}_{i_m} \right)
\\&=\frac{1}{m-k+1} \sum_{l=k}^m S_{k-1}
\left(x^{(1)}_{i_1} \ldots x^{(k-1)}_{i_{k-1}}  x^{(k+1)}_{i_{k}} \ldots x^{(l)}_{i_{l-1}} x^{(k)}_{i_{l}} x^{(l+1)}_{i_{l+1}} \ldots x^{(m)}_{i_m} \right)
\\&=T_k S_{k-1} \left(x^{(1)}_{i_1} \ldots  x^{(m)}_{i_m} \right)
,
\end{align*}
which completes the proof.
\end{proof}

Following \cite{nosim}, we turn to study how the coefficients of the succesive shuffles of $L_P$ change.
Let $L: \left(\C^n \right)^m\rightarrow \mathbb{C}$ be an $m$-linear form given by
\[L \left(x^{(1)},\ldots,x^{(m)} \right)=\sum_{i \in \mathcal{I}(m,n)} c_i x_{i_1}^{(1)} \ldots x_{i_m}^{(m)},\]
where $\mathcal{I}(m,n)=\{1,\ldots , n\}^m$. We will denote its coefficients by $c_i(L)=c_i$.

\begin{lemma}
\label{coef2}
 For $m,n \in \N$, $1 \leq k \leq m-1$, $i\in \mathcal{I}(m,n)$ and an $m$-homogeneous polynomial $P:\mathbb{C}^n\rightarrow \mathbb{C}$ we have
  \[c_i \left(S_{k-1} L_P \right)=\begin{cases}
                  (m-k+1) \left(1+\sum_{u=1}^{m-k} \delta_{i_k,i_{k+u}}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right) c_i \left(S_k L_P \right) \quad &\text{if } i_k\leq i_{k+1}
                  \\ 0 &\text{otherwise}
                 \end{cases}
,\]
where $\delta$ is the {Kronecker} delta and we take $S_0 L_P = L_P$.
\end{lemma}
\begin{proof}
 We begin the proof by calculating the coefficents $c_i\left(S_k L_P \right)$ in terms of the coefficients $c_i \left(S_{k-1} L_P \right)$.
 Observe that for an $m$-linear form $L: \left(\C^n \right)^m\rightarrow \mathbb{C}$ we have
 \begin{align*}
 T_k &L  \left(x^{(1)},\ldots,x^{(m)} \right) \notag
 \\& =\frac{1}{m-k+1} \sum_{l=k}^m L \left(x^{(1)},\ldots,x^{(k-1)},x^{(k+1)},\ldots,x^{(l)},x^{(k)},x^{(l+1)},\ldots,x^{(m)} \right) \notag
 \\& =\frac{1}{m-k+1} \sum_{l=k}^m \sum_{i \in \mathcal{I}(m,n)} c_i(L)
 x_{i_1}^{(1)}\ldots x_{i_{k-1}}^{(k-1)}x_{i_{k}}^{(k+1)} \ldots x_{i_{l-1}}^{(l)} x_{i_{l}}^{(k)} x_{i_{l+1}}^{(l+1)} \ldots x_{i_{m}}^{(m)} \notag
 \\& = \sum_{i \in \mathcal{I}(m,n)} \frac{1}{m-k+1} \sum_{l=k}^m  c_i(L)
 x_{i_1}^{(1)}\ldots x_{i_{k-1}}^{(k-1)} x_{i_{l}}^{(k)} x_{i_{k}}^{(k+1)} \ldots x_{i_{l-1}}^{(l)}  x_{i_{l+1}}^{(l+1)} \ldots x_{i_{m}}^{(m)} \notag
 \\& = \sum_{i \in \mathcal{I}(m,n)} \frac{1}{m-k+1} \sum_{l=k}^m  c_{\left(i_1,\ldots,i_{k-1},i_{k+1}, \ldots, i_{l},i_{k},i_{l+1}, \ldots, i_{m} \right)}(L)
 x_{i_1}^{(1)} \ldots x_{i_{m}}^{(m)}.
 \end{align*}
 Therefore, since $S_k=T_k S_{k-1}$, we deduce the formula
 \begin{align}
   \label{coef1}
   c_i \left(S_k L_P \right)=\frac{1}{m-k+1} \sum_{l=k}^m  c_{\left(i_1,\ldots,i_{k-1},i_{k+1}, \ldots, i_{l},i_{k},i_{l+1}, \ldots, i_{m} \right)} \left(S_{k-1} L_P \right).
 \end{align}

 By the definition of $L_P$ if a coefficient $c_i \left(L_P \right)$ is not zero, then the index $i$ must satisfy that $1\leq i_1 \leq \ldots \leq i_m \leq n$.
 We will prove inductively that for $0 \leq k \leq m-1$, if the coefficient $c_i \left(S_k L_P \right)$ is not zero,
 then the index $i$ must satisfy that $1\leq i_{k+1} \leq \ldots \leq i_m \leq n$.

 Since $S_0 L_P = L_P$, the case $k=0$ is already proven.
 Now assume the assertion holds for $0 \leq k-1 \leq m-1$ and fix $i\in \mathcal{I}(m,n)$ such that $i_s >i_{s+1}$ for some $k+1\leq s \leq m-1$.
 Applying the inductive hypothesis we may deduce that
 \[c_{\left(i_1,\ldots,i_{k-1},i_{k+1}, \ldots, i_{l},i_{k},i_{l+1}, \ldots, i_{m} \right)} \left(S_{k-1} L_P \right)=0,\]
 for every $k\leq l \leq m$.
 Hence, using \eqref{coef1} we get that $c_i \left(S_k L_P \right)=0$ proving the inductive step.
 In particular,  we have shown that $c_i \left(S_{k-1} L_P \right)=0$ if $i_k>i_{k+1}$ as sought.

 Now assume that $i_k\leq i_{k+1}$.
 If for some $k+1\leq s \leq m-1$ we have that $i_s >i_{s+1}$, then by the previous argument we may deduce that $c_i \left(S_{k-1} L_P \right)=c_i \left(S_k L_P \right)=0$ as desired.
 Therefore, it remains to check the statement when $1\leq i_k \leq \ldots \leq i_m \leq n$. Define $s = \sup \{k \leq u \leq m \ : i_u=i_k\}$ and notice that
 \[c_{\left(i_1,\ldots,i_{k-1},i_{k+1}, \ldots, i_{l},i_{k},i_{l+1}, \ldots, i_{m} \right)} \left(S_{k-1} L_P \right)=\begin{cases}
                  c_i \left(S_{k-1} L_P \right) \quad &\text{if } k\leq l\leq s
                  \\ 0 &\text{if } s< l\leq m
                 \end{cases}
 .\]
 Thus, we may push \eqref{coef1} further to get
 \begin{align*}

  c_i \left(S_k L_P \right)&=\frac{1}{m-k+1} \sum_{l=k}^m  c_{\left(i_1,\ldots,i_{k-1},i_{k+1}, \ldots, i_{l},i_{k},i_{l+1}, \ldots, i_{m} \right)} \left(S_{k-1} L_P \right) \notag
  \\ &=\frac{1}{m-k+1} \sum_{l=k}^s  c_i \left(S_{k-1} L_P \right)=\frac{s-k+1}{m-k+1}  c_i \left(S_{k-1} L_P \right).

 \end{align*}
 Since $s\geq k$, we have that $s-k+1\neq 0$. Thus, we get

 \begin{align*}
 \label{coef3}
  c_i \left(S_{k-1} L_P \right)&=\frac{m-k+1}{s-k+1}  c_i \left(S_k L_P \right)
  \\ &=(m-k+1) \left(1+\sum_{u=1}^{s-k} \left(\frac{1}{u+1}-\frac{1}{u}\right)\right) c_i \left(S_k L_P \right)
  \\ &=(m-k+1) \left(1+\sum_{u=1}^{m-k} \delta_{i_k,i_{k+u}}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right) c_i \left(S_k L_P \right).
 \end{align*}
 This concludes the proof.
\end{proof}

As in \cite{nosim}, we will restate the previous lemma using {Schur} products.
For $A,B\in\C^{\mathcal{I}(m,n)}$, the {Schur} product $A*B$ is given by
\[c_i(A*B)=c_i(A)c_i(B),\]
where $c_i(\cdot)$ denotes de $i$-th entry of a matrix.
By identifying an $m$-linear form with its coefficients, we may compute the product between a matrix and an $m$-form.
More precisely, for $A\in\C^{\mathcal{I}(m,n)}$ and an $m$-linear form $L: \left(\mathbb{C}^n \right)^m\rightarrow \mathbb{C}$ we define
$A*L: \left(\mathbb{C}^n \right)^m\rightarrow \mathbb{C}$ by
\[c_i(A*L)=c_i(A)c_i(L).\]
With this notation Lemma \ref{coef2} proves the formula
\begin{align}
 \label{formula1}
 S_{k-1} L_P=R_k*S_k L_P,
\end{align}
where $R_k\in\C^{\mathcal{I}(m,n)}$ is given by
\begin{align*}
 c_i \left(R_k \right)=
 \begin{cases}
  (m-k+1) \left(1+\sum_{u=1}^{m-k} \delta_{i_k,i_{k+u}}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right) \quad &\text{if } i_k\leq i_{k+1}
  \\ 0 &\text{otherwise}
 \end{cases}.
\end{align*}

The matrix $R_k\in\C^{\mathcal{I}(m,n)}$ may be decomposed as sums and products of simpler matrices.
For $u,v\in\{1,\ldots,m\}$, let $D^{u,v},T^{u,v}\in \mathbb{C}^{\mathcal{I}(m,n)}$ be such that for every $i\in \mathcal{I}(m,n)$ we have
  \[ c_i \left(D^{u,v} \right)= \begin{cases}
                  1 \quad &\text{if } i_u= i_v
                  \\ 0 &\text{otherwise}
                 \end{cases},\]
  \[ c_i \left(T^{u,v} \right)= \begin{cases}
                  1 \quad &\text{if } i_u\leq i_v
                  \\ 0 &\text{otherwise}
                 \end{cases}.\]
Keeping Remark \ref{rem1} in mind, we may observe that $T^{u,v}$ bears a close ressemblance with the main triangle projection $T:\C^{n\times n}\rightarrow\C^{n\times n}$.
Indeed, note that $c_i(T^{u,v})=c_{i_u,i_v}(T)$ for every $i\in\mathcal{I}(m,n)$.
\begin{lemma}
 \label{lema1}
 For $1\leq k \leq m-1$, we have
 \[R_k = (m-k+1)T^{k,k+1}*\left(1+\sum_{u=1}^{m-k} D^{k,k+u}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right).\]
\end{lemma}
\begin{proof}
 For $i\in \mathcal{I}(m,n)$, we deduce that
 \begin{align*}
  c_i\left((m-k+1)\vphantom{\left(1+\sum_{u=1}^{m-k} D^{k,k+u}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right)}\right.
     &\left. T^{k,k+1}*\left(1+\sum_{u=1}^{m-k} D^{k,k+u}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right)\right)=
  \\ &=(m-k+1) c_i \left(T^{k,k+1} \right) \left(1+\sum_{u=1}^{m-k} c_i \left(D^{k,k+u} \right)\left(\frac{1}{u+1}-\frac{1}{u}\right)\right)
  \\ &= c_i \left(T^{k,k+1} \right) (m-k+1) \left(1+\sum_{u=1}^{m-k} \delta_{i_k,i_{k+u}}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right)
  \\ &= c_i \left(R_k \right),
 \end{align*}
 which proves the statement.
\end{proof}

\section{Upper bounds}
In this section we provide the upper bounds for Theorem \ref{teo1}.
Let $\|\cdot\|$ be a norm on $\C^n$. For $A\in \C^{\mathcal{I}(m,n)}$, we define $\mu_{\|\cdot\|}(A)$ as the infimum of the constants $C>0$
such that for every $m$-linear form $L: \left(\C^n \right)^m\rightarrow \C$ we have
\[\sup_{\| x^{(k)} \|\leq 1}  \left|A*L \left(x^{(1)},\ldots,x^{(m)} \right) \right|\leq C \sup_{\| x^{(k)} \|\leq 1}  \left|L \left(x^{(1)},\ldots,x^{(m)} \right) \right|.\]
Note that $ \left(\C^{\mathcal{I}(m,n)},\mu_{\|\cdot\|} \right)$ is a {Banach} algebra.

We will use the following lemma by {Defant} and {Schl\"uters}.
\begin{lemma}[{\cite[Lemma 3.2]{nosim}}]
\label{lema2}
  For every $n,m\in\mathbb{N}$, every $u,v\in\{1,\ldots,m\}$ and every 1-unconditional norm $\| \cdot \|$ on $\mathbb{C}^n$
  \begin{align*}
   \mu_{\| \cdot \|} \left(D^{u,v} \right)&=1,
   \\ \mu_{\| \cdot \|} \left(T^{u,v} \right)&\leq \log_2(2n).
  \end{align*}

 Moreover, for every $1\leq p<2$, there exists a constant $c=c(p)$ so that for every $n,m\in\mathbb{N}$
 \[\mu_{\| \cdot \|_p} \left(T^{u,v} \right)\leq c.\]
\end{lemma}
As mentioned in Remark \ref{rem1}, the estimates for $T^{u,v}$ rely on bounds for the norm of the main triangle projection
obtained by Kwapie\'n and Pe{\l}czy\'nski in \cite{kwap} and Bennett in \cite{ben}.

\begin{corollary}
 For every $n,m\in\mathbb{N}$, every $1\leq k \leq m-1$ and every 1-unconditional norm $\| \cdot \|$ on $\mathbb{C}^n$ we have
 \[\mu_{\| \cdot \|} \left(R_k \right)\leq 2(m-k+1)\mu_{\| \cdot \|} \left(T^{k,k+1} \right).\]
\end{corollary}
\begin{proof}
 From the last lemma we know that $\mu_{\| \cdot \|} \left(D^{u,v} \right)=1$ for every $u,v\in\{1,\ldots,m\}$.
 Since $ \left(\C^{\mathcal{I}(m,n)},\mu_{\|\cdot\|} \right)$ is a {Banach} algebra, we may deduce from Lemma \ref{lema1} that
 \begin{align*}
  \mu_{\| \cdot \|} \left(R_k \right)&=\mu_{\| \cdot \|}\left((m-k+1)T^{k,k+1}*\left(1+\sum_{u=1}^{m-k} D^{k,k+u}\left(\frac{1}{u+1}-\frac{1}{u}\right)\right)\right)
  \\ &\leq (m-k+1) \mu_{\| \cdot \|} \left(T^{k,k+1} \right)\left(1+\sum_{u=1}^{m-k} \mu_{\| \cdot \|} \left(D^{k,k+u} \right)\left|\frac{1}{u+1}-\frac{1}{u}\right|\right)
  \\ &\leq (m-k+1) \left(1+\sum_{u=1}^{\infty} \left(\frac{1}{u}-\frac{1}{u+1}\right)\right) \mu_{\| \cdot \|} \left(T^{k,k+1} \right)
  \\ &= 2(m-k+1) \mu_{\| \cdot \|} \left(T^{k,k+1} \right),
 \end{align*}
 as required.
\end{proof}

We are ready to prove the upper bounds for Theorem \ref{teo1}.
\begin{theorem}
 \label{teo2}
There exists a universal constant $c_1\geq 1$ such that
 \[C(m,n)\leq c_1^m m^m (\log n)^{m-1}.\]
Moreover, for $1\leq p<2$, there is a constant $c_2=c_2(p)\geq 1$ for which
 \[C_p(m,n) \leq c_2^m m^m.\]
\end{theorem}
\begin{proof}
 Using \eqref{formula1}, the definition of $\mu_{\| \cdot \|}$ and the previous corollary we get
 \begin{align*}
  \sup_{\| x^{(k)} \|\leq 1}  \left|S_{k-1}L_P \left(x^{(1)}\right.\right. & \left.\left. ,\ldots,x^{(m)} \right) \right| =  \sup_{\| x^{(k)} \|\leq 1}  \left|R_k*S_k L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|
  \\ &\leq \mu_{\| \cdot \|} \left(R_k \right) \sup_{\| x^{(k)} \|\leq 1}  \left|S_k L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|
  \\ &\leq 2(m-k+1) \mu_{\| \cdot \|} \left(T^{k,k+1} \right) \sup_{\| x^{(k)} \|\leq 1}  \left|S_k L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|,
 \end{align*}
 for every $1\leq k \leq m-1$. Taking $\mu=\sup_{1\leq k\leq m-1}\mu_{\| \cdot \|} \left(T^{k,k+1} \right)$ and linking the previous inequalities together, we deduce that
 \begin{align*}
  \sup_{\| x^{(k)} \|\leq 1}  \left|L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right| &\leq 2m\mu \sup_{\| x^{(k)} \|\leq 1}  \left|S_1 L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|
  \\ &\leq 2^2m(m-1)\mu^2 \sup_{\| x^{(k)} \|\leq 1}  \left|S_2 L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|
  \\ &\leq \ldots \leq 2^{m-1}m!\mu^{m-1} \sup_{\| x^{(k)} \|\leq 1}  \left|S_{m-1} L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|.
 \end{align*}
 Using the identity $S_{m-1} L_P=B$ and applying \eqref{sim}, we obtain
 \begin{align*}
  \sup_{\| x^{(k)} \|\leq 1}  \left|L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right| &\leq 2^{m-1}m!\mu^{m-1} \sup_{\| x^{(k)} \|\leq 1}  \left|B \left(x^{(1)},\ldots,x^{(m)} \right) \right|
  \\ &\leq 2^{m-1}e^{m}m!\mu^{m-1} \sup_{\| x \|\leq 1} |P(x)|.
 \end{align*}
 The theorem follows by applying {Stirling's} formula to estimate $m!$ and Lemma \ref{lema2} to estimate $\mu$.
\end{proof}

\section{Lower Bounds}
Firstly, we provide a lower bound for $C_p(m,n)$.
\begin{lemma}
\label{lema3}
 For every $n\geq m$ and every $1\leq p<2$, we have that $C_p(m,n)\geq m^{\frac{m}{p}}$.
\end{lemma}
\begin{proof}
Let $P:\C^m \rightarrow \C$ be the $m$-homogeneous polynomial defined by
\[P(x)=x_1\ldots x_m.\]
So, its associated $m$-linear form $L_P: \left(\C^m\right)^m \rightarrow \C$ is given by
\[L_P \left(x^{(1)}, \ldots ,x^{(m)} \right)=x_1^{(1)} \ldots x_m^{(m)}.\]
Observe that
\begin{align}
\label{eq1}
\sup_{\| x^{(k)} \|_p\leq 1}  \left|L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|=\sup_{\| x^{(k)} \|_p\leq 1}  \left|x_1^{(1)} \ldots x_m^{(m)} \right|= 1.
\end{align}
where equality is achieved by taking $x^{(i)}$ to be the $i$-th canonical vector of $\ell_p^m$.

On the other hand, a straightforward computation using {Lagrange} multipliers gives
\begin{align}
 \label{eq2}
 \sup_{\| x \|_p\leq 1} |P(x)|=  \left|P\left(m^{-\frac{1}{p}}(1,\ldots, 1) \right) \right|=m^{-\frac{m}{p}} .
\end{align}
Applying \eqref{eq1} and \eqref{eq2} together with the definition of $C_p(m,n)$ we get
\[1=\sup_{\| x^{(k)} \|_p\leq 1}  \left|L_P \left(x^{(1)},\ldots,x^{(m)} \right) \right|\leq C_p(m,n) \sup_{\| x \|_p\leq 1} |P(x)|=m^{-\frac{m}{p}}C_p(m,n),\]
as desired.
\end{proof}

Secondly, we estimate $C(m,n)$ from below. In order to do this we will need the following special case of a theorem proved by {Pe{\l}czy\'nski}.
\begin{theorem}[{\cite[Theorem 1]{pel}}]
\label{teo3}
 For a finite index set $J$, let $(a_j)_{j\in J}$ and $(b_j)_{j\in J}$ be sequences of characters on compact abelian groups $S$ and $T$ respectively.
 Suppose there are constants $c_1,c_2>0$ such that
 \begin{align}
  \label{eq4}
  \frac{1}{c_1} \left\| \sum_{j \in J} \alpha_j a_j \right\|_{C(S)} \leq \left\| \sum_{j \in J} \alpha_j b_j \right\|_{C(T)}
  \leq c_2 \left\| \sum_{j \in J} \alpha_j a_j \right\|_{C(S)},
 \end{align}
 for every sequence of scalars $(\alpha_j)_{j \in J}\subseteq \C$.
 Then, for every {Banach} space $E$ and every sequence of vectors $(v_j)_{j \in J}\subseteq E$ we have
 \begin{align}
  \label{eq5}
  \frac{1}{c_1 c_2} \int_S \left\| \sum_{j \in J} v_j a_j(s) \right\|_E \, ds \leq \int_T \left\| \sum_{j \in J} v_j b_j(t) \right\|_E \, dt
  \leq c_1 c_2 \int_S \left\| \sum_{j \in J} v_j a_j(s) \right\|_E \, ds.
 \end{align}
\end{theorem}

We are ready to provide the lower bound for $C(m,n)$ stated in Theorem \ref{teo1}.
\begin{lemma}
\label{lema4}
 For  $n,m\in\mathbb{N}$ such that $\log\left(\frac{2n}{m}\right)\geq\pi$, we have
 \[C(m,n)\geq \left(\frac{\log\left(\frac{2n}{m}\right)-\pi}{\pi}\right)^{m/2}.\]
\end{lemma}
\begin{proof}
 Consider the norm $\|\cdot \|_\infty$ on $\C^n$.
 Since $P(x)=L_P(x,\ldots ,x)$, we deduce that
 \[\sup_{\| x \|_\infty\leq 1} |P(x)|\leq\sup_{\| x^{(k)} \|_\infty\leq 1}  \left|L_P \left(x^{(1)},\ldots,x^{(m)}\right)\right|
 \leq C(m,n) \sup_{\| x \|_\infty \leq 1} |P(x)|,\]
 for every $m$-homogeneous polynomial $P:\C^n\rightarrow \C$. Equivalently, by the maximum modulus principle we get
 \begin{align}
 \label{eq3}
  \sup_{x \in \T^n} |P(x)|\leq\sup_{x^{(k)}\in \T^n}  \left|L_P \left(x^{(1)},\ldots,x^{(m)}\right)\right|
  \leq C(m,n) \sup_{x \in \T^n} |P(x)|,
 \end{align}
 where $\T=\{z\in\C \ :\ |z|=1\}$.

 Thus, the conditions of {Pe{\l}czy\'nski's} theorem are satisfied. Indeed, denote the compact abelian groups $\T^n$ and $\left(\T^n\right)^m$ by $S$ and $T$ respectively
 and consider the index set $J=\{j \in \mathcal{I}(m,n) \ : \ 1 \leq j_1 \leq \ldots \leq j_m \leq n\}$.
 For every $j \in J$, define the characters $a_j:S \rightarrow \T$ and $b_j: T \rightarrow \T$ by
 \[a_j(x)=x_{j_1} \ldots x_{j_m} \quad \text{and} \quad b_j \left( x^{(1)}, \ldots , x^{(m)}\right)=x_{j_1}^{(1)} \ldots x_{j_m}^{(m)}.\]
 If we restate \eqref{eq3} with this notation we get \eqref{eq4}, with $c_1=1$ and $c_2=C(m,n)$.

 Therefore, we deduce from {Pe{\l}czy\'nski's} theorem that
 \begin{align}
 \label{eq8}
 \frac{1}{C(m,n)} \int_{\T^n} \left\| \sum_{j \in J} v_j x_{j_1} \ldots x_{j_m} \right\|_E \, dx
 &\leq \int_{\T^n}\ldots \int_{\T^n} \left\| \sum_{j \in J} v_j x_{j_1}^{(1)} \ldots x_{j_m}^{(m)} \right\|_E \, dx^{(1)} \ldots  dx^{(m)} \notag
 \\& \leq C(m,n) \int_{\T^n} \left\| \sum_{j \in J} v_j x_{j_1} \ldots x_{j_m} \right\|_E \, dx.
 \end{align}
 for every {Banach} space $E$ and every sequence of vectors $(v_j)_{j \in J}\subseteq E$.
 Choosing the space $E$ and the vectors $(v_j)_{j \in J}\subseteq E$ adequately will yield the estimate we seek.

 We will build upon an example provided by {Bourgain} (unpublished) and included in a paper by {McConnell} and {Taqqu} \cite[Example 4.1]{mctaq} (see also \cite[Section~6.9]{kwapien}).
 Consider the {Banach} space $F= \mathcal{L}(\ell_2)$. For every $1\leq i \neq j \leq n$, define vectors $v_{ij}\in F$ by
 \[v_{ij} = \frac{1}{i-j} e_i\otimes e_j+\frac{1}{j-i} e_j\otimes e_i.\]
 Using complex {Steinhaus} variables instead of {Bernoulli} random variables and proceeding as in \cite{kwapien} we get
 \begin{align}
 \label{eq6}
  \int_{\T^n}\left\|\sum_{1\leq i<j \leq n} v_{ij}x_i x_j\right\|&  \, dx \leq \pi \quad \quad \text{and}
  \\ \label{eq7} \int_{\T^n} \int_{\T^n} \left\|\sum_{1\leq i<j \leq n} v_{ij}x_i^{(1)} x_j^{(2)}\right\|& \, dx^{(1)} dx^{(2)} \geq \log n -\pi.
 \end{align}

 Note that by the previous estimations we obtain the desired result for $m=2$ since we have
 \begin{multline*}
  \log n -\pi\leq \int_{\T^n} \int_{\T^n} \left\|\sum_{1\leq i<j \leq n} v_{ij}x_i^{(1)} x_j^{(2)}\right\| \, dx^{(1)} dx^{(2)}
 \\ \leq C(2,n) \int_{\T^n}\left\|\sum_{1\leq i<j \leq n} v_{ij}x_i x_j\right\|  \, dx \leq C(2,n) \pi.
 \end{multline*}
 Moreover, this together with Theorem \ref{teo2} shows that the asymptotic behaviour of $C(2,n)$ is logarithmic.

 To conclude our argument it remains to extend this 2-variable example to $m$ variables.
 Assume $m$ is even and let $E= \bigotimes_{k=1}^{m/2}F$ be the projective tensor product of $m/2$ copies of $F$.
 Consider the $m$-homogeneous vector-valued polynomial $P:\mathbb{C}^n\rightarrow E$ defined by
\[P(x)= \sum_{\substack{\frac{2n}{m}(k-1)<j_{2k-1}<j_{2k}\leq \frac{2n}{m}k\\1\leq k \leq \frac{m}{2}}}v_jx_j,
\quad \text{where } v_j= v_{j_1 j_2}\otimes v_{j_3 j_4}\otimes \ldots \otimes v_{j_{m-1} j_m}.\]
Notice that
\[P(x)= \otimes_{k=1}^{m/2} \sum_{\frac{2n}{m}(k-1)<j_{2k-1}<j_{2k}\leq \frac{2n}{m}k}v_{j_{2k-1}j_{2k}}x_{j_{2k-1}}x_{j_{2k}}.\]
Applying \eqref{eq6} we get
\begin{align*}
 \int_{\T^n}\left\|P(x)\right\| \, dx &=
 \int_{\T^n} \prod_{k=1}^{m/2} \left\|\sum_{\frac{2n}{m}(k-1)<j_{2k-1}<j_{2k}\leq \frac{2n}{m}k}v_{j_{2k-1}j_{2k}}x_{j_{2k-1}}x_{j_{2k}}\right\| \, dx
 \\ &= \prod_{k=1}^{m/2} \int_{\T^n} \left\|\sum_{\frac{2n}{m}(k-1)<j_{2k-1}<j_{2k}\leq \frac{2n}{m}k}v_{j_{2k-1}j_{2k}}x_{j_{2k-1}}x_{j_{2k}}\right\| \, dx
 \\ &\leq \prod_{k=1}^{m/2} \pi = \pi^{m/2}.
 \end{align*}
 On the other hand, from \eqref{eq7} we deduce
 \begin{align*}
 \int_{\T^n} \ldots \int_{\T^n}&\left\|L_P\left(x^{(1)},\ldots,x^{(m)}\right)\right\| \, dx^{(1)} \ldots  dx^{(m)}=
 \\ &=\int_{\T^n} \ldots \int_{\T^n} \prod_{k=1}^{m/2}
 \left\|\sum_{\frac{2n}{m}(k-1)<j_{2k-1}<j_{2k}\leq \frac{2n}{m}k}v_{j_{2k-1}j_{2k}}x_{j_{2k-1}}^{(2k-1)}x_{j_{2k}}^{(2k)}\right\| \, dx^{(1)} \ldots  dx^{(m)}
 \\ &= \prod_{k=1}^{m/2} \int_{\T^n} \int_{\T^n}
 \left\|\sum_{\frac{2n}{m}(k-1)<j_{2k-1}<j_{2k}\leq \frac{2n}{m}k}v_{j_{2k-1}j_{2k}}x_{j_{2k-1}}^{(2k-1)}x_{j_{2k}}^{(2k)}\right\| \, dx^{(2k-1)} dx^{(2k)}
 \\ &\geq \prod_{k=1}^{m/2} \left(\log\left(\frac{2n}{m}\right)-\pi\right) =  \left(\log\left(\frac{2n}{m}\right)-\pi\right)^{m/2}.
\end{align*}
Finally, using \eqref{eq8} together with these estimates we obtain
\[C(n,m)\geq \left(\frac{\log\left(\frac{2n}{m}\right)-\pi}{\pi}\right)^{m/2},\]
as desired.
\end{proof}

Note that Lemmas \ref{lema3} and \ref{lema4} together with Theorem \ref{teo2} prove Theorem \ref{teo1}.

\begin{remark}
Tracing back the argument to obtain \eqref{eq7}, we find that Bourgain's example is based on a lower estimate of the main triangle projection's norm on $\mathcal{L}(\ell_2)$.
In other words, the lower bound for $C(m,n)$ was obtained by studying the behaviour of the main triangle projection as mentioned in Remark \ref{rem1}.
Although $C(m,n)$ and $C_p(m,n)$ were not completely characterized, it seems that the main triangle projection plays a crucial role in determining their asymptotic behaviour.
\end{remark}

\section*{Acknowledgements}
I thank my supervisor Daniel Carando for his guidance and fruitful discussions and  Sunke Schl\"uters for his helpful comments.


TITLE: What is the idea behind a projection operator? What does it do?
QUESTION [38 upvotes]: I know what a projection operator is, but I am unable to explain it in words without using mathematical symbols. Can anyone help me?
I don't need examples or the definition - I want to know why and how its need arose, and what is the idea behind it?

REPLY [1 votes]: The key is to choose the right frame of reference, and all will become clear. Consider the operator that takes points (x, y, z) in 3-dimensional space and maps them to (x, y, 0). Geometrically, this is what user50618 suggested with the steamroller above: the x and y positions remain the same, while the z gets compressed down to zero.
The matrix representing this projection is:
1   0   0
0   1   0
0   0   0

If you put the column vector [ x  y  z  ] to the right of that matrix, you see the multiplication:
1   0   0       x      x
0   1   0   *   y  =   y
0   0   0       z      0

If you do it again, no more change occurs. z remains zero. This is called being "idempotent."
And if you look at the diagonal of the matrix, you see two 1's for the directions that stay the same, and a single 0 for the direction that gets collapsed.
Now, ANY projection of 3-space onto a 2-dimensional subspace has EXACTLY that same geometry. It's just much harder to see when the direction of collapse is not lined up nicely with one of the coordinate axes.
The process of diagonalizing a matrix represents finding the natural directions of the linear transformation, and rewriting the matrix with respect to those natural directions. When written in a basis of its eigenvectors (the name for the natural directions), the matrix will be diagonal. In the case of a projection, the diagonal entries will all be ones or zeros, representing the directions which are preserved or collapsed.

Here is an example (not a projection), which is easy to write:
1   -1
-1  1

It is not immediately obvious what this linear transformation does, because its action is not aligned nicely with the coordinate axes.  But think about what it does to the vector (1, 1). It collapses it to zero.  And think about what it does to the vector (1, -1). That becomes (2, -2).  This tells us that the matrix represents the same geometric action as this matrix:
0   0
0   2

That is, one axis gets stretched to double its length, and the other gets squashed down to zero. This becomes clear when you use the "right" basis  - the basis of eigenvectors - to write the matrix.

Note that some matrices cannot be diagonalized, and some that can require complex numbers. But projections always can be diagonalized using only real numbers.


TITLE: How to convert formula to DNF and CNF?
QUESTION [0 upvotes]: I have to convert the following formula to a DNF and CNF:
$((x→y)→(z→¬x))→(¬y→¬z)$
Removing the arrows and using DeMorgan Laws, I ended up with:
$((¬x \vee ¬y) \wedge (z \wedge x)) \vee (y \wedge ¬z)$
Using the associative law I ended up with:
$((¬x \vee ¬y) \wedge (y \wedge ¬z)) \vee ((z \wedge x) \wedge (y \wedge ¬z))$
Now this is where I'm stuck. I'm not entirely sure whether or not I just did something wrong along the way. This looks kind of like a DNF, and since it has both y and not y on the left and z and not z on the right, it looks reminescent of a contradiction, but I am kind of stuck as neither of the two terms is a conjunction of atoms, but rather of smaller formulas.

REPLY [0 votes]: First, some things are going wrong in your initial steps already:
$$((x \to y)\to(z\to \neg x))\to (\neg y \to \neg z)$$
becomes:
$$\neg (\neg (\neg x \lor y) \lor (\neg z\lor \neg x)) \lor (\neg \neg y \lor \neg z)$$
which becomes:
$$((\neg x \lor y) \land \neg (\neg z\lor \neg x)) \lor (y \lor \neg z)$$
and thus:
$$((\neg x \lor y) \land (z\land x)) \lor (y \lor \neg z)$$
... which is different from what you had.
Now, by Association, we can drop parentheses:
$$((\neg x \lor y) \land z \land x) \lor y \lor \neg z$$
This is not yet in DNF, since you have a disjunction as a conjunct on the left. This is basically what you were struiggling with.
Well, when you have disjunctions as part of conjunctions, you can simply Distribute the conjunction over the disjunction, so you get:
$$((\neg x \land z \land x) \lor (y \land z \land x)) \lor y \lor \neg z$$
And we can drop some more parentheses:
$$(\neg x \land z \land x) \lor (y \land z \land x) \lor y \lor \neg z$$
and now it is nicely in DNF .... though it can still be simplified further:
The term on the left contains both $x$ and $ \neg x$, and hence is a contradiction, and hence can be removed completely. Also, the $y$ term absorbs the $y \land z \land x$ term, so that latter term can be removed as well, leaving you with:
$$y \lor \neg z$$


TITLE: Minimal polynomial of $2^{-1/5}$
QUESTION [2 upvotes]: I'm trying to show that $x^5-1/2$ is the minimal polynomial of $2^{-1/5}$.
I know I have to show that it's irreducible over Q. First I have to show that it has no rational roots (no problem!) then I have to show that it cannot be written as a product of a second degree and a third degree polynomial (also no problem). The thing is that I would like to have a cleaner solution. For instance, I've already shown that the minimal polynomial of the inverse element $2^{1/5}$ is $x^5-2$ using Eisenstein's criterion. It seems I should be able to use that somehow. Is it for example true that an element and its inverse have the same degree of the minimal polynomial? How would I go about to prove that?

REPLY [5 votes]: Is it for example true that an element and its inverse have the same degree of the minimal polynomial?

Yes. Let $K$ any field, and $\alpha \neq 0$ algebraic over $K$. Since $\alpha^{-1} \in K(\alpha)$ we have $K(\alpha^{-1}) \subset K(\alpha)$. Symmetrically, we have $K(\alpha) \subset K(\alpha^{-1})$, hence equality.
Now, $[K(\alpha) : K]$ is the degree of the minimal polynomial of $\alpha$, and of course $[K(\alpha^{-1}) : K]$ is the degree of the minimal polynomial of $\alpha^{-1}$. Since the extensions are the same, the degrees are the same.


TITLE: Collinear Points in 3-Dimensions
QUESTION [1 upvotes]: The points A(3, -1, z), B(1, 2, 6), and C(x, 8, 14) are collinear. Find the values of x and z.
I have tried finding common ratios between the points, but no common ratio is possible, I have a feeling that this involves making the points into vectors, but I am not sure at this point?

REPLY [0 votes]: I think you're assuming that the line passes through the origin.
Since $(1,2,6)$ is a point on the line, $(3,-1,z)-(1,2,6)$ and $(x,18,14)-(1,2,6)$
should have common ratios. Using this, you can figure out that $x=-3$ and $z=2$.


TITLE: The sum of odd numbers
QUESTION [0 upvotes]: How to know the sum of odd numbers that between $1$ and $1000$ and their remainder when we divide them by $5$ is $3$.

REPLY [1 votes]: Hint: You are looking for odd number of the  form $5j+3$ for some integer $j$. Since $3,5j+3$ are odd, therefore $5j$ must be even. Thus $j$ must be even. Let $j=2i$. The numbers that you are looking for are of the form $10i+3$.such that $1\leq 10i+3\leq 1000$. Thus, $\frac{-2}{10}\leq i\leq \frac{997}{10}$. Can you evaluate $\sum_{i=0}^{99} 10i+3$


TITLE: Proving $2(\sqrt{n} - 1) < \sum\limits_{i=1}^n\frac{1}{\sqrt i}$
QUESTION [6 upvotes]: I'm trying to prove $$2(\sqrt{n} - 1) < \sum_{i=1}^n\frac{1}{\sqrt i}$$ (Which is the opposite pretty much of Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$)
And I'm encountering some troubles I fail to see through.
My attempt is by induction, and for $n=1$ it's clear, then if I assume for $k$ I get that for $k+1$:
$$2(\sqrt{k+1} - 1) < \sum_{i=1}^{k+1}(\frac{1}{\sqrt i})$$
$$\sum_{i=1}^{k+1}(\frac{1}{\sqrt i}) > 2(\sqrt{k}-1)+\frac{1}{\sqrt{k+1}}$$
Which would mean I would like to find that:
$$2(\sqrt{k}-1)+\frac{1}{\sqrt{k+1}} - 2(\sqrt{k+1} - 1) > 0$$
But this is what I get:
$$\frac{1}{\sqrt{k+1}}+2\sqrt{k}-2\sqrt{k+1}=\frac{1}{\sqrt{k+1}}+2\frac{\left(\sqrt{k}-\sqrt{k+1}\right)\left(\sqrt{k}+\sqrt{k+1}\right)}{\sqrt{k}+\sqrt{k+1}}=$$
$$ \frac{1}{\sqrt{k+1}}+2\frac{k-k-1}{\sqrt{k}+\sqrt{k+1}}=\frac{1}{\sqrt{k+1}}-\frac{2}{\sqrt{k}+\sqrt{k+1}}=$$
$$ \frac{\sqrt{k}+\sqrt{k+1}-2\sqrt{k+1}}{\sqrt{k}\left(\sqrt{k}+\sqrt{k+1}\right)}<0)
 $$
So that is not true, how can I find that $\sum_{i=1}^{k+1}(\frac{1}{\sqrt i}) > 2(\sqrt{k+1} - 1)$ if what I get from my induction hypothesis doesn't help me since it's already smaller than what I'm searching for?

REPLY [0 votes]: Alternative approach: since $f(x)=\sqrt{x}$ is a differentiable and concave function on $\mathbb{R}^+$,
$$\delta(x,y) = \left\{\begin{array}{ccc}\frac{f(y)-f(x)}{y-x}&\text{if}&x\neq y\\ f'(x)&\text{if}&x=y\end{array}\right.$$
is a decreasing function with respect to both its parameters. This gives:
$$ \frac{1}{2\sqrt{n}}=\delta(n,n)\geq \delta(n,n+1) = \sqrt{n+1}-\sqrt{n}, $$
so, summing both sides of the previous inequality for $n=1,2,\ldots,N$ we get:
$$ \sum_{n=1}^{N}\frac{1}{\sqrt{n}}\geq 2\left(\sqrt{N+1}-1\right) $$
as wanted.


text:
\begin{document}

\maketitle

\begin{abstract}

In this paper, we propose a distributed zeroth-order policy optimization method for Multi-Agent Reinforcement Learning (MARL). Existing MARL algorithms often assume that every agent can observe the states and actions of all the other agents in the network. This can be impractical in large-scale problems, where sharing the state and action information with multi-hop neighbors may incur significant communication overhead. The advantage of the proposed zeroth-order policy optimization method is that it allows the agents to compute the local policy gradients needed to update their local policy functions using local estimates of the global accumulated rewards that depend on partial state and action information only and can be obtained using consensus. Specifically, to calculate the local policy gradients, we develop a new distributed zeroth-order policy gradient estimator that relies on one-point residual-feedback which, compared to existing zeroth-order estimators that also rely on one-point feedback, significantly reduces the variance of the policy gradient estimates improving, in this way, the learning performance. We show that the proposed distributed zeroth-order policy optimization method with constant stepsize converges to a neighborhood of the global optimal policy that depends on the number of consensus steps used to calculate the local estimates of the global accumulated rewards. Moreover, we provide numerical experiments that demonstrate that our new zeroth-order policy gradient estimator is more sample-efficient compared to other existing one-point estimators.
\end{abstract}

\section{Introduction}
\input{tex/intro}

\section{Preliminaries and Problem Formulation}
\label{sec:MARL}
\input{tex/prelim}

\section{Algorithm Design and Theoretical Analysis}
\label{sec:Algorithm}
\input{tex/algorithm}

\section{Experiments}
\input{tex/exp}

\section{Conclusion}
\input{tex/conclusion}

\input{tex/broad}

\bibliographystyle{icml2020}
\bibliography{biblio}

\input{tex/appendix}

\end{document}

config: arxiv


TITLE: Sphere mass increase rotation period
QUESTION [0 upvotes]: What is the effect on period of rotation of a sphere as mass and volume increase, when increasing mass makes no contribution to angular momentum?

REPLY [1 votes]: Angular momentum (like linear momentum) is a constant for a system with no external forces/torques.
Calculate the angular momentum of the starting material (in this case it should include the initial rotating sphere and all the accreting material).
$$ L_{total} = L_{initial sphere} + L_{accretion1} + ... + L_{accretion k}$$
Then use the moment of inertia of the now larger sphere and the known angular momentum to calculate the rotational velocity.
$$ L = I \omega $$
$$ \omega_{final} = \frac{L_{total}}{I_{final sphere}}$$


TITLE: a problem with "Lower bound of Wilson score confidence interval"
QUESTION [2 upvotes]: Hi,
I am trying to calculate the 'Most helpful' review. I found a solution few days ago on Calculating the "Most Helpful" review
I have a new problem now..
Let's say I have two items. The first item has "480 people found this review helpful among 961 people". The second item has "3 people found this review helpful among 5 people".
first item: 480 people liked it, but 481 people didn't.
second item: 3 people liked it, but 2 people didn't.
I personally think that the second item should have higher rank than the first item because more than 50% of people didn't like the first item.
When I use "Lower bound of Wilson score confidence interval for a Bernoulli parameter", I get the following value for the two items.

first: 0.467932469089
second: 0.230724282841

the first item has higher point than the second item.
Is this correct??

REPLY [3 votes]: This is an old question now but as I've been looking into this stuff tonight ...
You are calculating the confidence interval for a binomial distribution and using the lower bound as your "score" of helpfulness. A confidence interval defines a plausible range of values for the true mean given your observed values and sample size.
When the sample size is small (like just 5 people) this range will generally be larger as there is less confidence that the true mean has been observed. As such your lower bound could well be lower than the lower bound for another sample with a lower observed mean (like the first item in your example).
So yes, I think it probably is correct (although I haven't checked the answer myself!)


text:
\begin{document}

\maketitle
\begingroup\renewcommand\thefootnote{*}
\footnotetext{Authors contributed equally to this paper and are listed alphabetically.}
\endgroup

\begin{abstract}
  We study without-replacement SGD for solving finite-sum optimization problems.
  Specifically, depending on how the indices of the finite-sum are shuffled, we consider the $\randshuf$ (shuffle at the beginning of each epoch) and $\singshuf$ (shuffle only once) algorithms.
  First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors.
  Notably, our analysis is general enough to cover gradient dominated \emph{nonconvex} costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results.
  Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for $\randshuf$ by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.
\end{abstract}

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

\lettrine[lines=3]{\color{BrickRed}S}{\rm{}tochastic} gradient descent (SGD) \cite{robbins1951stochastic, kiefer1952stochastic} is a widely used optimization method for solving finite-sum optimization problems that arise in many domains such as machine learning:
\begin{align} \label{opt}
    \minimize_{\vx \in \reals^d} \quad F(\vx) \defeq \frac{1}{n} \sum_{i=1}^n f_i(\vx)\,.
\end{align}
Given an initial iterate $\vx_0$, at iteration $t\geq1 $, SGD samples a component index $i(t)$ and updates the current iterate using the (sub)gradient $\vg_{i(t)}$ of $f_{i(t)}$ at $\vx_{t-1}$:

\begin{equation*}
  \vx_{t} = \vx_{t-1} - \eta_t \vg_{i(t)}\ \text{for some step size $\ee_t>0$}.
\end{equation*}

There are two versions of SGD, depending on how we sample the index $i(t)$: \emph{with-replacement} and \emph{without-replacement}.
With-replacement SGD samples $i(t)$ uniformly and independently from the set of indices $\{1,\ldots,n\}$; hereafter, we use $\sgd$ to denote with-replacement SGD.
For without-replacement SGD, there are two popular versions in practice.
Calling one pass over the entire set of $n$ components an \emph{epoch}, one version randomly shuffles the indices at each epoch (which we call $\randshuf$), and the other version shuffles the indices only once and reuses that order for all the epochs (which we call $\singshuf$).

In modern machine learning applications, $\randshuf$ and $\singshuf$ are much more widely used than $\sgd$, due to their simple implementations and better empirical performance~\cite{bottou2009curiously,bottou2012stochastic}. However, most theoretical analyses have been devoted to $\sgd$ for its easy-to-analyze setting: each stochastic gradient is an i.i.d.\ unbiased estimate of the full gradient. Whereas for $\randshuf$ and $\singshuf$, not only is each stochastic gradient a \emph{biased} estimate of the full gradient, but each sample $i(t)$ is also \emph{dependent} on the previous samples within the epoch. This dependence poses significant challenges toward analyzing shuffling based SGD.
Recently, several works have (in part) overcome such challenges and initiated theoretical studies of  $\randshuf$ and $\singshuf$~\cite{gurbuzbalaban2015random, gurbuzbalaban2019incremental, shamir2016without, haochen2018random, nagaraj2019sgd, safran2019good, rajput2020closing, nguyen2020unified}.

\vspace*{-3pt}
\subsection{What is known so far?}
\vspace*{-3pt}
We provide in Table~\ref{tab:results} a comprehensive summary of the known upper and lower bounds for convergence of $\randshuf$. For a similar summary of $\singshuf$, please refer to Table~\ref{tab:resultssing} in Section~\ref{sec:singshuf}.
There are three classes of differentiable functions $F \defeq \frac{1}{n} \sum_{i=1}^n f_i$ considered in the table, in decreasing order of generality: (1) $F$ satisfies the Polyak-{\L}ojasiewicz (P{\L}) condition and $f_i$'s are smooth; (2) $F$ is strongly convex and $f_i$'s are smooth; (3) $F$ is strongly convex quadratic and $f_i$'s are quadratic.
Many existing results additionally assume that the component functions $f_i$'s are convex and/or all the iterates are bounded.

\begin{table}
\caption{\small A summary of existing convergence rates and our results for $\randshuf$.
All the convergence rates are with respect to the suboptimality of objective function value.
Note that since the function classes become more restrictive as we go down the table, the noted lower bounds are also valid for upper rows, and the upper bounds are also valid for lower rows. In the ``Assumptions'' column, inequalities such as $K \gtrsim \kappa^\alpha$ mark the requirements $K \geq C \kappa^\alpha \log (nK)$ for the bounds to hold, and \bia~denotes the assumption that all the iterates remain in a bounded set (see Assumption~\ref{a:1}).
Also, (LB) stands for ``lower bound.''
For $\singshuf$, please see Table~\ref{tab:resultssing} in Section~\ref{sec:singshuf}.}
\centering
\begin{threeparttable}
\begin{tabular}{ |l |l| l c r|  }
\hline
 \multicolumn{5}{|c|}{Convergence rates for $\randshuf$}\\
\hline \multicolumn{2}{|c|}{Settings} &References & Convergence rates & Assumptions\\
\hline\hline
\multirow{4}{1.3cm}[-10pt]{(1) $F$\\  satisfies\\P{\L}\\condition} & \multirow{4}{1.5cm}[-10pt]{$f_i$ smooth} &{Haochen and Sra~\cite{haochen2018random}}\tnote{$\dag$} & $O\Big(\frac{\log^3(nK)}{(nK)^2}+\frac{\log^4(nK)}{K^3}\Big)$& $K\gtrsim \kappa^2$~\& \bia\\
& &{Nguyen et al.~\cite{nguyen2020unified}} &$O\Big(\frac{1}{K^2}\Big)$& $K \geq 1$  \\
  & &\cellcolor{LightGray}{\bf Ours }(Thm~\ref{thm:plconv}) &\cellcolor{LightGray}$O\Big(\frac{\log^3(nK)}{nK^2}\Big)$& \cellcolor{LightGray} $K\gtrsim \kappa$\\
 \cline{3-5}
 & &{Rajput et al.~\cite{rajput2020closing}}& $\Omega\Big(\frac{1}{nK^2}\Big)$ (LB) & const.\ step size\\
 \hline\hline
\multirow{4}{1.3cm}[-20pt]{(2) $F$\\strongly\\convex} &    $f_i$ smooth
  & \cellcolor{LightGray}{\bf Ours }(Thm~\ref{thm:plconv}) &\cellcolor{LightGray}$O\Big(\frac{\log^3(nK)}{nK^2}\Big)$ & \cellcolor{LightGray} $K\gtrsim \kappa$\\
  \cline{2-5}
  &    \multirow{4}{1.5cm}[-7pt]{$f_i$ smooth\\  convex }  & {Nagaraj et al.~\cite{nagaraj2019sgd}} &$O\Big(\frac{\log^2(nK)}{nK^2}\Big)$& $K \gtrsim \kappa^2$~\& \bia\\
 & & {Mishchenko et al.~\cite{mishchenko2020random}}\tnote{$\ddag$} &$O\Big(\frac{\log^2(nK)}{nK^2}\Big)$& $K \gtrsim \kappa$ \\
  & &\cellcolor{LightGray}{\bf Ours }(Thm~\ref{thm:1}) &\cellcolor{LightGray}$O\Big(\frac{1}{nK^2}\Big)$ & \cellcolor{LightGray} $K\geq 1$~\& \bia\\
  \cline{3-5}
  & &{Rajput et al.~\cite{rajput2020closing}}& $\Omega\Big(\frac{1}{nK^2}\Big)$ (LB) & const.\ step size\\
  \hline\hline
 \multirow{6}{1.3cm}[-16pt]{(3) $F$\\ strongly\\convex\\ quadratic} &    \multirow{2}{1.5cm}[-3pt]{$f_i$ smooth\\quadratic}
 & {G{\"u}rb{\"u}zbalaban et al.~\cite{gurbuzbalaban2015random}}&  $O\Big(\frac{1}{(nK)^2}\Big) +o\Big(\frac{1}{K^2}\Big)$ &asymptotic\\
 & &  \cellcolor{LightGray}{\bf Ours }(Thm~\ref{thm:quadratic}) & \cellcolor{LightGray}$O\Big(\frac{\log^2(nK)}{(nK)^2} + \frac{\log^4(nK)}{nK^3}\Big)$& \cellcolor{LightGray} $K\gtrsim \kappa$\\
 \cline{2-5}
 & \multirow{4}{1.5cm}[-11pt]{$f_i$ smooth\\quadratic \\ convex}   & {Haochen and Sra~\cite{haochen2018random}} & $O\Big(\frac{\log^3(nK)}{(nK)^2} + \frac{\log^4(nK)}{K^3}\Big)$& $K\gtrsim \kappa$~\& \bia\\
 & & {Rajput et al.~\cite{rajput2020closing}}\tnote{*} & $O\Big(\frac{\log^2(nK)}{(nK)^2} + \frac{\log^3(nK)}{nK^3}\Big)$& $K\gtrsim \kappa^2 $~\& \bia\\
 & &\cellcolor{LightGray}{\bf Ours }(Thm~\ref{thm:2})\tnote{*} &\cellcolor{LightGray}$O\Big(\frac{1}{(nK)^2} + \frac{1}{nK^3}\Big)$&\cellcolor{LightGray} $K\geq 1$~\& \bia \\
 \cline{3-5}
 & &\makecell[l]{Safran and Shamir~\cite{safran2019good}}& $\Omega \Big(\frac{1}{(nK)^2} + \frac{1}{nK^3}\Big)$ (LB)& const.\ step size\\
  \hline
\end{tabular}
\begin{tablenotes}
\item[$\dag$] additionally assumes Lipschtiz Hessian, which the lower bound \cite{rajput2020closing} does not; hence, the rate does not contradict the lower bound when $K \gtrsim n$.
\item[$\ddag$] also presents a bound with epoch requirement $K \gtrsim \nicefrac{\kappa}{n}$ by assuming \textit{strongly convex} $f_i$'s.
\item[*] does not require that $f_i$'s are quadratic.
\end{tablenotes}
\end{threeparttable}
\label{tab:results}
\end{table}

In this paper, $n$ denotes the number of component functions, $K$ denotes the number of epochs, and $\kappa$ denotes the condition number of the problem: i.e., $\kappa:=\nicefrac{L}{\mu}$ where $L$ is the smoothness constant and $\mu$ is the strong convexity  or P{\L} constant. All the convergence rates are with respect to the suboptimality of objective function value (i.e., $F(x)-F(x^*)$ for a suitable iterate $x$).
In our notation the well-known optimal convergence rate of \sgd is $\OO{\nicefrac{1}{nK}}$, which we will refer to as the baseline.

\paragraph{Initial progress.}
One of the first works to report progress is due to by G{\"u}rb{\"u}zbalaban, Ozdaglar, and Parrilo~\cite{gurbuzbalaban2015random, gurbuzbalaban2019incremental} for strongly convex $F$ and smooth quadratic $f_i$'s. They prove an asymptotic convergence rate of $\OO{\nicefrac{1}{K^2}}$ for $K$ epochs when $n$ is treated as a constant, both for $\randshuf$ and $\singshuf$. This is indeed an asymptotic improvement over the convergence rate of $\OO{\nicefrac{1}{nK}}$ achieved by $\sgd$.
The scope of the inspiring result in \cite{gurbuzbalaban2015random}, however, does not match the scope of modern machine learning applications for its asymptotic nature and its treatment of $n$ as a constant\footnote{Although one can actually deduce the asymptotic convergence rate of $\OO{\nicefrac{1}{(nK)^2}}+o(\nicefrac{1}{K^2})$ closely following their arguments~\cite[(58)]{gurbuzbalaban2015random}, the lower order term does not show the exact dependence on $n$.}.
Indeed, in modern machine learning, $n$  cannot be regarded as a constant as it is equal to the number of data items in a training set, and the \emph{non-asymptotic} convergence rate is of greater significance as the algorithm is only run a few epochs in practice.

\paragraph{First non-asymptotic results.} Subsequent recent efforts seek to characterize non-asymptotic convergence rates in terms of both $n$ and $K$.
For the same setting as \cite{gurbuzbalaban2015random}, Haochen and Sra~\cite{haochen2018random} develop the first \emph{non-asymptotic} convergence rate of $\OO{\nicefrac{\log^3(nK)}{(nK)^2} +\nicefrac{\log^4(nK)}{K^3}}$ for $\randshuf$ under the condition $K \gtrsim \kappa \log (nK)$. They extend this result also to smooth functions satisfying the P{\L} condition and show the same convergence rate, albeit with an additional Lipschtiz Hessian assumption and a more stringent requirement $K \gtrsim \kappa^2 \log (nK)$.
These rates, however, improve upon the baseline rate $\OO{\nicefrac{1}{nK}}$ only after $\omega(\sqrt{n})$ epochs.

\paragraph{Tight upper and lower bounds.} The non-asymptotic results in~\cite{haochen2018random} are strengthened in follow-up works.
Nagaraj, Jain, and Netrapalli~\cite{nagaraj2019sgd} consider a setting where $F$ is strongly convex and the $f_i$'s are no longer assumed to be quadratic, just convex and smooth. They introduce coupling arguments to prove a non-asymptotic convergence rate of $\OO{\nicefrac{\log^2(nK)}{nK^2}}$ for $\randshuf$, under the epoch requirement $K \gtrsim \kappa^2 \log (nK)$. Note that this rate is better than the baseline  $\OO{\nicefrac{1}{nK}}$ as soon as the condition $K \gtrsim \kappa^2 \log (nK)$ is fulfilled.

The result in~\cite{nagaraj2019sgd} has motivated researchers to revisit the quadratic finite-sum case
and obtain a convergence rate that has a better dependency on $n$ than that of~\cite{haochen2018random}.
The first set of results in this direction are given by Safran and Shamir~\cite{safran2019good}, who develop a lower bound of $\Om{\nicefrac{1}{(nK)^2} +\nicefrac{1}{nK^3}}$ for $\randshuf$ under the assumption of constant step size. They also prove a lower bound of $\Om{\nicefrac{1}{nK^2}}$ for $\singshuf$\footnote{Note that these lower bounds hold for more general function classes as well.} under constant step size, and establish matching upper bounds for the \emph{univariate} case up to poly-logarithmic factors, evidencing that their lower bounds are likely to be tight.
For $\randshuf$, the question of tightness is settled by Rajput, Gupta, and Papailiopoulos~\cite{rajput2020closing} who establish the non-asymptotic convergence rate of $\OO{\nicefrac{\log^2(nK)}{(nK)^2} +\nicefrac{\log^3(nK)}{nK^3}}$ under the condition $K\gtrsim \kappa^2 \log (nK)$ by building on the coupling arguments in~\cite{nagaraj2019sgd}. Assuming constant step size, they also prove the lower bound $\Om{\nicefrac{1}{nK^2}}$ for strongly convex $F$, showing the tightness (up to poly-logarithmic factors) of the result in \cite{nagaraj2019sgd}.

Moreover, there is a concurrent work by Mishchenko et al.~\cite{mishchenko2020random}, which establishes a refined analysis and improves upon the epoch requirement of \cite{nagaraj2019sgd}  (see Table~\ref{tab:results}).
However, in contrast with our result, their analysis requires the individual components to be convex.
They also demonstrate that one can significantly relax the epoch requirement (to $K \gtrsim \nicefrac{\kappa}{n}$) by additionally assuming that individual components are \emph{strongly} convex.
This is also in contrast with our results to follow, because we prove a tighter rate (without poly-log factors) with epoch requirement $K \geq 1$ only assuming individual component convexity.
Notably, their analysis for strongly convex individual components applies to \singshuf as well, and guarantees the same rate.
We note that \cite{mishchenko2020random} also provides analyses of general convex and nonconvex costs.

\paragraph{Other related works.} Nguyen et al.~\cite{nguyen2020unified} provide a unified analysis for both $\randshuf$ and $\singshuf$, and prove $\OO{\nicefrac{1}{K^2}}$ convergence rates for $F$ satisfying the P{\L} condition or strong convexity. Although these results do not have epoch requirements, they do \emph{not} beat the baseline rate $\OO{\nicefrac{1}{nK}}$ of $\sgd$ unless $K\gtrsim n$.
Lastly, Shamir~\cite{shamir2016without} considers the case where $F$ is a generalized linear function and shows that without-replacement SGD is not worse than $\sgd$.
His proof techniques use tools from transductive learning theory, and as a result, his results only cover the first epoch.

\vspace*{-3pt}
\subsection{Limitations of the prior arts}
\vspace*{-3pt}
Despite such noticeable progress, there are two primary limitations shared by many existing results, including \emph{all} the minimax optimal upper bounds \cite{nagaraj2019sgd, rajput2020closing} known to date:
\begin{list}{{\tiny$\bullet$}}{\leftmargin=1.8em}

\item The convergence results assume that the component functions $f_i$'s are convex.

    For example, the tight rates on strongly convex $F$ \cite{nagaraj2019sgd} and quadratic $F$ \cite{rajput2020closing} are obtained using coupling arguments showing that each iterate of $\randshuf$ makes progress on par with $\sgd$, which crucially exploits the convexity of individual $f_i$'s. This dependence limits one from extending their results to nonconvex functions.
    \item The upper bounds require that the number of epochs be of the form $K \gtrsim \kappa^{\alpha} \log (nK)$ for some constant $\alpha\geq 1$\footnote{There are some exceptions, but they do not match the lower bounds \cite{nguyen2020unified} or rely on strongly convex components \cite{mishchenko2020random}.}, and have extra poly-logarithmic factors of $nK$. In many cases, these limitations stem from choosing a constant step size $\eta$ in the analysis. More specifically, it turns out that one needs to choose a step size of order $\eta \asymp \nicefrac{\kappa \log(nK)}{ n K}$, while in order to ensure a sufficient progress  during each epoch, one also needs to choose $\eta \lesssim (\kappa^{\alpha-1} n )^{-1}$.
    From these conditions, the requirement $K \gtrsim \kappa^{\alpha} \log (nK)$ and poly-log factors arise (see Section~\ref{ps:1} for details).
\end{list}

\subsection{Summary of our contributions} \label{sec:sum}
We overcome the limitations pointed out above. Our theorems can be put into three groups: (i)~using techniques that do \emph{not} require individual convexity, we extend the tight convergence bounds of $\randshuf$ to the more general class of nonconvex P{\L} functions, importantly, while also improving the epoch requirements of existing results (Theorems~\ref{thm:plconv} and \ref{thm:quadratic}); (ii)~by adopting varying step sizes, we prove convergence bounds of $\randshuf$ that are \emph{free} of epoch requirements and poly-log factors, this time with convexity (Theorems~\ref{thm:1} and \ref{thm:2}); and (iii)~we also prove a \emph{tight} convergence bound of $\singshuf$ for strongly convex functions without individual convexity (Theorem~\ref{thm:singshuf1})---see Tables~\ref{tab:results} and \ref{tab:resultssing} for a quick comparison with other results. Since the majority of our results are on $\randshuf$, we defer our $\singshuf$ result to Section~\ref{sec:singshuf} of the appendix, to better streamline the flow of the paper.

\begin{list}{{\tiny$\bullet$}}{\leftmargin=1.8em}
\item In Theorem~\ref{thm:plconv}, we prove that if $F$ satisfies the P{\L} condition and  has a nonempty and compact solution set, and $f_i$'s are smooth, then $\randshuf$ converges at the rate $\OO{\nicefrac{\log^3(nK)}{nK^2}}$. This bound holds as soon as $K \gtrsim \kappa \log(nK)$, and they match the lower bounds up to poly-log factors.
Remarkably, Theorem~\ref{thm:plconv} improves upon the epoch requirement $K \gtrsim \kappa^2 \log(nK)$ of an existing bound \cite{nagaraj2019sgd} for $\randshuf$ on smooth strongly convex functions, \emph{without} needing convexity of $f_i$'s.

\item In Theorem~\ref{thm:quadratic}, we prove a tight upper bound on $\randshuf$ for strongly convex quadratic functions that improves the existing epoch requirement $K \gtrsim \kappa^2 \log(nK)$ of~\cite{rajput2020closing} to $K \gtrsim \kappa \max \{1, \sqrt{\frac \kappa n }\} \log(nK)$, \emph{without} assuming the $f_i$'s to be convex.
We develop a fine-grained analysis on the expectation over random permutations to overcome issues posed by noncommutativity; for instance, we prove contraction bounds for small step sizes which circumvent the need for a conjectured (now false, see~\cite{lai2020recht}) matrix AM-GM inequality of~\cite{recht2012beneath}.

\item
Under the additional assumption that the $f_i$'s are convex, we establish the same convergence rates of $\randshuf$ for smooth strongly convex functions (Theorem~\ref{thm:1}) and strongly convex quadratic functions (Theorem~\ref{thm:2}) \emph{without epoch requirements}; i.e., for all $K \geq 1$! The key to obtaining this improvement is to depart from constant step sizes analyzed in most prior works and consider varying step sizes.
To analyze such varying step sizes, we develop  a variant of Chung's lemma (Lemma~\ref{main:2}) that can handle our case where the convergence rate depends on  two parameters $n$ and $K$; this lemma may be of independent interest. Notably, our approach also removes the extra poly-logarithmic factors in the convergence rates.

\item
Finally, we provide a tight convergence analysis for $\singshuf$, again without requiring the convexity of individual component functions. Theorem~\ref{thm:singshuf1} shows that for smooth strongly convex functions, $\singshuf$ converges at the rate $\OO{\nicefrac{\log^3 (nK)}{nK^2}}$ as soon as $K \gtrsim \kappa^2 \log (nK)$. We remark that this rate matches (up to poly-log factors) the existing lower bound $\Om{\nicefrac{1}{nK^2}}$~\cite{safran2019good} proven for a \emph{subclass}, namely, strongly convex quadratic functions.

\end{list}

\vspace*{-4pt}
\section{Problem setup and notation} \label{sec:setup}
\vspace*{-4pt}
We first summarize the notation used in this paper. For a positive integer $a$, we define $[a] \defeq \{1,2,\dots, a\}$; and for integers $a, b$ satisfying $a \leq b$, we let $[a:b] \defeq \{a,a+1,\dots, b-1,b\}$.
For a vector $\vv$, $\norm{\vv}$ denotes its Euclidean norm.

Given a function $h(\vx)$, we use $\mc X_h^* \subseteq \reals^d$ to denote its solution set (the set of its global minima).
We omit the subscript $h$ when it is clear from the context.

For solving  the finite-sum optimization~\eqref{opt} with more than one component ($n\geq2$), we consider $\randshuf$ and $\singshuf$ over $K$ epochs, i.e., $K$ passes over the $n$ component functions.
The distinction between these two  methods lies in the way we shuffle the components at each epoch.
For $\randshuf$, at the beginning of the $k$-th epoch, we pick a random permutation $\sigma_k : [n] \to [n]$ and access component functions in the order $f_{\sigma_k(1)}, f_{\sigma_k(2)}, \dots, f_{\sigma_k(n)}$.
We initialize $\vx_0^1 \defeq \vx_0$, and call $\vx_i^k$ the $i$-th iterate of $k$-th epoch. Then, we update the iterate using the stochastic gradient $\nabla f_{\sigma_k(i)}$ as follows:
\begin{align}\label{update}
    \vx_{i}^k \leftarrow \vx_{i-1}^k - \eee{k}{i} \nabla f_{\sigma_k(i)} (\vx_{i-1}^k) \,,
\end{align}
where $\eee{k}{i}$ is the step size for the $i$-th iteration of the $k$-th epoch.
We start the next epoch by setting $\vx_0^{k+1} \defeq \vx_{n}^k$. For $\singshuf$, we randomly pick a permutation $\sigma : [n] \to [n]$ at the first epoch, and use the same permutation over all epochs, i.e., $\sigma_k = \sigma$ for $k \in [K]$.

Next, we introduce a standard assumption for analyzing incremental methods, extensively used in the prior works~\cite{tseng1998incremental,gurbuzbalaban2019incremental,haochen2018random,nagaraj2019sgd,rajput2020closing} (see e.g. {\cite[Assumption 3.8]{gurbuzbalaban2019incremental}}):
\begin{assumption}[Bounded iterates assumption] \label{a:1}  We say the bounded iterates assumption holds if  all the iterates $\{\xx{k}{1},\xx{k}{2},\dots,\xx{k}{n}\}_{k\geq 1}$ are uniformly bounded, i.e., stay within  some compact set.
\end{assumption}
We remark that the bounded iterates assumption is not stringent as one can enforce this assumption by explicit projections~\cite{nagaraj2019sgd} or by adopting adaptive stepsizes~\cite{tseng1998incremental} if projection is undesirable.

\paragraph{Function classes studied in this paper.}
Let $h:\reals^d \to \reals$ be a differentiable function. We say $h$ is \emph{$L$-smooth} if $h(\vy) \leq h(\vx) +\inp{\nabla h(\vx)}{\vy-\vx} + \frac{L}{2}\norm{\vy-\vx}^2$ for all $\vx,\vy\in \reals^d$. We use $C_L^1(\reals^d)$ to denote the class of differentiable and $L$-smooth functions on $\reals^d$. A function $h$ is \emph{$\mu$-strongly convex} if $h(\vy) \geq h(\vx) +\inp{\nabla h(\vx)}{\vy-\vx} + \frac{\mu}{2}\norm{\vy-\vx}^2$ for all $\vx,\vy\in \reals^d$.
Lastly, a function $h$ satisfies the \emph{$\mu$-Polyak-{\L}ojasiewicz condition} (also known as \emph{gradient dominance}) if $\frac{1}{2} \norm{\nabla h(\vx)}^2 \geq \mu(h(\vx)-h^*)$ for any $\vx \in \reals^d$, where $h^*=\min_{\vx}h(\vx)$; we say $h$ is a $\mu$-P{\L} function.

 \vspace*{-4pt}
\section{Tight convergence analysis of \randshuf~for P{\L} functions}
\label{sec:PL}
\vspace*{-4pt}
To prove fast convergence rates of $\randshuf$, we need to characterize the aggregate progress made over one epoch as a whole. A general property of without-replacement SGD is the following observation due to Nedi{\'c} and Bertsekas~\cite[Chapter 2]{nedic2001convergence}:
for an epoch $k$, assuming that the iterates $\{\xx{k}{i}\}_{i=1}^n$ stay close to $\xx{k}{0}$, the aggregate update direction will closely approximate the \emph{full} gradient at $\xx{k}{0}$, i.e.,
\begin{align} \label{obs:per}
    \sum\nolimits_{i=1}^n\g_{\sigma_k(i)} (\xx{k}{i-1})\approx \sum\nolimits_{i=1}^n\g_{\sigma_k(i)} (\xx{k}{0})= \sum\nolimits_{i=1}^n\g_{i} (\xx{k}{0}) = n\nabla F(\xx{k}{0}).
\end{align}
Making this heuristic approximation~\eqref{obs:per} rigorous, we prove the following theorem:
\begin{theorem}[P{\L} class]
\label{thm:plconv}

Assume that $F$ is $\mu$-P{\L} and its solution set $\mc X^*$ is nonempty and compact. Also, assume each $f_i \in C_L^1(\reals^d)$.

Consider $\randshuf$ for the number of epochs $K$ satisfying $K \geq 10 \kappa \log (n^{1/2}K)$, step size $\eee{k}{i} = \eta \defeq \frac{2 \log (n^{1/2} K)}{\mu n K}$, and initialization $\vx_{0}$.
Then, with probability at least $1-\delta$, the following suboptimality bound holds for some $c = O(\kappa^3)$\footnote{Throughout this paper, we adopt the convention that $\kappa = \Theta(\nicefrac{1}{\mu})$, used in prior works \cite{haochen2018random, nagaraj2019sgd}.}:
\begin{equation*}
    \min_{k \in [K+1]} F(\vx_0^k) - F^* \leq
    \frac{F(\vx_{0})-F^*}{nK^2}
    +
    \frac{c \cdot \log^2(nK) \log\frac{nK}{\delta}}{nK^2}\,.\vspace*{-5pt}
\end{equation*}
\end{theorem}
{\noindent \bf Proof:} See Section~\ref{ps:1} for a proof sketch and Section~\ref{sec:proof-thm-plconv} for the full proof.\qed

\paragraph{Optimality of convergence rate.} It is important to note that Theorem~\ref{thm:plconv} matches the lower bound $\Om{\nicefrac{1}{nK^2}}$~\cite{rajput2020closing} for strongly convex costs, up to poly-logarithmic factors. What is somewhat surprising is that our upper bound holds for a \emph{broader} class of (nonconvex) P{\L} functions compared to this lower bounds.
Since Theorem~\ref{thm:plconv} applies to subclasses of P{\L} functions, it also gives the minimax optimal rates (up to log factors) for smooth strongly convex functions (see Table~\ref{tab:results}).

Notably, Theorem~\ref{thm:plconv} improves the epoch requirement $K \gtrsim \kappa^2 \log(nK)$ of the prior work \cite{nagaraj2019sgd} to $K \gtrsim \kappa \log(n^{1/2}K)$, \emph{without} requiring the convexity of $f_i$'s. Note that in \cite{nagaraj2019sgd}, convexity is crucial in the coupling argument to achieve the tight convergence rate.

\begin{remark}[Best iterate v.s.\ last iterate]
\label{rmk:bestvslast}
Note that Theorem~\ref{thm:plconv} is a guarantee for the best iterate, not the last iterate. However, the best iterate is needed only in pathological cases where some early iterate $\xx{k}{0}$ is already too close to the optimum, so that the ``noise'' dominates the updates and makes the last iterate have worse optimality gap than $\xx{k}{0}$.
By assuming bounded iterates (Assumption~\ref{a:1}) in place of the compactness of $\mc X^*$, the convergence rate in Theorem~\ref{thm:plconv} holds for the \emph{last} iterate (see Section~\ref{sec:proof-thm-plconv-outline} for details).
Conversely, for an existing last-iterate bound (e.g., \cite{rajput2020closing}), one can prove a corresponding best-iterate bound without Assumption~\ref{a:1} if $\mc X^*$ is compact.
\end{remark}

\begin{remark}[Similar bound for $\singshuf$]
In Section~\ref{sec:singshuf}, we show a similar convergence bound $\OO{\nicefrac{\log^3(nK)}{nK^2}}$ for $\singshuf$ on smooth strongly convex functions (Theorem~\ref{thm:singshuf1}).
Interestingly, Theorems~\ref{thm:plconv} and \ref{thm:singshuf1} together demonstrate that the optimal dependences on $n$ and $K$ are identical for $\randshuf$ and $\singshuf$ on smooth strongly convex costs; in other words, for this function class, there is no additional provable gain from reshuffling in terms of the dependence on $n$ and $K$.

\end{remark}

From the high-probability bound in Theorem~\ref{thm:plconv}, we can derive a corresponding expectation bound.
\begin{corollary}[P{\L} class]
\label{cor:plconv}
Under the setting of Theorem~\ref{thm:plconv}, the following holds for some $c = O(\kappa^3)$:
\begin{equation*}
    \E \bigg[ \min_{k \in [K+1]} F(\vx_0^k)  \bigg]- F^* \leq
    \frac{3(F(\vx_{0})-F^*)}{2nK^2}
    +
    \frac{c \cdot \log^3(nK)}{nK^2}\,.
\end{equation*}
\end{corollary}

So far, we have developed the optimal convergence rate of \randshuf~for P{\L} costs, which turn out to be also optimal for smooth strongly convex costs.
However, there is one case which Theorem~\ref{thm:plconv} does not match the lower bound, namely $\randshuf$ for quadratic costs: the lower bound of $\Omega(\nicefrac{1}{(nK)^2} + \nicefrac{1}{nK^3})$ is proved in \cite{safran2019good}.
Although Rajput et al.~\cite{rajput2020closing} actually obtain this rate, they assume the convexity of each component.
In light of Theorem~\ref{thm:plconv}, it is therefore natural to ask if we can close the gap without assuming convexity of each component.

\vspace*{-3pt}
\section{Tight bound on \randshuf~for quadratic functions}
\label{sec:quad}
\vspace*{-3pt}

We prove below a tight bound for $\randshuf$ on quadratics without the convexity of $f_i$'s. For simplicity, we assume (without loss) that the global optimum of $F$  is achieved at the origin.
\begin{theorem}[Quadratic costs]
\label{thm:quadratic}
Assume that $F(\vx) \defeq \frac{1}{n}\sum_{i=1}^n f_i(\vx) = \half \vx^T \mA \vx$ and $F$ is $\mu$-strongly convex. Let $f_i(\vx)\defeq \half \vx^T \mA_i \vx + \vb_i^T \vx$ and $f_i \in C_L^1(\reals^d)$.
Consider $\randshuf$ for the number of epochs $K$ satisfying $K \geq \frac{32}{3} \kappa \max \{1, \sqrt{\frac \kappa n} \} \log (nK)$, step size $\eee{k}{i} = \eta \defeq \frac{2\log (nK)}{\mu n K}$, and initialization $\vx_0$. Then the following bound holds for some $c_1 = O(\kappa^4)$ and $c_2 = O(\kappa^4)$:
\begin{align*}
    \E\left [F(\vx_0^{K+1}) \right] - F^*
    &\leq \frac{2 L\norm{\vx_0-\vx^*}^2}{n^2 K^2}
    + \frac{c_1 \cdot \log^2(nK)}{n^2 K^2} + \frac{c_2 \cdot \log^4(nK)}{nK^3}\,.
\end{align*}
\end{theorem}
{\noindent \bf Proof:} See  Section~\ref{ps:2} for a proof sketch and Section~\ref{sec:proof-thm-quadratic} for the full proof. \qed

\paragraph{Improvements.}
Theorem~\ref{thm:quadratic} improves the prior result~\cite{rajput2020closing} in many ways.
Most importantly, Theorem~\ref{thm:quadratic} does not require $f_i$'s to be convex, an assumption exploited in~\cite{rajput2020closing} for their coupling argument.
Moreover, Theorem~\ref{thm:quadratic} imposes a \emph{milder} epoch requirement: it only assumes $K \geq \frac{32}{3} \kappa \max \{1, \sqrt{\frac \kappa n} \} \log (nK)$,  which is better than $K \geq 128 \kappa^2 \log (nK)$ of \cite{rajput2020closing}.
As long as $\kappa \leq n$, our epoch requirement is $K \gtrsim \kappa \log(nK)$, matching that of the univariate case~\cite{safran2019good}. Lastly, unlike~\cite{rajput2020closing}, Theorem~\ref{thm:quadratic} does not rely on the bounded iterates assumption.

\begin{remark}[Tail averaging tricks] \label{rmk:tail}
Following \cite{nagaraj2019sgd}, we can also obtain a guarantee for the tail average of the iterates $\vx_0^{\lceil K/2 \rceil}, \dots, \vx_0^{K}$, which improves the constants appearing in the bound by a factor of $\kappa$. Due to space limitation, the statement and the proof of this improvement are deferred to Section~\ref{sec:proof-thm-quadratic2}.
\end{remark}

Thus far, we have established the optimal convergence rates of \randshuf~for P{\L} costs, strongly convex costs, and quadratic costs \emph{without} assuming the convexity of individual components, an assumption crucial to the analysis of prior arts~\cite{nagaraj2019sgd,rajput2020closing}. Due to our results, it may seem that there is no additional gain from the convexity of the $f_i$'s.  \emph{Is it really the case?}

\vspace*{-4pt}
\section{Eliminating epoch requirements with varying step sizes}
\label{sec:varyingstep}
\vspace*{-3pt}

In this section, we show that the convexity of $f_i$'s \emph{does} lead to gains. In particular, we show how this convexity helps one remove the epoch requirements as well as extra poly-log terms in previous convergence bounds~\cite{haochen2018random,nagaraj2019sgd,rajput2020closing}. The main technical distinction of this sharper result is to depart from constant step sizes and consider varying step sizes. We begin with the strongly convex case:
\begin{theorem}[Strongly convex costs]
\label{thm:1}

Assume that $F$ is $\mu$-strongly convex, and each $f_i$ is convex and $f_i \in C_L^1(\reals^d)$. Assume that the bounded iterates assumption (Assumption~\ref{a:1}) holds.
For any constant $\alpha>2$, let $\ini:= \alpha \cdot \kappa$, and consider the step sizes $\eee{1}{i} =  \frac{2\alpha/\mm}{\ini+i}$ for $i \in [n]$, and $\eee{k}{i}=  \frac{2\alpha/\mm}{\ini+nk}$ for $k \in [2:K]$ and $i \in [n]$.
Then, for any $K\geq 1$, the following convergence bound holds for \randshuf~with step sizes $\eee{k}{i}$, initialization $\vx_0$, and some  $c_1=O(\kappa^4)$  and $c_2=O(\kappa^\alpha)$:
\begin{align*}
     \E \left [ F(\vx_0^{K+1}) \right] - F^*  \leq  \frac{c_1 \cdot n}{(\ini+nK)^2}   +\frac{c_2\cdot  \norm{\vx_{0}-\xs}^2}{(\ini+nK)^{\alpha}}   \,.\vspace*{-3pt}
 \end{align*}
\end{theorem}
{\noindent \bf Proof:} See  Section~\ref{ps:3} for a proof sketch and Section~\ref{app:pf1} for the full proof. \qed

\paragraph{Removing epoch requirements.}
The most important feature of Theorem~\ref{thm:1} is that its rate holds for all $K\geq 1$. This is in stark contrast with the existing minimax optimal result~\cite{nagaraj2019sgd} which requires $K\gtrsim \kappa^2 \log(nK)$. Moreover, the dependency of the leading constant $c_1$ on $\kappa$ is identical with~\cite{nagaraj2019sgd}\footnote{Although the leading constant in \cite[Theorem 1]{nagaraj2019sgd} actually reads $\OO{\kappa^3}$, it is important to note that the result is for the tail-averaged iterate. For the last iterate, one can see that their leading constant becomes $\OO{\kappa^4}$.}.

\paragraph{Removing extra poly-log factors.}
Another notable feature of our bound is that it is not beset with extra poly-log factors appearing in the previous minimax optimal result~\cite{nagaraj2019sgd}, and thereby it closes the poly-log gap between the lower bound~\cite{rajput2020closing}.

With a similar technique, we can also prove the tight convergence rates for the case of quadratic $F$:
\begin{theorem}[Quadratic costs]
\label{thm:2}
Under the setting of Theorem~\ref{thm:1}, we additionally assume that $F$ is quadratic.
For  any constant $\alpha>4$, consider the same varying step sizes as in Theorem~\ref{thm:1}.
Then, for any $K\geq 1$, the following convergence bound holds for \randshuf~with step sizes $\eee{k}{i}$, initialization $\vx_0$, and some $c_1 =O(\kappa^4)$, $c_2=O(\kappa^6)$ and $c_3=O(\kappa^\alpha)$:
\begin{align*}
     \E \left [ F(\vx_0^{K+1})  \right] - F^* \leq   \frac{c_1}{(\ini+nK)^2} + \frac{c_2 \cdot n^2}{(\ini+nK)^3}    +\frac{c_3\cdot  \norm{\vx_{0}-\xs}^2}{(\ini+nK)^{\alpha}}   \,.
 \end{align*}
\end{theorem} \vspace{-2pt}
{\noindent \bf Proof:} Similar to Theorem~\ref{thm:1}. See Section~\ref{app:pf2}. \qed

\begin{remark}[Tightness of bounds]
\label{rmk:lowerbound}
We believe that the upper bounds developed in this section are likely tight, though we note that this tightness is not yet guaranteed because the existing lower bounds are all developed under the assumption of constant step sizes. Extension of the lower bounds to varying step sizes would be an interesting future research direction.
\end{remark}

\vspace*{-.3cm}
\section{Proof sketches}\label{sec:pfsk}
\vspace*{-6pt}
\subsection{Proof sketch of Theorem~\ref{thm:plconv}}
\vspace*{-3pt}
\label{ps:1}
As we mentioned in Section~\ref{sec:PL}, the key to obtaining a faster rate is to capture the per-epoch property \eqref{obs:per}.
By decomposing $\g_{\sigma_k(i)} (\xx{k}{i-1})$ into ``signal'' $\g_{\sigma_k(i)} (\xx{k}{0})$ and ``noise,'' we develop the following approximate version of \eqref{obs:per} by carefully expanding the updates \eqref{update} over the $k$-th epoch:
\begin{align}
    \vx_0^{k+1}
    &= \vx_0^k - \eta n \nabla F(\vx_0^k)  +\eta^2 \vr_k\,,
    \tag{\ref{obs:per}${}^\prime$} \label{obs:perprime}
\end{align}
where the error term $\vr_k$ is defined as the sum $\sum\nolimits_{i=1}^{n-1} \mM_i  \sum\nolimits_{j=1}^i \nabla f_{\sigma_k(j)}(\xx{k}{0})$ for some matrices $\mM_i$'s of bounded spectral norm.
Note that without the term $\eta^2 \vr_k$, \eqref{obs:perprime} is precisely equal to gradient descent update with the cost function $F$.
By smoothness of $F$, we have
\begin{equation}
\label{eq:smthnessbnd-sketch}
\begin{aligned}[b]
    F(\vx_0^{k+1}) - F(\vx_0^{k})
    &\leq \< \nabla F(\vx_0^k), \vx_0^{k+1} - \vx_0^k \> + \tfrac{L}{2} \norm{\vx_0^{k+1} - \vx_0^k}^2\\
    &\leq (-\eta n + \eta^2 n^2 L) \norm{\nabla F(\vx_0^k)}^2
    + \eta^2 \norm{\nabla F(\vx_0^k)} \norm{\vr_k}
    + L \eta^4 \norm{\vr_k}^2.
\end{aligned}
\end{equation}
Therefore, it is important to control the norm $\|\vr_k\|$ of the aggregate error term.
We seek sharp bounds on $\norm{\vr_k}$ but cannot invoke a standard concentration inequality as the gradients are sampled \emph{without-replacement}. We overcome this difficulty by applying a vector-valued version of Hoeffding-Serfling\footnote{The scalar-valued version of Hoeffding-Serfling inequality \cite{bardenet2015concentration} was also used in \cite{safran2019good}.} inequality \cite{schneider2016probability} to the partial sums $\sum\nolimits_{j=1}^i \nabla f_{\sigma_k(j)}(\xx{k}{0})$. For each of them, we have
\begin{align*}
  \Bigl\lVert\sum\nolimits_{j=1}^i \nabla f_{\sigma_k(j)}(\xx{k}{0})\Bigr\rVert
  &\leq \Bigl\lVert{\sum\nolimits_{j=1}^i \nabla f_{\sigma_k(j)}(\xx{k}{0})- i \nabla F(\xx{k}{0})}\Bigr\rVert + i\norm{\nabla F(\xx{k}{0})} \lesssim \sqrt{i} + i\norm{\nabla F(\xx{k}{0})},
\end{align*}

with high probability. Applying the union bound and summing over all $i \in [n-1]$, we obtain
\begin{align}\label{bd:norm}
    \norm{\vr_k} \lesssim   n^{3/2}+ n^2 \norm{\nabla F(\vx_0^k)}\,.
\end{align}
Substituting this bound \eqref{bd:norm} into \eqref{eq:smthnessbnd-sketch}, rearranging the terms, and applying the P{\L} inequality on $\norms{\nabla F(\xx{k}{0})}^2$, we obtain the following per-epoch progress bound, which holds for $\eta \leq \frac{1}{5nL}$:
\begin{align} \label{per:epoch}
  F(\vx_0^{k+1}) - F^* \lesssim (1-\eta n \mu) (F(\vx_0^{k}) - F^*)
  +  \eta^3 n^2.
\end{align}

Applying \eqref{per:epoch} over all epochs and substituting $\eta = \frac{2 \log (n^{1/2} K)}{\mu n K}$, the convergence rate follows. Substituting $\eta$ to $\eta \leq \frac{1}{5nL}$ gives the epoch requirement. See Section~\ref{sec:proof-thm-plconv} for details. \qed

\vspace{-5pt}
\subsection{Proof sketch of Theorem~\ref{thm:quadratic}}
\vspace*{-3pt}
\label{ps:2}
The proof builds on the techniques from \cite{safran2019good} for one-dimensional quadratic functions.

In place of the per-epoch analysis in Theorem~\ref{thm:plconv}, we recursively apply \eqref{update} all the way from the initial iterate $\xx{1}{0}$ to the last iterate $\xx{K+1}{0}$ and directly bound $\E[\norms{\xx{K+1}{0} -\vx^*}^2]$.
Indeed, as pointed out by Safran and Shamir~\cite{safran2019good}, the main technical difficulty in extending this approach to higher dimensions comes from the noncommutativity of matrix multiplication which, for example, results in the absence of the matrix AM-GM inequality \cite{recht2012beneath, lai2020recht}.
Through a fine-grained analysis of the expectation over uniform permutation, we overcome the problems posed by the noncommutativity and develop a tight upper bound.
For instance, we prove the following contraction bound (Lemma~\ref{lem:thm1-term1}) as an approximate alternative to the recently disproved matrix AM-GM inequality \cite{lai2020recht}, which holds for small enough $\eta$:
\begin{align} \label{ineq:amgm}
    \norm{\E \left [ \prod\nolimits_{t=1}^n (1-\eta \mA_{\sigma_k(t)}) \prod\nolimits_{t=n}^1 (1-\eta \mA_{\sigma_k(t)}) \right ]} \leq 1-\eta n \mu\,.
\end{align}
Although \eqref{ineq:amgm} only holds for small $\eta$ and is looser than the AM-GM inequality, it is remarkable that this bound holds for \emph{any} $n \geq 2$, especially given the result \cite{lai2020recht} that the matrix AM-GM inequality conjecture breaks as soon as $n = 5$.

Please refer to Section~\ref{sec:proof-thm-quadratic} for the full proof.   \qed

\vspace*{-3pt}
\subsection{Proof sketch of Theorem~\ref{thm:1}}
\vspace*{-3pt}
\label{ps:3}
First, due to the convexity of $f_i$'s, it turns out that  not only one can characterize the per-epoch progress bound akin to \eqref{per:epoch}, but also the progress made by each iteration (Proposition~\ref{per:0}).
This per-iteration progress bound is due to  \cite{nagaraj2019sgd}, which uses coupling arguments to demonstrate that with convexity, \randshuf~makes progress on par with \sgd.

Having such a finer control over the progress made by \randshuf, one can imagine that the varying step size choice takes  \emph{aggressive} steps in the initial epochs which in turn results in a warm start.
Despite this simple intuition, it turns out that the rigorous analysis is non-trivial.
In fact, there is a technical tool called \emph{non-asymptotic Chung's lemma}~\cite{chung1954stochastic} for turning individual progress made at each iteration/epoch into a global convergence bound.
However, as we illustrate in Section~\ref{sec:fail}, the non-asymptotic Chung's lemma does not yield the desired convergence rate; the main issue is that for  \randshuf, the convergence bound needs to capture the right order for \emph{two} parameters $n$ and $K$.
To overcome such a limitation, we develop a variant of Chung's lemma (Lemma~\ref{main:2}) which gives rise to the bound that captures the right order for both $n$ and $K$. See Section~\ref{app:varying} for the full proof. \qed

\vspace*{-3pt}
\section{Conclusion and future work}
\vspace*{-3pt}
Motivated by some limitations in the previous efforts, this paper establishes optimal convergence rates of $\randshuf$ and $\singshuf$.
Notably, our optimal convergence rates are obtained without relying on convex component functions, which are exploited in the prior works~\cite{nagaraj2019sgd,rajput2020closing}.
We also show that exploiting the convexity of component functions allows for further improvements for $\randshuf$.
By adopting time-varying step sizes and applying a variant of Chung's lemma, we develop sharper convergence bounds that do not come with any epoch requirement and extra poly-log factors.
We conclude this paper with several interesting open questions:\vspace{-5pt}
\begin{list}{{\tiny$\bullet$}}{\leftmargin=1.8em}
\setlength{\itemsep}{1pt}
\item (\emph{Extending lower bounds}) As noted in Remark~\ref{rmk:lowerbound}, all tight lower bounds known to date hold for constant step sizes and last iterates. It would be interesting to extend these bounds for more general settings, e.g., varying step size and arbitrary linear combination of iterates.
\item (\emph{Optimal rates for Lipschitz Hessian class}) Currently, there is a gap between the lower and upper bounds of $\randshuf$ for the smooth, strongly convex costs with the Lipschitz Hessian assumption: The best known lower bound is $\Om{\nicefrac{1}{(nK)^2} +\nicefrac{1}{nK^3}}$~\cite{safran2019good}, while the best known upper bounds are $\OO{\nicefrac{1}{nK^2}}$ (\cite{nagaraj2019sgd} and ours) and $\OO{\nicefrac{1}{(nK)^2}+\nicefrac{1}{K^3}}$ \cite{haochen2018random}.
Closing this gap would be of interest.
\item (\emph{Other cost functions})  It is also worthwhile to investigate if  without-replacement SGD achieves superior convergence rates over $\sgd$ for other classes of convex or nonconvex functions.
\item (\emph{Removing epoch requirements}) Our varying step size technique only works under the additional assumption that $f_i$'s are convex (Section~\ref{sec:varyingstep}). It would be interesting to see if such improvements can be made without relying on the convexity assumption, or for more general functions.
\item (\emph{Superiority of without-replacement for the first epoch}) Is without-replacement SGD faster than $\sgd$ even during the first epoch? It is demonstrated in \cite[Section 7.3]{haochen2018random} that for a special class of cost functions, this is indeed true.
However, even for quadratic functions, showing this is closely tied to the matrix AM-GM inequality~\cite{recht2012beneath}, which was recently proven to be false \cite{lai2020recht}.
\end{list}

\section*{Acknowledgements}
All authors acknowledge a support from NSF CAREER grant Number 1846088.
CY also acknowledges Korea Foundation for Advanced Studies for their support.
KA acknowledges Kwanjeong Educational Foundation for their support.
The authors appreciate Itay Safran and Ohad Shamir for catching an error in an initial claim about $\singshuf$, which has been corrected and updated in this revised version.

\bibliographystyle{plainnat}


TITLE: $f\colon B(0,1)\rightarrow\mathbb{C}$ continuous and $\int f\,dz=0$ for every circle $|z|=r$ implies $f$ is analytic
QUESTION [1 upvotes]: Is the following statement true?

Statement : Let $f\colon B(0,1)\rightarrow\mathbb{C}$ be a continuous mapping such that for every $r\in(0,1)$
$$
  \int_{|z|=r} f(z)\,dz=0
  ,
$$
then $f$ is analytic on $B(0,1)$.

Here $B(0,1)$ denotes the unit ball $\{z\in\mathbb{C}\colon\ |z|<1\}$.
I tried using an analogue of Morera's Theorem (*) proof in the following way:
Let $z\in B(0,1)$ and define the curve $\gamma_z$ as

if $\mathrm{Re}(z)>0$ or $\mathrm{Re}(z)<0$ ($w$ on image above). Note that if $z=iy$ with $y<0$, then we have two different curves approaching $z$.
Consider $F\colon B(0,1)\rightarrow\mathbb{C}$ defined by
$$
  \int_{\gamma_z} f(\zeta)\,d\zeta
  .
$$
Even when $z=iy$ with $y<0$, $F$ is well defined since the integral of $f$ over such circle is zero. I want to prove that $F'=f$ but I don't even know if that's possible... Is the statement above even true?

(*) Morera's Theorem states that if $f$ is a continuous function which satisfies $\int_{\partial\triangle}f=0$ for every triangle contained in $f$'s domain, then $f$ is analytic. To prove it one construct's a function $F$ such that $F'=f$...

Any help is appreciated, thanks!

REPLY [1 votes]: Your condition holds for every $f(z)$ satisfying $f(-z) = f(z)$, so it's not hard to find counterexamples that aren't analytic, such as $f(z) = |z|$.