text:
\begin{document}

\maketitle

\begin{abstract}
Stochastic descent methods (of the gradient and mirror varieties) have become increasingly popular in optimization. In fact, it is now widely recognized that the success of deep learning is not only due to the special deep architecture of the models, but also due to the behavior of the stochastic descent methods used, which play a key role in reaching ``good'' solutions that generalize well to unseen data. In an attempt to shed some light on why this is the case, we revisit some minimax properties of stochastic gradient descent (SGD) for the square loss of linear models---originally developed in the 1990's---and extend them to \emph{general} stochastic mirror descent (SMD) algorithms for \emph{general} loss functions and \emph{nonlinear} models.
In particular, we show that there is a fundamental identity which holds for SMD (and SGD) under very general conditions, and which implies the minimax optimality of SMD (and SGD) for sufficiently small step size, and for a general class of loss functions and general nonlinear models.
We further show that this identity can be used to naturally establish other properties of SMD (and SGD), namely convergence and \emph{implicit regularization} for over-parameterized linear models (in what is now being called the ``interpolating regime''), some of which have been shown in certain cases in prior literature. We also argue how this identity can be used in the so-called ``highly over-parameterized'' nonlinear setting (where the number of parameters far exceeds the number of data points) to provide insights into why SMD (and SGD) may have similar convergence and implicit regularization properties for deep learning.
\end{abstract}

\section{Introduction}

Deep learning has proven to be extremely successful in a wide variety of tasks \citep{krizhevsky2012imagenet,lecun2015deep,mnih2015human,silver2016mastering,wu2016google}. Despite its tremendous success, the reasons behind the good generalization properties of these methods to unseen data is not fully understood (and, arguably, remains somewhat of a mystery to this day). Initially, this success was mostly attributed to the special deep architecture of these models. However, in the past few years, it has been widely noted that the architecture is only part of the story, and, in fact, the optimization algorithms used to train these models, typically stochastic gradient descent (SGD) and its variants, play a key role in learning parameters that generalize well.

In particular, it has been observed that since these deep models are \emph{highly over-parameterized}, they have a lot of capacity, and can fit to virtually any (even random) set of data points \citep{zhang2016understanding}. In other words, highly over-parameterized models can ``interpolate'' the data, so much so that this regime has been called the ``interpolating regime'' \citep{mababe2017}. In fact, on a given dataset, the loss function often has (uncountably infinitely) many \emph{global} minima, which can have drastically different generalization properties, and it is not hard to construct ``trivial'' global minima that do not generalize. Which minimum among all the possible minima we pick in practice is determined by the optimization algorithm that we use for training the model.
Even though it may seem at first that, because of the non-convexity of the loss function, the stochastic descent algorithms may get stuck in local minima or saddle points, in practice they almost always achieve a global minimum \citep{kawaguchi2016deep,zhang2016understanding,lee2016gradient}, which perhaps can also be justified by the fact that these models are highly over-parameterized. What is even more interesting is that not only do these stochastic descent algorithms converge to global minima, but they converge to ``special'' ones that generalize well, even in the absence of any explicit regularization or early stopping \citep{zhang2016understanding}. Furthermore, it has been observed that even among the common optimization algorithms, namely SGD or its variants (AdaGrad \citep{duchi2011adaptive}, RMSProp \citep{tieleman2012lecture}, Adam \citep{kingma2014adam}, etc.), there is a discrepancy in the solutions achieved by different algorithms and their generalization capabilities \citep{wilson2017marginal}, which again highlights the important role of the optimization algorithm in generalization.

There have been many attempts in recent years to explain the behavior and properties of these stochastic optimization algorithms, and many interesting insights have been obtained \citep{achille2017emergence,chaudhari2018stochastic,shwartz2017opening,soltanolkotabi2017theoretical}. In particular, it has been argued that the optimization algorithms perform an \emph{implicit regularization} \citep{neyshabur2017geometry,ma2017implicit,gunasekar2017implicit,gunasekar2018characterizing,soudry2017implicit,gunasekar2018implicit} while optimizing the loss function, which is perhaps why the solution generalizes well.
Despite this recent progress, most results explaining the behavior of the optimization algorithm, even for SGD, are limited to linear or very simplistic models. Therefore, a general characterization of the behavior of stochastic descent algorithms for more general models would be of great interest.

\subsection{Our Contribution}
In this paper, we present an alternative explanation of the behavior of SGD, and more generally, the stochastic mirror descent (SMD) family of algorithms, which includes SGD as a special case. We do so by obtaining a fundamental identity for such algorithms (see Lemmas~\ref{lem:sum} and \ref{lem:sum_SMD}). Using these identities, we show that for general nonlinear models and general loss functions, when the step size is sufficiently small, SMD (and therefore also SGD) is the optimal solution of a certain minimax filtering (or online learning) problem. The minimax formulation is inspired by, and rooted, in $H^{\infty}$ filtering theory, which was originally developed in the 1990's in the context of robust control theory \citep{hassibi1999indefinite,simon2006optimal,hassibi1996h}, and we generalize several results from this literature, e.g., \citep{hassibi1994hoo,kivinen2006p}. Furthermore, we show that many properties recently proven in the learning/optimization literature, such as the implicit regularization of SMD in the over-parameterized linear case---when convergence happens---\citep{gunasekar2018characterizing}, naturally follow from this theory. The theory also allows us to establish new results, such as the convergence (in a deterministic sense) of SMD in the over-parameterized linear case. We also use the theory developed in this paper to provide some speculative arguments into why SMD (and SGD) may have similar convergence and implicit regularization properties in the so-called ``highly over-parameterized'' nonlinear setting (where the number of parameters far exceeds the number of data points) common to deep learning.

In an attempt to make the paper easier to follow, we first describe the main ideas and results in a simpler setting, namely, SGD on the square loss of linear models, in Section~\ref{sec:warmup}, and mention the connections to $H^{\infty}$ theory. The full results, for SMD on a general class of loss functions and for general nonlinear models, are presented in Section~\ref{sec:SMD}. We demonstrate some implications of this theory, such as deterministic convergence and implicit regularization, in Section~\ref{sec:implications}, and we finally conclude with some remarks in Section~\ref{sec:conclusion}. Most of the formal proofs are relegated to the appendix.

\section{Preliminaries}

Denote the training dataset by $\{(x_i,y_i): i=1,\dots,n\}$, where $x_i\in\mathbb{R}^d$ are the inputs, and $y_i\in\mathbb{R}$ are the labels. We assume that the data is generated through a (possibly nonlinear) model $f_i(w)=f(x_i,w)$ with some parameter vector $w\in\mathbb{R}^m$, plus some noise $v_i$, i.e., $y_i=f(x_i,w)+v_i$ for $i=1,\dots,n$. The noise can be due to actual measurement error, or it can be due to modeling error (if the model $f(x_i,\cdot)$ is not rich enough to fully represent the data), or it can be a combination of both. As a result, we do not make any assumptions on the noise (such as stationarity, whiteness, Gaussianity, etc.).

Since typical deep models have a lot of capacity and are highly over-parameterized, we are particularly interested in the over-parameterized (so-caled interpolating) regime, i.e., when $m>n$. In this case, there are many parameter vectors $w$ (in fact, uncountably infinitely many) that are consistent with the observations. We denote the set of these parameter vectors by
\begin{equation}
\mathcal{W} = \left\{w\in\mathbb{R}^m\mid y_i=f(x_i,w),\ i=1,\dots,n\right\}.
\end{equation}
(Note the absence of the noise term, since in this regime we can fully interpolate the data.) The set $\mathcal{W}$ is typically an ($m-n$)-dimensional manifold and depends only on the training data $\{(x_i,y_i): i=1,\dots,n\}$ and nonlinear model $f(\cdot,\cdot)$.

The total loss on the training set (empirical risk) can be denoted by
$L(w)=\sum_{i=1}^n L_i(w)$, where $L_i(\cdot)$ is the loss on the individual data point $i$. We assume that the loss $L_i(\cdot)$ depends only on the residual, i.e., the difference between the prediction and the true label. In other words,
\begin{equation}
L_i(w) = l(y_i-f(x_i,w)) ,
\end{equation}
where $l(\cdot)$ can be any nonnegative differentiable function with $l(0)=0$. Typical examples of $l(\cdot)$ include square ($l_2$) loss, Huber loss, etc.
We remark that, in the interpolating regime, every parameter vector in the set $\mathcal{W}$ renders each individual loss zero, i.e., $L_i(w) = 0$, for all $w\in\mathcal{W}$.

\section{Warm-up: Revisiting SGD on Square Loss of Linear Models}\label{sec:warmup}

In this section, we describe the main ideas and results in a simple setting, i.e., stochastic gradient descent (SGD) for the square loss of a linear model, and we revisit some of the results from $H^{\infty}$ theory \citep{hassibi1999indefinite,simon2006optimal}. In this case, the data model is $y_i = x_i^Tw+v_i$, $i=1,\ldots, n$ (where there is no assumption on $v_i$) and the loss function is $L_i(w) = \frac{1}{2}(y_i-x_i^Tw)^2$.

Assuming the data is indexed randomly, the SGD updates are defined as $w_i = w_{i-1}-\eta\nabla L_i(w_{i-1})$, where $\eta>0$ is the step size or learning rate.\footnote{For the sake of simplicity of presentation, we present the results for constant step size. We show in the appendix that all the results extend to the case of time-varying step-size.} The update in this case can be expressed as
\begin{equation}\label{eq:SGD}
w_i = w_{i-1}+\eta \left(y_i-x_i^Tw_{i-1}\right)x_i ,
\end{equation}
for $i\geq 1$ (for $i>n$, we can either cycle through the data, or select them at random).

\begin{remark}
We should point out that, when the step size $\eta$ is fixed, the SGD recursions have no hope of converging, unless there exists a weight vector $w$ which perfectly interpolates the data $\{(x_i,y_i): i=1,\dots,n\}$. The reason being that, if this is not the case, for any estimated weight vector in SGD there will exist at least one data point that has a nonzero instantaneous gradient and that will  therefore move the estimate by a non-vanishing amount.\footnote{Of course, one may get convergence by having a vanishing step size $\eta_i\rightarrow 0$. However, in this case, convergence is not surprising---since, effectively, after a while the weights are no longer being updated---and the more interesting question is ``what'' the recursion converges to.} It is for this reason that the results on the convergence of SGD and SMD (Sections~\ref{sec:warmup_convergence} and \ref{sec:implications}) pertain to the interpolating regime.
\end{remark}

\subsection{Conservation of Uncertainty}

Prior to the $i$-th step of any optimization algorithm, we have two sources of uncertainty: our uncertainty about the unknown parameter vector $w$, which we can represent by $w-w_{i-1}$, and our uncertainty about the $i$-th data point $(x_i,y_i)$, which we can represent by the noise $v_i$. After the $i$-th step, the uncertainty about $w$ is transformed to $w-w_i$. But what about the uncertainty in $v_i$? What is it transformed to? In fact, we will view any optimization algorithm as one which redistributes the uncertainties at time $i-1$ to new uncertainties at time $i$. The two uncertainties, or error terms, we will consider are $e_i$ and $e_{p,i}$, defined as follows.
\begin{equation}
e_i := y_i-x_i^Tw_{i-1} , \text{ and } e_{p,i} := x_i^Tw-x_i^Tw_{i-1} .
\end{equation}

$e_i$ is often referred to as the {\em innvovations} and is the error in predicting $y_i$, given the input $x_i$. $e_{p,i}$ is sometimes called the {\em prediction error}, since it is the error in predicting the noiseless output $x_i^Tw$, i.e., in predicting what the best output of the model is. In the absence of noise, $e_i$ and $e_{p,i}$ coincide.

One can show that SGD transforms the uncertainties in the fashion specified by the following lemma, which was first noted in \citep{hassibi1996h}.
\begin{lemma}\label{lem:equality}
For any parameter $w$ and noise values $\{v_i\}$ that satisfy $y_i =x_i^Tw+v_i$ for $i=1,\dots,n$, and for any step size $\eta>0$, the following relation holds for the SGD iterates $\{w_i\}$ given in Eq.~\eqref{eq:SGD}
\begin{equation}\label{eq:equality}
\|w-w_{i-1}\|^2 + \eta v_i^2 = \|w-w_i\|^2 + \eta\left(1-\eta\|x_i\|^2\right)e_i^2 + \eta e_{p,i}^2,\quad \forall i\geq 1.
\end{equation}
\end{lemma}

As illustrated in Figure~\ref{fig:SGD}, this means that each step of SGD can be thought of as a lossless transformation of the input uncertainties to the output uncertainties, with the specified coefficients.

Once one knows this result, proving it is straightforward. To see that, note that we can write $v_i=y_i-x_i^Tw$ as $v_i=(y_i-x_i^Tw_{i-1})-(x_i^Tw-x_i^Tw_{i-1})$. Multiplying both sides by $\sqrt{\eta}$, we have
\begin{equation}\label{eq:SGDequality_proof_eq1}
\sqrt{\eta}v_i=\sqrt{\eta}(y_i-x_i^Tw_{i-1})-\sqrt{\eta}(x_i^Tw-x_i^Tw_{i-1}) .
\end{equation}

On the other hand, subtracting both sides of the update rule~\eqref{eq:SGD} from $w$ yields
\begin{equation}\label{eq:SGDequality_proof_eq2}
w-w_i = (w-w_{i-1})-\eta\left(y_i-x_i^Tw_{i-1}\right)x_i.
\end{equation}
Squaring both sides of \eqref{eq:SGDequality_proof_eq1} and \eqref{eq:SGDequality_proof_eq2}, and subtracting the results leads to Equation~\eqref{eq:equality}.

A nice property of Equation~\eqref{eq:equality} is that, if we sum over all $i=1,\dots,T$, the terms $\|w-w_i\|^2$ and $\|w-w_{i-1}\|^2$ on different sides cancel out telescopically, leading to the following important lemma.
\begin{lemma}\label{lem:sum}
For any parameter $w$ and noise values $\{v_i\}$ that satisfy $y_i =x_i^Tw+v_i$ for $i=1,\dots,n$, any initialization $w_0$, any step size $\eta>0$, and any number of steps $T\geq 1$, the following relation holds for the SGD iterates $\{w_i\}$ given in Eq.~\eqref{eq:SGD}
\begin{empheq}[box=\fbox]{equation}\label{eq:sum}
\|w-w_{0}\|^2 + \eta \sum_{i=1}^T v_i^2 = \|w-w_T\|^2 + \eta\sum_{i=1}^T\left(1-\eta\|x_i\|^2\right)e_i^2 + \eta \sum_{i=1}^Te_{p,i}^2 .
\end{empheq}
\end{lemma}
As we will show next, this identity captures most properties of SGD, and implies several important results in a very transparent fashion. For this reason, this relation can be viewed as a ``fundamental identity'' for SGD.

\begin{figure}[t]
\begin{center}
\includegraphics[width=0.6\columnwidth]{SGD.png}
\end{center}
\caption{Illustration of Lemma~\ref{lem:equality}. Each step of SGD can be viewed as a transformation of the uncertainties with the right coefficients.}\label{fig:SGD}
\end{figure}

\subsection{Minimax Optimality of SGD}
For a given horizon $T$, consider the following minimax problem:
\begin{equation}
\min_{\{w_i\}}~\max_{w,\{v_i\}}~\frac{\|w-w_T\|^2+\eta\sum_{i=1}^Te_{p,i}^2}{\|w-w_0\|^2+\eta\sum_{i=1}^Tv_i^2} .
\label{hinf}
\end{equation}
This minimax problem is motivated by the theory of $H^\infty$ control and estimation \citep{francis,hassibi1999indefinite,basarbernhard}. The denominator of the cost function can be interpreted as the {\em energy of the uncertainties} and consists of two terms, $\|w-w_0\|^2$, the energy of our uncertainty of the unknown weight vector at the beginning of learning when we have not yet observed the data, and $\sum_{i=1}^Tv_i^2$, the energy of the uncertainty in the measurements. The numerator denotes the energy of the estimation errors in an {\em online setting}. The first term, $\|w-w_T\|^2$, is the energy of our uncertainty of the unknown weight vector after we have observed $T$ data points, and the second term, $\sum_{i=1}^Te_{p,i}^2 = \sum_{i=1}^T(x_i^Tw-x_i^Tw_{i-1})^2$, is the energy of the prediction error, i.e., how well we can predict the true uncorrupted output $x_i^Tw$ using measurements up to time $i-1$. The parameter $\eta$ weighs the two energy terms relative to each other. In this minimax problem, nature has access to the unknown weight vector $w$ and the noise sequence $v_i$ and would like to maximize the energy gain from the uncertainties to prediction errors (so that the estimator behaves poorly), whereas the estimator attempts to minimize the energy gain. Such an estimator is referred to as $H^\infty$-optimal and is robust because it safeguards against the worst-case noise. It is also conservative---for the exact same reason.\footnote{The setting described is somewhat similar to the setting of online learning, where one considers the relative performance of an online learner who needs to predict, compared to a clairvoyant one who has access to the entire data set \citep{onlineschwatrz,onlinehazan}. In online learning, the relative performance is described as a difference, rather than as a ratio in $H^\infty$ theory, and is referred to as {\em regret}.}

\begin{theorem} \label{thm:SGDminimax}
For any initialization $w_0$, any
step size
$0<\eta\leq\min_i\frac{1}{\|x_i\|^2}$, and any number of steps $T\geq 1$, the stochastic gradient descent iterates $\{w_i\}$ given in Eq.~\eqref{eq:SGD} are the optimal solution to the minimax problem (\ref{hinf}). Furthermore, the optimal minimax value (achieved by SGD) is $1$.
\end{theorem}

This theorem explains the observed robustness and conservatism of SGD. Despite the conservativeness of safeguarding against the worst-case disturbance, this choice may actually be the rational thing to do in situations where we do not have much knowledge about the disturbances, which is the case in many machine learning tasks.

Theorem~\ref{thm:SGDminimax} holds for any horizon $T\geq 1$. A variation of this result, i.e., when $T\to\infty$ and without the $\|w-w_T\|^2$ term in the numerator, was first shown in \citep{hassibi1994hoo,hassibi1996h}. In that case, the ratio $\frac{\eta\sum_{i=1}^{\infty}e_{p,i}^2}{\|w-w_0\|^2+\eta\sum_{i=1}^{\infty}v_i^2}$ in the minimax problem is in fact the \emph{$H^{\infty}$ norm} of the transfer operator that maps the unknown disturbances $(w-w_0,\{\sqrt{\eta}v_i\})$ to the prediction errors $\{\sqrt{\eta}e_{p,i}\}$.

We end this section with a stochastic interpretation of SGD \citep{hassibi1996h}. Assume that the true weight vector has a normal distribution with mean $w_0$ and covariance matrix $\eta I$, and that the noise $v_i$ are iid standard normal. Then SGD solves
\begin{equation}
\min_{\{w_i\}} \E \exp\left(\frac{1}{2}\cdot\left(\|w-w_T\|^2+\eta\sum_{i=1}^T(x_i^Tw-x_i^Tw_{i-1})^2\right)\right),
\label{risk-sense}
\end{equation}
and no exponent larger than $\frac{1}{2}$ is possible, in the sense that no estimator can keep the expected cost finite. This means that, in the Gaussian setting, SGD minimizes the expected value of an {\em exponential} quadratic cost. The algorithm is thus very adverse to large estimation errors, as they are penalized exponentially larger than moderate ones.

\subsection{Convergence and Implicit Regularization}\label{sec:warmup_convergence}
The over-parameterized (interpolating) linear regression regime is a simple but instructive setting, recently considered in some papers \citep{gunasekar2018characterizing,zhang2016understanding}. In this setting, we can show that, for sufficiently small step, i.e. $0<\eta\leq\min_i\frac{1}{\|x_i\|^2}$, SGD always converges to a special solution among all the solutions $\mathcal{W}$, in particular to the one with the smallest $l_2$ distance from $w_0$. In other words, if, for example, initialized at zero, SGD implicitly regularizes the solution according to an $l_2$ norm. This result follows directly from Lemma~\ref{lem:sum}.

To see that, note that in the interpolating case the $v_i$ are zero,

and we have $e_i=y_i-x_i^Tw_{i-1}=x_i^Tw-x_i^Tw_{i-1}=e_{p,i}$. Hence, identity \eqref{eq:sum} reduces to
\begin{equation}\label{eq:equality_noiseless_sum}
\|w-w_{0}\|^2 = \|w-w_{T}\|^2 + \eta\sum_{i=1}^T\left(2-\eta\|x_i\|^2\right)e_i^2 ,
\end{equation}
for all $w\in\mathcal{W}$. By dropping the $\|w-w_T\|^2$ term and taking $T\to\infty$, we have $\eta\sum_{i=1}^\infty\left(2-\eta\|x_i\|^2\right)e_i^2 \leq \|w-w_{0}\|^2$, which implies that, for $0<\eta<\min_i\frac{2}{\|x_i\|^2}$, we must have $e_i\to 0$ as $i\to\infty$. When $e_i=y_i-x_i^Tw_{i-1}$ goes to zero, the updates in \eqref{eq:SGD} vanish and we get convergence, i.e., $w\to w_{\infty}$. Further, again because $e_i\to 0$, all the data points are being fit, which means $w_\infty\in\mathcal{W}$.
Moreover, it is again very straightforward to see from \eqref{eq:equality_noiseless_sum} that the solution converged to is the one with minimum Euclidean norm from the initial point. To see that, notice that the summation term in Eq.~\eqref{eq:equality_noiseless_sum} is \emph{independent of $w$} (it depends only on $x_i,y_i$ and $w_0$). Therefore, by taking $T\to\infty$ and minimizing both sides with respect to $w\in\mathcal{W}$, we get
\begin{equation}
w_{\infty}=\argmin_{w\in\mathcal{W}}\|w-w_0\| .
\end{equation}
Once again, this also implies that if SGD is initialized at the origin, i.e., $w_0=0$, then it converges to the minimum-$l_2$-norm solution, among all the solutions.

\section{Main Result: General Characterization of Stochastic Mirror Descent}\label{sec:SMD}
Stochastic Mirror Descent (SMD) \citep{nemirovskii1983problem,beck2003mirror,cesa2012mirror,zhou2017stochastic} is one of the most widely used families of algorithms for stochastic optimization, which includes SGD as a special case. In this section, we provide a characterization of the behavior of general SMD, on \emph{general} loss functions and \emph{general} nonlinear models, in terms of a fundamental identity and minimax optimality.

For any strictly convex and differentiable potential $\psi(\cdot)$, the corresponding SMD updates are defined as
\begin{equation}
w_i = \argmin_w\ \eta w^T\nabla L_i(w_{i-1})+D_{\psi}(w,w_{i-1}) ,
\end{equation}
where
\begin{equation}
D_{\psi}(w,w_{i-1})=\psi(w)-\psi(w_{i-1})-\nabla\psi(w_{i-1})^T (w-w_{i-1})
\end{equation}
is the Bregman divergence with respect to the potential function $\psi(\cdot)$. Note that $D_\psi(\cdot,\cdot)$ is non-negative, convex in its first argument, and that, due to strict convexity, $D_\psi(w,w') = 0$ iff $w=w'$. Moreover, the updates can be equivalently written as
\begin{equation}\label{eq:SMD}
\nabla\psi(w_i)=\nabla\psi(w_{i-1})-\eta\nabla L_i(w_{i-1}) ,
\end{equation}
which are uniquely defined because of the invertibility of $\nabla\psi$ (again, implied by the strict convexity of $\psi(\cdot)$). In other words, stochastic mirror descent can be thought of as transforming the variable $w$, with a \emph{mirror map} $\nabla\psi(\cdot)$, and performing the SGD update on the new variable. For this reason, $\nabla\psi(w)$ is often referred to as the \emph{dual} variable, while $w$ is the \emph{primal} variable.

Different choices of the potential function $\psi(\cdot)$ yield different optimization algorithms, which, as we will see, result in different implicit regularizations. To name a few examples: For the potential function $\psi(w)=\frac{1}{2}\|w\|^2$, the Bregman divergence is $D_{\psi}(w,w')=\frac{1}{2}\|w-w'\|^2$, and the update rule reduces to that of SGD. For $\psi(w)=\sum_j w_j\log w_j$, the Bregman divergence becomes the unnormalized relative entropy (Kullback-Leibler divergence) $D_{\psi}(w,w')=\sum_j w_j\log\frac{w_j}{w'_j}-\sum_j w_j + \sum_j w'_j$, which corresponds to the exponentiated gradient descent (aka the exponential weights) algorithm.
Other examples include $\psi(w)=\frac{1}{2}\|w\|_Q^2=\frac{1}{2}w^TQw$ for a positive definite matrix $Q$, which yields $D_{\psi}(w,w')=\frac{1}{2}(w-w')^TQ(w-w')$, and the $q$-norm squared $\psi(w)=\frac{1}{2}\|w\|_q^2$, which with $\frac{1}{p}+\frac{1}{q}=1$ yields the $p$-norm algorithms \citep{grove2001general,gentile2003robustness}.

In order to derive an equivalent ``conservation law'' for SMD, similar to the identity \eqref{eq:equality}, we first need to define a new measure for the difference between the parameter vectors $w$ and $w'$ according to the loss function $L_i(\cdot)$. To that end, let us define
\begin{equation}\label{eq:D_Li}
D_{L_i}(w,w'):=L_i(w)-L_i(w')-\nabla L_i(w')^T(w-w'),
\end{equation}
which is defined in a similar way to a Bregman divergence for the loss function.\footnote{It is easy to verify that for linear models and quadratic loss we obtain $D_{L_i}(w,w') = (x_i^Tw-x_i^Tw')^2$.} The difference though is that, unlike the potential function of the Bregman divergence, the loss function $L_i(\cdot) = \ell(y_i-f(x_i,\cdot))$ need not be convex, even when $\ell(\cdot)$ is, due to the nonlinearity of $f(\cdot,\cdot)$. As a result, $D_{L_i}(w,w')$ is not necessarily non-negative. The following result, which is the general counterpart of Lemma~\ref{lem:equality}, states the identity that characterizes SMD updates in the general setting.

\begin{lemma}\label{lem:equality_SMD}
For any (nonlinear) model $f(\cdot,\cdot)$, any differentiable loss $l(\cdot)$, any parameter $w$ and noise values $\{v_i\}$ that satisfy $y_i =f(x_i,w)+v_i$ for $i=1,\dots,n$, and any step size $\eta>0$, the following relation holds for the SMD iterates $\{w_i\}$ given in Eq.~\eqref{eq:SMD}
\begin{equation}\label{eq:equality_SMD}
D_{\psi}(w,w_{i-1})+\eta l(v_i) = D_{\psi}(w,w_i) +E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) ,
\end{equation}
for all $i\geq 1$, where
\begin{equation}
E_i(w_i,w_{i-1}) := D_{\psi}(w_i,w_{i-1})-\eta D_{L_i}(w_i,w_{i-1})+\eta L_i(w_i) .
\end{equation}
\end{lemma}
The proof is provided in Appendix~\ref{sec:proof_of_equality_SMD}. Note that $E_i(w_i,w_{i-1})$ is not a function of $w$. Furthermore, even though it does not have to be nonnegative in general, for $\eta$ sufficiently small, it becomes nonnegative, because the Bregman divergence $D_{\psi}(.,.)$ is nonnegative.

Summing Equation~\eqref{eq:equality_SMD} over all $i=1,\dots,T$ leads to the following identity, which is the general counterpart of Lemma~\ref{lem:sum}.
\begin{lemma}\label{lem:sum_SMD}
For any (nonlinear) model $f(\cdot,\cdot)$, any differentiable loss $l(\cdot)$, any parameter $w$ and noise values $\{v_i\}$ that satisfy $y_i =f(x_i,w)+v_i$ for $i=1,\dots,n$, any initialization $w_0$, any step size $\eta>0$, and any number of steps $T\geq 1$, the following relation holds for the SMD iterates $\{w_i\}$ given in Eq.~\eqref{eq:SMD}
\begin{empheq}[box=\fbox]{equation}\label{eq:sum_SMD}
D_{\psi}(w,w_{0})+\eta \sum_{i=1}^T l(v_i) = D_{\psi}(w,w_T) +\sum_{i=1}^T \left( E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) \right) .
\end{empheq}
\end{lemma}
We should reiterate that Lemma~\ref{lem:sum_SMD} is a fundamental property of SMD, which allows one to prove many important results, in a direct way.

In particular, in this setting, we can show that SMD is minimax optimal in a manner that generalizes Theorem~\ref{thm:SGDminimax} of Section~\ref{sec:warmup}, in the following 3 ways: 1) General potential $\psi(\cdot)$, 2) General model $f(\cdot,\cdot)$, and 3) General loss function $l(\cdot)$. The result is as follows.
\begin{theorem}\label{thm:SMD}
Consider any (nonlinear) model $f(\cdot,\cdot)$, any non-negative differentiable loss $l(\cdot)$ with the property $l(0)=l'(0)=0$, and any initialization $w_0$. For sufficiently small step size, i.e., for any $\eta>0$ for which $\psi(w)-\eta L_i(w)$ is convex for all $i$, and for any number of steps $T\geq 1$, the SMD iterates $\{w_i\}$ given by Eq.~\eqref{eq:SMD}, w.r.t. any strictly convex potential $\psi(\cdot)$, is the optimal solution to the following minimization problem
\begin{equation}
\min_{\{w_i\}}\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\eta\sum_{i=1}^{T}D_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\eta\sum_{i=1}^{T}l(v_i)} .
\end{equation}
Furthermore, the optimal value (achieved by SMD) is $1$.
\end{theorem}
The proof is provided in Appendix~\ref{sec:proof_of_thm_SMD}.

For the case of square loss and a linear model, the result reduces to the following form.
\begin{corollary}\label{cor:SMD_squareloss_linear}
For $L_i(w)=\frac{1}{2}(y_i-x_i^Tw)^2$, for any initialization $w_0$, any sufficiently small step size, i.e., $0<\eta\leq\frac{\alpha}{\|x_i\|^2}$, and any number of steps $T\geq 1$, the SMD iterates $\{w_i\}$ given by Eq.~\eqref{eq:SMD}, w.r.t. any $\alpha$-strongly convex potential $\psi(\cdot)$, is the optimal solution to
\begin{equation}
\min_{\{w_i\}}\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\frac{\eta}{2}\sum_{i=1}^{T}e_{p,i}^2}{D_{\psi}(w,w_0)+\frac{\eta}{2}\sum_{i=1}^{T} v_i^2} .
\end{equation}
The optimal value (achieved by SMD) is $1$.
\end{corollary}

We should remark that Theorem~\ref{thm:SMD} and Corollary~\ref{cor:SMD_squareloss_linear} generalize several known results in the literature. In particular, as mentioned in Section~\ref{sec:warmup}, the result of \citep{hassibi1994hoo} is a special case of Corollary~\ref{cor:SMD_squareloss_linear} for $\psi(w)=\frac{1}{2}\|w\|^2$. Furthermore, our result generalizes the result of \citep{kivinen2006p}, which is the special case for the $p$-norm algorithms, again, with square loss and a linear model. Another interesting connection to the literature is that it was shown in \citep{hassibi1995h} that SGD is \emph{locally} minimax optimal, with respect to the $H^{\infty}$ norm. Strictly speaking, our result is not a generalization of that result; however, Theorem~\ref{thm:SMD} can be interpreted as SGD/SMD being \emph{globally} minimax optimal, but with respect to different metrics in the numerator and denominator. Namely, the uncertainty about the weight vector $w$ is measured by the Bregman divergence of the potential, the uncertainty about the noise by the loss, and the prediction error by the ``Bregman-divergence-like'' expression of the loss.

\section{Convergence and Implicit Regularization in Over-Parameterized Models}\label{sec:implications}

In this section, we show some of the implications of the theory developed in the previous section. In particular, we show convergence and implicit regularization, in the over-parameterized (so-called interpolating) regime, for general SMD algorithms. We first consider the linear interpolating case, which has been studied in the literature, and show that the known results follow naturally from our Lemma~\ref{lem:sum_SMD}. Further, we shall obtain some {\em new} convergence results. Finally, we discuss the implications for nonlinear models, and argue that the same results hold {\em qualitatively} in highly-overparameterized settings, which is the typical scenario in deep learning.

\subsection{Over-Parameterized Linear Models}

In this setting, the $v_i$ are zero, $\mathcal{W} = \left\{w\mid y_i=x_i^Tw,\ i=1,\dots,n\right\}$, and $L_i(w)=l(y_i-x_i^Tw)$, with any differentiable loss $l(\cdot)$. Therefore, Eq.~\eqref{eq:sum_SMD} reduces to
\begin{equation}\label{eq:sum_SMD_noiseless}
D_{\psi}(w,w_{0}) = D_{\psi}(w,w_T) +\sum_{i=1}^T \left( E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) \right) ,
\end{equation}
for all $w\in\mathcal{W}$, where
\begin{align}
D_{L_i}(w,w_{i-1}) &=L_i(w)-L_i(w_{i-1})-\nabla L_i(w_{i-1})^T(w-w_{i-1})\\
&= 0-l(y_i-x_i^Tw_{i-1})+l'(y_i-x_i^Tw_{i-1})x_i^T(w-w_{i-1})\\
&= -l(y_i-x_i^Tw_{i-1})+l'(y_i-x_i^Tw_{i-1})(y_i-x_i^Tw_{i-1})
\end{align}
which is notably \emph{independent of $w$}. As a result, we can easily minimize both sides of Eq.~\eqref{eq:sum_SMD_noiseless} with respect to $w\in\mathcal{W}$, which
leads to the following result.
\begin{proposition}\label{prop:ImpReg_SMD}
For any differentiable loss $l(\cdot)$, any initialization $w_0$, and any step size $\eta$, consider the SMD iterates given in Eq.~\eqref{eq:SMD} with respect to any strictly convex potential $\psi(\cdot)$. If the iterates converge to a solution $w_{\infty}\in\mathcal{W}$, then
\begin{equation}
w_{\infty}=\argmin_{w\in\mathcal{W}} D_{\psi}(w,w_0) .
\end{equation}
\end{proposition}
\begin{remark}
In particular, for the initialization $w_0=\argmin_{w\in\mathbb{R}^m} \psi(w)$, if the iterates converge to a solution $w_{\infty}\in\mathcal{W}$, then
\begin{equation}\label{eq:minimum_potential}
w_{\infty}=\argmin_{w\in\mathcal{W}} \psi(w) .
\end{equation}
\end{remark}
An equivalent form of Proposition~\ref{prop:ImpReg_SMD} has been shown recently in, e.g., \citep{gunasekar2018characterizing}.\footnote{To be precise, the authors in \citep{gunasekar2018characterizing} assume convergence to a global minimizer of the loss function $L(w)=\sum_{i=1}^n l(y_i-x_i^Tw)$, which with their assumption of the loss function $l(\cdot)$ having a unique finite root is equivalent to assuming convergence to a point $w_{\infty}\in\mathcal{W}$.} Other implicit regularization results have been shown in \citep{gunasekar2018implicit,soudry2017implicit} for classification problems, which are not discussed here.
Note that the result of \citep{gunasekar2018characterizing} does not say anything about \emph{whether the algorithm converges or not}. However, our fundamental identity of SMD (Lemma~\ref{lem:sum_SMD}) allows us to also establish convergence to the regularized point, for some common cases, which will be shown next.

What Proposition~\ref{prop:ImpReg_SMD} says is that depending on the choice of the potential function $\psi(\cdot)$, the optimization algorithm can perform an implicit regularization without any explicit regularization term. In other words, for any desired regularizer, if one chooses a potential function that approximates the regularizer, we can run the optimization without explicit regularization, and if it converges to a solution, the solution must be the one with the minimum potential.

In principle, one can choose the potential function in SMD for {\em any} desired convex regularization.  For example, we can find the maximum entropy solution by taking the potential to be the negative entropy. Another illustrative example follows.

\noindent {\bf Example [Compressed Sensing]:} In compressed sensing, one seeks the sparsest solution to an under-determined (over-parameterized) system of linear equations. The surrogate convex problem one solves is:
\begin{equation}
\begin{array} {cl} \min & \|w\|_1 \\ \mbox{subject to} & y_i = x_i^Tw,~~~i=1,\ldots n \end{array}
\end{equation}
One cannot choose $\psi(w) = \|w\|_1$, since it is neither differentiable nor strictly convex. However, $\psi(w) = \|w\|_{1+\epsilon}$, for any $\epsilon>0$, can be used. Figure 4 shows a  compressed sensing example, with $n=50$, $m=100$, and sparsity $k=10$. SMD was used with a step size of $\eta = 0.001$ and the potential function was $\psi(\cdot) = \|\cdot\|_{1.1}$. SMD converged to the true sparse solution after around 10,000 iterations. On this example, it was an order of magnitude faster than standard $l_1$ optimization.

\begin{figure}[thbp]
\begin{center}
\includegraphics[scale=.4]{Plot_notitle.png}
\end{center}
\label{fig:cs}
\caption{The training loss and actual error of stochastic mirror descent for compressed sensing. SMD recovers the actual sparse signal.}
\end{figure}

Next we establish \emph{convergence to the regularized point} for the convex case.

\begin{proposition}\label{prop:convergence_SMD}
Consider the following two cases.
\begin{enumerate}[label=(\roman*)]
\item $l(\cdot)$ is differentiable and convex and has a unique root at 0, $\psi(\cdot)$ is strictly convex, and $\eta>0$ is such that $\psi-\eta L_i$ is convex for all $i$.
\item $l(\cdot)$ is differentiable and quasi-convex, $l'(\cdot)$ is zero only at zero, $\psi(\cdot)$ is $\alpha$-strongly convex, and $0<\eta\leq\min_i\frac{\alpha |y_i-x_i^Tw_{i-1}|}{\|x_i\|^2|l'(y_i-x_i^Tw_{i-1})|}$.
\end{enumerate}

If either (i) or (ii) holds, then for any $w_0$, the SMD iterates given in Eq.~\eqref{eq:SMD} converge to
\begin{equation}
w_{\infty}=\argmin_{w\in\mathcal{W}} D_{\psi}(w,w_0) .
\end{equation}
\end{proposition}
The proof is provided in Appendix~\ref{sec:proof_of_prop_convergence_SMD}.

\subsection{Discussion of Highly Over-Parameterized Nonlinear Models}

Let us consider the highly-overparameterized nonlinear model
\begin{equation}
y_i = f(x_i,w),~~~i=1,\ldots,n,~~~~w\in \mathbb{R}^m
\end{equation}
where by highly-overparameterized we mean $m\gg n$. Since the model is highly over-parameterized, it is assumed that we can perfectly interpolate the data points $(x_i,y_i)$ so that the noise $v_i$ is zero. In this case, the set of parameter vectors that interpolate the data is given by
$\mathcal{W} = \{w \in \mathbb{R}^m\mid y_i = f(x_i,w),\ i=1,\ldots, n\}$,
and Eq.~\eqref{eq:sum_SMD}, again, reduces to
\begin{equation}
D_{\psi}(w,w_{0}) = D_{\psi}(w,w_T) +\sum_{i=1}^T \left( E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) \right) ,
\label{eq:nonlinearnov}
\end{equation}
for all $w\in\mathcal{W}$. Our proofs of convergence and implicit regularization for SGD and SMD in the linear case relied on two facts: (i) $D_{L_i}(w,w_{i-1})$ was non-negative (this allowed us to show convergence), and (ii)  $D_{L_i}(w,w_{i-1})$ was independent of $w$ (this allowed us to show implicit regularization). Unfortunately, neither of these hold in the nonlinear case.

However, they do hold in a {\em local} sense. In other words, (i) $D_{L_i}(w,w_{i-1})\geq 0$ for $w_{i-1}$ ``close enough'' to $w$ (see Figure~\ref{fig:local}), and (ii) $D_{L_i}(w,w_{i-1})$ is weakly dependent on $w$ for $w_{i-1}$ ``close enough.''  (Both statements can be made precise.)
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=.3]{local.jpg}
\end{center}
\caption{Non-negativity of $D_{L_i}(w,w_{i-1})$ for $w_{i-1}$ ``close enough'' to $w$.}
\label{fig:local}
\end{figure}

Now define
\begin{equation}
w_* = \mbox{arg}\min_{w\in{\cal W}}D_\psi(w,w_0) .
\end{equation}
Then one can show the following result.
\begin{theorem}
There exists an $\epsilon>0$, such that if $\|w_*-w_0\|<\epsilon$, then for sufficiently small step size $\eta>0$:
\begin{enumerate}
\item SMD iterates converge to a point $w_\infty\in{\cal W}$
\item $\|w_\infty-w_*\| = o(\epsilon)$
\end{enumerate}
\end{theorem}
This shows that if the initial condition is close enough, then we have convergence to a point $w_\infty$ that interpolates the data, and that $w_\infty$ is an order of magnitude closer to $w_*$ (the implicitly regularized solution) than the initial $w_0$ was. At first glance, this result seems rather dissatisfying. It relies on $w_0$ being close to the manifold ${\cal W}$ which appears hard to guarantee. We would now like to argue that in deep learning $w_0$ being close to ${\cal W}$ is often the case.

In the highly-overparameterized regime, $m\gg n$, and so the dimension of the manifold $\mathcal{W}$ is $m-n$, which is very large. Now if the $x_i$ are sufficiently random, then the tangent space to ${\cal W}$ at $w_*$ will be a randomly oriented affine subspace of dimension $m-n$. This means that any randomly chosen $w_0$ will whp have a very large component when projected onto $\mathcal{W}$. In particular, it can be shown that $\|w_*-w_0\|^2 = O(\frac{n}{m})\cdot\|y-f(x,w)\|^2$, where $y = \mbox{vec}(y_i,i=1,\ldots,n)$ and $f(x,w) = \mbox{vec}(f(x_i,w),i=1,\ldots,n)$. Thus, we may expect that, when $m\gg n$, the distance of any randomly chosen $w_0$ to $\mathcal{W}$ will be small and so SMD will converge to a point on $\mathcal{W}$ that approximately performs implicit regularization.

The gist of the argument is that (i) When $m\gg n$, any random initial condition is ``close'' to the $n-m$ dimensional solution manifold ${\cal W}$, (ii) when $w_0$ is ``close'' to $w_*$, then SMD converges to a point $w_\infty\in{\cal W}$, (iii) $w_\infty$ is ``an order of magnitude closer'' to $w_*$ than $w_0$ was, and (iv) thus, when highly overparamatrized, SMD converges to a point that exhibits implicit regularization.

Of course, this was a very heuristic argument that merits a much more careful analysis. But it is suggestive of the fact that SGD and SMD, when performed on highly-overparameterized nonlinear models, as occurs in deep learning, may exhibit implicit regularization.

\section{Concluding Remarks}\label{sec:conclusion}

We should remark that all the results stated throughout the paper extend to the case of time-varying step size $\eta_i$, with minimal modification. In particular, it is easy to show that in this case, the identity (the counterpart of Eq.~\eqref{eq:sum_SMD}) becomes
\begin{equation}
D_{\psi}(w,w_{0})+ \sum_{i=1}^T \eta_i l(v_i) = D_{\psi}(w,w_T) +\sum_{i=1}^T \left( E_i(w_i,w_{i-1}) +\eta_i D_{L_i}(w,w_{i-1}) \right) ,
\end{equation}

where $E_i(w_i,w_{i-1}) = D_{\psi}(w_i,w_{i-1})-\eta_i D_{L_i}(w_i,w_{i-1})+\eta_i L_i(w_i)$.
As a consequence, our main result will be the same as in Theorem~\ref{thm:SMD}, with the only difference that the small-step-size condition in this case is the convexity of $\psi(w)-\eta_iL_i(w)$ for all $i$, and the SMD with time-varying step size will be the optimal solution to the following minimax problem
\begin{equation}
\min_{\{w_i\}}\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\sum_{i=1}^{T}\eta_iD_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\sum_{i=1}^{T}\eta_il(v_i)} .
\end{equation}
Similarly, the convergence and implicit regularization results can be proven under the same conditions (See Appendix~\ref{sec:timevar} for more details on the time-varying case).

This paper opens up a variety of important directions for future work. Most of the analysis developed here is general, in terms of the \emph{model}, the \emph{loss function}, and the \emph{potential function}. Therefore, it would be interesting to study the implications of this theory for specific classes of models (such as different neural networks), specific losses, and specific mirror maps (which induce different regularization biases). Something for future work.

\bibliography{references}
\bibliographystyle{iclr2019_conference}

\newpage
\begin{center}
{\huge Supplementary Material}
\end{center}
\appendix

\section{Proof of Lemma~\ref{lem:equality_SMD}}\label{sec:proof_of_equality_SMD}
\begin{proof}
Let us start by expanding the Bregman divergence $D_{\psi}(w,w_i)$ based on its definition
\[ D_{\psi}(w,w_i) = \psi(w)-\psi(w_i)-\nabla\psi(w_i)^T(w-w_i).\]
By plugging the SMD update rule $\nabla\psi(w_i)=\nabla\psi(w_{i-1})-\eta\nabla L_i(w_{i-1})$ into this, we can write it as
\begin{equation}
D_{\psi}(w,w_i)= \psi(w)-\psi(w_i)-\nabla\psi(w_{i-1})^T(w-w_i) + \eta\nabla L_i(w_{i-1})^T(w-w_i) .
\end{equation}
Using the definition of Bregman divergence for $(w,w_{i-1})$ and $(w_i,w_{i-1})$, i.e., $D_{\psi}(w,w_{i-1}) = \psi(w)-\psi(w_{i-1})-\nabla\psi(w_{i-1})^T(w-w_{i-1})$ and $D_{\psi}(w_i,w_{i-1}) = \psi(w_i)-\psi(w_{i-1})-\nabla\psi(w_{i-1})^T(w_i-w_{i-1})$, we can express this as
\begin{align}
D_{\psi}(w,w_i) &= D_{\psi}(w,w_{i-1})+\psi(w_{i-1})+\nabla\psi(w_{i-1})^T(w-w_{i-1}) -\psi(w_i)\notag\\
&\hspace{4cm} -\nabla\psi(w_{i-1})^T(w-w_i) + \eta\nabla L_i(w_{i-1})^T(w-w_i)\\
&= D_{\psi}(w,w_{i-1})+\psi(w_{i-1})-\psi(w_i)+\nabla\psi(w_{i-1})^T(w_i-w_{i-1})\notag\\
&\hspace{7.5cm} +\eta\nabla L_i(w_{i-1})^T(w-w_i)\\
&= D_{\psi}(w,w_{i-1})-D_{\psi}(w_i,w_{i-1}) +\eta\nabla L_i(w_{i-1})^T(w-w_i) .
\end{align}
Expanding the last term using $w-w_i = (w-w_{i-1})-(w_i-w_{i-1})$, and following the definition of $D_{L_i}(.,.)$ from \eqref{eq:D_Li} for $(w,w_{i-1})$ and $(w_i,w_{i-1})$, we have
\begin{align}
D_{\psi}(w,w_i) &= D_{\psi}(w,w_{i-1})-D_{\psi}(w_i,w_{i-1}) +\eta\nabla L_i(w_{i-1})^T(w-w_{i-1})\notag\\
&\hspace{7cm} -\eta\nabla L_i(w_{i-1})^T(w_i-w_{i-1})\\
&= D_{\psi}(w,w_{i-1})-D_{\psi}(w_i,w_{i-1}) +\eta\left(L_i(w)-L_i(w_{i-1})-D_{L_i}(w,w_{i-1})\right)\notag\\
&\hspace{5cm} -\eta\left(L_i(w_i)-L_i(w_{i-1})-D_{L_i}(w_i,w_{i-1})\right)\\
&= D_{\psi}(w,w_{i-1})-D_{\psi}(w_i,w_{i-1}) +\eta\left(L_i(w)-D_{L_i}(w,w_{i-1})\right)\notag\\
&\hspace{6.5cm} -\eta\left(L_i(w_i)-D_{L_i}(w_i,w_{i-1})\right)
\end{align}
Defining $E_i(w_i,w_{i-1}) := D_{\psi}(w_i,w_{i-1})-\eta D_{L_i}(w_i,w_{i-1})+\eta L_i(w_i)$, we can write the above equality as
\begin{equation}
D_{\psi}(w,w_i) = D_{\psi}(w,w_{i-1})-E_i(w_i,w_{i-1}) +\eta\left(L_i(w)-D_{L_i}(w,w_{i-1})\right) .
\end{equation}
Notice that for any model class with additive noise, and any loss function $L_i$ that depends only on the residual (i.e. the difference between the prediction and the true label), the term $L_i(w)$ depends only on the noise term, for any ``true'' parameter $w$. In other words, for all $w$ that satisfy $y_i =f(x_i,w)+v_i$, we have $L_i(w)=l(y_i-f(x_i,w))=l(y_i-(y_i-v_i))=l(v_i)$ . Finally, reordering the terms leads to
\begin{equation}
D_{\psi}(w,w_i)+\eta D_{L_i}(w,w_{i-1}) +E_i(w_i,w_{i-1}) = D_{\psi}(w,w_{i-1}) +\eta l(v_i) ,
\end{equation}

which concludes the proof.
\end{proof}

\section{Proof of Theorem~\ref{thm:SMD}}\label{sec:proof_of_thm_SMD}
\begin{proof}
We prove the theorem in two parts. First, we show that the value of the minimax is at least $1$. Then we prove that the values is at most $1$, and is achieved by stochastic mirror descent for small enough step size.
\begin{enumerate}
\item
Consider the maximization problem
\begin{equation*}
\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\eta\sum_{i=1}^{T}D_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\eta\sum_{i=1}^{T}l(v_i)} .
\end{equation*}
Clearly, the optimal solution and the optimal values of this problem can, and will, be a function of $\{w_i\}$. Similarly, we can also choose feasible points that depend on $\{w_i\}$.
Any choice of a feasible point $(\hat{w},\{\hat{v}_i\})$ gives a lower bound on the value of the problem. Before choosing a feasible point, let us first expand the $D_{L_i}(w,w_{i-1})$ term in the numerator, according to its definition.
\begin{equation}
D_{L_i}(w,w_{i-1})=l(v_i) -l(y_i-f_i(w_{i-1})) +l'(y_i-f_i(w_{i-1}))\nabla f(w_{i-1})^T(w-w_{i-1}),
\end{equation}
where we have used the fact that $l(y_i-f_i(w))=l(v_i)$ for all consistent $w$, in the first term.

Now, we choose a feasible point as follows
\begin{equation}\label{hatvi}
\hat{v}_i=f_i(w_{i-1})-f_i(\hat{w}),
\end{equation}
where $\hat{w}$ is the choice of $w$, as will be described soon. The reason for choosing this value for the noise is that it ``fools'' the estimator by making its loss on the corresponding data point zero. In other words, for this choice, we have
\begin{align*}
D_{L_i}(w,w_{i-1})&=l(\hat{v}_i) -l(0) +l'(0)\nabla f(w_{i-1})^T(\hat{w}-w_{i-1})\\
& = l(\hat{v}_i)
\end{align*}
because $l(0)=l'(0)=0$. It should be clear at this point that this choice makes the second terms in the numerator and the denominator equal, independent of the choice of $\hat{w}$. What remains to do, in order to show the $1$ lower-bound, is to take care of the other two terms, i.e., $D_{\psi}(w,w_T)$ and $D_{\psi}(w,w_0)$. As we would like to make the ratio equal to one, we would like to have $D_{\psi}(w,w_T)=D_{\psi}(w,w_0)$,
which is equivalent to having
\[
\psi(w)-\psi(w_{T})-\nabla\psi(w_{T})^T (w-w_{T})=\psi(w)-\psi(w_{0})-\nabla\psi(w_{0})^T (w-w_{0})
\]
which is, in turn, equivalent to
\begin{equation}\label{eq:solve_for_w}
\left(\nabla\psi(w_{T})-\nabla\psi(w_{0})\right)^T w = -\psi(w_{T}) +\psi(w_{0}) +\nabla\psi(w_{T})^T w_{T} -\nabla\psi(w_{0})^T w_{0} .
\end{equation}
Since $\nabla\psi$ is an invertible function, $\nabla\psi(w_{T})-\nabla\psi(w_{0})\neq 0$, if $w_T\neq w_0$. Therefore, the above equation has a solution for $w$, if $w_T\neq w_0$. As a result, choosing $\hat{w}$ to be a solution to \eqref{eq:solve_for_w} makes $D_{\psi}(\hat{w},w_T)=D_{\psi}(\hat{w},w_0)$, if $w_T\neq w_0$. For the case when $w_T=w_0$, it is trivial that $D_{\psi}(\hat{w},w_T)=D_{\psi}(\hat{w},w_0)$ for any choice of $\hat{w}$. In this case, we only need to choose $\hat{w}$ to be different from $w_0$, to avoid making the ratio $\frac{0}{0}$. Hence, we have the following choice
\begin{equation}\label{hatw}
\hat{w}=\begin{cases}
\text{a solution of \eqref{eq:solve_for_w}} & \text{ for } w_T\neq w_0\\
w_0+\delta w \ \text{ for some } \delta w\neq 0 & \text{ for } w_T=w_0
\end{cases}
\end{equation}
Choosing the feasible point $\hat{w},\{v_i\}$ according to \eqref{hatw} and \eqref{hatvi}  leads to
\begin{multline}
\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\eta\sum_{i=1}^{T}D_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\eta\sum_{i=1}^{T}l(v_i)}\\
\geq \frac{D_{\psi}(\hat{w},w_T)+\eta\sum_{i=1}^{T}l(f_i(w_{i-1})-f_i(\hat{w}))}{D_{\psi}(\hat{w},w_0)+\eta\sum_{i=1}^{T}l(f_i(w_{i-1})-f_i(\hat{w}))}.
\end{multline}
Taking the minimum of both sides with respect to $\{w_i\}$, we have
\begin{multline}
\min_{\{w_i\}}\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\eta\sum_{i=1}^{T}D_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\eta\sum_{i=1}^{T}l(v_i)}\\
\geq \min_{\{w_i\}} \frac{D_{\psi}(\hat{w},w_T)+\eta\sum_{i=1}^{T}l(f_i(w_{i-1})-f_i(\hat{w}))}{D_{\psi}(\hat{w},w_0)+\eta\sum_{i=1}^{T}l(f_i(w_{i-1})-f_i(\hat{w}))}\ =\ 1.
\end{multline}
The equality to $1$ comes from the fact the that the optimal solution of the minimization either has $w^*_T=w_0$ or $w^*_T\neq w_0$, and in both cases the ratio is equal to $1$.

\item
Now we prove that, under the small step size condition (convexity of $\psi(w)-\eta L_i(w)$ for all $i$), SMD makes the minimax value at most $1$, which means that it is indeed an optimal solution. Recall from Lemma~\ref{lem:sum_SMD} that
\begin{equation*}
D_{\psi}(w,w_{0})+\eta \sum_{i=1}^T l(v_i) = D_{\psi}(w,w_T) +\sum_{i=1}^T E_i(w_i,w_{i-1}) +\eta \sum_{i=1}^T D_{L_i}(w,w_{i-1})  ,
\end{equation*}

where
\begin{equation*}
E_i(w_i,w_{i-1}) = D_{\psi}(w_i,w_{i-1})-\eta D_{L_i}(w_i,w_{i-1})+\eta L_i(w_i) .
\end{equation*}
It is easy to check that when $\psi(w)-\eta L_i(w)$ is convex, $D_{\psi}(w_i,w_{i-1})-\eta D_{L_i}(w_i,w_{i-1})$ is in fact a Bregman divergence (i.e. the Bregman divergence with respect to the potential $\psi(w)-\eta L_i(w)$), and therefore it is nonnegative for any $w_i$ and $w_{i-1}$. Furthermore, we know that the loss $L_i(w_i)$ is also nonnegative for all $w_i$. It follows that $E_i(w_i,w_{i-1})$ is nonnegative for all values of $w_i,w_{i-1}$ and $i$. As a result, we have the following bound.
\begin{equation}
D_{\psi}(w,w_{0})+\eta \sum_{i=1}^T l(v_i) \geq D_{\psi}(w,w_T) +\eta \sum_{i=1}^T D_{L_i}(w,w_{i-1}) .
\end{equation}

Since the Bregman divergence $D_{\psi}(w,w_{0})$ and the loss $l(v_i)$ are nonnegative, the left-hand side expression is nonnegative, and it follows that
\begin{equation}
\frac{D_{\psi}(w,w_T) +\eta \sum_{i=1}^T D_{L_i}(w,w_{i-1})} {D_{\psi}(w,w_{0})+\eta \sum_{i=1}^T l(v_i)}\leq 1 .
\end{equation}

In fact, this means that independent of the choice of the maximizer (i.e. for all $\{v_i\}$ and $w$), as long as the step size condition is met, SMD makes the ratio less than or equal to $1$.
\end{enumerate}
Combining the results of 1 and 2 above concludes the proof.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:SGDminimax}}
\begin{proof}
This result is a special case of Theorem~\ref{thm:SMD}, which was proven above. In this case, $\psi(w)=\frac{1}{2}\|w\|^2$, $f(x_i,w)=x_i^Tw$, and $l(z)=\frac{1}{2}z^2$. Therefore, $D_{\psi}(w,w_T)=\frac{1}{2}\|w-w_T\|^2$, $D_{\psi}(w,w_0)=\frac{1}{2}\|w-w_0\|^2$, $D_{L_i}(w,w_{i-1})=\frac{1}{2}(x_i^Tw-x_i^Tw_{i-1})^2$, and $l(v_i)=\frac{1}{2}v_i^2$, which leads to the result.
\end{proof}

\section{Proof of Proposition~\ref{prop:convergence_SMD}}\label{sec:proof_of_prop_convergence_SMD}
\begin{proof}
To prove convergence, we appeal again to Equation~\eqref{eq:sum_SMD_noiseless}, i.e.
\begin{equation}\label{eq:proof_sum_SMD_noiseless}
D_{\psi}(w,w_{0}) = D_{\psi}(w,w_T) +\sum_{i=1}^T \left( E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) \right) ,
\end{equation}
for all $w\in\mathcal{W}$. We prove the two cases separately.

\begin{enumerate}
\item The proof of case (i) is straightforward. When $l(\cdot)$ is differentiable and convex, $L_i$ is also convex, and therefore $D_{L_i}(w,w_{i-1})$ is nonnegative.
Moreover, when $\psi-\eta L_i$ is convex, $E_i(w_i,w_{i-1})$ is also nonnegative. Therefore, the entire summand in Eq.~\eqref{eq:proof_sum_SMD_noiseless} is nonnegative, and has to go to zero for $i\to\infty$. That is because as $T\to\infty$, the sum should remain bounded, i.e., $\sum_{i=1}^{\infty} \left( E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) \right)\leq D_{\psi}(w,w_{0})$.
As a result of the non-negativity of both terms in the sum, we have both $E_i(w_i,w_{i-1})\to 0$ and $D_{L_i}(w,w_{i-1})\to 0$ as $i\to\infty$, which imply $L_i(w_{i-1})\to 0$. This implies that the updates in \eqref{eq:SMD} vanish and we get convergence, i.e., $w\to w_{\infty}$. Further, again because $L_i(w_{i-1})\to 0$, and 0 is the unique root of $l(\cdot)$, all the data point are being fit, which means $w_{\infty}\in\mathcal{W}$.

\item To prove case (ii), note that we have

\begin{align}
D_{L_i}(w,w_{i-1}) &=L_i(w)-L_i(w_{i-1})-\nabla L_i(w_{i-1})^T(w-w_{i-1})\\
&= 0-l(y_i-x_i^Tw_{i-1})+l'(y_i-x_i^Tw_{i-1})x_i^T(w-w_{i-1})\\
&= -l(y_i-x_i^Tw_{i-1})+l'(y_i-x_i^Tw_{i-1})(y_i-x_i^Tw_{i-1}) , \label{eq:proof_convergence_SMD_quasi_1}
\end{align}
and
\begin{align}
E_i(w_i,w_{i-1}) &= D_{\psi}(w_i,w_{i-1})-\eta D_{L_i}(w_i,w_{i-1})+\eta L_i(w_i)\\
&= D_{\psi}(w_i,w_{i-1}) + \eta \left(L_i(w_{i-1})+\nabla L_i(w_{i-1})^T(w_i-w_{i-1})\right)\\
&= D_{\psi}(w_i,w_{i-1}) + \eta \left(l(y_i-x_i^Tw_{i-1})-l'(y_i-x_i^Tw_{i-1})x_i^T(w_i-w_{i-1})\right) . \label{eq:proof_convergence_SMD_quasi_2}
\end{align}
It follows from \eqref{eq:proof_convergence_SMD_quasi_1} and \eqref{eq:proof_convergence_SMD_quasi_2} that the summand in Equation~\eqref{eq:proof_sum_SMD_noiseless} is
\begin{align}
E_i(w_i,w_{i-1}) +\eta D_{L_i}(w,w_{i-1}) &= D_{\psi}(w_i,w_{i-1}) + \eta l'(y_i-x_i^Tw_{i-1})(y_i-x_i^Tw_{i}) .
\end{align}
The first term is a Bregman divergence, and is therefore nonnegative. In order to establish convergence, one needs to argue that the second term is nonnegative as well, so that the summand goes to zero as $i\to\infty$. Since $l(\cdot)$ is increasing for positive values and decreasing for negative values, it is enough to show that $y_i-x_i^Tw_{i-1}$ and $y_i-x_i^Tw_{i}$ have the same sign, in order to establish nonnegativity. It is not hard to see that if the distance between the two points is less than or equal to the distance of $y_i-x_i^Tw_{i}$ from the origin, then the signs are the same. In other words, if $|(y_i-x_i^Tw_{i})-(y_i-x_i^Tw_{i-1})|=|x_i^T(w_i-w_{i-1})|\leq |y_i-x_i^Tw_{i-1}|$, then the sign are the same.

Note that by the definition of $\alpha$-strong convexity of $\psi(\cdot)$, we have
\begin{equation}
(\nabla\psi(w_i)-\nabla\psi(w_{i-1}))^T(w_i-w_{i-1})\geq \alpha \|w_i-w_{i-1}\|^2 ,
\end{equation}
which implies
\begin{equation}
-\eta\nabla L_i(w_{i-1})^T(w_i-w_{i-1})\geq \alpha \|w_i-w_{i-1}\|^2 ,
\end{equation}
by substituting from the SMD update rule. Upper-bounding the left-hand side by $\eta\|\nabla L_i(w_{i-1})\|\|(w_i-w_{i-1})\|$ implies
\begin{equation}
\eta\|\nabla L_i(w_{i-1})\|\geq \alpha \|w_i-w_{i-1}\| .
\end{equation}
This implies that we have the following bound
\begin{equation}
|x_i^T(w_i-w_{i-1})|\leq \|x_i\| \|w_i-w_{i-1}\| \leq \frac{\eta\|x_i\|\|\nabla L_i(w_{i-1})\|}{\alpha} .
\end{equation}
It follows that if $\eta\leq\frac{\alpha|y_i-x_i^Tw_{i-1}|}{\|x_i\|\|\nabla L_i(w_{i-1})\|}$, for all $i$, then the signs are the same, and the summand in Eq.\eqref{eq:proof_sum_SMD_noiseless} is indeed nonnegative.
This condition can be equivalently expressed as $\eta\leq\frac{\alpha |y_i-x_i^Tw_{i-1}|}{\|x_i\|^2|l'(y_i-x_i^Tw_{i-1})|}$ for all $i$, or $\eta\leq\min_i\frac{\alpha |y_i-x_i^Tw_{i-1}|}{\|x_i\|^2|l'(y_i-x_i^Tw_{i-1})|}$, which is the condition in the statement of the proposition.

Now that we have argued that the summand is nonnegative, the convergence to $w_{\infty}\in\mathcal{W}$ is immediate. The reason is that both $D_{\psi}(w_i,w_{i-1})\to 0$ and $l'(y_i-x_i^Tw_{i-1})(y_i-x_i^Tw_{i})\to 0$, as $i\to\infty$. The first one implies convergence to a point $w_{\infty}$. The second one implies that either $y_i-x_i^Tw_{i-1}=0$ or $y_i-x_i^Tw_{i}= 0$, which, in turn, implies $w_{\infty}\in\mathcal{W}$.
\end{enumerate}
\end{proof}

\section{Time-Varying Step-Size}\label{sec:timevar}
The update rule for the stochastic mirror descent with time-varying step size is as follows.
\begin{equation}\label{eq:SMD_timevarying}
w_i = \argmin_w\ \eta_i w^T\nabla L_i(w_{i-1})+D_{\psi}(w,w_{i-1}) ,
\end{equation}
which can be equivalently expressed as $\nabla\psi(w_i)=\nabla\psi(w_{i-1})-\eta_i\nabla L_i(w_{i-1})$, for all $i$.
The main results in this case are as follows.
\begin{lemma}
For any (nonlinear) model $f(\cdot,\cdot)$, any differentiable loss $l(\cdot)$, any parameter $w$ and noise values $\{v_i\}$ that satisfy $y_i =f(x_i,w)+v_i$ for $i=1,\dots,n$, any initialization $w_0$, any step size sequence $\{\eta_i\}$, and any number of steps $T\geq 1$, the following relation holds for the SMD iterates $\{w_i\}$ given in Eq.~\eqref{eq:SMD_timevarying}
\begin{equation}
D_{\psi}(w,w_{0})+ \sum_{i=1}^T \eta_i l(v_i) = D_{\psi}(w,w_T) +\sum_{i=1}^T \left( E_i(w_i,w_{i-1}) +\eta_i D_{L_i}(w,w_{i-1}) \right) ,
\end{equation}
\end{lemma}
\begin{proof}
The proof is straightforward by summing the following equation for all $i=1,\dots,T$
\begin{equation}
D_{\psi}(w,w_{i-1})+\eta_i l(v_i) = D_{\psi}(w,w_i) +E_i(w_i,w_{i-1}) +\eta_i D_{L_i}(w,w_{i-1}) ,
\end{equation}
which can be easily shown in the same way as in the proof of Lemma~\ref{lem:equality_SMD} in Appendix~\ref{sec:proof_of_equality_SMD}.
\end{proof}

\begin{theorem}
Consider any general model $f(\cdot,\cdot)$, and any differentiable loss function $l(\cdot)$ with property $l(0)=l'(0)=0$. For sufficiently small step size, i.e., for any sequence $\{\eta_i\}$ for which $\psi(w)-\eta_i L_i(w)$ is convex for all $i$, the SMD iterates $\{w_i\}$ given by Eq.~\eqref{eq:SMD_timevarying} are the optimal solution to the following minimization problem
\begin{equation}
\min_{\{w_i\}}\max_{w,\{v_i\}}\frac{D_{\psi}(w,w_T)+\sum_{i=1}^{T}\eta_i D_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\sum_{i=1}^{T}\eta_i l(v_i)} .
\end{equation}
Furthermore, the optimal value (achieved by SMD) is $1$.
\end{theorem}
\begin{proof}
The proof is similar to that of Theorem~\ref{thm:SMD}, as presented in Appendix~\ref{sec:proof_of_thm_SMD}. The argument for the upper-bound of $1$ is exactly the same. For the second part of the proof, we use the previous Lemma.
It follows from the convexity of $\psi(w)-\eta_i L_i(w)$ that $E_i(w_i,w_{i-1})\geq 0$, and as a result we have
\begin{equation}
\frac{D_{\psi}(w,w_T)+\sum_{i=1}^{T}\eta_i D_{L_i}(w,w_{i-1})}{D_{\psi}(w,w_0)+\sum_{i=1}^{T}\eta_i l(v_i)} \leq 1
\end{equation}
for SMD updates, which concludes the proof.
\end{proof}
The convergence and implicit regularization results hold similarly, and can be formally stated as follows.
\begin{proposition}
Consider the following two cases.
\begin{enumerate}[label=(\roman*)]
\item $l(\cdot)$ is differentiable and convex and has a unique root at 0, $\psi(\cdot)$ is strictly convex, and the positive sequence $\{\eta_i\}$ is such that $\psi-\eta_i L_i$ is convex for all $i$.
\item $l(\cdot)$ is differentiable and quasi-convex and has zero derivative only at 0, $\psi(\cdot)$ is $\alpha$-strongly convex, and $0<\eta_i\leq\frac{\alpha |y_i-x_i^Tw_{i-1}|}{\|x_i\|^2|l'(y_i-x_i^Tw_{i-1})|}$ for all $i$.
\end{enumerate}

If either (i) or (ii) holds, then for any initialization $w_0$, the SMD iterates given in Eq.~\eqref{eq:SMD_timevarying} converge to
\begin{equation}
w_{\infty}=\argmin_{w\in\mathcal{W}} D_{\psi}(w,w_0) .
\end{equation}
\end{proposition}
\begin{proof}
The proof is similar to that of Proposition~\ref{prop:convergence_SMD}, as provided in Appendix~\ref{sec:proof_of_prop_convergence_SMD}.
\end{proof}

\end{document}


TITLE: The number of cyclic subgroups of order 15 in $\mathbb{Z}_{30} \oplus \mathbb{Z}_{20}$
QUESTION [6 upvotes]: What is the number of cyclic subgroup of order 15 in $\mathbb{Z}_{30} \oplus  \mathbb{Z}_{20}$?
I have counted the number of elements with order 15 in $\mathbb{Z}_{30} \oplus  \mathbb{Z}_{20}$ that is $48$, by counting all possibilities of $(a,b)$ where $a\in\mathbb{Z}_{30}$ , $b \in \mathbb{Z}_{20}$ and  $\def\lcm{\operatorname{lcm}}\lcm(|a|,|b|)=15$.
My argument is that for an element that has order $15$, say $(x,y)$, then
$\langle(x,y)\rangle  =  \langle(x,y)^2\rangle  =   \langle (x,y)^4\rangle    =  \langle (x,y)^7\rangle  = ...=\langle (x,y)^{14}\rangle$
So there are $8$ different elements with order $15$ such that the generate the same subrgroup. So my answer is that there are $\frac{48}{8}=6$ different cyclic subgroups of order 15,
 am i correct? or maybe there are more simpler ways to solve this problem?

REPLY [4 votes]: Provided you correctly counted the elements of order$~15$, your answer is correct. You can indeed count cyclic subgroups by counting their generators (elements or order$~n$) and dividing by the number $\phi(n)$ of generators per cyclic subgroup, since every element of order$~n$ lies in exactly one cyclic subgroup of order$~n$ (the one that it generates).
Here is how I would count the elements of order$~15$. By the Chinese remainder theorem one has $\newcommand\Z[1]{\Bbb Z_{#1}}\Z{30}\cong\Z2\oplus\Z3\oplus\Z5$ and $\Z{20}\cong\Z4\oplus\Z5$, so all in all we are dealing with the group $\Z2\oplus\Z4\oplus\Z3\oplus\Z5^2$. To have order $15$, an element must have a trivial (zero) component in $\Z2$ and $\Z4$, in $\Z3$ it must have as component one of the $2$ generators, and it's component in $\Z5^2$ must be any one of the $24$ nonzero elements. Indeed you get $2\times24=48$ elements of order$~15$.


TITLE: Chern Classes and Stiefel-Whitney Classes
QUESTION [9 upvotes]: I'm trying to understand the relationship between Chern classes and Stiefel-Whitney classes, and I came upon this problem (14-E) in Milnor-Stasheff's Characteristic Classes.
We are asked to define the Stiefel-Whitney classes in the same way as was constructed for Chern classes, using mod 2 coefficients: $w_n(\xi) := e(\xi)$ mod 2 and $w_i(\xi):=(\pi_0^*)^{-1}w_i(\xi_0)$ for $i<n$, where $\pi_0^*: H^{2i}(B)\to H^{2i}(E_0)$ is an isomorphism for $i<n$.
In the problem, it states:

In this approach there is some difficulty in showing that $w_{n-1}(\xi_0)$ belongs to the image of $\pi_0^*.$ It suffices to show that $w_{n-1}(\xi_0)$ restricts to zero in each fiber $F_0$, or equivalently, that the tangent bundle $\tau$ of the $(n-1)$-sphere satisfies $w_{n-1}(\tau)=0$.

This is easy to prove since $e(\tau)=0$ or $2$ depending on odd or even dimensions, so $e(\tau)$ mod $2=0=w_{n-1}(\tau).$ But why does it suffice to prove this? That is, I don't necessarily understand why this proves "$w_{n-1}(E_0)$ belongs to the image of $\pi_0^*$." I'm misunderstanding a step in this logic that is perhaps quite trivial.

REPLY [7 votes]: The map $\pi_0^*$ fits into a long exact sequence including
$$ H^{n-1}(B) \to H^{n-1}(E_0) \to H^n(E, E_0)$$
So, we want to check that $w_{n-1}(\xi_0)$ maps to zero under $H^{n-1}(E_0) \to H^n(E, E_0)$. The class in $H^n(E, E_0)$ is determined by its restrictions to the fibers $H^n(F, F_0)$ which is isomorphic via the corresponding long exact sequence to $H^{n-1}(F_0)$, thus we need to see where $w_{n-1}(\xi_0)$ maps to under the restriction $H^{n-1}(E_0)\to H^{n-1}(F_0)$. At this point, by the definition of $\xi_0$ and naturality, it should be easy to see that $w_{n-1}(\xi_0)$ maps to $w_{n-1}(\tau)$ where $\tau$ is the tangent bundle of the $(n-1)$-sphere.


text:
\begin{document}
\pagenumbering{roman} \setcounter{page}{0}
\title{From the Bethe Ansatz to the Gessel-Viennot Theorem}
\author{R. Brak\dag, J. W. Essam\ddag \, and A. L. Owczarek\dag
        \thanks{{\tt {\rm email:} brak@maths.mu.oz.au,
j.essam@vms.rhbnc.ac.uk, aleks@ms.unimelb.edu.au}} \\

         \dag Department of Mathematics and Statistics,\\
         The University of Melbourne,\\
         Parkville, Victoria 3052, Australia\\

         \ddag Department of Mathematics,\\
         Royal Holloway, University of London,\\
         Egham, Surrey TW20 0EX, England.}
\date{
\begin{center}

	23 February, 1999
\end{center}
}

\maketitle

\begin{abstract}
We state and prove several theorems that demonstrate how the
coordinate Bethe Ansatz for the eigenvectors of suitable transfer
matrices of a generalised inhomogeneous five-vertex model on the
square lattice, given certain conditions hold, is equivalent to the
Gessel-Viennot determinant for the number of configurations of $N$
non-intersecting directed lattice paths, or vicious walkers, with
various boundary conditions. Our theorems are sufficiently general to
allow generalisation to any regular planar lattice.
\vspace{1cm}

\noindent{\bf Key words:} Vicious walkers, Lattice Paths,
Gessel-Viennot Theorem, Bethe Ansatz, Transfer Matrix method.

\end{abstract}
\vfill

\newpage
\pagenumbering{arabic}

\section{Introduction}

\setcounter{page}{1}
The problem of non-intersecting paths or vicious walkers has been
studied by the statistical mechanics community who have been
interested in them as simple models of various polymer and other
physical systems and independently by the combinatorics community who
have been interested in them in connection with binomial determinants.
In statistical mechanics they are generally known as vicious walkers,
a term coined by Fisher \cite{fisher84}, who studied the continuous
version of the model.  Various cases of the lattice problem were later
studied by Forrester
\cite{forrester89,forrester89b,forrester90}.  Independently in the area of
combinatorics the problem of non-intersecting paths was solved by a
very general theorem of Gessel and Viennot \cite{gessel85,gessel89},
following the work of Lindstr\"{o}m \cite{lindstrom73}, and Karlin and
McGregor \cite{karlin59b,karlin59}.  All these studies express the
number of configurations as the value of a
determinant. Non-intersecting walks arose in yet another context, that
of vertex models in statistical mechanics, where it was noticed that
if the vertices of the six-vertex model are drawn in a particular way
they could be interpreted as lattice paths
\cite{wu68a,guttmann98a}.  If one of the vertices had weight zero,
giving a five-vertex model, the resulting paths were
non-intersecting. The vertex models are traditionally solved by
expressing the partition function (a generating function) in terms of
transfer matrices.  The partition function is then evaluated by either
of two very powerful techniques, that of commuting transfer matrices
\cite{baxter82} or by direct diagonalisation of the transfer matrices
using the coordinate Bethe Ansatz \cite{bethe31,lieb67b}. In this
paper we bring the independent results of the two communities together
for the case of $N$ non-intersecting paths.  We will show that the
Bethe Ansatz (from statistical mechanics) and the Gessel-Viennot
Theorem (from combinatorics) are essentially equivalent for a fairly
general problem on the square lattice. The theorems proved should be
easily generalisable to other planar lattices. The connection between the
six-vertex model and non-intersecting path problems, from which this
correspondence stems, has been recently discussed in general terms
\cite{guttmann98a}. Here we shall consider a model equivalent to a
generalised five-vertex model on the square lattice where the
(Boltzmann) weights associated with walk edges are inhomogeneous in
one direction.

\section{The model}

A lattice path or walk in this paper is a walk on a square lattice
rotated $45^{\circ}$ which has steps in only the north-east or
south-east directions, and with sites labelled $(m,y)$ (see figure 1). A set
of walks is \emph{non-intersecting} if they have no sites in common.
We are concerned with enumerating the number of configurations of $N$
non-intersecting walks, starting and ending at given positions, in
various geometries: 1) walks in a plane without boundaries; 2) walks
which are confined to the upper half plane; and 3) walks which are
confined to a strip of a given width, $L$.  More generally, one may be
interested in interacting cases where the walks nearest the boundaries
are attracted or repulsed by contact interactions: combinatorially
this requires knowledge of the number of walks with particular numbers
of contacts with each of the boundaries.  In this paper we shall focus
on case 3 since the other 2 cases can be easily obtained from this
case as limits.

To more easily describe our model we require the following sub-domains
of $\integers^{N}$
\begin{subequations}
	\label{eq:doms}
\begin{align}
	\cS{o}{L}
&=\{y \suchthat 1\le y\le L,
	y\in\integers \text{ and $y$ odd}\},
	\label{eq:stripnoo}\\
	\cS{e}{L}
 &=\{y \suchthat 0\le y\le L,
	y\in\integers \text{ and $y$ even}\},
	\label{eq:stripnoe}\\
	\cS{}{L}
&=\{y \suchthat 0\le y\le L,y\in\integers\},
	\label{eq:stripno}\\
	\cU{o}{L}
&=  \{(y_{1},\ldots,y_{N})\,| \, 1\le y_{1}
		< \ldots <y_{N}\le L, \text{ $y_{i}\in\cS{o}{L}$}\} \label{eq:doms3}\\
	\cU{e}{L}
&= \{(y_{1},\ldots,y_{N})\,| \, 0\le y_{1} <
		\ldots <y_{N}\le L, \text{ $y_{i}\in\cS{e}{L}$}\}
		\label{eq:doms4}\\
	\cU{}{L}
&= \{(y_{1},\ldots,y_{N})\,| \, 0\le y_{1} <
		\ldots <y_{N}\le L, \text{ $y_{i}\in\cS{}{L}$}\}
		\label{eq:doms5}
\end{align}
\end{subequations}
We will use $\cU{p}{L}$ to denote $\cU{o}{L}$ or $\cU{e}{L}$.
Let $N$ non-intersecting walks, confined to a strip of width $L$,
start at $y$-coordinates $\bxi=(\xi_{1},\ldots,\xi_{N})\in\,
\cU{p}{L}$ in column $m=0$ of the lattice sites
and terminate after $t$ steps at $y$-coordinates
$\bxf=(\xf_{1},\ldots,\xf_{N})\in\, \cU{p'}{L}$ in the $t^{th}$
column. If $t$ is even then $p'=p$ else $p'=\bar p$, where $\bar{p}$
is the opposite parity to $p$. We will only consider the case that $L$
is odd so that $|\!\cU{e}{L}\!|=|\!\cU{o}{L}\!|={{\half(L+1)}\choose N}$.  (If
$L$ is even a null space enters the subsequent analysis of the
transfer matrices leading to a distracting complication.) We are
considering paths such that a) if $(m-1,y)$ is the position of a path
in column $m-1$ the only possible positions for that path in column
$m$ are $(m,y^{\prime})$ with $y^{\prime}=y\pm 1$ and $0\le
y^{\prime}\le L$ and b) the non-intersection is defined through the
constraint that if there are $N$ sites occupied at $m=0$ then in each
column of sites ($0\leq m\leq t$) there are exactly $N$ occupied
sites. We generalise the walk problem associated with the five-vertex
problem \cite{wu68a,guttmann98a} by assigning a weight $w(y,y^{\prime})$ to
the lattice edge from site $(m-1,y)$ to $(m,y^{\prime})$ with
$y^{\prime}=y\pm 1$ (see figure 1). Notice that, since
$w(y,y^{\prime})$ is assumed independent of the column index $m$, due
to the square lattice structure the weights are periodic in the $m$
direction with period two: Note if $y\in\cS{p}{L}$ then
$y'\in\cS{\bar{p}}{L}$, and in general $w(y,y')\ne w(y',y)$. For the sake
of generality we also associate an arbitrary weight $v(y^i)$ with each
of the sites occupied at $m=0$. The weight associated with a given set
of walks is the product of $w$ weights over all edges occupied by the
walks multiplied by the product of the $v$ weights for each of the
initial sites occupied. The generating function $\ZNWW_{t}(\bxi\pto
\bxf)$, of
$N$ walks of length $t$ starting at $\by=\bxi$ in column $m=0$ and
finishing at $\by=\bxf$ in column $m=t$ is the sum of these weights
over all sets of walks connecting $\bxi$ and $\bxf$:
\begin{equation}\label{part-def}
\ZNWW_{t}(\bxi\pto \bxf) = \sum_{\mathcal{Y}}\;
\prod_{j=1}^N v(y_j(0))\prod_{m=1}^t  w(y_j(m-1),y_j(m))
\end{equation}
where $y_j(m)$ is the position of the $j^{th}$ walk in column $m$ and
the set $\mathcal{Y}$ is given by
\begin{eqnarray}
\mathcal{Y} & = &\{ y_j(m)|1\leq j \leq N, 0 \leq m \leq t,1\leq y_1(m)< y_2(m) < \cdots < y_N(m) \leq L,
\nonumber \\
	& &  y_j(m)=y_j(m-1)\pm 1 \mbox{ and
} y_j(0) = y_j^i,\; y_j(t) = y_j^f.
\}
\end{eqnarray}
With homogeneous weights away from the boundaries
but extra weights at the boundaries the associated six-vertex model
has been considered in \cite{owczarek89}. However, we note
that in \cite{owczarek89}, and in most other studies of the
six-vertex model, only such properties of the model are calculated
that are averages over all numbers of walks, $N$. Here in contrast we
are considering the generating function for a fixed number of walks, $N$, of a
fixed finite length $t$. We will use the transfer matrix method from
statistical mechanics to find this generating function in terms of a
determinant of one-walk generating functions.

\begin{figure}[ht]
\begin{center}

 \figswitch{file=bethe-to-GV-fig.eps}{width=15cm}

 \end{center}
\caption{\it   Three non-intersecting directed walks of length $t=14$
in a strip of width $L=9$. The variables $m$, $y_j^i$ and $y_j^f$ shown. The
walk closest to the lower wall has weight
$v(1)w(1,2)w(2,3)w(3,2)\cdots w(1,0)w(0,1)$ with $y^i_1=1$ and
$y^f_1=1$.  }
\label{fig:walks}
\end{figure}

Precisely, we will show that the partition or generating function,
$\ZNWW_{t}(\byi\pto\byf)$, for non-intersecting walk configurations of
$N$ walks in which the $j^{th}$ walk starts at $y_j^i$ and arrives at
$y_j^f$ after $t$ steps is given by the following determinant:
\begin{equation}
\ZNWW_{t}({\bf y}^i\pto {\bf y}^f)=
\left|
\begin{array}{cccc}
	\ZSWW_{t}(y_1^i\pto y_1^f)&\ZSWW_{t}(y_1^i\pto y_2^f)&
	   \dots&\ZSWW_{t}(y_1^i\pto y_N^f)\\
	\ZSWW_{t}(y_2^i\pto y_1^f)&\ZSWW_{t}(y_2^i\pto y_2^f)&
	   \dots&\ZSWW_{t}(y_2^i\pto y_N^f)\\
	.&.&.&.\\
	.&.&.&.\\
	.&.&.&.\\
	\ZSWW_{t}(y_N^i\pto y_1^f)&\ZSWW_{t}(y_N^i\pto y_2^f)&
	\dots&\ZSWW_{t}(y_N^i\pto y_N^f)
\end{array}
\right|
\label{eq:det2}
\end{equation}
where $\ZSWW_{t}(y_j^i\pto y_k^f)$ is the generating
function for configurations of a single walk starting at $y_j^i$ and
ending at $y_k^f$ in a strip of width $L$. This is then a
generalisation of the `master formulae' of Fisher (equation (5.9) of
\cite{fisher84}) and of Forrester (equation (4) of \cite{forrester89})
where unweighted non-intersecting walks are considered. Importantly,
this determinantal result is precisely that given by the very general
Gessel-Viennot Theorem \cite{gessel85,gessel89} for this problem: the
walks considered on this lattice with the generalised weights
considered satisfy the conditions of the theorem (see
\cite{guttmann98a} for a discussion of a one wall case with
homogeneous weights).

\section{From Bethe Ansatz to determinant}
\label{sec:N-walkers}

\subsection{Transfer matrix formulation}

The generating function of our walk problem in a strip can be formulated as the
matrix element of a product of so-called transfer matrices (see
below for their precise definition).  This `transfer matrix' contains
the weights of all the possible edge configurations of $N$ walks of
two adjacent columns of sites. As such it is related to an invariant
subspace of the full six-vertex transfer matrix
\cite{guttmann98a}. In other words the non-zero elements of the
six-vertex transfer matrix occur in diagonal blocks each of which is
an ``$N$-walk transfer matrix'' for some $N$. There are of course
several ways of setting up a strip transfer matrix.  The most common
are the site-to-site and the edge-to-edge matrices which add either
edges or sites respectively to the walks.  In the case of the
six-vertex model the edge-to-edge matrix is usually chosen.  Our
choice of vertex-to-vertex (we shall use vertex and site
interchangeably) matrix is determined by the requirements that the
corresponding eigenvalue problem be as simple as possible while
ensuring the non-intersecting constraint can be easily implemented.

The calculation of the generating function using the transfer matrix
formulation then hinges on the spectral decomposition of the matrix.
The matrices we diagonalise will be matrices that add two-steps to the
evaluation of the generating function at a time. However the
generating function is initially constructed in terms of one-step
transfer matrices as these are useful since the non-intersecting condition
is explicit.

\begin{defin}\label{tm-def}
Let $y\in\cS{e}{L} $ and $y'\in\cS{o}{L}$. For $N=1$ the one-step
transfer matrices are defined as
\begin{subequations}\label{eq:t-one}
	\begin{align}
	\left(\Teo\right)_{y,y'}&=
		\begin{cases}
			0         &\text{if $|y-y'|>1$}\\
			 w(y,y')  &\text{if $|y-y'|=1$}
\end{cases}\label{eq:teo}\\
\intertext{and}
	\left(\Toe\right)_{y',y}&=
		\begin{cases}
			0        &\text{if $|y'-y|>1$}\\
			 w(y',y) &\text{if $|y-y'|=1$}.
\end{cases}\label{eq:toe}
\end{align}
\end{subequations}
The $N$-walk transfer matrices for $N>1$ are constructed from
sub-matrices of a direct product of the above $N=1$
matrices:
\begin{subequations}\label{eq:t-N}
	\begin{align}
	(\TNoe)_{\by,\by'}&
	=\left(\bigotimes_{i=1}^{N}\Toe\right)_{\by,\by'}\qquad \qquad
	\text{$\by\in\cU{o}{L}$ and $\by' \in \cU{e}{L}$}
	\label{eq:dptmtoe}\\
\intertext{and}
(\TNeo)_{\by',\by}&
	=\left(\bigotimes_{i=1}^{N}\Teo\right)_{\by',\by}\qquad \qquad
	\text{$\by' \in \cU{e}{L}$ and $\by\in\cU{o}{L}$}
	\label{eq:dptmteo}
\end{align}
\end{subequations}
\end{defin}
Note that since we are only considering $L$ being odd we have that
$\TNoe$ and $\TNeo$ are square matrices and that in general
$\left(\Toe\right)_{y',y}\ne \left(\Teo\right)_{y,y'}$. More
importantly, the restriction of the row and column spaces of the
direct product eliminates the possibility of two walks arriving at the
same lattice point. Furthermore the condition that the one-walker
transfer matrix vanishes for $|y'-y|>1$ prevents the generation of
configurations in which pairs of walks ``cross'' \emph{without}
sharing a common lattice site (only nearest neighbour steps are
allowed in all cases). This ``non-crossing'' condition is
unnecessarily restrictive in the one-walk case. However, for $N>1$, if
further neighbour steps are allowed then, in general, it is \emph{not}
possible to use the Bethe Ansatz. This condition is the analogue of the
``non-crossing condition'' of the Gessel-Viennot Theorem.

The generating function $\ZNWW_{t}(\bxi\pto \bxf)$ of $N$
non-intersecting walks of length $t$ in a strip is related to
$\ZNWW_{t-1}(\bxi\pto \bf{y})$ by recurrence, the coefficients of which
are the elements of one of the two one-step transfer matrices defined
above.  This relationship is given by the following lemma.
\begin{lem}\label{part-tm}
The generating function $\ZNWW_{t}(\bxi\pto \bxf)$ is given for $t>0$, depending
on whether $\bxf \in \cU{e}{L}$ or not, by
\begin{equation}\label{transdef}
\ZNWW_{t}(\bxi\pto \bxf)=
\left\{
\begin{array}{l}
\sum_{\bx \in \cU{e}{L}}\ZNWW_{t-1}(\bxi \pto {\bf y})(\TNeo)_{{\bf y},\bxf}
\qquad\hbox{for}\qquad \bxf \in \cU{o}{L}\\
\\
\sum_{\bx \in \cU{o}{L}}\ZNWW_{t-1}(\bxi\pto {\bf y})(\TNoe)_{{\bf y},\bxf}
\qquad\hbox{for}\qquad \bxf \in \cU{e}{L}\; .
\end{array}
\right.
\end{equation}
\end{lem}
\begin{proof}
A simple proof of this Lemma can be constructed using induction on $t$.
\end{proof}

Together with the initial condition
\begin{equation}
\ZNWW_{0}(\bxi\pto \bxf)= \d_{\bxi,\bxf} V(\bxi),
\end{equation}
where
\begin{equation}\label{factor}
V(\bxi)=\prod_{\a =1}^N v(y^i_\a),
\end{equation}
equation \eqref{transdef} determines $\ZNWW_{t}(\bxi\pto \bxf)$.

A simple corollary of this Lemma (again shown by induction) is that
the partition function can be written in terms of ``two-step''
transfer matrices.
\begin{cor}\label{two-steo-cor}
The generating function $\ZNWW_{t}(\bxi\pto \bxf)$ is given, depending
on whether $t$ is even or odd, as
\begin{subequations}\label{part-tstrans}
\begin{align}\label{part-tstransa}
\ZNWW_{2r}(\bxi\pto \bxf)&=
\left\{
\begin{array}{ll}
V(\bxi)\left((\TNe)^{r}\right)_{\bxi,\bxf}
& \hbox{for}\quad \bxi \in \cU{e}{L} \hbox{ and } \bxf \in \cU{e}{L}\\
\\
V(\bxi)\left((\TNo)^{r}\right)_{\bxi,\bxf}
& \hbox{for}\quad \bxi \in \cU{o}{L} \hbox{ and } \bxf \in \cU{o}{L}
\end{array}
\right.\\
\intertext{or }
\label{part-tstransb}
\ZNWW_{2r+1}(\bxi\pto \bxf)&=
\left\{
\begin{array}{ll}
V(\bxi)\sum_{\bx \in
\cU{e}{L}}\left((\TNe)^{r}\right)_{\bxi,\bx}(\TNeo)_{{\bf y},\bxf}
& \hbox{for}\quad \bxi \in \cU{e}{L} \hbox{ and } \bxf \in \cU{o}{L}\\
\\
V(\bxi)\sum_{\bx \in
\cU{o}{L}}\left((\TNo)^{r}\right)_{\bxi,\bx}(\TNoe)_{{\bf y},\bxf}
& \hbox{for}\quad \bxi \in \cU{o}{L} \hbox{ and } \bxf \in \cU{e}{L}
\end{array}
\right.
\end{align}
\end{subequations}
for $r =0,1,2,\dots$, where the two-step transfer matrices are defined as
\begin{subequations}\label{eq:twostep}
\begin{align}
	\TNe &=\TNeo\, \TNoe \label{eq:twostepa}\\
	\TNo &=\TNoe \,\TNeo.  \label{eq:twostepb}
\end{align}
\end{subequations}
\end{cor}
The two-step transfer matrices correspond to adding \emph{two} steps to the
paths.  We show below that the generating function $\ZNWW_{t}(\bxi\pto
\bxf)$ may in fact be expressed in terms of the eigenvalues and
eigenvectors of the two-step matrices. In general the two-step
matrices are \emph{not} symmetric and hence one has to consider left
and right eigenvectors.  The $N$-walk eigenvectors will be constructed
from the one-walk eigenvectors via the Bethe Ansatz.  Used in this
context the Ansatz expresses the components of the $N$-walk
eigenvectors as a determinant of the components of one-walk
eigenvectors (see (\ref{eq:Bethe}) below).

\subsection{From transfer matrices to determinants}

This section contains our main results in the form of two theorems
that state under what conditions the $N$-walk generating function can
be written as the determinant (\ref{eq:det2}). In summary, our
theorems proven below show that the \emph{equivalence} of the Bethe
Ansatz in the form of equation \eqref{eq:Bethe} and the result of the
Gessel-Viennot Theorem in the form (\ref{eq:stripdet}) rests on
showing that for any given problem the Ansatz is sufficiently good to
provide a spanning (or complete) set of eigenvectors.  This in turn
depends only on the completeness of the one-walk eigenvectors
(conditions of Lemma \ref{lem:cyclic}).

In this paper it is not our purpose to prove that all choices of the
functions $w(y,y')$ which make up the elements of the one-walk
transfer matrices allow for the conditions of our theorems to be
satisfied. However, these theorems have been subsequently used to
analyse some interesting cases in detail \cite{brak98e} where as a
consequence we show that an arbitrary boundary weight on one boundary
(and special weight on the other) with homogeneous weights otherwise
satisfies the conditions of the theorems. Also, we point out that
since the Gessel-Viennot determinant holds for any function $w(y,y')$
it is almost certainly true that our conditions are satisfied always.

It is however our main purpose here to demonstrate how the Bethe
Ansatz gives the solution of the $N$-walk problem \emph{given} the
solution of the one-walk problem.

The first theorem states the conditions under which the $N$-walk
transfer matrices can be diagonalised using a Bethe Ansatz:
the major condition is
that the one-walk transfer matrix problem can be solved --- see
Lemma \ref{lem:cyclic}. The second theorem basically states that if the Bethe
Ansatz gives a complete set of eigenvectors for the $N$-walk problem for any
$N$, then the $N$-walk generating function is a determinant of
one-walk generating functions.

To begin we set up the conditions that define a solution of the
one-walk problem: these will be the conditions our two theorems
require.

\begin{lem}
\label{lem:cyclic}
Suppose that there exist linearly independent sets of column vectors
$\{\evec{o}{R}{k}\}_{k\in\cK_{1}}$ and
  $\{\evec{e}{R}{k}\}_{k\in\cK_{1}}$, where $\cK_{1}$ is
  some index set, which satisfy
\begin{equation}\label{eq:cyclic-rR}
		  \Teo\evec{o}{R}{k}=\l_{k}\evec{e}{R}{k}
		  \qquad\hbox{and}\qquad
		  \Toe\evec{e}{R}{k}=\l_{k}\evec{o}{R}{k}
\end{equation}
with $\l_{k} \in \mathbb{C}$, and which span the column spaces of
$\Teo$ and $\Toe$ respectively (in which case they are said to be
complete).  Further let $\Te$ and $\To$ be defined by
\eqref{eq:twostep} then
\begin{itemize}
\item[(i)]
$\evec{o}{R}{k}$ and $\evec{e}{R}{k}$ are right
  eigenvectors of $\To$ and $\Te$ respectively with
  eigenvalue $\l_{k}^{2}$.

\item [(ii)]
corresponding sets $\{\evec{o}{L}{k}\}_{k\in\cK_{1}}$ and
  $\{\evec{e}{L}{k}\}_{k\in\cK_{1}}$ of row vectors may be found such
  that
\begin{equation}\label{oc}
\evecb{p}{L}{k}\cdot\evec{p}{R}{k'}=\d_{k,k'} \qquad \hbox{and}
\qquad \sum_{k\in\cK_{1}}\evec{p}{R}{k}(y)\evecb{p}{L}{k}(y')=\d_{y,y'}
\end{equation}
for each $p\in\{e,o\}$, where the $*$ denotes complex
conjugation. Note that the vectors of \eqref{oc} have components
indexed by $y$.
\item[(iii)] the row vectors of (ii) satisfy
\begin{equation}\label{eq:cyclic-rL}
\evec{o}{L}{k}\Toe=\l_{k}\evec{e}{L}{k}
		  \qquad\hbox{and}\qquad
\evec{e}{L}{k}\Teo=\l_{k}\evec{o}{L}{k}
\end{equation}
  and also $\evec{o}{L}{k}$ and $\evec{e}{L}{k}$ are left
  eigenvectors of $\To$ and $\Te$ respectively with eigenvalue
  $\l_{k}^{2}$.
\end{itemize}
\end{lem}
Note that since the vectors in \eqref{eq:cyclic-rR} span the space the
cardinality of the index set $\cK_{1}$ is $(L+1)/2$.  The proof of the
lemma is elementary linear algebra and we omit it. Notice that if
$\l_k$ is a solution of \eqref{eq:cyclic-rR} then so is $-\l_k$ with
vector $\evec{e}{R}{k}$ replaced by $-\evec{e}{R}{k}$. These vectors
are clearly not independent and normally sufficient independent
vectors to form a spanning set are obtained by taking only the
positive values of $\l_k$.

From the above left and right one-walk vectors
we now construct the $N$-walk vectors and hence eigenvectors of $\TNe$ and $\TNo$.
\begin{thm}\label{th:det}
	 Let $\TNe$ and $\TNo$, $N>1$, be given by equations
	 \eqref{eq:twostep}. By imposing an arbitrary ordering on the
elements of $\cK_{1}$ define
         \begin{equation}
          \cK_{N}=\{\bk=(k_1,k_2,\dots k_N)|k_i\in\cK_{1}\mbox{ and }
k_1<k_2<\dots < k_N\}
         \end{equation}
         and
         \begin{equation}
		\Lam_{\bk}=\prod_{\a=1}^{N}\l_{k_{\a}}.
		\label{eq:Neval}
	 \end{equation}
         (a) If for  $C\in\{L,R\}$ and
	 $p\in\{e,o\}$, $\{\evec{p}{C}{k}\}_{k\in\cK_{1}}$ satisfy the
conditions of Lemma \ref{lem:cyclic} then the vectors
$\{\Evec{p}{C}{\bk}\}_{\bk\in\cK_{N}}$ given by the Bethe Ansatz,
	\begin{align}
		\Evec{p}{C}{\bk}(\by)=&\sum_{\s\in P_{N}}\e_{\s}
		\prod_{\a=1}^{N}\evec{p}{C}{k_{\s_{\a}}}(y_{\a})
                =\sum_{\s\in P_{N}}\e_{\s}
		\prod_{\a=1}^{N}\evec{p}{C}{k_{{\a}}}(y_{\s_\a})
		\qquad\text{$\bx\in\cU{p}{L}$},
		\label{eq:Bethe}
	\end{align}
	where $P_{N}$ is the set of $N!$ permutations of
$\{1,2,\ldots,N\}$, $\s = (\s_{1}, \s_{2}, \ldots, \s_{N}) \in P_N$
and $\e_{\s}$ is the signature of the permutation $\s$,
        satisfy
        \begin{equation}\label{eq:cyclic-RR}
		  \TNoe\Evec{e}{R}{\bk}=\Lam_{\bk}\Evec{o}{R}{\bk}
		  \qquad\hbox{and}\qquad
		  \TNeo\Evec{o}{R}{\bk}=\Lam_{\bk}\Evec{e}{R}{\bk}.
	\end{equation}
        (b) Moreover the conclusions of parts (i), (ii) and (iii) of Lemma
        \ref{lem:cyclic} hold with $\evec{p}{C}{k}$ replaced by
        $\Evec{p}{C}{\bk}$, $\Teo$ and $\Toe$ replaced by
        $\TNeo$ and $\TNoe$, $\cK_{1}$ replaced by $\cK_{N}$, and
        $\l_k$ replaced by $\Lam_{\bk}$.

\end{thm}
\noindent The proofs of part of this theorem and Theorem \ref{thm:specdecom} require the following result.
\begin{prop}
For $\bk\in\,\cK_{N}$ and $\by \in\,\cU{p}{L}$ let
\begin{equation}
\Phi_\bk(\bx) = \sum_{\s\in P_{N}}\e_{\s}
		\prod_{\a=1}^{N}\phi_{k_{{\s_\a}}}(y_{\a})\qquad\hbox{and}\qquad
\Psi_\bk(\bx) = \sum_{\s\in P_{N}}\e_{\s}
		\prod_{\a=1}^{N}\psi_{k_{\s_\a}}(y_{\a}).
\end{equation}
Also let
\begin{equation}
f(\bk)=\prod_{\a=1}^{N}f(k_{\a})
\end{equation}
then
\begin{equation}\label{ksum}
\sum_{\bk\,\in\,\cK_{N}}f(\bk)\Phi_\bk(\bx)\Psi_\bk(\bx')=\sum_{\s\in P_{N}}\e_{\s}
\prod_{\a=1}^{N}\left(\sum_{k_\a\in\,\cK_1 }f(k_\a)\phi_{k_{{\a}}}
(y_{\a}) \psi_{k_{\a}}(y_{\s_\a}')\right)
\end{equation}
and
\begin{equation}\label{ysum}
\sum_{\by\,\in\,\cU{p}{L}}\Phi_\bk(\bx)\Psi_{\bk'}(\bx)=\sum_{\s\in P_{N}}\e_{\s}
\prod_{\a=1}^{N}\left(\sum_{y_\a\,\in\cS{p}{L}}\phi_{k_{{\a}}}
(y_{\a}) \psi_{k_{\s_\a}'}(y_{\a})\right)
\end{equation}
\end{prop}
\begin{proof}
\begin{align}
\sum_{\bk\,\in\,\cK_{N}}f(\bk)\Phi_\bk(\bx)\Psi_\bk(\bx')=&\sum_{\s\in P_{N}}\e_{\s}
\sum_{\bk\,\in\,\cK_{N}}\sum_{\tau\in P_{N}}\e_{\tau}\prod_{\a=1}^{N}
f(k_\a)\phi_{k_{{\tau_\a}}}(y_{\a})\psi_{k_{{\s_\a}}}(y_{\a}')\\
=&\sum_{\s'\in P_{N}}\e_{\s'}
\sum_{\bk\,\in\,\cK_{N}}\sum_{\tau\in P_{N}}\prod_{\a=1}^{N}
f(k_\a)\phi_{k_{{\tau_\a}}}(y_{\a})\psi_{k_{{\tau_\a}}}(y_{\s'_\a}')
\end{align}
The double sum over permutations, $\tau$ and $\bk\in\cK_N$ is equivalent to summing each
$k_\a$ independently over $\cK_1$ (terms for which two or more components of $\bk$ are
equal make zero contribution) and the first result follows. The second result follows
in the same way by interchanging the roles of $k$ and $y$.
\end{proof}

\begin{proof}({\it of Theorem \ref{th:det}}$\,$)
(a) We first obtain
the cyclic property \eqref{eq:cyclic-RR} as follows.
\begin{subequations}\label{eq:crux}
\begin{align}
\left(\TNoe \Evec{e}{R}{\bk}\right)_\bx
&= \sum_{\by'\in\cU{e}{L}}\sum_{\s\in P_{N}}\e_{\s}
	\left(\TNoe\right)_{\by,\by'}
	\prod_{\a=1}^{N}\evec{e}{R}{k_{\s_{\a}}}(y'_{\a})
	\label{eq:crux1}\\
&= \sum_{\s\in P_{N}}\e_{\s}
	\sum_{\by'\in\cU{e}{L}}
	\prod_{\a=1}^{N}\left(\Toe\right)_{y_{\a},y'_{\a}}
	\evec{e}{R}{k_{\s_{\a}}}(y'_{\a})
	\qquad \left(\hbox{using}\quad\eqref{eq:t-N}\right)\label{eq:crux2} \\
&=\sum_{\s\in P_{N}}\e_{\s}\left[\sum_{y'_{1}\in\cS{e}{L}}
	\left(\Toe\right)_{y_{1},y'_{1}}\evec{e}{R}{k_{\s_{1}}}(y'_{1})
	\right] \ldots
	\left[\sum_{y'_{N}\in\cS{e}{L}}
	\left(\Toe\right)_{y_{N},y'_{N}}
	\evec{e}{R}{k_{\s_{N}}}(y'_{N})
	\right]\label{eq:crux3}\\
&=\sum_{\s\in P_{N}}\e_{\s} \,
	\left[\l_{k_{\s_{1}}} \evec{o}{R}{k_{\s_{1}}}(y_{1})
	\right]
	\ldots
	\left[\l_{k_{\s_{N}}}\evec{o}{R}{k_{\s_{N}}}(y_{N})
	\right] \qquad \left(\hbox{using}\quad\eqref{eq:cyclic-rR}\right)
	\label{eq:crux4}\\
&=  \Lam_{\bk}\, \Evec{o}{R}{\bk}(\by)
 	\end{align}
\end{subequations}
The critical step, and the whole reason for
introducing the Bethe Ansatz, is to enable one to go from
the restricted sums of \eqref{eq:crux2} to the unrestricted
sums in \eqref{eq:crux3}.  This is justified for two
reasons,
\begin{enumerate}
\item since $\Evec{e}{R}{\bk}(\by')$ is a determinant,
if any of the $y_{\a}$'s are equal then $\Evec{e}{R}{\bk}=0$
-- this allows the restriction $y'_{1}<y'_{2}\ldots<y'_{N}$
on the sum to be relaxed to $y'_{1}\le y'_{2}\ldots\le y'_{N}$
\item  the $y_\a$ are in strictly increasing order combined with
the fact that the matrix elements of $\Toe$,
are only non-zero if $|y_{\a}-y'_{\a}|\le 1$ allows the
restriction on the sum  to be removed altogether.
\end{enumerate}
The second part of \eqref{eq:cyclic-RR}
follows mutatis mutandis.

(b) (i) The vector $\Evec{e}{R}{\bk}$ is a right eigenvector of $\TNe$
with eigenvalue $\Lam_{\bk}^{2}$, since
\[
\TNe \Evec{e}{R}{\bk}=\TNeo\TNoe \Evec{e}{R}{\bk}=
\TNeo \Lam_{\bk} \Evec{o}{R}{\bk}= \Lam_{\bk}^{2} \Evec{e}{R}{\bk}
\]
which follows from \eqref{eq:cyclic-RR}. Similarly $\Evec{o}{R}{\bk} $
is a right eigenvector of $\TNo$ with eigenvalue $\Lam_{\bk}^{2}$.

\noindent (ii)
Let us start by deriving the first result of part (ii), namely the
orthogonality and normalisation condition. Using \eqref{ysum}, for
$\bk,\bk'\in\cK_N$
\begin{align}
\sum_{\by \in \cU{p}{L} }\Evecb{p}{L}{\bk} (\bx)
	\Evec{p}{R}{\bk'} (\bx)\notag
=& \sum_{\s\in P_{N}}\e_{\s}
\prod_{\a=1}^{N}\left( \sum_{y_\a\,\in\cS{p}{L}}\evecb{p}{L}{k_\a}
(y_{\a}) \evec{p}{R}{k_{\s_\a}'}(y_{\a}) \right)\notag\\
=& \sum_{\s\in P_{N}}\e_{\s}\prod_{\a=1}^{N}\d_{k_\a,k_{\s_\a}'}
\qquad\left(\hbox{using}\quad\eqref{oc}\right)\notag\\
=&\prod_{\a=1}^{N}\d_{k_\a,k_{\a}'}\notag
\end{align}
since the components of $\bk$ and $\bk'$ are in the same order only the identity
permutation gives a non-zero delta function product. Thus
\begin{equation}\label{ortho}
\Evecb{p}{L}{\bk} \cdot \Evec{p}{R}{\bk} = \d_{\bk,\bk'}.
\end{equation}

Our derivation of the second part of (ii), namely the ``completeness
condition'', closely parallels the derivation of the orthogonality and
normalisation condition. Using
\eqref{ksum}, for $\bx,\bx'\in\cU{p}{L}$
\begin{align}
\sum_{\bk \in \cK_N }\Evec{p}{R}{\bk}(\bx)\Evecb{p}{L}{\bk}(\bx')\notag
=& \sum_{\s\in P_{N}}\e_{\s}
\prod_{\a=1}^{N}\left( \sum_{k_\a\,\in\cK_1}\evec{p}{R}{k_{\a}}(y_{\a})\evecb{p}{L}{k_\a}
(y_{\s_\a}')  \right)\notag\\
=& \sum_{\s\in P_{N}}\e_{\s}\prod_{\a=1}^{N}\d_{y_\a,y_{\s_\a}'}
\qquad\left(\hbox{using}\quad\eqref{oc}\right)\notag\\
=&\prod_{\a=1}^{N}\d_{y_\a,y_{\a}'}\notag
\end{align}
so
\begin{equation}\label{comp}
\sum_{\bk \in \cK_N }\Evec{p}{R}{\bk}(\bx)\Evecb{p}{L}{\bk}(\bx')= \d_{\bx,\bx'}
\end{equation}
Notice that $|\cK_N|= {{\half(L+1)}\choose N}$ which is the row (and column) space
dimension, as it should be for completeness.

\noindent (iii) Using basic linear algebra gives
\begin{equation}\label{eq:cyclic-RR-new}
		  \Evec{o}{L}{\bk}\TNoe=\Evec{e}{L}{\bk}\Lam_{\bk}
		  \qquad\qquad\qquad
		  \Evec{e}{L}{\bk}\TNeo=\Evec{o}{L}{\bk}\Lam_{\bk}
	\end{equation}
and
\begin{equation}\label{eq:cyclic-RR-new-t}
\Evec{e}{L}{\bk}\TNe = \Evec{e}{L}{\bk}\Lam_{\bk}^{2}\qquad\qquad\qquad
\Evec{o}{L}{\bk}\TNo = \Evec{o}{L}{\bk}\Lam_{\bk}^{2}
\end{equation}
\end{proof}

\begin{lem}\label{lem:part}
If the conditions of Theorem \ref{th:det} hold then
\begin{equation}\label{eq:sdN}
		\ZNWW_{t}(\bxi\pto \bxf)=
		V(\bx^i)
		\sum_{\bk\in\cbK}\,\,
		   \Evec{p'}{R}{\bk} (\bxi) \Lam^{t}_{\bk}
			\Evecb{p}{L}{\bk} (\bxf)
\qquad\bxi\in\cU{p'}{L}\text{and}\quad\bxf\in\cU{p}{L}
\end{equation}
where if $t$ is even, $p'=p$ but otherwise $p$ and $p'$ are of opposite parity.
\end{lem}
\begin{proof}
If the conditions of Theorem \ref{th:det} hold then we have that
\eqref{ortho}, \eqref{comp},
\eqref{eq:cyclic-RR-new} and  \eqref{eq:cyclic-RR-new-t} are valid.
Using \eqref{eq:cyclic-RR-new} and \eqref{comp} it follows that
\begin{equation}
(\,\TNoe)_{\bx,\bx'}=\sum_{\bk\in\cbK}\Lam_{\bk}\Evec{o}{R}{\bk} (\bx)\Evecb{e}{L}{\bk} (\bx')
\qquad\hbox{and}\qquad(\,\TNeo)_{\bx,\bx'}=
\sum_{\bk\in\cbK}\Lam_{\bk}\Evec{e}{R}{\bk} (\bx)\Evecb{o}{L}{\bk}
(\bx').
\end{equation}
Also, using \eqref{eq:cyclic-RR-new-t} and \eqref{comp} it follows that
\begin{equation}(\,\TNe)_{\bx,\bx'}=\sum_{\bk\in\cbK}\Lam_{\bk}^2\Evec{e}{R}{\bk} (\bx)\Evecb{e}{L}{\bk} (\bx')
\qquad\hbox{and}\qquad(\,\TNo)_{\bx,\bx'}=
\sum_{\bk\in\cbK}\Lam_\bk^2\Evec{o}{R}{\bk} (\bx)\Evecb{o}{L}{\bk}
(\bx').
\end{equation}
Substituting these into \eqref{part-tstrans} and using \eqref{ortho}
gives the result immediately.

\end{proof}

\begin{thm}
	\label{thm:specdecom}
	 If the conditions of Theorem \ref{th:det} hold then
	 \begin{equation}
		\ZNWW_{t}(\bx^i\pto {\bf y}^f) =
		\det|| \ZSWW_{t}(y^i_\a\pto {y}^f_{\beta})
		||_{\a,\beta=1\ldots N}.
		\label{eq:stripdet}
	\end{equation}
\end{thm}
\begin{proof}
Using \eqref{factor}, \eqref{ksum} and \eqref{eq:sdN} (which follows
from \eqref{oc} by Lemma \ref{lem:part})
\begin{align}
\ZNWW_{t}(\by^i\pto \by^f)
&=\sum_{\s\in P_{N}}\e_{\s}
\prod_{\a=1}^{N}\left(v(y_\a^i)\sum_{k_{\a}\in\,\cK_1}\lambda_{k_{\a}}^t\evec{p'}{R}{k_{\a}}
(y^i_{\a}) \evecb{p}{L}{k_{\a}} (y^f_{\s_\a})\right)
		\notag\\
&= \sum_{\s\in P_N}
		\e_\s  \prod_{\a=1}^N
		\ZSWW_{t}(y^i_\a
		\pto {y}^f_{\s_{\a}}).
		\label{eq:npart6}
\end{align}
which is an expansion of the required determinant.
\end{proof}

Finally, we point out that the result of Theorem \ref{thm:specdecom}
is also the conclusion of the Gessel-Viennot Theorem.

\subsection{One wall and no wall geometries}

When $L > (t-|y^i_N-y^f_N|)/2+\max(y^i_N,y^f_N)$ the walk closest to
the wall at $y=L$ cannot touch it since the $N^{th}$ walk (of $t$
steps) needs at least $|y^i_N-y^f_N|$ steps to go from $y^i_N$ to
$y^f_N$ and any excursion close to the wall from the end point closest
to the wall ($\max(y^i_N,y^f_N)$) needs just as many steps to return
(hence the factor of $1/2$).  Hence, when this condition holds, the
strip generating function, $\ZSWW_{t}(y^i_\a \pto {y}^f_{\beta})$
becomes equal to the generating function for walks that are affected
by only one wall, $\ZSW_{t}(y^i_\a\pto {y}^f_{\beta})$.  Hence taking
the limit $L\to\infty$ gives the following corollary:
\begin{cor} For $\by^{i}\in\cU{p}{L}$ and $\by^{f}\in\cU{p'}{L}$, the
$N$-walk generating function with only one  wall at height $y=0$ is given by,
	\begin{equation}
		\ZNW_{t}(\by^i\pto \by^f)	= \det ||
		\ZSW_{t}(y^i_\a\pto {y}^f_{\beta})
		||_{\a,\beta=1\ldots N}\,.
		\label{eq:semidet}
	\end{equation}
\end{cor}

If we also condition the walk closest to the
wall at $y=0$ so that it cannot touch that wall we will end up with
the ``no boundary'' results.

\section*{Acknowledgements}

Financial support from the Australian Research Council is gratefully
acknowledged by RB and ALO. JWE is grateful for financial support from
the Australian Research Council and for the kind hospitality provided
by the University of Melbourne during which time this research was
begun.

config: arxiv