TITLE: Finding a point at which only certain linear functionals are integral
QUESTION [0 upvotes]: Let $C$ be a full-dimensional rational polyhedral cone in $\Bbb R^d$ with facets $G_1,\ldots,G_n$ . For each $i$, let  $h_i$ be an integer-valued linear functional on $\Bbb R^d$ whose kernel is the span of $G_i$. Here's my question: Choose a subset of the facets. Is it possible to find a point $x$ in $\Bbb R^d$ such that $h_i(x)\in \Bbb Z$ iff $G_i$ is one of our chosen facets?

REPLY [1 votes]: Clearly yes if $d\leq 2$. Clearly yes if $n\leq 3$, since the linear functionals $h_i$ are independent. Clearly no if $d>2$ and $n\geq 4$, as an example $x\geq 0$, $x+y\geq0$, $x+z\geq 0$, $y+z\geq 0$ shows (if $x$, $x+y$, and $x+z$ are integral then $y+z$ is integral as well).


TITLE: Show that $\{\hat {f _n }\} $ converges in measure to $f$
QUESTION [0 upvotes]: I want to show that if $f_n $ converges in measure to $f $ and for each $n$  $\mu ( \{x : |\hat {f _n (x)} -f_n(x) \ge \frac {1 } {n } \} )=\frac {1 } {n } $, then $\{\hat {f _n }\}  $ converges in measure to $f$.

A sequence $\{f _n \} $ of measurable functions is said to converge in measure if there is a measurable function $f $ such that, for any $\epsilon >0$
$$\lim \mu ( \{x : |f _n (x)-f(x) \ge \epsilon \} )=0$$
I sort of know that since $|\hat {f _n } -f |\le |\hat {f _n } -f _n |+ |f _n - f |$, then
$\{x: |\hat {f _n }(x) -f(x) |\ge \epsilon \} \subset \{x:|\hat {f _n }(x) -f _n(x) |+ |f _n(x) - f(x) |\ge \epsilon \} $.
But how can I claim that $\mu (\{x: |\hat {f _n }(x) -f(x) |\ge \epsilon \}) \le \mu ( \{x:|\hat {f _n }(x) -f _n(x) |\ge \epsilon\} )+ \mu(\{x:|f _n(x) - f(x) |\ge \epsilon \}) $
Thanks in advance!

REPLY [1 votes]: Since $|\hat f_n(x) - f(x)| \le |f_n(x) - f(x)| + |\hat f_n(x) - f_n(x)|$, at least one of the terms on the right must be greater than $\frac{\epsilon}{2}$ if the expression on the left is greater than $\epsilon$. That is,
$$
\{ x : |\hat f_n(x) - f(x)| > \epsilon \} \subset \{ x : |f_n(x) - f(x)| > \epsilon/2 \} \cup \{ x : |\hat f_n(x) - f_n(x)| > \epsilon/2 \}.$$ Then
$$ \mu(\{| \hat f_n - f| > \epsilon \}) \le \mu(\{ |f_n - f| > \epsilon/2\}) + \mu(\{ |\hat f_n - f| > \epsilon/2\}).$$
Both terms on the right tend to 0 as $n \to \infty$.


TITLE: Arithmetic Mean Linear?
QUESTION [1 upvotes]: Is a function that finds the arithmetic mean of a set of real numbers a linear function?
So is $\left(X_1 +  X_2 + \cdots +  X_n\right)/n$ linear or not?
I'm not sure because so long as the set stays the same size $n$ could be defined as a constant.

REPLY [2 votes]: To talk about linearity, the domain and range of a function must be vector spaces, in this case over the real numbers. So your first question should be, what vector space do you take the arithmetic mean to be defined on? It turns out you must fix the value of $n$ to get any reasonable vector space with the arithmetic mean defined. If you mix various length sequences, they cannot be added (and extending the shorter sequence by zeros in order to perform the addition is not an option, because this changes its mean value). Once you realise $n$ must be fixed, you should have no difficulty seeing that the arithmetic mean is a linear function.


TITLE: 10 coins probability question
QUESTION [3 upvotes]: We throw 10 coins, what is the probability that one is heads and nine of them are tails. What is the difference if we throw them all at once or one by one.
My thought process:
If we throw them all at once:
We need to get the number of all combinations in the denominator, so that would be: $\frac{10(10-1)}{2}$, the number of valid combinations for us is if we throw them all at once would then be only one, so we would get: $P(\text{All at once})=\frac{1}{45}$
If we throw them one by one, then: $P(\text{One by one})=\frac{10}{2^{10}}$, because the valid combinations are $HTTTTTTTTT$, $THTTTTTTTT$,...,$TTTTTTTTTH$.
Can somebody explain why is there a difference if we throw them all at once vs one by one, is my calulation for all at once even correct?

REPLY [3 votes]: Your calculations for throwing the coins one by one are correct.  You should obtain the same answer if you throw them all at once.  Imagine marking each of the ten coins with a different number (or a distinct color) so that we can distinguish between them.  There are ten possible ways for one of those ten coins to be the one that turns up heads.  Since each of the ten coins has two possible outcomes, there are $2^{10}$ outcomes in the sample space.  Hence, the probability that exactly one heads is obtained is
$$\Pr(\text{exactly one head}) = \frac{10}{2^{10}}$$


TITLE: Adding feet to latitude and longitude and convert points to feet
QUESTION [0 upvotes]: I am having a difficult time trying to figure out how to add feet to a latitude and longitude because I am very unfamiliar with lat and long coordinates. I have found several formulas to try and convert latitude and longitude to feet but I am not sure which ones are correct. For example, this website: http://www.colorado.edu/geography/gcraft/warmup/aquifer/html/distance.html I am not sure how to use or apply this method.
I have the latitude and longitude of two points and I want to be able to find the vector of the points. I believe I have to convert the latitude and longitude to feet in order for this to work. Can anyone please help me out in trying to figure this out?

REPLY [1 votes]: You can use the results given in that website to good approximation as long as the distance between your two points is much less than the radius of the Earth.
If your two points are $A$ and $B$ and their latitudes and longitudes are $\lambda_A$, $\phi_A$, and $\lambda_B$, $\phi_B$ ($\lambda$ is lat, $\phi$ is lon) then the distance between them in latitude is 69.172mi $\times$ ($\lambda_B - \lambda_A$).  (I am assuming $\phi_A$ and $\phi_B$ are in degrees.)
Distance in longitude is a bit more complicated.  The latitudes $\lambda_A$ and $\lambda_B$ should not differ by very much.  (Which is a consequence of what I said above, that the distance between the two points should be much smaller than the radius of the Earth.)  If this is the case, we can settle on a "compromise" $\lambda_C = (\lambda_A+\lambda_B)/2$.  Then, distance in longitude is
$69.172$ mi $\times \cos (\lambda_C) \times (\phi_B - \phi_A)$.
Again, I am assuming that all angle are in degrees.  I am also assuming you will have a $\cos$ function that calculates in terms of degrees.
So now you have your distance in lat and your distance in lon, so there's your vector.  If you calculate as I describe, your numbers will be in miles.  To get feet, multiply them both by 5280 ft/mi.


TITLE: Spotting crankery
QUESTION [40 upvotes]: Underwood Dudley published a book called mathematical cranks that talks about faux proofs throughout history. While it seems to be mostly for entertainment than anything else, I feel it has become more relevant in modern mathematics. Especially with the advent of arXiv, you can obtain research papers before they are peer reviewed by a journal. So how does one tell between a crank proof and a genuine proof? This seems to be tough to discern in general.
For instance Perelman's proof was not submitted to any journal but published online. How did professional mathematicians discern that it was a genuine proof?
So how does one spot a crank proof? It seems that John Baez once (humorously) proposed a "crackpot checklist". Would this seem like a fair criterion?

REPLY [1 votes]: I like to believe I was a legitimate 100% Organic GMO-Free Crank back in high school. I was running around doing things like solving the twin prime conjecture and trying to find a way to solve factoring in polynomial time.
These days i'm not.
So I think I am well suited to answer this. I think the quickest way to differentiate a crank from an actual researcher is just simply competence. They give you a paper, you start reading the paper, and don't try to use any hints or razors, just read that thing line by line until you run into the first sentence that doesn't make sense.
You email back the researcher, and they should be able to elucidate and make that obvious so you can proceed.
When you email back the crank, they will not succeed in making it obvious.
There you go, that is it. That's your crank test. Cranks are dangerous because not all of them believe in conspiracy theories or are angry or make you sign an NDA before your read their paper etc... Some cranks can really slip through the cracks but (assuming you are competent) that test above is really bullet proof.
Unfortunately, none of us can accurately judge our competence and in that case only god can save us because you might think something made sense when really it didn't and the crank thinks that you-thinking-it-made-sense validates their work leading to more crankery that goes undetected.
The only solution to that is going to be computer verified proofs. But we still have a while to go until it is easy to make them as it is to say program in python, and moreover the habit of verifying-proofs-via-computer-as-precursor-to-publishing should have infected the mainstream as widespread as say the pandemic of LaTeX.


TITLE: Inversion of a metric
QUESTION [0 upvotes]: I am currently reading a paper by Bredberg $et.al$ arXiv:1101.2451 titled "From Navier-Stokes to Einstein". In this paper, the authors have considered a metric of the form \begin{eqnarray}ds^2_{p+2} = -r d\tau^2+2 d\tau dr +dx^idx_i\\-2(1-\frac{r}{r_c})v_idx^id\tau-2\frac{v_i}{r_c}dx^idr\\+(1-\frac{r}{r_c})\Big[(v^2+2p)d\tau^2+\frac{v_iv_j}{r_c}dx^idx^j\Big]+\big(\frac{v^2}{r_c}+\frac{2P}{r_c}\Big)d\tau dr\\ +\mathcal{O(\epsilon^3)} \end{eqnarray}
The first line conains terms of the order $\mathcal{O(\epsilon^0)}$, second line of the order $\mathcal{O}(\epsilon)$  and the third line of the order  $\mathcal{O}(\epsilon^2)$. Here $v_i \sim  \mathcal{O}(\epsilon)$, $P \sim  \mathcal{O}(\epsilon^2)$. The authors have considered timelike hypersurfaces $r = r_c$. I am trying to find out the unit normal to these hypersurfaces $n^a$. The Unit normal to these hypersurfaces are given by $n^{\mu}\partial_{\mu} =  \frac{1}{\sqrt{r_c}}\partial_{\tau}+\sqrt{r_c}(1-\frac{P}{r_c})\partial_{r}+\frac{v^i}{\sqrt{r_{c}}}\partial_i+\mathcal{O}(\epsilon^3)$. To achieve this form of the contravariant unit normal $n^a$, i need to invert the metric and find $g^{\mu \nu}$ upto order $\mathcal{O(\epsilon^2)}.$ I am currently stuck in this. Any help regarding the inversion of this metric either via hand or by CAS would be highly regarded. PS: Notation:- the spacetime dimension is $p+2$ with $\tau$ being the time coordinate ,$r$ being the radial coordinate and $i = 1,2,....p$ being the angular coordinates.

REPLY [2 votes]: I am assuming that you're working with the background field method formalism, where we define
$$g_{\mu \nu} = \bar{g}_{\mu \nu} + h_{\mu \nu}$$
so that every other quantity is expressed as an infinite series in $h_{\mu \nu}$. Then, the inverse metric up to $\mathcal{O}(h^2)$ is given by
$$g^{\mu \nu } = \bar{g}^{\mu \nu } - h^{\mu \nu } + h_{\alpha }{}^{\nu } h^{\mu \alpha }$$
which you can easily compute once you know $\bar{g}_{\mu \nu }$ and $h_{\mu \nu }$. Note that all contractions, traces, etc. are taken with respect to the background metric $\bar{g}_{\mu \nu}$.


TITLE: Calculate interests
QUESTION [2 upvotes]: Simply wants to calculate interests of an initial amount $N$, with a monthly payback  $m$, and a year interest rate of $R$
I guess the interests are not cumulated each month, but just at the end of the year.
Yet each month the total amount is decremented of 1 payback.
So it does $(N-6m)R$ interests at the end of the first year
2nd year initial amount: $N-12m+(N-6m)R$
2nd year interests: $(N-18m+(N-6m)R)R$
(... while the amount is positive)
I don't find any easy way to recurse it, if it's possible?
Edit
seeing comments, I think rather interests are added each month
so with $r=R/12$
1st month interests: $(Nr) +$
2nd month interests: $(N-m+Nr)r +$
3rd month interests: $( (N-m+Nr)(1+r) -m )r +$
4th month interests: $( (N-m+Nr)(1+r)^2 -m(1+r) -m )r +$
5th month interests: $( (N-m+Nr)(1+r)^3 -m(1+r)^2 -m(1+r) -m )r +$
6th month interests: $( (N-m+Nr)(1+r)^4 -m(1+r)^3 -m(1+r)^2 -m(1+r) -m )r +$
...
xth month interests: $( (N-m+Nr)(1+r)^x -m((1+r)^x-1)/r )r $
$= (Nr-m)(1+r)^{i+1} +m$
$= I(x)$
so the loan interests after x months could be calculated   with:
$\sum_{1..x} \ I(y)  = (x-1)m+(Nr-m)(1+r)^2((1+r)^x-1)/r$
but not sure if it's correct...
the yth month intial amount is  $I(y)/r = 1/r*( (1+r)^{y+1} *(Nr-m) +m)$ that helps to  know when the loan is finished
@Limitless I'm going to check if it gives same result with your answer

REPLY [3 votes]: Let $V(y,b;N,m,r)$ calculate the value of the interest of an initial amount of money, $N$, put into an account on the $b$th month with a monthly payback of $m$ and a yearly interest rate of $r$ at the end of the $y$th year.
Naturally, for $V(0,b;N,m,r)$ we have $N$ since this is just the initial amount and $0$ years have passed. At the end of year one, we have $N+(N-(12-b)m)r=N+(N-12m+bm)r$. This is because the money is put in at the $b$th month and $(12-b)$ months remain in the year. Thus, we have $(12-b)$ monthly paybacks, and that is where we get $(N-(12-b)m)$. Given that $(N-(12-b)m)$ is the yearly balance in the account at the end of the year, it accrues an interest of $(N-(12-b)m)r$. Thus, the total value at the end of the year is that (the interest accrued) added to the original, so we have $N+(N-(12-b)m)r=N+(N-12m+bm)r$.
For the end of the second year, we have $N+(N-12m+bm)r+[N+(N-12m+bm)r-12m]r$. If we let $N_1=N+(N-12m+bm)r$, this makes much more sense: $$N+(N-12m+bm)r+[N+(N-12m+bm)r-12m]r=N_1+[N_1-12m]r;$$
that is, it's simply the amount of year one, $N_1$, plus the interest accrued after the $12$ monthly paybacks (the interest accrued being the $[N_1-12m]r$).
For the end of the third year, we have $N_1+[N_1-12m]r+(N_1+[N_1-12m]r-12m)r$. In other words, if we let $N_y=V(y,b;N,m,r)$, our recurrence becomes almost obvious: $N_x=N_{x-1}+(N_{x-1}-12m)r$. So, your recurrence is:
$$V(y,b;N,m,r)=V(y-1,b;N,m,r)+\left[V(y-1,b;N,m,r)-12m\right]r,$$
or, using the $N_y$ notation,
$$N_x=N_{x-1}+(N_{x-1}-12m)r.$$
Addendum: Solving the Recursion
To solve the recursion, I first put it into a nicer form: $$N_x=N_{x-1}+rN_{x-1}-12mr=(1+r)N_{x-1}-12mr.$$ Now, let $C=-12mr$ and $u=1+r$. We have, then,
$$N_{x}=(1+r)N_{x-1}-12mr=uN_{x-1}+C.$$
As we continue putting the recursion inside itself, we see a pattern:
$$\begin{align}
N_x&=uN_{x-1}+C\\
&=u(uN_{x-2}+C)+C\\
&=u^2N_{x-2}+uC+C\\
&=u^2(uN_{x-3}+C)+uC+C\\
&=u^3N_{x-3}+u^2C+uC+C\\
&=\dots
\end{align}
$$
In other words, we're noticing that if we continue this until we're at $N_2$, we have (note: we're not going all the way back to $N_1$ or $N_0$ since this pattern begins at $N_2$):
$$N_x=u^{x-2}N_{2}+\left(\sum_{0 \le i \le x-3}u^i\right)C.$$
The sum has a closed form since it is the canonical geometric sum. Its closed form is simply $\frac{1-u^{x-2}}{1-u}$. Thus, we have:
$$N_x=u^{x-2}N_2+\left(\frac{1-u^{x-2}}{1-u}\right)C.$$
After subbing back in and completing some simplifications, we finally arrive at
$$N_x=(1+r)^{x-2}N_2+12((1+r)^{x-2}-1)m.$$
Now, recalling that $N_2=N_1+(N_1-12m)r$ and $N_1=N_0+(N_0-bm)r$, we have $N_2=N_0+(N_0-bm)r+(N_0+(N_0-bm)r-12m)r$. This is more compactly stated as $$N_2=N_0+\left((2+r)N_0-(b+br+12)m \right)r.$$
Subbing $N_2$ in, our final statement is thusly:
$$V(y,b;N,m,r)=(1+r)^{x-2}\left[N_0+\left((2+r)N_0-(b+br+12)m \right)r\right]+12((1+r)^{x-2}-1)m.$$
Remark

[. . .]it does (N−6m)r interests at the end of the first year

It would appear that your case is $b=6$. Throw that into the above formula and it simplifies a tad.


text:
\begin{document}

\title{A Stochastic Subgradient Method for\\ Distributionally Robust Non-Convex Learning
}

\author{\name Mert G\"{u}rb\"{u}zbalaban$^\text{*}$ \email mg1366@rutgers.edu
\AND
\name Andrzej Ruszczy{\'n}ski$^\text{*}$ \email rusz@rutgers.edu
       \AND
       \name  Landi Zhu$^\text{*}$ \email lz401@scarletmail.rutgers.edu\\
      \addr Department of Management Science and Information Systems\\ Rutgers Business School, Piscataway, USA. \\
      *The authors are in alphabetical order.

      }

\editor{TBD}

\maketitle

\begin{abstract} We consider a distributionally robust formulation of stochastic optimization problems arising in statistical learning, where robustness is with respect to uncertainty in the underlying data distribution. Our formulation builds on risk-averse optimization techniques and the theory of coherent risk measures. It uses semi-deviation risk for quantifying uncertainty, allowing us to compute solutions that are robust against perturbations in the population data distribution. { We consider a broad class of generalized differentiable loss functions that can be non-convex and non-smooth, involving upward and downward cusps, and we develop an efficient stochastic subgradient method for distributionally robust problems with such functions. We prove that it converges to a point satisfying the optimality conditions. To our knowledge, this is the first method with rigorous convergence guarantees in the context of generalized differentiable non-convex and non-smooth distributionally robust stochastic optimization. Our method allows for control of the desired level of robustness with little extra computational cost compared to population risk minimization \mg{with stochastic gradient methods}.} We also illustrate the performance of our algorithm on real datasets arising in convex and non-convex supervised learning problems.
\end{abstract}

\section{Introduction}

Statistical learning theory deals with the problem of making predictions and constructing models from a set of data. A
typical statistical learning problem can be formulated as a stochastic optimization problem:
\begin{equation} \min_{x\in X} \mathbb{E}_{D\sim \mathbb{P}} \left[\ell(x,D)\right],
\label{pbm-stoc-opt}
\end{equation}
where $\ell:\Rb^n\times \Rb^d\to \Rb$ is the loss function of the predictor $x$ on the random data $D$ with an unknown distribution with probability law $\mathbb{P}$, and $X\subset\mathbb{R}^n$ is the feasible set (see, \emph{e.g.}, \citep{vapnik2013nature}). We consider loss functions that can be non-convex or non-differentiable (non-smooth). This framework includes a large class of problems in supervised learning including deep learning, linear and non-linear regression and classification tasks \citep{shalev2014understanding}.

A central problem in statistics is to make decisions that generalize well (i.e. work well on unseen data) as well as decisions that are robust to perturbations in the underlying data distribution \citep{DASZYKOWSKI2007203}. Indeed, the statistical properties of the input data may be subject to some variations and distributional shifts and a major goal is to build models that are not too sensitive to small changes in the input data distribution. This motivates the following distributionally robust version of the problem \eqref{pbm-stoc-opt}:
\begin{equation}
\min_{x\in X} \max_{\mathbb{Q}\in \mathcal{M}(\mathbb{P})} \mathbb{E}_{D\sim \mathbb{Q}} \left[\ell(x,D)\right],
\label{pbm-robust-stoc-opt}
\end{equation}
where $\mathcal{M}(\mathbb{P})$ is a weakly closed convex set of probability measures that models perturbations to the law $\mathbb{P}$, and the predictor $x$ is chosen to accommodate worst-case perturbations.
References \citep{BAKER2008253,seidman2020robust,madry2017towards} provide thorough discussion of the relevance of robustness in
statistical learning. Problem \eqref{pbm-robust-stoc-opt} is related to quantifying risk of the random data distribution \citep{gao2017wasserstein,robust-cvar}; its computational tractability depends on the underlying risk measure and the uncertainty set $\mathcal{M}(\mathbb{P})$ \citep{ruszczynski2006,duchi2018learning,esfahani2018data}. Existing approaches to modelling $\mathcal{M}(\mathbb{P})$ include conditional value at risk \citep{robust-cvar}, $f$-divergence based sets \citep{duchi2018learning}, Wasserstein balls around $\mathbb{P}$ \citep{sinha2017certifying,gao2016distributionally}, and other statistical distance based approaches (see, \emph{e.g.}, \citep{gao2016distributionally}). When $\ell$ is non-convex and non-differentiable, these formulations lead to non-convex min-max problems. To our knowledge,  none of the existing algorithms admit provable convergence guarantees to a stationary point of \eqref{pbm-robust-stoc-opt} in this general case.
\cite{sinha2017certifying} consider the case when $\mathcal{M}(\mathbb{P})$ is defined as the $\rho$-neighborhood of the probability law $\mathbb{P}$ under the
Wasserstein metric, where $\rho$ is the desired level of robustness. The authors formulate a Lagrangian relaxation of this problem for a fixed penalty parameter $\gamma\geq 0$ and show that when the loss is smooth and the penalty parameter is large enough (or by duality if the desired level of robustness $\rho$ is small enough), the stochastic gradient descent (SGD) method achieves the rates of convergence that are achievable in standard smooth non-convex optimization. The authors also provide a data-dependent upper bound for the worst-case population
objective \eqref{pbm-robust-stoc-opt} for any robustness level $\rho$. Soma and Yoshida \citep{soma2020statistical} proposed a conditional value-at risk (CVaR) formulation for robustness and show that for convex and smooth losses their algorithm based on SGD has $\mathcal{O}(1/\sqrt{n})$-convergence to the optimal CVaR, where $n$ is the number of samples. For nonconvex and smooth loss functions, they also show a generalization bound on the CVaR. However, none of these guarantees apply if the loss is non-smooth.

{For some structured regression and classification problems of practical interest,   distributionally robust formulations that result in finite-dimensional convex programs are known \citep{robust-log-reg,esfahani2018data,mehrotra,kuhn2019wasserstein} to be solvable in polynomial time; see also the reference \citep{tractable-review} which contains a detailed list of tractable reformulations of distributionally robust constraints for several risk measures. For convex losses, conic interior point solvers or gradient descent with backtracking Armijo line-searches

can also be used for solving a sample-based approximation of \eqref{pbm-robust-stoc-opt}, when $\mathcal{M}(\mathbb{P})$ is defined via the $f$-divergences \citep{duchi2018learning}. However, these approaches can be prohibitively expensive when the dimension or the number of samples are large}. {For smooth and convex losses, Namkoong and Duchi \citep{namkoong2016stochastic} showed that a sample-based approximation of \eqref{pbm-robust-stoc-opt} with $f$-divergences results in a min-max problem which can then be solved with a bandit mirror descent algorithm with number of iterations comparable to that of the SGD for solving the sample-based approximation of the problem \eqref{pbm-stoc-opt}. However, similar convergence guarantees for non-convex or non-smooth losses were not given.} {We also note that} there are data-driven distributionally robust stochastic optimization formulations (see, \emph{e.g.}, \citep{esfahani2018data,gao2017wasserstein,gao2016distributionally}) {which} replace the population measure $\mathbb{P}$ with an empirical measure $\mathbb{P}^{N}$ constructed from samples of input data. A disadvantage is that the resulting set $\mathcal{M}(\mathbb{P}^{N})$ becomes random.

We propose a new formulation of \eqref{pbm-robust-stoc-opt} based on the

mean--semideviation measure of risk \citep{OR:1999,OR:2001}. We propose a specialized stochastic subgradient method for solving the resulting
problem, {which we call the \emph{single-time scale} (STS) method.} Our method has local convergence guarantees for a large class of possibly non-convex and non-smooth loss functions.

\textbf{Modeling $\mathcal{M}(\mathbb{P})$ with mean semi-deviation risk.}
Consider the random loss $Z = \ell(x,D)$
 defined on a sample space $\varOmega$ equipped with a sigma algebra $\Fc$. We assume $\mathbb{E}(Z)$ to be finite, \emph{i.e.}, $Z \in \Zc = \Lc_1(\varOmega,\Fc,\mathbb{P})$. The mean--semideviation risk measure is defined as follows:
\begin{equation}
\label{msd}
\rho[Z]  = \Eb[Z] + \varkappa\, \Eb\big[\max\big(0,Z - \Eb[Z]\big)\big],\qquad \varkappa \in [0,1].
\end{equation}
It is known to be a coherent measure of risk \citep{ADEH:1999} (see also \citep{follmer2011stochastic,shapiro2009lectures} and the references therein). In particular, it has the \emph{dual representation} \citep{RuSh:2006a},

\[
\rho[Z] = \max_{\mu \in \Ac} \int_\varOmega Z(\omega)\mu(\omega)\;\mathbb{P}(d\omega) =
{\max_{\mathbb{Q}~:~ \frac{d\mathbb{Q}}{d\mathbb{P}}\in \Ac} \int_\varOmega Z(\omega)\;\mathbb{Q}(d\omega)}=
\max_{{\mathbb{Q} ~:~ \frac{d\mathbb{Q}}{d\mathbb{P}}\in \Ac}}\Eb_\mathbb{{Q}}[Z],
\]
where $\Ac$ is a convex and closed set defined as  follows:
\begin{equation}
\Ac = \big\{ \mu= \1+ \xi - \Eb[\xi]: \ \xi\in \Lc_{\infty}(\varOmega,\Fc,\mathbb{P}), \  \|\xi\|_\infty \le \varkappa,\ \xi \ge 0 \big\}.
\notag
\end{equation}
This provides \eqref{msd} with robustness with respect to the probability distribution; the level of robustness is controlled by the parameter $\varkappa$.
{After plugging $Z=\ell(x,D)$ into this formulation,
we obtain}
\begin{equation}
\label{stoch_prob}
\min_{x\in X} \max_{\mathbb{Q}\in\mathcal{M}(\mathbb{P})}\Eb_\mathbb{Q}[\ell(x,D)] = \min_{x\in X}\;  \Eb\Big[\ell(x,D) + \varkappa \max\big(0,\ell(x,D) - \Eb[\ell(x,D)]\big)\Big],
\end{equation}
with the perturbation set
\begin{equation}
\mathcal{M}(\mathbb{P}) = \big\{ \mathbb{Q} : \frac{d\mathbb{Q}}{d\mathbb{P}} \in \mathcal{A}\big\}.
\label{eq-Mp}
\end{equation}
An advantage of the formulation \eqref{stoch_prob} is that the perturbation set is implied rather than defined with the use of a metric in the space of probability measures.

Problem \eqref{stoch_prob} can be cast in the following form
of a composition optimization problem:
\begin{equation}
\label{main_prob}
\min_{x\in X}\; f(x,h(x)),
\end{equation}

with the functions
\begin{align}
f(x,u) &= \Eb\Big[\ell(x,D) + \varkappa\max\big(0,\ell(x,D) - u \big)\Big], \label{f-def}\\
h(x) &= \Eb[\ell(x,D)]. \label{h-def}
\end{align}
 The main difficulty is that neither  values nor (sub)gradients of $f(\cdot)$, $h(\cdot)$, and of their composition are available.
Instead, we postulate access to their random estimates. Such estimates, however, may be biased, because estimating a
(sub)gradient of the composition $F(x) = f(x,h(x))$ involves estimating $h(x)$. Although problem \eqref{main_prob} can be further rewritten in the standard format of composition optimization,
\begin{equation}
\label{composition}
\min_{x\in X} f(\bar{h}(x)),
\end{equation}
with $\bar{h}(x) = (x,h(x))$, but the more specific formulation \eqref{main_prob} allows us to derive a more efficient specialized method, because $x$ is observed.

 The research on composition optimization problems of form \eqref{composition}  started from
penalty functions for stochastic constraints and composite regression models in \citep[Ch. V.4]{ermoliev1976methods}.
An established approach was to use two-level stochastic
recursive algorithms with two stepsize sequences in different time scales:  a slower one for updating the
main decision variable $x$, and a faster one for filtering the value of the inner function $h$.
References \citep{wang2017stochastic,WaLiFa17,kalogerias2018recursive,yang2019multi} provide a detailed account of these techniques and existing results.

A Central Limit Theorem for stochastic versions of  problem \eqref{composition} has been established in  \citep{dentcheva2017statistical}.  Large deviation bounds for the empirical optimal value were derived in \citep{ermoliev2013sample}. A new single time-scale method for problem \eqref{composition} with continuously differentiable functions has been recently proposed in \citep{ghadimi2018single}. It has  the complexity of ${\cal O}(1/\epsilon^2)$ to obtain an $\varepsilon$-solution
 of the problem, the same as methods for one-level unconstrained stochastic optimization. However, the construction of the method
 and its analysis depend on the Lipschitz constants of the gradients of the functions involved. Our problem \eqref{main_prob}, unfortunately, involves a nonsmooth function $\max(\cdot,\cdot)$, and may also
 involve a nonsmooth (non-differentiable) loss function $\ell(\cdot,\cdot)$. Indeed, many key problems in machine learning involve non-convex and non-smooth loss functions. A prominent example is deep learning with ReLU activation functions (see \emph{e.g.} \citep{goodfellow2016deep}). There are many other statistical learning problems where the objective can be non-smooth and non-differentiable such as non-convex generalized linear models and non-convex regression and risk minimization (see \emph{e.g.} \citep{hastie2015statistical,nonconvex-learning,allen2016variance,JMLR:v11:teo10a}). The organic non-differentiability and non-convexity are additional challenges for the solution method.

\textbf{Contributions.} We propose to model the perturbation to input data distribution by mean-semi\-deviation risk, according to \eqref{eq-Mp}. Our formulation leads to the distributionally robust learning problem \eqref{stoch_prob} which has the advantage that it results in a convex optimization problem when the loss $\ell$ is convex, {in contrast to some alternative formulations which result in min-max optimization problems (see, \emph{e.g.}, \citep{robust-cvar,namkoong2016stochastic}}).

When the loss is non-convex and non-smooth, we can still find a stationary point to \eqref{stoch_prob}, by our novel single time-scale parameter-free stochastic subgradient method. We prove that it finds a stationary point of \eqref{stoch_prob} for a general class of loss functions that can be non-convex and non-differentiable.
To our knowledge, out method is the first method with {probability one} convergence guarantees for solving a distributionally robust formulation of a population minimization problem, where the loss can be non-convex or non-differentiable.

{We also note that the computational cost of stochastic first-order optimization algorithms are typically measured in terms of the number of stochastic gradient or subgradient evaluations they require (see, \emph{e.g.}, \citep[Section 6]{bubeck}, \citep{jain2018accelerating,ghadimi2013optimal}). Standard SGD methods (which go back to Robbins and Monro's pioneering work \citep{robbins1951stochastic}) applied to the non-robust optimization problem \eqref{pbm-stoc-opt} can operate with one stochastic subgradient evaluation under similar assumptions to ours, however they are not applicable to the robust formulation \eqref{pbm-robust-stoc-opt} directly. In contrast, our method can converge to a stationary point of the robust formulation \eqref{pbm-robust-stoc-opt} with probability one requiring at most two stochastic subgradient evaluations at every iteration. Therefore, comparing the numbers of stochastic gradient evaluations, the computational cost of each iteration of our method is at most twice that of the standard SGD method, requiring little extra computational cost for computing robust solutions.}

\section{The single time-scale (STS) method with subgradient averaging}
\label{s:3}
{
We present the method for problems of the form \eqref{stoch_prob}, in which the loss function $\ell(x,D)$
is differentiable in a generalized sense \citep{norkin1980generalized} with respect to $x$ and integrable with respect to $D$.
This broad class of functions is contained in the set of locally Lipschitz functions,
and contains all semismooth locally Lipschitz loss functions that can be non-convex and non-differentiable \citep{mifflin1977semismooth}.
{We note that this class includes many of the losses arising in statistical learning problems, including population and empirical risk minimization with possibly non-convex and non-smooth regularizers \citep{hastie2015statistical,nonconvex-learning,allen2016variance,JMLR:v11:teo10a,vapnik2013nature}, weakly convex and continuous losses \citep{davis-dima,lee-weakly-convex} as well as deep learning with ReLU activations \citep{goodfellow2016deep}.}

Recall that the Clarke subdifferential $\partial_x\ell(x,D)$ is an inclusion-minimal generalized derivative of $\ell(\cdot,D)$ \citep{norkin1980generalized}.
 We make the following assumptions.

\begin{tightitemize}
\item[(A1)] The set $X\subset \Rb^n$ is convex and compact;
\item[(A2)] For almost every (a.e.) $\omega\in \Omega$, the function $\ell(\cdot,D(\omega))$ is differentiable in a generalized sense with
the subdifferential $\partial_x \ell(x,D(\omega))$, $x\in \Rb^n$.  Moreover, for every compact set $K \in \Rb^n$ an integrable function $L_K:
\varOmega\to \Rb$ exists, satisfying
$\sup_{x\in K}\sup_{g \in \partial \ell(x,D(\omega)) } \|g\| \le L_K(\omega)$.
\end{tightitemize}
Under (A2), the function \eqref{h-def} is also differentiable in a generalized sense. Although its generalized derivative is not readily available, we can draw $\widetilde{D}$ from the distribution of $D$
and use an element of $\partial_x\ell(x,\widetilde{D})$ as a \emph{stochastic subgradient}  (a random vector whose expected value is a subgradient).
Furthermore, the function \eqref{f-def} is also differentiable in a generalized sense with respect to $(x,u)$.
Its stochastic subgradient can be obtained as follows. First, we observe
$\ell(x,\widetilde{D})$ and choose
\[
\lambda \in  \begin{cases} \{0\} & \text{ if } \ell(x,\widetilde{D}) < u,\\
 [0,1] & \text{ if } \ell(x,\widetilde{D}) = u,\\
 \{1\} & \text{ if } \ell(x,\widetilde{D}) > u.
\end{cases}
\]
Then the vector $\begin{bmatrix} \tilde{g}_x \\ \tilde{g}_u \end{bmatrix}$, where
$\tilde{g}_x \in (1+ \lambda \varkappa)\partial_x\ell(x,\widetilde{D})$, $\tilde{g}_u = -\lambda\varkappa$,
is a stochastic subgradient of the function $f(x,u)$ which is defined by \eqref{f-def}. These formulas follow from calculus rules for generalized subdifferentials
of compositions \citep[Thm. 1.6]{mikhalevich1987nonconvex} and expected values \citep[Thm. 23.1]{mikhalevich1987nonconvex}.
We can also use different samples for calculating  stochastic subgradients of \eqref{f-def} and \eqref{h-def}.
}

The {STS} method generates three random sequences: approximate solutions $\{x^k\}$,
path-averaged stochastic subgradients $\{z^k\}$, and inner function estimates $\{u^k\}$, all defined
on a certain probability space $(\Omega,\Fc,P)$. We let $\Fc_k$ to be
the $\sigma$-algebra generated by
$\{x^0,\dots,x^k,z^0,\dots,z^k,u^0,\dots,u^k\}$.
Starting from the initialization
$x^0 \in X$, $z^0 \in \Rb^n$, $u^0 \in \Rb$, the method uses parameters  $a>0$, $b>0$ and ${c}>0$ to generate $x^k, z^k, u^k$ for $k>0$.
At each iteration $k=0,1,2,\dots$, we compute
\begin{equation}
\label{QP}
y^k = \argmin_{y \in X}\  \left\{\langle z^k, y-x^k \rangle + \frac{{c}}{2} \|y-x^k\|^2\right\},
\end{equation}
and, with an $\Fc_k$-measurable stepsize $\tau_k \in \big(0,\min(1,1/a)\big]$, we set
\begin{equation}
\label{def_xk}
x^{k+1} = x^k + \tau_k (y^k-x^k).
\end{equation}
Then, we obtain statistical estimates:
\begin{tightitemize}
\item $\tilde{g}^{k+1}=\begin{bmatrix}\tilde{g}_x^{k+1} \\ \tilde{g}_u^{k+1}\end{bmatrix}$ of an element ${g}^{k+1}=\begin{bmatrix} g_x^{k+1}\\ g_u^{k+1}\end{bmatrix}\in \partial\!f(x^{k+1},u^k)$,
\item $\tilde{h}^{k+1}$  of $h(x^{k+1})$, and
\item $\tilde{J}^{\,k+1}$ of an element $J^{k+1}\in \partial h(x^{k+1})$ with the convention that $J^{k+1}$ is a row vector,
\end{tightitemize}
and we update the running averages as
\begin{align}
z^{k+1} &= z^k + a\tau_k \Big(\tilde{g}_x^{k+1}+\big[\tilde{J}^{\,k+1}\big]^\top \tilde{g}_u^{k+1} - z^k\Big),  \label{def_zk}\\
u^{k+1} &= u^k + \tau_k \tilde{J}^{\,k+1} (y^k-x^k) + b \tau_k \big(\tilde{h}^{k+1}-u^k\big).   \label{def_uk}
\end{align}
We assume the following conditions on the stepsizes and the stochastic estimates:
\begin{tightitemize}
\item[(A3)] $\tau_k \in \big(0,\min(1,1/a)\big]$ for all $k$, $\lim_{k\to\infty}\tau_k= 0$, $\sum_{k=0}^\infty \tau_k = \infty$,
$\sum_{k=0}^\infty \Eb[\tau_k^2] < \infty$;
\item[(A4)] For all $k$,
\begin{tightlist}{iii}
\item
$\tilde{g}^{k+1} = g^{k+1} + e_g^{k+1} + \delta_g^{k+1}$, with \\ $g^{k+1}\in \partial\!f(x^{k+1},u^k)$,
 $\Eb\big\{e_g^{k+1}\big|\Fc_k\big\} = 0$, $\Eb\big\{\|e_g^{k+1}\|^2|\Fc_k\big\}\le \sigma_g^2$, \\$\lim_{k\to \infty} \delta_g^{k+1}=0$,
\item $\tilde{h}^{k+1} = h(x^{k+1}) + e_h^{k+1} + \delta_h^{k+1}$, with\\
$\Eb\big\{e_h^{k+1}\big|\Fc_k\big\} = 0$,  $\Eb\big\{\|e_h^{k+1}\|^2|\Fc_k\big\}\le \sigma_h^2$, $\lim_{k\to \infty} \delta_h^{k+1}=0$,
\item $\tilde{J}^{\,k+1} = J^{k+1} + E^{k+1} + \Delta^{k+1}$,with \\
$J^{k+1}\in \partial h(x^{k+1})$,
$\Eb\big\{E^{k+1}\big|\Fc_k\big\} = 0$, $\Eb\big\{\|E^{k+1}\|^2|\Fc_k\big\}\le \sigma_E^2$,
\end{tightlist}
and $e_g^{k+1}$ and $E^{k+1}$ are statistically independent, given $\Fc_k$.
\end{tightitemize}
These assumptions are pretty standard in the study of stochastic gradient and stochastic approximation methods \citep{kushner2003stochastic}. As discussed before, the stochastic estimates satisfying these conditions can be obtained by drawing at each iteration one or two independent samples: $D_1^{k+1}$ and $D_2^{k+1}$, from the data. Then we can take
\begin{align*}
\tilde{g}_x^{k+1} &\in \begin{cases} \partial_x \ell(x^{k+1}, D_1^{k+1}) & \text{if } \ell(x^{k+1}, D_1^{k+1}) < u^k,\\
                                    (1+\varkappa) \partial_x \ell(x^{k+1}, D_1^{k+1}) & \text{if } \ell(x^{k+1}, D_1^{k+1}) \ge u^k,
                                    \end{cases}\\
\tilde{g}_u^{k+1} &=\begin{cases} 0 & \text{if } \ell(x^{k+1}, D_1^{k+1}) < u^k,\\
                                   -\varkappa & \text{if } \ell(x^{k+1}, D_1^{k+1}) \ge u^k,
                                    \end{cases}\\
\tilde{h}^{k+1} &=  \ell(x^{k+1}, D_1^{k+1}),
\\
\tilde{J}^{\,k+1} &\in \begin{cases}
\big\{\tilde{g}_x^{k+1}\big\}  & \text{if } \ell(x^{k+1}, D_1^{k+1}) < u^k,\\
 \partial_x \ell(x^{k+1}, D_2^{k+1}) & \text{if } \ell(x^{k+1}, D_1^{k+1}) \ge u^k.
\end{cases}
\end{align*}
When $\ell(x^{k+1}, D_1^{k+1}) < u^k$, only one sample, $D_1^{k+1}$, is needed, because
$\big[\tilde{J}^{\,k+1}\big]^\top \tilde{g}_u^{k+1}=0$ in \eqref{def_zk} in this case. {In any case,  each iteration of our algorithm requires at most two stochastic subgradient evaluations.}

Our method refines and specializes the approach to multi-level stochastic optimization recently developed in \citep{ruszczynski2020stochastic}. { We extend this approach to a new case in which the upper level function function is not continuously differentiable and thus the
conditions of \citep{ruszczynski2020stochastic} are not satisfied. We establish the convergence in the new case as well, as detailed in the following section.}

\section{Convergence analysis}

To recall optimality conditions for problem \eqref{stoch_prob}, and analyze our method, we need to introduce  relevant multifunctions.
For a point $x\in \Rb^n$, we define the set:
\begin{equation}
\label{GF}
G_F(x) = {\rm conv} \big\{ s\in \Rb^{n}: s = g_x + J^\top g_u,\ g \in \partial\! f(x,h(x)), \ J \in \partial h(x) \big\}.
\end{equation}
By \citep[Thm. 1.6]{mikhalevich1987nonconvex},
the set $G_F(x)$ is a generalized subdifferential of the composition function $F(x)=f(x,h(x))$.
We call a point $x^*\in X$ \emph{stationary} for problem \eqref{stoch_prob}, if
\begin{equation}
\label{stationary}
0 \in  G_F(x^*) + N_X(x^*),
\end{equation}
where $N_X(x)$ is the normal cone to $X$ at $x$.
The set of stationary points
is denoted by $X^*$. We start from a useful property of the gap function {$\eta:X\times \Rb^n\to(-\infty,0]$},
\begin{equation}
\label{gap}
\eta(x,z) = \min_{y\in X} \left\{\langle z, y-x \rangle + \frac{{c}}{2} \|y-x\|^2\right\}.
\end{equation}
We denote the minimizer in \eqref{gap} by $\bar{y}(x,z)$. Since it is a projection of $x-z/{c}$ on $X$,
\begin{equation}
\label{opt-eta}
 \langle z ,\bar{y}(x,z)-x \rangle  + {c} \| \bar{y}(x,z)-x \|^2 \le 0.
\end{equation}
Moreover, a point $x^*\in X^*$ if and only if $z^*\in G_F(x^*)$ exists
 such that $\eta(x^*,z^*)=0$. Consider the multifunction $\varGamma: \Rb^n\times \Rb^n \times \Rb \rightrightarrows \Rb^n \times \Rb$:
\begin{equation}
\label{Gamma-def}
\begin{aligned}
\varGamma(x,z,u)=&\big\{(R,v): \exists g \in \partial f(x,u), \exists J \in \partial h(x), \\
&v=J  \big(\bar{y}(x,z)-x\big) + b(h(x)-u), \ R=a\big(g_{x}+J^\top g_{u}-z\big)\big\}.
\end{aligned}
\end{equation}

With this notation, we can write the updates \eqref{def_zk}--\eqref{def_uk} as follows:
\begin{equation}
\label{u-abstract}
\begin{bmatrix}
z^{k+1} \\ u^{k+1}
\end{bmatrix} \in  \begin{bmatrix} z^k \\ u^k \end{bmatrix}
+ \tau_k \varGamma(x^{k+1},z^k,u^k) + \tau_k \theta^{k+1} + \tau_k \alpha^{k+1},
\end{equation}
where, for some constant $C^{\theta}$,
\begin{equation}
\label{theta-abstract}
\Eb\big[\theta^{k+1}\,\big|\, \Fc_k\big]=0,  \quad \Eb\big[\|\theta^{k+1}\|^2\,\big|\,\Fc_k\big]\le C^{\theta}, \quad  k=0,1,\dots
\end{equation}
and
\begin{equation}
\label{alpha-abstract}
\lim_{k\to \infty} \alpha^{k+1} = 0.\quad \text{a.s.}.
\end{equation}
The verification of relations \eqref{u-abstract}--\eqref{alpha-abstract} is  straightforward from the
description of the algorithm and assumptions (A3)--(A4). Two technical results are needed for further analysis.

\begin{lemma}
\label{l:Gamma}
The multifunction $\varGamma$
is compact and convex valued.
\end{lemma}
\begin{proof}
By assumption, for a.e. $\omega \in \Omega$, the loss function $\ell(x,D(\omega))$ is generalized differentiable, and therefore the function $f(x,u)$ is also generalized differentiable where $\partial_x f(x,u)$, $\partial_u f(x,u)$ and $\partial h(x)$ are all convex and compact \citep{norkin1980generalized}.

Since the function $F(u,D(\omega))=\ell(x,D(\omega))+\varkappa \cdot \max(0,\ell(x,D(\omega)-u)$ {is generalized differentiable for a.e. $\omega$},
{by the interchangeability of the generalized subdifferential and integral operators \citep[Thm. 23.1]{mikhalevich1987nonconvex}, we obtain}:

\begin{equation}
\partial_u f (x,u)=\mathbb{E} [\partial_u F(u,D)].
\end{equation}
We also have
$$ \partial_uF(u,D)=\varkappa \cdot \left\{
\begin{aligned}
-1, &\ u<\ell(x,D), \\
[-1,0],&\ u=\ell(x,D), \\
0,&\ u>\ell(x,D),
\end{aligned}
\right.
$$
which implies
\begin{align*}
 \partial_u f(x,u)&= - \varkappa\, \Pbb\big\{u<\ell(x,D)\big\}+\varkappa \big[-\Pbb\big\{u=\ell(x,D)\big\},0\big]\\
&=\varkappa \big[-\Pbb\big\{u \le \ell(x,D)\big\}, -\Pbb\big\{u<\ell(x,D)\big\}\big].
\end{align*}

If we denote $\Pbb\big\{u\le \ell(x,D)\big\}$ and $\Pbb\big\{u<\ell(x,D)\big\}$ by $P_1$ and $P_2$ respectively, we obtain
$\partial_u f(x,u) = \varkappa \cdot [-P_1,-P_2]$.

Now, in order to prove that $\varGamma (x,z,u)$ is convex-valued, we choose two points in $\varGamma (x,z,u)$: $A=(R_a,v_{1a},v_{2a})$ and $B=(R_b,v_{1b},v_{2b})$. Since every point in $\varGamma (x,z,u)$ is generated by  a pair of $(g,J)$ from $\partial f(x,u) \times \partial h(x) $, we can also denote the pair generating the point $A$ by $(a_1,a_2)$, and the pair generating the point $B$ by $(b_1, b_2)$.

For every $\theta \in [0,1]$, the convex combination $(R^\theta, v_1^\theta, v_2^\theta)$ of $A$ and $B$ can be expressed as:
\begin{align*}
R^\theta &= a(\theta a_{1x} + (1-\theta)b_{1x} + \theta a_{1u}a_2 +(1-\theta)b_{1u}b_2-z),\\
v_1^\theta &= (\theta a_{1x} + (1-\theta)b_{1x})(\bar{y}(x,z)-x)+\theta a_{1u} a_2 +(1-\theta)b_{1u}b_2 + b(f(x,u_2)-u_1),\\
v_2^\theta &= \theta a_2 +(1-\theta)b_2.
\end{align*}
If we can always find a pair $(c_1,c_2) \in \partial f(x,u) \times \partial h(x)$ that generates this convex combination, then $\varGamma (x,z,u)$ is convex-valued.

First, since $\partial_x f(x,u)$ and $\partial h(x)$ are convex sets, we can choose $c_{1x}=\theta a_{1x} + (1-\theta)b_{1x}, c_2=\theta a_2 + (1-\theta)b_2$ (we do not choose $c_{1u}$ yet); then the corresponding point $C=(g_c, v_{1c}, v_{2c})$ is:
\begin{align*}
R_c \  &= a(\theta a_{1x} + (1-\theta)b_{1x} + c_{1u} (\theta a_2 +(1-\theta)b_2)-z),\\
v_{1c} &= (\theta a_{1x} + (1-\theta)b_{1x})(\bar{y}(x,z)-x)+c_{1u} (\theta a_2 +(1-\theta)b_2) + b(f(x,u_2)-u_1),\\
v_{2c} &= \theta a_2 +(1-\theta)b_2.
\end{align*}
Furthermore, we have $c_{1u} \in \partial_u f(x,u)=\varkappa \cdot [-P_1,-P_2]$, so for the common item $c_{1u} (\theta a_2 +(1-\theta)b_2)$ in $R_c$ and $v_{1c}$, any value between $-\varkappa P_1 (\theta a_2 +(1-\theta)b_2)$ and $-\varkappa P_2 (\theta a_2 +(1-\theta)b_2)$ can be achieved.

On the other hand, for the common item $\theta a_{1u}a_2 +(1-\theta)b_{1u}b_2$ in $R^\theta$ and $v_1^\theta$, since $a_{1u},b_{1u} \in \partial_u f(x,u)=\varkappa \cdot [-P_1,-P_2]$, we have:
\begin{equation}
-\varkappa P_1 (\theta a_2 +(1-\theta)b_2) \le \theta a_{1u}a_2 +(1-\theta)b_{1u}b_2 \le -\varkappa P_2 (\theta a_2 +(1-\theta)b_2),
\end{equation}
so there must exist $c_{1u}^* \in \partial_u f(x,u)$ that satisfies:
\begin{align*}
c_{1u}^* (\theta a_2 +(1-\theta)b_2) &= \theta a_{1u}a_2 +(1-\theta)b_{1u}b_2.
\end{align*}
This implies that for this value of $c_{1u}$,
\begin{align*}

(R^\theta, v_1^\theta, v_2^\theta) = (R_c, v_{1c}, v_{2c}),
\end{align*}
and we conclude that $\varGamma (x,z,u)$ is convex-valued. Furthermore, because $\partial_x f(x,u), \partial_u f(x,u)$ and $\partial h(x)$ are all compact, the set $\varGamma (x,z,u)$ is compact as well.
\end{proof}

\begin{lemma}
\label{l:bounded}
The sequences $\{z^k\}$ and $\{u^k\}$ are bounded with probability 1.
\end{lemma}
The proof is routine and is therefore omitted.

We analyze the method by the differential inclusion technique, by refining and specializing the approach adopted in \citep{ruszczynski2020stochastic}.
{ Although our model does not fit the assumptions of \citep{ruszczynski2020stochastic},  our result on the convexity of the multifunction $\varGamma(\cdot)$ allows for proving convergence in this case as well.}

\begin{theorem}
\label{t:convergence}
If the assumptions {\rm (A1)--(A4)} are satisfied,
then with probability 1 every accumulation point $\hat{x}$ of the sequence $\{x^k\}$ is stationary, $\lim_{k\to\infty} (u^k-h(x^k))=0$, and the sequence $\{F(x^k)\}$ is convergent.
\end{theorem}
\begin{proof}
We consider a specific trajectory of the method and divide the proof into three standard steps.

\emph{Step 1: The Limiting Dynamical System.}  We denote by $p^k=(x^k,z^k,u^k)$, $k=0,1,2,\dots$, a realization
of the sequence generated by the algorithm.
We introduce the accumulated stepsizes
$t_k = \sum_{j=0}^{k-1}\tau_j$, $k=0,1,2 \dots$, and we construct the interpolated trajectory
\[
P_0(t) = p^k + \frac{t-t_{k}}{\tau_k}(p^{k+1}-p^k),\quad t_{k}\le t \le t_{k+1},\quad k=0,1,2,\dots.
\]
For an increasing sequence of positive numbers $\{s_k\}$ diverging to infinity, we define shifted trajectories $P_k(t) =P_0(t+s_k)$.
The sequence $\{p^k\}$ is bounded by Lemma \ref{l:bounded} and so are the functions $P_k(\cdot)$.

By \citep[Thm. 3.2]{majewski2018analysis},  for any infinite set $\Kc$ of positive integers,
there exist an infinite  subset $\Kc_1 \subset \Kc$ and an absolutely continuous function  $P_\infty:
[0,+\infty) \to X\times \Rb^n\times \Rb^m$ such that for any $T > 0$
\[
\lim_{\substack{{k\to\infty}\\{k\in \Kc_1}}}\sup_{t\in[0,T]} \big\| P_k(t)-P_\infty(t)\big\|= 0,
\]
and $P_\infty(\cdot)=\big(X_\infty(\cdot),Z_\infty(\cdot),U_\infty(\cdot)\big)$
is a solution of the system of differential equations and inclusions corresponding to \eqref{def_xk} and
 and \eqref{u-abstract}:
\begin{gather}
\dt{x}(t) = \bar{y}\big(x(t),z(t)\big)-x(t), \label{dx}\\
\big(\dt{z}(t), \dt{u}(t)\big) \in \varGamma(x(t),z(t),u(t)). \label{dz}

\end{gather}
Moreover, for any $t\ge 0$, the triple $\big(X_\infty(t),Z_\infty(t),U_\infty(t)\big)$
is an accumulation point of the sequence $\{(x^k,z^k,u^k)\}$.

In order to analyze the equilibrium points of the system \eqref{dx}--\eqref{dz}, we first study the dynamics
of the functions $H(t) = h(X(t))$ and $F(t) = f(X(t),U(t))$.
It follows from \eqref{dx} that the path $X(\cdot)$ is continuously differentiable. By virtue of assumption (A2)
and \citep[Thm. 1]{Rusz-OptLet},
for any $J(t) \in \partial h(X(t))$,
\begin{equation}
\label{f-incr-M}
 \dt H(t)
=   J(t) \dt X(t).
\end{equation}
Again, Assumption (A2) and  \citep[Thm. 1]{Rusz-OptLet} imply that for any $G(t) \in \partial f(X(t),U(t))$,
\begin{equation}
\label{f-incr-m-2}
 \dt F(t)
=   G_x(t)^\top  \dt X(t)  + G_u(t)^\top  \dt U(t).
\end{equation}
To understand the dynamics of $U(\cdot)$, from \eqref{dz} and \eqref{u-abstract} we deduce that
\begin{equation}
\label{UM}
\dt U(t) = \hat{J}(t) \dt X(t) + b [H(t) - U(t)],
\end{equation}
with some $\hat{J}(t) \in \partial h(X(t))$.
Therefore, using $J(\cdot) = \hat{J}(\cdot)$ in \eqref{f-incr-M}, we obtain
\begin{equation}
\label{Um}
\dt U(t) =  \dt H(t) + b[ H(t) - U(t)].
\end{equation}
Consequently, the solution of \eqref{f-incr-m-2}--\eqref{UM} has the form:
 \begin{equation}
 \label{Phi-sol}
   \dt F(t) =
   \hat{G}(t)^\top \dt X(t) + b G_u(t)^\top[ H(t) - U(t)].
 \end{equation}
with $\hat{G}(t) = {G}_x(t) + \hat{J}(t)^\top  G_u(t)$.
These observations will help us study the stability of the system.

\emph{Step 2: Descent Along a Path.}  We use the Lyapunov function
\begin{equation}
\label{Lyapunov}
W(x,z,u) = a f(x,u) -  \eta(x,z)  + \gamma \big\|h(x)-u\big\|,
\end{equation}
with the coefficient $\gamma>0$ to be specified later.

Directly from \eqref{Phi-sol} we obtain
\begin{equation}
\label{f-incr2}
  f(X(T),U(T)) - f(X(0),U(0))
 = \int_0^T  \hat{G}(t)^\top \dt{X}(t)  \;dt
  + b  \int_0^T  G_{u}(t)^\top \big[H(t)-U(t)\big]\;dt.
\end{equation}

We now estimate the change of $\eta(X(\cdot),Z(\cdot))$ from 0 to $T$.
 Since $\bar{y}(x,z)$ is unique, the function $\eta(\cdot,\cdot)$ is continuously differentiable.
Therefore, the chain formula holds for it as well:
\begin{multline*}
\eta(X(T),Z(T)) - \eta(X(0),Z(0)) \\
= \int_0^T  \big\langle \nabla_x \eta(X(t),Z(t)), \dt{X}(t) \big\rangle \;dt +
\int_0^T  \big\langle \nabla_z \eta(X(t),Z(t)), \dt{Z}(t) \big\rangle \;dt.
\end{multline*}
From \eqref{dz} we obtain
\[
\dt{Z}(t) = a\big(\hat{G}^\top (t) - Z(t)\big),
\]
with the same $\hat{G}(\cdot)$ as in \eqref{Phi-sol} and \eqref{f-incr2}.

Substituting
$\nabla_x \eta(x,z) = -z+{c}(x- \bar{y}(x,z))$,
$\nabla_z \eta(x,z) =  \bar{y}(x,z)-x$,  and
using \eqref{opt-eta}, we obtain
\begin{align*}
\lefteqn{\eta(X(T),Z(T)) - \eta(X(0),Z(0))}\quad  \\
&= \int_0^T  \big\langle -Z(t)+{c}(X(t)-\bar y(X(t),Z(t)))\, , \,\bar{y}(X(t),Z(t)) - X(t) \big\rangle \;dt \\
&{\quad } +
a \int_0^T  \big\langle \bar y(X(t),Z(t))-X(t)\,,\,\hat{G}(t) - Z(t) \big\rangle \;dt\\
&\ge\; a \int_0^T  \big\langle \bar y(X(t),Z(t))-X(t)\,,\, \hat{G}(t) - Z(t) \big\rangle \;dt\\
&\ge\; a \int_0^T  \hat{G}(t)^\top\big( \bar y(X(t),Z(t))-X(t)\big) \;dt
 + a{c} \int_0^T  \big\| \bar y(X(t),Z(t))-X(t)\big\|^2 \;dt.
   \end{align*}
With a view at \eqref{dx}, we conclude that
\begin{equation}
\label{eta-incr}
 \eta(X(T),Z(T)) - \eta(X(0),Z(0))
  \ge \;  a \int_0^T  \hat{G}^\top(t) \dt X(t) \;dt
 + a{c} \int_0^T  \big\| \dt X(t)\big\|^2 \;dt.
  \end{equation}

We now estimate the increment of $\big\|  H(\cdot)-U(\cdot)\big\|$ from 0 to $T$. As
 $\| \cdot\| $ is convex and $H(\cdot)$ and $U(\cdot)$ are absolutely continuous, the chain rule applies as well: for any
 $\lambda(t) \in \partial \| H(t)- U(t)\|$ we have
\[
 \big\|H(T)-U(T)\big\| -  \big\|H(0)-U(0)\big\|
= \int_0^T \big\langle \lambda(t),  \dt H(t) - \dt U(t) \big\rangle\; dt.
\]
By \eqref{Um},  $\dt H(t) - \dt U(t) = b\big[ U(t)-H(t)\big]$ for almost all $t$.
Furthermore,
\[
\lambda_m(t)=\frac{H(t)-U(t)}{\|H(t)-U(t)\|},\quad \text{if}\quad  H(t)\ne U(t).
\]
Therefore
\begin{equation}
\label{norm-incr}
 \big\|H(T)-U(T)\big\| -  \big\|H(0)-U(0)\big\| = - b \int_0^T \big\| H(t)-U(t)\big\| \; dt.
 \end{equation}

We can now combine \eqref{f-incr2}, \eqref{eta-incr}, and \eqref{norm-incr} to estimate the change of the function \eqref{Lyapunov}:
\begin{multline*}

W\big(X(T),Z(T),U(T)\big) - W\big(X(0),Z(0),U(0)\big)\quad \\
\quad \le   a  b   \int_0^T  {G}_{u}(t)^\top\big[H(t)-U(t)\big]\;dt
 - a{c} \int_0^T  \big\| \dt X(t)\big\|^2 \;dt
- b \gamma  \int_0^T \big\|H(t)-U(t)\big\|\;dt.
\end{multline*}
Because the paths $X(t)$ and $U(\cdot)$ are bounded a.s. and the functions $f_m$ are locally Lipschitz,  a (random) constant $L$ exists, such that
$\big \| {G}_{u}(t)\big\| \le L$.
The last estimate entails:
\begin{multline}
\label{W-incr}
W\big(X(T),Z(T),U(T)\big) - W\big(X(0),Z(0),U(0)\big) \\
 \le - a{c} \int_0^T  \big\| \dt X(t)\big\|^2 \;dt - b (\gamma-aL)  \int_0^T \|H(t)-U(t)\|\;dt.
\end{multline}
By choosing $\gamma > aL$, we ensure that $W(\cdot)$ has the descent property to be used in our stability analysis at Step 3.
The fact that $L$ (and thus $\gamma$) may be different for different paths is irrelevant, because our analysis is path-wise.

\emph{Step 3: Analysis of the Limit Points.} Define the set
\[
\quad \Sc = \big\{ (x,z,u)\in X^* \times \Rb^n\times \Rb: \eta(x,z)=0,\
  u=h(x)\big\}.\quad
\]
Suppose $(\bar{x},\bar{z},\bar{u})$ is an accumulation point of the sequence $\{(x^k,z^k,u^k)\}$. If $\eta(\bar{x},\bar{z}) <0$ or
$\bar{u}\ne h(\bar{x})$, then
every solution $(X(t),Z(t),U(t))$ of the system \eqref{dx}--\eqref{dz},
starting from $(\bar{x},\bar{z},\bar{u})$ has $\|\dt X(0)\| > 0$ or $\|H(0)-U(0)\| >0$.
Using \eqref{W-incr} and arguing as in \citep[Thm. 3.20]{duchi2018stochastic} or \citep[Thm. 3.5]{majewski2018analysis},
we obtain a contradiction. Therefore,
we must have $\eta(\bar{x},\bar{z})=0$ and
$\bar{u}= h(\bar{x})$. Suppose $\bar{x}\not \in X^*$. Then

\begin{equation}
\label{non-opt}
\dist\big(0,  G_F(\bar{x}) + N_X(\bar{x})\big) >0.
\end{equation}
Suppose the system \eqref{dx}--\eqref{dz}
starts from $(\bar{x},\bar{z},\bar{u})$ and $X(t)=\bar{x}$ for all $t\ge 0$. From \eqref{dz} and \eqref{Gamma-def}, in view of the
equations $\bar{y}(\bar{x},\bar{z})=\bar{x}$ and  $\bar{u}=h(\bar{x})$, we obtain  $U(t)=  f(\bar{x})$ for all $t \ge 0$.
The inclusion \eqref{dz}, in view of \eqref{GF}, simplifies
\[
\dt{z}(t) \in a \big( G_F(\bar{x}) - z(t)\big).
\]
For the convex Lyapunov function $V(z) = \dist\big(z,G_F(\bar{x})\big)$,
we apply the classical chain formula \citep{brezis1971monotonicity}
on the path $Z(\cdot)$:
\[
V((Z(T)) - V(Z(0)) = \int_0^T \big\langle \partial V(Z(t)), \dt Z(t)\big\rangle \;dt.
\]
For $Z(t)\notin G_F(\bar{x})$, we have
\[
\partial V(Z(t)) = \frac{Z(t) - \proj_{G_F(\bar{x})}(Z(t))}{ \| Z(t) - \proj_{G_F(\bar{x})}(Z(t))\|}
\]
 and $\dt Z(t) = a (d(t) - Z(t))$ with some $d(t)\in G_1(\bar{x})$. Therefore,
\[
\big\langle \partial V(Z(t)), \dt Z(t)\big\rangle \le  - a \| Z(t) - \proj_{G_1(\bar{x})}(Z(t))\| = -a V(Z(t)).
\]
It follows that
\[
V((Z(T)) - V(Z(0)) \le - a \int_0^T  V(Z(t)) \;dt,
\]
and thus
\begin{equation}
\label{Z-conv}
\lim_{t\to\infty} \dist\big(Z(t),G_F(\bar{x})\big) = 0.
\end{equation}
It follows from \eqref{non-opt}--\eqref{Z-conv} that $T>0$ exists,
such that $ -Z(T) \not \in N_X(\bar{x})$, which yields $\dt X(T)\ne 0$. Consequently,
the path $X(t)$ starting from $\bar{x}$ cannot be constant (our supposition made right after \eqref{non-opt} cannot be true).  But if is not constant, then again $T>0$ exists, such that $\dt X(T)\ne 0$. By Step 1,
the triple $(X(T),Z(T),U(T))$ would have to be an accumulation point of the sequence $\{(x^k,z^k,u^k)\}$, a case already excluded.
We conclude that every accumulation point $(\bar{x},\bar{z},\bar{u})$  of the sequence $\{(x^k,z^k,u^k)\}$ is in $\Sc$.
The convergence of the sequence $\big\{W(x^k,z^k,u^k)\big\}$ then follows in the same way as
\citep[Thm. 3.20]{duchi2018stochastic} or \citep[Thm. 3.5]{majewski2018analysis}. As $\eta(x^k,z^k)\to 0$,
the convergence of $\{f(x^k,u^k)\}$ follows as well. Since $h(x^k)-u^k \to 0$, the sequence $\{F(x^k)\}$ is convergent
as well.
\end{proof}

\section{Numerical experiments}

In this section, we report results of numerical experiments that illustrate the performance of our single time-scale (STS) method for deep learning and logistic regression. For both applications, we consider perturbations in the training data set which leads to a distributional shift in the population measure $\mathbb{P}$, whereas we do not perturb the test data. We run the STS algorithm on the contaminated training data and investigate the robustness of the solution found by STS by considering different samples from the test data and the corresponding distribution of the test loss. {Our numerical results were obtained using Python (Version 3.7) on an Alienware Aurora R8 desktop with a 3.60 GHz CPU (i7-2677M) and 16GB memory.}

\subsection{Deep learning} We consider a fully-connected network on two benchmark datasets: MNIST \citep{lecun2010mnist} and CIFAR10 \citep{Krizhevsky09learningmultiple}, where the model has the depth (the number of layers) of 3 and the width (the number of neurons per hidden layer) of 100. The MNIST dataset is split into a training dataset of $60000$ examples and a test dataset of $10000$ examples, whereas the CIFAR10 dataset is split into a training part of $50000$ examples and a test part of $10000$ examples.
In both MNIST and CIFAR10 datasets, the output variable $y$ to be predicted is an integer valued from $0$ to $9$. We distort the distributions of MNIST and CIFAR10 training datasets by deleting all the data points with a $y$ value equal to $0$ (such points account for approximately 10$\%$ of the whole dataset). Based on the contaminated data, we train our model with different robustness levels $\kappa$ for 4000 iterations. To test the robustness of the model found by STS, we sample 100 points from the test dataset and compute the corresponding loss; and repeat this procedure 200 times for both datasets to generate a histogram of the test loss. We then report the corresponding cumulative distribution function (CDF) of the test loss in Figures \ref{figure-1} and  \ref{figure-2} for different values of $\kappa$, compared with results from a model trained by SGD.\footnote{{There are also adversarial learning methods \citep{madry2017towards,goodfellow2014explaining,kurakin2016adversarial,zhang2019you} where the aim is to be resistant to norm-bounded perturbations of the input before we have access to it; however, we do not compare with these methods as our formulation \eqref{stoch_prob} focuses on a distributional shift.}}

If the training data are not contaminated at all, {we have observed in our experiments} that STS generates a similar or slightly worse solution than SGD.
{This is expected as STS optimizes a penalized (robust) loss \eqref{stoch_prob} which is different than the empirical loss. The numerical details are omitted for the sake of brevity.
On the other hand}, when the data contains distributional shifts, we see a clear advantage of the STS method over the SGD method.

\begin{figure}[h!]
\centering
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_m_4_01_del0.pdf}
  \caption{$\varkappa = 0.1$.}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_m_4_03_del0.pdf}
  \caption{$\varkappa = 0.3$.}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_m_4_05_del0.pdf}
  \caption{$\varkappa = 0.5$.}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_m_4_08_del0.pdf}
  \caption{$\varkappa = 0.8$.}
\end{subfigure}
\caption{The CDFs of the SGD solution and the STS solutions under different robustness levels $\kappa$
for MNIST after 4000 iterations.}
\label{figure-1}
\end{figure}

\begin{figure}[h!]
\centering
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_c_4_01_del0.pdf}
  \caption{$\varkappa = 0.1$.}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_c_4_03_del0.pdf}
  \caption{$\varkappa = 0.3$.}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_c_4_05_del0.pdf}
  \caption{$\varkappa = 0.5$.}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=\linewidth]{cdf_c_4_08_del0.pdf}
  \caption{$\varkappa = 0.8$.}
\end{subfigure}
\caption{The CDFs of the SGD solution and the STS solutions under different robustness levels $\varkappa$
for CIFAR10 after 4000 iterations.}
\label{figure-2}
\end{figure}

\subsection{Logistic regression}

We consider binary logistic regression on the Adult dataset \citep{Dua:2019} where the loss function has the form
\mg{$\ell(x,D) = \left[\log(1+\exp(-b\, a^Tx))\right]$ where $D=(a,b)$ is the input data.}
The problem is to predict whether the annual income of a person will be above \$50,000 or not, based on $n=123$ predictor variables. The dataset has 32561 training examples and 16281 test examples. We follow a similar methodology as before, where we distort the training data by deleting $80\%$ of the data points with the corresponding income below \$50,000. We trained our model with STS and another state-of-the-art method Bandit Mirror Descent (BMD) developed in \citep{namkoong2016stochastic}, allowing both methods to execute the same {numbers of iterations}, which corresponds to 80000 iterations of the STS method. We then compare the cdf of the loss of the trained models based on 3000 samples from the test data. The results are reported in Figure
\ref{fig:duchi_r} for different values of the robustness level $\kappa$. We see that STS results in smaller errors {and conclude that our method has desirable robustness properties with respect to perturbations in the input distribution.}

\begin{figure}[h!]
\centering
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=1\linewidth]{cdf_sts_01_n08.pdf}
  \caption{$\varkappa$ = 0.1}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=1\linewidth]{cdf_sts_03_n08.pdf}
  \caption{$\varkappa$ = 0.3}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=1\linewidth]{cdf_sts_05_n08.pdf}
  \caption{$\varkappa$ = 0.5}
\end{subfigure}
\begin{subfigure}{0.43\textwidth}
  \includegraphics[width=1\linewidth]{cdf_sts_08_n08.pdf}
  \caption{$\varkappa$ = 0.8}
\end{subfigure}
\caption{The CDFs of the BMD solution and the STS solutions under different robustness levels $\varkappa$ for the Adult dataset after 80000 iterations.}
\label{fig:duchi_r}
\end{figure}

\section{Acknowledgements}
Mert G\"urb\"uzbalaban's and Landi Zhu's research are supported in part by the grants Office of Naval Research Award Number N00014-21-1-2244, National Science Foundation (NSF) CCF-1814888, NSF DMS-2053485, NSF DMS-1723085.

\bibliography{multi}

\end{document}

config: arxiv


TITLE: How to find the Fourier's coefficient $a_n$ of the Fourier's series of $\sin(x)$ on $(0,\pi]$, $0$on $(-\pi,0]$
QUESTION [3 upvotes]: Considering $g(x)$, periodical with a period of $2\pi$ defined by
\begin{equation*}
  g(x)=
     \begin{cases}
       0 & \text{for $x \in (-\pi;0]$} \\
        \sin(x)  & \text{for $x \in [0;\pi)$}
     \end{cases}
\end{equation*}
I want to find the Fourier's series $S(g)$ of $g$.
\begin{align*}
a_n&=\frac{1}{\pi}\int\limits_0^\pi \sin(x)\cos(x)d(x)\\
&=[sin^2(x)]-\int\limits_0^\pi \cos^2(x)d(x)\\
&=-\frac{1}{2}\int\limits_0^\pi (\cos(2x)+1)d(x)\\
&= \sin(2x)+\frac{x}{2}\\
\end{align*}
I've the feeling, seeing the solution of \begin{equation*}
  g(x)=
     \begin{cases}
       0 & \text{for $x \in (-\pi;0]$} \\
        x\sin(x)  & \text{for $x \in [0;\pi)$}
     \end{cases}
\end{equation*}
That I'm wrong...

REPLY [2 votes]: For
\begin{equation*}
  g(x)=
     \begin{cases}
       0 & \text{$x \in [-\pi,0)$} \\
        \sin(x)  & \text{$x \in [0,\pi)$}
     \end{cases}
\end{equation*}
Write
$$g(x) = \frac12 a_0 + \sum_{n=1}^{\infty} \left (a_n \cos{n x} + b_n \sin{n x} \right ) $$
$$a_0 = \frac1{\pi} \int_0^{\pi} dx \, \sin{x} = \frac{2}{\pi}$$
$$a_1 = \frac1{\pi} \int_0^{\pi} dx \, \sin{x} \cos{x} = 0$$
$$b_1 = \frac1{\pi} \int_0^{\pi} dx \, \sin^2{x} = \frac12$$
For $n \gt 1$:
$$\begin{align}a_n &= \frac1{\pi} \int_0^{\pi} dx \, \sin{x} \cos{n x}\\ &= \frac1{2 \pi}  \int_0^{\pi} dx \, \left [\sin{(n+1) x} - \sin{(n-1) x} \right ]\\ &= \frac1{2 \pi} \left [\frac{1-(-1)^{n+1}}{n+1} - \frac{1-(-1)^{n-1}}{n-1} \right ] \\ &= -\frac{1+(-1)^n}{\pi (n^2-1)} \end{align}$$
$$\begin{align}b_n &= \frac1{\pi} \int_0^{\pi} dx \, \sin{x} \sin{n x}\\ &= \frac1{2 \pi}  \int_0^{\pi} dx \, \left [\cos{(n-1) x} - \cos{(n+1) x} \right ]\\ &= 0 \end{align}$$
Thus,

$$g(x) = \frac1{\pi} + \frac12 \sin{x} - \frac{2}{\pi} \sum_{n=1}^{\infty} \frac{\cos{2 n x}}{4 n^2-1}$$


TITLE: Evaluating function
QUESTION [0 upvotes]: Here is the function:
$$f(a)=\sqrt{f(a)+\sqrt{f(f(a))+\sqrt{f(f(f(a)))+\cdots}}}$$
Is there another way to represent this function so that it only has $f(a)$ on one side and no $f(a)$'s on the other side of the $=$ sign? In other words, simplify the function as best as you can. Thank you very much.

REPLY [1 votes]: Square both sides, rearrange and simplify:
$f(a) \cdot (f(a) - 1) - f(f(a)) = 0$
I doubt there is any way to get rid of the $f(f(a))$ term.  And it may introduce extraneous solutions because of the squaring.


TITLE: Norm of operator in a Hilbert space
QUESTION [8 upvotes]: Consider a complex Hilbert space $H$ and an operator $T\in\mathcal{L}(H,H)$. Define
$$\|T\|=\sup_{\|x\|=\|y\|=1}\lvert\langle Tx, y\rangle\rvert$$, $$\||T|\|=\sup_{\|x\|=1}\lvert\langle Tx,x\rangle\rvert$$
Can you find an example of a complex Hilbert space $H$ and an operator $T$ such that $\|T\|=2\||T|\|$. I've been thinking about it and I can't find it.

REPLY [5 votes]: Take, for example,
$$
T=\begin{bmatrix}0 & 1\\0 & 0\end{bmatrix}.
$$
Then
$$
\sup_{\|x\|=1}|x^TTx|=\sup_{\|x\|=1}|x_1x_2|=\sup_{t}|\cos t\sin t|=\frac12\sup_t|\sin 2t|=\frac12,
$$
but
$$
\sup_{\|x\|=\|y\|=1}|y^TTx|=\sup_{\|x\|=\|y\|=1}|y_1x_2|=1.
$$


text:
\section{Stability of Modified-CS with Add-LS-Del}
\label{addLSdel_modcs}

The last two issues mentioned above in Sec. \ref{limitations} can be partly addressed by replacing the single support estimation step by a support addition step (that uses a smaller threshold), followed by an LS estimation step and then a deletion step that thresholds the LS estimate. The addition step threshold needs to be just large enough to ensure that the matrix used for LS estimation is well-conditioned. If the threshold is chosen properly and if $n$ is large enough, the LS estimate will have smaller error than the modified-CS output. As a result, deletion will be more accurate and in many cases one can use a larger deletion threshold. The addition-LS-deletion idea was simultaneously introduced in \cite{cosamp} (CoSaMP) for a static sparse reconstruction and in our older work \cite{kfcsicip,kfcspap} (KF-CS) for recursive reconstruction of sparse signal sequences.

Let $\alpha_{add}$ denote the addition threshold and let $\alpha_{del}$ denote the deletion threshold. We summarize the algorithm in Algorithm \ref{modcsalgo_2}.

\begin{algorithm}[h!]
\caption{{\bf \small Modified-CS with Add-LS-Del}}

For $t \ge 0$, do
\ben
\item {\em Simple CS. } If $t = 0$, set $T = \emptyset$ and compute $\xhat_{t,modcs}$ as the solution of
\bea
\min_\beta  \|(\beta)\|_1 \ \text{s.t.} \ || y_0 - A_0 \beta || \le \eps
\label{simpcs}
\eea

\item {\em Modified-CS. } If $t>0$, set $T = \Nhat_{t-1}$ and compute $\xhat_{t,modcs}$ as the solution of
\bea
\min_\beta  \|(\beta)_{T^c}\|_1 \ \text{s.t.} \ || y_t - A \beta || \le \eps
\label{modcs}
\eea
\label{step1}

\item {\em Additions / LS.} Compute $T_\dett$ and LS estimate using it:
\label{addls}
\bea
T_\dett \se T \cup \{i \in T^c: |(\xhat_{t,modcs})_i| > \alpha_{add} \} \nn \\
(\xhat_{t,\dett})_{T_\dett} \se {A_{T_\dett}}^\dag y_t, \ \ (\xhat_{t,\dett})_{T_\dett^c} = 0
\label{Tdett}
\eea

\item {\em Deletions / LS.} Compute $\tT$ and LS estimate using it:
\label{delete}
\bea
\tT \se  T_{\dett} \setminus  \{i \in T_\dett: |(\xhat_{t,\dett})_i| \le \alpha_{del} \} \nn \\

(\xhat_{t})_{\tT} \se {A_{\tT}}^\dag  y_t, \ \ (\xhat_{t})_{\tT^c} = 0
\label{finalls}
\eea

\item Set $\Nhat_t = \tT$. Output $\xhat_t$. Feedback $\Nhat_t$.

\een

\label{modcsalgo_2}
\end{algorithm}

\bd [Define $T_\dett,\Delta_\dett, \Delta_{e,\dett}$]
The set $T_\dett$ is the set obtained after the support addition step. It is defined in (\ref{Tdett}) in Algorithm \ref{modcsalgo_2}. We use $\Delta_\dett:=N_t \setminus  T_\dett$ to denote the missing elements from $T_\dett$ and we use $\Delta_{e,\dett}:=T_\dett \setminus N_t$ to denote the extras.
\ed

\subsection{Stability result for modified-CS with add-LS-del}
\label{stab_modcs}

The first step to show stability is to find sufficient conditions for (a) a certain set of large coefficients to definitely get detected, and (b) to definitely not get falsely deleted, and (c) for the zero coefficients in $T_\dett$ to definitely get deleted. These can be obtained using  Corollary \ref{modcs_cs_bnd} and the following simple facts which we state as a proposition, in order to easily refer to them later.
\begin{proposition}(simple facts)
\ben
\item An $i \in \Delta$ will definitely get detected if $|x_i|  > \alpha_{add} + \|x - \xhat_{modcs}\|$. This follows since  $ \|x - \xhat_{modcs}\| \ge \|x - \xhat_{modcs}\|_\infty \ge |(x - \xhat_{modcs})_{i}|$.
\label{det1}

\item Similarly, an $i \in T_\dett$ will definitely not get falsely deleted if $|x_i| >  \alpha_{del} + \|(x - \xhat_\dett)_{T_\dett}\|$.
\label{nofalsedel1}

\item All $i \in \Delta_{e,\dett}$ (the zero elements of $T_\dett$) will definitely get deleted if $\alpha_{del} \ge \|(x - \xhat_\dett)_{T_\dett}\|$.
\label{truedel1}

\item Consider LS estimation using known part of support $T$, i.e. consider the estimate $(\xhat_{LS})_T = {A_T}^\dag y$ and $(\xhat_{LS})_{T^c} = 0$ computed from $y:=Ax+w$. Let $\Delta = N \setminus T$ where $N$ is the support of $x$. If $\|w\| \le \eps$ and if $\delta_{|T|} < 1/2$, then $\|(x - \xhat_{LS})_{T}\| \le \sqrt{2} \eps + 2{\theta_{|T|,|\Delta|}} \|x_{\Delta}\|$ (instead of $\delta_{|T|} < 1/2$, one can pick any $b<1$ and the constants will change appropriately).
\label{errls1}

\een
\label{prop1}
\end{proposition}

Combining the above facts with Corollary \ref{modcs_cs_bnd}, we can easily get the following three lemmas.

\begin{lemma}[Detection condition]
Assume that $\|w\| \le \eps$, $|N| \le S_N$, $|\Delta_e| \le S_{\Delta_e}$, $|\Delta| \le S_\Delta$. Let $\Delta_1:=\{i \in \Delta: |x_i| \ge b_1 \}$. All elements of $\Delta_1$ will get detected at the current time if $\delta_{S_N + S_{\Delta_e} + S_\Delta} < (\sqrt{2}-1)/2$ and  $b_1 > \alpha_{add} + 8.79\eps$.

\label{detectcond_modcs}
\end{lemma}

{\em Proof: } The lemma follows from fact \ref{det1} of Proposition \ref{prop1} and Corollary \ref{modcs_cs_bnd}.

\begin{lemma}[No false deletion condition]
Assume that $\|w\| \le \eps$, $|T_\dett| \le S_T$ and $|\Delta_\dett| \le S_\Delta$. For a given $b_1$, let $T_1:=\{i \in T_\dett: |x_i| \ge b_1\}$. All $i \in T_1$ will not get (falsely) deleted at the current time if $\delta_{S_T} < 1/2$ and $b_1 > \alpha_{del} + \sqrt{2} \eps + 2{\theta_{S_T,S_\Delta}} \|x_{\Delta_\dett}\|$
\label{nofalsedelscond}
\end{lemma}

{\em Proof: } The lemma follows directly from fact \ref{nofalsedel1} and fact \ref{errls1} (applied with $T \equiv T_\dett$ and $\Delta \equiv \Delta_\dett$) of Proposition \ref{prop1}.

\begin{lemma}[Deletion condition]
Assume that $\|w\| \le \eps$, $|T_\dett| \le S_T$ and $|\Delta_\dett| \le S_\Delta$. All elements of $\Delta_{e,\dett}$ will get deleted if $\delta_{S_T} < 1/2$ and $\alpha_{del} \ge \sqrt{2} \eps + 2{\theta_{S_T,S_\Delta}} \|x_{\Delta_\dett}\|$.
\label{truedelscond}
\end{lemma}
{\em Proof: } The lemma follows directly from fact \ref{truedel1} and fact \ref{errls1} (applied with $T \equiv T_\dett$ and $\Delta \equiv \Delta_\dett$) of Proposition \ref{prop1}.

Using the above lemmas and the signal model, we can obtain sufficient conditions to ensure that, for some $d_0 \le d$, at each time $t$, $\tDelta_t \subseteq \Sset_t(d_0)$ (so that $|\tDelta| \le (2d_0-2)S_a$) and $|\tDelta_{e}|=0$, i.e. only elements smaller than $d_0 r$ may be missed and there are no extras. For notational simplicity, we state the special case below which uses $d_0=2$ (for the general case see Appendix \ref{stabres_modcs_gen}). The proof is given in Appendix \ref{proof_addLSdel_modcs}.

The proof again follows by induction, but is more complicated than that in the previous section, due to the support addition and deletion steps. We use the induction assumption; $T_t = \tT_{t-1}$; and the fact that $N_t = N_{t-1} \cup \Aset_t \setminus \Rset_t$ to bound $|T_t|,|\Delta_{e,t}|,|\Delta_t|$. This part of the proof is the same as that of Theorem \ref{stabres_simple_modcs}. The next two parts are different and more complicated. We use the bounds from the first part; equation (\ref{sseteq_2}); Lemma \ref{detectcond_modcs}; the limit on the number of false detections; and $|T_\dett| \le |N| + |\Delta_{e,\dett}|$ to bound $|\Delta_{\dett,t}|,|\Delta_{e,\dett,t}|,|T_{\dett,t}|$. Finally, we use the bounds from the second part and Lemmas \ref{nofalsedelscond} and \ref{truedelscond} to bound $|\tDelta_t|,|\tDelta_{e,t}|,|\tT_t|$.

\begin{theorem}[Stability of modified-CS with add-LS-del]
Assume Signal Model \ref{sigmod2} and  $\|w_t\| \le \eps$. If
\ben
\item {\em (addition and deletion thresholds) }
\ben
\item $\alpha_{add}$ is large enough so that there are at most $S_a$ false additions per unit time,
\label{addthresh}

\item $\alpha_{del}  = \sqrt{2} \eps +  2 \sqrt{S_a} \theta_{S_0+2S_a,S_a} r $,
\label{delthresh}
\een
\label{add_del_thresh}

\item {\em (support size, support change rate)} $S_0,S_a$ satisfy
\ben

\item $\delta_{S_0 + 3S_a} < (\sqrt{2}-1)/2$,

\item $\theta_{S_0+2S_a,S_a} < \frac{1}{2}  \frac{1}{2\sqrt{S_a}}$,
\label{theta_ass}
\een
\label{measmodel}

\item {\em (new element increase rate) } $r \ge \max(G_1,G_2)$, where
\label{add_del}
\bea
G_1 \sdefn  \frac{ \alpha_{add} + 8.79 \eps }{2} \nn \\
G_2 \sdefn \frac{\sqrt{2} \eps}{1 - 2\sqrt{S_a }\theta_{S_0+2S_a,S_a}}
\eea
\item {\em (initial time)} at $t=0$, $n_0$ is large enough to ensure that $\tDelta  \subseteq \Sset_0(2)$, $|\tDelta| \le 2S_a$,  $|\tDelta_e| =0$, $|\tT| \le S_0$,
\label{initass}
\een
then,  at all $t \ge 0$,
\ben
\item $|\tT_t| \le S_0$, $|\tDelta_{e,t}| =0$, and $|\tDelta_t| \le 2S_a$,

\item $|T_t| \le S_0$, $|\Delta_{e,t}| \le S_a$, and $|\Delta_t| \le 2S_a$

\item $|\tT_{\dett,t}| \le S_0+2S_a$, $|\tDelta_{e,\dett,t}| \le 2S_a$, and $|\tDelta_{\dett,t}| \le S_a$

\item $\|x_t-\xhat_t\| \le \sqrt{2} \eps + (2\theta_{S_0,2S_a}+1) \sqrt{2S_a} r$

\item $\|x_t - \xhat_{t,modcs}\| \le 8.79 \eps$
\een
\label{stabres_modcs}
\end{theorem}

\subsection{Discussion}
Notice that condition \ref{theta_ass} may become difficult to satisfy as soon as $S_a$ increases, which will happen when the problem dimension, $m$, increases (and consequently $S_0$ increases, even though $S_a$ and $S_0$ remain small fractions of $m$, e.g. typically $S_0 \approx 10\%m$ and $S_a \approx 0.2\%m$). The reason we need this condition is because in facts \ref{nofalsedel1} and \ref{truedel1} of Proposition \ref{prop1}, and hence also in lemmas \ref{nofalsedelscond} and \ref{truedelscond} and the final result, we bound the $\ell_\infty$ norm of the LS step error, $\|(x - \xhat_\dett)_{T_\dett}\|_\infty$ by the $\ell_2$ norm, $\|(x - \xhat_\dett)_{T_\dett}\|$.

This is clearly a loose bound - it holds with equality only when the entire LS step error is concentrated in one dimension. In practice, as observed in simulations, this is usually not true. The LS step error is quite spread out since the LS step tends to reduce the bias in the estimate. Thus it is not unreasonable to assume that $\|(x - \xhat_\dett)_{T_\dett}\|_\infty \le \|(x - \xhat_\dett)_{T_\dett}\| / \sqrt{S_a}$ (LS step error is spread out enough to ensure this) at all times. In simulations, we observed that when $m=200$, $S_0=20$, $S_a=2$,  $r=3/4$, $n=59$, $w_t \sim^{i.i.d.} unif(-c,c)$ with $c=0.1266$, and we used $\alpha_{add}=c/2$, $\alpha_{del}=r/2$ this was true 99.8\% of the times. The same was true even with $r$ was reduced to $2/5$. When we increased the problem size five times to $m=1000$, $S_0=100$, $S_a=10$, $n=295$, this was true 93\% of the times. In all cases, 100\% of the times, $(\|(x - \xhat_\dett)_{T_\dett}\|/\sqrt{S_a}) /\|(x - \xhat_\dett)_{T_\dett}\|_\infty < 0.78$. All simulations used a random-Gaussian matrix $A$.

With this extra assumption, lemmas \ref{nofalsedelscond} and \ref{truedelscond} will get replaced by the following two lemmas. With using these new lemmas, condition \ref{theta_ass} will get replaced by $\theta_{S_0+2S_a,S_a} < 1/4$ which is an easily satisfiable condition. Moreover, this also makes the lower bound on the required value of $r$ (rate of coefficient increase/decrease) smaller.

\begin{lemma}
Assume that $\|w\| \le \eps$, $|T_\dett| \le S_T$ and $|\Delta_\dett| \le S_\Delta$.  For a given $b_1$, let $T_1:=\{i \in T_\dett: |x_i| \ge b_1\}$. All $i \in T_1$ will not get (falsely) deleted at the current time if
\ben
\item  $\delta_{S_T} < 1/2$,
\item  $\|(x - \xhat_\dett)_{T_\dett}\|_\infty \le \|(x - \xhat_\dett)_{T_\dett}\| / \sqrt{S_a}$ (the LS step error is spread out enough), and
\item $b_1 > \alpha_{del} + (\sqrt{2} \eps + 2{\theta_{S_T,S_\Delta}} \|x_{\Delta_\dett}\|)/ \sqrt{S_a}$.

\een
\label{nofalsedels_equalLS}
\end{lemma}

\begin{lemma}[Deletion condition]
Assume that $\|w\| \le \eps$, $|T_\dett| \le S_T$ and $|\Delta_\dett| \le S_\Delta$.
All elements of $\Delta_{e,\dett}$ will get deleted if
\ben
\item  $\delta_{S_T} < 1/2$,
\item  $\|(x - \xhat_\dett)_{T_\dett}\|_\infty \le \|(x - \xhat_\dett)_{T_\dett}\| / \sqrt{S_a}$ (the LS step error is spread out enough), and
\item $\alpha_{del} \ge (\sqrt{2} \eps + 2{\theta_{S_T,S_\Delta}} \|x_{\Delta_\dett}\|)/ \sqrt{S_a}$.

\een
\label{truedelscond_equalLS}
\end{lemma}

By using lemmas \ref{nofalsedels_equalLS} and \ref{truedelscond_equalLS} instead of lemmas \ref{nofalsedelscond} and \ref{truedelscond} respectively,  and doing everything else exactly as in the proof of Theorem \ref{stabres_modcs}, we get the following corollary.

\begin{corollary}[Stability of modified-CS with add-LS-del]
Assume Signal Model \ref{sigmod2} and  $\|w_t\| \le \eps$. Let $e_t:=(x_t - \xhat_{\dett,t})_{T_{\dett,t}}$. Assume that $\|e_t\|_\infty \le \|e_t\| / \sqrt{S_a}$ at all $t$ (the LS step error is spread out enough). If

\ben
\item {\em (addition and deletion thresholds) }
\ben
\item $\alpha_{add}$ is large enough so that there are at most $S_a$ false additions per unit time,
\label{addthresh}

\item $\alpha_{del}  = \sqrt{\frac{2}{S_a}} \eps + 2 \theta_{S_0+2S_a,S_a} r $,
\label{delthresh}
\een
\label{add_del_thresh}

\item {\em (support size, support change rate)} $S_0,S_a$ satisfy
\ben
\item  $\delta_{S_0 + 3S_a} \le (\sqrt{2}-1)/2$,
\label{measmod_delta}

\item $\theta_{S_0+2S_a,S_a} \le  \frac{1}{4}$
\label{measmod_theta}
\een
\label{measmodel}

\item {\em (new element increase rate) } $r \ge \max(G_1,G_2)$, where
\label{add_del}
\bea
G_1 \sdefn \frac{ \alpha_{add} + C_1(S_0 + 3S_a ) \eps }{2} \le \frac{ \alpha_{add} + 8.79 \eps }{2}  \nn \\
G_2 \sdefn \frac{\sqrt{2} \eps}{\sqrt{S_a} (1 - 2\theta_{S_0+2S_a,S_a})}

\eea

\item {\em (initial time)} at $t=0$, $n_0$ is large enough to ensure that $\tDelta  \subseteq \Sset_0(2)$, $|\tDelta| \le 2S_a$,  $|\tDelta_e| =0$, $|\tT| \le S_0$,
\label{initass}

\een
then all conclusions of Theorem  \ref{stabres_modcs} hold.
\label{cor2_relax}
\end{corollary}

Notice that conditions \ref{delthresh}, condition \ref{measmod_theta} and condition \ref{add_del} ($r \ge G_2$) are weaker compared to those in Theorem \ref{stabres_modcs}. Everything else is the same. For large sized problems, condition \ref{measmod_theta} of Theorem \ref{stabres_modcs} is the stronger condition out of the two conditions that $S_0, S_a$ needed to satisfy. On the other hand, in this corollary, condition \ref{measmod_delta} is the stronger of the two. This condition is easy to satisfy even for large sized problems.

Let us compare our result with the CS result given in Corollary \ref{cs_bnd}. It needs $\delta_{2S_0} < (\sqrt{2}-1)/2=0.207$. On the other hand, if the LS step error is spread out enough, we only need (a) $\delta_{S_0 + 3S_a} \le (\sqrt{2}-1)/2=0.207$ and (b) $\theta_{S_0+2S_a,S_a} < \frac{1}{4}$. Notice that the LHS of (b) is not larger than that of (a) while its RHS is larger. Thus, (a) is the dominant condition. When $S_a \ll S_0$ (in fact as long as $S_a < S_0/3$), clearly this is weaker than what CS needs to achieve the same error bound.

Also, let us compare this result with that for modified-CS (without add-LS-del) given in Theorem \ref{stabres_simple_modcs}. Because of add-LS-del, the addition threshold, $\alpha_{add}$, can now be much smaller, as long as the number of false adds is small\footnote{e.g. in simulations with $r=0.4$, we were able to use $\alpha_{add}=0.06$ and still ensure number of false adds less than $S_a$ (other parameters: $m=200$, $S_0=20$, $S_a=2$,  $r=0.4$, $n=59$, $w_t \sim^{i.i.d.} unif(-c,c)$ with $c=0.1266$, $\alpha_{add}=0.06$, $\alpha_{del}=r/2$).}. If $\alpha_{add}$ is close to zero, the value of $G_1$ is almost half that of $G$, i.e. the minimum required coefficient increase rate, $r$, gets reduced by almost half. Notice that since $\theta_{S_0+2S_a} \le 1/4$, so $G_2 \le (2\sqrt{2} \eps)/\sqrt{S_a} \le 4.4 \eps \le G_1$, i.e. the upper bound on $G_2$ is smaller than $4.4 \eps$, which is the lower bound on $G_1$. Thus $G_1$ is what decides the minimum allowed value of $r$.


TITLE: Representation of symmetric group as Cremona transformations
QUESTION [1 upvotes]: Question from me and a colleague:
Given a matrix
\begin{equation}
U =
\begin{bmatrix}
U_{11} & U_{12} \\
U_{21} & U_{22}
\end{bmatrix}
\quad \text{with } U_{22} \neq 0,
\end{equation}
denote its determinant by $\Delta$ and let
\begin{equation} \label{defineswap}
\operatorname{sw}(2 \overline{2})(U) =
\begin{bmatrix}
\Delta/U_{22} & U_{12}/U_{22}\\
-U_{21}/U_{22} & 1/U_{22}
\end{bmatrix},
\end{equation}
a matrix with determinant $U_{11}/U_{22}$.
(The notation is meant to suggest the word ``swap.")
Suppose that the indeterminates
$U_{11}$, $U_{12}$,
$U_{21}$, $U_{22}$
are replaced by rational functions of
four indeterminates
$z(1)$, $z(2)$, $z(\overline{1})$, $z(\overline{2})$.
Then these two equations are equivalent:
\begin{equation}
U
\begin{bmatrix}
z(1) \\
z(2)
\end{bmatrix}
=
\begin{bmatrix}
z(\overline{1}) \\
z(\overline{2})
\end{bmatrix}
\quad \Leftrightarrow \quad
\operatorname{sw}(2 \overline{2})(U)
\begin{bmatrix}
z(1) \\
z(\overline{2})
\end{bmatrix}
=
\begin{bmatrix}
z(\overline{1}) \\
z(2)
\end{bmatrix}.
\end{equation}
This seems to be the tip of an iceberg: there is a representation
$$
\operatorname{sw}: S_{4} \to \operatorname{Crem}(M_2)
$$
of the symmetric group $S_{4}$ in the group of Cremona transformations of the
space of $2$-by-$2$ matrices. We think of $S_{4 }$ as the group of permutations
of the set $\{1,2,\overline{1},\overline{2}\}$, and for each such permutation $\pi$
we have
\begin{equation}
\operatorname{sw}(\pi)(U)
\begin{bmatrix}
z(\pi(1)) \\
z(\pi(2))
\end{bmatrix}
=
\begin{bmatrix}
z(\pi(\overline{1})) \\
z(\pi(\overline{2}))
\end{bmatrix}.
\end{equation}
If $\pi$ is an element of the subgroup $S_2 \times S_2$, then $\operatorname{sw}(\pi)$
is just the appropriate simultaneous permutation of rows and columns.
This leads us to ask whether there is a representation
$$
\operatorname{sw}: S_{2n} \to \operatorname{Crem}(M_n)
$$
with similar properties. Suppose that $U$ is an $n$-by-$n$ matrix of indeterminates,
and that its entries have been replaced by rational functions in
the indeterminates $z(1), z(2), \dots, z(n), z(\overline{1}), z(\overline{2}), \dots, z(\overline{n})$
so as to satisfy
this equation:
\begin{equation}
U
\begin{bmatrix}
z(1) \\
z(1) \\
\vdots \\
z(n)
\end{bmatrix}
=
\begin{bmatrix}
z(\overline{1}) \\
z(\overline{2}) \\
\vdots \\
z(\overline{n})
\end{bmatrix}.
\end{equation}
Think of $S_{2n}$ as the group of permutations
of the set $\{1,2,\dots,n,\overline{1},\overline{2},\dots,\overline{n}\}$.
We demand that
for each such permutation $\pi$
we have
\begin{equation}
\operatorname{sw}(\pi)(U)
\begin{bmatrix}
z(\pi(1)) \\
z(\pi(2)) \\
\vdots \\
z(\pi(n))
\end{bmatrix}
=
\begin{bmatrix}
z(\pi(\overline{1})) \\
z(\pi(\overline{2})) \\
\vdots \\
z(\pi(\overline{n}))
\end{bmatrix},
\end{equation}
and we demand that
if $\pi$ is an element of the subgroup $S_n \times S_n$, then $\operatorname{sw}(\pi)$
is the appropriate simultaneous permutation of rows and columns.

REPLY [1 votes]: Serge Cantat provided a definitive explanation.
In the Grassmannian $G(n,2n)$, there is an open dense subset
consisting of those $n$-planes that are the graphs of linear maps
from $\mathbb A^n$ to $\mathbb A^n$.
The symmetric group $S^{2n}$ acts on the Grassmannian, and
if we restrict the action to this open set we see the desired representation.
To illustrate in the case $n=2$, here's how to obtain the matrix formula
shown above. Represent a point of the Grassmannian $G(2,4)$ by a 4-by-2 matrix whose columns span the 2-plane. The matrix $U$  determines the point
\begin{equation*}
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
U_{11} & U_{12} \\
U_{21} & U_{22}
\end{bmatrix}.
\end{equation*}
We now compute how the transposition $(2 \overline{2})$ acts:
\begin{equation*}
(2 \overline{2}) \cdot
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
U_{11} & U_{12} \\
U_{21} & U_{22}
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
U_{11} & U_{12} \\
U_{21} & U_{22}
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 \\
U_{21} & U_{22} \\
U_{11} & U_{12} \\
0 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
\Delta/U_{22} & U_{12}/U_{22}\\
-U_{21}/U_{22} & 1/U_{22}
\end{bmatrix}.
\end{equation*}
(To obtain the last equation we have used column operations to restore an identity matrix at the top.)
The bottom square matrix is exactly what we wrote above.
Alternatively, we may use the Plücker coordinates obtained from the six 2-by-2 subdeterminants:
\begin{equation*}
\begin{aligned}
U \mapsto \, & [1:U_{12}:U_{22}:-U_{11}:-U_{21}:\Delta] \\
(2 \overline{2}) \cdot U \mapsto \, & [U_{22}:U_{12}:1:-\Delta:U_{21}:U_{11}] \\
& =
\left[1:
\frac{U_{12}}{U_{22}}:
\frac{1}{U_{22}}:
\frac{-\Delta}{U_{22}}:
\frac{U_{21}}{U_{22}}:
\frac{U_{11}}{U_{22}}:
\right]
\end{aligned}
\end{equation*}
and note that the point of projective space $\mathbb P^5$ we obtain is the image of the matrix in our formula.