TITLE: The local lipschitz condition implies differentiability?
QUESTION [8 upvotes]: I know differentiability implies the local lipschitz condition. however, I am not sure the converse.
Actually, I think it might be.
The definition of the local lipschitz condition is that for
$$
f: A \subset \mathbb{R}^m \rightarrow \mathbb{R}^n
$$
and $ \forall x_{0} \in A$, there are a constant $M > 0$ and a $\delta_{0} > 0$ such that $\lVert x- x_{0}\rVert < \delta_{0}$ implies
$$
\lVert f(x) - f(x_{0})\rVert \leq M\lVert x-x_{0}\rVert
$$
And the definition of differentialbility is that $\lVert x-x_{0}\rVert < \delta $ implies
$$
\lVert f(x) - f(x_{0}) - Df(x_{0})(x-x_{0})\rVert < \epsilon \lVert x-x_{0}\rVert
$$

REPLY [11 votes]: No. Consider $f(x))=|x|$, which is Lipschitz but not differentiable.
However, Rademacher's theorem states that a (locally) Lipschitz function is differentiable almost everywhere.

REPLY [6 votes]: Think about $f(x)=|x|$. Is it (globally) Lipschitz continuous? What about differentiable?


TITLE: How to solve this differential equation $y'^2+y^2=C$?
QUESTION [0 upvotes]: I'm struggling to solve this differential equation
$$(y')^2+y^2=C$$
where $C$ is an arbitrary constant. I have no idea how to proceed when $y'$ is squared.

REPLY [1 votes]: Let $$z=\frac{y}{\sqrt{C}},$$ so that $$(z')^2+z^2=1.$$ Hence $$z'=\sqrt{1-z^2}$$ or $$z'=-\sqrt{1-z^2}.$$ Here, the possible cases are that $z=-1,$ $z=1,$ or $-1\lt{z}\lt1.$ For the former two, the solution is already given by the cases themselves. For the latter, $$\frac{z'}{\sqrt{1-z^2}}=\pm1,$$ hence $$\int_0^t\frac{z'}{\sqrt{1-z^2}}\,\mathrm{d}t=\pm{t}=\arcsin[z(t)]-\arcsin[z(0)],$$ hence $$z(t)=\sin(\arcsin[z(0)]\pm{t})=z(0)\cos(t)\pm\sqrt{1-z(0)^2}\sin(t)=z(0)\cos(t)+z'(0)\sin(t).$$ Hence $$y(t)=-\sqrt{C},$$ $$y(t)=\sqrt{C}[z(0)\cos(t)+z'(0)\sin(t)],$$ $$y(t)=\sqrt{C}.$$ Furthermore, you can have piecewise solutions that incorporate the three above. Remember that $1=\sin(\arcsin[z(0)]\pm{t})$ is solved by $$\arcsin[z(0)]\pm{t}=2m\pi+\frac{\pi}2,$$ hence $$t=\mp\arcsin[z(0)]\pm\left(2m\pi+\frac{\pi}2\right),$$ and an analogous solution exists for $-1=\sin(\arcsin[z(0)]\pm{t}),$ so at these points, you can branch off from a sinusoidal function to a constant function, and this gives you infinitely many solution families.


TITLE: why does contour lines intersect at saddle points?
QUESTION [4 upvotes]: Consider functions of two variables. A saddle point of $f(x,y)$ is a point in the domain of $f$ (or on the graph of $f$ by an abuse of language) where the gradient is $\bf 0$, but which is not a local extremum of the function. A classic example is $(0,0)$ for $f(x,y)=y^2-x^2$. However, there are two types of saddle points.
Type I: the graph looks like a saddle.
Type II: the graph does not look like a saddle. e.g. $f(x,y)=x^3$, and $f(x,y)=x^2+y^3$.
I have two questions:
Question 1: How to rigorously define saddle points of the above two types?
Question 2: A folklore theorem says $P$ is a saddle point of type I if and only if the contour lines (aka level curves) intersect at $P$. I don't find a proof of such a result, and I'm not sure if the theorem holds as "if and only if" or just holds in one direction.

REPLY [2 votes]: A reasonable definition for saddle points of type I is the following:

Let $f\colon\mathbf{R}^2\to\mathbf{R}$ be a smooth function, a saddle point of type I of $f$ is a point $p\in\mathbf{R}^2$ such that $\frac{\partial f}{\partial x}(p)=0=\frac{\partial f}{\partial y}(p)$ and $\begin{bmatrix}\frac{\partial^2 f}{\partial x^2}(p) & \frac{\partial^2 f}{\partial x\partial y2}(p)\\\frac{\partial^2 f}{\partial y\partial x}(p) & \frac{\partial^2 f}{\partial y^2}(p)\end{bmatrix}$ has nonpositive determinant.

Regarding the saddle points of type II, you can always say that the previous matrix has zero determinant (it cannot have nonnegative determinant, otherwise $p$ would be a maximum or a minimum). However, from the differential topology view point, this is not such a great definition, since the level sets around such critical points can be very different looking.
Using a standard result called Morse's lemma, around a saddle point of type I, there exist local coordinates such that $f(x,y)=x^2-y^2$, in this local model, it is clear that the level curves $f^{-1}(0)$ intersects at $(0,0)$. The reverse implication is false, a counter example is given by $f(x,y)=x^3-3xy^2$ for which $(0,0)$ is a saddle point of type II, even though $f^{1}(0)$ consists of three transversally intersecting curves.


TITLE: Calculate line integral type 1 $\int_C z\,ds$
QUESTION [0 upvotes]: With $C:x^2+y^2=z^2,y^2=ax$ form point $O(0,0,0)$ to point $A(a,a,a\sqrt2)$.
Calculate line integral type 1:
$$I=\int_C z\,ds$$
I have some problems with this exercise. I have idea that let $x=x(\phi),y=y(\phi),z=z(\phi)\rightarrow I= \int_{\phi_1}^{\phi_2} z(\phi) \sqrt{x(\phi)'+y(\phi)'+z\phi'} \, d\phi$:
First, we have $y^2=ax$, hence $x^2+ax=z^2\rightarrow (x+\frac a 2)^2-z^2=\frac{a^2}{4}$
Hence let $x+\frac{a}{2}=\frac{a}{2} \cosh(\phi),z=\sinh(\phi)$
At point $O(0,0,0) \rightarrow \phi =0$ but the problem is at point $A(a,a,a\sqrt2),\phi $ is a irrational number ( I can't calculate exactly )
Can everyone help me? Thank u for your help

REPLY [0 votes]: If you are having difficulty with the way you have parametrized, you can parametrize the curve as,
$r(x) = (x, \sqrt{ax}, \sqrt {x^2+ax}), \ 0 \leq x \leq a$
Once you find $|r'(x)|$, multiply by $z = \sqrt{x^2+ax}$ and you can get the integrand down to the form $\sqrt{u^2-b^2}$. Finally use $u = b \cosh (v)$ substitution and you are done.
Based on how you are parametrizing,
$r(t) = \left(- \dfrac{a}{2} + \dfrac{a}{2} \cosh (t), a \sinh \left(\dfrac{t}{2}\right), \dfrac{a}{2} \sinh (t) \right)$,
$0 \leq t \leq \cosh^{-1}(3)$
$r'(t) = \dfrac{a}{2} \left(\sinh (t), \cosh \left(\dfrac{t}{2}\right), \cosh(t)\right)$
So integral is,
$\displaystyle \frac{a}{2} \int_0^{\cosh^{-1}(3)}  \sinh(t) \ |r'(t)| \ dt$
Can you take it from here? After simplification,  a substitution of the form $a +  \cosh (t) = b \cosh (u)$ may be required.


TITLE: Two-variable generating functions for Laguerre polynomials
QUESTION [5 upvotes]: Where can I find generating functions for orthogonal polynomials in two variables?
Lebedev's book (Special Functions and their Applications, Dover, 1972) gives a closed form for
$$
\sum_{n=0}^\infty \frac{n!}{\Gamma(n+\alpha+1)} L_n^\alpha(x) L_n^\alpha(y) t^n
$$
as an explicit function of $x,y,t$ (it involves a Bessel function). However, I need to sum over the upper index (when it is an integer), to find
$$
\sum_{k=0}^\infty \frac{n!}{(n+k)!} L_n^k(x) L_n^k(y) t^k = {??}
$$
in a closed form $F(x,y,t)$, for a fixed positive integer $n$. Are generating functions of this kind to be found in the literature? (Not on DLMF, as far as I can see.) A closed form for the previous sum would be great, a pointer to a suitable article would be better.

REPLY [1 votes]: I think that http://arxiv.org/pdf/math-ph/0409066v1 (Multivariate Orthogonal Polynomials (symbolically) page 15, has the representation you are looking for [whether it will help you compute your sum, I am not sure, but maybe their Maple package will do the thinking for you?


text:
\begin{document}

\maketitle
\begin{abstract}
  Motivated by the training of Generative Adversarial Networks (GANs), we study methods for solving minimax problems with additional nonsmooth regularizers.
  We do so by employing \emph{monotone operator} theory, in particular the \emph{Forward-Backward-Forward (FBF)} method, which avoids the known issue of limit cycling by correcting each update by a second gradient evaluation.
  Furthermore, we propose a seemingly new scheme which recycles old gradients to mitigate the additional computational cost.
  In doing so we rediscover a known method, related to \emph{Optimistic Gradient Descent Ascent (OGDA)}.
  For both schemes we prove novel convergence rates for convex-concave minimax problems via a unifying approach. The derived error bounds are in terms of the gap function for the ergodic iterates.
  For the deterministic and the stochastic problem we show a convergence rate of $\mathcal{O}(\nicefrac{1}{k})$ and $\mathcal{O}(\nicefrac{1}{\sqrt{k}})$, respectively.
  We complement our theoretical results with empirical improvements in the training of Wasserstein GANs on the CIFAR10 dataset.
\end{abstract}

\section{Introduction}
\label{sec:intro}
\emph{Generative Adversarial Networks (GANs)}~\cite{GAN} have proven to be a powerful class of generative models, producing for example unseen realistic images.
Two neural networks, called generator and discriminator, compete against each other in a game.
In the special case of a zero sum game this task can be formulated as a minimax (aka saddle point) problem.

Conventionally, GANs are trained using variants of (stochastic) \emph{Gradient Descent Ascent (GDA)} which are known to exhibit oscillatory behavior and thus fail to converge even for simple bilinear saddle point problems, see~\cite{GAN2}.
We therefore propose the use of methods with provable convergence guarantees for (stochastic) convex-concave minimax problems, even though GANs are well known to not warrant these properties.
Along similar considerations an adaptation of the \emph{Extragradient method (EG)}~\cite{extragradient} for the training of GANs was suggested in~\cite{VIP-GAN-gidel}, whereas~\cite{OGDA,OGDA2,OGDA3} studied \emph{Optimistic Gradient Descent Ascent (OGDA)} based on \emph{optimistic mirror descent}~\cite{omd,omd2}.
We however investigate the \emph{Forward-Backward-Forward (FBF)} method~\cite{tseng} from monotone operator theory, which uses two gradient evaluations per update, similar to EG, in order to circumvent the aforementioned issues.

Instead of trying to improve GAN performance via new architectures, loss functions, etc., we contribute to the theoretical foundation of their training from the point of view of optimization.

\paragraph{Contribution.} Establishing the connection between GAN training and \emph{monotone inclusions}~\cite{bc} motivates to use the FBF method, originally designed to solve this type of problems. This approach allows to naturally extend the constrained setting to a regularized one making use of the proximal operator.

We also propose a variant of FBF reusing previous gradients to reduce the computational cost per iteration, which turns out to be a known method, related to OGDA.\ By developing a unifying scheme that captures FBF and a generalization of OGDA, we reveal a hitherto unknown connection.
Using this approach we prove novel non asymptotic convergence statements in terms of the minimax gap for both methods in the context of saddle point problems.
In the deterministic and stochastic setting we obtain rates of $\mathcal{O}(\nicefrac{1}{k})$ and $\mathcal{O}(\nicefrac{1}{\sqrt{k}})$, respectively.
Concluding, we highlight the relevance of our proposed method as well as the role of regularizers by showing empirical improvements in the training of Wasserstein GANs on the CIFAR10 dataset.

\paragraph{Organization.} This paper is structured as follows. In Section~\ref{sec:mon-incl} we highlight the connection of GAN training and monotone inclusions and give an extensive review of methods with convergence guarantees for the latter.

The main results as well as a precise definition of the measure of optimality are discussed in Section~\ref{sec:main}. Concluding, Section~\ref{sec:experiments} illustrates the empirical performance in the training of GANs as well as solving bilinear problems.

\section{GAN training as monotone inclusion}
\label{sec:mon-incl}

The GAN objective was originally cast as a two-player zero-sum game (see~\cite{GAN}) between the discriminator $D_y$ and the generator $G_x$ given by
\begin{equation*}
  \label{eq:gan}
  \min_x \max_y\, \E_{\rho \sim q}[\log(D_y(\rho))] + \E_{\zeta \sim p}[\log(1-D_y(G_x(\zeta)))],
\end{equation*}
exhibiting the aforementioned minimax structure.
Due to problems with vanishing gradients in the training of such models, a successful alternative formulation called \emph{Wasserstein GAN (WGAN)}~\cite{wgan} has been proposed. In this case the minimization tries to reduce the Wasserstein distance between the true distribution $q$ and the one learned by the generator. Reformulating this distance via the Kantorovich Rubinstein duality leads to an inner maximization over 1-Lipschitz functions which are approximated via neural networks, yielding the saddle point problem
\begin{equation*}
  \label{eq:wgan}
  \min_x \max_y\, \E_{\rho \sim q}[D_y(\rho)] - \E_{\zeta \sim p}[D_y(G_x(\zeta))].
\end{equation*}

\subsection{Convex-concave minimax problems}
Due to the observations made in the previous paragraph we study the following abstract minimax problem
\begin{equation}
  \label{eq:stoch-minimax-reg}
  \min_{x\in\R^d} \max_{y\in\R^n} \, \Psi(x,y) :=f(x) + \E_{\xi \sim Q}\left[\Phi(x,y;\xi)\right] - h(y),
\end{equation}
where the convex-concave coupling function $\Phi(x,y) := \E_{\xi \sim Q}\left[\Phi(x,y;\xi)\right]$ is differentiable with $L$-Lipschitz continuous gradient. The proper, convex and lower semicontinuous functions $f:\R^d \to \R\cup\{+\infty\}$ and $h:\R^n \to \R\cup\{+\infty\}$ act as regularizers.
A solution of~\eqref{eq:stoch-minimax-reg} is given by a so-called \emph{saddle point} $(x^*,y^*)$ fulfilling for all $x$ and $y$
\begin{equation}
  \Psi(x^*,y) \le \Psi(x^*,y^*) \le \Psi(x,y^*).
\end{equation}
In the context of two-player games this corresponds to a pair of strategies, where no player can be better off by changing just their own strategy.

For illustrative purposes, we will restrict ourselves for now to the special case of the \emph{deterministic constrained} version of~\eqref{eq:stoch-minimax-reg}, given by
\begin{equation}
  \label{eq:constrained}
  \min_{x\in X} \max_{y\in Y}\, \Phi(x,y)
\end{equation}
where $f$ and $h$ are given by indicator functions of closed convex sets $X$ and $Y$, respectively.

The indicator function $\delta_C$ of a set $C$ is defined as $\delta_C(z)=0$ for $z\in C$ and $\delta_C(z)=+\infty$ otherwise.

\subsection{Minimax problems as monotone inclusions}
If the coupling function $\Phi$ is convex-concave and differentiable then the necessary and sufficient optimality condition can be written as a so-called \emph{monotone inclusion} using
\begin{equation}
  \label{eq:F-from-saddle}
  F(x,y) := (\nabla_x\Phi(x, y), -\nabla_y\Phi(x, y))
\end{equation}
and the \emph{normal cone} $N_\Omega$ of the convex set $\Omega:= X \times Y$.
By denoting $w=(x,y)\in\R^m$ where $m=d+n$, it reads
\begin{equation}
  \label{eq:mon-incl}
  0 \in F(w) + N_\Omega(w).
\end{equation}
The normal cone mapping is given by
\begin{equation}
  N_\Omega(w)=\{v\in \R^m : \langle v,w'-w \rangle\le0 \quad \forall w'\in\Omega\},
\end{equation}
for $w\in\Omega$ and $ N_\Omega(w) = \emptyset $ for $ w \notin \Omega $.
Here, the operators $F$ and $N_\Omega$ satisfy well known properties from convex analysis~\cite{bc}, in particular the first one is monotone (and Lipschitz if $\nabla\Phi$ is so) whereas the latter one is maximal monotone.

We call a, possibly \emph{set-valued}, operator $A$ from $\R^m$ to itself monotone~\cite{bc} if
\begin{equation}
  \langle u - u', z - z'\rangle \ge 0 \quad \forall u\in A(z), u' \in A(z').
\end{equation}

We say $A$ is maximal monotone, if there exists no monotone operator $A'$ such that the graph of $A$ is properly contained in the graph of $A'$.

Problems of type~\eqref{eq:mon-incl} have been studied thoroughly in convex optimization, with the most established solution methods being \textit{Extragradient (aka Korpelevich)}~\cite{extragradient} and \textit{Forward-Backward-Forward (aka Tseng)}~\cite{tseng}.
Both methods are known to generate sequences of iterates converging to a solution of~\eqref{eq:mon-incl}.
Note that in the unconstrained setting (i.e.\ if $\Omega$ is the entire space) both of these algorithms even produce the same iterates.

\subsection{Solving monotone inclusions}
\label{sec:methods}
The connection between monotone inclusions and saddle point problems is of course not new.
The application of Extragradient (EG) to minimax problems has been studied in the seminal paper~\cite{mirror-prox} under the name of \textit{Mirror Prox} and a convergence rate of $\mathcal{O}(\nicefrac1k)$ in terms of the function values has been proven.
Even a stochastic version of the Mirror Prox algorithm has been studied in~\cite{stoch-mirror-prox} with a convergence rate of $\mathcal{O}(\nicefrac{1}{\sqrt{k}})$. Applied to problem~\eqref{eq:mon-incl}, with $P_\Omega$ being the projection onto $ \Omega $, it iterates
\begin{equation}
  \label{eq:eg}
  \text{EG:}
  \left\lfloor \begin{array}{l}
           w_k = P_\Omega[z_k - \alpha_k F(z_k)] \\
           z_{k+1} = P_\Omega[z_k - \alpha_k F(w_k)].
         \end{array}\right.
\end{equation}
The Forward-Backward-Forward (FBF) method has not been studied rigorously for minimax problems yet, despite promising applications in~\cite{bot-michael-rifbf} and its advantage of it only requiring one projection, whereas EG needs two. It is given by
\begin{equation}
  \label{eq:fbf}
  \text{FBF:}
  \left\lfloor \begin{array}{l}
           w_k = P_\Omega[z_k - \alpha_k F(z_k)] \\
           z_{k+1} = w_k + \alpha_k (F(z_k) - F(w_k)).
         \end{array}\right.
\end{equation}
Both, EG and FBF, have the ``disadvantage'' of needing two gradient evaluations per iteration. A possible remedy --- suggested in~\cite{VIP-GAN-gidel} for EG under the name of \emph{extrapolation from the past} --- is to recycle previous gradients.

In a similar fashion we introduce
\begin{equation}
  \label{eq:fbf-past}
  \text{FBFp:}
  \left\lfloor \begin{array}{l}
           w_k = P_\Omega[z_k - \alpha_k F(w_{k-1})] \\
           z_{k+1} = w_k + \alpha_k (F(w_{k-1}) - F(w_k)),
         \end{array}\right.
\end{equation}
where we replaced $F(z_k)$ by $F(w_{k-1})$ twice in~\eqref{eq:fbf}.
As a matter of fact, the above method can be written exclusively in terms of the first variable $w_k$ by incrementing the index $k$ in the first update and then substituting in the second line. This results in
\begin{equation}
  \label{eq:yura-reflection}
  w_{k+1} = P_\Omega\Big[w_k - \alpha_{k+1} F(w_k) +\alpha_k(F(w_{k-1}) - F(w_k))\Big].
\end{equation}
This way we rediscover a known method which was studied in~\cite{yura-mat-reflection} for general monotone inclusions under the name of \emph{forward-reflected-backward}. It reduces to \emph{optimistic mirror descent}~\cite{omd,omd2} in the unconstrained case with constant step size $\alpha_k=\alpha$, giving
\begin{equation}
  \label{eq:optimistic-step}
  w_{k+1} = w_k - \alpha (2F(w_k) - F(w_{k-1}))
\end{equation}
which has been proposed for the training of GANs under the name of \emph{Optimistic Gradient Descent Ascent (OGDA)}, see~\cite{OGDA,OGDA2,OGDA3}.

All of the above methods and extensions rely solely on the monotone operator formulation of the saddle point problem where the two components $x$ and $y$ play a symmetric role. Taking the special minimax structure into consideration,~\cite{aybat-apd} showed convergence of a method that uses an optimistic step~\eqref{eq:optimistic-step} in one component and a regular gradient step in the other, thus requiring less storing of past gradients in comparison to~\eqref{eq:yura-reflection}.

On the downside, however, by reducing the number of required gradient evaluations per iteration, the largest possible step size is reduced from $\nicefrac{1}{L}$ (see~\cite{extragradient} or Section~\ref{sec:main}) to $\nicefrac{1}{2L}$ (see~\cite{VIP-GAN-gidel,yura-mat-reflection,yura-reflection} or Section~\ref{sec:main}). To summarize, the number of required gradient evaluations is halved, but so is the step size, resulting in no clear net gain.

\subsection{Regularizers}
\label{sub:regularizers}

The role of regularizers is well studied in many fields such as statistics~\cite{lasso}, signal processing~\cite{signal-processing} or inverse problems~\cite{ROF-TV-denoising}.
They serve different purposes such as inducing sparsity in the solution or conditioning of the problem.
In the context of deep learning this has been explored from different perspectives, e.g.\ in incremental convex neural networks where neurons with zero weights are removed from the network and new ones are inserted according to different policies, see~\cite{bach-convex-NN,convex-NN,l1-regularization-NN,nonconvex-sparse-NN}.

In the framework of monotone operator theory the optimality condition of the regularized minimax problem~\eqref{eq:stoch-minimax-reg} can be written as

\begin{equation}
  \label{eq:mon-incl-reg}
  0 \in F(w) +  \partial r(w),
\end{equation}
where $r$ is given by $(x,y) \mapsto f(x)+h(y)$. The possibly set-valued operator $\partial r$ denotes the subdifferential of $ r $ and is given by
\begin{equation}
  \partial r(w) := \{v \in \R^m : \langle v, w' - w \rangle + r(w) \le r(w') \quad \forall w'\in\R^m \}.
\end{equation}
The monotone inclusion~\eqref{eq:mon-incl-reg} generalizes~\eqref{eq:mon-incl} in a natural way, since $N_\Omega = \partial \delta_\Omega$.
Similarly, the projection constitutes a special case of the so-called \emph{proximal mapping} which for the function $r$ and $ \lambda > 0 $ is given by
\begin{equation}
  \prox{\lambda r}{w} := \argmin_{w'\in \R^m}\Big\{ r(w') + \frac{1}{2 \lambda} \Vert w' - w \Vert^2\Big\}.
\end{equation}
In particular, the proximal mapping of the indicator $\delta_\Omega$ yields the projection onto the set $\Omega$, i.e.\ $\operatorname{prox}_{\lambda \delta_\Omega} = P_\Omega $.

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

Motivated by the considerations above we study the inclusion problem
\begin{equation}
  \label{eq:main}
  0 \in F(w) + \partial r(w),
\end{equation}
where $F:\R^m \to \R^m$ is a monotone and Lipschitz operator and $r:\R^m \to \R\cup\{+\infty\}$ is a proper convex lower semicontinuous function.

\subsection{Measure of optimality}
\label{sub:measure-of-optimality}
There are two common quantities measuring the quality of a point with respect to the monotone inclusion~\eqref{eq:mon-incl-reg}. The most natural one is the distance to the solution set for which typically only asymptotic convergence can be proved. We will therefore focus on the following \emph{gap function}, given for any $w\in\R^m$ by
\begin{equation}
  \sup_{z \in \R^m}\, \langle F(z), w-z \rangle + r(w) - r(z),
\end{equation}
for which we will be able to prove quantitative convergence rates.
If $r$ is the indicator $\delta_\Omega$ of the compact and convex set $\Omega$ it is clear that the supremum is only taken over $z\in\Omega$ and and will thus be finite.
Since the problem~\eqref{eq:main} is in general unconstrained and the supremum can be infinite we consider instead, as done in e.g.~\cite{nesterov2007dual}, the \emph{restricted} gap where the above supremum is taken over an auxiliary compact set $B\subset\R^m$ instead of the entire space.
Note that the restricted gap is in general only a reasonable measure of optimality for elements of $B$. It is nonnegative on $B$ and zero for points of $B$ which solve~\eqref{eq:main}.
Additionally we want to be able to conclude that if a point $w^*$ has zero gap it solves~\eqref{eq:main}. This is for example the case if $w^*$ is in the interior of $B$, which can always be ensured if $B$ is chosen large enough.

If $F$ arises from a saddle point problem~\eqref{eq:stoch-minimax-reg} meaning that $F$ has the form~\eqref{eq:F-from-saddle}, we want to use a more problem specific measure, the minimax gap, which for a point $w=(u,v)\in\R^d\times\R^n$ is given by
\begin{equation}
  \sup_{(x,y)\in B} \Psi(u,y) - \Psi(x,v).
\end{equation}
This minimax gap fulfills the same properties of being nonnegative on $B$ and zero for solutions of~\eqref{eq:main}. In order to capture both at the same time we define the following unifying gap
\begin{equation}
  \label{eq:unifying-gap}
  G_B(w) := \begin{cases}
    \sup_{(x,y)\in B}\, \Psi(u,y) - \Psi(x,v)  &  \text{if $F$ and $r$ come from~\eqref{eq:stoch-minimax-reg}} \\
    \sup_{z\in B} \,  \langle F(z),w-z \rangle + r(w) - r(z) &  \text{otherwise}.
  \end{cases}
\end{equation}

\subsection{Methods}
We now present a novel unifying scheme for solving problem~\eqref{eq:main}, which generalizes FBF~\eqref{eq:fbf} and in addition recovers the method motivated in~\eqref{eq:fbf-past} as FBFp.
Let us point out again that the latter algorithm was already introduced in~\cite{yura-mat-reflection} and corresponds to OGDA~\cite{omd,OGDA,OGDA2} if $F$ stems from the minimax setting~\eqref{eq:F-from-saddle}.

\begin{algo}[generalized FBF]
  \label{alg:generalized-det-fbf}
  For a starting point $z_0 \in \R^m$ and step sizes $\alpha_k>0$ we consider for all $k \geq 0$
  \begin{equation}
    \left\lfloor \begin{array}{l}
             w_k = \prox{\alpha_k r}{z_k - \alpha_k F(\diamondsuit_k)} \\
             z_{k+1} = w_k + \alpha_k (F(\diamondsuit_k) - F(w_k)).
           \end{array}\right.
       \end{equation}
       For $\diamondsuit_k=z_k$ this reduces to the well known FBF method, whereas $\diamondsuit_k=w_{k-1}$, with the additional initial condition $w_{-1}=z_0$, recycles previous gradients (FBFp).
\end{algo}

Consider the scenario where $F$ is given as an expectation $\E_\xi[F(\cdot\,;\xi)]$, e.g.\ coming from~\eqref{eq:stoch-minimax-reg}, and only a stochastic estimator $F(\cdot\, ;\xi)$ is accessible instead of $F$ itself.
In this case we adapt Algorithm~\ref{alg:generalized-det-fbf} in the following way.
\begin{algo}[generalized stochastic FBF]
  \label{alg:generalized-stoch-fbf}
  For a starting point $z_0 \in \R^m$ and step sizes $\alpha_k>0$ we consider for all $k \geq 0$
  \begin{equation*}
    \left\lfloor \begin{array}{l}
             \xi_k \sim Q \quad(\text{optionally } \eta_k \sim Q)\\
             w_k = \prox{\alpha_k r}{z_k - \alpha_k F(\diamondsuit_k;\triangle_k)} \\
             z_{k+1} = w_k + \alpha_k (F(\diamondsuit_k;\triangle_k) - F(w_k;\xi_k)).
           \end{array}\right.
    \end{equation*}
    For $\diamondsuit_k=z_k$ and $\triangle_k=\eta_k$ this results in a stochastic version of FBF, whereas $\diamondsuit_k=w_{k-1}$ and $\triangle_k = \xi_{k-1}$ recycles previous gradients (stochastic FBFp) with the additional initial condition $w_{-1}=z_0$ and $\xi_{-1}=\eta_0$.
\end{algo}
Even though both methods encompassed by the unifying scheme Algorithm~\ref{alg:generalized-det-fbf} have been studied in the deterministic setting before, the stated convergence results are new. However, we want to point out that the stochastic version of FBFp has not been considered prior to this work.

\subsection{Convergence}

Let in the following $B \subset \R^m$ be the compact set of the restricted (unifying) gap function~\eqref{eq:unifying-gap} with $D:= \sup_{w,z\in B} \Vert z-w \Vert$ denoting its diameter. For convenience in the estimation we assume that the starting point $z_0$ of the discussed methods is in $B$.

\begin{theorem}[deterministic]
  \label{thm:deterministic}
  Let ${(w_k)}_{k\ge0}$ be the sequence generated by Algorithm~\ref{alg:generalized-det-fbf}. If
  \begin{enumerate}[(i)]
    \item FBF, i.e.\ $\diamondsuit_k=z_k$, with step size $\alpha_k=\alpha \le \nicefrac{1}{L}$, or
    \item FBFp, i.e.\ $\diamondsuit_k=w_{k-1}$, with step size $\alpha_k=\alpha \le \nicefrac{1}{2L}$
  \end{enumerate}
  is chosen, then for all $K\ge 1$ the averaged iterates $\bar{w}_K := \frac{1}{K}\sum_{k=0}^{K-1} w_k \,$ fulfill
  \begin{equation}
    G_{B}(\bar{w}_K) \le \frac{D^2}{2\alpha K},
  \end{equation}
  where $G_B$ is the restricted gap defined in~\eqref{eq:unifying-gap}.
\end{theorem}

In order to derive similar convergence statements for the stochastic algorithm we need to assume (standard) properties of the gradient estimator $F(\cdot\,;\xi)$.
\begin{assumption}
  \label{ass:unbiased}
  Unbiasedness: $\E_\xi [F(w;\xi)] = F(w) \, \forall w \in \R^m$.
\end{assumption}

\begin{assumption}
  \label{ass:bounded-var}
  Bounded variance: $\E_\xi [\Vert F(w;\xi) - F(w) \Vert^2] \le \sigma^2 \, \forall w \in \R^m$.
\end{assumption}

In particular we actually only need the above assumption to hold for all iterates $w_k$.
Such an hypothesis is in practice difficult to check, but could be exploited in special cases where additional properties of the variance and boundedness of the iterates are known a priori.

\begin{assumption}
  \label{ass:independent}
  The samples $\xi_k$ are independent of the iterates $w_k$, for all $k\ge0$.
\end{assumption}
Equipped with these assumptions we are now able to proof the statement.

\begin{theorem}[stochastic]
  \label{thm:stoch}
  Let Assumption~\ref{ass:unbiased},~\ref{ass:bounded-var} and~\ref{ass:independent} hold and let ${(w_k)}_{k\ge0}$ be the sequence generated by Algorithm~\ref{alg:generalized-stoch-fbf}. If
  \begin{enumerate}[(i)]
    \item stochastic FBF, i.e.\ $\diamondsuit_k=z_k$ and $\triangle_k=\eta_k$, with step size $\alpha_k \le \alpha  \le \nicefrac{1}{\sqrt{2}L}$, or
    \item stochastic FBFp, i.e.\ $\diamondsuit_k=w_{k-1}$ and $\triangle_k=\xi_{k-1}$, with step size $\alpha_k \le \alpha \le \nicefrac{1}{3L}$
  \end{enumerate}
  is chosen, then for all $K\ge 1$ the averaged iterates $\bar{w}_K := \frac{\sum_{k=0}^{K-1} \alpha_k w_k}{\sum_{k=0}^{K-1} \alpha_k} \,$ fulfill
  \begin{equation}
    \Exp{G_B(\bar{w}_K)} \le \frac{D^2 + 18\sigma^2\sum_{k=0}^{K-1}\alpha^2_k}{2\sum_{k=0}^{K-1}\alpha_k},
  \end{equation}
  where $G_B$ is the restricted gap defined in~\eqref{eq:unifying-gap}.
\end{theorem}
The above theorem exhibits a classical step size dependence~\cite{robbins-monro}, yielding convergence for sequences ${(\alpha_k)}_{k\ge0}$ that are square summable $\sum_{k=0}^{\infty} \alpha_k^2 < +\infty$ but not summable $\sum_{k=0}^{\infty}\alpha_k = +\infty$. Additionally, if in the setting of Theorem~\ref{thm:stoch} the step size is chosen $\alpha_k= \alpha/\sqrt{k+1}$, a convergence rate can be obtained and is given by
\begin{equation}
  \label{eq:stoch-rate}
  \Exp{G_B(\bar{w}_K)} = \mathcal{O}\Big(\frac{1}{\sqrt{K}}\Big).
\end{equation}
If the step size does not go to zero, the gap can usually not be expected to vanish either. However, we can still show decrease in the gap up to a residual stemming from the variance. In particular, for a constant step size $\alpha_k=\alpha$ we have
\begin{equation}
  \label{eq:stoch-constant}
  \Exp{G(\bar{w}_K)} \le \frac{D^2}{2\alpha K} + 9\sigma^2\alpha.
\end{equation}
Additionally, if the number of iterations $K$ is fixed beforehand, a conclusion similar to~\eqref{eq:stoch-rate} can be obtained by choosing $\alpha=\nicefrac{1}{\sqrt{K}}$ in~\eqref{eq:stoch-constant}.

\section{Experiments}
\label{sec:experiments}

Due to the theoretical nature of this work, the aim of this section is rather to validate the results on standard examples and not to strive to achieve new state-of-the-art results. Instead we simply aim to show how the use of methods with convergence guarantees, albeit only in the monotone setting, can yield better training performance.

\subsection{2D toy example}
\label{sec:toy}

Following~\cite{GAN2, VIP-GAN-gidel, mesched-GAN-converge} we consider the canonical example $\min_{x} \max_{y} \, xy$, which illustrates the cycling behavior of (even bilinear) minimax problems, and augment this approach by adding a nonsmooth L1-regularizer for one player, resulting in
\begin{equation}
  \label{eq:2d-toy}
  \min_{x\in\R} \max_{y\in[-1,1]}\, \kappa |x| + xy,
\end{equation}
with $\kappa > 0$.

Figure~\ref{fig:2d-toy} highlights the aforementioned issue of GDA (and its proximal extension PGDA) cycling around the solution. The other methods, for which we display the averaged iterates, however do converge to a solution and show a decrease in the restricted gap according to theory.
Even though the proximal steps provide improvement towards the solution $(0,0)$ and FBF only uses half the amount of evaluations compared to EG, it outperforms the competing algorithms.

\begin{figure}[h!]
  \centering
  \begin{subfigure}[b]{0.49\linewidth}
    \centering
    \includegraphics[width=\linewidth]{plots/all_traj.pdf}
    \caption{Trajectories converging to solution.}
  \end{subfigure}
  \begin{subfigure}[b]{0.49\linewidth}
    \centering
    \includegraphics[width=\linewidth]{plots/gap_function.pdf}
    \caption{Restricted gap function.}
  \end{subfigure}
  \caption{A comparison of the methods presented in Section~\ref{sec:methods} applied to problem~\eqref{eq:2d-toy} with $\kappa=0.01$. \emph{PGDA} denotes (alternating) gradient descent ascent with proximal steps. As mentioned in the introduction it fails to converge. \emph{EGp} denotes the method presented in~\cite{VIP-GAN-gidel} as extrapolation from the past. For the restricted gap we use $B_1=B_2=[-1,1]$.}
  \label{fig:2d-toy}
\end{figure}

\subsection{WGAN trained on CIFAR10}
\label{sec:cifar}

In this section we apply the above proposed techniques from monotone inclusions to the training of Wasserstein GANs making use of the DCGAN architecture~\cite{dcgan}. All models are trained on the CIFAR10 dataset~\cite{cifar10} which consists of 60,000 images in 10 different classes (with 50,000 training images and 10,000 test images) using an NVIDIA RTX 2080Ti GPU.\

We choose to work with the original WGAN formulation including weight clipping, since it includes regularizers innately (the indicator of a box for the weights of the discriminator). Although more recent models like ones for example based on ResNet~\cite{resnet} or SAGAN~\cite{SAGAN} architectures provide better overall performance, they usually do not warrant the use of regularizers.
We do this to highlight the difference between FBF and EG, as without projections or proximal steps they are equivalent and their relevance including state-of-the-art architectures has already been shown~\cite{VIP-GAN-gidel, SVRG-gidel-SAGAN}.

In addition we propose a modification of the WGAN formulation which replaces the box constraint on the discriminator's weights with an L1-regularization, under the name of \emph{WGAN-L1}.
This results in a \emph{soft-thresholding} operation instead of the ``harsh'' clipping.

\begin{table}[h!]
  \centering
  \begin{tabular}{@{\extracolsep{4pt}}lcccc@{}}
    \hline
    & \multicolumn{2}{c}{Inception Score (IS)} & \multicolumn{2}{c}{Fr{\'e}chet Inception Distance (FID)} \\
    \cline{2-3} \cline{4-5}
    & \multirow{2}{*}{clip} & \multirow{2}{*}{prox} & \multirow{2}{*}{clip} & \multirow{2}{*}{prox} \\
    Method &  & & & \\
    \hline
    AltAdam1 & 4.12$\pm$0.06 & 4.43$\pm$0.03 & 56.44$\pm$0.62 & 50.86$\pm$2.17\\
    Extra Adam & 4.07$\pm$0.05 & 4.67$\pm$0.11 & 56.67$\pm$0.61 & 47.24$\pm$1.21\\
    \textbf{FBF Adam} & \textbf{4.54$\pm$0.04} & \textbf{4.68$\pm$0.16} & \textbf{45.85$\pm$0.35} & \textbf{46.60$\pm$0.76}\\
    Optimistic Adam & 4.35$\pm$0.06 & 4.63$\pm$0.13 & 50.41$\pm$0.46 & 47.98$\pm$1.49\\
    \hline
  \end{tabular}
  \vspace{0.2cm}
  \caption{
    The best Inception Score (IS) and Fr{\'e}chet Inception Distance (FID), averaged over 5 runs. The column denoted by \emph{clip} refers the standard formulation WGANs where the weights of the discriminator are clipped after every gradient step to enforce the box constraint, whereas \emph{prox} refers alternative implementation using the $1$-norm of the weights for regularization. The latter provides improvement throughout all considered methods. For both formulations, the FBF method (with Adam update) yields the best results (higher IS and lower FID).}
    \label{tab:is-fid}
\end{table}

Given the ubiquity and dominance of Adam~\cite{adam} as an optimizer for many deep learning related training tasks, instead of using vanilla SGD we opt for Adam updates. This results in a method we call \emph{FBF Adam}. Analogous approaches have been applied in~\cite{VIP-GAN-gidel} and~\cite{OGDA} resulting in \emph{Extra Adam} and \emph{Optimistic Adam}, respectively. We compare the aforementioned methods with the status-quo in GAN training, namely alternating one Adam step for each network: \emph{AltAdam1}.

Our hyperparameter search was limited to the step sizes when using the WGAN-L1 formulation, while all other parameters were kept the same as in~\cite{VIP-GAN-gidel, bot-michael-rifbf}.
It seems noteworthy that in the case of soft-thresholding bigger step sizes performed better with the only exception of AltAdam1.

\begin{figure}[h!]
  \begin{subfigure}[b]{0.33\linewidth}
    \centering
    \includegraphics[width=\linewidth]{plots/IS_clip.png}
  \end{subfigure}
  \begin{subfigure}[b]{0.3\linewidth}
    \centering
    \includegraphics[width=0.7\linewidth]{plots/FBF_adam_sample.png}

  \end{subfigure}
  \begin{subfigure}[b]{0.33\linewidth}
    \centering
    \includegraphics[width=\linewidth]{plots/IS_prox.png}
  \end{subfigure}
  \caption{
    \textbf{Left:} Mean and standard deviation of the IS averaged over 5 runs on the WGAN objective with weight clipping. \textbf{Middle:} Samples from the DCGAN generator trained with the WGAN-L1 objective using the FBF method with Adam updates.
    \textbf{Right:} Mean and standard deviation of the IS averaged over 5 runs on the WGAN-L1 objective using the proximal operator;
  The WGAN-L1 objective improves the IS in comparison to weight clipping and stabilizes the behavior of all considered methods during the training procedure. The advantage of using FBF Adam is most pronounced in the case of weight clipping.}
  \label{fig:gan}
\end{figure}

The two evaluation metrics used are the Inception Score (IS)~\cite{is-original} and the Fr{\'e}chet inception distance (FID)~\cite{fid}, both computed on 50,000 samples. In the case of the IS we use the updated and corrected implementation from~\cite{is-pytorch}. All results are averaged over $5$ runs for each method.

Table~\ref{tab:is-fid} reports the best IS and FID for each method. FBF Adam outperforms all considered competitors with respect to both evaluation metrics with the most significant difference for WGAN with weight clipping (``clip''). One can also see that WGAN-L1 using the proximal operator (``prox'') improves the performance of all considered methods, decreasing the absolute and relative differences. Note that the results with WGAN-L1 are comparable for the three methods with underlying convergence guarantees in the convex-concave case.
Figure~\ref{fig:gan} shows the training progress regarding IS for each method and both problem formulations. The graphs suggest that making use of WGAN-L1 objective has a stabilizing effect during training leading to a smoother and more consistent learning curve --- a property that only FBF Adam seems to exhibit for weight clipping.

\section{Conclusion}
\label{sec:conclusion}

By highlighting the connection between GAN objectives and monotone inclusions, we are able to tackle their training via the Forward-Backward-Forward method which is known to converge to a solution for convex-concave minimax problems. We deepened this theoretical understanding by proving novel convergence rates in terms of the function values.
Since FBF provides a natural way to deal with nonsmooth regularizers via the proximal mapping, we modified the WGAN objective to encompass a $1$-norm instead of the usual weight clipping.
We showed that this formulation provides a benefit for all considered methods, smoothing the training process and improving Inception Score and Fr{\'e}chet Inception Distance.
Moreover FBF outperformed all competitors including the commonly used Gradient-Descent-Ascent method as well as other more principled schemes such as Extragradient or Optimistic GDA, where the Adam optimizer was used for all.
The rigorous theoretical considerations complemented by promising practical results suggest that application of FBF may be fruitful to a wider range of GAN formulations, leading to more reliable training results.

\section*{Acknowledgements}
\label{sec:}

This project has received funding from the doctoral programme \textit{Vienna Graduate School on Computational Optimization (VGSCO)}, FWF (Austrian Science Fund), project W 1260, as well as project P 29809-N32.

config: arxiv


TITLE: Combinatorics: arrangement with permutations of $N$ elements
QUESTION [0 upvotes]: I have a combinatorics problem, and I am not sure of my answer, which seems stupidly large. Could anyone spot the mistake?
I have a set of $7$ unique elements. First, I need to know how many permutations I can get out of those $7$ elements.
(e1, e2, ....)
(e2, e1, ....)

If I am not mistaken, the answer is $7!$.
For each permutation, each element can take a certain number of value:
e1: 1 value
e2: 1 value
e3: 9 values
e4: 13 values
e5: 17 values
e6: 51 values
e7: 51 values

How many possible combination of $7$ values can I get?
e.g. If the permutation set is (e1, e3, e2, e5, e6, e4, e7), I could get:
(e1.val1, e3.val5, e2.val1, e5.val17, e6.val32, e7.val44)

I think it is:
7! * (9*13*17*51*51)

Then for each possible combination, $500$ steps are required (by an algorithm).
Thus, the total number of steps performed is:
7! * (9*13*17*51*51) * 500

If I had run this program on a powerfull workstation, I would have taken that number. But trillions of steps performed by my laptop in a few days seems a bit large.

REPLY [1 votes]: No everything is correct. Note that final value you get is ca. $1.30\times 10^{13}$, which is a formidable number.


TITLE: Confusion between these two combinatorial problems
QUESTION [1 upvotes]: These two problems both come from Hossein Pishro-Nik's Introduction to Probability.
The first problem (which I will explain the set up and the solution):
Suppose we have 20 white phones and 10 black phones. We choose 9 phones at random. What is the probability that we have exactly four black phones.
Solution: The probability of this will be the number of ways we can have 4 black phones over the number of ways we can have any 9 phones.
$$P(\text{exactly four phones}) = \frac{\binom {10} {4} \binom {20} {5}}{\binom {30} {9}} $$
The numerator is the number of ways to select 4 black phones from 10 black phones times the number of ways to select 5 white phones from 20 white phones. The numerator is the number of combinations of 9 we can have from the 30 total phones.
What I don't understand is why selecting the 4 black phones doesn't determine the entire combination. Since the phones have to be black or white, if we say only four of them are black, then the rest have to be black so there's no need to multiply by $\binom {20} {5}$. This reasoning works for the next problem.
Second problem: Suppose we have a 20 by 20 grid. We start at the point $(0,0)$ and make only upward or rightward steps to get to the point $(40, 20).$
Solution: Here choosing the sequence of 10 rightward steps or choosing the sequence of 10 upward steps completely determines the path since we can only move up or right.
As a result, the answer is $ \binom {20}{10}$.
I don't see why the reasoning for the second question wouldn't work for the first question since the choice is binary (literally black or white).

REPLY [0 votes]: If you choose nine telephones at random, the chance that you will have four black telephones is the same as the chance that you will have five white telephones -- you can't have one without the other.
Following your argument, this probability would be
$$ P(\text{$5$ white telephones}) \stackrel?= \frac{\binom{20}{5}}{\binom{30}{9}}. $$
But this comes out to a different result than
$$ P(\text{$4$ black telephones}) \stackrel?= \frac{\binom{10}{4}}{\binom{30}{9}}. $$
So there is something wrong in this way of computing the probability.

Your second example is not a probability question. It's a simple counting question.
One thing that makes the path on the grid simpler is that at each step you really have only two choices: up or right. Unlike the telephones, where each black telephone was a distinct object before your choice (and remains one afterward), and where it makes sense to ask, if the first telephone you chose is black, which black telephone was it, if your first step on the grid is to the right, there's no question of "which rightward step" it was. It can only be the rightward step from $(0,0)$ to $(1,0).$
Also, unlike the telephones, where choosing one telephone as your first telephone does not prevent any other telephone from being chosen as the second one,
making a rightward step from $(0,0)$ to $(1,0)$ rules out a lot of steps that otherwise might have been possible.
For example, after $(0,0)$ to $(1,0)$ you cannot have a rightward step from
$(0,1)$ to $(1,1)$.
You also cannot have an upward step from $(0,0)$ to $(0,1)$.
Yet you could have chosen an upward step from $(0,0)$ to $(0,1)$
and then a rightward step from $(0,1)$ to $(1,1)$
if you had done those two steps first.
So the analogy "the step is either rightward or upward; the telephone is either black or white" is a bad analogy. There are all kinds of constraints on the steps that have no analogous constraints for the telephones, and freedoms of choice of telephones that do not exist for the steps on the grid.
This is why you have to actually consider the mechanics of a problem and not just grab a few numbers from it and throw them into an arbitrary formula.


TITLE: When a structure is a mathematical structure?
QUESTION [2 upvotes]: We know that a group or a topology, for example, are purely mathematical objects. But what, for example, about a turing machine, or a normal-form game? They are also structures, but one could say that they belong to computer science and ecomonics, respectively, and that they are not mathematical structures. But they all are rigorously defined using logic and sets, so, what makes them different to say that one is a mathematical object and another one not?

REPLY [3 votes]: Turing machines and normal-form games are definitely mathematical structures. Although these concepts have applications in computer science or economics, they are also studied as abstract structures in their own right, leaving aside the limitations of any particular computer system or economy.
Many mathematical concepts start out from the consideration of physical "real world" examples, but they become mathematical structures when the essential parts of these examples are abstracted and studied independently. For instance, the whole field of probability and statistics originated from studying practical problems of calculating fair odds in gambling.


TITLE: Real Analysis : $x^n = a$ has only one solution.
QUESTION [1 upvotes]: I have a question regarding the following exercises.
(1)
Let $n \in \mathbb {N}$. For all $a \in \mathbb {R}$ with $a \geq 0$ there exists $x \in \mathbb {R}$  with $x \geq 0$ such that $x^n = a$.
(2) The equation $x^n = a$ has just one solution for $x \geq 0$. That solution is called $n$-th root of $a$.
These two problems seem intuitive. Especially the second one since to me it seems that there is only some small step required to get me the right result / proof. However, Taking the $n$-th root obviously is not the solution.

REPLY [1 votes]: Too trivial?
Uniqueness of solution.
1)$a>0;$
Assume that $x^n =y^n=a.$ Then $x, y >0.$
$(x/y)^n=1$ $\Rightarrow x/y=1;$ $x=y;$
2)$a=0;$
Implies $x=y=0.$
Appended:
$ b:=x/y =1$ is the only real number $b>0$ that satisfies
$b^n=1;$
1)Assume $b>1$.
Then $b^2>b>1$. Continuing inductively
we get  $b^n>1;$
2)Assume $b<1;$
Similarly we get  $b^n<1;$
3)$b=1$ satisfies $b^n=1,$ and
we are done.


TITLE: Derivation of momentum operator
QUESTION [5 upvotes]: From a video lecture on quantum mechanics at MIT OCW I found that you didn't need to know Schrödinger's equation to know the momentum operator which is $\frac{\hbar}{i}\frac{\partial}{\partial x}$. This can be derived from a 'simple' wave function of the type
$$ \psi = Ae^{i(\boldsymbol{\mathbf{k}}\cdot \boldsymbol{\mathbf{r}}- \omega t )} $$
 Where we require eigenvalues for $\mathcal{\hat{p}}$ to be $\hbar k$
My questions are:

I understand the complex notation is for convenience. Since it's a complex exponential it'll give us a real and imaginary wave. Does the imaginary part have any physical significance? Are we to interpret this as two waves in superposition in the complex plane?
As we derive the expression for $\mathcal{\hat{p}}$ for this specific function, how does it guarantee that this is indeed the $\mathcal{\hat{p}}$ for every other arbitrary wave function? Can it be derived besides using the wave function I mentioned?

REPLY [2 votes]: The momentum operator is the generator of shifts. In 3 dimensions ($\hbar =1$
)
\begin{equation*}
(\exp [i\mathbf{a\cdot p}]f)(\mathbf{x})=f(\mathbf{x+a})
\end{equation*}
Expanding in $\mathbf{a}$
\begin{equation*}
i\mathbf{a\cdot p}f(\mathbf{x})=\mathbf{a\cdot }\partial _{\mathbf{x}}f(%
\mathbf{x)}
\end{equation*}
or
\begin{equation*}
\mathbf{p}f(\mathbf{x})=\frac{1}{i}\partial _{\mathbf{x}}f(\mathbf{x)}
\end{equation*}
This does not depend on the particular $f$. In your case
\begin{equation*}
(\exp [i\mathbf{a\cdot p}]\psi )(\mathbf{x},t)=A\exp [i\mathbf{k\cdot (x+a}%
-\omega t)
\end{equation*}
so
\begin{equation*}
\mathbf{p}\psi (\mathbf{x},t)=\mathbf{k}\psi (\mathbf{x},t)
\end{equation*}


TITLE: Norm not differentiable on a dense set of $\mathbb{R}^n$
QUESTION [1 upvotes]: Would you have an example of a norm on $\mathbb{R}^n$ ($n \ge 2$) which is not differentiable on a dense set?

REPLY [3 votes]: I believe the following works: let $f:[-1,1]\to\mathbb R$ be a concave function such that $$f(-x)=f(x)$$ for all $x$, i.e. $f$ is even, and $$f(-1)=f(1)=0.$$ Suppose further that $f$ is not differentiable on a dense set. (This answer should suffice to construct such a function.) Define $$K=\{(x,y)\in\mathbb R^2\mid -f(x) \leq y\leq f(x)\}.$$ There exists a norm $\|\cdot\|$ on $\mathbb R^2$ such that $K$ is precisely the unit ball with respect to $\|\cdot\|$. You may define it by the formula $$\|(x,y)\|=\inf\{r>0\mid (x,y)\in rK\}.$$ (This is the so-called Minkowski functional associated to $K$.)
Now, observe that if $x_0\in[-1,1]$ is a point at which $f$ is non-differentiable, then $\|\cdot\|$ will be non-differentiable along the line $L(x_0)$ through the points $(x_0,f(x_0))$ and $(0,0)$.
Here's a rough sketch of this: suppose $L(x_0)$ is such a line, $a\neq 0$ and $F=\|\cdot\|$ is differentiable at $a(x_0,f(x_0))$. Then, the set of points $(x,y)$ such that $$\langle(\operatorname{grad}F)(a(x_0,f(x_0)),(x,y)\rangle=0$$ provides us with a tangent line to the curve $\|(x,y)\|=a$. (The gradient vector is non-zero, since by homogeneity, $F$ is linear and non-zero along $L(x_0)$ in a small neighborhood of $a(x_0,f(x_0))$.) But the curve $\|x,y\|=a$ is simply a scaled version of the graph of $f$, which is not differentiable at $x$, so it cannot have such a tangent line, contradiction.
Now let $A$ be the set of all points $(a,b)$ lying in some line $L(x)$ such that $f'(x)$ does not exist. Since such $x$ are dense in $[-1,1]$, we can show that $A$ is dense in the plane and we are done.


TITLE: How to obtain this formula for 2+1 dimensional boosts
QUESTION [0 upvotes]: In this paper on anyons, a formula for boost transformations in 2+1 dimensional spacetime is given (equations 2.7--2.10).
The boost transformation here is defined as:
$$\displaystyle B(p) \hat{p} = p$$
where $\hat{p}$ is the rest frame momentum = $(m,0,0)$.
The formula for $B(p)$ is then given to be:
$$\displaystyle B(p) = e^{i \Omega_a(p)J^a} $$
where $J^a$ are representations of the generators of so(2,1), given by ${(J^b)}_{ac}= i{{\epsilon_a}^b}_c$. (The so(2,1) algebra is $[J^a,J^b]=i\epsilon^{abc}J_c$.)
$\Omega_a(p)$ is given by:
$$\displaystyle \Omega_a(p) = \epsilon_{abc} \frac{p^b}{|p|}\eta^c\ln \frac{E+|p|}{m} $$
where $\eta^a = (1,0,0)$ and $E= \sqrt{|p|^2 +m^2}$.
I want to understand how to derive or understand this formula for the boost generator.

REPLY [1 votes]: To boost a vector $(m,0,0)$ to a general vector, $p$, one must do a Lorentz transformation in the direction of $p$. To determine the magnitude, check this Wikipedia article, https://en.wikipedia.org/wiki/Lorentz_transformation, which gives the formula for a general Lorentz transformation:
$$L=\begin{bmatrix}\gamma&-\gamma\beta n_x&-\gamma\beta n_y\\\gamma\beta n_x&1+(\gamma-1)n^2_x&(\gamma-1)n_xn_y\\\gamma\beta n_y&1+(\gamma-1)n_xn_y&(\gamma-1)n_y^2\end{bmatrix}$$
I have suppressed the z index because it is a three dimensional problem. $\gamma$ turns out to be $(1+\dfrac{p^2}{m^2})^{1/2}$ and $\beta$ is $\frac{p}{(p^2+m^2)^{1/2}}$.
Now, it remains to be shown that $L=exp(i\Omega_a(p)J^a)$. Expanding out the argument of the exponential it becomes, $$exp(i\Omega_a(p)J^a)=exp[ln(\frac{E+p}{m})\begin{bmatrix}0&-p_x/p&-p_y/p\\p_x/p&0&0\\p_y/p&0&0\end{bmatrix}]$$. This matrix is equivalent to a rotation matrix corresponding to a rotation by an angle $\theta=ln(\frac{E+P}{m})$ about an axis $\hat{n}=(0,-p_y/p,p_x/p)$ which you can verify by checking page 5 of this article.
Then using the form of the rotation matrix given there and substituting for
$\theta$ we get the answer.


TITLE: Definition of free module
QUESTION [0 upvotes]: i) Let $ M$ be a free $R$-module. By definition $ M = R \oplus R \oplus\cdots\oplus R$ .
Can anyone could explain me why $ M = Rx_1 \oplus\cdots\oplus Rx_n$ where $x_1,\ldots,x_n$ elements of $M$. My idea is to prove that $ R \cong Rx_i$. Is thatthe correct solve?
ii)If $k$ is the quotient ring of $R$ ($R$ an intergal domain), $L$ a finite extension of $k$ and $M$ contains elements of $L$. Then the number of copies of $R$ are the same with $[L:k]$ . If yes what is the prove of that?

REPLY [1 votes]: For (i), this is just two choices of notation for the same thing.  You can write an element of $M$ as $(r_1, r_2, \ldots, r_n)$, or you can write it as $r_1 x_1 + r_2 x_2 + \cdots r_n x_n$.  (So, in the previous notation, $x_1 = (1, 0, 0, \ldots, 0)$, etc.)
For (ii), I don't know what you mean by "M contains elements of L."


TITLE: Rotating the bucket in circular motion without spilling water
QUESTION [6 upvotes]: In the bucket experiment when the bucket reaches the top of the circle why will it have a normal force acting on the water downwards? Doesn't normal force oppose any other force? There is no force acting upwards... (As we are an observer in an inertial frame so we wont consider the centrifugal force because it is a pseudo force)

REPLY [5 votes]: I want to focus on one thing, here. The nature of the normal force.
You write

Doesn't normal force oppose any other force?

which is a easy impression to get when you are introduced to the normal force in the context of things sitting on other things in a gravitational field, but that's not the best way to think about it.
The normal force keeps things from occupying the same space.
So consider a book sitting on the lab bench. It's subject to gravity, and in the absence of other forces would fall. But to fall it would have to occupy the same space as the solid top of the bench. The normal force is the interaction between to two objects that resists their inter-penetrating. In this case it has to provide a force that is equal and opposite to that of gravity to make that happen.
In the case of the water in the bucket, it's inertia would take it in a straight line, gravity modifies that into a parabola, but the sides and bottom of the bucket are moving in a circle for both those things to be true (the bucket goes in a circle and the water goes in a parabola) the water would have to move through the bottom of the bucket. The normal force serves to prevent the water from penetrating the solid material of the bucket and must supply whatever forces (beyond that of gravity) are necessary to cause the motion to be in a circle.


TITLE: Construct an volume form on $\mathbb RP^n$ (n odd) using the antipodal map
QUESTION [3 upvotes]: We have the volume form  $\mu=i^*(\omega)$ on $S^n$, where $$\omega=\sum_{j=1}^{n}(-1)^{j-1}x_{j}dx_{1}\wedge\cdots\wedge \hat{dx_{j}}\wedge\cdots dx_{n+1}$$ is a k-form on $\mathbb R^{n+1}$ and $i:S^n\to \mathbb R^{n+1}$ is the inclusion.
Define the antipodal map $A:S^n\to S^n$ by $x \mapsto -x$. Indeed, $A^*(\mu)=(-1)^{n+1}\mu$. Does this gives us a volume form on $\mathbb R P^n$ for n odd? It seems we have the projection map $p:S^n\to  \mathbb R P^n$, but it's the wrong direction to pull back the form. Any help will be appreciated.

REPLY [1 votes]: HINT: Pull back by local inverses of $p$, and use your computation to check that you get a well-defined form on $\Bbb RP^n$. Alternatively, define a form $\eta$ on $\Bbb RP^n$ by setting its value $\eta([x])(v_1,\dots,v_n)$ to be something in terms of $\mu$, and check that everything is well-defined.


TITLE: How to define states in Markov Chains?
QUESTION [0 upvotes]: For words problems, I'm having trouble defining what state should be in a Markov chain, when the states aren't that obvious. Are there any general procedures that should be followed in order to identify what a state should be?
An example I'm having trouble with would be something like this where to me the states aren't obvious.

REPLY [1 votes]: Here the states of the markov chain are the types of exams (so there are three states). You can tell cause each time we transfer to a new exam according to some probability rule depending on the exam we just had.


TITLE: Is $a^k$ the multiplicative order of $a$ modulo $q$?
QUESTION [0 upvotes]: Let $a>1$ be postive integers and $q$ be a prime such that
$$\left. q \,\middle|\, \frac{a^{a^k}-1}{a-1}\right.,$$
and $m(q)$ be the multiplicative order of $a$ modulo $q$. Prove or disprove $$m(q)=a^k$$
My idea: since
$$a^{a^k}\equiv 1 \pmod q$$
and $(q,a)=1$, so
$$m(q)=a^k$$
Is it right? Thanks.

REPLY [1 votes]: My idea: since $$a^{a^k}\equiv 1 \pmod q$$

That claim would benefit from a simple justification.
That aside, your question is really whether $a^x \equiv 1 \pmod q$ and $(q, a) = 1$ suffices for $m(q) = x$. If you go back to the definition of the multiplicative order, you should see how to construct a counterexample.


TITLE: Question about the hands with one heart and one seven excluding the $7$ of hearts
QUESTION [0 upvotes]: The answer is $\binom{12}1 \binom31 \binom{36}3$ which makes sense. Number $\binom{12}1 \binom31$ accounts for the first two cards. I was wondering why counting the combinations of the other three cards as $\binom{12}3 \binom31 \binom31 \binom31$ doesn't work. We choose three cards out of eleven denominations (can't choose $7$), then choose suits for each card out of available three because hearts are not allowed.

REPLY [0 votes]: So I'm guessing you want to draw a five-card hand so that you have exactly one heart and exactly one seven but not the seven of hearts.
As you say, there are $12$ hearts allowed, so the $12\choose 1$ makes sense. Then there are $3$ sevens allowed so the $3\choose 1$ makes sense.
Now you need three more cards. There were $52$ cards in the deck, but you cannot pick a heart ($13$ of them) or a seven ($3$ of them not double-counting the heart). This gives a factor of $36\choose 3$.
You're question is why we cant write ${12\choose 3}{3\choose 1}{3\choose 1}{3\choose 1}$ to represent picking three denominations, then picking a suit three times. The issue is that you can pick the same denomination more than once. As @pettni noted, you could draw, for example, three sixes. You can verify that ${36\choose 3}\neq {12\choose 1}{3\choose 1}{3\choose 1}{3\choose 1}$.