TITLE: Probability of passing a multiple choice test by guessing, if guessing is penalized
QUESTION [1 upvotes]: Given a test with n questions, 3 choices each, where a question contributes to the score with 1/n if correct, r/n if wrong (-1 < r < 0), and 0 if not answered, and k·n is needed to pass the exam (0 < k < 1/n). Say also that a student can only guess (has no clue of the matter to be examined), what would be her chances (best choice) to pass the exam?
Update: let n be around 50, since this matters for approximating the distribution.

REPLY [1 votes]: Here is a computational solution.
In general, given a fixed number of questions $N=50$ and a fixed probability $p=1/3$ that a student's guess is correct, and one point for each correct answer, the probability that a student passes depends on the following variables:

How many questions $Q$ the student chooses to attempt, rather than leave blank.
The penalty $R$ for incorrect answers.
The threshold $T$ of points required to pass.

We can eliminate one of these variables $Q$ by assuming the student behaves optimally: For a given value of $R$ (penalty) and $T$ (passing threshold), we can find the value of $Q$ that maximizes the probability of passing, whatever it is. Then we can use that value of $Q$ as a benchmark— a student can do no better than the optimal strategy.
As a result of assuming the student chooses the optimal strategy, the probability that a student passes by guessing becomes a function of only two variables: $R$ (penalty for incorrect guess) and $T$ (passing threshold). We can brute-force compute the values for penalty values $0 \leq R \leq 1$ and threshold values $0\leq T \leq N$, as a sum of binomial-type probabilities.
The result is a chart like the following:

Here, the x-axis records the number of points $T$ required to pass — $T$ only goes as high as 25 (requiring at least half of the responses to be correct answers), because beyond that the probability of success by guessing is negligible no matter the penalty.
The y-axis records the penalty $R$ for guessing.
This chart allows you to see how you can set the penalty for guessing and the threshold for passing so as to control the probability that a completely random guesser passes.

Please feel free to use or double-check my Python code: https://pastebin.com/yT8hqd6y

Edit: Roughly speaking, for reasonable threshold levels, the relationship between $R$ and $T$ is approximately linear: if $p=\frac{1}{3}$ is the probability that a student answers a question correctly, then a student has a 50% chance of passing when the penalty and threshold are set according to
$$T = pN (1-2R)$$
Here, $pN$ is the expected number of correct answers when guessing on all of the questions. In particular, note that when there is no penalty $R=0$, this implies that the student is more likely to fail than succeed if the threshold for points is greater than the expected number of correct answers when guessing on everything.


TITLE: Show the feasible set of convex functions is convex.
QUESTION [1 upvotes]: Problem Statement
Let $g_{1},\dots, g_{M}$ be convex functions and let  $b_{1},\dots, b_{M}$ be real numbers. Show that $F:=  \{ \boldsymbol{x} \in \mathbb{R}^{d} : g_{i}(\boldsymbol{x}) \leq b_{i}, $ for all $i = 1,\dots , M \}$ is a convex set.
Attempted Proof
We endeavour to prove that a given set, $F:=  \{ \boldsymbol{x} \in \mathbb{R}^{d} : g_{i}(\boldsymbol{x}) \leq b_{i} \forall i = 1,\dots , M \}$ is convex. Where $\{g_{i}\}_{i=1}^{M}$ represents convex functions and  $\{b_{i}\}_{i=1}^{M}$ represents real integers.
We know, from the definition of a convex set that the feasible set  $F:=  \{ \boldsymbol{x} \in \mathbb{R}^{d} : g_{i}(\boldsymbol{x}) \leq b_{i}, $ for all $i = 1,\dots , M \}$ is convex  on the condition that all the functions  $\{g_{i}\}_{i=1}^{M}$ are convex.
Explanation
I am trying to show that the set is convex by taking two points x and y which are in the set and show that for any $\lambda \in [0,1]$, the point $\lambda \boldsymbol{x} + (1-\lambda) \boldsymbol{y} $ is also in the set. Where a point will be in the set if it satisfies all the constraints.
The problem is I am struggling to take my first attempted at a proof and use a more mathematically method to prove this by taking two points in the set as described above. I would like to use the definition of a convex function ,i.e. a convex function $f$ , is one that satisfies for $0 \leq \lambda \leq1$,
    \begin{eqnarray*}
   f(\lambda \boldsymbol{x} +(1-\lambda)\boldsymbol{y} ) \leq \lambda f(\boldsymbol{x}) + (1-\lambda)f(\boldsymbol{y}) \text{.}
\end{eqnarray*}
 I have found similar questions with regards to the sum or quotient of convex functions online but I have not come across a proof of this with a good solution so far. Could someone please show me how they would formulate this proof.
This question was similar:
From convex set to convex function

REPLY [0 votes]: Let $g_1, g_2, \ldots, g_M$ be convex functions from $\mathbb{R}^d \to \mathbb{R}$ and $b_1, b_2, \ldots, b_M \in \mathbb{R}$. We want to show that $F := \{ x \in \mathbb{R}^d : g_i(x) \leq b_i, \, i \in 1, 2, \ldots, M\}$ is convex.
To start, suppose that $x_1 \in F$ and $x_2 \in F$ are arbitrary points in $F$ and that $t \in (0,1)$. We want to show that $x_3 = tx_1 + (1-t)x_2 \in F$.
First, consider an arbitrary $i \in 1,2,\ldots, M$. By definition of the convexity of $g_i$, we know that $g_i(x_3) = g_i(tx_1 + (1-t) x_2) \leq tg_i(x_1) + (1-t)g_i(x_2)$. By definition of $F$, we know that $tg_i(x_1) + (1-t)g_i(x_2) \leq tb_i + (1-t)b_i = b_i$. Thus we have that $g_i(x_3) \leq b_i$, and we can repeat this argument for all $i$. Thus $x_3 \in F$. Hence $F$ is a convex set.


text:
\begin{document}

\maketitle

\begin{abstract}
	We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among $n$ workers, who can take SGD steps and coordinate with a central server. Unfortunately, this could require a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism. The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs $\Omega ( \sqrt{T} )$ communications for $T$ local gradient steps in order for the error to scale proportionately to $1/(nT)$, this has been successively improved in a string of papers, with the state-of-the-art requiring  $\Omega \left( n \left( \mbox{ polynomial in  log } (T) \right) \right)$ communications. In this paper, we give a new analysis of Local SGD. A consequence of our analysis is that Local SGD can achieve an error that scales as $1/(nT)$ with only a fixed number of communications independent of $T$: specifically, only $\Omega(n)$  communications are required.
\end{abstract}

\section{Introduction}

Stochastic Gradient Descent (SGD) is a widely used algorithm to minimize a convex or non-convex function $F$ in which model parameters are updated iteratively as follows:
\begin{align*}
	\bx^{t+1} = \bx^t - \eta_t \hbg^t,
\end{align*}
where $\hbg^t$ is a stochastic gradient of $F$ at $\bx^t$ and $\eta_t$ is the learning rate.
This algorithm can be naively parallelized by adding more workers independently  to compute a gradient and then average them at each step to reduce the variance in estimation of the true gradient $\nabla F(\bx^t)$ \cite{dekel2012optimal}. This method requires each worker to share their computed gradients with each other at every iteration.

However, it is widely acknowledged that communication is a major bottleneck of this method for large scale optimization applications \cite{mcmahan2016communication,konevcny2016federated,lin2017deep}.
Often, mini-batch parallel SGD is suggested to address this issue by increasing the computation to communication ratio.
Nonetheless, too large mini-batch size might degrades the performance \cite{lin2018don}. Along the same lines of increasing compute to communication, \textit{local} SGD has been proposed to reduce communications \cite{mcmahan2016communication,dieuleveut2019communication}. In  this method, workers compute (stochastic) gradients and update their parameters locally, and communicate only once in a while to obtain the average of their parameters.
Local SGD improves the communication efficiency not only by reducing the number of communication rounds, but also alleviates the synchronization delay caused by waiting for slow workers and evens out the variations in workers' computing time \cite{wang2018cooperative}.

On the other hand, since individual gradients of each worker are calculated at different points, this method introduces residual error as opposed to fully synchronous SGD. Therefore, there is a trade-off between having fewer communication rounds and introducing additional errors to the gradient estimates.

The idea of making local updates is not new and has been used in practice for a while  \cite{konevcny2016federated}. However, until recently, there have been few successful efforts to analyze Local SGD theoretically and therefore it is not fully understood yet.
The paper \cite{zhang2016parallel} shows that for quadratic functions, when the variance of the noise is higher far from the optimum, frequent averaging leads to faster convergence.
One of the main questions we want to ask is: how many communication rounds are needed for Local SGD to have the \textit{same} convergence rate of a synchronized parallel SGD while achieving performance that linearly improves in the number of workers?

\cite{stich2018local} was among the earlier works that tried to answer this question for general strongly convex and smooth functions and showed that the communication rounds can be reduced up to a factor of $H = \O(\sqrt{T/n})$, without affecting the asymptotic convergence rate (up to constant factors), where $T$ is the total number of iterations and $n$ is number of parallel workers.

Focusing on smooth and possibly non-convex functions which satisfy  a Polyak-Lojasiewicz condition, \cite{haddadpour2019local} demonstrates that only $R = \Omega((Tn)^{1/3})$ communication rounds are sufficient to achieve asymptotic performance that scales proportionately to $1/n$.

More recently, \cite{khaled2019tighter} and \cite{stich2019error} improve upon the previous works by showing linear-speed up for Local SGD with only $\Omega \left(n \mbox{ poly log }(T) \right)$ communication rounds when data is identically distributed among workers and $F$ is strongly convex. Their works also consider the cases when $F$ is not necessarily strongly-convex as well as the case of data being heterogeneously distributed among workers in \cite{khaled2019tighter}.

\begin{table}
    \caption{Comparison of Similar Works}
    \label{table: comparison}
    \begin{threeparttable}[b]
    \centering
    \def\arraystretch{2}
    \resizebox{\textwidth}{!}{
    \begin{tabular}{| c c c c c |}

    \hline

    \thead{noise\\model} & \thead{$H=T$ \tnote{a}\\convergent} & \thead{communication\\rounds, $R$} & \thead{convergence rate,\\$F(\hat \bx^t) - F^*$} & Reference \\

    \hline
    uniform  & no  & $\Omega(\sqrt{Tn})$ & $\O(\frac{\xi^0}{R^3} + \frac{\sigma^2}{\mu n T} + \frac{\kappa G^2}{\mu R^2})$
    \tnote{b}& \cite{stich2018local} \\
    \thead{uniform with\\strong-growth \tnote{c}} & no & $\Omega((Tn)^{1/3})$ &
    $\O(\frac{\xi^0}{R^3}+\frac{\kappa \sigma^2}{\mu n T} + \frac{\kappa^2 \sigma^2}{\mu n T R})$ & \cite{haddadpour2019local} \\
    \thead{uniform with\\strong-growth} & no & $ \Omega(n*\text{poly-log} (T))$ &
    $\tilde \O(\frac{\kappa n H \xi^0}{\exp(R/(\kappa n))} + \frac{\sigma^2}{\mu n T})$ \tnote{d} & \cite{stich2019error} \\
    uniform & yes & $ \Omega(n*\text{poly-log} (T))$ &
    $\tilde \O( \frac{\kappa \xi^0}{T^2} + \frac{\kappa \sigma^2}{n \mu T} + \frac{\kappa^2 \sigma^2}{\mu T R} )$ & \cite{khaled2019tighter} \\
    \thead{uniform with\\strong-growth} & yes & $\Omega(n)$ &
    $\O(\frac{\kappa^4 \ln(TR^{-2})\xi^0}{T^2} + \frac{\kappa \sigma^2}{\mu n T} + \frac{\kappa^2 \sigma^2}{\mu T R})$ & \textbf{This Paper} \\

    \hline
    \end{tabular}
    }
    \begin{tablenotes}
    \item [a] $H$ is the length of inter-communication intervals.
    \item [b] $G$ is the uniform upper bound assumed for the $l_2$ norm of gradients in the corresponding work.
    \item [c] This noise model is defined in Assumption \ref{as: g}.
    \item [d] $\tilde \O (.)$ ignores the poly-logarithmic and constant factors.
    \end{tablenotes}
    \end{threeparttable}
\end{table}

In this work, we focus on smooth and strongly-convex functions with a very general noise model. The main contribution of this paper is to propose a communication strategy which requires only $R = \Omega(n)$ communication rounds to achieve performance that scales as $1/n$ in the number of workers. To the best of the authors' knowledge, this is the only work to show this result (without additional poly-logarithmic terms and constants).
Our analysis can also recover some of the best known rates for special cases, e.g., when $H$ is constant, where $H$ is defined as the length of intercommunication intervals.
A summary of our results compared to the available literature can be found in Table \ref{table: comparison}.

The rest of this paper is organized as follows. In the following subsection we outline the related literature and ongoing works. In Section  \ref{sec: Problem} we define the main problem and state our assumptions. We present our theoretical findings in Section \ref{sec: convergence} and the sketch of proofs in Section \ref{sec: sketch of proof}, followed by numerical experiments in Section \ref{sec: Numerical } and conclusion remarks in Section \ref{sec: conclustion}.

\subsection{Related Works}
There has been a lot of effort in the recent research to take into account the communication delays and training time in designing faster algorithms \cite{mcdonald2010distributed,zhang2015deep,bijral2016data,kairouz2019advances}.
See \cite{tang2020communication} for a comprehensive survey of communication efficient distributed training algorithms considering both system-level and algorithm-level optimizations.

 Many works study the communication complexity of distributed methods for convex optimization \cite{arjevani2015communication} \cite{woodworth2020local}  and statistical estimation \cite{zhang2013information}.
\cite{woodworth2020local} presents a rigorous comparison of Local SGD with $H$ local steps and mini-batch SGD with  $H$ times larger mini-batch size and the same number of communication rounds (we will refer to such a method as large mini-batch SGD) and show regimes in which each algorithm performs better: they show that Local SGD is strictly better than large mini-batch SGD when the functions are quadratic. Moreover, they prove a lower bound on the worst case of Local SGD that is higher than the worst-case error of large mini-batch SGD in a certain regime.
\cite{zhang2013information} studies the minimum amount of communication required to achieve centralized minimax-optimal rates by establishing lower bounds on minimax risks for distributed statistical estimation under a communication budget.

A parallel line of work studies the convergence of Local SGD with non-convex functions \cite{zhou2017convergence}.
\cite{yu2019parallel} was among the first works to present provable guarantees of Local SGD with linear speed up.
\cite{wang2018cooperative} and \cite{koloskova2020unified} present unified frameworks for analyzing decentralized SGD with local updates, elastic averaging or changing topology.
The follow-up work \cite{wang2018adaptive} presents ADACOMM, an adaptive communication strategy that starts with infrequent averaging and then increases the communication frequency in order to achieve a low error floor. They analyze the error-runtime trade-off of Local SGD

with nonconvex functions and propose communication times to achieve faster runtime.

In \textit{One-Shot Averaging} (OSA), workers perform local updates with no communication during the optimization until the end when they average their parameters. This method can be seen as an extreme case of Local SGD with $H=T$, on the opposite end of synchronous SGD \cite{mcdonald2009efficient,zinkevich2010parallelized,zhang2013communication,rosenblatt2016optimality,godichon2017rates}. \cite{dieuleveut2019communication} provides non-asymptotic analysis of mini-batch SGD and one-shot averaging as well as regimes in which mini-batch SGD could outperform one-shot averaging.

Another line of work reduces the communication by compressing the gradients and hence limiting the number of bits transmitted in every message between workers \cite{lin2017deep,alistarh2017qsgd,wangni2018gradient,stich2018sparsified,stich2019error}.

Asynchronous methods have been studied widely due to their advantages over synchronous methods which suffer from synchronization delays due to the slower workers \cite{olshevsky2018robust}.
\cite{wang2019matcha} studies the error-runtime trade-off in decentralized optimization and proposes MATCHA, an algorithm which parallelizes inter-node communication by decomposing the topology into matchings.
\cite{hendrikx2019accelerated} provides an accelerated stochastic algorithm for decentralized optimization of finite-sum objective functions that by carefully balancing the ratio between communications and computations match the rates of the best known sequential algorithms while having the network scaling of optimal batch algorithms.
However, these methods are relatively more involved and they  often require full knowledge of the network, solving a semi-definite program and/or calculating communication probabilities (schedules).

\subsection{Notation}
For a positive integer $s$, we define $[s]:=\{1,\ldots,s\}$. We use bold letters to represent vectors. We denote vectors of all $0$s and $1$s by $\mathbf{0}$ and $\mathbf{1}$, respectively. We use $\Vert \cdot \Vert$ for the Euclidean  norm.

\section{Problem Formulation}\label{sec: Problem}
Suppose there are $n$ workers  $\V=\{1, \ldots, n\}$, trying to minimize $F:\R^d \rightarrow \R$ in parallel.
We assume all workers have access to $F$ through noisy gradients. In Local SGD, workers perform local gradient steps and occasionally calculate the average of all workers' iterates.

Having access to the same objective function $F$ is of special interest if the data is stored in one place accessible to all machines or is distributed identically among workers with no memory constraints. We hope that results presented here can be extended to applications with heterogeneous data distributions \cite{khaled2019tighter}.

We will make the following additional assumptions.

\begin{assumption}\label{as: F}
	Function $F:\R^d\rightarrow \R$ is differentiable, $\mu$-strongly convex and $L$-smooth for $L\geq\mu>0$. In particular,
	\begin{align*}
		\frac{\mu}{2}\Vert \bx - \by \Vert^2 \leq F(\by) - F(\bx) - \langle \nabla F(\bx), \by - \bx \rangle \leq \frac{L}{2}\Vert \bx - \by \Vert^2, \qquad \forall x,y\in \R^d.
	\end{align*}
	We define $\kappa=L/\mu$ to be the condition number of $F$.
\end{assumption}
We make the following assumption on the noise of the stochastic gradients.
\begin{assumption}\label{as: g}
	Each worker $i$ has access to a gradient oracle which returns an unbiased estimate of the true gradient in the form $\hbg_i(\bx) = \nabla F(\bx) + \e_i$, such that $\e_i$ is a zero-mean conditionally independent random noise with its expected squared norm error bounded as
	\begin{align*}
	\E[\e_i] = \mathbf 0, \qquad \E[\Vert \e_i \Vert^2|\bx] \leq c\Vert \nabla F(\bx) \Vert^2 + \sigma^2,
	\end{align*}
	where $\sigma^2,c\geq0$ are constants.
\end{assumption}
To save space, we define $\hbg_i^t := \hbg(\bx_i^t)$ as the stochastic gradient of node $i$ at iteration $t$, and $\bg_i^t = \nabla F(\bx_i^t)$ as the true gradient at the same point.

The noise model of Assumption \ref{as: g} is very general and it includes the common case with uniformly bounded squared norm error when $c=0$. As it is noted by \cite{zhang2016parallel}, the advantage of periodic averaging compared to one-shot averaging only appears when $c/\sigma^2$ is large. Therefore, to study Local SGD, it is important to consider a noise model as in Assumption \ref{as: g} to capture the effects of frequent averaging.
Among the related works mentioned in Table \ref{table: comparison}, only \cite{stich2019error} and \cite{haddadpour2019local} analyze this noise model while the rest study the special case with $c=0$.
SGD under this noise model with $c>0$ and $\sigma^2=0$ was first studied in \cite{schmidt2013fast} under the name \textit{strong-growth condition}. Therefore we refer to the noise model considered in this work as \textit{uniform with strong-growth}.

In Local SGD, each worker $i$ holds a local parameter $\bx_i^t$ at iteration $t$ and a set $\I \subset [T]$ of communication times, and performs the following update:
\begin{align}\label{eq: Local SGD process}
\bx_i^{t+1} = \begin{cases}
x_i^t - \eta_t \hbg_i^t, \qquad &\text{if } t+1 \notin \I,\\
\frac{1}{n}\sum_{j=1}^n (\bx_j^t - \eta_t \hbg_j^t),
\qquad &\text{if } t+1 \in \I.
\end{cases}
\end{align}
When $\I = [T]$, we recover the fully synchronized parallel SGD, while $\I = \{T\}$ recovers one-shot averaging.
The pseudo code for Local SGD is provided as Algorithm \ref{alg: Local SGD}.
\begin{algorithm}
	\caption{Local SGD}
	\begin{algorithmic}[1]\label{alg: Local SGD}
		\STATE Input $\bx_i^0 = \bx^0$ for $i \in [n]$, total number of iterations $T$, the step-size sequence $\{\eta_t\}_{t=0}^{T-1}$ and $\I \subseteq [T]$
		\FOR{$t=0,\ldots,T-1$}
		\FOR{$j=1,\ldots,n$}
		\STATE evaluate a stochastic gradient $\hbg_j^t$
		\IF{$t+1 \in \mathcal{I}$}
		\STATE $\bx_j^{t+1} = \frac{1}{n}\sum_{i=1}^n (\bx_i^t - \eta_t \hbg_i^t)$
		\ELSE
		\STATE $\bx_j^{t+1} = \bx_j^t - \eta_t \hbg_j^t$
		\ENDIF
		\ENDFOR
		\ENDFOR
	\end{algorithmic}
\end{algorithm}

The main goal of this paper is to study the effect of communication times on the convergence of the Local SGD and provide better theoretical guarantees. In what follows, we claim that by carefully choosing the step size, linear speed-up of parallel SGD can be attained with only a small number of communication instances.

\section{Convergence Results}\label{sec: convergence}
In this section we present our convergence results for Local SGD.
In the following theorem, we show an upper bound for the sub-optimality error, in the sense of function value, for any choice of communication times $\I$.

Before proceeding with our results, let us introduce some notation. Let $0=\tau_0<\tau_1 < \ldots < \tau_R = T$ be the communication times. Define $H_i := \tau_{i+1} - \tau_i$, as the length of $i+1$-th inter-communication interval, for $i=0,\ldots,k-1$. Moreover, define $\bbx^t := (\sum_{i=1}^n \bx_i^t)/n$ as the the average of the iterates of all workers. Notice that $\bx_i^t = \bbx^t$ for $t\in \I$.

The main results of this paper will be obtained by specializing the following bound.

\begin{theorem}\label{thm: general}
	Suppose Assumptions \ref{as: F} and \ref{as: g} hold. Choose $\beta \geq 2\kappa^2 $ and communication times $\I = \{\tau_i|i=1,\ldots,R\}$ such that it holds
	\begin{align}\label{eq: beta condition}
	    9\kappa^2c \ln(1 + \frac{H_i - 1}{\tau_i + \beta}) + 2\kappa(1+\frac{c}{n}) - (\tau_i +1 + \beta)\leq 0, \qquad i=0,\ldots,R-1.
	\end{align}
	Set $\eta_k = 2/ (\mu (k+\beta))$. Then, using Algorithm \ref{alg: Local SGD}, we have
	\begin{align}\label{eq: opt E3}

	\E[F(\bbx^T)] - F^* \leq \frac{\beta^2 (F(\bbx^0) - F^*)}{T^2}  +  \frac{2L \sigma^2}{n \mu^2 T} + \frac{9L^2 \sigma^2}{ \mu^3 T^2} \sum_{t=0}^{T-1} \frac{t-\tau(t)}{t+\beta},
	\end{align}
	where $F^* := \min_{\bx} F(\bx)$ and $\tau(t) := \max\{t' \in \mathcal{I}| t' \leq t\}$ is the most recent communication time.
\end{theorem}
The last term in Equation \eqref{eq: opt E3} is due the to disagreement between workers (consensus error), introduced by local computations without any communication. As the inter-communication intervals become larger, $t-\tau(t)$ becomes larger as well and increases the overall optimization error. This term explains the trade-off between communication efficiency and the optimization error.

Note that condition \eqref{eq: beta condition} is mild. For instance, it suffices to set $\beta \geq \max \{9\kappa^2 c \ln(1 + T/(2\kappa^2)) + 2\kappa(1+c/n), 2\kappa^2\}$. Moreover, the bound in \eqref{eq: opt E3} is for the last iterate $T$, and does not require keeping track of a weighted average of all the iterates.

Theorem \ref{thm: general} not only bounds the optimization error, but introduces a methodological approach to select the communication times to achieve smaller errors. For the scenarios when the user can afford to have a certain number of a communications, they can select $\tau_i$ to minimize the last term in \eqref{eq: opt E3}.

We next discuss the implications of Theorem \ref{thm: general} under various conditions.

\paragraph{One-Shot Averaging.} Plugging $H=T$ in Theorem \ref{thm: general}, we obtain a convergence rate of $\O(\kappa^2 \sigma^2/(\mu T))$ without any linear speed-up. Among previous works, only \cite{khaled2019tighter} shows a similar result.

\subsection{Fixed-Length Intervals}
A simple way to select the communication times $\I$, is to split the whole training time $T$ to $R$ intervals of length at most $H$. Then we can use the following bound in Equation \eqref{eq: opt E3},
\begin{align*}
\sum_{t=0}^{T-1} \frac{t-\tau(t)}{t+\beta} \leq (H-1)\sum_{t=0}^{T-1} \frac{1}{t+\beta} \leq (H-1) \ln(1+\frac{T}{ \beta - 1}).
\end{align*}
We state this result formally in the following corollary.
\begin{corollary}
	Suppose assumptions of Theorem \ref{thm: general} hold and in addition, workers communicate at least once every $H$ iterations. Then,
	\begin{align}\label{eq: fixed-int}
	\E[F(\bbx^T)] - F^* \leq \frac{\beta^2(F(\bbx^0) - F^*)}{T^2} +  \frac{2L \sigma^2}{n \mu^2 T} + \frac{9L^2 \sigma^2 (H-1)}{ \mu^3 T^2} \ln(1 + \frac{T}{\beta - 1}).
	\end{align}
\end{corollary}

\paragraph{Linear Speed-Up.}
Setting $H= \O(T/(n \ln(T)))$ we achieve linear-speed up in the number of workers, which is equivalent to a communication complexity of $R = \Omega(n \ln(T))$. To the best of the authors' knowledge, this is the tightest communication complexity that is shown to achieve linear speed-up. \cite{khaled2019tighter} and \cite{stich2019error} have shown a similar communication complexity, however with slightly higher degrees of dependence on $\ln(T)$, e.g., $R=\Omega(n \ln(T)^2)$ in \cite{khaled2019tighter}.

\paragraph{Recovering Synchronized SGD.} When $H=1$, the the last term in \eqref{eq: fixed-int} disappears and we recover the convergence rate of parallel SGD, albeit, with a worse dependence on $\kappa$.

\subsection{Varying Intervals}
In the previous subsection, we observed that with our current analysis, having fixed-length inter-communication intervals, linear speed-up can be achieved with only $\Omega(n\ln(T))$ rounds of communications. A natural question that might arise is whether we can improve the result above even further.

Let us allow consecutive inter-communication intervals, i.e., $H_i := \tau_{i+1} - \tau_i$, grow linearly, where $0=\tau_0 <\tau_1<\ldots<\tau_R = T$ are the communication times. The following Theorem presents a performance guarantee for this choice of communication times.

\begin{theorem}\label{thm: logT}
	Suppose Assumptions \ref{as: F} and \ref{as: g} hold. Choose the maximum number of communications $1 \leq R \leq \sqrt{2T}$ and set $a:=\lceil 2T/R^2 \rceil \geq 1$, $H_i = a(i+1)$ and $\tau_{i+1} = \min(\tau_i + H_i, T)$ for $i=0,\ldots,R-1$. Choose $\beta \geq \max \{2 \kappa^2, 9\kappa^2c \max\{\ln(3), \ln(1+T/(R^2\kappa^2))\} + 2\kappa(1+c/n) \}$ and set $\eta_t = 2/ \mu (t+\beta)$. Then using Algorithm \ref{alg: Local SGD} we have,
	\begin{align}\label{eq: opt general linear H}
	\E[F(\bbx^T)] - F^* \leq \frac{ \beta^2 (F(\bbx^0) - F^*)}{T^2} +  \frac{2L \sigma^2}{n \mu^2 T}
	+ \frac{72L^2 \sigma^2}{\mu^3 TR}.
	\end{align}
\end{theorem}

The choice of communication times in Theorem \ref{thm: logT} aligns with the intuition that workers need to communicate more frequently at the beginning of the optimization. As the the step-sizes become smaller and workers' local parameters get closer to the global minimum, they diverge more slowly from each other and, hence, less communication is required to re-align them.

\paragraph{Linear Speed-Up.}
Choosing communication rounds $R = \Omega(n)$, we achieve an error that scales as $1/(nT)$ in the number of workers when $T=\Omega(n^2)$. {\bfseries This is the main result of this paper}: it shows that we can get a linear speedup in the number of workers by simply increasing the number of iterations while keeping the total number of communications bounded.

\section{Sketch of Proof}\label{sec: sketch of proof}
Here we give an outline of the proofs for the results presented in this paper. The proof of the following lemmas are left to the Appendix.

\paragraph{Perturbed Iterates.}
A common approach in analyzing parallel algorithms such as Local SGD is to study the evolution of the sequence $\{\bbx^t\}_{t\geq0}$. We have,
\begin{align}\label{eq: average x update}
    \bbx^{t+1} = \bbx^t - \frac{\eta_t}{n}\sum_{i=1}^n \hbg_i^t
    = \bbx^t - \eta_t \tbg^t,
\end{align}
where $\tbg^t := (\sum_{i=1}^n \hbg_i^t)/n$ is the average of the stochastic gradient estimates of all workers.

Let us define $\xi^t:= \E[F(\bbx^t)] - F^*$ to be the optimality error. The following lemma, which is similar to a part of the proof found in \cite{haddadpour2019local}, bounds the optimality error at each iteration recursively.
\begin{lemma}\label{lem: error decay}
    Let Assumptions \ref{as: F} and \ref{as: g} hold. Then,
    \begin{align*}
	    \xi^{t+1} \leq \xi^t(1 - \mu \eta_t) + \frac{L^2 \eta_t}{2n} \E \left[ \sum_{i=1}^n \Vert \bbx^t - \bx_i^t \Vert^2 \right] + \frac{\eta_t^2 L}{2} \E[\Vert \tbg^t \Vert_2^2 ]
	    - \frac{\eta_t}{2n} \E \left[ \sum_{i=1}^n \Vert \nabla F(\bx_i^t) \Vert^2\right].
	\end{align*}
\end{lemma}
Equipped with Lemma \ref{lem: error decay}, we can bound the consensus error ($\E[\sum_{i=1}^n \Vert \bbx^t - \bx_i^t \Vert^2]$) as well as the term $\E[\Vert \tbg^t \Vert^2]$ in the following lemmas.

\paragraph{Consensus Error.}
In the following lemmas, we utilize the structure of the problem to bound the consensus error recursively.
\begin{lemma}\label{lem: consensus 1}
	Let Assumptions \ref{as: F} and \ref{as: g} hold. Then,
	\begin{multline}\label{eq: consensus 2}
	\E\left[ \sum_{i=1}^n \Vert \bx_i^{t+1} - \bbx^{t+1} \Vert^2 \right] \leq \E\left[ \sum_{i=1}^n \Vert \bx_i^{t} - \bbx^t \Vert^2 \right](1 - 2\eta_t \mu + \eta_t^2 L^2) \\
	+ (n-1)\eta_t^2\sigma^2
	+ (1-\frac{1}{n})\eta_t^2 c\E [\sum_{i=1}^n \Vert g_i^t \Vert^2].
	\end{multline}
\end{lemma}

This lemma, bounds how much the consensus error grows at each iteration. Of course, when workers communicate, this error resets to zero and thus, we can calculate an upper bound for the consensus error, knowing the last iteration communication occurred and the step-size sequence. The following lemma takes care of that. Before stating the following lemma, let us define $G^t := \frac{1}{n}\sum_{i=1}^n \Vert \bg_i^t \Vert^2$.

\begin{lemma}\label{lem: consensus 2}
	Let assumptions of Theorem \ref{thm: general} hold. Then,
	\begin{align}
	\E\left[ \sum_{i=1}^n \Vert \bx_i^{t} - \bbx^t \Vert^2 \right] \leq

    9(n-1)\sum_{k=\tau(t)}^{t-1}\frac{c\E[G^k]+\sigma^2}{\mu^2(t+\beta)^2}.
	\end{align}
\end{lemma}

\paragraph{Variance.}
Our next lemma bounds $E[\Vert \tbg^t \Vert^2]$.
\begin{lemma}\label{lem: variance}
    Under Assumption \ref{as: g} we have,
    \begin{align*}
        \E [\Vert \tbg^t \Vert^2 ] \leq (1+\frac{c}{n})
        \E[G^t] + \frac{\sigma^2}{n}.
    \end{align*}
\end{lemma}

The proofs of  Theorems \ref{thm: general} and \ref{thm: logT} follow from these lemmas. Due to space constraints, these proofs are given in the supplementary information.

\section{Numerical Experiments}\label{sec: Numerical }
To verify our findings and compare different communication strategies in Local SGD, we performed the following numerical experiments.

 \subsection{Quadratic Function With Strong-Growth Condition}
As discussed in \cite{zhang2016parallel,dieuleveut2019communication}, under uniformly bounded variance, one-shot averaging performs asymptotically as well as mini-batch SGD. Therefore, to fully capture the importance of the choice of communication times $\I$, we design a \textit{hard} problem, where noise variance is uniform with strong-growth condition, defined in Assumption \ref{as: g}.  Let us define $F(\bx) = \E_\zeta f(\bx, \zeta)$ where,
\begin{align}\label{eq: f-zeta}
    f(\bx, \zeta) := \sum_{i=1}^d \frac{1}{2}x_i^2 (1 + z_{1,i}) + \bx^\top \bz_2,
\end{align}
$\zeta = (\bz_1, \bz_2)$, where $\bz_1, \bz_2 \in \R^d, z_{1,i}\sim \mathcal{N}(0,c_1)$ and $z_{2,i} \sim \mathcal{N}(0,c_2)$, $\forall i \in[d]$ are random variables with normal distributions. We assume at each iteration $t$, each worker $i$ samples a $\zeta_i^t$ and uses $\nabla f(\bx, \zeta_i^t)$ as a stochastic estimate of $\nabla F(\bx)$.  It is easy to verify that $F(\bx) = (1/2)\bx^2$ is $1$-strongly convex, $F^* = 0$ and $\E_\zeta[\Vert \nabla f(\bx, \zeta) - \nabla F(\bx) \Vert^2] = c \Vert \nabla F(\bx) \Vert^2 + \sigma^2$, where $c = c_1$ and $\sigma^2 = dc_2$.

We use Local SGD to minimize $F(\bx)$ using different communication strategies. We select $c_1=9, c_2=0.25, d=3$, $n=20$ machines and $T=1000$ iterations and the step-size sequence $\eta_t = 2/\mu(t+\beta)$ with $\beta=1$. We start each simulation from the initial point of $\bx^0 = \mathbf 1_d$ and repeat each simulation $500$ times. The average of the results are reported in Figures \ref{fig: res2}(a) and \ref{fig: res2}(b). Moreover, average performance of Local SGD with different number of workers $n$ and the communication strategy proposed in this paper with $R=n$ is shown in Figure \ref{fig: res2}(c) along with the respective convergence rate of $\sigma^2/(\mu n t)$.

\begin{figure}
	\centering
	\begin{subfigure}[b]{0.325\textwidth}
		\includegraphics[width=\textwidth]{figures/iteration_c3_d3_n20_T1000_500x.png}
		\caption{Error over iterations.}
	\end{subfigure}
	\begin{subfigure}[b]{0.325\textwidth}
		\includegraphics[width=\textwidth]{figures/communication_c3_d3_n20_T1000_500x.png}
		\caption{Error over communications.}
	\end{subfigure}
	\begin{subfigure}[b]{0.325\textwidth}
		\includegraphics[width=\textwidth]{figures/c3_d3_sigmap5_T4000_32x_speedup.png}
		\caption{Speed-up in the network size.}
	\end{subfigure}
	\caption{Local SGD with different communication strategies with $F(\bx)=\E_\zeta f(\bx, \zeta)$ defined in \eqref{eq: f-zeta}, $c=9, \sigma=0.5, d=3, \beta=1$. Figures (a) and (b) show the error of different communication methods over iteration and communication round, respectively, with a fixed network size of $n=20$. Figure (c) shows the convergence of Local SGD with the communication method proposed in this paper ($n$ communication rounds) for different network sizes. The dashed lines are showing $\sigma^2/(\mu n t)$.}
	\label{fig: res2}
\end{figure}

Figure \ref{fig: res2}(a) shows that {\em the method with increasing communication intervals ($H_i = 3(i+1)$) proposed in this paper performs better than all the other communication strategies in the transient time as well as in the final error}, requiring much less communication rounds. In particular, the method with the same number of communications but fixed intervals ($H=25$), has both higher transient error and final error. This affirms the advantages of having more frequent communication at the beginning of the optimization. Indeed, observe that in Figures \ref{fig: res2}(a), the only method which outperforms the method we propose is the one that communicates at every step.

Figure \ref{fig: res2}(b) reveals the effectiveness of each communication round in different methods. We observe that there's an initial spike in the initial communications in methods $H=5$ and $H_i = 3(i+1)$. This is mainly because these two methods have more frequent communications at the beginning of the training, where the step-sizes are larger. Other methods experience this increase as well, however since they communicate later, it's not observed in this figure. Indeed, observe that the only method which makes better use of communication periods than our method in Figure \ref{fig: res2}(b) is one-shot averaging, which is not competitive in terms of its final error.

Figure \ref{fig: res2}(c) verifies that linear-speed up in the number of workers can be achieved with only $R=n$ communication rounds. Moreover, it shows that Local SGD achieves the optimal convergence rate of $\sigma^2/(n \mu T)$ asymptotically.

\subsection{Regularized Logistic Regression}
We also performed additional numerical experiments with regularized logistic regression using two real data sets. Due to space constraints, the results are presented in supplementary information.

\section{Conclusion}\label{sec: conclustion}
We have presented a new  analysis of Local SGD and studied the effect of choice of communication times on the final optimality error. We proposed a communication strategy which achieves linear speed-up in the number of workers with only $\Omega(n)$ communication rounds, independent of the total number of iterations $T$.
Numerical experiments further confirmed our theoretical findings, and showed that our method achieves smaller error than previous methods using fewer communications.

\section*{Broader Impact}

The results presented in this paper could help speed up training in many machine learning applications. The potential broader impacts are therefore somewhat generic for machine learning: this research could amplify  all the benefits ML can bring by making it cheaper in terms of computational cost, while simultaneously amplifying all the ways ML could be misused.

\begin{ack}

\end{ack}

\small
\bibliographystyle{alpha}
\bibliography{References}

\newpage
\appendix
\section{Missing Proofs}
Let us define the following notations used in the proofs presented here.
\begin{align*}
    \bbg^t := (\sum_{i=1}^n \bg_i^t)/n, \qquad G^t := \frac{1}{n}\sum_{i=1}^n \Vert \bg_i^t \Vert^2, \qquad & \e_i^t := \hbg_i^t - \bg_i^t.
\end{align*}
Moreover, define $\F^t:=\{\bx_i^k, \hbg_i^k | 1\leq i \leq n, 0\leq k \leq t-1 \} \cup \{\bx_i^t | 1 \leq i \leq n\}$.

\begin{lemmapp}[\ref{lem: error decay}]
    Let Assumptions \ref{as: F} and \ref{as: g} hold. Then,
    \begin{align*}
	    \xi^{t+1} \leq \xi^t(1 - \mu \eta_t) + \frac{L^2 \eta_t}{2n} \E \left[ \sum_{i=1}^n \Vert \bbx^t - \bx_i^t \Vert^2 \right] + \frac{\eta_t^2 L}{2} \E[\Vert \tbg^t \Vert_2^2 ]
	    - \frac{\eta_t}{2n} \E \left[\sum_{i=1}^n \Vert \nabla F(\bx_i^t) \Vert^2\right].
	\end{align*}
\end{lemmapp}

\begin{proof}[Proof of Lemma \ref{lem: error decay}]

	By Assumption \ref{as: F} and \eqref{eq: average x update} we have,
	\begin{align}\label{eq: opt E1}
	\E[F(\bbx^{t+1}) - F(\bbx^t)] \leq -\eta_t \E[\langle \nabla F(\bbx^t), \tbg^t \rangle ] + \frac{\eta_t^2 L}{2} \E[\Vert \tbg^t \Vert_2^2 ].
	\end{align}
	We bound the first term on the R.H.S of \eqref{eq: opt E1} by conditioning on $\F^t$ as follows:
	\begin{align} \label{eq: opt E2}
	\E[\langle  \nabla F(\bbx^t), \tbg^t \rangle | \mathcal{F}^{t} ] &= \frac{1}{n} \sum_{i=1}^n \langle \nabla F(\bbx^t), \E[\hbg_i^t | \bx_i^t] \rangle \nonumber \\
	&= \frac{1}{2} \Vert \nabla F(\bbx^t) \Vert^2 + \frac{1}{2n} \sum_{i=1}^n \Vert \nabla F(\bx_i^t) \Vert^2 - \frac{1}{2n} \sum_{i=1}^n \Vert \nabla F(\bbx^t) - \nabla F(\bx_i^t) \Vert^2  \nonumber\\
	& \geq \mu (F(\bbx^t) - F^*) + \frac{1}{2n} \sum_{i=1}^n \Vert \nabla F(\bx_i^t) \Vert^2  - \frac{L^2}{2n} \sum_{i=1}^n \Vert \bbx^t - \bx_i^t \Vert^2,
	\end{align}
	where we used $\langle a, b \rangle  = \frac{1}{2} \Vert a \Vert ^2 + \frac{1}{2} \Vert b\Vert^2 - \frac{1}{2} \Vert a-b \Vert ^2$ in the second equation and $(1/2)\Vert \nabla F(\bx) \Vert^2 \geq \mu (F(\bx) - F^*)$ as well as smoothness of $F$ in the last inequality.
	Taking full expectation of \eqref{eq: opt E2} and combining it with \eqref{eq: opt E1} concludes the lemma.

\end{proof}

We state an important identity in the following lemma.
\begin{lemma}\label{lem: u - ubar}
    Let $\bu_1, \ldots \bu_n \in \R^d$ be $n$ arbitrary vectors. Define $\bar \bu = (\sum_{i=1}^n \bu_i)/n$. Then,
    \begin{align*}
        \sum_{i=1}^n \Vert \bu_i - \bar \bu \Vert^2 = \sum_{i=1}^n \Vert \bu_i \Vert^2 - n \Vert \bar \bu \Vert^2.
    \end{align*}
\end{lemma}

\begin{proof}
We have
    \begin{align*}
        \sum_{i=1}^n \Vert \bu_i - \bar \bu \Vert^2 &= \sum_{i=1}^n \Vert \bu_i \Vert^2 + n \Vert \bar \bu \Vert^2 - 2\sum_{i=1}^n \langle \bu_i, \bar \bu \rangle \\
        &= \sum_{i=1}^n \Vert \bu_i \Vert^2 + n \Vert \bar \bu \Vert^2 - 2n \langle \bar \bu, \bar \bu \rangle \\
        & = \sum_{i=1}^n \Vert \bu_i \Vert^2 - n \Vert \bar \bu \Vert^2.
    \end{align*}
\end{proof}

\begin{lemmapp}[\ref{lem: consensus 1}]
	Let Assumptions \ref{as: F} and \ref{as: g} hold. Then,
	\begin{multline*}
	\E\left[ \sum_{i=1}^n \Vert \bx_i^{t+1} - \bbx^{t+1} \Vert^2 \right] \leq \E\left[ \sum_{i=1}^n \Vert \bx_i^{t} - \bbx^t \Vert^2 \right](1 - 2\eta_t \mu + \eta_t^2 L^2) \\ + (n-1)\eta_t^2\sigma^2 + (1-\frac{1}{n})\eta_t^2 c\E [\sum_{i=1}^n \Vert g_i^t \Vert^2].
	\end{multline*}
\end{lemmapp}
\begin{proof}[Proof of Lemma \ref{lem: consensus 1}]

	We have,
	\begin{align}\label{eq: consensus var}
	\E [  \sum_{i=1}^{n} \Vert \bx_i^{t+1} - \bbx^{t+1} \Vert^2 ] = \sum_{i=1}^{n} \Vert \E[\bx_i^{t+1} - \bbx^{t+1}] \Vert^2 + \sum_{i=1}^{n} \E \left[\Vert \bx_i^{t+1} - \bbx^{t+1} - \E[\bx_i^{t+1} - \bbx^{t+1}] \Vert^2 \right].
	\end{align}
	Let us consider the first term on the right hand side of \eqref{eq: consensus var}. Taking conditional expectation of both sides of \eqref{eq: average x update} implies,
	\begin{align} \label{eq: consensus 1}
	\sum_{i=1 }^{n} \Vert \E[\bx_i^{t+1} - \bbx^{t+1} | \ \F^{t}] \Vert^2 &= \sum_{i =1}^{n} \Vert \bx_i^t - \bbx^t - \eta_t(\bg_i^t - \bar \bg^t) \Vert^2
	\nonumber \\
	&= \sum_{i=1}^{n} \left(\Vert \bx_i^t - \bbx^t \Vert^2 + \eta_t^2\Vert \bg_i^t - \bar \bg^t \Vert^2 - 2 \eta_t \langle \bg_i^t, \bx_i^t - \bbx^t \rangle \right)
	\end{align}
	By $L$-smoothness of $F$,
	\begin{align} \label{eq: consensus L}
	\sum_{i=1}^n \Vert \bg_i^t - \bar \bg^t \Vert^2 = \frac{1}{n} \sum_{\{i,j\}} \Vert \bg_i^t - \bg_j^t \Vert^2 \leq \frac{L^2}{n} \sum_{\{i,j\}} \Vert \bx_i^t - \bx_j^t \Vert^2 = L^2 \sum_{i=1}^n \Vert \bx_i^t - \bbx^t \Vert^2.
	\end{align}
	Moreover, by $\mu$-strong convexity of $F$,
	\begin{multline} \label{eq: consensus mu}
	\sum_{i=1}^n \langle \bg_i^t, \bx_i^t - \bbx^t \rangle = \sum_{i=1}^n  \langle \bg_i^t, \frac{1}{n} \sum_{j=1}^n (\bx_i^t - \bx_j^t) \rangle \\
	= \frac{1}{n} \sum_{\{i,j\}} \langle \bg_i^t - \bg_j^t, \bx_i^t - \bx_j^t \rangle \geq \frac{\mu}{n} \sum_{\{i,j\}} \Vert \bx_i - \bx_j \Vert^2 = \mu \sum_{i=1}^{n} \Vert \bx_i^t - \bbx^t \Vert^2,
	\end{multline}
	where we used $\langle \nabla F(\bx) - \nabla F(\by), \bx - \by \rangle \geq \mu \Vert \bx - \by \Vert^2$ in the inequality.
	Combining \eqref{eq: consensus 1}-\eqref{eq: consensus mu} we obtain,
	\begin{align*}
	\sum_{i=1 }^{n} \Vert \E[\bx_i^{t+1} - \bbx^{t+1} | \F^t] \Vert^2 &\leq \sum_{i=1}^{n} \Vert \bx_i^t - \bbx^t \Vert^2 \left( 1 - 2\eta_t \mu + \eta_t^2L^2 \right),
	\end{align*}
	Now, consider the second term on the right hand side of \eqref{eq: consensus var}.
	We have,
	\begin{align*}
	    \sum_{i=1}^{n} \E \left[\left\Vert \bx_i^{t+1} - \bbx^{t+1} - \E[\bx_i^{t+1} - \bbx^{t+1}] \right\Vert^2 | \F^t \right] &=
	    \sum_{i=1}^{n} \E \left[\left\Vert \bx_i^{t+1} - \E[\bx_i^{t+1}] - (\bbx^{t+1} - \E[\bbx^{t+1}]) \right\Vert^2 | \F^t \right] \\
	    &= \eta_t^2 \sum_{i=1}^{n} \E \left[ \left\Vert \e_i^t - \bar \e^t \right\Vert^2 | \F^t \right] \\
	    &= \eta_t^2 \left(\sum_{i=1}^{n} \E \left[ \left\Vert \e_i^t \right\Vert^2 | \F^t \right]- n \E \left[ \left\Vert \bar \e^t \right\Vert^2 |\F^t \right]\right) \\
	    &= \eta_t^2 \sum_{i=1}^{n} \E \left[ \left\Vert \e_i^t \right\Vert^2 | \F^t \right](1-\frac{1}{n}) \\
	    &\leq (n-1)\eta_t^2\sigma^2 + (1-\frac{1}{n})\eta_t^2 c\sum_{i=1}^n \Vert g_i^t \Vert^2,
	\end{align*}
	where $\e_i^t$ are defined at the beginning of this section and $\bar \e^t := (\sum_{i=1}^n \e_i^t)/n$ and we used Lemma \ref{lem: u - ubar} in the third equation and the conditional independence of $\e_i^t$ to use $\E[\Vert \bar \e^t \Vert^2 | \F^t] = (1/n^2)\sum_{i=1}^n \E[\Vert \e_i^t \Vert^2 | \F^t]$ in the last equality.

	Taking full expectation of the two relations above with respect to $\F^t$ and combining them with \eqref{eq: consensus var} completes the proof.
\end{proof}

\begin{lemmapp}[\ref{lem: consensus 2}]
	Let assumptions of Theorem \ref{thm: general} hold. Then,
	\begin{align*}
	\E\left[ \sum_{i=1}^n \Vert \bx_i^{t} - \bbx^t \Vert^2 \right] \leq

    9(n-1)\sum_{k=\tau(t)}^{t-1}\frac{c\E[G^k]+\sigma^2}{\mu^2(t+\beta)^2}.
	\end{align*}
\end{lemmapp}

Before proving this lemma, let us state and prove the following lemma.
\begin{lemma}\label{lem: products}
	Let $b \geq a > 2$ be integers. Define $\Phi(a,b) = \prod_{i=a}^b \left( 1 - \frac{2}{i} \right)$. We then have $
	\Phi(a,b) \leq \left( \frac{a}{b+1} \right)^{2}.$
\end{lemma}
\begin{proof}
	Indeed,
	\begin{align*}
	\ln (\Phi(a,b))  =  \sum_{i=a}^b \ln \left( 1 - \frac{2}{i} \right)
	\leq  \sum_{i=a}^b - \frac{2}{i}
	\leq  -  2\left[ \ln (b+1) - \ln (a) \right].
	\end{align*}
	where we used the inequality $\ln (1-x) \leq -x$ as well as the standard technique of viewing $\sum_{i=a}^b 1/i$ as a Riemann sum for $\int_{a}^{b+1} 1/x ~dx$ and observing that the Riemann sum overstates the integral. Exponentiating both sides now implies the lemma.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lem: consensus 2}]
	Define $a^k =  \E\left[ \sum_{i=1}^n \Vert \bx_i^{k} - \bbx^k \Vert^2 \right]$ and $\Delta_k = (1 - 2\eta_k \mu + \eta_k^2 L^2)$ for $k\geq 0$ . By Lemma \ref{lem: consensus 1},
	\begin{align*}
	a^{t} &\leq \Delta_{t-1}a^{t-1}  + \eta_{t-1}^2(n-1)(\sigma^2 + c \E[G^{t-1}]) \\
	& \leq \Delta_{t-1}(\Delta_{t-2}a^{t-2} + \eta_{t-2}^2(n-1)(\sigma^2+c\E[G^{t-2}])) + \eta_{t-1}^2(n-1)(\sigma^2+c\E[G^{t-1}]) \\
	& \leq \ldots \leq \prod_{k=\tau(t)}^{t-1} \Delta_k a^{\tau(t)} +
	(n-1)\sum_{k=\tau(t)}^{t-1} \eta_k^2(\sigma^2+c\E[G^k])\prod_{i=k+1}^{t-1} \Delta_i \\
	&= (n-1)\sum_{k=\tau(t)}^{t-1} \eta_k^2(\sigma^2+c\E[G^k])\prod_{i=k+1}^{t-1} \Delta_i,
	\end{align*}
	where we used $a^{\tau(t)}= 0$ in the last equation.

	By the choice of stepsize and $\beta\geq 2\kappa^2$,  we have
	\begin{align*}
	    \Delta_k = 1-\frac{4}{(k+\beta)} + \frac{4L^2}{\mu^2 (k+\beta)^2} \leq 1 - \frac{4}{k+\beta} + \frac{4\kappa^2}{(k+\beta)\beta}
	    \leq 1 - \frac{4}{k+\beta} + \frac{2}{(k+\beta)} =  1 - \frac{2}{k+\beta}.
	\end{align*}
	Therefore, by Lemma \ref{lem: products},
	\begin{align*}
	a^t \leq (n-1) \sum_{k = \tau(t)}^{t-1} \frac{4(\sigma^2+c\E[G^k])}{\mu^2 (k+\beta)^2 } \frac{(k+\beta+1)^2}{(t + \beta)^2} \leq (n-1) \sum_{k = \tau(t)}^{t-1} \frac{9(\sigma^2+c\E[G^k])}{\mu^2 (t+\beta)^2},

	\end{align*}
	where we used $(k+\beta + 1)/(k+\beta)\leq (\beta+1)/\beta \leq 3/2$ since $\beta \geq 2\kappa^2 \geq 2$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lem: variance}]
    We have,
    \begin{align*}
        \E[\Vert \tbg^t \Vert^2|\F^t] = \E[\Vert \bbg^t + \bar \e^t \Vert^2 | \F_t] = \Vert \bbg^t \Vert^2 + \E[\Vert \bar \e^t \Vert^2| \F^t] \leq  \frac{1}{n}\sum_{i=1}^n \Vert \bg_i^t \Vert^2 + \frac{1}{n^2}\sum_{i=1}^n(\sigma^2 + c\Vert \bg_i^t \Vert^2),
    \end{align*}
    where in the last inequality we used Lemma \ref{lem: u - ubar} and the conditional independency of $\e_i^t$ to separate the noise terms.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm: general}]

	Combining Equations Lemmas \ref{lem: error decay}-\ref{lem: variance} and plugging $\eta_t = 2/(\mu(t+\beta))$ we obtain
	\begin{multline*}
	    \xi^{t+1} \leq \xi^t(1 - \mu \eta_t) +
	    \frac{9L^2}{\mu^3(t+\beta)^3}
	    \sum_{k=\tau(t)}^{t-1} (c\E[G^k]+\sigma^2)
	    \\
	    + \frac{2L}{\mu^2(t+\beta)^2} \left( (1+\frac{c}{n}) \E[G^t] + \frac{\sigma^2}{n} \right)
	    - \frac{1}{\mu(t+\beta)} \E[G^t].
	\end{multline*}

	Let us multiply both sides of relation above by $(t+\beta)^2$

	and use the following inequality
	\begin{align*}
	    (1-\mu \eta_t)(t+\beta)^2 = (1 - \frac{2}{t+\beta})(t+\beta)^2 = (t+\beta)^2 - 2(t+\beta) < (t+\beta-1)^2,
	\end{align*}
	to obtain,
	\begin{multline*}
	\xi^{t+1} (t+\beta)^2 \leq \xi^t (t+\beta-1)^2 + \frac{2L \sigma^2}{n \mu^2} +
	\frac{9L^2}{\mu^3(t+\beta)} \sum_{k=\tau(t)}^{t-1} (c\E[G^k]+\sigma^2) \\ +
	\left( \frac{2L}{\mu^2}(1+\frac{c}{n}) - \frac{t+\beta}{\mu} \right)\E[G^t].
	\end{multline*}
	Summing relation above for $t=\tau_i,\ldots,\tau_{i+1}-1$, where $\tau_i,\tau_{i+1}\in \I$ are two consecutive communication times, implies,
	\begin{multline*}
	\xi^{\tau_{i+1}}(\tau_{i+1} + \beta -1 )^2 \leq \xi^{\tau_i}(\tau_{i} + \beta -1 )^2  +  \frac{2L \sigma^2}{n \mu^2}(\tau_{i+1} - \tau_i)
	+ \frac{9L^2\sigma^2}{\mu^3}\sum_{t=\tau_i}^{\tau_{i+1}-1} \frac{t-\tau_i}{t+\beta} \\
	+ \sum_{t=\tau_i}^{\tau_{i+1}-1}\E[G^t] \left( \sum_{k=t+1}^{\tau_{i+1}-1}\frac{9L^2 c}{\mu^3(k+\beta)} + \frac{2L}{\mu^2}(1+\frac{c}{n}) - \frac{t+\beta}{\mu} \right).
	\end{multline*}
	Each of the coefficients of $\E[G^t]$ in above can be bounded by,
	\begin{align*}
	    \sum_{k=t+1}^{\tau_{i+1}-1}\frac{9L^2 c}{\mu^3(k+\beta)} + \frac{2L}{\mu^2}(1+\frac{c}{n}) - \frac{t+\beta}{\mu} &\leq
	    \frac{9L^2c}{\mu^3}\ln(\frac{\tau_{i+1}+\beta -1 }{\tau_i + \beta})
	    + \frac{2L}{\mu^2}(1+\frac{c}{n}) - \frac{\tau_i + 1 +\beta}{\mu} \\
	    & = \frac{1}{\mu}\left( 9\kappa^2c \ln(1 + \frac{H_i - 1}{\tau_i + \beta}) + 2\kappa(1+\frac{c}{n}) - (\tau_i +1 + \beta)\right) \\
	    &\leq 0,
	\end{align*}
	where we used $\sum_{k=t_1+1}^{t_2} 1/k \leq \int_{t_1}^{t_2} dx/x = \ln(t_2/t_1)$ in the first inequality and the last inequality comes from the assumption of the theorem. Now that the coefficients of $\E[G^k]$ are non-positive, we can simply ignore them and obtain,
	\begin{align*}
	\xi^{\tau_{i+1}}(\tau_{i+1} + \beta -1 )^2 \leq \xi^{\tau_i}(\tau_{i} + \beta -1 )^2  +  \frac{2L \sigma^2}{n \mu^2}(\tau_{i+1} - \tau_i)
	+ \frac{9L^2\sigma^2}{\mu^3}\sum_{t=\tau_i}^{\tau_{i+1}-1} \frac{t-\tau_i}{t+\beta}.
	\end{align*}
	Recursing relation above for $i=0,\ldots,R-1$ implies,
	\begin{align*}
	    \xi^{T}(T + \beta -1 )^2 \leq \xi^{0}( \beta -1 )^2  +  \frac{2L \sigma^2}{n \mu^2}T
	+ \frac{9L^2\sigma^2}{\mu^3}\sum_{t=0}^{T-1} \frac{t-\tau(t)}{t+\beta}.
	\end{align*}
	Dividing both sides by $(T+\beta -1 )^2$ concludes the proof.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm: logT}]
	We have,
	\begin{align*}
	\tau_j = \tau_0 + \sum_{i=0}^{j-1} H_i = a \frac{j(j+1)}{2}, \qquad j=0,\ldots,k-1.
	\end{align*}
	Hence,
	\begin{align*}
	    1 + \frac{H_0-1}{\tau_0 + \beta} &= 1 + \frac{a-1}{\beta} \leq 1 + \frac{T}{R^2\kappa^2},\\
	    1 + \frac{H_i-1}{\tau_i + \beta} &\leq 1 + \frac{a(i+1)}{\frac{ai(i+1)}{2}} \leq 3, \qquad i\geq 1.
	\end{align*}
	Thus, $9\kappa^2c \ln(1 + \frac{H_i - 1}{\tau_i + \beta}) + 2\kappa(1+\frac{c}{n}) - (\tau_i +1 + \beta)\leq 0, i=0,\ldots,R-1$ and we can use Theorem \ref{thm: general}.
	Moreover,
	\begin{align*}
	\sum_{t=0}^{T-1} \frac{t-\tau(t)}{t+\beta} &\leq \sum_{j=0}^{R-1} \sum_{i=1}^{H_j - 1} \frac{i}{\tau_j + i + \beta } \leq H_0 + \sum_{j=1}^{R-1} \sum_{i=1}^{H_j - 1} \frac{i}{\tau_j + 1 + \beta } \\
	&= a + \sum_{j=1}^{R-1} \frac{H_j (H_j - 1)}{2(\tau_j + 1 + \beta)} = a + \sum_{j=1}^{R-1} \frac{a(j+1) (a(j+1) - 1)}{a j(j+1) + 2(1 + \beta)} \\
	&\leq a + \sum_{j=1}^{R-1} \frac{a^2 (j+1)^2 }{aj(j+1)} \leq 2aR.

	\end{align*}

    Plugging the values of $R$ and $a$ implies,
	\[ \sum_{t=0}^{T-1} \frac{t-\tau(t)}{t+\beta} \leq 2aR \leq 2(\frac{2T}{R^2}+1)R = \frac{4T}{R} + 2R \leq \frac{4T}{R} + \frac{4T}{R} = \frac{8T}{R}, \]
    where we used $R\leq \sqrt{2T}$ in the last inequality. Using the relation above together with Theorem \ref{thm: general} concludes the proof.
\end{proof}

\newpage
\section{More Numerical Experiments}
In this section we present more numerical experiments as well as discussion on how different hyper-parameters were selected.

\subsection{An Experiment With Real Data: Logistic Regression for Hospitalization Prediction}
We consider binary classification and select $l_2$-regularized logistic regression with its corresponding loss function as the objective function $F$ to be minimized, i.e.,
\begin{align*}
	F(\bx) = \frac{1}{N} \sum_{j=1}^N \left( \ln(1+\exp(\bx^\top \mathbf A_j)) - 1_{(b_j = 1)} \bx^\top \mathbf A_j \right)
	+ \frac{\lambda}{2} \Vert \bx \Vert_2^2,
\end{align*}
where $\lambda$ is the regularization parameter, $\mathbf A_j \in \R^d$ and $b_j \in \{ 0,1 \}$, $j=1,\ldots,N$ are features (data points) and their corresponding class labels, respectively.
We used a real data set from the American College of Surgeons National Surgical Quality Improvement Program (NSQIP) to predict whether a specific patient will be re-admitted within 30 days from discharge after general surgery. This data set consists of $N = 722,101$ data points for training with $d=231$ features including (i) baseline demographic and health care status characteristics, (ii) procedure information and (iii) pre-operative, intra-operative, and post-operative variables.

We perform Local SGD with $n=20$ workers, $\lambda = 0.05$, $\beta = 1$, $T=500$ iterations and batch size of $b=1$  with four different communication strategies for $H$:
(i) one from \cite{stich2018local} with the choice of $\sqrt{T/(bn)} \approx 7$, (ii) one from \cite{haddadpour2019local} with the choice of $T^{2/3}/(nb)^{1/3} \approx 36$, (iii) a strategy with the time varying communication intervals with $H_i = a(i+1), a = 5$ and $R = 20$ communication rounds proposed in this paper, (iv) a strategy with the same number of communications however with a fixed $H=T/n = 50$, and finally, (v) selecting $H = T$ for one-shot averaging.
Each simulation has been repeated $10$ times and the average of their performance is reported in Figure \ref{fig: res1}.

\begin{figure}
	\centering
	\begin{subfigure}[b]{0.49\textwidth}
		\includegraphics[width=\textwidth]{figures/iteration_n20_T500_10x.png}
		\caption{Error over iterations.}
	\end{subfigure}
	\begin{subfigure}[b]{0.49\textwidth}
		\includegraphics[width=\textwidth]{figures/communication_n20_T500_10x.png}
		\caption{Error over communication rounds.}
	\end{subfigure}
	\caption{Local SGD with different communication strategies on the NSQIP data set.}
	\label{fig: res1}
\end{figure}

It can be seen that all four communication strategies have similar behavior over the number of iterations. However, the methods proposed in this paper reach the same error level with much less communication rounds, i.e., $20$ versus $143$ (\cite{haddadpour2019local}) or $28$(\cite{stich2018local}).
Surprisingly, one-shot averaging performs just as well as synchronized SGD. This could be due to the fact that our bounds analyze the worst-case scenario. Studying one-shot averaging and cases where it performs well is out of the scope of this paper and is left to future work.

We also notice that, as we get closer to the end of training, the methods with fixed-length communication intervals, have smaller improvement with each communication (see Figure \ref{fig: res1}-b). However, with the growing communication interval suggested in this paper, each communication decreases the error significantly. This further confirms that less frequent communication is needed towards the end of training.

\subsection{Logistic Regression on a9a Data Set}
Here we repeat the experiment above on the a9a data set from LIBSVM \cite{CC01a}. This data set consists of $N=32561$ data points for training with $d = 123$ features.
We use same parameters as we did for (NSQIP) data set, except this time we repeat each training $50$ times due to smaller size of the data set. The results are presented in Figure \ref{fig: res3}. Here, we observe a similar performance of different communication strategies.

\begin{figure}
	\centering
	\begin{subfigure}[b]{0.49\textwidth}
		\includegraphics[width=\textwidth]{figures/iteration_n20_T500_50x_a9a.png}
		\caption{Error over iterations.}
	\end{subfigure}
	\begin{subfigure}[b]{0.49\textwidth}
		\includegraphics[width=\textwidth]{figures/communication_n20_T500_50x_a9a.png}
		\caption{Error over communication rounds.}
	\end{subfigure}
	\caption{Local SGD with different communication strategies on the a9a data set.}
	\label{fig: res3}
\end{figure}

\subsection{Discussion}
We note that other communication strategies proposed in related works have often suggested their own step-size sequence or sometimes a fixed step-size. Designing an experiment to have a completely fair comparison of different methods while capturing all possible applications is not easy, if possible at all. Therefore, to make our comparison more fair, we used the same step-size sequence with $\beta = 1$ for all methods in each experiment.
Moreover, the central goal of the numerical experiments here, is to demonstrate the effectiveness of our suggested communication strategy, using minimal number of communication rounds.

\end{document}

config: arxiv


TITLE: Correspondence between Viterbi algorithm and Smith-Waterman
QUESTION [4 upvotes]: Viterbi is an algorithm for finding the maximum likelihood assignment to the hidden variables of an HMM, given the observed variables (we know the transition and emission probabilities of the HMM).  However, the dynamic programming algorithm that finds the best alignment between two strings (Smith-Waterman), is also referred to as Viterbi.  I'm trying to understand why Smith-Waterman is an instantiation of Viterbi.  Specifically, what is the HMM that represents the alignment problem, what are the possible values for the hidden variables, what are the emission probabilities for each hidden variable, and what is the observed data.  Can you help me see the correspondence?

REPLY [1 votes]: I think the best way of seeing the similarities is to see both algorithms as shortest path methods: Given a graph of a certain diameter, you find the shortest path between a start and a finish node recursively by first finding all shortest paths of length 1, then using that to find all shortest paths of length 2, and so on. When you reach the diameter of the graph, you know you have found the global minimum.

In the case of a Hidden Markov Model, the nodes in the graph are value assignment pairs $(s_i,v)$, where $s_i$ is a hidden variable, and $v$ is one of its values. Two pairs are then connected if they assign values to two consecutive variables, $s_i$ and $s_{i+1}$.
One will typically also add a dummy start node that connects to all the time $1$ variable-value pairs, $(s_1,v)$, and a finish node to which all the time $n$ variable-value pairs $(s_n,v)$ are connected. A value assignment for the whole sequences is then a path between these two dummy nodes.
In the case of string matching algorithms, the nodes are positions $(i,j)$, indicating how much of each of the two strings we have consumed so far. The possible transitions are determined by the editing operations you have access to: A deletion will for instance correspond to a step from $(i,j)$ to $(i+1,j)$ since it consumes input character but no output characters.
In this case, an alignment corresponds to a path from the position $(0,0)$ to the position $(n,m)$ if you require both strings to be consumed entirely. If, on the other hand, you only require the first string to be consumed, any path terminating at the wall $\{(n,k):\, k=1,2,\ldots,m\}$ will do.

In both cases, the available steps from node to node need to be equipped with price tags for the minimization problem to make sense. In the case of the HMM, the step from $(s_i,v_i)$ to $(s_{i+1},v_{i+1})$ should be assigned the logarithmic price
$$
\log \frac{1}{p(s_{i+1}\, |\,s_i)} + \frac{1}{\log p(e\, |\, s_{i+1})},
$$
where $p(s_{i+1}\, |\,s_i)$ is the transition probability, and $p(e\, |\, s_{i+1})$ is the emission probability, assuming that the emitted symbol was $e$.
Since the individual steps are independent, this logarithmic pricing scheme will make the step prices additive. In the case of string alignment, the prices should be the inverse logarithmic probabilities of various kinds of errors (like reversals, deletions, etc.).
I hope this answers you question. You might also want to have a look at chapter 16 of David McKay's Information Theory, Inference, and Learning Algorithms, which discusses these and other algorithms from the perspective of message passing schemes. (You can download it from his website.)


TITLE: If X is a binomial random variable, find $E(X(X - 1) (X - 2))$
QUESTION [0 upvotes]: If X is a binomial random variable, how do you find $E(X(X - 1)(X - 2))$?

Here's my approach:
$E(X(X - 1)(X - 2)) = E(X^3 - 3X^2 + 2X)$
$E(X) = np, Var(X) = np(1 - p)$
$Var(X) = E(X^2) - (E(X))^2$
$E(X^2) = np(1 - p) + (np)^2$
So, $E(X^3 - 3X^2 + 2X) = E(X^3) - 3E(X^2) + 2E(X)$
How should I deal with $E(X^3)$?

REPLY [0 votes]: Given any discrete random variable $X$, the probability generating function (pgf) of $X$ is $G_X(t):=\mathbb{E}t^X$. Note that $\mathbb{E}\prod_{i=0}^{n-1}(X-i)=G_X^{(n)}(1)$. As an example consider $X\sim B(n,\,p)\implies G_X(t)=\sum_{k=0}^\infty\binom{n}{k}(pt)^k q^{n-k}=(q+pt)^n$. Hence $\mathbb{E}X(X-1)(X-2)=n(n-1)(n-2)p^3(q+pt)^{n-3}|_{t=1}=n(n-1)(n-2)p^3$.


TITLE: Structure satisfiability and entailment
QUESTION [2 upvotes]: Let $Fv[\phi]$ be the free variables of $\phi$. Suppose there are 2 formulas $A,B$ such that $Fv[A] \subseteq \{x,y\}$ and $Fv[B] \subseteq \{x,y\}$.
Prove/Disprove: $T \nvdash A\wedge B$ iff there exists a structure $M$ such that $M\models T \cup \neg(A\wedge B)$

I'm pretty sure it is wrong. My reasoning is that if that even though there is no structure such that when $ M \models T$, then $M \models A \wedge B$, that doesn't necessarily mean that there is no variable assignment $v$ such that $M, v \models A \wedge B$. So what we need is  formulas such that for each structure $M$ that models $T$ there exists an assignment $v_1$ such that $M, v_1 \models A \wedge B$, and also and assignment $v_2$ such that $M, v_2 \not\models A \wedge B$. However, I cannot find such formulas and I'd like an example.
thanks

REPLY [1 votes]: Found a counterexample:
$$T= \emptyset$$
$$ A = B = p(x)\vee\neg p(y)$$
works here


TITLE: Example of a bounded set with a minimum but no maximum
QUESTION [0 upvotes]: Using the definition of a bounded set to be a set where there exists a positive number M>0 such that every element of the set s < M.
How could you then have a set without a maximum? Surely M is the maximum?

REPLY [1 votes]: The interval $[0,1)$ is the easiest example.


TITLE: Is there any way to rewrite a partial differential equation using language of differential forms, tensors, etc?
QUESTION [23 upvotes]: My question is: usually, a partial differential equation, for example, those coming from physics, is written in a language of vector calculus in a local coordinate. Is there any way (or any algorithm) that we can use to rewrite it using language of differential forms, tensor, exterior calculus, Hodge star and other operators which are coordinate independent? An example,  the Grad f can be rewritten as a geometric form: (df)#, where # is a sharp operator turning a one-form into a vector.  I am currently facing this problem to turn a partial differential equation into its coordinate-independent form, which involves forms, tensors, exterior calculus and other operators.
Thank you for anyone who help me about this problem!

REPLY [1 votes]: Basic paper is
Journal of Mathematical Physics , Vol. 12. New York: American Institute of Physics. (1971): 653-666 (so called "Harrison-Estabrook procedure.")
This procedure is implemented in package "Liesymm" for Maple.


TITLE: Derivation of adjoint equation for the one-dimensional convection-diffusion equation
QUESTION [0 upvotes]: I am reading the paper "An Introduction to the Adjoint Approach to Design"(https://link.springer.com/article/10.1023/A:1011430410075). In this paper, derivation of the adjoint equation for the one-dimensional convection-diffusion equation is illustrated. But I don't understand why two terms are zero in the derivation.
The one-dimensional convection-diffusion equation
$$
Lu\equiv \frac{du}{dx}-\epsilon\frac{d^2u}{dx^2}, \;\; 0<x<1
$$
subject to the homogeneous boundary conditions $u(0)=u(1)=0$
Using integration by parts, for any twice-differentiable function $v$ we have
$$
(v,Lu)=\int_{0}^{1} v  \Big(\frac{du}{dx}-\epsilon\frac{d^2u}{dx^2}\Big)dx \\
=\int_{0}^{1} u  \Big(-\frac{dv}{dx}-\epsilon\frac{d^2v}{dx^2}\Big)dx
+ \Big[vu -\epsilon v\frac{du}{dx}-\epsilon u\frac{dv}{dx} \Big]^1_0 \\
=\int_{0}^{1} u  \Big(-\frac{dv}{dx}-\epsilon\frac{d^2v}{dx^2}\Big)dx
+ \Big[\epsilon v\frac{du}{dx} \Big]^1_0
$$
Why $vu$ and $-\epsilon u\frac{dv}{dx}$ are 0 and you get the below?
$$
\Big[vu -\epsilon v\frac{du}{dx}-\epsilon u\frac{dv}{dx} \Big]^1_0
= \Big[\epsilon v\frac{du}{dx} \Big]^1_0
$$

REPLY [1 votes]: The terms $vu$ and $-\epsilon u \frac{dv}{dx}$ are 0 because they are evaluated at the boundaries where $u(0) = u(1) = 0$. The remaining boundary terms prescribes the boundary condition on the costate variable, $v(0) = v(1) = 0$.
I hope that helps.


TITLE: If x in set of integers, then exactly one of the following is the case:
QUESTION [0 upvotes]: a) $X$ is positive
b) $X=0$
c) $-X$ is positive
We finished building integers and now, we are building rational numbers. This question is on my text book and i was trying to exercise. I dont know where to start. I know that integers are equivalence classes in $\mathbb N\times\mathbb N$. And I know rule of being positive in integers.

REPLY [0 votes]: When building the numbers the more difficult proofs are those on $\mathbb N$ since for the subsequent classes the proofs relies on a corresponding property on the earlier classes.
In this case the proof relies that for each pair $x$, $y$ of natural numbers exactly one of $x>y$, $x<y$ or $x=y$ is true (which of course is proven by induction twice).
The extension to $\mathbb Z$ first must define the relations on $\mathbb Z$ of course (or one does that at about the same time) and also negation. In doing so we need to know that for two numbers $x$ and $y$ we have that for each candidate of the equivalence class we have that $x_p+y_n$ and $x_n+y_p$ compares in the same way (that $x<y$ is well defined by the relation $x_p+y_n < x_n+y_p$). Also the corresponding is done for negation to define $-x$.
We have that due to the property in $\mathbb N$ that exactly one of $x_p+y_n < x_n+y_p$, $x_p+y_n > x_n+y_p$ and $x_p+y_n = x_n+y_p$ is true. Especially we have exactly one of $x_p + 0_n > x_n+0_p$ (ie $x>0$), $x_p + 0_n < x_n + 0_p$ (ie $x<0$ or by using definition of negation immediately means $-x > 0$) or $x_p+0_n = x_n+0_p$ (ie $x=0$).


TITLE: Height on a semiabelian variety
QUESTION [2 upvotes]: Let $A$ be a semiabelian variety over $\bar{\mathbb{Q}}$ and $B$ a semiabelian subvariety of $A$. Let $\pi:A\to A/B$ be the canonical morphism. Let $h:A(\bar{\mathbb{Q}})\to\mathbb{R}$ and $h':(A/B)(\bar{\mathbb{Q}})\to\mathbb{R}$ be canonical heights. (see
POONEN B., "Mordell-Lang plus Bogomolov").
Question : $\exists{\alpha,\beta\geq 0},~~\forall a'\in(A/B)(\bar{\mathbb{Q}}),~~\exists a\in A(\bar{\mathbb{Q}})\text{ such that }\left \{
\begin{array}{rcl}
\pi(a)&=&a' \\
h(a)&\leq& \alpha h'(a') +\beta
\end{array}
\right.$
Remark : If $A$ is split, it is true with $\beta=0$. (Because $A/B$ is isogenous to a semiabelian subvariety of $A$).
Thanks.

REPLY [2 votes]: I think the answer is yes. More generally, suppose $\pi:X\rightarrow Y$ is a surjective map of irreducible schemes over $\mathbb{Q}$ with compactifications $\overline{X},\overline{Y}$ respectively. Pick very ample line bundles $\mathcal{L}_X, \mathcal{L}_Y$ and use them to define heights $h_X,h_Y$. Then there exist $\alpha,\beta>0$ such that for any $y\in Y(\bar{\mathbb{Q}})$ there exists $x$ over it with $h_X(x)\leq \alpha h_Y(y) + \beta$.
I believe these heights are comparable to the canonical heights on a semi-abelian variety, so this should answer your question.
After a finite etale base change the generic point of $Y$ will have a section back to $X$, so by possibly replacing $Y$ by an open subset of it, and making this base change we can assume that $\pi$ has a section $\psi:Y\rightarrow X$. Note that etale base changes won't affect the height by more than a constant. Moreover, replacing $Y$ by an open subset is justified because we can then repeat the argument for the complement of this open set and this process will eventually end by Noetherian induction. We now shrink a bit further to assume that $Y$ is an affine scheme $Y=\rm{spec}(R)$. I claim that one can take $x=\psi(y)$.
Since $\mathcal{L}_Y$ is very ample, we can take a basis of sections $(y_1,\dots,y_n)$ such that $(y_i/y_j)_{i,j}$ generate the fraction field of $R$. Letting $(x_1,\dots,x_m)$ be the corresponding sections of $\mathcal{L}_X$ it follows that there are rational functions $Q_{i,j}(y_1/y_2,\dots,y_1/y_n)$ which are equal to the restriction of $x_i/x_j$ to $\psi(Y)$. The claim follows.