text:
\begin{document}

\maketitle

\begin{abstract}
 We introduce an inexact oracle model for variational inequalities (VI) with monotone operator, propose a numerical method which solves such VI's and analyze its convergence rate. As a particular case, we consider VI's with H\"older-continuous operator and show that our algorithm is universal. This means that without knowing the H\"older parameter $\nu$ and H\"older constant $L_{\nu}$ it has the best possible complexity for this class of VI's, namely our algorithm has complexity $O\left( \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}}R^2 \right)$, where $R$ is the size of the feasible set and $\varepsilon$ is the desired accuracy of the solution. We also consider the case of VI's with strongly monotone operator and generalize our method for VI's with inexact oracle and our universal method for this class of problems. Finally, we show, how our method can be applied to convex-concave saddle point problems with H\"older-continuous partial subgradients.
 \\
 \textbf{Keywords: }Variational inequality, monotone operator, H\"older continuity, inexact oracle, complexity estimate\\
 \textbf{AMS: }65K15
, 90C33
, 90C06
, 68Q25

, 65Y20
, 68W40
, 58E35

\end{abstract}

\section{Introduction}
\label{S:Intro}
The main problem, we consider, is the following weak variational inequality (VI)
\begin{equation}
\text{Find} \quad x_* \in Q : \quad \langle g(x), x_* - x \rangle \leq 0, \quad \forall x \in Q
\label{eq:PrSt}
\end{equation}
where $Q$ is a closed convex subset of finite-dimensional vector space $E$ and continuous operator $g(x): Q \to E^*$ is monotone
$$
\langle g(x) - g(y) , x - y \rangle \geq 0, \quad x,y \in Q.
$$
Under the assumption of continuity and monotonicity of the operator, this problem is equivalent to strong variational inequality, in which the goal is to find $x_* \in Q $ s.t. $\langle g(x_*), x_* - x \rangle \leq 0, \quad \forall x \in Q$. Variational inequalities with monotone operators are strongly connected with convex optimization problems and convex-concave saddle point problems. In the former case, operator $g$ is the subgradient of the objective, and in the latter case operator $g$ is composed from partial subgradients of the objective in the saddle point problem. Studying VI's is also important for equilibrium and complementarity problems \cite{harker1990finite,facchinei2007finite}.
Our focus here is on numerical methods for such problems, their convergence rate and complexity estimates. Numerical methods for VI's are known since 1970's when the extragradient method was proposed in \cite{korpelevich1976extragradient}. More recently, \cite{nemirovski2004prox} proposed a non-Euclidean variant of this method, called Mirror Prox algorithm. Under the assumption of $L_1$-Lipschitz continuity of the operator $g$, i.e. $g$ satisfies $\|g(x)-g(y)\|_*\leq L_1\|x-y\|$, $x,y \in Q$, this method has complexity $O\left(\frac{L_1R^2}{\varepsilon}\right)$, where $R$ characterizes the diameter of the set $Q$, $\varepsilon$ is the desired accuracy. By complexity we mean the number of iterations of an algorithm to find a point $\widehat{x} \in Q$ s.t.
\[
\max_{u \in Q} \langle g(u), \widehat{x} - u \rangle \leq \varepsilon.
\]
Different methods with similar complexity were also proposed in \cite{solodov1999hybrid,auslender2005interior,nesterov2007dual,monteiro2010complexity,koshal2011multiuser,Mish2019,Bot,Malitsky2018}. In the same paper \cite{nesterov2007dual}, Nesterov proposed a method for VI's with bounded variation of the operator $g$, i.e. $g$ satisfying $\|g(x)-g(y)\|_*\leq L_0$, $x,y \in Q$ for some $L_0 >0$, and complexity $O\left(\frac{L_0^2R^2}{\varepsilon^2}\right)$. He also raised a question, whether it is possible to propose a method, which automatically "adjusts to the actual level of smoothness of the current problem instance". One of the goals of this paper is to propose such an algorithm.

To do so, we consider a more general class of operators $g$ being H\"older-continuous on $Q$, i.e., for some $\nu \in [0,1]$ and $L_{\nu} \geq 0$,
\begin{equation}
\label{eq:GHoeldDef}
\|g(x) - g(y)\|_* \leq L_{\nu}\|x-y\|^{\nu}, \quad x,y \in Q.
\end{equation}
This class covers both the case of $g$ with bounded variation ($\nu = 0$) and Lipschitz-continuous $g$ ($\nu = 1$). Variational inequalities with H\"older-continuous monotone operator were already considered in \cite{nemirovski2004prox}, where a special choice of the stepsize for the Mirror Prox algorithm leads to complexity
\[
O\left(\left(\frac{L_{\nu}}{\varepsilon}\right)^{\frac{2}{1+\nu}} R^2 \right),
\]
which is optimal for this class of problems, see \cite{nemirovsky1983problem}. The authors of \cite{dang2015convergence} consider VI's with non-monotone H\"older-continuous operator. Unfortunately, both papers use $\nu$ and $L_{\nu}$ to define the stepsize of their methods. This is in contrast to optimization, where so called universal algorithms were proposed, which do not use the information about the H\"older class $\nu$ and H\"older constant $L_{\nu}$, see \cite{nesterov2015universal,lan2015generalized,gasnikov2018universal,baimurzina2017universal,dvurechensky2017gradient,dvurechensky2017universal,guminov2017universal,guminov2019accelerated}. In this paper, we propose a universal method for VI's with H\"older-continuous monotone operator. We also generalize this method for the case of VI's with strongly monotone operator. Such problems were considered in \cite{nesterov2011strongly_VI}, but only for the case $\nu=1$ and known constant $L_1$.

On the other hand, as it was shown for optimization problems by \cite{devolder2014first,nesterov2015universal}, universal methods have an interesting connection with methods for smooth problems with inexact oracle. Namely, it can be shown that a function with H\"older-continuous subgradient can be considered as a Lipschitz-smooth function with inexact oracle. Despite that there are many works on optimization methods with inexact oracle, see e.g. \cite{aspremont2008smooth,devolder2014first,dvurechensky2016stochastic,bogolubsky2016learning,dvurechensky2017universal,cohen2018acceleration,aybat2018robust,stonyakin2019gradient}, we are not aware of any definition of inexact oracle for VI's and methods for VI's with inexactly given operator. By this paper, we close this gap and introduce a theory for methods for VI's with inexact oracle.

To sum up, our contributions in this paper are as follows.
\begin{itemize}
	\item We introduce a definition of inexact oracle for VI's with monotone operator and provide several natural examples, where such inexactness naturally arises.
	\item We show, how H\"older-continuous operator can be dealt with in our framework of inexact oracle.
	\item We generalize Mirror Prox algorithm for VI's with inexact oracle and provide theoretical analysis of its convergence rate.
	\item As a corollary, we prove that this method is universal for VI's with H\"older-continuous monotone operator, i.e. has complexity
	\[
	O\left( \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}}R^2 \right)
	\]
	and, unlike existing methods, does not require any knowledge about $L_{\nu}$ or $\nu$.
	\item We generalize our algorithm for the case of $\mu$-strongly monotone operator $g$ and obtain complexity
	\[
	O\left( \inf_{\nu \in [0,1]} \left(\frac{L_{\nu}}{\mu}\right)^{\frac{2}{1+\nu}}\frac{1}{\varepsilon^{\frac{1-\nu}{1+\nu}}} \cdot \log_2 \frac{R^2}{\varepsilon}\right)
	\]
	to find a point $\widehat{x} \in Q$ s.t. $\|\widehat{x} - x_* \| \leq \varepsilon$.
	\item Finally, we show, how our method can be applied to convex-concave saddle point problems.
\end{itemize}

\subsection{Preliminaries}
\label{S:prel}
We start with the general notation and description of proximal setup.
Let $E$ be a finite-dimensional real vector space and $E^*$ be its dual. We denote the value of a linear function $u \in E^*$ at $x\in E$ by $\langle u, x \rangle$. Let $\|\cdot\|$ be some norm on $E$, $\|\cdot\|_{*}$ be its dual, defined by $\|u\|_{*} = \max\limits_{x} \big\{ \langle u, x \rangle, \| x \| \leq 1 \big\}$. We use $\nabla f(x)$ to denote any subgradient of a function $f$ at a point $x \in {\rm dom} f$.

We choose a {\it prox-function} $d(x)$, which is continuous, convex on $Q$ and
\begin{enumerate}
	\item admits a continuous in $x \in Q^0$ selection of subgradients $\nabla d(x)$, where $Q^0 \subseteq Q$ is the set of all $x$, where $\nabla d(x)$ exists;
	\item $d$ is $1$-strongly convex on $Q$ with respect to $\|\cdot\|$, i.e., for any $x \in Q^0, y \in Q$ $d(y)-d(x) -\langle \nabla d(x) ,y-x \rangle \geq \frac12\|y-x\|^2$.
\end{enumerate}
Without loss of generality, we assume that $\min\limits_{x\in Q} d(x) = 0$.

We define also the corresponding {\it Bregman divergence} $V[z] (x) = d(x) - d(z) - \langle \nabla d(z), x - z \rangle$, $x \in Q, z \in Q^0$. Standard proximal setups, i.e. Euclidean, entropy, $\ell_1/\ell_2$, simplex, nuclear norm, spectahedron can be found in \cite{ben-tal2015lectures}.
Below we use Bregman divergence in so-called {\it prox-mapping}
\begin{equation}
\min_{x \in Q} \left\{\langle g,x \rangle + M V[\bar{x}](x)		 \right\} ,
\label{eq:PrMap}
\end{equation}
where $M >0 $, $\bar{x} \in Q^0$, $g \in E^*$ are given. We allow this problem to be solved inexactly in the following sense.
Assume that we are given $\delta_{pu} >0$, $M >0 $, $\bar{x} \in Q^0$, $g \in E^*$. We call a point $\tilde{x} = \tilde{x}(\bar{x},g,M,\delta_{pc},\delta_{pu}) \in Q^0$ an {\it inexact prox-mapping} iff for any $\delta_{pc} >0$ we can calculate $\tilde{x}$ s.t. it holds that
\begin{equation}
\left\langle g + M\left[\nabla d(\tilde{x}) - \nabla d(\bar{x}) \right], u - \tilde{x} \right\rangle \geq - \delta_{pc}-\delta_{pu}, \quad \forall u \in Q.
\label{eq:InPrMap}
\end{equation}
We write
\begin{equation}
\tilde{x} = {\mathop {\arg \min }\limits_{x\in Q}}^{\delta_{pc}+\delta_{pu}}\left\{\langle g,x \rangle + M V[\bar{x}](x)	 \right\}.
\label{eq:InPrMap1}
\end{equation}
Here $\delta_{pu}$ denotes the error of the prox-mapping, which is not controlled, and $\delta_{pc}$ denotes the error of the prox-mapping, which can be controlled and made as small as desired.

\section{Inexact Oracle for Variational Inequalities}
\label{S:IO}

Our goal is to consider in a unified manner VI's with H\"older-continuous operator and VI's with inexact information about the operator. This can be done by considering H\"older-continuous operator as a particular case of Lipschitz-continuous operator with some inexactness. Thus, we introduce the following definition of inexact oracle for the operator $g$.

\begin{Def}
	\label{Def:IO}
	We assume that there exists some $\delta_u > 0$ (uncontrolled error) and for any points $x,y \in Q$ for any number $\delta_c > 0$ (controlled error) there exists a constant $L(\delta_c) \in (0, +\infty)$ and one can calculate $\tilde{g}(x,\delta_c,\delta_u), \tilde{g}(y,\delta_c,\delta_u) \in E^*$ satisfying
	\begin{align}
	\langle \tilde{g}(y,\delta_c,\delta_u) - \tilde{g}(x,\delta_c,\delta_u), y - z \rangle & \leq \frac{L(\delta_c)}{2}\left(\|y-x\|^2 + \|y-z\|^2\right) + \delta_c+\delta_u, 	\label{eq:g_or_def} \\
	\langle \tilde{g}(y,\delta_c,\delta_u) - g(y), y - z \rangle & \geq - \delta_u, \quad \forall z \in Q. \label{eq:g_or_deff}
	\end{align}

\end{Def}

In this definition, $\delta_c$ represents the error of the oracle, which we can control and make as small as we would like to. On the opposite, $\delta_u$ represents the error which we can not control.

The following examples show that this definition is reasonable and satisfies our goal of covering both the case of H\"older-continuous operator and the case of inexact values of the operator.

\begin{Ex}

[\textit{Lipschitz-continuous operator with inexact values and bounded set}]
\label{Ex:Lip_oper}

	Let us assume that
	\begin{enumerate}
		\item The operator $g$ is $L$-smooth on $Q$, i.e., for all $x,y \in Q$, $\|g(x) - g(y)\|_* \leq L\|x-y\|$.
		\item\label{eq:def_in_2} The set $Q$ is bounded with $\max_{x, y \in Q} \|x-y\| \leq D$.
		\item\label{eq:def_in_3} There exists $\bar{\delta}_u > 0$ and, at any point $x \in Q$, we can calculate approximation $\bar{g}(x)$ for $g(x)$ s.t. $\|\bar{g}(x)-g(x)\|_* \leq \bar{\delta}_u$.
	\end{enumerate}
	Then, for any $z \in Q$,
	\begin{align*}
	\langle \bar{g}(y) - \bar{g}(x) , y-z \rangle & \hspace{-0.2em} = \hspace{-0.2em} \langle \bar{g}(y) - g(y) , y-z \rangle - \langle \bar{g}(x) - g(x) , y-z \rangle + \langle g(y) - g(x) , y-z \rangle \\
	& \leq 2 \bar{\delta}_u D + \|g(y) - g(x) \|_* \|y-z\| \leq 2 \bar{\delta}_u D + L \|y-x\| \|y-z\| \\
	& \leq 2 \bar{\delta}_u D + \frac{L}{2}\left(\|y-x\|^2 + \|y-z\|^2\right).
	\end{align*}
	Thus, we can set $\delta_u = 2 \bar{\delta}_u D$ and $L(\delta_c) \equiv L$. Further,
	$$|\langle \overline{g}(y)-g(y),y-z \rangle|\leq \| \overline{g}(y)-g(y) \|_* \|y-z\| \leq \overline{\delta}_{u}D = \frac{1}{2}\delta_u < \delta_u$$
	and we have
	$$
	\langle \overline{g}(y)-g(y),y-z \rangle > - \delta_u.
	$$
\end{Ex}

\begin{Ex}

[\textit{H\"older-continuous operator}]
\label{Ex:Hold}

	Assume that operator $g$ is H\"older-continuous on $Q$, i.e. \cref{eq:GHoeldDef} holds. The following technical lemma is the main clue for considering such operators in the inexact oracle framework.

	\begin{Lm}
		\label{Lm:HoldToLip}
		Let $a,b,c \geq 0$, $\nu \in [0,1]$. Then, for any $\delta > 0$,
		$$
		ab^{\nu}c \leq \left(\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu}} \frac{a^{\frac{2}{1+\nu}}}{2} \left(b^2+c^2\right) + \frac{\delta}{2}.
		$$
	\end{Lm}
	The proof of this lemma is given in the \cref{appA}.
	Using this Lemma, we have, for any $x,y,z \in Q$ and $\delta > 0$,
	\begin{align*}
	\langle g(y) - g(x) , y-z \rangle & \leq \|g(y) - g(x) \|_* \|y-z\| \leq L_{\nu}\|x-y\|^{\nu} \|y-z\| \\

	& \leq \frac{1}{2}\left(\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}} \left(\|x-y\|^2+\|y-z\|^2\right) + \frac{\delta}{2}.
	\end{align*}
	Thus, we can set $\delta_u = 0$, $\delta_c =\frac{\delta}{2}$, and $L(\delta_c) = \left(\frac{1}{2\delta_c}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}}$ to get \cref{eq:g_or_def}. Inequality \cref{eq:g_or_deff} holds as equality.
\end{Ex}

\begin{Ex}

[\textbf{\it H\"older-continuous operator with inexact values on a bounded set}]
\label{Ex:HoldInexact}

	Let us assume that:
	\begin{enumerate}
		\item The operator $g(x)$ is H\"older-continuous on $Q$, i.e. satisfies \cref{eq:GHoeldDef}.

		\item\label{eq:def_in_2_ex3} The set $Q$ is bounded with $\max_{x, y \in Q} \|x-y\| \leq D$.
		\item\label{eq:def_in_3_ex3} There exist $\bar{\delta}_u > 0$ and at any point $x \in Q$, we can calculate approximation $\bar{g}(x)$ for $g(x)$ s.t. $\|\bar{g}(x)-g(x)\|_* \leq \bar{\delta}_u$.
	\end{enumerate}
	Then, for any $z \in Q$,
	\begin{align*}
	\langle \bar{g}(y) - \bar{g}(x) , y-z \rangle & \hspace{-0.2em} = \hspace{-0.2em} \langle \bar{g}(y) - g(y) , y-z \rangle - \langle \bar{g}(x) - g(x) , y-z \rangle + \langle g(y) - g(x) , y-z \rangle \\
	& \leq 2 \bar{\delta}_u D + \|g(y) - g(x) \|_{*} \|y-z\| \leq 2 \bar{\delta}_u D + L_{\nu} \|y-x\|^{\nu} \|y-z\| \\
	& \leq 2 \bar{\delta}_u D + \frac{1}{2}\left(\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}} \left(\|x-y\|^2+\|y-z\|^2\right) + \frac{\delta}{2},
	\end{align*}
	where \cref{Lm:HoldToLip} was used to get the last inequality. \\
	Thus, we can set $\delta_u = 2 \bar{\delta}_u D$, $\delta_c =\frac{\delta}{2}$, and $L(\delta_c) = \left(\frac{1}{2\delta_c}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}}$ to get \cref{eq:g_or_def}. Inequality \cref{eq:g_or_deff} can be shown in the same way as in the \cref{Ex:Lip_oper}.
\end{Ex}

\begin{Ex}

[\textbf{\it Connection with $(\delta,L)$-oracle in optimization}]
\label{ExampVI2.5}

Let convex function $f:\,Q\rightarrow\mathbb{R}$, where $Q$ is convex compact, be endowed with $(\delta,L)$-oracle \cite{devolder2014first}. This means that for some $L > 0$ at any $y \in Q$ there exist a pair
$(f_{\delta}(y),g_{\delta}(y))\in \mathbb{R}\times\mathbb{R}^{n}$ such that, for all $y \in Q$
\begin{equation}\label{EEE2}
f_{\delta}(y)+\langle g_{\delta}(y),x-y\rangle\leq f(x)\leq f_{\delta}(y)+\langle g_{\delta}(y),x-y\rangle+\frac{L\|x-y\|^{2}}{2}+\delta
\end{equation}
Let us show that $g_{\delta}$ satisfies \cref{Def:IO}.

Clearly, for all $x\in Q$,
$f_{\delta}(x)\leq f(x)\leq f_{\delta}(x)+\delta $.
Further, by left inequality in \eqref{EEE2}:
$$f(x)\geq f_{\delta}(y)+\langle g_{\delta}(y),x-y\rangle\geq f(y)+\langle g_{\delta}(y),x-y\rangle-\delta,$$
and
\begin{equation}\label{eqv_plus}
\langle g_{\delta}(y),x-y\rangle\leq f(x)-f(y)+\delta\quad\forall\,x,y\in Q.
\end{equation}
The right inequality in \eqref{EEE2} means for all $x,y,z\in Q$:
$$f(x)\leq f_{\delta}(z)+\langle g_{\delta}(z),x-z\rangle+\frac{L}{2}\|x-z\|^{2}+\delta\leq f(z)+ \langle g_{\delta}(z),x-z\rangle+\frac{L}{2}\|x-z\|^{2} +\delta,$$
and
$$f(x)-f(z)\leq \langle g_{\delta}(z),x-z\rangle+\frac{L}{2}\|x-z\|^{2} +\delta,$$
and, similarly,
$$f(z)-f(y)\leq \langle g_{\delta}(y),z-y\rangle+\frac{L}{2}\|z-y\|^{2} +\delta.$$
So, $f(x)-f(y)-\langle g_{\delta}(z),x-z\rangle-\langle g_{\delta}(y),z-y\rangle\leq\frac{L}{2}\|x-z\|^{2}+\frac{L}{2}\|z-y\|^{2} +2\delta.$
Further, \eqref{eqv_plus} means:
$$\langle g_{\delta}(y),x-y\rangle-\langle g_{\delta}(z),x-z\rangle-\langle g_{\delta}(y),z-y\rangle\leq\frac{L}{2}\|z-x\|^{2}+\frac{L}{2}\|y-z\|^{2} +3\delta, \text{ i.e.}$$
$$\langle g_{\delta}(y)- g_{\delta}(z),x-z\rangle\leq\frac{L}{2}\|z-x\|^{2}+\frac{L}{2}\|y-z\|^{2} +3\delta,$$
or
$$\langle g_{\delta}(z)- g_{\delta}(y),z-x\rangle\leq\frac{L}{2}\|z-x\|^{2}+\frac{L}{2}\|z-y\|^{2} +3\delta,\quad \forall\,x,y,z\in Q.$$
So, \eqref{eq:g_or_def} holds for $L(\delta_{c})=L,\,\delta_{c}=0$ and $\delta_{u}=3\delta$ and $\tilde{g}(y,\delta_c,\delta_u) = g_{\delta}(y)$.

Under additional assumption $ \|g_{\delta}(y)-g(y) \| \leq \bar{\delta}_u$, we have:
	\begin{equation}
	\label{eq:ex4_10s2}
	\langle g_{\delta}(y)-g(y),y-x \rangle \geq -
	\bar{\delta}_u \|x-y\| \geq - \bar{\delta}_u D, \quad \forall x,y \in Q,
	\end{equation}
i.e. \eqref{eq:g_or_deff} holds.

\end{Ex}

\section{Generalized Mirror Prox}
In this section, we introduce a new algorithm for problem \cref{eq:PrSt} with inexact oracle for $g$ satisfying \cref{Def:IO}, which we call Generalized Mirror Prox (GMP). The algorithm is listed as \cref{Alg:UMP} below.

\begin{algorithm}[ht]
\caption{Generalized Mirror Prox}
\label{Alg:UMP}
\begin{algorithmic}[1]
 \REQUIRE accuracy $\e > 0$, uncontrolled oracle error $\delta_u >0$, uncontrolled error of prox-mapping $\delta_{pu} >0$, initial guess $M_{-1} >0$, prox-setup: $d(x)$, $V[z] (x)$.
 \STATE Set $k=0$, $z_0 = \arg \min_{u \in Q} d(u)$.
 \FOR{$k=0,1,...$}
			\STATE Set $i_k=0$, $\delta_{c,k} = \frac{\e}{4}$, $\delta_{pc,k} = \frac{\e}{8}$.
			\REPEAT
				\STATE Set $M_k=2^{i_k-1}M_{k-1}$.

				\STATE Calculate
				\begin{equation}
				w_k={\mathop {\arg \min }\limits_{x\in Q}}^{\delta_{pc,k}+\delta_{pu}} \left\{\la \tg(z_k,\delta_{c,k},\delta_u),x \ra + M_kV[z_k](x) 		 \right\}.
				\label{eq:UMPwStep}
				\end{equation}

				\STATE Calculate
				\begin{equation}
				z_{k+1}={\mathop {\arg \min }\limits_{x\in Q}}^{\delta_{pc,k}+\delta_{pu}} \left\{\la \tg(w_k,\delta_{c,k},\delta_u),x \ra + M_kV[z_k](x) 		 \right\}.
				\label{eq:UMPzStep}
				\end{equation}
				\STATE $i_k=i_k+1$.
			\UNTIL{
			\begin{equation}
			\la \tg(w_k,\delta_c,\delta_u) - \tg(z_k,\delta_c,\delta_u), w_k - z_{k+1} \ra \leq \frac{M_k}{2}\left(\|w_k-z_k\|^2 + \|w_k-z_{k+1}\|^2\right) + \frac{\e}{2}+\delta_u.
			\label{eq:UMPCheck}
			\end{equation}}
			\STATE Set $k=k+1$.

	\ENDFOR
		\ENSURE $\widehat{w}_k = \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}}\sum_{i=0}^{k-1}M_i^{-1}w_i$.

\end{algorithmic}
\end{algorithm}

\begin{Th}
	\label{Th:UMPGenRate}
	Assume that $g$ satisfies \cref{eq:g_or_def}, \cref{eq:g_or_deff}. Then, for any $k \geq 1$ and any $u \in Q$,
	\begin{equation}
	\label{eq:UMPGenRate}
	\frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} \langle g(w_i) , w_i - u \rangle \leq \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} (V[z_0](u)-V[z_{k}](u)) + \frac{\varepsilon}{2}+\delta_u+ 2 \delta_{pu}.
	\end{equation}
\end{Th}
\begin{proof}

As it follows from \cref{eq:g_or_def}, if $M_k \geq L(\frac{\epsilon}{4})$, \cref{eq:UMPCheck} holds. Thus, \cref{Alg:UMP} is correctly defined.

Let us fix some iteration $k\geq 0$. For simplicity, we denote $\tilde{g}(z_k) = \tilde{g}(z_k,\delta_{c,k},\delta_u) $ and $\tilde{g}(w_k) = \tilde{g}(w_k,\delta_{c,k},\delta_u)$.
By the definition of inexact prox-mapping \cref{eq:InPrMap}, \cref{eq:InPrMap1} and \cref{eq:UMPwStep}, \cref{eq:UMPzStep}, we have, for any $u\in Q$,
\begin{align}
 \langle & \tilde{g}(z_k) + M_k\nabla d(w_k) - M_k \nabla d(z_k), u - w_k \rangle \geq - \delta_{pu} - \frac{\varepsilon}{8}, \label{eq:Th:UMPGenRatePr1} \\
 \langle &\tilde{g}(w_k) + M_k\nabla d(z_{k+1}) - M_k \nabla d(z_k), u - z_{k+1} \rangle \geq - \delta_{pu} - \frac{\varepsilon}{8}. \label{eq:Th:UMPGenRatePr2}
\end{align}
Whence, for all $u\in Q$,
\begin{align*}
\langle \tilde{g}(w_k)&, w_k - u \rangle = \langle \tilde{g}(w_k) , z_{k+1} - u \rangle + \langle \tilde{g}(w_k) , w_k - z_{k+1}\rangle \\
& \hspace{-1em} \stackrel{\cref{eq:Th:UMPGenRatePr2}}{\leq} M_k \langle \nabla d(z_k) - \nabla d(z_{k+1}), z_{k+1} - u \rangle + \langle \tilde{g}(w_k) , w_k - z_{k+1}\rangle + \delta_{pu} + \frac{\varepsilon}{8} \\
& \hspace{-1em} = M_k(d(u) - d(z_k) - \langle \nabla d(z_k), u - z_k \rangle )
 - M_k(d(u) - d(z_{k+1}) - \\
& - \langle \nabla d(z_{k+1}), u - z_{k+1} \rangle) - M_k(d(z_k) - d(z_{k+1}) - \langle \nabla d(z_{k+1}), z_k - z_{k+1} \rangle ) + \\
& + \langle \tilde{g}(w_k) , w_k - z_{k+1}\rangle + \delta_{pu} + \frac{\varepsilon}{8} \\
& \hspace{-1em} = M_k V[z_k](u)-M_k V[z_{k+1}](u) - M_k V[z_k](z_{k+1}) + \langle \tilde{g}(w_k) , w_k - z_{k+1}\rangle +\\
& + \delta_{pu} + \frac{\varepsilon}{8}
\end{align*}
Further, for all $u\in Q$,
\begin{align*}
\langle \tilde{g}(w_k) , &w_k - z_{k+1}\rangle - M_k V[z_k](z_{k+1}) = \langle \tilde{g}(w_k) - \tilde{g}(z_k) , w_k - z_{k+1}\rangle - \\
&- M_k V[z_k](z_{k+1}) + \langle \tilde{g}(z_k) , w_k - z_{k+1}\rangle \\
& \hspace{-1em} \stackrel{\cref{eq:Th:UMPGenRatePr1}}{\leq} \langle \tilde{g}(w_k) - \tilde{g}(z_k) , w_k - z_{k+1}\rangle + M_k \langle \nabla d(z_k) - \nabla d(w_k), w_k - z_{k+1} \rangle - \\
& - M_k V[z_k](z_{k+1}) + \delta_{pu} + \frac{\varepsilon}{8} \\
& \hspace{-1em} = \langle \tilde{g}(w_k) - \tilde{g}(z_k) , w_k - z_{k+1}\rangle + M_k \langle \nabla d(z_k) - \nabla d(w_k), w_k - z_{k+1} \rangle - \\
& - M_k(d(z_{k+1})-d(z_k)-\langle \nabla d(z_k), z_{k+1} - z_k \rangle ) + \delta_{pu} + \frac{\varepsilon}{8} \\
& \hspace{-1em} = \langle \tilde{g}(w_k) - \tilde{g}(z_k) , w_k - z_{k+1}\rangle- M_k(d(w_k)-d(z_k)-\langle \nabla d(z_k), w_k - z_k \rangle ) - \\
& - M_k(d(z_{k+1}) - d(w_k)-\langle \nabla d(w_k), z_{k+1} - w_k \rangle ) + \delta_{pu} + \frac{\varepsilon}{8} \\
& \hspace{-1em} = \langle \tilde{g}(w_k) - \tilde{g}(z_k) , w_k - z_{k+1}\rangle - M_kV[z_k](w_k) - M_k V[w_k](z_{k+1}) + \delta_{pu} + \frac{\varepsilon}{8}\\
& \hspace{-1em} \leq \langle \tilde{g}(w_k) - \tilde{g}(z_k) , w_k - z_{k+1}\rangle - \frac{M_k}{2}(\|z_k-w_k\|^2+\|z_{k+1}-w_k\|^2) + \delta_{pu} + \frac{\varepsilon}{8}\\
& \hspace{-1em} \stackrel{\cref{eq:UMPCheck}}{\leq} \frac{3\varepsilon}{8}+\delta_u + \delta_{pu}.
\end{align*}

Thus, we obtain, for all $u\in Q$ and $i \geq 0$,
$$
M_i^{-1} \langle \tilde{g}(w_i) , w_i - u \rangle \leq V[z_i](u)-V[z_{i+1}](u) + \frac{M_i^{-1} \varepsilon}{2}+M_i^{-1} (\delta_u + 2 \delta_{pu}).
$$
Summing up these inequalities for $i$ from 0 to $k-1$, we have:
$$
\frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} \langle \tilde{g}(w_i) , w_i - u \rangle \leq \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} (V[z_0](u)-V[z_{k}](u)) + \frac{\varepsilon}{2}+\delta_u + 2 \delta_{pu}.
$$
Taking into account \cref{eq:g_or_deff}, we obtain the statement of the \cref{Th:UMPGenRate}.
\end{proof}

\begin{Cor}
	\label{Cor:VIsol}
	Assume that the operator $g$ satisfies \cref{eq:g_or_def}, \cref{eq:g_or_deff}. Also assume that the set $Q$ is bounded. Then, for all $k \geq 0$, we have
	\begin{equation}
	\label{eq:}
	\max_{u\in Q} \langle g(u) , \widehat{w}_k - u \rangle \leq \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \max_{u\in Q}V[z_0](u) + \frac{\varepsilon}{2} + \delta_u + 2 \delta_{pu},

	\end{equation}
	where
	$$
	 \widehat{w}_k = \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} w_i.
	$$
\end{Cor}

\begin{proof}
	By monotonicity of $g$, we have, for all $i \geq 0$ and $u \in Q$,
	$$
	 \langle g(u), w_i - u \rangle = \langle g(w_i), w_i - u \rangle + \langle g(u) - g(w_i), w_i - u \rangle \leq \langle g(w_i), w_i - u \rangle,
	$$
	Therefore, for any $u \in Q$,
	$$
	 \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} \langle g(w_i) , w_i - u \rangle \geq \langle g(u), \widehat{w}_k - u \rangle.
	$$
	Combining this with \cref{Th:UMPGenRate} and taking the maximum over all $u \in Q$, we obtain the statement of the \cref{Cor:VIsol}.

	Note that if $\max_{u \in Q} V[z_0](u) \leq D$, we can construct the following adaptive stopping criterion for our algorithm
	$$
	 \frac{D}{\sum_{i=0}^{k-1}M_i^{-1}} \leq \frac{\varepsilon}{2}.
	$$

	Next, we consider the case of H\"older-continuous operator $g$ and show that \cref{Alg:UMP} is universal. For simplicity we assume that the prox-mapping is calculated exactly, i.e. $\delta_{pc}=\delta_{pu}=0$ and $\delta_u=0$. In this case it is sufficient to set $\delta_{c,k} = \frac{\varepsilon}{2}$ on each iteration of \cref{Alg:UMP}.
\end{proof}

\begin{Cor}[Universal Method for VI]
	\label{Cor:UMPHoldUniv}
	Assume that the operator $g$ is H\"older-continuous with constant $L_{\nu}$ for some $\nu \in [0,1]$ and $M_{-1} \leq \left(\frac{1}{\varepsilon}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}}$. Also assume that the set $Q$ is bounded. Then, for all $k \geq 0$, we have
	\begin{equation}
	\label{eq:UMPRate}
	\max_{u\in Q} \langle g(u) , \widehat{w}_k - u \rangle \leq \frac{2 L_{\nu}^{\frac{2}{1+\nu}}}{ k \varepsilon^{\frac{1-\nu}{1+\nu}}} \max_{u\in Q}V[z_0](u) + \frac{\varepsilon}{2}.
\end{equation}
\end{Cor}

\begin{proof}
	As it follows from \cref{eq:g_or_def}, if $M_k \geq L(\frac{\varepsilon}{2})$, \cref{eq:UMPCheck} holds. Thus, for all $i = 0, ..., k-1$, we have $M_i \leq 2\cdot L(\frac{\varepsilon}{2})$ and
	$$
	\frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \leq \frac{2L(\frac{\varepsilon}{2})}{k} \leq \frac{2 L_{\nu}^{\frac{2}{1+\nu}}}{ k\varepsilon^{\frac{1-\nu}{1+\nu}}},
	$$
	\cref{eq:UMPRate} holds. Here $L(\cdot)$ is defined in \cref{Ex:Hold}.
\end{proof}

	Let us add some remarks. Since the \cref{Alg:UMP} does not use the values of parameters $\nu$ and $L_{\nu}$, we obtain the following iteration complexity bound to achieve $\max_{u\in Q} \langle g(u) , \widehat{w}_k - u \rangle \leq \varepsilon$
	$$
	4 \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}} \cdot \max_{u\in Q}V[z_0](u).
	$$
	Using the same reasoning as in \cite{nesterov2015universal}, we estimate the number of oracle calls for \cref{Alg:UMP}.
	The number of oracle calls on each iteration $k$ is equal to $2i_k$. At the same time, $M_k=2^{i_k-2}M_{k-1}$ and, hence, $i_k = 2+ \log_2\frac{M_k}{M_{k-1}}$.

	Thus, the total number of oracle calls is
	\begin{equation}\label{equiv_iter_2}
	\sum\limits_{j = 0}^{k-1} i_{j} = 4k + 2\sum\limits_{i = 0}^{k-1}\log_{2} \frac{M_{j}}{M_{j-1}} < 4k + 2 \log_{2} \left(2L\left(\frac{\varepsilon}{2}\right)\right) - 2 \log_{2} (M_{-1}),
	\end{equation}
	where we used that $M_{k} \leq 2 L(\frac{\varepsilon}{2})$.

	Thus, the number of oracle calls of the \cref{Alg:UMP} does not exceed:
	$$
	16 \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}} \cdot \max_{u\in Q}V[z_0](u) + 2 \inf_{\nu\in[0,1]} \log_2 2\left(\left(\frac{1}{\varepsilon}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}}\right) - 2\log_2(M_{-1}).
	$$

\section{Solving VI's with Strongly Monotone Operator}
In this section, we assume, that $g$ in \cref{eq:PrSt} is a strongly monotone operator, which means that, for some $\mu > 0$,
\begin{equation}
\label{eq:gStrMonDef}
\langle g(x) - g(y), x - y\rangle \geq \mu \|x-y\|^2 \quad \forall x, y \in Q.
\end{equation}
We slightly modify the assumptions on prox-function $d$. Namely, we assume that $0 = \arg \min_{x \in Q} d(x)$ and that $d$ is bounded on the unit ball in the chosen norm $\|\cdot\|$, that is
\begin{equation}
d(x) \leq \frac{\Omega}{2}, \quad \forall x\in Q : \|x \| \leq 1,
\label{eq:dUpBound}
\end{equation}
where $\Omega$ is some known constant. Note that for standard proximal setups, $\Omega = O(\ln \text{dim}E)$. Finally, we assume that we are given a starting point $x_0 \in Q$ and a number $R_0 >0$ such that $\| x_0 - x_* \|^2 \leq R_0^2$, where $x_*$ is the solution to \cref{eq:PrSt}.

\begin{algorithm}
\caption{Restarted Generalized Mirror Prox}
\label{Alg:RUMP}
\begin{algorithmic}[1]
 \REQUIRE accuracy $\e > 0$, $\mu >0$, $\Omega$ s.t. $d(x) \leq \frac{\Omega}{2} \ \forall x\in Q: \|x\| \leq 1$; $x_0, R_0 \ s.t. \|x_0-x_*\|^2 \leq R_0^2.$
 \STATE Set $p=0,d_0(x)=d\left(\frac{x-x_0}{R_0}\right)$.
 \REPEAT

			\STATE Set $x_{p+1}$ as the output of Algorithm 1 for monotone case with accuracy $\mu\e/2$, prox-function $d_{p}(\cdot)$ and stopping criterion $\sum_{i=0}^{k-1}M_i^{-1}\geq \frac{\Omega}{\mu}$.
			\STATE Set $R_{p+1}^2 = R_0^2 \cdot 2^{-(p+1)} + 2(1-2^{-(p+1)})(\frac{\e}{4}+\delta_u+ 2 \delta_{pu})$.
			\STATE Set $d_{p+1}(x) \leftarrow d\left(\frac{x-x_{p+1}}{R_{p+1}}\right)$.
			\STATE Set $p=p+1$.

			\UNTIL
			$p > \log_2\frac{2R_0^2}{\e}	$
		\ENSURE $x_p$.
\end{algorithmic}
\end{algorithm}

\begin{Th}
	\label{Th:RUMPCompl}
	Assume that $g$ is strongly monotone with parameter $\mu$. Also assume that the prox-function $d$ satisfies \cref{eq:dUpBound} and the starting point $x_0 \in Q$ and a number $R_0 >0$ are such that $\| x_0 - x_* \|^2 \leq R_0^2$, where $x_*$ is the solution to \cref{eq:PrSt}. Then, for $p\geq 0$
	\[
	\|x_p - x_*\|^2 \leq R_0^2\cdot 2^{-p} + \frac{\varepsilon}{2} + \frac{2\delta_u + 4 \delta_{pu}}{\mu},
	\]
	and the point $x_p$ returned by \cref{Alg:RUMP} satisfies $\|x_p-x_*\|^2\leq \varepsilon + \frac{2\delta_u + 4 \delta_{pu}}{\mu}$.
\end{Th}

\begin{proof}
	Let us denote $\Delta = \frac{\varepsilon}{4} + \frac{\delta_u + 2 \delta_{pu}}{\mu}$. We show by induction that, for $p \geq 0$,
	\[
	\|x_p - x_*\|^2 \leq R_0^2\cdot 2^{-p} + 2(1-2^{-p})\Delta,
	\]
	which leads to the statement of the \cref{Th:RUMPCompl}.
	For $p=0$ this inequality holds by the theorem assumption. Assuming that it holds for some $p\geq 0$, our goal is to prove it for $p+1$ considering the outer iteration $p+1$.
	Observe that the function $d_{p}$ defined in \cref{Alg:RUMP} is 1-strongly convex w.r.t. the norm $\|\cdot\|$.

	Using the definition of $d_{p}(\cdot)$ and \cref{eq:dUpBound}, we have, since $x_p = \arg \min_{x \in Q} d_p(x)$ and $\|x_p-x_*\|\leq R_p$
	\[
	V_{p}[x_{p}](x_*) = d_{p}(x_{*}) - d_{p}(x_{p}) - \langle \nabla d_{p}(x_{p}), x_{*} - x_{p} \rangle \leq d_{p}(x_{*}) = R_p^2d\left(\frac{x_{*}-x_p}{R_p}\right) \leq \frac{\Omega R_p^2}{2}.
	\]
	Thus, by \cref{Th:UMPGenRate}, taking $u = x_*$, we obtain
	\begin{multline*}
		\frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} \langle g(w_i) , w_i - x_{*} \rangle \leq \frac{V_{p}[x_{p}](x_{*})}{\sum_{i=0}^{k-1}M_i^{-1}} + \frac{\mu\varepsilon}{4} + \delta_u + 2 \delta_{pu} \leq \\
		\leq \frac{\Omega R_p^2}{2\sum_{i=0}^{k-1}M_i^{-1}} + \mu \Delta.
	\end{multline*}
	Since the operator $g$ is continuous and monotone, the solution to weak VI \cref{eq:PrSt} is also a strong solution and
	$
	\langle g(x_*), x_* - w_i \rangle \leq 0, \quad i=0,...,k-1.
	$
	This and the strong monotonicity of $g$ \cref{eq:gStrMonDef} give, for all, $i=0,...,k-1$,
	\[
	\langle g(w_i) , w_i - x_*\rangle \geq \langle g(w_i) - g(x_*) , w_i-x_*\rangle \geq \mu\|w_i-x_*\|^2.
	\]
	Thus, by convexity of the squared norm, we obtain
	\begin{align*}
	\mu \|x_{p+1}-x_*\|^2 &= \mu \left\|\frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} w_i-x_*\right\|^2 \hspace{-0.6em}
	\leq \frac{\mu}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} \|w_i-x_*\|^2 \\
	& \leq \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} \sum_{i=0}^{k-1} M_i^{-1} \langle g(w_i) , w_i - x_{*} \rangle \leq \frac{\Omega R_p^2}{2\sum_{i=0}^{k-1}M_i^{-1}} + \mu \Delta.
	\end{align*}
	Using the stopping criterion $\sum_{i=0}^{k-1} M_i^{-1} \geq \frac{\Omega}{\mu}$, we obtain
	\begin{align*}
	\|x_{p+1}-x_*\|^2 \leq \frac{R_p^2}{2} + \Delta = &\frac{1}{2} (R_0^2 \cdot 2^{-p} + 2(1-2^{-p})\Delta ) +\Delta \\ =
	& R_0^2 \cdot 2^{-(p+1)} + 2(1-2^{-(p+1)})\Delta,
	\end{align*}
	which finishes the induction proof.
\end{proof}

\begin{Cor}
	\label{Cor:RUMPHoldUniv}
	Assume that the operator $g$ is H\"older-continuous with constant $L_{\nu}$ for some $\nu \in [0,1]$ and strongly monotone with parameter $\mu$. Then \cref{Alg:RUMP} returns a point $x_p$ s.t. $\|x_p-x_*\|^2\leq \varepsilon + \frac{2\delta_u+4\delta_{pu}}{\mu}$ and the total number of iterations of the inner \cref{Alg:UMP} does not exceed
	\begin{equation}\label{eq_string_monot}
	\inf_{\nu \in [0,1]} \left\lceil \left(\frac{L_{\nu}}{\mu}\right)^{\frac{2}{1+\nu}}\frac{2^{\frac{2}{1+\nu}}\Omega }{\varepsilon^{\frac{1-\nu}{1+\nu}}} \cdot \log_2 \frac{2 R_0^2}{\varepsilon}\right\rceil.
	\end{equation}
\end{Cor}

\begin{proof}
	Let us denote $\hat{p} = \left\lceil \log_2 \frac{2 R_0^2}{\varepsilon}\right\rceil$. As it was shown in \cref{Cor:UMPHoldUniv}, on each inner iteration, $M_i \leq 2L(\frac{\mu\varepsilon}{4}) = 2\left(\frac{2}{\mu\varepsilon}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}}$. Thus, by the stopping criterion $\sum_{i=0}^{k-1} M_i^{-1} \geq \frac{\Omega}{\mu}$, the inner cycle stops at most when
	\[
	k_p = \left\lceil \left(\frac{L_{\nu}}{\mu}\right)^{\frac{2}{1+\nu}}\frac{2^{\frac{2}{1+\nu}}\Omega }{\varepsilon^{\frac{1-\nu}{1+\nu}}}\right\rceil
	\]
	and we have
	\begin{equation*}
	N = \sum_{p=1}^{\hat{p}} k_p \leq \left\lceil \left(\frac{L_{\nu}}{\mu}\right)^{\frac{2}{1+\nu}}\frac{2^{\frac{2}{1+\nu}}\Omega }{\varepsilon^{\frac{1-\nu}{1+\nu}}} \cdot \log_2 \frac{2 R_0^2}{\varepsilon}\right\rceil.
	\end{equation*}
	Since the \cref{Alg:UMP} does not need to know $\nu$ and $L_{\nu}$, we can take the infimum.
\end{proof}

We point that the complexity estimate for the case $\nu=0$, up to a logarithmic factor, is $O\left(\frac{L_0^2}{\mu^2\varepsilon}\right)$, whereas one would expect $O\left(\frac{L_0^2}{\mu\varepsilon}\right)$. The reason is that we measure the error in terms of the distance to the solution $\|x_p- x_*\|$, but not in terms of the residual in VI $\max_{u \in Q} \langle g(u), x_p - u \rangle$, as in \cref{Cor:UMPHoldUniv}.

\section{Applications to Saddle Point Problems}
\label{S:saddle_point}
In this section, we consider saddle point problems and show, how Generalized Mirror Prox can be applied to such problems. The problem, we consider is
\begin{equation}\label{eq:SadPointPrSt}
f^*=\min\limits_{u\in Q_1}\max\limits_{v\in Q_2}f(u,v),
\end{equation}
where $Q_1 \subset E_1$ and $Q_2 \subset E_2$ are convex and closed subsets of normed spaces $E_1$ and $E_2$ with norms $\|\cdot\|_1$ and $\|\cdot\|_2$ respectively.
Based on the norms in $E_{1}$ and $E_{2}$, we define the norm on their product $E_1\times E_2$ as $\|x\|=\max\{\|u\|_1,\|v\|_2\}$, $x=(u,v)\in E_1\times E_2$ with the corresponding dual norm $\|s\|_*=\|z\|_{1,*}+\|w\|_{2,*}$, $s=(z,w)\in E^*$,

where $\|\cdot\|_{1,*}$ and $\|\cdot\|_{2,*}$ are the norms on the conjugate spaces $E^*_1$ and $E^*_2$, dual to $\|\cdot\|_1$ and $\|\cdot\|_2$ respectively.

The function $f$ in \cref{eq:SadPointPrSt} is assumed to be convex in $u$ and concave in $v$. As it is usually done, we consider the operator
\begin{equation}\label{eq:gSadPointDef}
g(x)=
\begin{pmatrix}
\nabla_u f(u,v)\\
-\nabla_v f(u,v)
\end{pmatrix}, \; x=(u,v) \in Q:=Q_1 \times Q_2.
\end{equation}

By the convexity of $f$ in $u$ and the concavity in $v$, the operator $g$ is monotone
\begin{equation}
\langle g(x)-g(y),x-y\rangle \geq 0 \quad \forall x,y\in Q\subset E,
\end{equation}
where $x=(u_1,v_1), y=(u_2,v_2)$.

The following lemma gives sufficient conditions for $g$ to be H\"older-continuous, i.e. $g$ satisfies \cref{eq:GHoeldDef}.
\begin{Lm}\label{Lm:HoeldfToHoeldG}
	Assume that $f$ in \cref{eq:SadPointPrSt} is such that there exist such number $\nu \in [0,1]$ and constants $L_{11,\nu},L_{12,\nu},L_{21,\nu},L_{22,\nu} < +\infty$ that
	\begin{equation}\label{eq:Sadle_Hold1}
	\|\nabla_u f(u+\Delta u,v+\Delta v)-\nabla_u f(u,v)\|_{1,*}\leq L_{11,\nu}\| \Delta u\|_{1}^{\nu}+L_{12,\nu}\| \Delta v\|_{2}^{\nu},
	\end{equation}
	\begin{equation}\label{eq:Sadle_Hold2}
	\|\nabla_v f(u+\Delta u,v+\Delta v)-\nabla_v f(u,v)\|_{2,*}\leq L_{21,\nu}\| \Delta u\|_{1}^{\nu}+L_{22,\nu}\| \Delta v\|_{2}^{\nu}
	\end{equation}
	for all $u, u+\Delta u\in Q_1, v, v+\Delta v \in Q_2$. Then $g$ defined in \cref{eq:gSadPointDef} is H\"older-continuous, i.e. satisfies \cref{eq:GHoeldDef} with the same $\nu$ and $L_{\nu} = L_{11,\nu}+L_{12,\nu}+L_{21,\nu}+L_{22,\nu}$.
\end{Lm}

\begin{proof}
	Indeed, for each $x=(u_1,v_1), y=(u_2,v_2) \in Q$ we have:
	\begin{align*}
	 \| g(x)-&g(y)\|_* = \| \nabla_u f(u_1,v_1)-\nabla_u f(u_2,v_2)\|_{1,*}+ \| \nabla_v f(u_1,v_1)-\nabla_v f(u_2,v_2)\|_{2,*}\\
	 & \hspace{-1em}\leq L_{11,\nu}\|u_1-u_2\|_1^{\nu}+L_{12,\nu}\|v_1-v_2\|_2^{\nu}+L_{21,\nu}\|u_1-u_2\|_1^{\nu}+L_{22,\nu}\|v_1-v_2\|_2^{\nu} \\
	 &\hspace{-1em} =(L_{11,\nu}+L_{21,\nu})\|u_1-u_2\|_1^{\nu}+(L_{12,\nu}+L_{22,\nu})\|v_1-v_2\|_2^{\nu}\\
	 &\hspace{-1em}\leq (L_{11,\nu}+L_{12,\nu}+L_{21,\nu}+L_{22,\nu})\max\{\|u_1-u_2\|_1^{\nu},\|v_1-v_2\|_2^{\nu}\}\\
	 &\hspace{-1em}=(L_{11,\nu}+L_{12,\nu}+L_{21,\nu}+L_{22,\nu})\|x-y\|^{\nu}.
	\end{align*}

\end{proof}
\begin{Rem}
	As an alternative the following primal and dual norms for $E = E_1\times E_2$ can be considered $\|x\|=\sqrt{\|u\|_1^2+\|v\|_2^2}$, $x=(u,v)\in E_1\times E_2$, and $\|s\|_*= \sqrt{\|z\|_{1,*}^2+\|w\|_{2,*}^2}$, $s=(z,w)\in E^*$,

	where $\|\cdot\|_{1,*}$ and $\|\cdot\|_{2,*}$ are the norms on the conjugate spaces $E^*_1$ and $E^*_2$, dual to $\|\cdot\|_1$ and $\|\cdot\|_2$ respectively.

	We have for each $x=(u_1,v_1), y=(u_2,v_2) \in Q$:
	\begin{align*}
	 \| &g(x)-g(y)\|^2_* = \| \nabla_u f(u_1,v_1)-\nabla_u f(u_2,v_2)\|_{1,*}^2+ \| \nabla_v f(u_1,v_1)-\nabla_v f(u_2,v_2)\|_{2,*}^2 \\
	 &\leq 2(L_{11,\nu}^2\|u_1-u_2\|_1^{2\nu}+L_{12,\nu}^2\|v_1-v_2\|_2^{2\nu} + L_{21,\nu}^2\|u_1-u_2\|_1^{2\nu} + L_{22,\nu}^2\|v_1-v_2\|_2^{2\nu})\\
	 &=2(L_{11,\nu}^2+L_{21,\nu}^2)\|u_1-u_2\|_1^{2\nu} + (L_{12,\nu}^2+L_{22,\nu}^2)\|v_1-v_2\|_2^{2\nu}\\
	 &\leq (L_{11,\nu}^2 + L_{12,\nu}^2 + L_{21,\nu}^2 + L_{22,\nu}^2)\max\{\|u_1-u_2\|_1^{2\nu},\|v_1-v_2\|_2^{ 2\nu}\}) \\
	 &\leq 2(L_{11,\nu}^2+L_{12,\nu}^2+L_{21,\nu}^2+L_{22,\nu}^2)\|x-y\|^{2\nu}
	\end{align*}

	and
	$$
	\| g(x)-g(y)\|_* \leq \sqrt{2(L_{11,\nu}^2+L_{12,\nu}^2+L_{21,\nu}^2+L_{22,\nu}^2)} \|x-y\|^{\nu}.
	$$

\end{Rem}

\begin{Rem}
	Generally speaking, if the set $Q$ is bounded, one can consider different level of smoothness in \cref{eq:Sadle_Hold1} and \cref{eq:Sadle_Hold2}.

	Assume that for some numbers $\nu_{11}, \nu_{12}, \nu_{21}, \nu_{22} \in [0; 1]$:
	\begin{align}
	 &\|\nabla_u f(u+\Delta u,v+\Delta v)-\nabla_u f(u,v)\|_{1,*}\leq \widehat{L}_{11}\| \Delta u\|_{1}^{\nu_{11}} + \widehat{ L}_{12}\| \Delta v\|_{2}^{\nu_{12}}, \label{eq:Sadle_Hold11} \\
	 &\|\nabla_v f(u+\Delta u,v+\Delta v)-\nabla_v f(u,v)\|_{2,*}\leq \widehat{L}_{21}\| \Delta u\|_{1}^{\nu_{21}} + \widehat{L}_{22}\| \Delta v\|_{2}^{\nu_{22}} \label{eq:Sadle_Hold12}
	\end{align}

	for all $u, u+\Delta u\in Q_1, v, v+\Delta v \in Q_2$.
	Then the statement of \cref{Lm:HoeldfToHoeldG} holds for
	$\nu = \min\{\nu_{11}, \, \nu_{12},\, \nu_{21} \, \nu_{22}\} \in [0;1].$
	Indeed, from \cref{eq:Sadle_Hold11}, \cref{eq:Sadle_Hold12}, we have
	\begin{equation*}
	\|\nabla_u f(u+\Delta u,v+\Delta v)-\nabla_u f(u,v)\|_{1,*}\leq \widehat{L}_{11} \cdot D_Q^{\nu_{11} - \nu} \cdot \| \Delta u\|_{1}^{\nu} + \widehat{L}_{12}\cdot D_Q^{\nu_{12} - \nu} \cdot\| \Delta v\|_{2}^{\nu},
	\end{equation*}
	\begin{equation*}
	\|\nabla_v f(u+\Delta u,v+\Delta v)-\nabla_v f(u,v)\|_{2,*}\leq \widehat{L}_{21}\cdot D_Q^{\nu_{21} - \nu} \cdot\| \Delta u\|_{1}^{\nu} + \widehat{L}_{22} \cdot D_Q^{\nu_{22} - \nu} \cdot\| \Delta v\|_{2}^{\nu}
	\end{equation*}
	for all $u, u+\Delta u\in Q_1, v, v+\Delta v \in Q_2$, $D_Q = \sup\{\|x-y\|\,|\, x, y \in Q\}$.
\end{Rem}

Next theorem shows, how \cref{Alg:UMP} can be applied to solve the saddle point problem \cref{eq:SadPointPrSt}.
\begin{Th}
	\label{Th:UMPforSadPoint}
	Let the assumptions of \cref{Lm:HoeldfToHoeldG} hold and set $Q$ be bounded and $L_{\nu}$ be given in \cref{Lm:HoeldfToHoeldG}. Assume also that \cref{Alg:UMP} with accuracy $\varepsilon$ is applied to the operator $g$ defined in \cref{eq:gSadPointDef} and $w_i = (u^{i},v^{i})$ is the sequence generated by this algorithm. Then
	\[
	\max_{v\in Q_2} f(\widehat{u}_k,v) - \min_{u \in Q_1} f(u,\widehat{v}_k) \leq \frac{ 2L_{\nu}^{\frac{2}{1+\nu}}}{ k \varepsilon^{\frac{1-\nu}{1+\nu}}} \max_{x\in Q}V[w_0](x) + \frac{\varepsilon}{2},
	\]

	\[
	\text{{\rm where}} \quad (\widehat{u}_k, \widehat{v}_k) = \frac{1}{S_k}\sum_{i=0}^{k-1} M_i^{-1} (u^{i},v^{i}), \quad S_k=\sum\limits_{i = 0}^{k-1} M_i^{-1}.
	\]
	Moreover, in the number of iterations
	\[
	O\left( \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}} \cdot \max_{x\in Q}V[w_0](x) \right)
	\]
	the algorithm finds a pair $(\widehat{u},\widehat{v})$ satisfying
	$\max_{v\in Q_2} f(\widehat{u},v) - \min_{u \in Q_1} f(u,\widehat{v}) \leq \varepsilon$.

\end{Th}
\begin{proof}
	By convexity of $f$ in $u$ and concavity of $f$ w.r.t $v$, we have, for all $u \in Q_1$,
	\begin{align*}
	\frac{1}{S_k} \sum_{i=0}^{k-1} \left\langle \nabla_u f(u^{i},v^{i}),u^{i}-u\right \rangle_1 & \geq \frac{1}{S_k} \sum_{i=0}^{k-1} M_i^{-1} (f(u^{i},v^{i})-f(u,v^{i})) \\
	& \geq \frac{1}{S_k} \sum_{i=0}^{k-1} M_i^{-1} f(u^{i},v^{i})-f(u,\widehat{v}_k).
 \end{align*}
	In the same way, we obtain, for all $v \in Q_2$,
	\[
	\frac{1}{S_k} \sum_{i=0}^{k-1} M_i^{-1} \left\langle -\nabla_v f(u^{i},v^{i}),v^{i}-v\right \rangle_2 \geq -\frac{1}{S_k} \sum_{i=0}^{k-1} M_i^{-1} f(u^{i},v^{i})+f(\widehat{u}_k,v).
	\]
	Summing these inequalities, by \cref{eq:gSadPointDef} and \cref{Th:UMPGenRate}, we obtain that, for all $u \in Q_1$, $v \in Q_2$ and $x = (u,v)$,
	\[
	f(\widehat{u}_k,v) - f(u,\widehat{v}_k) \leq \frac{1}{S_k} \sum_{i=0}^{k-1} M_i^{-1} \langle g(w_i), w_i - x \rangle \leq \frac{1}{\sum_{i=0}^{k-1}M_i^{-1}} V[w_0](x) + \frac{\varepsilon}{2}.
	\]
	Since $M_i \leq 2 L\left(\frac{\varepsilon}{2}\right)$, where $L(\cdot)$ is given in \cref{Ex:Hold}, and the set $Q$ is bounded, we obtain
	\[
	\max_{v\in Q_2} f(\widehat{u}_k,v) - \min_{u \in Q_1} f(u,\widehat{v}_k) \leq \frac{2 L_{\nu}^{\frac{2}{1+\nu}}}{ k \varepsilon^{\frac{1-\nu}{1+\nu}}} \max_{x\in Q}V[w_0](x) + \frac{\varepsilon}{2}.
	\]
	The iteration complexity follows from the requirement for $k$ to make the first term in r.h.s. smaller than $\varepsilon$.

\end{proof}

\begin{Rem}
	Since for a saddle point $(u_*,v_*) \in Q,$
	$
	\max\limits_{v \in Q_2}f(u_*,v)=\min\limits_{u \in Q_1}f(u,v_*)
	$, the inequality
 $\max_{v\in Q_2} f(\widehat{u},v) - \min_{u \in Q_1} f(u,\widehat{v}) \leq \varepsilon$, means that $(\widehat{u},\widehat{v})$ is a good approximation for $(u_*,v_*)$.
\end{Rem}

\begin{Rem}
	For $\mu$-strongly convex-concave saddle point problems \cref{Alg:RUMP} returns a point $x_p$ s.t. $\|x_p-x_*\|^2\leq \varepsilon + \frac{2\delta_u+4\delta{pu}}{\mu}$ (for exact solution $x_*$) with the complexity estimate given in \cref{eq_string_monot}.

\end{Rem}

An important particular case of saddle point problem is the saddle point problem in the method of Lagrange multipliers.
Let us consider the following convex optimization problem:
\begin{equation}
\label{eq:ex4_problem}
f(x)\rightarrow\min \ \
\text{s.t.} \;\; x \in Q, \quad \phi_j(x)\leq 0, \quad j=1,...,m,
\end{equation}
where $Q$ is a compact set, $f$ and $\phi_j$ are convex and have H\"older-continuous subgradients
$$\|\nabla f(x) - \nabla f(y)\|_* \leq L_{\nu_0} \|x - y\|^{\nu_0}, $$
$$ \|\nabla \phi_j(x) - \nabla \phi_j(y)\|_* \leq L_{\nu_j} \|x - y\|^{\nu_j} \quad \forall x, y \in Q, j=1,...,m $$
for some $\nu_0, ..., \nu_m \geq 0$ and $L_{\nu_0}, ..., L_{\nu_m} >0$.
The corresponding Lagrange function for this problem is $L(x,\lambda)= f(x) + \sum\limits_{j=1}^{m}\lambda_j\phi_j(x)$, where $\lambda_j \geq 0$, $j=1,...,m$ are Lagrange multipliers.
If a point $(x_*,\lambda_*)$ is a saddle point of the convex-concave Lagrange function $L(x,\lambda)$, then $x_*$ is a solution to \cref{eq:ex4_problem}.
Assume also that the Slater's constraint qualification condition holds, i.e. there exists a point $\bar{x}$ s.t. $\phi_j(\bar{x}) < 0$, $j=1,...,m$. Then it can be shown that the optimal Lagrange multiplier $\lambda_*$ is bounded. Thus, instead of minimization problem \cref{eq:ex4_problem}, one can consider the saddle point problem $\min_{x \in Q} \max_{\lambda \in \Lambda} L(x, \lambda)$, which is a convex-concave problem on a bounded set. Using \cref{Lm:HoeldfToHoeldG} and the H\"older continuity assumption for subgradients of $f$ and $\phi_j$, we see that \cref{Alg:UMP} and \cref{Th:UMPforSadPoint} can be applied. We underline that by its nature, the smoothness level of the primal problem and the dual problem is different. Thus, it is important for the algorithm to adapt to the actual level of smoothness.

Next we introduce the concept inexact oracle for saddle point problems \eqref{eq:SadPointPrSt}.

\begin{Def}
 \label{Def:IOSedlo}
	Assume that there exists some $\delta_u > 0$ (uncontrolled error) and for any points $x,y \in Q$ for any number $\delta_c > 0$ (controlled error) there exist a constant $L(\delta_c) \in (0, +\infty)$ and one can calculate $\tilde{g}(x,\delta_c,\delta_u), \tilde{g}(y,\delta_c,\delta_u) \in E^*$ satisfying
	\begin{equation}
	\label{eq:g_or_def_sedlo}
	\langle \tilde{g}(y,\delta_c,\delta_u) - \tilde{g}(x,\delta_c,\delta_u), y - z \rangle \leq \frac{L(\delta_c)}{2}\left(\|y-x\|^2 + \|y-z\|^2\right) + \delta_c+\delta_u,
	\end{equation}
	and, for each $x = (u_x, v_x), y = (u_y, v_y) \in Q$,
	\begin{equation}
	\label{eq:g_or_deff_sedlo}
	f(u_y, v_x) - f(u_x, v_y) \leq
	\langle \tilde{g}(y,\delta_c,\delta_u), y - x \rangle + \delta_u.
	\end{equation}
\end{Def}
\begin{Rem}
Recall (see \cref{Def:IO}), that $\delta_c$ represents the error of the oracle, which we can control and make as small as we would like to. On the opposite, $\delta_u$ represents the error, which we can not control.
\end{Rem}

\begin{Ex}

[\textbf{\it Saddle point problems and ($\delta,L$)-oracle in optimization}]
\label{Ex:delta_L_sad_point}

Assume that we can calculate
	$$g_{\delta}(x)=\begin{pmatrix}
	g_{\delta, u}(u,v)\\
	- g_{\delta, v}(u,v)
	\end{pmatrix}, x=(u,v)\in Q,$$
	where $(f_{\delta, u}, g_{\delta, u})$ is a $(\delta,L)$-oracle $f$ w.r.t. $u$, and $-(f_{\delta, v}, \widetilde{g}_{\delta, v})$ is a $(\delta,L)$-oracle for ($-f$) w.r.t. $v$, see \cref{EEE2}.
	Define $\|x\| = \|(u, v)\| := \sqrt{\|u\|^2+\|v\|^2}$.

	As in \cref{ExampVI2.5}, for each
	$x = (u_x, v_x), y = (u_y, v_y)$, $z = (u_z, v_z) \in Q$:
	\begin{align}
	 &\langle g_{\delta, u}(u_y, v_y)- g_{\delta, u}(u_x, v_x), u_y-u_z \rangle \leq \frac{L}{2}(\|u_y-u_z\|^2+\|u_y-u_x\|^2)+3\delta, \label{eq:ex4_9su} \\
	 &\langle -g_{\delta, v}(u_y, v_y)+g_{\delta, v}(u_x, v_x), v_y-v_z \rangle \leq \frac{L}{2}(\|v_y-v_z\|^2+\|v_y-v_x\|^2)+3\delta, \label{eq:ex4_9sv}
	\end{align}

	and we have

	\begin{equation}
	\label{eq:ex4_9s1}
	\langle g_{\delta}(y) - g_{\delta}(x),y-z \rangle \leq \frac{L}{2}(\|y-z\|^2+\|y-x\|^2)+6\delta.
	\end{equation}

Further, from inequalities
\begin{align}
 &f(u_{y},v_{y})-f(u_{x},v_{y})\leq \langle g_{\delta,u}(y),u_{y}-u_{x}\rangle+\delta, \notag \\
 & f(u_{y},v_{x})-f(u_{y},v_{y})\leq \langle -g_{\delta,v}(y),v_{y}-v_{x}\rangle+\delta \notag
\end{align}

we have
\begin{equation}\label{SaddleModelIneq}
f(u_{y},v_{x})-f(u_{x},v_{y})\leq\langle g_{\delta}(y),y-x\rangle+2\delta.
\end{equation}
So, $g_{\delta}(y) = \tilde{g}(y,\delta_c,\delta_u)$ satisfies \cref{Def:IOSedlo} for $\delta_{u} = 6 \delta$, $\delta_c = 0$ and $L(\delta_c) = L$.

\end{Ex}
Similarly to \cref{Th:UMPforSadPoint} it is sufficient to make
 \[
	O\left( \inf_{\nu\in[0,1]}\left(\frac{L(\delta_c)}{\varepsilon} \right) \cdot \max_{x\in Q}V[w_0](x) \right)
	\]
	iterations of \cref{Alg:UMP}, to find a pair $(\widehat{u},\widehat{v})$ satisfying
	$$\max_{v\in Q_2} f(\widehat{u},v) - \min_{u \in Q_1} f(u,\widehat{v}) \leq \varepsilon + O(\delta_u +\delta_c).
	$$

\section{Conclusion}
We propose a generalization of Mirror Prox algorithm for VI's with monotone operator given with some inexactness. In the particular case of H\"older-continuous operator, our algorithm is universal with respect to H\"older parameters. Note that some adaptive method proposed in \cite{Malitsky2018}, but only for for Lipschitz-continuous operators and Euclidean prox-structure. We also present how restart technique can be applied to accelerate our method under additional assumption of strong monotonicity of the operator. It would be interesting to understand, whether the dual extrapolation technique \cite{nesterov2007dual} can be extended for the case of inexact oracle and to obtain a universal method. To show the advantages of the proposed \cref{Alg:UMP}, a series of numerical experiments were performed for different examples and reported in \cref{S:numerics}.

\bibliographystyle{siamplain}
\bibliography{references}

\appendix
\section{Proof of \cref{Lm:HoldToLip}}\label{appA}
\begin{proof}
	Let us fix some $\nu \in [0,1]$. Then, for any $x \in [0,1 ]$, $x^{2\nu}\leq 1$. On the other hand, for any $x \geq 1$, $\ x^{2\nu}\leq x^{2}$. Thus, for any $x \ge 0$, $x^{2\nu}\leq x^2+ 1$.

	Hence, for any $\alpha , \beta \geq 0$,
	$$
	\alpha^{\nu}\beta\leq \frac{\alpha^{2\nu}}{2}+\frac{\beta^{2}}{2}\leq \frac{\alpha^{2}}{2}+\frac{\beta^{2}}{2}+\frac{1}{2}.
	$$
	Substituting $\alpha=\frac{ba^{\frac{1}{1+\nu}}}{\delta^{\frac{1}{1+\nu}}}$ and $\beta=\frac{ca^{\frac{1}{1+\nu}}}{\delta^{\frac{1}{1+\nu}}}$, we obtain
	$$
	\frac{b^{\nu}a^{\frac{\nu}{1+\nu}}}{\delta^{\frac{\nu}{1+\nu}}}\frac{ca^{\frac{1}{1+\nu}}}{\delta^{\frac{1}{1+\nu}}}\leq \frac{b^{2}a^{\frac{2}{1+\nu}}}{2\delta^{\frac{2}{1+\nu}}}+\frac{c^{2}a^{\frac{2}{1+\nu}}}{2\delta^{\frac{2}{1+\nu}}}+\frac{1}{2}
	$$
	and
	$$
	ab^{\nu}c \leq \left(\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu}} \frac{a^{\frac{2}{1+\nu}}}{2} \left(b^2+c^2\right) + \frac{\delta}{2}.
	$$
\end{proof}

\section{Numerical Experiments}
\label{S:numerics}
To show the practical performance of the proposed \cref{Alg:UMP}, a series of numerical experiments were performed for different examples. In \cref{sec:strongly_VI}, we consider VI with Lipschitz-continuous strongly monotone operator, which is not potential. We see linear convergence of the basic \cref{Alg:UMP} without using restarts. In \cref{sec:SPP}, we consider non-smooth saddle point problem. Finally, in \cref{sec:Fermat_Torr_stei} we consider Lagrange saddle point problem induced by Fermat-Torricelli-Steiner problem.

All experiments were implemented in Python 3.4, on a computer fitted with Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz, 1992 Mhz, 4 Core(s), 8 Logical Processor(s). RAM of the computer is 8 GB.

\subsection{VI with Strongly Monotone Operator} \label{sec:strongly_VI}
Consider the variational inequality with the operator $\displaystyle g:\mathbb{R}^{n}\rightarrow \mathbb{R}^{n}$ with the components given by
\begin{equation}\label{Problem}
[g(x)]_i= \exp\left(x_{i}+\frac{x_{i+1}}{\exp(3)}\right), \; i=1,...,n
\end{equation}
with the convention $x_{n+1}=x_1$

on the set $Q = \{x \in \mathbb{R}^n: \|x\|_2 \leq 1 \}$, where $\| \cdot\|_2$ is the standard Euclidean norm.

The operator $g$ is not potential, i.e. is not a gradient of any function, since
\begin{equation}\label{eqv_potent_op}
\frac{\partial}{\partial x_{2}}\left(\exp\left(x_{1}+\frac{x_{2}}{\exp(3)}\right)\right)=\frac{1}{\exp(3)} \exp\left(x_{1}+\frac{x_{2}}{\exp(3)}\right),
\end{equation}
$$\frac{\partial}{\partial x_{1}}\left(\exp\left(x_{2}+\frac{x_{3}}{\exp(3)}\right)\right)=0.$$

We show that the operator $g$ satisfies the Lipschitz condition and is monotone on $Q$. By the mean value theorem, for arbitrary $i,j=1,...,n$, we have:
\begin{align}
 \exp\bigg(x_{i} &+\frac{x_{j}}{\exp(3)}\bigg) - \exp\left(y_{i}+\frac{y_{j}}{\exp(3)}\right) \hspace{-0.2em}= \hspace{-0.2em} \exp\left(x_{i}+\frac{x_{j}}{\exp(3)}\right) - \exp\left(y_{i}+\frac{x_{j}}{\exp(3)} \right) \notag \\
 & +\exp\left(y_{i}+\frac{x_{j}}{\exp(3)}\right) - \exp\left(y_{i}+\frac{y_{j}}{\exp(3)} \right) \notag \\
 &= \exp\left(\alpha_{i}+\frac{x_{j}}{\exp(3)} \right)(x_{i}-y_{i})+ \frac{1}{\exp(3)} \exp\left(y_{i}+\frac{\gamma_{j}}{\exp(3)}\right)(x_{j}-y_{j}) \label{eq examp2}
\end{align}

for some $\alpha_{i} \in [x_i, y_i]$ and $\gamma_{j} \in [x_j, y_j]$, whence $ |\alpha_{i}|\leq 1$ and $|\gamma_{j}|\leq 1$.

Hence,
\begin{equation}\label{ineqalphax}
\max\left\{\left|\alpha_{i}+\frac{x_{j}}{\exp(3)}\right|,\left|y_{i}+\frac{\gamma_{j}}{\exp(3)}\right| \right\} \leq 1 + \frac{1}{\exp(3)} < \sqrt{2},
\end{equation}

and, from \cref{eq examp2},
$$\left|\exp \left(x_{i}+\frac{x_{j}}{\exp(3)} \right) - \exp \left(y_{i}+\frac{y_{j}}{\exp(3)}\right)\right|<\exp(\sqrt{2})|x_{i}-y_{i}|+ $$
$$
+ \exp (\sqrt{2}-3)|x_{j}-y_{j}| < \exp (\sqrt{2})\left(|x_{i}-y_{i}|+|x_{j}-y_{j}|\right).
$$
Further, by the inequality $(a+b)^2 \leq 2(a^2 + b^2)$, we have, for all $x,y\in Q$,
$$
\|g(x)-g(y)\|^{2} < 4\exp(2\sqrt{2})\|x-y\|^{2} \; \text{and} \; \|g(x)-g(y)\|< 2\exp(\sqrt{2})\|x-y\|.
$$

Therefore, the operator $g$ satisfies the Lipschitz property with constant $\displaystyle L = 2\cdot \exp(\sqrt{2})$.

Further, \cref{eq examp2} means that for arbitrary $x,y\in Q$
\begin{multline*}
\langle g(x)-g(y),x-y\rangle=\sum_{k=1}^{n}c_{k}(x_{k}-y_{k})^{2}+\sum_{k=1}^{n-1}d_{k}(x_{k}-y_{k})(x_{k+1}-y_{k+1})+\\
+d_{n}(x_{n}-y_{n})(x_{1}-y_{1}),
\end{multline*}

where by \eqref{eqv_potent_op} and \eqref{ineqalphax}
$$\displaystyle c_{k}> \exp(-\sqrt{2}),\; d_{k}<\exp(\sqrt{2}-3)< \exp(-\sqrt{2}) \quad \forall k=1,...,n.$$
Since $\displaystyle 2 ab \leq a^{2}+b^{2}$, for each $k$,

$d_{k}(x_{k}-y_{k})(x_{k+1}-y_{k+1}) \geq - \frac{1}{2}((x_{k}-y_{k})^2+(x_{k+1}-y_{k+1})^2)$, and we obtain
$$\langle g(x)-g(y),x-y\rangle> \exp (-\sqrt{2})\sum_{k=1}^{n}(x_{k}-y_{k})^{2}- \exp(-\sqrt{2})\sum_{k=1}^{n}(x_{k}-y_{k})^{2}=0.$$
Therefore, the operator $g$ is strongly monotone.

\begin{Rem}
	Suppose at each iteration of the \cref{Alg:UMP} the constant $M_k$ is devided not by $2$, but by an arbitrary constant $a>1$.
	The number of oracle calls on each iteration $k$ is equal to $2i_k$. At the same time, $M_k=a^{i_k-2}M_{k-1}$, so $i_k = 2+ \log_a\frac{M_k}{M_{k-1}}$.

	Thus, since $M_{k} \leq a L(\frac{\varepsilon}{2})$, the total number of oracle calls is
	\begin{equation}
	\sum\limits_{j = 0}^{k-1} i_{j} = 4k + 2\sum\limits_{i = 0}^{k-1}\log_{a} \frac{M_{j}}{M_{j-1}} < 4k + 2 \log_{a} \left(aL\left(\frac{\varepsilon}{2}\right)\right) - 2 \log_{a} (M_{-1})
	\end{equation}
	and the number of oracle calls of the \cref{Alg:UMP} does not exceed
	$$
	4 \inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon} \right)^{\frac{2}{1+\nu}} \cdot \max_{u\in Q}V[z_0](u) + 2 \inf_{\nu\in[0,1]} \log_a a\left(\left(\frac{1}{\varepsilon}\right)^{\frac{1-\nu}{1+\nu}} L_{\nu}^{\frac{2}{1+\nu}}\right) - 2\log_a(M_{-1}).
	$$
\end{Rem}

We run \cref{Alg:UMP} with different values of the accuracy

$\varepsilon \in \{10^{-i}, 5\times 10^{-i-1}, i=1,...,4\},$

and different values of the dimension
$n \in \{ 10^{i}, i=3,...,6\}$

 with the starting point $x_0=\left( \frac{1}{n}, \frac{1}{n}, \ldots, \frac{1}{n} \right) \in \mathbb{R}^n $. The proximal structure is given by Euclidean norm and squared Euclidean norm as a prox-function. Prox-mapping is considered to be exact.

The results of the work of \cref{Alg:UMP} are presented in \cref{appB_iter_log_standard} (number of iterations as a function of accuracy $\varepsilon$) and \cref{appB_time_log_standard} (required time as a function of accuracy $\varepsilon$).
As it is expected from the theoretical results, the number of iterations does not depend on the dimension and all four plots for different dimensions coincide in \cref{appB_iter_log_standard}. Notably, the plot is close to a straight line, i.e. in the experiments the iteration number $k$ to reach accuracy $\varepsilon$ is proportional to $\ln(1/\varepsilon)$, meaning that the converegence is actually linear. We emphasize that the restart technique in \cref{Alg:RUMP} was not used, which means that the basic \cref{Alg:UMP} adjusts itself to strong monotonicity and accelerates to linear convergence rate. The dependence of time on the dimension is approximately linear since the number of arithmetic operations on each iteration is proportional to $n$.

\cref{appB_iter_log_mod}---\cref{appB_time_log_mod} show the same results for the modification of \cref{Alg:UMP}, in which at each iteration the constant $M_k$ is divided not by $2$, but by $16$.

\begin{figure}[tbhp]
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB1_iter_log.jpg}
	\caption{Results of \cref{Alg:UMP} for the operator \cref{Problem} for different values of the dimension $n$.}
	\label{appB_iter_log_standard}
	\endminipage\hfill
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB1_time_log.jpg}
	\caption{Results of \cref{Alg:UMP} for the operator \cref{Problem} for different values of the dimension $n$.}
 \label{appB_time_log_standard}
	\endminipage\hfill
\end{figure}

\begin{figure}[tbhp]
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB1_iter_log_mod.jpg}
	\caption{Results of the modified \cref{Alg:UMP} for the operator \cref{Problem} with different values of the dimension $n$.}
	\label{appB_iter_log_mod}
	\endminipage\hfill
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB1_time_log_mod.jpg}
	\caption{ Results of the modified \cref{Alg:UMP} for the operator \cref{Problem} with different values of the dimension $n$.}
	\label{appB_time_log_mod}
	\endminipage\hfill
\end{figure}

\subsection{Non-Smooth Saddle Point Problem}\label{sec:SPP}

Let $x=(u,v) \in \mathbb{R}^{p} \times \mathbb{R}^{q}:=\mathbb{R}^{n}; \, n=p+q.$ Consider the following non-smooth convex-concave saddle point problem
\begin{equation}\label{spp_App:C}
 \min\limits_{u \in Q_1}\max\limits_{v \in Q_2} \{ f(u,v) := \|u-\alpha\|_2 + \langle Au - b, v \rangle - \|v-\beta\|_2 \},
\end{equation}
where $Q_1 \times Q_2 \subset \mathbb{R}^{p} \times \mathbb{R}^{q}:=\mathbb{R}^{n}$, $\alpha \in \mathbb{R}^{p}$, $\beta \in \mathbb{R}^{q}$ are fixed points, $b \in \mathbb{R}^{q}$ and the matrix $A \in \mathbb{R}^{q \times p}$. Due to the non-smoothness of $f$, the corresponding operator $g$ given in \cref{eq:gSadPointDef}
 is H\"older-continuous with $\nu = 0$.

We take $ p=1000$, $q=500 $, therefore, $n=1500$. We also set
$\alpha_i = 0.1/\sqrt{1000}, \, i=1,...,p$ and $\beta_j = -0.1/\sqrt{500}, \, j = 1,...,q$. $Q_1 = \{u \in \mathbb{R}^p: \|u\|_2 \leq 1 \}$ and $Q_2 = \{v \in \mathbb{R}^q: \|v\|_2 \leq 1 \}$. $\varepsilon \in \{ 1/(2i+2), i=0,1,2,3,5,7,9,11,13,15,18,23,31\}$, $L^0 = \frac{\|g(1,0,...,0)-g(0,1,0,0,...,0)\|}{\sqrt{2}}$ and $x^0=\textbf{0}\in \mathbb{R}^n$.

The entries of the matrix $A$ are drawn from the standard normal distribution. The entries of the vector $b$ are random integers drawn from the discrete uniform distribution in the closed interval $[-10,10]$. For each value of the parameters, the random data was drawn 10 times and the results were averaged.

The results of the work of the \cref{Alg:UMP} for the problem \eqref{spp_App:C}, are represented in \cref{iter_SPP} and \cref{time_SPP}, below. These results demonstrate the number of iterations produced by \cref{Alg:UMP} to reach the $\varepsilon$-solution of the problem \eqref{spp_App:C}, and the running time of the algorithm in seconds, for the above mentioned different values of the accuracy $\varepsilon$.

As it is known \cite{nemirovsky1983problem}, for a VI with a non-smooth operator, the theoretical iteration complexity estimate $O\left(\frac{1}{\varepsilon^2}\right)$ is optimal. However, experimentally we see from slope of the line in \cref{iter_SPP} that, due to the adaptivity the proposed \cref{Alg:UMP} has iteration complexity $O\left(\frac{1}{\sqrt[3]{\varepsilon}}\right)$.

\begin{figure}[tbhp]
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB2_iter_loglog.jpg}
	\caption{Results of \cref{Alg:UMP} for saddle point problem with $p=1000, q=500 (n=1500)$ .}
	\label{iter_SPP}
	\endminipage\hfill
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB2_time_loglog.jpg}
	\caption{Results of \cref{Alg:UMP} for saddle point problem with $p=1000, q=500 (n=1500)$.}
	\label{time_SPP}
	\endminipage\hfill
\end{figure}

\subsection{Lagrange Saddle Point Problem}\label{sec:Fermat_Torr_stei}

We consider an example of a variational inequality with a non-smooth and not strongly monotone operator, i.e. with $\nu = 0$, for which the proposed universal method, due to its adaptivity to the level of smoothness of the problem, in practice works with iteration complexity much smaller than the predicted by theory.

This example is naturally connected with the analogue of the well-known {\it Fermat-Torricelli-Steiner problem}, but with some non-smooth functional constraints.

For a given set of $N$ points $A_k \in \mathbb{R}^n, k=1,...,N$ we need to solve the optimization problem
$$ \min_{x \in Q} \left\{f(x):= \sum\limits_{k=1}^N \|x - A_k\|_2 \left| \; \varphi_p(x):= \sum_{i=1}^n \alpha_{pi}|x_i| - 1 \leq 0 \right., \; p=1,...,m \right\},$$
where $Q$ is a convex compact, $\alpha_{pi}$ are drawn from the standard normal distribution and then truncated to be positive.

The corresponding Lagrange saddle point problem is defined as
$$
\min_{x \in Q} \max_{\overrightarrow{\lambda} = (\lambda_1,\lambda_2,\ldots,\lambda_m)^T \in \mathbb{R}^m_+} L(x,\lambda):=f(x)+\sum\limits_{p=1}^m\lambda_p\varphi_p(x),

$$

As it was described in \cref{S:saddle_point}, this problem is equivalent to the variational inequality with monotone non-smooth operator
$$
G(x,\lambda)=
\begin{pmatrix}
\nabla f(x)+\sum\limits_{p=1}^m\lambda_p\nabla\varphi_p(x), \\
(-\varphi_1(x),-\varphi_2(x),\ldots,-\varphi_m(x))^T
\end{pmatrix}.
$$
For simplicity, we assume that there exist (potentially very large) bound for the optimal Lagrange multiplier $\overrightarrow{\lambda}^*$, which allows us to compactify the feasible set for the pair $(x,\overrightarrow{\lambda})$ to be a Euclidean ball of some radius. We believe that the approach from \cite{monteiro2010complexity,dang2015convergence} to deal with unbounded feasible sets can be extended to our setting and we leave this for future work.

We run \cref{Alg:UMP} for different values of $n, m$, and $N$ with standard Euclidean prox-structure and the starting point $(x^0, \overrightarrow{\lambda}^0) = \frac{1}{\sqrt{m+n}} \textbf{1} \in \mathbb{R}^{n+m}$, where $\textbf{1} $ is the vector of all ones.

 Points $A_k$, $k=1,...,N$ are chosen randomly from standard normal distribution. For each value of the parameters, the random data was drawn 10 times and the results were averaged.

The results of the work of \cref{Alg:UMP}, are represented in \cref{appD_iter_log_log} and \cref{appD_time_log_log}. These results demonstrate the number of iterations produced by \cref{Alg:UMP} to reach the $\varepsilon$-solution of the Fermat-Torricelli-Steiner problem, and the running time of the algorithm in seconds, with different values of the accuracy $\varepsilon \in \{ 1/2^i, i=1,2,3,4,5,6\}$.

As it is known \cite{nemirovsky1983problem}, for a VI with a non-smooth operator, the theoretical iteration complexity estimate $O\left(\frac{1}{\varepsilon^2}\right)$ is optimal. However, experimentally we see from slope of the lines in \cref{appD_iter_log_log} that, due to the adaptivity of the proposed method \cref{Alg:UMP}, has iteration complexity $O\left(\frac{1}{\sqrt[4]{\varepsilon}}\right)$.

\begin{figure}[H]
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB3_iter_loglog.jpg}
	\caption{Results of \cref{Alg:UMP} for Fermat-Torricelli-Steiner problem with different values of $m$ and $n$.}
	\label{appD_iter_log_log}
	\endminipage\hfill
	\minipage{0.49\textwidth}
	\includegraphics[width=\linewidth]{appB3_time_loglog.jpg}
	\caption{Results of \cref{Alg:UMP} for Fermat-Torricelli-Steiner problem with different values of $m$ and $n$.}
	\label{appD_time_log_log}
	\endminipage\hfill
\end{figure}

\end{document}


TITLE: Prove that $f$ is an increasing function
QUESTION [0 upvotes]: Let $f$ be defined on the open interval $(a,b)$ and assume that for each $x\in(a,b)$ there exists a $1$-ball $B(x)$ in which $f$ is increasing. Can someone help me to prove that $f$ is increasing throughout $(a,b)$? Any answers will be much appreciated.

REPLY [0 votes]: Let $x,y\in(a,b)$ with $x<y$. Pick $q\in(0,1)$
Let $n=\min\{k\in\mathbb N\mid x+qk\ge y\}$  and let $x_i=x+qi$ for $0\le i<k$. Then $n\ge 1$ and $$f(x)=f(x_0)<f(x_1)<\ldots <f(x_{n-1})< f(y).$$


TITLE: Schur-Weyl duality and q-symmetric functions
QUESTION [15 upvotes]: Disclaimer: I'm far from an expert on any of the topics of this question. I apologize in advance for any horrible mistakes and/or inaccuracies I have made and I hope that the spirit of the question will still be clear despite them.
The (integral) representation rings of the symmetric groups can be packed together into a hopf algebra $H_1 = \oplus_n Rep(\Sigma_n)$ where the multiplication (resp. comultiplication) comes from induction (resp. restriction) along $\Sigma_n \times \Sigma_k \to \Sigma_{n+k}$. In fact there's a further structure one can put on $H$ corresponding to the inner product of characters and a notion of positivity (all together its sometimes called a "positive self adjoint hopf algebra"), but for simplicity I will disregard this structure in what follows (of course if its not important for the answer that would be great to know).
Its well known that sending the irreducible specht modules to their corresponding schur functions induces an isomorphism of hopf algebras to the (integral) hopf algebra of symmetric functions.
Following the "$\mathbb{F}_1$-philosophy" it is tempting to define a ring of "q-symmetric functions" as the hopf algebra $H_q = \oplus_n Rep(GL_n(\mathbb{F}_q))$ equipped with the same structures as above.

Question 1: Is there a hopf algebra over $\mathbb{Z}[q]$ which
  specializes at a prime power $q=p^n$ to $H_{p^n}$ and at $q=1$ to
  $H_1$ the classical ring of symmetric functions?

By schur weyl duality we also know that $H_1 \cong Rep(GL_{\infty}(\mathbb{C})):= colim_n Rep(GL_n(\mathbb{C}))$ (at least as rings). It seems natural to ask if there's any form of schur duality going in the other direction.

Question 2: Is there any kind of relationship between the rings $Rep(\Sigma_{\infty}) := colim_n Rep(\Sigma_n)$ and $\oplus_n Rep(GL_n(\mathbb{C}))$?
Question 3: Is there a $\mathbb{Z}[q]$-algebra which specializes to $Rep(GL_{\infty}(\mathbb{F}_q))$ at a prime power $q = p^n$ and to $Rep(\Sigma_{\infty})$ at $q=1$?

REPLY [14 votes]: As Sam Hopkins says, the category of all representations of $GL_n(\mathbb F_q)$ is too large to give what you want.  Instead, let's consider the category of unipotent representations,  i.e.  those appearing in the irreducible decomposition of $\mathbb Q [GL_n(\mathbb F_q)/B_n(\mathbb F_q)]$.
Unipotent representations are not closed under the naive induction product,  but they are closed under parabolic induction $V*W = {\rm Ind}_{P(n,m)}^{GL_{n+m}} V \otimes W$.  This gives $\oplus_n  {\rm Rep}^{un}(GL_n(\mathbb F_q))$ the structure of a monoidal category.  Instead of being symmetric monoidal, it is now braided monoidal!  The Grothendieck ring is a $q$ deformation of the ring of symmetric functions.
Finally, by Morita theory,  unipotent representations are equivalent to representations of $\mathcal H_n(q) = {\rm End}_{GL_n}(\mathbb Q GL_n/B_n )$,  here $\mathcal H_n(q)$ is the  Iwahori-Hecke algebra which $q$-deforms the group ring of $S_n$.  It is Schur-Weyl  dual  to representations of the quantum group $U_q(GL_\infty)$.


TITLE: $\lim \sup, \lim \inf $ of a fraction of sequence
QUESTION [1 upvotes]: Let $x_n$ be an upper bounded sequence, $y_n$ is a sequence that $\forall n \in \mathbb{N}$ such that $y_n \rightarrow y>0 $ then prove that:
$$ \lim \sup \frac{x_n}{y_n} = \frac{\lim \sup x_n}{\lim y_n } $$
I don't know how to begin. Well I know that there exists an $M$ such that $x_n < M$ and that $y_n $ converges to $y$. This can be written with the $\epsilon - \delta$ definition but I don't know if this works.
Any suggestions, hints?

REPLY [1 votes]: For sufficiently high $n$, $y_n>0$ so define $u_n:=\sup_{k>n}\frac{x_k}{y_k}$ for large $n$. This sequence is monotone so it has a limit. If $x=\limsup x_n$, we want to show that $\lim_{n\to\infty}u_n=\frac{x}y$. Fix $\epsilon>0$. Since $y_n\to y>0$ and $t\mapsto t^{-1}$ is continuous, $\frac1{y_n}\to\frac1y$. So there exists $N\in\mathbb{N}$ such that
$$\frac1y-\epsilon<\frac1{y_k}<\frac1y+\epsilon$$
for all $k>N$. This implies
$$\left(\frac1y-\epsilon\right)\sup_{k>n}x_k<u_n<\left(\frac1y+\epsilon\right)\sup_{k>n}x_k$$
for all $n\ge N$. Letting $n\to\infty$ we get
$$\left(\frac1y-\epsilon\right)x\le\lim_{n\to\infty} u_n\le\left(\frac1y+\epsilon\right)x$$
by the squeeze law. The result follows by letting $\epsilon\to0$.
EDIT: Throughout I have implicitly assumed $x>-\infty$. If this is not the case then the only change we need to make is noting that
$$\lim_{n\to\infty}u_n\le\left(\frac1y+\epsilon\right)\sup_{k>n}x_k=-\infty$$
and certainly $\frac{\limsup x_n}{\lim y_n}=-\infty$.


TITLE: Electron Self-Energy
QUESTION [2 upvotes]: Suppose an electron is bound to a nucleus, leading to an overall charge density
$$
\rho(x) = Ze\delta(x) - e \left|\psi(x) \right|^2.
$$
If I interpret this charge density just as I would in the context of classical electrostatics, I could easily calculate the electric field arising from it. I routinely think about such an electric field, especially in chemistry, where I often informally consider the electron orbitals to be interacting with each other via Coulomb repulsion. This electric field contains an energy given by
$$
U = \frac{1}{8\pi} \int \left| \vec{E(x)} \right|^2 d^3x.
$$
Using Gauss' Law, this energy can be rewritten in terms of the charge density that gives rise to it as
$$
U = \frac{1}{2}\int \frac{\rho(x_1)\rho(x_2)}{|x_{1}-x_{2}|} d^3x_1 d^3x_2.
$$
Substituting my expression for $\rho(x)$ gives three terms:
$$
U = \frac{(Ze)^2}{2} \int \frac{\delta(x_1)\delta(x_2)}{|x_{1}-x_{2}|} d^3x_1 d^3x_2 \\
  - Ze^2 \int \frac{|\psi(x)|^2}{|x|} d^3x \\
  + \frac{e^2}{2} \int  \frac{|\psi(x_1)|^2|\psi(x_2)|^2}{|x_{1}-x_{2}|} d^3x_1 d^3x_2.
$$
The first and second terms are totally understandable. The first is the electrostatic self-energy of the nucleus. If one remembers that the charge density of a nucleus is not actually a delta function, but rather some distribution with a length scale on the order of the nuclear radius, it can be understood to have a finite value that gives an upper bound on, for example, the energy released in some process like nuclear fission. Because the nuclear radius typically doesn't change in processes I am interested in, I regard this as a constant and ignore it.
The second term just gives the Coulomb attraction between the nucleus and electron. This is the term routinely used in the Hamiltonian to calculate e.g. the energy of a hydrogen-like atom.
The third term I have little understanding of. The only length scale in the integrand is the Bohr radius $a$, and so the third term will be on the order of $\frac{e^2}{a}$, which is on the order of the binding energy of the nucleus and electron. The fine-structure constant doesn't appear, and so this cannot be regarded as a self-energy interaction stemming from some QED correction (I am treating the electric field classically anyway, so that's expected).
So what is it? Does it have any physical significance, and why is it ignored when one usually calculates the energy of a hydrogen-like atom? This term should increase the atomic radius and cause the electronic charge density to 'repel itself'. I think my result is incorrect and the third term should be absent, but I am not sure what assumption is wrong.

REPLY [0 votes]: This question is related to the initial Schrödinger's interpretation of $|\psi|^2$ as charge density (up to a constant factor). Taking into account the self-energy seemed to yield incorrect results for the energies of the atomic levels.
A.O. Barut wrote a lot about this problem (see, e.g., Ann. Physik Leipzig 45 (1988) 1, 31-36 and references there).
Abstract:

Radiation theory is reformulated by reviving the interpretation of
$\psi$-waves as realistic material waves of electronic matter and the
relation of this formulation to second quantized quantum field theory
is discussed.

I did not check his derivations in detail, but he seems to say that taking into account the self-field gives correct results after some renormalization:

The contribution of the self energy can then be calculated by an
iterative procedure. Infinite terms separate and can be absorbed into
energy and mass terms on the left hand side of eq. (10). A more
careful analysis [14] shows that the infrared and ultra-violet
divergences actually do not appear if the intergrals are properly
defined by their Mellin transformations in the same way as the
infinite terms in classical electrodynamics disappear by the use of
Riesz potential [15]. In these last treatments no renormalization
seems to be necessary, the parameters of the theory $e$ and $m$, are
already the physical charge and mass.

Let me also note that I recently proposed a plasma-like modification of Schrödinger's interpretation (Entropy 2022, 24(2), 261 ; Quantum Rep. 2022, 4(4), 486-508)


TITLE: Equivalence class over a set of natural numbers with conditions
QUESTION [1 upvotes]: My discrete math class has this problem: we need to find the equivalence classes for the equivalence relation over the set of $\mathcal{N}$ onto $\mathcal{N}$ defined as follows:
$$xRy \iff (x-3.3)(y-3.6)>0$$
I thought that there's only 1 class: $\{\mathcal{N}-{0,1,2,3}\}$ that is all natural numbers greater than 3. However the solution says that there's another equivalance class: $\{0,1,2,3\}$. But how can this be?
$$1R2 \to (1-3.3)(2-3,6) <0$$
so clearly such input renders the output to be below zero hence it can't be part of the relation.

REPLY [1 votes]: $$(1-3.3)(2-3.6)\color{red}{>}0$$
or more generally
$$x\cdot y>0\iff (x>0\ \land  y>0)\ \lor \ (x<0\ \land  y<0)$$


TITLE: Does this vector equation have a solution
QUESTION [0 upvotes]: I am working with a modified version of the Lorentz force equation wherein I am trying to find generalized E and B field components that produce a specific particle path. I have replaced E with $$\vec{E}=\frac{\vec{v} ^{2}}{2\vec{r}}$$ so my only unknowns are the x,y,z components of the B field.
I want to solve the following equation now for Bx, By, and Bz where a,v, r (and E) are known.
$$
\vec{a} = \vec{E}+\vec{v}\times \vec{B}
$$
I am not sure if the following matrix can be used to solve this equation, but, if it is, it doesn't seem to have a solution. (due to the 0 determinant). I figured that there would be a solution because there are three unknowns (Bx, By, Bz) and three equations, but I am trouble proving this.
$$
\begin{pmatrix}
 0& -v_{z} &v_{y} \\
 v_{z}&0  &-v_{x} \\
 -v_{y}&  v_{x}& 0
\end{pmatrix}\begin{pmatrix}
B_{x}\\
B_{y}\\
B_{z}
\end{pmatrix} =\begin{pmatrix}
a_{x}-E_{x}\\a_{y}-E_{y}
\\ a_{z}-E_{z}
\end{pmatrix}
$$
So mainly I want to know if the matrix I have set up represents the equation above it and if a solution for the B components can be achieved.

REPLY [1 votes]: The cross product $\vec{v}\times$ is indeed not invertible, due to the fact that it has a non-trivial nullspace (all vectors parallel to $\vec{v}$).
There are thus two possibilities:

$\vec{a}-\vec{E}$ is perpendicular to $\vec{v}$: a solution exists where the components of $\vec{B}$ perpendicular to $\vec{v}$ are uniquely specified but the component of $\vec{B}$ parallel to $\vec{v}$ is arbitrary.
$\vec{a}-\vec{E}$ is not perpendicular to $\vec{v}$: your equation is a contradiction, no solution exists.


TITLE: Khinchin's Law of Large numbers proof unclarity.
QUESTION [1 upvotes]: This is the formulation:
Let $X_n,n=1,2,...$ be independent, equally distributed random variables. $EX_k=a$(expectation) $k=1,2,...$. For this sequence of $X_n$ the law of large numbers applies: $$\frac{1}{n}\sum_{k=1}^{n}X_k \to^{P}a.$$
Proof:
Let $t$ be  a real fixed number. (With $f_x(t)$ I denote the characteristic function of variable X).
So
$$f_{\frac{1}{n}\sum_{k=1}^{n}X_k}(t)=\prod_{k=1}^{n}f_{X_k}(\frac{t}{n})=\text{(this equality is unclear to me }=(1+ai\frac{t}{n}+o(\frac{t}{n}))^n\to^{n\to \infty}\text{this is unclear to me also }=e^{ait}$$
This definitely has something to do with macloren's series of $e^x.$ I just can't see it clearly. I would very much appreciate if someone could do a step by step clarifications of these unclear inequalities to me.

REPLY [1 votes]: We have $f_{X}(t) = 1 + i t a + o(t)$ as $t \rightarrow 0$.
Characteristic functions, however, have these two general properties:
$$
f_{ {1 \over n} X(t)} = f_{X}(t/n) \quad \mbox{and} \quad
f_{ X(t) + Y(t) } = f_{X}(t) f_{Y}(t).
$$
(i.e., rescaling the original r.v. rescales the argument of the char. fun., and sums of r.v.'s are transformed into products of char. fun.'s).
The first equality that is unclear to you follows from these two properties.
The last conclusion (limit) you are asking about is obtained by dropping the negligible term $o(t)$ and examining the limit
$$
\lim_{n \rightarrow +\infty} \; (1 + {1 \over n} i a t)^{n}.
$$
And it is one of these: https://en.wikipedia.org/wiki/List_of_limits#Notable_special_limits


TITLE: Centralizers and conjugacy classes
QUESTION [1 upvotes]: Let $G$ be a finite group with order 168 such that for each element $g \in G$ wih order $7$, the centralizer $C_G (g)$ is equal to $\langle g \rangle$. Compute the number of conjugacy classes of elements $g$ of order $7$ and find the size of the conjugacy class for such an element.

I tried to begin with the class equation, but didn't have any luck. I don't know if I will need to use the definition of a Sylow subgroup at some point here.
I would appreciate any help.

REPLY [4 votes]: Let $G$ act on $G$ by conjugation.  Then each orbit of an element is its conjugacy class, and the size of the orbit is the index of the element's stabilizer.  We're given that the stabilizer (which is the element's centralizer) has size $7$ so it has index $24$.  Thus, each conjugacy class of an element of order $7$                                                                                has size $24$.
The $7$-Sylow subgroups of $G$ are not normal.  If one were, its non-trivial elements would have a conjugacy class of size no more than $6$.
Thus, $G$ must have $8$ $7$-Sylow subgroups (because no other divisor $d$ of $168$ satisfies $d \equiv 1 \pmod 7$).  Two distinct $7$-Sylow subgroups of $G$ must have trivial intersection, which means $G$ has $48$ distinct elements of order $7$.  Therefore, there are $2$ such conjugacy classes.


TITLE: radius of convergence involving power series
QUESTION [0 upvotes]: Consider the power series $$\sum_{n=1}^{\infty}\left[x^n(1-\cos\left(1 \over n\right))\right].$$
(I) Determine its radius of convergence $R$
(II) Examine the convergence/divergence of the power series when $x = +R$ and $x = -R$

Help will be much appreciated. Im not sure how to proceed

REPLY [1 votes]: If we use the well known equivalence
$$1-\cos(X)\sim \frac{X^2}{2}\;\;\;(X\to 0)$$
with $X=\frac 1n$ and $n\to  +\infty$,
we get
$$1-\cos(\frac 1 n)\sim \frac{1}{2n^2}$$
the two series have the same radius $R=1,$ by ratio test
at $x=\pm1, $
$\sum \frac{1}{n^2}$ and $\sum (1-\cos(\frac{1}{n})) (-1)^n $ converge absolutly by the limit comparison test.