text:
\begin{document}

\maketitle

\begin{abstract}
In this paper, we propose a new algorithm to speed-up the convergence of accelerated proximal gradient (APG) methods. In order to minimize a convex function $f(\mathbf{x})$, our algorithm introduces a simple line search step after each proximal gradient step in APG so that a biconvex function $f(\theta\mathbf{x})$ is minimized over scalar variable $\theta>0$ while fixing variable $\mathbf{x}$. We propose two new ways of constructing the auxiliary variables in APG based on the intermediate solutions of the proximal gradient and the line search steps. We prove that at arbitrary iteration step $t (t\geq1)$, our algorithm can achieve a smaller upper-bound for the gap between the current and optimal objective values than those in the traditional APG methods such as FISTA \cite{Beck:2009:FIS:1658360.1658364}, making it converge faster in practice. In fact, our algorithm can be potentially applied to many important convex optimization problems, such as sparse linear regression and kernel SVMs. Our experimental results clearly demonstrate that our algorithm converges faster than APG in all of the applications above, even comparable to some sophisticated solvers.
\end{abstract}

\section{Introduction}\label{sec:intr}
As a general convex minimization algorithm, accelerated proximal gradient (APG) has been attracting more and more attention recently, and it has been widely used in many different research areas such as signal processing \cite{Combettes_Pesquet}, computer vision \cite{conf/cvpr/BaoWLJ12}, and data mining \cite{Zhou:2010:NFG:1933307.1934518}. In general, APG solves the following problem:
\begin{equation}\label{eqn:problem}
\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})=f_1(\mathbf{x})+f_2(\mathbf{x})
\end{equation}
where $\mathcal{X}\subseteq\mathbb{R}^n$ denotes the closed and convex feasible set for variable $\mathbf{x}\in\mathbb{R}^n$, and $f(\mathbf{x}):\mathbb{R}^n\rightarrow\mathbb{R}$ is a convex function, which consists of a convex and differentiable function $f_1$ with Lipschitz constant $L\geq0$ and a convex but non-differentiable function $f_2$.

In APG, proximal gradient is used to update variables based on the proximity operator, denoted as $\mathbf{prox}$. The basic idea of proximity operator is to approximate a convex function using a strongly convex function whose minimizer in the feasible set is returned as an approximate solution for the original minimization problem. At the optimal solution, the solution returned by proximity operator is identical to the optimal. As an example among classic APG algorithms, the basic version of FISTA \cite{Beck:2009:FIS:1658360.1658364} is shown in Alg. \ref{alg:fista}, where $\forall t=1,\cdots,T, \gamma_t$ denotes the step size. From FISTA, we can see that APG generates an {\it auxiliary variable} (\ie $\mathbf{v}_t$ in Alg. \ref{alg:fista}) for proximal gradient so that the convergence rate of APG for general convex optimization is $O(\frac{1}{T^2})$, which was proved to be optimal for first-order gradient descent methods \cite{tagkey198475}.

Generally speaking, the computational bottleneck in APG comes from the following two aspects:

\textbf{(\rmnum{1}) Computation of proximal gradients.}
Evaluating the gradients of $f_1$ could be time-consuming, because the evaluation is over the entire dataset. This situation is more prominent for high dimensional and large-scale datasets. Also, projecting a point into the feasible set may be difficult. Many recent approaches have attempted to reduce this computational complexity. Inexact proximal gradient methods \cite{DBLP:conf/nips/SchmidtRB11} allow to approximate the proximal gradients with controllable errors in a faster way while guaranteeing the convergence. Stochastic proximal gradient methods \cite{atchade2014stochastic,rosasco2014convergence} allow to compute the proximal gradients using a small set of data in a stochastic fashion while guaranteeing the convergence as well. Distributed proximal gradient methods \cite{chen2012fast} decompose the optimization problem into sub-problems and solve these sub-problems locally in a distributed way using proximal gradient methods.

\textbf{(\rmnum{2}) Number of iterations.}
In order to minimize the number of iterations, intuitively in each iteration the resulting function value should be as close to the global minimum as possible. One way to achieve this is to optimize the step size in the proximal gradient (\eg $\gamma_t$ in Alg. \ref{alg:fista}), which unfortunately may be very difficult for many convex functions. Instead, in practice line search \cite{Beck:2009:FIS:1658360.1658364,DBLP:conf/icml/LinX14,DBLP:journals/focm/ScheinbergGB14,DBLP:journals/siamjo/Xiao013} is widely used to estimate the step size so that the function value is decreasing. For instance, backtracking \cite{Beck:2009:FIS:1658360.1658364,DBLP:journals/focm/ScheinbergGB14} is a common line search technique to tune the step size gradually. In general, the line search in the proximal gradient step has to evaluate the function repeatedly by changing the step size so that numerically the learned step size is close to the optimal. Alternatively many types of restarting schemes \cite{DBLP:conf/icml/LinX14,DBLP:journals/mp/Nesterov13,Brendan2013} have been utilized to reduce the number of iterations empirically.  Here additional restarting conditions are established and evaluated periodically. If such conditions are satisfied, the algorithm will be re-initialized using current solutions.

\begin{algorithm}[t]\small
\SetAlgoLined
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{$f(\mathbf{x})$, $\lambda$, $\mathbf{x}_0$}
\Output{$\mathbf{x}$}
\BlankLine
\For{$t=1,\cdots,T$}{
$\mathbf{v}_t\leftarrow\mathbf{x}_t+\frac{t-1}{t+2}\left(\mathbf{x}_t-\mathbf{x}_{t-1}\right)$; \quad
$\mathbf{x}_t\leftarrow\mathbf{prox}_{\lambda f_2}(\mathbf{v}_t-\gamma_t\triangledown f_1(\mathbf{v}_t))$;
}
\Return $\mathbf{x}_T$\;
\caption{FISTA \cite{Beck:2009:FIS:1658360.1658364}: Fast Iterative Shrinkage-Thresholding Algorithm}\label{alg:fista}
\end{algorithm}

\subsection{Our Contributions}
In this paper, we focus on reducing the number of iterations, and simply assume that the non-differentiable function $f_2$ is {\it simple} \cite{DBLP:journals/mp/Nesterov13} for performing proximal gradient efficiently, \eg $\ell_1$ norm.

Our first contribution is to propose a new general algorithm, {\it \underline{R}apidly \underline{A}ccelerated \underline{P}rox\underline{i}mal Gra\underline{d}ient (\textbf{RAPID})}, to speed up the empirical convergence of APG, where an additional simple line search step is introduced after the proximal gradient step. Fig. \ref{fig:intuition}(a) illustrates the basic idea of our algorithm in 2D. After the proximal gradient step, another line search is applied along the direction of the current solution $\mathbf{x}$. Ideally, we would like to find a scalar $\theta>0$ so that $\theta=\argmin_{\{\hat{\theta}|\hat{\theta}\mathbf{x}\in\mathcal{X}\}}f(\hat{\theta}\mathbf{x})$. Therefore, we can guarantee $f(\theta\mathbf{x})\leq f(\mathbf{x})$. The positiveness of $\theta$ guarantees that both $\mathbf{x}$ and $\theta\mathbf{x}$ point to the same direction so that the information from gradient descent can be preserved. Geometrically, this additional line search tries to push $\mathbf{x}$ towards the optimal solution, making the distance between the current and optimal solutions smaller. Unlike the line search in the proximal gradient, the computation of finding the optimal $\theta$ can be very cheap (\eg with close-form solutions) for many convex optimization problems, such as LASSO \cite{tibshirani96regression} and group LASSO \cite{yuan2006model} (see Section \ref{sec:app}). Also, in order to guarantee the convergence of our algorithm, we further propose two ways of constructing the auxiliary variables based on the intermediate solutions in the previous and current iterations, as illustrated in Fig. \ref{fig:intuition}(b).

Our second contribution is that theoretically we prove that at an arbitrary iteration $t$, the upper bound of the objective error $f(\theta_t\mathbf{x}_t)-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})$ in our algorithm is consistently smaller than that of $f(\mathbf{x}_t)-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})$ in traditional APG methods such as FISTA. This result implies that in order to achieve the same precision, the number of iterations in our algorithm is probably no more than that in APG. In other words, empirically our algorithm will converge faster than APG.

Our third contribution is that we apply our general algorithm to several interesting convex optimization problems, \ie LASSO, group LASSO, least square loss with trace norm \cite{Ji:2009:AGM:1553374.1553434,journals/mp/Tseng10}, and kernel support vector machines (SVMs), and compare our performance with APG and other existing solvers such as SLEP \cite{Liu:2009:SLEP:manual} and LIBSVM \cite{CC01a}. Our experimental results demonstrate the correctness of our theorems on faster convergence than APG, and surprisingly in most cases, our algorithm can be comparable with those sophisticated solvers.

This paper is organized as follows. In Section \ref{sec:alg}, we explain the details of our RAPID algorithm, including the new line search step and how to construct the auxiliary variables. In Section \ref{sec:app}, we take LASSO, group LASSO, least square loss with trace norm, and kernel SVMs as examples to demonstrate the empirical performance of our algorithm with experimental results and comparison with APG and other existing solvers. The theoretical results on the convergence rate of our algorithm are proven in Section \ref{sec:analysis}, and finally we conclude the paper in Section \ref{sec:con}.

\begin{figure}[t]
\begin{minipage}[b]{0.35\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=0.9\columnwidth]{intuition.png}}
 \centerline{\footnotesize{(a)}}
 \end{center}
\end{minipage}

\begin{minipage}[b]{0.65\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=\columnwidth]{rapid.png}}
 \centerline{\footnotesize{(b)}}
 \end{center}
\end{minipage}\vspace{-5mm}
\caption{\footnotesize{(a) Illustration of the basic idea of our algorithm for improving convergence of APG in 2D, where $\mathbf{o}$ denotes the origin of the 2D coordinate system, $\mathbf{v}$, $\mathbf{x}$, $\theta\mathbf{x}$, and $\mathbf{x}^*$ denote the solutions at the initial point, after the proximal gradient step, after the line search step, and at the minimum, respectively, and the directed lines denote the updating directions. (b) Illustration of the differences between APG and our RAPID in terms of constructing the auxiliary variable $\mathbf{v}_t$ in iteration $t$, where directed lines denote the generating orders of intermediate solutions, and the dotted lines denote the directions of the auxiliary variable starting at the solution in iteration $t-1$. This figure is best viewed in color.}}\label{fig:intuition}
 \vspace{-2mm}
\end{figure}

\section{Algorithms}\label{sec:alg}

In general, there are two basic steps in each iteration in APG algorithms: (1) performing {\it proximal gradients}, and (2) constructing {\it auxiliary variables}. Proximal gradient is defined as applying {\it proximity operator} to a gradient descent step.

\begin{mydef}[Proximity Operator \cite{Combettes_Pesquet}]
The proximal operator $\mathbf{prox}:\mathbb{R}^n\rightarrow\mathbb{R}^n$ is defined by
\begin{equation}
\mathbf{prox}_{\lambda f}(\mathbf{v})=\argmin_{\mathbf{x}\in\mathcal{X}}\left(f(\mathbf{x})+\frac{1}{2\lambda}\|\mathbf{x}-\mathbf{v}\|_2^2\right),
\end{equation}
where $\|\cdot\|_2$ is the Euclidean norm, $\mathcal{X}$ is a closed and convex set, and $\lambda>0$ is a scaling parameter.
\end{mydef}

Alg. \ref{alg:rapid} shows our RAPID algorithm, where in each iteration $t(t\geq 1)$ four steps are involved:
\begin{itemize}
\item[Step 1:] A proximal gradient step using the auxiliary variable $\mathbf{v}_{t-1}$, same as APG.
\item[\textbf{\em Step 2}:] \textbf{\em A simple line search step along the direction of the current solution $\mathbf{x}_t$.} Actually the definition of $\theta_t$ in Alg. \ref{alg:rapid} is equivalent to the following equation:
\begin{equation}
\mathbf{x}_t^*=\mathbf{prox}_{\lambda_{\theta}f}(\mathbf{x}_t)\in\{\tilde{\mathbf{x}}_t|\exists\theta, \tilde{\mathbf{x}}_t=\theta\mathbf{x}_t\in\mathcal{X}\}.
\end{equation}
In other words, this line search step essentially {\it adapts} the current solution $\mathbf{x}_t$ to a better one in a very efficient way (\eg with close-form solutions).
\item[Step 3:] Updating parameter $\eta_t$ used for constructing the new auxiliary variable $\mathbf{v}_t$, same as APG. Note that any number sequence $\{\eta_t\}$ can be used here as long as the sequence satisfies $\forall t\leq1, \frac{1-\eta_{t+1}}{\eta_{t+1}^2}\leq\frac{1}{\eta_t^2}$.
\item[\textbf{\em Step 4}:] \textbf{\em Updating the new auxiliary variable $\mathbf{v}_t$ using one of the following two equations:}
\begin{eqnarray}\label{eqn:rapid-1}
\mathbf{v}_t=\eta_t(1-\eta_{t-1}^{-1})\theta_{t-1}\mathbf{x}_{t-1}+\eta_t\eta_{t-1}^{-1}\mathbf{x}_t+(1-\eta_t)\theta_t\mathbf{x}_t,
\end{eqnarray}
\begin{eqnarray}\label{eqn:rapid-2}
\mathbf{v}_t=\eta_t(1-\eta_{t-1}^{-1})\theta_{t-1}\mathbf{x}_{t-1}+(1-\eta_t+\eta_t\eta_{t-1}^{-1})\theta_t\mathbf{x}_t.
\end{eqnarray}
In this way, our algorithm guarantees its convergence, but with different convergence rate. See our comparison results in Section \ref{sec:app}.
\end{itemize}
Fig. \ref{fig:intuition}(b) illustrates the differences in constructing the auxiliary variable between APG and our RAPID. In APG, the auxiliary variable $\mathbf{v}_t$ is constructed along the gradient of $\mathbf{x}_t-\mathbf{x}_{t-1}$ starting from $\mathbf{x}_t$. Similarly, in RAPID we would like to construct the auxiliary variable $\mathbf{v}_t$ using $\theta_t\mathbf{x}_t$ and the other intermediate solutions in the previous and current iterations (\ie $\mathbf{x}_{t-1}, \theta_{t-1}\mathbf{x}_{t-1}, \mathbf{x}_t$). It turns out that {\em all possible combinations of intermediate solutions for constructing $\mathbf{v}_t$ end up with Eq. \ref{eqn:rapid-1}}, with guaranteed better upper bounds over $f(\theta_t\mathbf{x}_t)-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})$ than those over $f(\mathbf{x}_t)-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})$ in APG in arbitrary iteration $t$ (see Theorem \ref{thm:rapid-1} in Section \ref{sec:analysis}). Under a mild condition, we can adopt the same way as APG to construct $\mathbf{v}_t$ using the final solutions in the previous and current iterations, \ie $\theta_{t-1}\mathbf{x}_{t-1}$ and $\theta_t\mathbf{x}_t$, which is exactly Eq. \ref{eqn:rapid-2}. However, for this setting we lose the theoretical guarantee of better upper bounds than APG, as shown in Theorem \ref{thm:rapid-2} in Section \ref{sec:analysis}. Nevertheless, surprisingly, in our experiments our algorithm using Eq. \ref{eqn:rapid-2} outperforms than that using Eq. \ref{eqn:rapid-1} with significant improvement in terms of empirical convergence (see Section \ref{sec:app} for details).

\begin{algorithm}[t]\small
\SetAlgoLined
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{$f(\mathbf{x})$, $\lambda_{\mathbf{x}}$, $\lambda_{\theta}$}
\Output{$\mathbf{x}$}
\BlankLine
$\mathbf{x}_0\leftarrow\mathbf{0}$; $\mathbf{v}_0\leftarrow\mathbf{x}_0$; $\theta_0\leftarrow 1$; $\eta_0\leftarrow 1$;\\
\For{$t=1,\cdots,T$}{
$\mathbf{x}_t\leftarrow\mathbf{prox}_{\lambda_{\mathbf{x}}f_2}(\mathbf{v}_{t-1}-\gamma_t\triangledown f_1(\mathbf{v}_{t-1}))$;
$\theta_t\leftarrow\argmin_{\{\theta|\theta\mathbf{x}_t\in\mathcal{X}\}}\left\{f(\theta\mathbf{x}_t)+\frac{1}{2\lambda_{\theta}}\|\theta\mathbf{x}_t-\mathbf{x}_t\|_2^2\right\}$; \\
$\eta_t=\frac{\sqrt{\eta_{t-1}^4+4\eta_{t-1}^2}-\eta_{t-1}^2}{2}$; \quad Update $\mathbf{v}_t$ using either Eq. \ref{eqn:rapid-1} or Eq. \ref{eqn:rapid-2};
}
\Return $\theta_T\mathbf{x}_T$\;
\caption{RAPID: \underline{R}apidly \underline{A}ccelerated \underline{P}rox\underline{i}mal Gra\underline{d}ient Algorithms}\label{alg:rapid}
\end{algorithm}

\section{Numerical Examples}\label{sec:app}

In this section, we will explain how to apply our algorithm to solve (1) sparse linear regression (\ie LASSO, group LASSO, and least square fitting with trace-norm), and (2) binary kernel SVMs. We also compare our empirical performance with APG and some other existing solvers.

\subsection{Sparse Linear Regression}
\subsubsection{Problem Settings}
We denote $\mathbf{A}=\{\mathbf{a}_i\}_{i=1,\cdots,N}\in\mathbb{R}^{N\times d}$ as a data matrix, $\mathbf{y}=\{y_i\}_{i=1,\cdots,N}\in\mathbb{R}^{N}$ as a regression target vector, $\mathbf{Y}=\{\mathbf{y}_j\}_{j=1,\cdots,M}\in\mathbb{R}^{N\times M}$ as a matrix consisting of $M$ regression tasks, $\mathbf{x}\in\mathbb{R}^d$ as a linear regressor, $\mathbf{X}=\{\mathbf{x}_j\}_{j=1,\cdots,M}\in\mathbb{R}^{d\times M}$ as a matrix consisting of $M$ linear regressors, and $\lambda\geq0$ as a regularization parameter. As follows, for each method we list its loss function, regularizer, proximity operation, and optimal line search scalar $\theta$, which are used in Alg. \ref{alg:rapid}.

\textbf{(\rmnum{1}) Loss functions (\ie $f_1$, convex and differentiable).} Least square loss is used in all the methods, \ie $\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_2^2$ for LASSO and group LASSO, and $\frac{1}{2}\sum_{j=1}^{M}\|\mathbf{A}\mathbf{x}_j-\mathbf{y}_j\|_2^2$ for trace-norm.

\textbf{(\rmnum{2}) Regularizers (\ie $f_2$, convex but non-differentiable).} The corresponding regularizers in LASSO, group LASSO, and trace-norm are $\lambda\|\mathbf{x}\|_1$, $\lambda\sum_{g\in\mathcal{G}}\|\mathbf{x}^{(g)}\|_2$, and $\lambda\|\mathbf{X}\|_*=\mathbf{trace}\left(\sqrt{\mathbf{X}^T\mathbf{X}}\right)=\sum_{j=1}^{\min(d,M)}\sigma_j$, respectively. Here, $\|\cdot\|_1$ and $\|\cdot\|_2$ denote $\ell_1$ and $\ell_2$ norms, $(\cdot)^T$ denotes the matrix transpose operator, $g\in\mathcal{G}$ denotes a group index, $\mathbf{x}^{(g)}$ denotes a group of variables without overlaps, and $\sigma_j$ denotes the $j^{th}$ singular value for matrix $\sqrt{\mathbf{X}^T\mathbf{X}}$.

\textbf{(\rmnum{3}) Proximity operators.} According to their regularizers, the proximity operators can be calculated efficiently as follows, where $\mathbf{u}=\{u_j\}$ and $\mathbf{U}=\{\mathbf{u}_j\}$ are denoted as the variable vector and matrix after the gradient descent:
\begin{itemize}
\item LASSO: $\mathbf{prox}_{\lambda f_{\|\cdot\|_1}}(u_j)=\mathbf{sign}(u_j)\cdot\max\left\{0,|u_j|-\lambda\right\}$, where $\mathbf{sign}(u_j)=1$ if $u_j\geq0$, otherwise, $\mathbf{sign}(u_j)=-1$; and $|u_j|$ denotes its absolute value.
\item Group LASSO: $\mathbf{prox}_{\lambda f_{\|\cdot\|_2}}(u_j^{(g)})=\frac{u_j^{(g)}}{\|\mathbf{u}^{(g)}\|_2}\cdot\max\left\{0,\|\mathbf{u}^{(g)}\|_2-\lambda\right\}$.
\item Trace norm: Letting $\mathbf{U}=\mathbf{P}\cdot\mathbf{diag}(\boldsymbol{\sigma})\cdot\mathbf{Q}^T$, where $\mathbf{P}\in\mathbb{R}^{d\times n}$ and $\mathbf{P}\in\mathbb{R}^{M\times n}$ are two matrices and $\boldsymbol{\sigma}$ is a vector with $n$ singular values of $\mathbf{U}$, then we have $\mathbf{prox}_{\lambda f_{\|\cdot\|_*}}(\mathbf{U})=\mathbf{P}\cdot\mathbf{prox}_{\lambda f_{\|\cdot\|_1}}(\boldsymbol{\sigma})\cdot\mathbf{Q}^T$. Here $\mathbf{prox}_{\lambda f_{\|\cdot\|_1}}$ is an entry-wise operator.
\end{itemize}

\textbf{(\rmnum{4}) Optimal line search scalar $\theta$.}
For each problem, we re-define $\theta$ as $\theta_t=\argmin_{\theta}\left\{f(\theta\mathbf{x}_t)\right\}$ in arbitrary iteration $t$ by setting $\lambda_{\theta}=+\infty$ in Alg. \ref{alg:rapid}, because there exists a close-form solution in this case. Letting $\forall t, \frac{\partial f(\theta\mathbf{x}_t)}{\partial\theta}=0$, we have $\theta_t=\frac{\mathbf{y}^T\mathbf{A}\mathbf{x}_t-f_2(\mathbf{x}_t)}{\|\mathbf{A}\mathbf{x}_t\|_2^2}$ for LASSO or group LASSO, and $\theta_t=\frac{\sum_j\mathbf{y}_j^T\mathbf{A}(\mathbf{x}_j)_t-\lambda\|\mathbf{X}_t\|_*}{\sum_j\|\mathbf{A}(\mathbf{x}_j)_t\|_2^2}$ for trace-norm.

\subsubsection{Experimental Results}
\begin{figure}[htbp]
\begin{minipage}[b]{0.33\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=0.8\columnwidth]{syn_LASSO.png}}
 \centerline{\footnotesize{(a)}}
 \end{center}
\end{minipage}

\begin{minipage}[b]{0.33\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=0.8\columnwidth]{syn_gLASSO.png}}
 \centerline{\footnotesize{(b)}}
 \end{center}
\end{minipage}

\begin{minipage}[b]{0.33\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=0.8\columnwidth]{syn_trace.png}}
 \centerline{\footnotesize{(c)}}
 \end{center}
\end{minipage}\vspace{-4mm}
\caption{\footnotesize{Empirical convergence rate comparison using synthetic data on (a) LASSO, (b) group LASSO, and (c) trace-norm. This figure is best viewed in color.}}\label{fig:synthetic}

\end{figure}

We test and compare our RAPID algorithm on some synthetic data. For each sparse linear regression method, we generate a $10^3$ sample data matrix with $10^3$ dimensions per sample as variable $\mathbf{A}$, and its associated regression target vector (matrix) $\mathbf{y}$ ($\mathbf{Y}$) randomly by normal distributions. The APG and RAPID methods are modified based on the code in \cite{Brendan2013}\footnote{The code can be downloaded from \url{https://github.com/bodono/apg}. We do not use the re-starting scheme in the code.}, and SLEP \cite{Liu:2009:SLEP:manual} is a widely used sparse learning toolbox for our comparison. Here, RAPID-I and RAPID-II denote our algorithm using Eq. \ref{eqn:rapid-1} and Eq. \ref{eqn:rapid-2}, respectively. SLEP-0, SLEP-1, and SLEP-2 are the three settings used in SLEP with different parameters $mFlag$ and $lFlag$ (\ie (mFlag, lFlag)=SLEP-\#: (0,0)=0, (0,1)=1, (1,1)=2). Please refer to the toolbox manual for more details. For trace-norm, SLEP actually implements the APG algorithm as its solver.

Fig. \ref{fig:synthetic} shows our comparison results. In Fig. \ref{fig:synthetic}(a), the performances of SLEP-0 and SLEP-1 are identical, and thus there is only one curve (\ie the brown one) for both methods. Clearly, our RAPID-II algorithm works best in these three cases in terms of empirical convergence rate. Since we can only guarantee that the upper bound of the difference between the current and optimal objective values in each iteration in RAPID is no bigger than that in APG (see Section \ref{sec:analysis}), sometimes the actual objective value using RAPID may be larger than that using APG, as shown in Fig. \ref{fig:synthetic}(a).

\subsection{Kernel SVMs}

We are interested in solving binary kernel SVMs as well, because it is a widely used {\em constrained} optimization problem.

\subsubsection{Problem Settings}
Given a kernel matrix $\mathbf{K}\in\mathbb{R}^{N\times N}$ and a binary label vector $\mathbf{y}\in\{-1,1\}^{N}$ with $N$ samples, a binary kernel SVM can be formulated as follows:
\begin{eqnarray}\label{eqn:binary-svms}
\lefteqn{\hspace{-49mm}\min_{\boldsymbol{\alpha}}f(\boldsymbol{\alpha})=\frac{1}{2}\boldsymbol{\alpha}^T\mathbf{Q}\boldsymbol{\alpha}-\mathbf{e}^T\boldsymbol{\alpha}}\\
\begin{array}{ll}
s.t. & \forall i, 0\leq\alpha_i\leq C, \mathbf{y}^T\boldsymbol{\alpha}=0,\nonumber
\end{array}
\end{eqnarray}
where $\mathbf{Q}=\mathbf{K}\odot(\mathbf{y}\mathbf{y}^T)$, $\odot$ is the entry-wise product operator, $\mathbf{e}=\{1\}^N$ denotes a vector of 1's, and $C\geq0$ is a predefined constant.

\begin{algorithm}[t]\footnotesize
\SetAlgoLined
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{$\mathbf{Q}$, $\mathbf{y}$, $C$}
\Output{$\boldsymbol{\alpha}$}
\BlankLine
$\mathbf{x}_0\leftarrow\mathbf{0}$; $\mathbf{v}_0\leftarrow\mathbf{x}_0$; $\theta_0\leftarrow 1$; $\eta_0\leftarrow 1$;\\
\For{$t=1,\cdots,T$}{
$\Delta\mathbf{v}_t\leftarrow\mathbf{Q}\mathbf{v}_{t-1}-\mathbf{e}$; $\Delta\mathbf{v}_t\leftarrow\Delta\mathbf{v}_t-\left(\frac{\mathbf{y}^T\Delta\mathbf{v}_t}{\|\mathbf{y}\|_1}\right)\mathbf{y}$; $\gamma_{\mathbf{v}}\leftarrow\frac{\Delta\mathbf{v}_t^T\mathbf{Q}\mathbf{v}_{t-1}-\mathbf{e}^T\Delta\mathbf{v}_t}{\Delta\mathbf{v}_t\mathbf{Q}\Delta\mathbf{v}_t}$; $\boldsymbol{\alpha}_t\leftarrow\mathbf{v}_{t-1}-\gamma_{\mathbf{v}}\Delta\mathbf{v}_t$; \\
\Repeat{$\forall i, 0\leq\alpha_{t,i}\leq C, \mathbf{y}^T\boldsymbol{\alpha}_t=0$}
{
$\forall i, \alpha_{t,i}\leftarrow\max\{0,\min\{C,v_{t,i}\}\}$;
$\boldsymbol{\alpha}_t\leftarrow\boldsymbol{\alpha}_t-\left(\frac{\mathbf{y}^T\boldsymbol{\alpha}_t}{\|\mathbf{y}\|_1}\right)\mathbf{y}$;
}
$\theta_t\leftarrow\min\{\frac{C}{\max_i\alpha_{t,i}},\frac{\mathbf{e}^T\boldsymbol{\alpha}_t}{\boldsymbol{\alpha}_t^T\mathbf{Q}\boldsymbol{\alpha}_t}\}$; $\eta_t=\frac{\sqrt{\eta_{t-1}^4+4\eta_{t-1}^2}-\eta_{t-1}^2}{2}$; Update $\mathbf{v}_t$ using either Eq. \ref{eqn:rapid-1} or Eq. \ref{eqn:rapid-2};
}
\Return $\boldsymbol{\alpha}\leftarrow\theta_t\boldsymbol{\alpha}_t$\;
\caption{RAPID-SVMs}\label{alg:rapid-svm}
\end{algorithm}

With RAPID, Eq. \ref{eqn:binary-svms} can be solved using Alg. \ref{alg:rapid-svm}, where each iteration contains the following 5 steps:
\begin{itemize}
\item[Step 1:] Perform line search for the step size $\gamma_{\mathbf{v}}$ in gradient descent by ignoring the constraints.
\item[Step 2:] Update $\boldsymbol{\alpha}_t$ using gradient descent with $\Delta\mathbf{v}_t$ and learned $\gamma_{\mathbf{v}}$.
\item[Step 3:] Alternatively project $\boldsymbol{\alpha}_t$ into one constraint set while fixing the other until both are satisfied.
\item[Step 4:] Update $\theta_t$ with guarantee that $\theta_t\boldsymbol{\alpha}_t$ satisfies the constraints.
\item[Step 5:] Update the auxiliary variable $\mathbf{v}_t$ as the same as in Alg. \ref{alg:rapid}.
\end{itemize}
Alg. \ref{alg:rapid-svm} can be adapted to an APG solver by fixing $\theta_t=1$ and using the update rule in FISTA for $\mathbf{v}_t$.

\subsubsection{Experimental Results}
\begin{figure}[htbp]
\begin{minipage}[b]{0.33\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=\columnwidth]{svm0.png}}
 \centerline{\footnotesize{(a)}}
 \end{center}
\end{minipage}

\begin{minipage}[b]{0.33\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=\columnwidth]{svm1.png}}
 \centerline{\footnotesize{(b)}}
 \end{center}
\end{minipage}

\begin{minipage}[b]{0.33\linewidth}
 \begin{center}
 \centerline{\includegraphics[width=\columnwidth]{svm2.png}}
 \centerline{\footnotesize{(c)}}
 \end{center}
\end{minipage}\vspace{-4mm}
\caption{\footnotesize{Empirical convergence rate comparison using covtype data for SVMs.}}\label{fig:svm-comparison}

\end{figure}

We test and compare our RAPID-SVMs on the binary {\it covtype} dataset \cite{conf/nips/CollobertBB01}. This dataset contains 581012 samples with 54 dimensions per sample. Duo to the memory issue, we randomly select 5\% data as training and use the rest data as testing. For simplicity, we utilize linear kernels for creating $\mathbf{K}$, and solve Eq. \ref{eqn:binary-svms} with $C$ equal to one of $\{0.1, 1, 10\}$.

Our results are shown in Fig. \ref{fig:svm-comparison}, where RAPID is compared with APG and another popular SVM solver, LIBSVM \cite{CC01a}. The stop criterion for both RAPID is to check whether $1-\frac{\min\{|f(\theta_{t-1}\mathbf{x}_{t-1})|,|f(\theta_t\mathbf{x}_t)|\}}{\max\{|f(\theta_{t-1}\mathbf{x}_{t-1})|,|f(\theta_t\mathbf{x}_t)|\}}\leq 10^{-7}$ is satisfied. Similarly, for APG, $1-\frac{\min\{|f(\mathbf{x}_{t-1})|,|f(\mathbf{x}_t)|\}}{\max\{|f(\mathbf{x}_{t-1})|,|f(\mathbf{x}_t)|\}}\leq 10^{-7}$ is checked. For LIBSVM we use its default settings. As we see, in all these three cases RAPID converges significantly faster than APG. With the increase of $C$, RAPID begins to fluctuate. However, we can easily control this by checking the objective value in each iteration to ensure it will not increase. If increasing, the solution will not be updated. We will add this feature in our implementation in the future. Compared with LIBSVM, when $C=0.1$ or $C=1$, RAPID converges better, resulting in slightly better classification accuracies, while for $C=10$, RAPID performs worse, since it does not converge yet. Still, RAPID-II performs better than RAPID-I in all the cases.

\section{Algorithm Analysis}\label{sec:analysis}
In this section, we present our main theoretical results on the convergence rate of our RAPID algorithm in Theorem \ref{thm:rapid-1} and \ref{thm:rapid-2}, which is clearly better than those of conventional APG methods such as FISTA, leading to faster convergence in practice.

\begin{lemma}[Sandwich \cite{Baldassarre}]\label{lem:Sandwich}
Let $\tilde{f}$ be the linear approximation of $f$ in $\mathbf{v}$ \wrt $f_1$, \ie $\tilde{f}(\mathbf{w};\mathbf{v})=f_1(\mathbf{v})+\langle\triangledown f(\mathbf{v}), \mathbf{w}-\mathbf{v}\rangle+f_2(\mathbf{w})$, where $\langle\cdot,\cdot\rangle$ denotes the inner product between two vectors. Then
\begin{equation}
f(\mathbf{w})\leq\tilde{f}(\mathbf{w};\mathbf{v})+\frac{L}{2}\|\mathbf{w}-\mathbf{v}\|_2^2\leq f(\mathbf{w})+\frac{L}{2}\|\mathbf{w}-\mathbf{v}\|_2^2.
\end{equation}
\end{lemma}

\begin{lemma}[3-Point Property \cite{Baldassarre}]\label{lem:3-point}
If $\hat{\mathbf{w}}=\argmin_{\mathbf{w}\in\mathbb{R}^d}\frac{1}{2}\|\mathbf{w}-\mathbf{w}_0\|_2^2+\phi(\mathbf{w})$, then for any $\mathbf{w}\in\mathbb{R}^d$,
\begin{equation}
\phi(\hat{\mathbf{w}})+\frac{1}{2}\|\hat{\mathbf{w}}-\mathbf{w}_0\|_2^2\leq\phi(\mathbf{w})+\frac{1}{2}\|\mathbf{w}-\mathbf{w}_0\|_2^2-\frac{1}{2}\|\mathbf{w}-\hat{\mathbf{w}}\|_2^2.
\end{equation}
\end{lemma}

\begin{lemma}
In Alg. \ref{alg:rapid}, at an arbitrary iteration $t$, we have
\begin{equation}\label{eqn:2-terms-theta}
f(\theta_t\mathbf{x}_t)\leq f(\mathbf{x}_t)-\frac{1}{2\lambda_{\theta}}\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2.
\end{equation}
\end{lemma}
\begin{proof}\footnotesize
Clearly, the definition of $\theta_t$ in Alg. \ref{alg:rapid} satisfies the condition in Lemma \ref{lem:3-point}. Therefore, we have:
\begin{eqnarray}
f(\theta_t\mathbf{x}_t)&\leq& f(\theta_t\mathbf{x}_t)+\frac{1}{2\lambda_{\theta}}\|\theta_t\mathbf{x}_t-\mathbf{x}_t\|_2^2 \\
&\leq& \min_{\theta_t^*}\left\{f(\theta_t^*\mathbf{x}_t)+\frac{1}{2\lambda_{\theta}}\left(\|\theta_t^*\mathbf{x}_t-\mathbf{x}_t\|_2^2-\|\theta_t^*\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2\right)\right\} \,\Leftarrow (\mbox{Lemma}\, \ref{lem:3-point})\nonumber\\
&\leq& f(\mathbf{x}_t)-\frac{1}{2\lambda_{\theta}}\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2.\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\Leftarrow (\theta_t^*=1)\nonumber
\end{eqnarray}
\end{proof}

\begin{thm}\label{thm:rapid-1}
Let $\mathbf{x}^*=\argmin_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})$ and $\lambda_{\theta}=\frac{1}{L}$. If Alg. \ref{alg:rapid} updates $\mathbf{v}_t$ using Eq. \ref{eqn:rapid-1}, in iteration $T (\forall  T\geq1)$ in Alg. \ref{alg:rapid}, we have
\begin{equation}
f(\theta_T\mathbf{x}_T)-f(\mathbf{x}^*)\leq\frac{2L}{(T+1)^2}\left[\|\mathbf{x}^*-\mathbf{z}_0\|_2^2-\sum_{t=1}^{T}\frac{\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2}{\eta_{t-1}^2}\right],
\end{equation}
where $\mathbf{z}_0$ is a constant.
\end{thm}
\begin{proof}\footnotesize
Since $\mathbf{x}_{t+1}$ satisfies the conditions in Lemma \ref{lem:Sandwich} and Lemma \ref{lem:3-point}, we have:
\begin{eqnarray}\label{eqn:2-terms-x}
f(\mathbf{x}_{t+1})&\leq& \tilde{f}(\mathbf{x}_{t+1};\mathbf{v}_{t})+\frac{L}{2}\|\mathbf{x}_{t+1}-\mathbf{v}_{t}\|_2^2 \leq \tilde{f}(\mathbf{v}_{t}^*;\mathbf{v}_{t})+\frac{L}{2}\left(\|\mathbf{v}_{t}^*-\mathbf{v}_{t}\|_2^2-\|\mathbf{v}_{t}^*-\mathbf{x}_{t+1}\|_2^2\right)\nonumber\\
&=&\tilde{f}(\mathbf{v}_t^*; \mathbf{v}_t)+\frac{L\eta_t^2}{2}\left(\|\mathbf{x}^*-\mathbf{z}_t\|_2^2-\|\mathbf{x}^*-\mathbf{z}_{t+1}\|_2^2\right),
\end{eqnarray}
where $\mathbf{v}_{t}^*=(1-\eta_{t})\theta_t\mathbf{x}_t+\eta_{t}\mathbf{x}^*$, and $\mathbf{z}_{t+1}=\theta_{t}\mathbf{x}_t+\eta_{t}^{-1}(\mathbf{x}_{t+1}-\theta_t\mathbf{x}_t)$. Due to the convexity of $\tilde{f}$, we can rewrite Eq. \ref{eqn:2-terms-x} as follows:
\begin{eqnarray}\label{eqn:theta_tx}
f(\mathbf{x}_{t+1})&\leq&(1-\eta_t)\tilde{f}(\theta_t\mathbf{x}_t;\mathbf{v}_t)+\eta_t\tilde{f}(\mathbf{x}^*;\mathbf{v}_t)+\frac{L\eta_t^2}{2}\left(\|\mathbf{x}^*-\mathbf{z}_t\|_2^2-\|\mathbf{x}^*-\mathbf{z}_{t+1}\|_2^2\right)\nonumber\\
&\leq&(1-\eta_t)f(\theta_t\mathbf{x}_t)+\eta_t f(\mathbf{x}^*)+\frac{L\eta_t^2}{2}\left(\|\mathbf{x}^*-\mathbf{z}_t\|_2^2-\|\mathbf{x}^*-\mathbf{z}_{t+1}\|_2^2\right).
\end{eqnarray}
Based on Eq. \ref{eqn:2-terms-theta} and \ref{eqn:theta_tx}, we have:
\begin{equation}\label{eqn:key}
f(\theta_{t+1}\mathbf{x}_{t+1})\leq(1-\eta_t)f(\theta_t\mathbf{x}_t)+\eta_t f(\mathbf{x}^*)+\frac{L\eta_t^2}{2}\left(\|\mathbf{x}^*-\mathbf{z}_t\|_2^2-\|\mathbf{x}^*-\mathbf{z}_{t+1}\|_2^2\right)-\frac{L}{2}\|\mathbf{x}_{t+1}-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2.
\end{equation}
Letting $\epsilon_t=f(\theta_t\mathbf{x}_t)-f(\mathbf{x}^*)$ and $\Phi_t=\frac{L}{2}\|\mathbf{x}^*-\mathbf{z}_t\|_2^2$, we can rewrite Eq. \ref{eqn:key} as follows:
\begin{eqnarray}
&&\epsilon_{t+1}\leq(1-\eta_t)\epsilon_t+\eta_t^2(\Phi_t-\Phi_{t+1})-\frac{L}{2}\|\mathbf{x}_{t+1}-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2\\
&\Leftrightarrow& \frac{1}{\eta_t^2}\epsilon_{t+1}-\frac{1-\eta_t}{\eta_t^2}\epsilon_t\leq\Phi_t-\Phi_{t+1}-\frac{L}{2\eta_t^2}\|\mathbf{x}_{t+1}-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2\nonumber
\end{eqnarray}
$\because$ the sequence $\{\eta_t\}_{t=0,1,\cdots}$ in Alg. \ref{alg:rapid} satisfies $\forall t, \frac{1-\eta_{t+1}}{\eta_{t+1}^2}=\frac{1}{\eta_t^2}$, $\therefore \frac{1-\eta_{t+1}}{\eta_{t+1}^2}\epsilon_{t+1}=\frac{1}{\eta_{t}^2}\epsilon_{t+1}$, leading to
\begin{eqnarray}
\frac{1-\eta_{t+1}}{\eta_{t+1}^2}\epsilon_{t+1}-\frac{1-\eta_t}{\eta_t^2}\epsilon_t\leq\Phi_t-\Phi_{t+1}-\frac{L}{2\eta_t^2}\|\mathbf{x}_{t+1}-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2.
\end{eqnarray}
Letting $g_t=\frac{1-\eta_t}{\eta_t^2}\epsilon_t$, we have $g_0=0$ and
\begin{eqnarray}\label{eqn:deduction}
\lefteqn{\hspace{-16mm}\forall T\geq1, \, \sum_{t=0}^{T-1}\left(g_{t+1}-g_t\right)=g_T-g_0=\frac{\epsilon_T}{\eta_{T-1}^2}\leq\sum_{t=0}^{T-1}\left(\Phi_t-\Phi_{t+1}\right)-\frac{L}{2}\sum_{t=0}^{T-1}\frac{\|\mathbf{x}_{t+1}-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2}{\eta_t^2}}\nonumber\\
&& \leq\Phi_0-\frac{L}{2}\sum_{t=1}^{T}\frac{\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2}{\eta_{t-1}^2}=\frac{L}{2}\|\mathbf{x}^*-\mathbf{z}_0\|_2^2-\frac{L}{2}\sum_{t=1}^{T}\frac{\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2}{\eta_{t-1}^2}.
\end{eqnarray}
Since the sequence $\{\eta_t\}_{t=0,1,\cdots}$ also satisfies $\eta_t\leq \frac{2}{t+2}$, based on Eq. \ref{eqn:deduction} we have $\frac{\epsilon_T(T+1)^2}{4}\leq\frac{\epsilon_T}{\eta_{T-1}^2}$. Therefore,
\begin{eqnarray}\label{eqn:conclusion}
\epsilon_T\leq\frac{2L}{(T+1)^2}\left[\|\mathbf{x}^*-\mathbf{z}_0\|_2^2-\sum_{t=1}^{T}\frac{\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2}{\eta_{t-1}^2}\right].
\end{eqnarray}
\end{proof}

\begin{thm}\label{thm:rapid-2}
Let $\mathbf{x}^*=\argmin_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x})$ and $\lambda_{\theta}=\frac{1}{L}$. If Alg. \ref{alg:rapid} updates $\mathbf{v}_t$ using Eq. \ref{eqn:rapid-2}, and suppose in any iteration $t (t\geq1)$,  $\mathbf{v}_t^*=(1-\eta_t)\theta_t\mathbf{x}_t+\eta_t\mathbf{x}^*$ and $\|\mathbf{v}_t^*-\mathbf{x}_{t+1}\|_2^2=\|\mathbf{v}_t^*-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2+\xi_{t+1}$, then in iteration $T (\forall T\geq1)$ we have
\begin{equation}
f(\theta_T\mathbf{x}_T)-f(\mathbf{x}^*)\leq\frac{2L}{(T+1)^2}\left[\|\mathbf{x}^*-\mathbf{z}_0\|_2^2-\sum_{t=1}^{T}\left(\frac{\|\mathbf{x}_t-\theta_t\mathbf{x}_t\|_2^2}{\eta_{t-1}^2}+\xi_t\right)\right],
\end{equation}
where $\mathbf{z}_0$ is a constant.
\end{thm}
\begin{proof}\footnotesize
Based on the assumptions of the theorem and Eq. \ref{eqn:2-terms-x}, we have
\begin{eqnarray}\label{eqn:2-terms-x-2}
f(\mathbf{x}_{t+1})
&\leq& \tilde{f}(\mathbf{v}_{t}^*;\mathbf{v}_{t})+\frac{L}{2}\left(\|\mathbf{v}_{t}^*-\mathbf{v}_{t}\|_2^2-\|\mathbf{v}_{t}^*-\mathbf{x}_{t+1}\|_2^2\right)\nonumber\\
&=& \tilde{f}(\mathbf{v}_{t}^*;\mathbf{v}_{t})+\frac{L}{2}\left(\|\mathbf{v}_{t}^*-\mathbf{v}_{t}\|_2^2-\|\mathbf{v}_{t}^*-\theta_{t+1}\mathbf{x}_{t+1}\|_2^2-\xi_{t+1}\right)\nonumber\\
&=&\tilde{f}(\mathbf{v}_t^*; \mathbf{v}_t)+\frac{L\eta_t^2}{2}\left(\|\mathbf{x}^*-\mathbf{z}_t\|_2^2-\|\mathbf{x}^*-\mathbf{z}_{t+1}\|_2^2-\xi_{t+1}\right),
\end{eqnarray}
where $\mathbf{z}_{t+1}=\theta_{t}\mathbf{x}_t+\eta_{t}^{-1}(\theta_{t+1}\mathbf{x}_{t+1}-\theta_t\mathbf{x}_t)$. Following the same proof strategy for Theorem \ref{thm:rapid-1}, we can easily prove this theorem.
\end{proof}

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

In this paper, we propose an improved APG algorithm, namely, Rapidly Accelerated Proximal Gradient (RAPID), to speed up the convergence of conventional APG algorithms. Our first idea is to introduce a new line search step after the proximal gradient step in APG to push the current solution $\mathbf{x}_t$ towards a new one $\theta\mathbf{x}_t\in\mathcal{X} (\theta>0)$ so that $f(\theta\mathbf{x}_t)$ is minimized over scalar $\theta$. Our second idea is to propose two different ways of constructing the auxiliary variable in APG using the intermediate solutions in the previous and current iterations. In this way, we can prove that our algorithm is guaranteed to converge with a smaller upper bound of the gap between the current and optimal objective values than those in APG algorithms. We demonstrate our algorithm using two applications, \ie sparse linear regression and kernel SVMs. In summary, our RAPID converges faster than APG, in general, and for some problems RAPID based algorithms can be comparable with the sophisticated existing solvers.

\bibliographystyle{ieee}
\bibliography{egbib}

\end{document}


TITLE: Question about the degree of the inverse of a polynomial $p(x)$ modulo $q(x)$
QUESTION [1 upvotes]: I have a doubt about the modular inverse polynomial degree.
Let $p(X)$ be a polynomial in the ring $F[X]$ with $\deg(p)=\delta$, where $F$ is a finite field with characteristic 2. If $\gcd(p(X),q(X)) = 1$, what is the degree of the inverse polynomial of $p(X)$ modulo $q(X)$?
Thanks for your replies.

REPLY [1 votes]: If you take a Bezout relation in $F[X]$
$$u(X)p(X)+v(X)q(X)=1$$
the inverse of $p(X)$ modulo $q(X)$ is $u(X)$. Now i don't really understand what you mean by the "degree" of the inverse, but if you want the degree of an inverse which is of degree lesser than $\deg(q)$, you should just work out this Bezout relation and see that it gives $\deg(u)+\deg(p)=\deg(v)+\deg(q)$ as long as $q$ is not trivial.


TITLE: Field extension of fixed field has degree greater than the size of the group
QUESTION [2 upvotes]: Let $K$ be a field, $G\leqslant\mathrm{Aut}(K)$ a (finite) group, and $K^G$ the fixed subfield of $K$.
How exactly would you go about proving the following?$$[K:K^G]\geqslant|G|$$
For some reason I have come to a complete blank trying to even start on this!
I would much prefer some hints to a complete solution, but either is appreciated.
Edit:
Sorry, just saw that this hint is at the bottom of the question:
You may assume that if $\sigma_1,\ldots,\sigma_n$ are distinct field homomorphisms from $K$ to $L$ then $\{\sigma_1,\ldots,\sigma_n\}$ is linearly independent over $L$.

REPLY [2 votes]: I abbreviate $F=K^G$. Let $n=[K:F]$. Consider the set $V$ of $F$-linear mappings from $K$ to itself. The $V$ has the usual structure of a vector space over $F$, and clearly has dimension $n^2$, after all $V$ is isomorphic to the space of $n\times n$ matrices over $F$.
But $V$ also has a structure of a vector space over $K$. Just multiply the values by scalars from $K$ instead of restricting yourself to $F$ (this works only because the range, here $K$, already has multiplication by elements of $K$ defined.
What is the dimension of $V$ as a vector space over $K$? Call it $m$. The same argument that you have seen when proving the product formula in a tower of field extensions shows that
$$
n^2=\dim_FV=[K:F]\dim_KV=nm.
$$
This implies that $m=n$.
It sounds like you want to think about the rest (great!), so I spoilerize the rest (mouseover the pale pink block to see the text).

 The Lemma in your hint exhibits a set of $|G|$ elements of $V$ that are linearly independent over $K$. Basic linear algebra tells us that the size of a linearly independent set is bounded from above by the dimension of the space. Therefore

$$
|G|\le \dim_KV=n=[K:F].
$$
Q.E.D.


text:
\section{Problem Formulation}\label{sec:pf}\vspace{-.2cm}
In this section, we  introduce the background of MARL, which is modeled as a multi-agent Markov decision process (MDP). Under this model, we formulate the policy evaluation problem as a primal-dual convex-concave optimization problem.

\textbf{Multi-agent MDP}~~Consider a group of $N$ agents.
We are interested in the multi-agent MDP:
\begin{align*}
\big(  {\cal S} , \{ {\cal A}_i \}_{i = 1}^N, {\cal P}^{\bm a}, \{ {\cal R}_i \}_{i=1}^N, \gamma \big) \eqs,
\end{align*}
where ${\cal S} $ is the state space and ${\cal A}_i$
is the action space for agent $i$. We write
${\bm s} \in {\cal S}$
and ${\bm a} \eqdef (a_1,...,a_N) \in {\cal A}_1 \times \cdots \times {\cal A}_N$
as the joint state and action, respectively.
The function ${\cal R}_i ({\bm s}, {\bm a})$ is the
local reward received by agent $i$
after taking joint action
${\bm a}$ at state ${\bm s} $, and  $\gamma \in (0,1)$ is the discount factor.
Both ${\bm s}$ and ${\bm a}$ are available to all agents, whereas the reward ${\cal R}_i$ is  {\it private} for agent $i$.

In contrast to a single-agent MDP, the agents are coupled
together by the state transition matrix
${\cal P}^{\bm a} \in \RR^{   |{\cal S}|
\times  |{\cal S}| }$, whose $({\bm s}, {\bm s}')$-th element
is the probability of transiting from ${\bm s}$ to ${\bm s}'$,
 after taking a  joint action  ${\bm a}$.
This scenario arises from large-scale applications such as sensor networks \citep{rabbat2004distributed, cortes2004coverage}, swarm robotics \citep{kober2012reinforcement, corke2005networked}, and power grids \citep{callaway2011achieving, dall2013distributed}, which strongly motivates the development of a multi-agent RL strategy.
Moreover,  under the collaborative setting, the goal is to maximize the collective return of all agents.  Suppose there exists a central controller that collects the rewards of, and assigns the action to  each individual agent, the problem reduces to the classical MDP with action space $\cal A$ and global reward function $R_c ({\bm s}, {\bm a} ) = N^{-1} \sum_{i=1}^N {\cal R}_i ({\bm s}, {\bm a})$.  Thus, without such a central controller, it is essential for the agents to collaborate with each other so as to solve the multi-agent problem based solely on  local information.

Furthermore, a joint policy, denoted by $\bm{\pi}$, specifies the rule of making sequential decisions for the agents.  Specifically, $\bm{\pi} ( {\bm a} | {\bm s}  )$ is the  conditional probability of taking joint action ${\bm a} $ given the
current state ${\bm s} $.
We define the reward function of joint policy $\bm{\pi}  $  as an average of the local rewards:
\beq \label{eq:reward} \textstyle
R_c^{\bm{\pi}} ( {\bm s} ) \eqdef \frac{1}{N} \sum_{i=1}^N R_i^{\bm \pi} ({\bm s} ), \qquad \text{where}~~
R_i^{{\bm \pi }} ({\bm s} )  \eqdef
\EE_{ {\bm a} \sim {\bm \pi} ( \cdot | {\bm s}  ) } \big[  {\cal R}_i ( {\bm s}, {\bm a} ) \big] \eqs.
\eeq
That is, $R_c^{\bm {\pi}}({\bm s} )  $ is the expected value of the average of the rewards when the agents follow policy ${\bm \pi}$ at state ${\bm s}$.
Besides,  any fixed policy ${\bm \pi}$ induces a Markov chain over $\cal S$, whose transition matrix is  denoted by ${\bm P} ^{\bm \pi}$.  The $({\bm s}, {\bm s}')$-th element  of ${\bm P} ^{\bm \pi}$ is given by
\begin{align*} \textstyle
[ {\bm P} ^{\bm \pi}]_{{\bm s}, {\bm s}' }  = \sum_{{\bm a} \in {\cal A} }  {\bm \pi }({\bm a}  | {\bm s} ) \cdot [ {\cal P}^{\bm a} ]_{{\bm s}, {\bm s}' } .
\end{align*}
When this Markov chain is aperiodic and irreducible, it induces a stationary distribution $\mu^{\bm \pi}$  over $\cal S$.

\textbf{Policy Evaluation}~~
A central problem in reinforcement learning is \emph{policy evaluation}, which refers to learning the \emph{value function} of a given policy.
This problem appears as a key component in both value-based methods such as policy iteration, and policy-based methods such as actor-critic algorithms \citep{sutton1998reinforcement}.
Thus, efficient estimation of  the value functions in  multi-agent MDPs enables us to extend the successful approaches in single-agent RL to the setting of MARL.

Specifically,
for any given joint policy $\bm{\pi}$, the value function of ${\bm \pi} $, denoted by $V^{\bm{\pi}} \colon \cal S\rightarrow \RR$, is defined as the expected value of the discounted cumulative reward when the  multi-agent MDP is  initialized with a given state and the agents follows policy ${\bm \pi}$ afterwards. For any state
 ${\bm s} \in \cal S$, we define
\beq \label{eq:loc_reward} \textstyle
V^{\bm{\pi}} ( {\bm s} ) \eqdef \EE\Big[ \sum_{p=1}^\infty \gamma^p {\cal R}_c^{\bm{\pi}} ( {\bm s}_p ) \!~ | \!~
{\bm s}_1 = {\bm s} , \bm{\pi} \Big] \eqs.

\eeq
To simplify the notation, we define the  vector ${\bm V}^{\bm{\pi}} \in \RR^{|\cal S| } $
through stacking up $V^{\bm{\pi}} ( {\bm s} )$  in \eqref{eq:loc_reward} for all ${\bm s}$.
By definition, $V^{\bm {\pi}}$ satisfies the  Bellman equation
\beq\label{eq:bellman}
{\bm V}^{\bm{\pi}} = {\bm R}_c^{\bm{\pi}} + \gamma {\bm P}^{\bm{\pi}} {\bm V}^{\bm{\pi}} \eqs,
\eeq
where
${\bm R}_c^{\bm{\pi}}$ is obtained by stacking up

\eqref{eq:reward}
and $[ {\bm P}^{\bm{\pi}} ]_{ {\bm s}, {\bm s}' } \eqdef
\EE_{ \bm{\pi} } [ {\cal P}_{{\bm s}, {\bm s}'}^{ {\bm a} } ]$
is the expected transition matrix.  Moreover, it can be shown that ${\bm V}^{\bm {\pi}}$ is the unique solution of \eqref{eq:bellman}.

When the number of states is large, it is impossible to store ${\bm V}^{\bm {\pi}}$. Instead,
our goal  is to learn an approximate version of the value function via function approximation.
In specific,  we  approximate ${V}^{\bm{\pi}}({\bm s})$ using the family of  linear functions
\begin{align*}
\bigl \{ V_{\prm} ( {\bm s} ) \eqdef \bm{\phi}^\top ( {\bm s} ) \prm \colon \prm \in \RR^d \} ,
\end{align*}
where $\prm \in \RR^d$ is the parameter, $\bm{\phi} ( {\bm s} ) \colon {\cal S} \rightarrow \RR^d$ is a known dictionary consisting of $d$ features, e.g., a feature mapping induced by a neural network.
To simplify the notation, we
 define  $\bm{\Phi} \eqdef ( ... ; \bm{\phi}^\top ( {\bm s} ); ... ) \in \RR^{|  {\cal S} | \times d} $ and let ${\bm V} _{\prm} \in \RR^{|\cal S|} $ be the vector constructed by stacking up $\{ V_{\prm}({\bm s}) \}_{{\bm s} \in {\cal S} } $.

With function approximation,  our problem is reduced to finding a
$\prm \in \RR^d$ such that ${\bm V}_{\prm} \approx {\bm V}^{\bm \pi}$.  Specifically, we seek for $\prm$
such that the mean squared projected Bellman error (MSPBE)
\begin{align} \label{eq:mspbe}
{\sf MSPBE}^\star ( \prm )  & \eqdef \frac{1}{2} \Big \| {\bm \Pi}_{\bm{\Phi}} \Bigl  (
{\bm V}_{\prm} - \gamma {\bm P}^{\bm{\pi}}  {\bm V}_{\prm}
- {\bm R}_c^{\bm{\pi}} \Big ) \Big\|_{ {\bm D} }^2  +\rho \| \prm \|^2
 \end{align}
is minimized,
where ${\bm D} = \text{diag} [ \{ \mu^{\bm \pi}({\bm s}) \}_{{\bm s} \in {\cal S} } ]  \in \RR^{ |{  \cal S} | \times | {\cal S} | } $ is a diagonal matrix constructed using the stationary
distribution of ${\bm \pi}$, $ {\bm \Pi}_{\bm{\Phi}} \colon \RR^{| {\cal S} | } \rightarrow \RR^{| {\cal S} | } $ is the projection onto subspace $\{ \bm{\Phi} \prm \colon \prm \in \RR^d \}$,
defined as ${\bm \Pi}_{\bm{\Phi}} = \bm{\Phi} ( \bm{\Phi}^\top {\bm D} \bm{\Phi} )^{-1} \bm{\Phi}^\top {\bm D}$,
and $\rho \geq 0$ is a free
parameter controlling the regularization on $\prm$.

For any positive semidefinite matrix ${\bm A} $, we define  $\| {\bm v} \|_{\bm A} = \sqrt{ {\bm v} ^\top {\bm A} {\bm v} } $ for any vector ${\bm v}$. By direct computation, when  $\bm{\Phi}^\top {\bm D} \bm{\Phi}$ is invertible,  the MSPBE defined  in \eqref{eq:mspbe}  can be written as
\beq\label{eq:population_mspbe}
 {\sf MSPBE}^\star ( \prm )  = \frac{1}{2} \Big\| \bm{\Phi}^\top {\bm D} \Big(
{\bm V}_{\prm} - \gamma {\bm P}^{\bm{\pi}}  {\bm V}_{\prm}
- {\bm R}_c^{\bm{\pi}} \Big) \Big\|_{ (\bm{\Phi}^\top {\bm D} \bm{\Phi})^{-1} }^2
+ \rho \| \prm \|^2  \eqs =  \frac{1}{2} \Big\| {\bm A} \prm - {\bm b} \Big\|_{ {\bm C}^{-1} }^2 + \rho \| \prm \| ^2 ,
\eeq
where we define

${\bm A} \eqdef \EE \big[ \bm{\phi} ( {\bm s}_p ) \big( \bm{\phi} ( {\bm s}_p ) - \gamma \bm{\phi} ( {\bm s}_{p+1} ) \big)^\top \big],$ ${\bm C} \eqdef \EE \big[ \bm{\phi} ( {\bm s}_p ) \bm{\phi}^\top ( {\bm s}_p ) \big],$ and $ {\bm b} \eqdef \EE \big[
{\cal R}_c^{\bm{\pi}} ( {\bm s}_p ) \bm{\phi} ( {\bm s}_p ) \big]$.  Here  the expectations  in ${\bm A},$ ${\bm b}$, and ${\bm C}$ are all taken with respect to (\wrt) the stationary distribution $\mu^{\bm \pi}$.
Furthermore, when ${\bm A}$  is full rank and ${\bm C}$ is positive definite, it can be shown that the MSPBE in \eqref{eq:population_mspbe} has a unique minimizer.

To obtain a practical optimization problem,  we replace  the expectations above by  their sampled averages from $M$ samples. In specific, for a given policy $\bm{\pi}$,
a finite state-action sequence
$\{ {\bm s}_p, {\bm a}_p \}_{p=1}^{M}$ is simulated from the multi-agent
MDP using  joint policy ${\bm \pi}$. We also observe  ${\bm s}_{M+1}$, the next state of ${\bm s}_{M}$.
Then we construct the sampled versions of ${\bm A}$, ${\bm b}$, ${\bm C}$, denoted respectively by $\hat{\bm A}$, $\hat{\bm C}$, $\hat{\bm b}$, as
\beq\label{eq:empirical_matrices}
\begin{split}
& \textstyle  \hat{\bm A} \eqdef
\frac{1}{M} \sum_{p=1}^{M} {\bm A}_p,~

\hat{\bm C} \eqdef \frac{1}{M} \sum_{p=1}^{M} {\bm C}_p,~

\hat{\bm b} \eqdef \frac{1}{M} \sum_{p=1}^{M} {\bm b}_p,~~\text{with} \\

&
{\bm A}_p \eqdef \bm{\phi} ( {\bm s}_p ) \big( \bm{\phi} ( {\bm s}_p ) - \gamma \bm{\phi} ( {\bm s}_{p+1} ) \big)^\top,~
{\bm C}_p \eqdef \bm{\phi} ( {\bm s}_p ) \bm{\phi}^\top ( {\bm s}_p ),~
{\bm b}_p \eqdef {\cal R}_c ( {\bm s}_p, {\bm a}_p ) \bm{\phi} ( {\bm s}_p ) \eqs,
\end{split}
\eeq
where
${\cal R}_c ( {\bm s}_p, {\bm a}_p ) \eqdef N^{-1} \sum_{i=1}^N {\cal R}_i( {\bm s}_p, {\bm a}_p)$ is the average of the local rewards received by each agent when taking action ${\bm a}_p$ at state ${\bm s}_p$. Here we assume that $M$ is sufficiently large such that $\hat {\bm C}$ is invertible and $\hat {\bm A}$ is full rank. Using the terms defined in \eqref{eq:empirical_matrices}, we obtain the empirical MSPBE
\beq\label{eqMSPBE2}
{\sf MSPBE} ( \prm ) \eqdef  \frac{1}{2} \Big\| \hat{\bm A} \prm - \hat{\bm b} \Big\|_{ \hat{\bm C}^{-1} }^2 + \rho \| \prm \| ^2  \eqs,
\eeq
which converges to $  {\sf MSPBE}^\star ( \prm )$ as $M \rightarrow \infty$.
Let $\hat \prm$ be a minimizer of the empirical MSPBE, our estimation of ${\bm V}^{\bm \pi}$ is given by $ {\bm \Phi} \hat \prm$. Since the rewards $ \{ {\cal R}_i ( {\bm s}_p, {\bm a}_p) \}_{i=1}^N $  are  private to each agent, it is impossible for any agent to  compute $ {\cal R}_c ( {\bm s}_p, {\bm a}_p ) $,
and minimize the empirical MSPBE \eqref{eqMSPBE2} independently.

\textbf{Multi-agent, Primal-dual, Finite-sum Optimization}~~
Recall that under the multi-agent MDP, the agents are able to observe the states and the joint actions, but can only observe their local rewards. Thus, each agent is able to compute $\hat {\bm A}$ and $\hat {\bm C}$ defined in \eqref{eq:empirical_matrices}, but is unable to obtain $\hat {\bm b}$. To resolve this issue, for any $i\in \{ 1, \ldots, N\}$ and any $p \in \{ 1, \ldots, M \}$, we define
${\bm b}_{p,i} \eqdef {\cal R}_i ( {\bm s}_p, {\bm a}_p ) \bm{\phi} ( {\bm s}_p )$ and $\hat{\bm b}_i \eqdef M^{-1} \sum_{p=1}^{M} {\bm b}_{p,i}$, which  are   known
to agent $i$ only.
By direct computation, it  is easy to verify that
minimizing ${\sf MSPBE}(\prm)$ in \eqref{eqMSPBE2} is equivalent to solving
\beq \label{eq:prob}
\min_{\prm \in \RR^d} ~\frac{1}{N} \sum_{i=1}^N {\sf MSPBE}_i( \prm ) ~~ \text{where}~~
{\sf MSPBE}_i ( \prm ) \eqdef \frac{1}{2} \Big\| \hat{\bm A} \prm - \hat{\bm b}_i \Big\|_{ \hat{\bm C}^{-1} }^2 + \rho \| \prm \|^2 \eqs.
\eeq
The equivalence  can be seen  by comparing the optimality conditions of  two optimization problems.

Importantly, \eqref{eq:prob} is a
\emph{multi-agent optimization
problems} \citep{nedic2009distributed} whose objective is to minimize a summation of $N$ local functions
coupled together by the common parameter $\prm$.
Here ${\sf MSPBE}_i ( \prm ) $ is private to agent $i$ and the parameter $\prm$ is shared by all agents.
As inspired by \citep{nedic2003least, liu2015finite, du2017stochastic}, using Fenchel duality, we obtain  the conjugate form
of ${\sf MSPBE}_i(\prm)$, \ie
\beq\label{eq:fenchel}
\frac{1}{2} \Big\| \hat{\bm A} \prm - \hat{\bm b}_i \Big\|_{ \hat{\bm C}^{-1} }^2 +  \rho \| \prm \|^2   =
\max_{ {\bm w}_i \in \RR^d } \Big( {\bm w}_i^\top \big( \hat{\bm A} \prm - \hat{\bm b}_i \big)
- \frac{1}{2}  {\bm w}_i^\top \hat{\bm C} {\bm w}_i  \Big) +  \rho \| \prm \|^2  \eqs.

\eeq

Observe that each of $\hat{\bm A}, \hat{\bm C}, \hat{\bm b}_i$ can be expressed as
a finite sum of matrices/vectors. By \eqref{eq:fenchel}, problem
\eqref{eq:prob} is equivalent to a
 \emph{multi-agent},
\emph{primal-dual} and \emph{finite-sum} optimization problem:
\beq \label{eq:opt_pd}
\min_{\prm \in \RR^d} \max_{ {\bm w}_i   \in  \RR^d ,i = 1,...,N } \frac{1}{NM} \sum_{i=1}^N \sum_{p=1}^M
\underbrace{\big( {\bm w}_i^\top {\bm A}_p \prm - {\bm b}_{p,i}^\top {\bm w}_i - \frac{1}{2} {\bm w}_i^\top {\bm C}_p {\bm w}_i + \frac{\rho}{2} \| \prm \|^2 \big)}_{\eqdef J_{i,p} ( \prm, {\bm w}_i )} \eqs.
\eeq

Hereafter, the global objective function is denoted by $J(\prm,  \{ {\bm w}_i \}_{i=1}^N )
 \eqdef (1/NM) \sum_{i=1}^N \sum_{p=1}^M J_{i,p} (\prm, {\bm w}_i )$, which is convex  \wrt the primal variable $\prm$ and is concave \wrt the dual variable $\{{\bm w}_i\}_{i=1}^N$.

It is worth noting that  the challenges in solving \eqref{eq:opt_pd} are three-fold.
First, to obtain a saddle-point solution
$( \{{\bm w}_i\}_{i=1}^N, \prm )$,
any  algorithm for \eqref{eq:opt_pd} needs  to update the primal and dual variables  simultaneously,
which can be difficult as objective function needs
not be strongly convex with respect to $\prm$.
In this case,  it is nontrivial to compute a solution efficiently.
Second, the objective function of \eqref{eq:opt_pd} consists
of a sum of $M$ functions, with $M \gg 1$ potentially, such that
conventional primal-dual methods \citep{chambolle2016ergodic} can no longer
be applied due to the increased complexity. Lastly,
since $\prm$ is shared by all the agents,
when solving \eqref{eq:opt_pd}, the $N$ agents need to reach a  consensus on
 $\prm$ without sharing the local functions, e.g.,

$J_{i,p}(\cdot)$ has to remain unknown
to all agents except for agent $i$ due to privacy concerns.
Although finite-sum convex optimization problems  with shared variables are well-studied,   new algorithms and theory are  needed for    convex-concave saddle-point problems.
Next, we propose  a novel decentralized first-order algorithm that tackles these difficulties and converges to a saddle-point solution of \eqref{eq:opt_pd} with linear rate.
\vspace{-.1cm}

config: arxiv


TITLE: Approximation of $\frac {n-c \choose k} {n\choose k} $ using a radical
QUESTION [1 upvotes]: Is there a good approximation for
$\frac {n-c \choose k}  {n\choose k} $, given large parameter n (k,c can be large as well, but k,c<n/2)?
I think I can express it as a simple exponent function f(n,k,c), but i am not sure.
I prove that this expression equals
$\Pi_{j=0}^{k-1}(1-\frac{c}{n-j})$
But i can't continue further

REPLY [3 votes]: Using the factorial definition, we can rewrite this as $$\frac{n!(n-(c+k))!}{(n-c)!(n-k)!}$$
and then use falling factorials to reduce to $$\frac{n^{\underline{(c+k)}}(n-(c+k))!^2}{(n-k)^\underline c (n-c)^\underline k (n-(c+k))!^2}=\frac{n^{\underline{c+k}}}{(n-k)^\underline c (n-c)^\underline k}$$
$n^\underline t$ is a polynomial of degree $t$. Hence, we may apply what I refer to as Domination Leads To Irrelevancy: $$\lim_{x\to\infty}\bigg[\frac{\sum_{k=0}^m a_k x^k}{\sum_{k=0}^n b_k x^k}\bigg]=\lim_{x\to\infty}\bigg[\frac{a_m}{b_n}x^{m-n}\bigg]=\begin{cases} \frac{a_mb_n}{|a_mb_n|}\infty & m>n \\ \frac{a_m}{b_n} & m=n \\ 0 & m<n \end{cases}$$
to see that the value will be very close to, and approaches $1$ for sufficiently large $n$ as both polynomials are degree $c+k$ and our leading coefficients are both $1$.


TITLE: Trace regularity result $\lVert n \times u\rVert_{H^{-1/2}}$
QUESTION [6 upvotes]: There is a result in a paper I am reading :
Let $\Omega$ be a bounded domain.  For any $\epsilon > 0$, there is a constant $C(\epsilon)$ such that
$$\lVert n \times u\rVert_{H^{-1/2}(\partial \Omega)} \leq \epsilon\lVert \nabla \times u\rVert_{L^2(\Omega)} + C(\epsilon)\lVert u\rVert_{L^2(\Omega)} $$ where $n$ is the normal.

Here is the proof provided : For any $\phi \in H^{1/2}(\partial \Omega) $, consider the problem
$$\nabla \times (\nabla \times w) + \frac{1}{\epsilon^2}w = 0 \text{ in } \Omega $$
$$ -n \times (n \times w) = \phi \text{ on } \partial \Omega$$
Then, the result follows immediately from estimating $|(n\times \phi)|$.

I am somewhat new to these types of arguments.  Can I get a first step here?  Thanks in advance.

REPLY [2 votes]: The author meant to resolve one problem: How to define the tangential trace of a vector field as a bounded linear functional on surfaces.
I do not think the result is as obvious as the author claimed.
Bold faced letters are used for vector field and its function space here just to avoid confusion. $\newcommand{\v}[1]{\boldsymbol{#1}}$
Suppose $\v{w}$ satisfies:
$$
\begin{aligned}
\nabla \times (\nabla \times \v{w}) + \frac{1}{\epsilon^2}\v{w }&= 0 \quad\text{ in } \Omega
\\
-\v{n} \times (\v{n} \times \v{w}) &= \v{\phi} \quad\text{ on } \partial \Omega
\end{aligned}\tag{1}
$$
and $\v{\phi}\in \v{H}^{1/2}(\partial \Omega)$. The corresponding variational problem is to find: $\v{w} \in \v{H}^1(\Omega)$ satisfying the boundary condition and:
$$
\int_{\Omega} \epsilon(\nabla  \times \v{w})\cdot (\nabla  \times \v{v}) +\int_{\Omega} \frac{1}{\epsilon}\v{w}\cdot \v{v} = 0
$$
for any test function $\v{v}\in \v{H}^1(\Omega)\cap\{\v{v}=0 \text{ on } \partial \Omega\}$. This problem is well-posed in a subspace of $\v{H}^1$ vector field: namely divergence free vector field with a zero normal component on boundary. Then the well-posedness can be established by Lax-Milgram lemma. And for divergence free vector field, the $\v{H}^1$-norm is equivalent to $\|\cdot\|_{\epsilon}:=\left(\frac{1}{\epsilon}\| \cdot\|_{\v{L}^2}^2 + \epsilon\| \nabla \times \cdot\|_{\v{L}^2}^2\right)^{1/2}$ for fixed $\epsilon$. Therefore there exists a solution for (1) weakly.
So for any $\v{\phi}\in \v{H}^{1/2}(\partial \Omega)$ that is defined on boundary, we could associate with it a divergence free $\v{H}^1$-vector field satisfying (1) inside the domain, and the Dirichlet type tangential projection boundary condition. And following natural estimate "solution bounded by data" for $\|\cdot\|_{\epsilon}$ holds:
$$
\|\v{w}\|_{\v{H}^1(\Omega)} \leq C(\epsilon)\|\v{w}\|_{\epsilon}\leq C(\epsilon)\|\v{\phi}\|_{\v{H}^{1/2}(\partial \Omega)}\tag{2}
$$
Now for any $\v{f}\in \v{H}^{1/2}(\partial \Omega)$, with its corresponding problem (1)'s solution $\v{v}\in \v{H}^1(\Omega)$ with boundary data $\v{n}\times(\v{f}\times\v{n})$. We have
$$\int_{\partial \Omega} \v{\phi} \times \v{n} \cdot \v{f} = \int_{\partial \Omega} \v{\phi} \times \v{n} \cdot (\v{n}\times(\v{f}\times\v{n}))  = \int_{\Omega} ( \nabla\times \v{w} \cdot \v{v} - \nabla\times \v{v}\cdot\v{w}) $$
Hence the dual norm by definition can be estimated by:
$$
\begin{aligned}
&\|\v{\phi} \times\v{n} \|_{\v{H}^{-1/2}} = \sup_{\v{f}} \frac{\left|\displaystyle\int_{\partial \Omega} \v{\phi} \times \v{n} \cdot \v{f}\,\right|}{\|\v{f}\|_{\v{H}^{1/2}(\partial \Omega)}}
\\
&\leq \sup_{\v{v}}  \frac{
\sqrt{\epsilon}\|\nabla\times \v{w}\| \frac{1}{\sqrt{\epsilon}}\|\v{v}\| + \sqrt{\epsilon}\| \nabla\times \v{v}\| \frac{1}{\sqrt{\epsilon}}\|\v{w}\| }{\|\v{v}\|_{\v{H}^{1}( \Omega)}}
\\
&\leq \sup_{\v{v}}  \frac{(\epsilon\|\nabla\times \v{w}\|^2 + \frac{1}{\epsilon}\|\v{w}\|^2 )^{1/2} (\epsilon\|\nabla\times \v{v}\|^2 + \frac{1}{\epsilon}\|\v{v}\|^2 )^{1/2}}{\|\v{v}\|_{\v{H}^{1}( \Omega)}}
\\
&\leq c(\epsilon)(\epsilon\|\nabla\times \v{w}\|^2 + \frac{1}{\epsilon}\|\v{w}\|^2 )^{1/2}
\end{aligned}\tag{3}
$$
We also need to balance the constant related to $\epsilon$ from (2) in the first inequality in (3). The last step is to notice that
$$
\v{\phi} \times \v{n}= -\v{n} \times (\v{n} \times \v{w}) \times\v{n} = \v{w} \times \v{n}
$$
Hence for $\v{w}\in \v{H}^1$:
$$
\|\v{w} \times\v{n} \|_{\v{H}^{-1/2}}^2\leq C( \epsilon\|\nabla\times \v{w}\|^2_{\v{L}^2(\Omega)} + \frac{1}{\epsilon}\|\v{w}\|^2_{\v{L}^2(\Omega)})
$$
As Glitch pointed, the constant $C$ depends on $\epsilon$, so the result is rather pointless.

Remark: The key step is essentially the same with Glitch. The differences are:

I didn't introduce the extra $\v{H}(\mathrm{curl})$ space like he did. We could just restrict ourselves for $\v{H}^1$-vector field why this estimate is correct. Therefore the boundary condition given by the paper is correct. Otherwise, we have to consider a problem like Glitch proposed, using Neumann boundary condition: $\v{n}\times(\nabla \times \v{w}) = \v{\phi}$ on $\partial \Omega$.
I didn't use the extension operator. When passing the first inequality in (3), Glitch used extension operator's property. I used the estimate from the boundary value problem.
The proof here I cooked up is solely for catering the boundary value problem that paper claimed to use. I still prefer Glitch's more "canonical" proof which is the same with what I learned from my electromagnetics class.
(EDIT)As Glitch pointed out, this is only true for some $\v{H}^1$-vector field. I am conjecting might be true for any $\v{H}^1$-vector field, there is a boundary Helmholtz decomposition such that the $\v{L}^2$-trace space can be decomposed into the trace spaces of divergence free $\v{H}^1$ and curl free $\v{H}^1$, such that the tangential trace is bounded by this $\v{H}^1$-vector field's $\v{H}(\mathrm{curl})$-norm inside, and the normal trace is bounded by its $\v{H}(\mathrm{div})$-norm inside. Apparently this generates a new question for myself...


TITLE: Delta Function as The Probability Distribution Function.
QUESTION [7 upvotes]: When a random variable $X$ has only one possible outcome $x_0$, the probability density function at $X=x_0$ is infinite, while the probability density at other locations is zero. Then the p.d.f is exactly a delta function $\Pr(X=x) = \delta(x=x_0)$.
However, when I tried to calculate the entropy of the random variable, the problem arises. How can I calculate the integral $\int_{-\infty}^{+\infty}{\delta(x-x_0)\log\delta(x-x_0) \, dx}$?

REPLY [0 votes]: A delta distribution can be viewed as a Bernoulli distribution with p = 0, and its entropy is zero


TITLE: Are the quaternions not uncountably categorical?
QUESTION [15 upvotes]: Boris Zilber has argued that the field of the complex numbers is "logically perfect".  For one thing, the theory of an algebraically closed field of characteristic zero is uncountably categorical: it admits a unique model, up to isomorphism, of some uncountable cardinality - and thus a unique model of each uncountable cardinality, by Morley's theorem!
The field of real numbers is not "logically perfect" in Zilber's sense. More precisely, the theory of a real closed field is not uncountably categorical.
This led Terry Bollinger to ask about the quaternions.
Has anyone studied this?  For starters, we need to settle on a 'theory of quaternions'.  I want a theory where the only operations are + and ×, and the only constants are 0 and 1.  Here's my guess about how to proceed.  First we impose the axioms of a division ring (including associativity for multiplication, to rule out the octonions!).  We impose a 'characteristic zero' axiom schema that says $1 + 1 + \cdots + 1$ can never equal zero.  Then we impose an 'algebraically closure' axiom saying that any polynomial whose coefficients all commute has a root.  (Any commuting set of quaternions lies in a subring isomorphic to the complex numbers.)  Finally, we impose an axiom saying that multiplication is not commtuative, to rule out the complex numbers.
I haven't thought about this much, but I'm hoping these are enough, with the help of the Frobenius theorem.
Then we can ask if the theory of quaternions is uncountably categorical.  My guess is that it's not.
Here's my rough reasoning.  The center of the quaternions forms a copy of the real numbers.  Moreoever, I'm guessing that we can prove using our 'theory of quaternions" that the center of the quaternions is a real closed field.  Conversely, starting from any real closed field, we can build a model of the theory of quaternions.  So, I believe we're in trouble, since the theory of a real closed field is not uncountably categorical.
Perhaps someone can say if this sort of argument is valid: if in some structure we can define a subset and this subset, equipped with some operations in our theory, is a model of a second theory that's not uncountably categorical... and any model of that second theory arises in this way... then the original theory could not have been uncountably categorical.
Or, if this doesn't work, maybe someone can straighten things out!

REPLY [7 votes]: I don't think the axioms suffice.  Here is some background:
Theorem 16.16 of TY Lam's "First Course in Noncommutative Rings" states:  "The centrally finite noncommutative division rings which are right algebraically closed are precisely the division rings over real closed fields.  These division rings are also left algebraically closed."
Lam goes on to say that, without the "centrally finite" assumption, not much seems to be known.
In http://eprints.biblio.unitn.it/1626/1/ghiloni-octonions-preprint.pdf, published in J. Algebra Appl., 11, 1250088 (2012), Ghiloni seems to prove the octonionic analogue.  Also, Ghiloni attributes the result above to Niven, Baer, and Jacobson, based on I. Niven, Equations in quaternions. Amer. Math. Monthly 48, (1941), 654–661.
For a noncommutative ring $D$, the "right algebraically closed" condition states that for any nonconstant polynomial $a_0 + a_1 X + \cdots + a_n X^n$ with coefficients in $D$, there exists an element $d \in D$ such that $a_0 + a_1 d + \cdots + a_n d^n = 0$.  This is stronger than the condition you give, in which the coefficients are required to commute with each other.
The "centrally finite" condition (required in the quaternionic and octonionic results) states that the whole algebra is a finite-dimensional vector space over the center of the algebra.
Lam's remark suggsts that, without the "centrally finite" assumption, there may be right/left algebraically closed division rings which are not quaternion algebras over a real closed field.  Since his axioms for algebraic closure are stronger (or at least as strong) as yours, but you omit the central finiteness condition, I think your axioms could allow some exotic examples.
Now, I think an exotic example is given in the paper "Algebraically-closed skew-fields" by L Makar-Limanov, Journal of Algebra Volume 93, Issue 1, March 1985, Pages 117–135.  Makar-Limanov gives an even stronger definition of "algebraically closed" (using polynomials in the amalgamated product $A \ast Z[X]$ (amalgamated over $Z$) ).  There Makar-Limanov constructs a centrally infinite, algebraically closed (in his strong sense) division algebra (a.k.a. skew-field).  So Makar-Limanov's algebra will satisfy the axioms of the question, without being a quaternion algebra over a real closed field.
Add an axiom which implies "centrally finite" and I think it's golden.  Unfortunately, I can't think of such an axiom which doesn't explicitly bound the dimension over the center, for example:  "For every five elements $a,b,c,d,e$ of the algebra, there exist five elements $u,v,w,x,y$ of the center of the algebra, not all zero, such that $ua + vb + wc + xd + ye = 0$."


text:
\begin{document}
\maketitle

\vspace{-.3cm}

\begin{abstract}
IA sufficient condition for the existence of a solution for generalized vector equilibrium problem (GVEP) on Hadamard manifold, by using  a version of  KKM lemma  on this context,  is presented in this paper.  It is worth to point out that, in particular,   existence result  of solution for optimization problems, vector optimization problems, Nash equilibria problems, complementarity problems and variational inequality problems can be obtained as a special case of the existence result  for GVEP in this new context.
\end{abstract}
{\bf Keywords:} Vector equilibrium problem\;$\cdot$\; Vector optimization\;$\cdot$\; Hadamard  manifold.

\noindent{\bf AMS subject classification:} \,90C33\,$\cdot$\,65K05\,$\cdot$\, 47J25  $\cdot$\,91E10.

\section{Introduction}

The generalized vector equilibrium problem (denoted by GVEP)  has been widely studied and is a very active field of research. One of the motivations is that several problems can be formulated as a generalized vector equilibrium problem, for instance, \mbox{optimization} problems, vector optimization problem, Nash equilibria problems, complementarity problems, fixed point problems and variational inequality problems. An extensive development is found, e.g., in    Fu~\cite{FU2000}, Fu and Wan \cite{FUAn2002}, Konnov and Yao\cite{KonnovYao1999}, Ansari et al. \cite{AnsarKonnovYao2001}, Farajzadeh et al. \cite{FarajzadehAmini-Harandi2008} and  their references. An important issue is under what conditions there exists a solution to GVEP. In the linear setting, several authors have provided results answering this question; see, for instance, , e.g., \cite{ANSARI1999},    Fu~\cite{FU2000}, Fu and Wan \cite{FUAn2002}, Konnov and Yao\cite{KonnovYao1999}, Ansari et al. \cite{AnsarKonnovYao2001}, Farajzadeh et al. \cite{FarajzadehAmini-Harandi2008} and  their references.

The first papers  dealing with the  subject on  existence of solution for equilibrium problems in the Riemannian context were Colao et al.~\cite{CLMM2012} and  Zhou and Huang\cite{ZhouHuang2009}, by generalizing  KKM lemma  to  Hadamard manifold.   By using   KKM lemma  on Hadamard manifold Zhou and Huang \cite{Zhou2013} have obtained  result of existence for vector optimization problems and vector variational inequality on this context.   In a similar manner   Li and Huang \cite{XiaHuang2013} have present result of existence for special class of  GVEP.  In the present work, we  use   KKM lemma  on Hadamard manifold  for proving existence result for GVEP. As far as we know it is  a new contribution of this paper.   It is worth to point out that our result include the results of  \cite{CLMM2012, Zhou2013} and not is included in the paper \cite{XiaHuang2013}.

The organization of the paper is as follows.
In Section \ref{sec2},  some notations and  basic results  used in the paper are presented. In Section \ref{s.main} the main results are stated and proved.  Some final remarks are made in Section~\ref{fr}.

\section{Notations and basics results}\label{sec2}
\subsection{Riemanian Geometry}
In this section, we recall some fundamental and basic concepts needed for reading this paper. These results and concepts can be found in the books on Riemannian geometry, see do Carmo~\cite{MP1992} and Sakay~\cite{S1996}.

Let $M$ be a $n$-dimensional connected manifold. We denote by $T_xM$ the $n$-dimensional {\it tangent space} of $M$ at $x$, by $TM=\cup_{x\in M}T_xM$ {\itshape{the tangent bundle}} of $M$ and by ${\cal X}(M)$ the space of smooth vector fields over $M$. When $M$ is endowed with a Riemannian metric $\langle .\,,\,. \rangle$, with the corresponding norm denoted by $\| . \|$, then $M$ is a Riemannian manifold. Recall that the metric can be used to define the length of piecewise smooth curves $\gamma:[a,b]\rightarrow M$ joining $x$ to $y$, i.e., $\gamma(a)=x$ and $\gamma(b)=y$, by $l(\gamma):=\int_a^b\|\gamma^{\prime}(t)\|dt$, and moreover, by minimizing this length functional over the set of all such curves, we obtain a Riemannian distance $d(x,y)$ inducing the original topology on $M$. We denote by $B(x,\epsilon)$ the Riemannian ball on $M$ with center $x$ and radius $\epsilon>0$. A vector field $V$ along $\gamma$ is said to be {\it parallel} iff $\nabla_{\gamma^{\prime}} V=0$. If $\gamma^{\prime}$ itself is parallel we say that $\gamma$ is a {\it geodesic}. Given that the geodesic equation $\nabla_{\ \gamma^{\prime}} \gamma^{\prime}=0$ is a second-order nonlinear ordinary differential equation, we conclude that the geodesic \mbox{$\gamma=\gamma _{v}(.,x)$} is determined by its position $x$ and velocity $v$ at $x$. It is easy to verify that $\|\gamma ^{\prime}\|$ is constant.  The restriction of a geodesic to a closed bounded interval is called a {\it geodesic segment}.  We usually do not distinguish between a geodesic and its geodesic segment, as no confusion can arise.  A Riemannian manifold is {\it complete} iff the geodesics are defined for any values of $t$. The \mbox{Hopf-Rinow's} Theorem~(\cite[Theorem 2.8, page 146]{MP1992} or~\cite[Theorem~{1.1}, page 84]{S1996}) asserts that, if this is the case, then  $( M, d)$ is a complete metric space and, bounded and closed subsets are compact. From the completeness of the Riemannian manifold $M$, the {\it exponential map} $\exp_{x}:T_{x}  M \to M $ is defined by $\exp_{x}v\,=\, \gamma _{v}(1,x)$, for each $x\in M$.  A complete simply-connected Riemannian manifold of nonpositive sectional curvature is called an Hadamard manifold.  It is known that if $M$ is a Hadamard manifold, then $M$ has the same topology and differential structure as the Euclidean space $\mathbb{R}^n$; see, for instance,~\cite[Lemma 3.2, page 149]{MP1992} or \cite[Theorem 4.1, page 221]{S1996}. Furthermore, are known some similar geometrical properties to the existing in Euclidean space $\mathbb{R}^n$, such as, given two points there exists an unique geodesic segment that joins them.  {\it In this paper, all manifolds $M$ are assumed to be Hadamard and finite dimensional}.

\subsection{Convexity} \label{sec3}

A set $\Omega\subset M$ is said to be {\it convex}  iff any
geodesic segment with end points in $\Omega$ is contained in
$\Omega$, that is, iff $\gamma:[ a,b ]\to M$ is a geodesic such that $x =\gamma(a)\in \Omega$ and $y =\gamma(b)\in \Omega$, then $\gamma((1-t)a + tb)\in \Omega$ for all $t\in [0,1]$.  For an arbitrary set $\mathcal{B} \subset M$ the {\it convex hull} of $\mathcal{B}$ denoted by $ \mbox{co}(\mathcal{B})$, that is, the smallest convex subset of $M$ containing $\mathcal{B}$. Let $\Omega\subset M$ be a convex set.

\subsection{Set-valued mapping} \label{sec3}

For any  set $\mathcal{A}$ we denote $2^{\mathcal A}$  the set of all subset of $\mathcal{A}$.   Let $M$ be a Hadamard manifold,   $\Omega \subset M$ a nonempty  set. For $T: \Omega \rightarrow 2^{\mathbb{Y}}$ a set-valued mapping  the {\it domain} and the {\it range}  are the sets, respectively, defined by
\begin{equation} \label{eq:dr}
\mbox{dom}T:=\left\{ x\in \Omega ~: ~T(x)\neq \varnothing \right\}, \qquad   \mbox{rge} T:=\left\{ y \in {\mathbb{Y}} ~: ~y\in T(x) \mbox{ for some } x \in \Omega \right\},
\end{equation}
and the {\it inverse} is set-valued mapping $T^{-1}:= {\mathbb{Y}} \rightarrow 2^{\Omega} $ defined by
\begin{equation} \label{eq:dr}
T^{-1}(y):=\left\{x\in \Omega ~:~ y\in T(x) \right\}.
\end{equation}
A set-valued mapping $T: \Omega \rightarrow 2^{\mathbb{Y}}$ is said to be \emph{upper semicontinuous} on $\Omega$ if, for each $x_0\in \Omega$ and any open set $V$ in $\Omega$ containing $T(x_0)$, exists an open neighborhood $U$ of $x_0$ in $\Omega$ such that $T(x)\subset V$ for all $x\in U$.

Next result is a version  of   KKM lemma  in Riemannian context  due to \cite{CLMM2012},  which is an extension to Hadamard manifold of KKM theorem see,  for example,  \cite{TARAF1987}.
 \begin{lemma}  \label{le:colao}
Let $M$ be a Hadamard manifold,   $\Omega \subset M$ a nonempty closed convex set and  $G:\Omega \rightarrow 2^{\Omega}$  a set-valued mapping such that, for each $y\in\Omega, G(y)$ is closed. Suppose that
\begin{itemize}
\item [(i)] there exists $y_0\in\Omega$ such that $G(y_0)$ is compact;
\item [(ii)] $\forall ~ y_1,...,y_m\in \Omega,~\emph{co}(\{y_1,...,y_m\})\subset\bigcup_{i=1}^{m}G(y_i)$.
\end{itemize}
Then $\bigcap_{y\in \Omega}^{}G(y)\neq \varnothing.$
\end{lemma}
\begin{proof}
See, \cite[Lemma 3.1]{CLMM2012}.
\end{proof}

\section{Generalized  vectorial   equilibrium problem} \label{s.main}

In this section, we present a sufficient condition for the existence of solution of generalized vector equilibrium problem on Hadamard manifolds. From now on, $\Omega \subset M$ will denote a nonempty closed convex set and $ \mathbb{Y}$ denotes  a topological vector space. Let $C: \Omega \rightarrow 2^{\mathbb{Y}}$ be set-valued mapping such that
\begin{equation} \label{eq:cx}
 C(x) ~  \mbox{ is a closed convex cone},  \qquad \mbox{int}\,C(x)\neq \varnothing, \qquad  \forall~   x \in \Omega.
\end{equation}
A set-valued mapping  $F:\Omega\times\Omega \rightarrow 2^{\mathbb{Y}}$  is called $C_x$ - \emph{quasiconvex-like} if for any geodesic segment $\gamma:[0, 1]\to \Omega$  there holds
 $$
 F(x,\gamma(t))\subseteq F(x,\gamma(0))-C(x) \quad ~ \mbox{or} ~ \quad  F(x,\gamma(t))\subseteq F(x,\gamma(1))-C(x), \qquad \forall \; t\in [0,1].
 $$

Then, given a set-valued mapping  $F: \Omega\times \Omega \rightarrow 2^{\mathbb{Y}}$, the {\it generalized vector equilibrium problem} in the Riemannian context (denoted by GVEP) consists in:
\begin{equation}\label{eq:p}
\mbox{Find $x^{*}\in \Omega$}:\quad F(x^\ast,y) \nsubseteq -\mbox{int}\,C(x^{*}),\qquad \forall \ y \in \Omega.
\end{equation}
Next result is closed related to   \cite[Theorem 2.1]{ANSARI1999}.  It  establish an existence result of solution for GVEP as an application  of Lemma~\ref{le:colao}.

\begin{theorem} \label{th:main}
Let $F:\Omega\times\Omega \rightarrow 2^{\mathbb{Y}}$ be a set-valued mapping such that  for each $x, y\in\Omega$
\begin{itemize}
\item [{\bf h1}.]   $F(x,x)\not\subset -\emph{int}\,C(x)$;
\item [{\bf h2}.]  $F(\cdot,y)$ is upper semicontinuos;
\item [{\bf h3}.] $F$ is $C_x$-quasiconvex-like;
\item [{\bf h4}.] there exist $D\subset\Omega$   compact  and  $ y_0 \in\Omega$  such that $x\in\Omega\backslash D \Rightarrow F(x,y_0)\subset -\emph{int}\,C(x)$.
\end{itemize}
Then the solution set $S^{\ast}$ of  the GVEP defined in \eqref{eq:p} is a compact  nonempty set.
\end{theorem}
From now on we assume that every assumptions on Theorem~\ref{th:main} hold.  In order to prove Theorem~\ref{th:main} we need of some  preliminaries. First we define the set-valued mapping  $P:\Omega \rightarrow 2^{\Omega}$ given by
\begin{equation} \label{eq:set}
P(x):= \left\{y\in\Omega~:~F(x,y)\subset-\mbox{int}\,C(x) \right\}.
\end{equation}
\begin{lemma} \label{l:at1}
If    $S^{\ast}=\varnothing$ then, for each $x, y\in\Omega$, the set-valued mapping $P$  satisfies the following conditions:
\begin{itemize}
\item[i)]  the set $P(x)$ is nonempty and convex;
\item[ii)] $P^{-1}(y)$ is an open set and  $\bigcup_{y\in\Omega}^{}P^{-1}(y)=\Omega$;
\item[iii)]  there exists $y_0\in\Omega$ such that $P^{-1}(y_0)^{c}$ is compact.
\end{itemize}
\end{lemma}
\begin{proof}
Since   the solution set $S^{\ast}=\varnothing$,  the definition  in \eqref{eq:set} allow us to conclude that $P(x)\neq\varnothing$, for all $x\in \Omega$, which proof the first statement in item $i$.  Let $x\in \Omega$. For proving that  $P(x)$ is convex, take    $y_1,y_2\in P(x)$ and a geodesic $\gamma: [0, 1] \to \Omega$ such that $\gamma(0)=y_1$ and $\gamma(1)=y_2$.  Using the assumption {\bf h1}  we have
\begin{equation} \label{eq:itws}
 F(x,\gamma(t))\subseteq F(x,y_1)-C(x) \quad ~ \mbox{or} ~ \quad  F(x,\gamma(t))\subseteq F(x,y_2)-C(x).
\end{equation}
As $y_1,y_2\in P(x)$, definition of $P(x)$ in \eqref{eq:set} implies that $F(x,y_1)\subset-\mbox{int}\,C(x)$  and $F(x,y_2)\subset-\mbox{int}\,C(x)$. Hence,  taking in account that $-\mbox{int}\,C(x) - C(x) \subset -\mbox{int}\,C(x)$  it follows from \eqref{eq:itws} that
$$
 F(x,\gamma(t))\subset -\mbox{int}\,C(x),
$$
and the proof of item $i$ is concluded.

Now we are going to prove item $ii$.  First of all note that using definition in  \eqref{eq:dr} we have
\begin{equation} \label{eq:pm1}
P^{-1}(y)=\{x\in \Omega~: ~y\in P(x)\}=\{x\in\Omega ~: ~F(x,y)\subset-\mbox{int}\, C(x)\},
\end{equation}
where the second equality follows from definition of the set $P(x)$ in \eqref{eq:set}.   Take  $x_0\in P^{-1}(y)$. From the second equality in \eqref{eq:pm1} and   that  $-\mbox{int}\,C(x)$ is an open set, using  {\bf h2},  there exists  $ V_{x_0}\subset \Omega$   an open set  such that
$
 F(x,y)\subset-\mbox{int}\,C(x),
$
for all $ x\in V_{x_0}.$
Therefore, $P^{-1}(y)$ is open, which proof the first part in  item $ii$.  Definition in \eqref{eq:pm1} implies that $P^{-1}(y)\subseteq \Omega$ for all $y\in \Omega$. For concluding the proof of item $ii$, is sufficient to prove that  $\Omega\subseteq \bigcup_{y\in\Omega}^{}P^{-1}(y)$.   Let  $x\in\Omega$. From  Item $i$  we  have $P(x)\neq\varnothing$ and hence  there exists $y\in P(x)$. Therefore  $x\in P^{-1}(y)$ for some $y\in \Omega$, which conclude the proof  of item $ii$.

For proving  item $iii$, first note that  from assumption {\bf h4} and definition in \eqref{eq:pm1},  we have
$$
P^{-1}(y_0)^{c}=\{x\in\Omega~:~F(x,y_0)\not\subset-\mbox{int}\,C(x)\}\subset D,
$$
for some $y_0\in \Omega$ and $D\subset \Omega$ a  compact set.  From item $i$  the set $P^{-1}(y_0)$ is an open set,  and since  $D$ is a compact set,  we conclude from last inclusion  that $P^{-1}(y_0)^{c}$  is a compact set and the proof of the proposition is concluded.
\end{proof}
Now we are ready to prove our main result, namely,   Theorem~\ref{th:main}.
\begin{proof}
Let us suppose, by contradiction,  that he solution set   $S^{\ast}=\varnothing$. Let $ G :   \Omega \to  2^{\Omega}$ be  the set-valued mapping defined by
\begin{equation} \label{eq:faux}
G(y):=P^{-1}(y)^{c}.
\end{equation}
Define  the set $D:=\bigcap_{y\in \Omega}^{}G(y)$. We have two passibility  for the set $D$, namely,   $D\neq \varnothing$ or   $D= \varnothing$. If  $D\neq \varnothing$, i.e.,  $\bigcap_{y\in \Omega}^{}P^{-1}(y)^{c}\neq \varnothing$,  then we have
$
\bigcup_{y\in \Omega}^{}P^{-1}(y)\neq \Omega,
$
which is a contradition with the item $ii$ in  Lemma~\ref{l:at1}. Hence,  we conclude that  $D= \varnothing$, i. e.,
$$
\bigcap_{y\in \Omega}^{}G(y)= \varnothing .
$$
Thus, as we are under the assumption  $S^{\ast}=\varnothing$, combining definition in \eqref{eq:faux} and    Lemma~\ref{l:at1} items ii and iii, we conclude  that,  for each $y\in\Omega$,  the set $G(y)$ is closed and  there exists $y_0\in\Omega$ such that $G(y_0)$ is a compact set. Hence,  as $\bigcap_{y\in \Omega}^{}G(y)= \varnothing$,  Lemma~\ref{le:colao}  implies  that there exist  $ y_1,...,y_m\in \Omega$ such that
$$
\mbox{co}\{y_1,...,y_m\}\not\subset \bigcup_{i=1}^{m}G(y_i),
$$
and  thus  there exists $x\in \mbox{co}\{y_1,...,y_m\}$ such that  $x\notin G(y_i)=P^{-1}(y_i)^{c} $ for all $i=1, \ldots m$ or,  equivalently,    there exists $x\in \mbox{co}\{y_1,...,y_m\}$ such that  $x\in P^{-1}(y_i) $ for all $i=1, \ldots m$.  Therefore,  we conclude that
\begin{equation} \label{eq:rmth}
\exists ~ y_1,...,y_m\in \Omega,  \quad \exists ~ x\in \mbox{co}\{y_1,...,y_m\};  \quad   y_i\in P(x), \quad    \forall ~i=1, \ldots m.
\end{equation}
   Taking into  account that  $S^{\ast}=\varnothing$, items i of Lemma~\ref{l:at1}  implies that $P(x)$ is convex, which together with  relations in \eqref{eq:rmth} yields
   $$
   \exists ~  x  \in \Omega:~ ~x\in P(x).
   $$
 Last inclusion and definition in \eqref{eq:set} imply   that there exists  $x  \in \Omega$ such that  $F(x,x)\subset-\mbox{int}\,C(x)$, obtaining  a contradiction with the assumption {\bf h1} in Theorem~\ref{th:main}. Therefore,  the solution set  $S^{\ast}\neq\varnothing$ and the proof of Theorem~\ref{th:main} is concluded.
\end{proof}

\begin{remark}
Note that, in particular,  when $M=\mathbb{R}^{n}$, our problem~\eqref{eq:p} retrieves a particular instance of the generalized vector equilibrium problem studied by Ansari and Yao in \cite{ANSARI1999}. In the case where $C(x)=\mathbb{R}_{+}$, for each $x\in \Omega$, $\mathbb{Y}=\mathbb{R}$ and $F$ is single-valued map from $\Omega \times \Omega$ to $\mathbb{R}$, then the problem \eqref{eq:p} reduces to the equilibrium problem on Hadamard manifold considered by Colao et al. in \cite{CLMM2012}; see also Bento et al.~\cite{BCSS2013}. Now, let us consider the following vector optimization problem on Hadamard manifold:
\begin{equation} \label{eq:vopt}
\left\{\begin{array}{c}
w-\emph{min}f(x),\\
s. t.\; x\in \Omega,
\end{array}\right.
\end{equation}
where $f:M\to\mathbb{R}^{m}$ vector function and $w-\emph{min}$ denotes weak minimum.  Zhou and Huang~\cite{Zhou2013} presented an existence result of solutions for the problem \eqref{eq:vopt} by showing the equivalence of this with the variational inequality problem on Hadamard manifold (studied by N\'emeth in \cite{N2003}):
\begin{equation}\label{prob:VVI}
\mbox{Find $x^{*}\in \Omega$}:\quad \langle A(x^*), \exp^{-1}_{x^*}y\rangle \notin -\mathbb{R}^m_{++},\qquad \forall \ y \in \Omega,
\end{equation}
in the particular case where $f$ is a differentiable and convex vector function  and $A$ is the Riemannian Jacobian of  $f$. Taking into account that $x^{*}\in \Omega$ is a weak minimum of \eqref{eq:vopt} iff
\[
f(x)-f(x^{*})\notin -\mathbb{R}_{++}^{m}, \qquad \forall x\in \Omega,
\]
we point out that, in particular,   Theorem~\ref{th:main} is an existence result of solution for the problem \eqref{eq:vopt}  even in the case where f is only quasi convex and not necessarily differentiable.
\end{remark}

\section{Final remarks} \label{fr}
In this paper we study  basics intrinsic properties of  generalized vector equilibrium problem in Hadamard manifolds, and we
touch only slightly  the equilibrium problem theory in this  context.  We expect that the results of this paper become a
first step towards a more general theory, including hyperbolic spaces and algorithms for solving that problems on Hadamard manifolds. We foresee further progress in this topic in the  nearby future.