text:
In this section, we provide experimental evidence for the implicit bias of the learning rate discussed in \Cref{sec:implicit-bias-learn-rate}. Through experiments for low-rank matrix recovery, \Cref{sec:experiment-low-rank} shows that the learning rate ratio $\alpha$ affects the solution that gradient descent converges to, and that an optimal $\alpha$ does not depend on the rank of matrix and sparsity of corruption. Furthermore, \Cref{sec:experiment-image} shows the effectiveness of implicit bias of learning rate in alleviating overfitting for robust image recovery, and demonstrates that our method produces better recovery quality when compared to DIP for varying test images and corruption levels, all with a single model and set of learning parameters.

\begin{figure}
	\begin{subfigure}{0.32\linewidth}
		\centerline{
    \includegraphics[width=1.8in]{RPCA_step_size}}
  \caption{Effect of learning rate ratio $\alpha$}
  \label{fig:RPCA-vary-stepsize}
  \end{subfigure}
  \hfill
	\begin{subfigure}{0.32\linewidth}
		\centerline{
			\includegraphics[width=1.8in]{figs/phase_RPCA_varyPandR_apg}}
			\caption{Convex method \cite{lin2009fast}}
			  \label{fig:RPCA-convex}
	\end{subfigure}
	\hfill
	\begin{subfigure}{0.32\linewidth}
		\centerline{
			\includegraphics[width=1.8in]{figs/phase_RPCA_varyPandR_gd}}
			\caption{Our method}
			\label{fig:RPCA-ours}
	\end{subfigure}
	\caption{\small \textbf{Numerical results for robust PCA} (with $n = 50$). (a) Relative reconstruction error for the output ($\widehat\mX, \widehat\mS$) of our method with varying step size ratio $\alpha$. Here, we set $r=5$ and $p=30\%$. (b, c) Probability of successful recovery over $10$ trials with varying $r$ (y-axis) and $p$ (x-axis). Here, we fixed $\alpha=\sqrt{n}$. White indicates always successful recovery, while black means total failure.
	}\label{fig:RPCA-phase}
\vspace{-14pt}
\end{figure}

\subsection{Robust Recovery of Low-rank Matrices}
\label{sec:experiment-low-rank}
\vspace{-0.3em}

We conduct experiments for a particular case of low-rank matrix recovery problem, namely the robust PCA problem, in which the operator $\mathcal{A}$ is the identity operator. More specifically, the goal is to recovery a low-rank matrix $\mX_\star$ and a sparse matrix $\mS_\star$ from the mixture $\mY = \mX_\star + \mS_\star$, possibly without prior knowledge on the rank $r$ of $\mX_\star$ and the percentage of nonzero entries $p$ of $\mS_\star$. For any given $r$, we generate $\mX_\star \in \mathbb R^{n \times n}$ by setting $\mX_\star = \mU_\star\mU_\star^\top$, where $\mU_\star$ is an $n\times r$ matrix with i.i.d. entries drawn from standard Gaussian distribution. For any given $p$, we generate $\mS_\star \in \mathbb R^{n \times n}$ by sampling uniformly at random $n^2 \cdot p$ locations from the matrix and setting those entries by sampling i.i.d. from a zero-mean Gaussian distribution with standard deviation $10$. We use $n = 50$.

We apply our double over-parameterization method in \eqref{eq:rms-over-1} for the robust PCA problem,

Specifically, we initialize $\mU$ and $\vg$ by drawing i.i.d. entries from zero mean Gaussian distribution with standard deviation $10^{-4}$, and initialize $\vh$ to be the same as $\vg$. The learning rate for $\mU$ as well as for $\{\vg, \vh\}$ are set to $\tau$ and $\alpha \cdot \tau$, respectively, where $\tau = 10^{-4}$ for all experiments.

\myparagraph{Effect of learning rate ratio $\alpha$}
We set $r = 5$ and $p = 30\%$, perform $2\times 10^4$ gradient descent steps and compute reconstruction errors for the output of our algorithm $(\wh\mX, \wh\mS)$ relative to the ground truth $(\mX_\star, \mS_\star)$. \Cref{fig:RPCA-vary-stepsize} illustrates the performance with varying values of $\alpha$. We observe that $\alpha$ affects the solution that the algorithm converges to, which verifies that the learning rate ratio has an implicit regularization effect. Moreover, the best performance is given by $\alpha = \sqrt{n}$, which is in accordance with our theoretical result in \Cref{thm:dynamic-rms}.

\vspace{-0.05in}
\myparagraph{Effect of rank $r$ and outlier ratio $p$ and phase transition} We now fix $\alpha = \sqrt{n}$ and study the ability of our method for recovering matrices of varying rank $r$ with varying percentage of corruption $p$. For each pair $(r, p)$, we apply our method and declare the recovery to be successful if the relative reconstruction error $\frac{\norm{\wh\mX - \mX_\star}{F}}{\norm{\mX_\star}{F}}$ is less than $0.1$. \Cref{fig:RPCA-ours} displays the fraction of successful recovery in $10$ Monte Carlo trials. It shows that a single value of the parameter $\alpha$ leads to correct recovery for a wide range of $r$ and $p$. \Cref{fig:RPCA-convex} shows the fraction of successful recovery for the convex method in \eqref{eq:rpca-cvx-weight} (with the Accelerated Proximal Gradient \cite{lin2009fast} solver \footnote{\scriptsize\url{http://people.eecs.berkeley.edu/~yima/matrix-rank/sample_code.html}}).

\begin{figure}
\captionsetup[subfigure]{labelformat=empty,font=footnotesize,skip=-0.9em}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=13cm 20.2cm 2.5cm 20.5cm, clip,width=\linewidth]{figs/Ours_n05_true.jpg}
	\end{subfigure}
    \begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=3.2cm 20.2cm 12.4cm 20.5cm, clip,width=\linewidth]{figs/Ours_n05_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
	        \includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/DIP_n05_best.jpg}
	        \caption{PSNR $=16.46$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
	        \includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/DIPL1_n05_best.jpg}
	        \caption{PSNR $=29.07$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
	        \includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/Ours_n05_best.jpg}
	        \caption{PSNR $=31.60$}
	\end{subfigure}
	\\[-0.2em]
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=13cm 20.2cm 2.5cm 20.5cm, clip,width=\linewidth]{figs/Ours_peppers_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=3.2cm 20.2cm 12.4cm 20.5cm, clip,width=\linewidth]{figs/Ours_peppers_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/DIP_peppers_best.jpg}
		    \caption{PSNR $=16.63$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/DIPL1_peppers_best.jpg}
			\caption{PSNR $=29.13$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/Ours_peppers_best.jpg}
			\caption{PSNR $=30.76$}
	\end{subfigure}
	\\[-0.2em]
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=13cm 20.2cm 2.5cm 20.5cm, clip,width=\linewidth]{figs/Ours_baboon_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=3.2cm 20.2cm 12.4cm 20.5cm, clip,width=\linewidth]{figs/Ours_baboon_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/DIP_baboon_best.jpg}
			\caption{PSNR $=18.56$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/DIPL1_baboon_best.jpg}
			\caption{PSNR $=20.37$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=2.8cm 16.2cm 2.2cm 16.3cm, clip,width=\linewidth]{figs/Ours_baboon_best.jpg}
			\caption{PSNR $=21.38$}
	\end{subfigure}
	\\[-0.2em]
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=14.7cm 22.1cm 4.2cm 22.2cm, clip,width=\linewidth]{figs/Ours_kodim03_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=4.9cm 22.1cm 14.1cm 22.2cm, clip,width=\linewidth]{figs/Ours_kodim03_true.jpg}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=5.8cm 19.2cm 5.2cm 19.3cm, clip,width=\linewidth]{figs/DIP_kodim03_best.png}
			\caption{PSNR $=16.57$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=5.8cm 19.2cm 5.2cm 19.3cm, clip,width=\linewidth]{figs/DIPL1_kodim03_best.jpg}
			\caption{PSNR $=31.87$}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\includegraphics[trim=5.8cm 19.2cm 5.2cm 19.3cm, clip,width=\linewidth]{figs/Ours_kodim03_best.jpg}
			\caption{PSNR $=32.47$}
	\end{subfigure}
	\\
	\begin{subfigure}{0.195\linewidth}
			\caption{\small  Input}
	\end{subfigure}
	\begin{subfigure}{0.195\linewidth}
			\caption{\small  Groundtruth}
	\end{subfigure}
		\begin{subfigure}{0.195\linewidth}
			\caption{\small  DIP}
	\end{subfigure}
		\begin{subfigure}{0.195\linewidth}
			\caption{\small  DIP-$\ell_1$}
	\end{subfigure}
		\begin{subfigure}{0.195\linewidth}
			\caption{\small  Ours}
	\end{subfigure}

	\caption{\small \textbf{Robust image recovery for salt-and-pepper corruption.} PSNR of the results is overlaid at the bottom of the images. For our method, all cases use the same network width, learning rate, and termination condition. For DIP and DIP-$\ell_1$, case-dependent early stopping is used which is essential for their good performance. Despite that, our method achieves the highest PSNRs and best visual quality.}
	\label{fig:dip}
\vspace{-12pt}
\end{figure}

\vspace{-0.05in}
\subsection{Robust Recovery of Natural Images}
\label{sec:experiment-image}
\vspace{-1mm}
Following \cite{ulyanov2018deep}, we evaluate the performance of our method for robust image recovery using images from a standard dataset\footnote{\scriptsize\url{http://www.cs.tut.fi/~foi/GCF-BM3D/index.html\#ref_results}}. Corruption for the images is synthesized by adding salt-and-pepper noise, where ratio $p$ of randomly chosen pixels are replaced with either $1$ or $0$ (each with $50\%$ probability).

The network $\phi(\bm \theta)$ for our method in \eqref{eq:dip-double} is the same as the denoising network in \cite{ulyanov2018deep}, which has a U-shaped architecture with skip connections. Each layer of the network contains a convolutional layer, a nonlinear LeakyReLU layer and a batch normalization layer. We also follow \cite{ulyanov2018deep} on the initialization of network parameters $\bm \theta$, which is the Kaiming initialization. Meanwhile, we initialize $\vg$ and $\vh$ by i.i.d. zero-mean Gaussian distribution with a standard deviation of $10^{-5}$. We use learning rate $\tau = 1$ and set $\alpha = 500$ for all our experiments below.

\vspace{-0.05in}

\myparagraph{No need to tune model width or terminate early} We compare our method with a variant of DIP that we call DIP-$\ell_1$, which is based on solving $\min_{\bm \theta} \ell(\phi(\bm \theta) - \vy)$ with $\ell(\cdot)$ being $\norm{\cdot}{1}$. As shown in \Cref{fig:DIP-overview}, DIP-$\ell_1$ requires either choosing appropriate network width or early termination to avoid overfitting.
Note that neither of these can be carried out in practice without the true (clean) image.
On the other hand, our method does not require tuning network width or early termination. Its performance continues to improve as training proceeds until stabilises.

\vspace{-0.05in}

\myparagraph{Handling different images and varying corruption levels}
The benefit mentioned above enables our method to handle different images and varying corruption levels \emph{without} the need to tune network width, termination condition and any other learning parameters.
In our experiments, we fix the number of channels in each convolutional layer to be $128$, run $150,\!000$ gradient descent iterations and display the output image.
The results are shown in Figure~\ref{fig:dip} (for four different test images) and Figure~\ref{fig:dip_varying_noise} (for four corruption levels, see Appendix~\ref{sec:extra-exp}).
For DIP and DIP-$\ell_1$, we report the result with the highest PSNR in the learning process (i.e., we perform the best early termination for evaluation purposes -- note that this cannot be carried out in practice).
Despite that, our method obtains better recovery quality in terms of PSNR for all cases.
We display the learning curves for these experiments in Figure~\ref{fig:different_figure} and Figure~\ref{fig:varying_p} (see Appendix~\ref{sec:extra-exp}), which show that our method does not overfit for all cases while DIP-$\ell_1$ requires a case-dependent early termination.


TITLE: Name of a metric space concept
QUESTION [8 upvotes]: I have a metric space with the following property (a bit like having unique geodesics): for any points $a,b,x,y$ with $d(a,b)=d(a,x)+d(x,b)=d(a,y)+d(y,b)$ and $d(a,x)=d(a,y)$, we have $x=y$.  Is there an established name for this?
(UPDATE: the condition $d(a,x)=d(a,y)$ was omitted by mistake in the original question.)

REPLY [3 votes]: It is easy to prove that the completion of your space can be any separable metric space
where metric spheres are nowhere dense.

Does not it scare you?

Answer to the comment:
Not all of your spaces can be embedded into a metric tree.
BTW, there is a nice characterization of subsets in a metric tree:
$$ | x - y | + | a - b | \le \max\{|x-a| + |y-b|,|x-b|+|y-a|\}$$
for all points $x,y,a,b$
(here $|x-y|$ denotes the distance from $x$ to $y$).
In other words, the values
$$X=|x-a|+|y-b|,$$
$$Y=|x-b|+|y-a|,$$
$$Z=|x-y|+|a-b|$$ satisfy ulrtatriangle inequality.
This inequality  can be also thought as a discrete analog of CAT[−∞] inequality.


TITLE: Why does $\sqrt[n]{n} = e^{\frac{\log n}{n}}$?
QUESTION [0 upvotes]: $\sqrt[n]{n} = e^{\frac{\log n}{n}}$
I came upon this equation on this site but with no further explanation and frankly I don't understand how can we get $e^{\frac{\log n}{n}}$ from $\sqrt[n]{n}$.
Thanks in advance.

REPLY [1 votes]: It is a simple application of the logarithm and exponential operators. In fact in general, when $f(x)>0$ you have
$$f(x)^{g(x)}=e^{\ln f(x)^{g(x)}}=e^{g(x)\ln f(x)}\tag 1$$
Hence, in your case,
$$\sqrt[n]{n} \equiv n^{\frac1n}=e^{\frac 1n \ln n}=e^{\frac{\ln n}{n}}$$

REPLY [1 votes]: $e^{\frac{\ln x}{x}}=(e^{\ln x})^{\frac{1}{x}}$
Now we know,  $e^{\ln x}=x$.
So  $e^{\frac{\ln x}{x}}=(e^{\ln x})^{\frac{1}{x}}=\sqrt[x]x$
□


TITLE: Solving the soliton equation without energy
QUESTION [1 upvotes]: In this passage from Srednicki's Quantum Field Theory (page 576)

The solution of interest is time independent, so we can set $\dot\varphi = 0$. We can also rewrite the remaining terms in $E$ as
  \begin{align}
E &= \int_{-\infty}^{+\infty}\mathrm{d}x\Bigl[\tfrac{1}{2}\Bigl(\varphi' - \sqrt{2V(\varphi)}\Bigr)^2 + \sqrt{2V(\varphi)}\varphi'\Bigr] \\
&= \int_{-\infty}^{+\infty}\mathrm{d}x \tfrac{1}{2}\Bigl(\varphi' - \sqrt{2V(\varphi)}\Bigr)^2 + \int_{-v}^{+v}\sqrt{2V(\varphi)}\mathrm{d}\varphi \\
&= \int_{-\infty}^{+\infty}\mathrm{d}x \tfrac{1}{2}\Bigl(\varphi' - \sqrt{2V(\varphi)}\Bigr)^2 + \tfrac{2}{3}(m^2/\lambda)m.\tag{92.5}
\end{align}
  Since the first term in eq. (92.5) is positive, the minimum possible energy is $M \equiv \tfrac{2}{3}(m^2/\lambda)m$; this is much larger than the particle mass $m$ if the theory is weakly coupled ($\lambda \ll m^2$). Requiring the first term in eq. (92.5) to vanish yields $\varphi' = \sqrt{2V(\varphi)}$, which is easily integrated to get
  $$\varphi(x) = v\tanh\Bigl(\tfrac{1}{2}m(x - x_0)\Bigr),\tag{92.6}$$

How do they get the solution (92.6) where the energy E is missing?
I want to get the equation (92.6) from equation(92.5), can you do some process?

REPLY [1 votes]: There are two aspects to this question: a) where do we get the requirement $\varphi' = \sqrt{2 V(\varphi)}$, and b) how do we get 92.6 from that.
a) We're looking for a solution $\varphi(x)$ that minimizes $E$ - we will also want it to be the solution that limits to $\varphi \to \pm v$ as $x\to \pm \infty$.  Eq. 92.5 shows that the energy is a constant term independent of $\varphi$ plus the integral of a positive term (as DJBunk noted above).  The term
$$\int dx \left(\varphi'(x)-\sqrt{2 V(\varphi)}\right)^2 \ge 0$$
since the field is real.  Then its minimum is zero, which occurs if $\varphi'(x)-\sqrt{2 V(\varphi)} = 0$ everywhere.
Srednicki defines $V(\varphi) = \frac{\lambda}{8} (\varphi^2 - v^2)^2$ and $m = \sqrt{\lambda} v$.
b) We can tell that 92.6 is right by plugging it into $\varphi'(x)-\sqrt{2 V(\varphi)} = 0$.  This just takes a bit of algebra and the hyperbolic trig identities - the only hard part is to note that since $|\varphi(x)| \le v$, $\sqrt{ (\varphi^2-v^2)^2} = |\varphi^2-v^2| = v^2-\varphi^2$.
Here's how you get 92.6 if you don't already know the answer:  Plugging in $V(\varphi) = \frac{\lambda}{8} (\varphi^2 - v^2)^2$ to $\varphi'(x)=\sqrt{2 V(\varphi)}$, we get
$$ \varphi'(x) = \frac{\sqrt{\lambda}}{2} \sqrt{ (\varphi^2-v^2)^2} = |\varphi^2-v^2|$$
If we define $\varphi = v \chi$, we get
$$\chi' = \frac{m}{2} |(\chi^2-1)|$$
The solution we are looking for limits to $\chi \to \pm 1$ as $x\to\pm \infty$; I will assume that these are the maxima and minima of the function, i.e. $|(\chi^2-1)| = 1-\chi^2$.  I'm not sure if this assumption can be avoided cleverly - right now, we can just think of it as a guess, and see if there is a solution that satisfies it.  $\chi' = \frac{m}{2} (\chi^2-1)$ is separable and can be integrated directly:
$$\int \frac{d\chi}{1-\chi^2} = \frac{m}{2} \int dx$$
so
$$\tanh^{-1} \chi = \frac{m}{2} x + \textrm{const.}$$
choosing the constant to be $-\frac{m}{2}x_0$ gives $\chi = \tanh\left[\frac{m}{2} (x-x_0)\right]$ or $\varphi(x) = v\tanh\left[\frac{m}{2} (x-x_0)\right]$, which is 92.6


TITLE: I like to know if there is approximated expression of something
QUESTION [0 upvotes]: I like to know if there is approximated expression of below things.
$$e^{-x}\sum^{9}_{k=0}\frac{1}{k!}x^{k}$$
$x$ is not always small.
I know behind part is Maclaurin series but summation range is specified.
How can i approach?
Thank you

REPLY [2 votes]: $$e^{-x}\sum_{k=0}^{9}\frac{x^k}{k!} = \int_{0}^{x}\frac{t^9}{9!}e^{-t}\,dt=1-\int_{x}^{+\infty}\frac{t^9}{9!}e^{-t}dt=1-\frac{x^{10}}{9!}\int_{1}^{+\infty}t^{9}e^{-xt}\,dt.$$


TITLE: Expand into Laurent's Series
QUESTION [0 upvotes]: Expand into Laurent's series after the power of z-a for the following function
$$  f(z)=\frac{z+z^2}{(1-z)^3} $$for a = 0 .
I know the formula for the Laurent's series but I don't know how to apply it.

REPLY [0 votes]: I would start from the expansion of $\dfrac1{1-z}$ to obtain the expansion of $\dfrac 1{(1-z)^3}$:
$$\dfrac 1{(1-z)^3}=\frac12\biggl(\frac1{1-z}\biggr)\!\vphantom{\biggl)}''=\frac12\sum_{n=1}^{\infty}n(n-1)z^{n-2}=\sum_{n=1}^{\infty}\binom n2z^{n-2}$$
(with the convention that $\binom 12=0\,$).
Now multiply by $z$ and $z^2$:
 $$ \frac{z+z^2}{(1-z)^3} =\sum_{n=1}^{\infty}\binom n2z^{n-1}+\sum_{n=1}^{\infty}\binom n2z^{n}=\sum_{n=1}^{\infty}\biggl[\binom n2+\binom{n+1}2\biggr]z^{n}  $$
and simplify the coefficients.


TITLE: Gradient descent for periodic function
QUESTION [1 upvotes]: Problem:
minimize E=$\sum_{t=0}^T [ Y(t)-\sum_{k=0}^K(X(t+k)*cos(k*F+PHI)) ]^2$
where F, PHI - has to be optimized;
Y(t), X(t) 1D arrays are given;
t=0...T; T=1000;
k=0..K; K=10;
I can use FFT and get direct estimation of F and PHi (and it works fine), but my question is: are there other methods which can work in time domain using iterative approach?
I tried to use mini-batch gradient descent, but because the problem has a lot of local minimums, it rarely converges (and strongly depend on initialization).

REPLY [0 votes]: Edit: My main point is that
it's possible to rewrite this as a sum $\sum\limits_{i}g_{i}(F,\phi)$.
(with possibly a very large number of terms)
where, each of these functions has a Lipschitz continuous derivative. This essentially comes from the fact that $\cos$ and it's derivatives are bounded, and the fact that the parameters only interact through linear combinations. That means you can apply gradient descent with a constant step size.
For details, see p.144 at http://www.stat.purdue.edu/~vishy/introml/notes/Optimization.pdf
In any case, that is just show it's possible to design an algorithm which is guaranteed to reach some local minimum, but it depends on where you start.