text:
\section{Introduction}

This work considers the following, possibly nonconvex, finite-sum optimization problem:
\begin{equation}
\label{problem}
    \textstyle{\min}_{w \in \mathbb{R}^d}\left\{P(w) = \tfrac{1}{n}
    \textstyle{\sum}^n_{i = 1} f_i(w)\right\},
\end{equation}
where $w\in \mathbb{R}^d$ is the model/weight parameter and the loss functions $f_i:\mathbb{R}^d \to \mathbb{R}$  $\forall i \in [n]:=\{1\dots n\}$ are smooth and twice differentiable. Throughout this work it is assumed that \eqref{problem} has an optimal solution, with a corresponding optimal value, denoted by $w^*$, and $P^* = P(w^*)$, respectively.
\\[2pt]
Problems of the form \eqref{problem} cover a plethora of applications, including empirical risk minimization, deep learning, and supervised learning tasks such as regularized least squares or logistic regression \cite{shalev2014understanding}. This minimization problem can be difficult to solve, particularly when the number of training samples $n$, or problem dimension $d$, is large, or if the problem is nonconvex.
\\[2pt]
Stochastic Gradient Descent ({\tt SGD}) is one of the most widely known methods for problem \eqref{problem}, and its origins date back to the 1950s with the work \cite{Robbins1951}. The explosion of interest in machine learning has led to an immediate need for reliable and efficient algorithms for solving \eqref{problem}. Motivated by, and aiming to improve upon, vanilla {\tt SGD}, many novel methods have already been developed for convex and/or strongly convex instances of \eqref{problem}, including {\tt SAG}/{\tt SAGA} \cite{LeRoux2012,Defazio2014}, {\tt SDCA} \cite{Shalev-Shwartz2013}, {\tt SVRG} \cite{Johnson2013,Xiao2014}, {\tt S2GD} \cite{Konecny2017} and {\tt SARAH} \cite{Nguyen2017}, to name just a few. In general, these methods are simple, have low per iteration computational costs, and are often able to find an $\varepsilon$-optimal solution to \eqref{problem} quickly, when $\varepsilon>0$ is not too small. However, they often have several hyper-parameters that can be difficult to tune, they can struggle when applied to ill-conditioned problems, and many iterations may be required to find a high accuracy solution.
\\
Non-convex instances of the optimization problem \eqref{problem} (for example, arising from deep neural networks (DNNS)) have been diverting the attention of researchers of late, and new algorithms are being developed to fill this gap \cite{Ghadimi2013,Ghadimi2016,Lei2017,Li2021zerosarah}.
Of particular relevance to this work is the {\tt PAGE} algorithm presented in \cite{Li2021}. The algorithm is conceptually simple, involving only one loop, and a small number of parameters, and can be applied to non-convex problems \eqref{problem}. The main update involves either a minibatch {\tt SGD} direction, or the previous gradient with a small adjustment (similar to that in {\tt SARAH} \cite{Nguyen2017}).  The {\tt Loopless SVRG} ({\tt L-SVRG}) method \cite{Hofmann2015,Qian2021}, is also of particular interest here. It is a simpler `loopless' variant of {\tt SVRG}, which, unlike for {\tt PAGE}, involves an unbiased estimator of the gradient, and it can be applied to non-convex instances of problem \eqref{problem}.
\\[2pt]
For problems that are poorly scaled and/or ill-conditioned, second order methods that incorporate curvature information, such as Newton or quasi-Newton methods \cite{Dennis1977,Fletcher1987,Nocedal2006}, can often outperform first order methods. Unfortunately, they can also be prohibitively expensive, in terms of both computational and storage costs. There are several works that have tried to reduce the potentially high cost of second order methods by using only approximate, or partial curvature information. Some of these stochastic second order, and quasi-Newton \cite{Jahani2021sonia,Jahani2020sr1} methods have shown good practical performance for some machine learning problems, although, possibly due to the noise in the Hessian approximation, sometimes they perform similarly to first order variants.
\\[2pt]
An alternative approach to enhancing search directions is to use a \emph{preconditioner}. There are several methods for problems of the form \eqref{problem}, which use what we call a `first order preconditioner' --- a preconditioner built using gradient information --- including {\tt Adagrad} \cite{Duchi2011}, RMSProp \cite{tieleman2012lecture}, and {\tt Adam} \cite{Kingma2015}. {\tt Adagrad} \cite{Duchi2011} incorporates a diagonal preconditioner that is built using accumulated gradient information from the previous iterates. The preconditioner allows every component of the current gradient to be scaled adaptively, but it has the disadvantage that the elements of the preconditioner tend to grow rapidly as iterations progress, leading to a quickly decaying learning rate. A method that maintains the ability to adaptively scale elements of the gradient, but overcomes the drawback of a rapidly decreasing learning rate, is RMSProp. It does this by including a momentum parameter, $\beta_2$ in the update for the diagonal preconditioner. In particular, at each iteration the updated diagonal preconditioner is taken to be a convex combination (using a momentum parameter $\beta_2$) of the (square) of the previous preconditioner and the Hadamard product of the current gradient with itself. So, gradient information from all the previous iterates is included in the preconditioner, but there is a preference for more recent information. {\tt Adam} \cite{Kingma2015} combines the positive features of {\tt Adagrad} and RMSProp, but it also uses a first moment estimate of the gradient, providing a kind of additional momentum. {\tt Adam} preforms well in practice, and is among the most popular algorithms for DNN.
\\[2pt]
Recently, second order preconditioners that use approximate and/or partial curvature information have been developed and studied. The approach in {\tt AdaHessian} \cite{Yao2020} was to use a diagonal preconditioner that was motivated by Hutchinson's approximation to the diagonal of the Hessian \cite{Bekas2007}, but that also stayed close to some of the approximations used in existing methods such as {\tt Adam} \cite{Kingma2015} and {\tt Adagrad} \cite{Duchi2011}. Because of this, the approximation often differed markedly from the true diagonal of the Hessian, and therefore it did not always capture good enough curvature information to be helpful. The work {\tt OASIS} \cite{Jahani2021}, proposed a preconditioner that was closely based upon Hutchinson's approach, and provided a more accurate estimation of the diagonal of the Hessian, and correspondingly led to improved numerical behaviour in practice. The preconditioner presented in \cite{Jahani2021} is adopted here.
\subsection{Notation and Assumptions}\label{Sec:Notation}
Given a Positive Definite (PD) matrix $D\in \mathbb{R}^{d\times d}$, the weighted Euclidean norm is defined to be $\|x\|_D^2 = x^T D x$, where $x\in \mathbb{R}^d$.
The symbol $\odot$ denotes the Hadamard product, and {\tt diag}$(x)$ denotes the $d\times d$ diagonal matrix whose diagonal entries are the components of the vector $x\in \mathbb{R}^d$.
\\[2pt]
Recall that problem \eqref{problem} is assumed to have an optimal solution $w^*$, with corresponding optimal value $P^* = P(w^*)$. As is standard for stochastic algorithms, the convergence guarantees presented in this work will develop a bound on the number of iterations $T$, required to push the expected squared norm of the gradient below some error tolerance $\varepsilon >0$, i.e., to find a $\hat{w}_T$ satisfying
\begin{eqnarray}\label{epsoptsoln}
\mathbb E [\|\nabla P(\hat{w}_T)\|_2^2] \leq \varepsilon^2.
\end{eqnarray}
A point $\hat{w}_T$ satisfying \eqref{epsoptsoln} is referred to as an $\varepsilon$-optimal solution. Importantly, $\hat{w}_T$ is \emph{some} iterate generated in the first $T$ iterations of each algorithm, but it is \emph{not necessarily} the $T$th iterate.
\\[2pt]
Throughout this work
we assume
that each $f_i:\mathbb{R}^d \to \mathbb{R}$ and $P:\mathbb{R}^d \to \mathbb{R}$
are twice differentiable and also $L$-smooth. This is formalized in the following assumption.
\begin{assumption}[$L$-smoothness]\label{smoothness}
For all $i \in [n]$ $f_i$ and
$P$ are assumed to be twice differentiable and $L$-smooth, i.e.,
$\forall i \in [n], \forall w,w' \in \dom(f_i)$ we have $\| \nabla f_i(w)
 - \nabla f_i(w') \|
 \leq L \|w-w'\|$,
and $\forall w,w' \in \dom(P)$ we have $\| \nabla P(w)
 - \nabla P(w') \|
 \leq L \|w-w'\|.$
\end{assumption}
For some of the results in this work, it will also be assumed that the function $P$ satisfies the PL-condition. Note that the PL-condition does not imply convexity (see Footnote~1 in \cite{Li2021}).
\begin{assumption}[Polyak-\L{}ojasiewicz-condition]\label{PL}
A function $P: \mathbb{R}^d \rightarrow \mathbb{R}$ satisfies the PL-condition  if there exists $ \mu >0$, such that $\|\nabla P(w)\|^2 \geq 2\mu (P(w)-P^{*}),~ \forall w \in \mathbb{R}^d.$
\end{assumption}

 \begin{wrapfigure}{r}{0.6\textwidth}
\vskip-40pt

    \centering
    \small
	\captionof{table}{Comparison of scaled stochastic methods for non-convex problems. {\em Notation:} $T$ denotes the number of iterations. The `Tuning of $\beta_2$' column shows whether it is easy (`$+$'), or difficult (`$-$') to tune $\beta_2$. Our preconditioner \eqref{approx_Hessian_2} works with any $\beta_2$. {\tt Adam} only supports certain large $\beta \approx 1$ \cite{defossez2020simple, reddi2019convergence}.}
	\vskip-2pt
    \label{tab:comparison0}
    \small
  \begin{threeparttable}
    \begin{tabular}{|c|c|c|c|}
    \hline
    \textbf{Method} & \textbf{Reference} & \textbf{Convergence} & \textbf{Tuning of $\beta_2$}  \\
    \hline
   \texttt{Adagrad} & \cite{Duchi2011, zou2018weighted, defossez2020simple} & \myred{$\frac{1}{\sqrt{T}}$} & +
    \\ \hline
    \texttt{RMSProp} & \cite{tieleman2012lecture} & \multicolumn{2}{c|}{\myred{no theory}}
    \\ \hline
    \texttt{Adam} & \cite{Kingma2015, defossez2020simple} & \myred{$\frac{1}{\sqrt{T}}$} & \myred{\textbf{--}}
    \\ \hline
    \texttt{AdaHessian} & \cite{Yao2020}  & \multicolumn{2}{c|}{\myred{no theory}}
    \\ \hline
    \texttt{OASIS} & \cite{Jahani2021} & \myred{$\frac{1}{\sqrt{T}}$} & +
    \\ \hline \hline
    \cellcolor{bgcolor2}{\texttt{Scaled SARAH}} & \cellcolor{bgcolor2}{This work} & \cellcolor{bgcolor2}{$\frac{1}{T}$}& \cellcolor{bgcolor2}{+}
    \\ \hline
    \cellcolor{bgcolor2}{\texttt{Scaled L-SVRG}} & \cellcolor{bgcolor2}{This work} & \cellcolor{bgcolor2}{$\frac{1}{T}$} & \cellcolor{bgcolor2}{+}
    \\ \hline
    \end{tabular}
    \end{threeparttable}
\vskip5pt
\captionof{table}{A summary of the main results of this work. Complexities for {\tt{Scaled SARAH}} and {\tt{Scaled L-SVRG}} are given for nonconvex problems (first row), and under the PL assumption (second row). {\em Notation:} $L$ = smoothness constant, $\mu$ = PL constant, $\varepsilon$ = solution accuracy \eqref{epsoptsoln}, $\Delta_0 = P(w^0) - P^*$, $n$ = data size, and $\Gamma, \alpha$ are upper and lower bounds of the Hessian approximation.
}
\vskip-2pt
\label{Table:complexityresults}
  \begin{threeparttable}
  \tiny
\begin{tabular}{ |c|c|c| }
 \hline
  & \tt{Scaled SARAH} & \tt{Scaled L-SVRG} \\ [0.5ex]
 \hline\hline
 \textsc{NC} & $\mathcal{O}\left({\color{blue}\frac{\Gamma}{\alpha}} \frac{\sqrt{n}L\Delta_0}{\varepsilon^2} \right)$ & $\mathcal{O}\left({\color{blue}\frac{\Gamma}{\alpha}}\frac{n^{\nicefrac{2}{3}}L\Delta_0}{\varepsilon^2}\right)$ \\
 \hline
 \textsc{PL} & $\mathcal{O}\left(\max\left\{n,{\color{blue}\frac{\Gamma}{\alpha}} \sqrt{n}\frac{L}{\mu} \right\} \log\frac{\Delta_0}{\varepsilon}\right)$ & $\mathcal{O}\left(\max\left\{n, {\color{blue}\frac{\Gamma}{\alpha}}n^{\nicefrac{2}{3}}\frac{L}{\mu} \right\}
 \log\frac{\Delta_0}{\varepsilon}\right)$ \\
 \hline
\end{tabular}
    \end{threeparttable}
\vskip-10pt
\end{wrapfigure}
\subsection{Contributions}
The main contributions of this work are stated below, and are summarized in Tables~\ref{tab:comparison0} and \ref{Table:complexityresults}.
\renewcommand{\arraystretch}{2}

\\
\emph{$\bullet$ {\bf Scaled SARAH.}} We present a new algorithm called {\tt Scaled SARAH}, which is a combination of the {\tt SARAH} \cite{Nguyen2017} and {\tt PAGE} \cite{Li2021} algorithms, coupled with the diagonal preconditioner from \cite{Jahani2021}. The inclusion of the preconditioner results in adaptive scaling of every element of the search direction (negative gradient), which leads to improved practical performance, particularly on ill-conditioned and poorly scaled problems. The algorithm is simple (a single loop) and is easy to tune (Section~\ref{Sec:ScaledPage}).
\\
\emph{$\bullet$ {\bf Scaled L-SVRG.}} The {\tt Scaled L-SVRG} algorithm is also presented, which is similar to {\tt L-SVRG}, but with the addition of the diagonal preconditioner \cite{Jahani2021}. Again, the preconditioner allows all elements of the gradient to be scaled adaptively, the algorithm uses a single loop structure, and for this algorithm an unbiased estimate of the gradient is used. The inclusion of adaptive local curvature information via the preconditioner leads to improvments in practical performance (Sections~\ref{Sec:ScaledLSVRG}).
\\[2pt]
\emph{$\bullet$ {\bf Convergence guarantees.}} Theoretical guarantees show that both {\tt Scaled SARAH} and {\tt Scaled L-SVRG} converge and we present an explicit bound for the number of iterations required by each algorithm to obtain an iterate that is $\epsilon$-optimal. Convergence is guaranteed for both {\tt Scaled SARAH} and {\tt Scaled L-SVRG} under a smoothness assumption on the functions $f_i$. If both smoothness and the PL-condition hold, then improved iteration complexity results for {\tt Scaled SARAH} and {\tt Scaled L-SVRG} are obtained, which show that expected function value gap converges to zero at a linear rate (see Theorems~\ref{Thm:ScaledPageLPL} and \ref{Thm:ScaledLSVRGLPL}.) Our scaled methods achieve the best known rates for non-convex stochastic problems, and {\tt Scaled SARAH} and {\tt Scaled L-SVRG} are the first preconditioned methods that achieve a linear rate of convergence under the PL assumption. (See Sections~\ref{Sec:ScaledLSVRG}.)
\\
\emph{$\bullet$ \bf Numerical experiments.} Extensive numerical experiments were performed (Sections~\ref{Sec:Numerical} and \ref{App:experiments}) under various parameter settings to investigate the practical behaviour of our new scaled algorithms. The inclusion of preconditioning in {\tt Scaled SARAH} and {\tt Scaled L-SVRG} led to improvements in performance compared with no preconditioning in several of the experiments, and  {\tt Scaled SARAH} and {\tt Scaled L-SVRG} were competitive with, and often outperformed, {\tt Adam}.
\\[2pt]
{\bf Paper outline.} This paper is organised as follows. In Section~\ref{Sec:Preconditioner} we describe the diagonal preconditioner that will be used in this work. In Section~\ref{Sec:ScaledPage}, we describe a new {\tt Scaled  PAGE} algorithm and present theoretical convergence guarantees. In Section~\ref{Sec:ScaledLSVRG}, we introduce the {\tt Scaled L-SVRG} algorithm, which adapts the {\tt L-SVRG} algorithm to include a preconditioner. We present numerical experiments demonstrating the practical performance of our proposed methods in Section~\ref{Sec:Numerical} and concluding remarks are given in Section~\ref{Sec:Conclusion}. All proofs (Sections~\ref{Sec:ProofsSARAH} and \ref{Sec:ProofsLSVRG}), additional numerical experiments (Section~\ref{App:experiments}), and further details and discussion can be found in the appendix.

\section{Diagonal Preconditioner}\label{Sec:Preconditioner}

In this section we describe the diagonal preconditioner that is used in this work. The paper \cite{Bekas2007} described Hutchinson's approximation to the diagonal of the Hessian, and this provided motivation for the diagonal preconditioner proposed in \cite{Jahani2021}, which is adopted here.  In particular, given an initial approximation $D_0$, (to be described soon), and Hessian approximation momentum parameter $\beta\in(0,1)$ (equivalent to the second moment hyperparameter, $\beta_2$ in {\tt Adam} \cite{Kingma2015}), for all $t\geq 1$,
\begin{equation}
\label{approx_Hessian_1}
    D_{t} = \beta D_{t-1} + (1-\beta)\texttt{diag}\left(z_t\odot \nabla^2P_{\mathcal{J}_t}(w_t)z_t\right),
\end{equation}
where $z_t$ is a random vector with Rademacher distribution\footnote{i.e., the components of the $z_t$ are $\pm1$ with equal probability.}, $\mathcal{J}_t$ is an index set randomly sampled from $[n]$, and
\begin{eqnarray}\label{Hessianbatch}
\nabla^2P_{\mathcal{J}_t}(w_t) = \frac1{|\mathcal{J}_t|} \sum_{j\in \mathcal{J}_t} \nabla^2 f_{j}(w_t).
\end{eqnarray}

Finally, for $\alpha>0$ (where the parameter $\alpha>0$ is equivalent to the parameter $\epsilon$ in {\tt Adam} \cite{Kingma2015} and {\tt AdaHessian} \cite{Yao2020}), the diagonal preconditioner is:
\begin{equation}\label{approx_Hessian_2}
    \left(\hat{D}_{t}\right)_{i,i} = \max\{\alpha, \left|D_t\right|_{i,i}\}.
\end{equation}
The expression \eqref{approx_Hessian_2} ensures that the preconditioner $\hat{D}_{t}$ is always PD, so it is well-defined and results in a descent direction. The absolute values are necessary because the objective function is potentially nonconvex, so the batch Hessian approximation could be indefinite. In fact, even if the Hessian is PD, $D_t$ in \eqref{approx_Hessian_1} may still contain negative elements due to the sampling strategy used.
\\[2pt]
The preconditioner \eqref{approx_Hessian_2} is a good estimate of the diagonal of the (batch) Hessian because Hutchinson's updating formula \eqref{approx_Hessian_1} is used. Hence, it captures accurate curvature information, which is helpful for poorly scaled and ill-conditioned problems. Because the preconditioner is diagonal it is easy and inexpensive to apply it's inverse, and the associated storage costs are low.
\\[2pt]
The preconditioner \eqref{approx_Hessian_1}+\eqref{approx_Hessian_2} depends on the parameter $\beta$: if $\beta = 1$ then the preconditioner is fixed for all iterations, whereas if $\beta = 0$ then the preconditioner is simply a kind of sketched batch Hessian. Taking $0<\beta<1$ gives a convex combination of the previous approximation and the current approximation, thereby ensuring that the entire history is included in the preconditioner, but is damped by $\beta$, and the most recent information is also present. See Section~\ref{sec:beta} for a detailed discussion of the choice of $\beta$.
\\[2pt]
The main computational cost of the approximation in \eqref{approx_Hessian_1} is the (batch) Hessian-vector product $\nabla^2P_{\mathcal{J}_t}(w_t)z_t$. Fortunately, this can be efficiently calculated using two rounds of back propagation. Moreover, the preconditioner is matrix-free, simply needing an oracle to return the Hessian vector product, but it does not need explicit access to the batch Hessian itself; see Appendix B in \cite{Jahani2021}. Therefore, the costs (both computational and storage) for this preconditioner are not burdensome.
\\[2pt]
As previously mentioned, the approximation \eqref{approx_Hessian_1} requires an initial estimate $D_0$ of the diagonal of the Hessian, and this is critical to the success of the preconditioner. In particular, one must take
\begin{equation}\label{init_Hessian}
    D_0 = \frac1{m}
 \sum_{j=1}^m \texttt{diag}\left(z_j\odot \nabla^2P_{\mathcal{J}_j}(w_0)z_j\right),
\end{equation}
where $\mathcal{J}_j$ denotes sampled batches and the vectors $z_j$ are generated from a Radermacher distribution.
This ensures that $\hat D_t$ does indeed approximate the diagonal of the Hessian; see Section~3.3 in \cite{Jahani2021}.
\\[2pt]
The following remark confirms that the diagonal preconditioner is both PD and bounded.
\begin{lemma}[See Remark 4.10 in \cite{Jahani2021}]\label{Remark_Gammaalpha}
For any $t\geq 1$, we have $\alpha I\preccurlyeq \hat{D}_t \preccurlyeq \Gamma I$, where $0<\alpha \leq \Gamma = \sqrt{d} L$.
\end{lemma}
Note that Remark 4.10 is proved incorrectly in \cite{Jahani2021}.

\section{\tt{Scaled SARAH} }\label{Sec:ScaledPage}

Here we propose a new algorithm, {\tt Scaled SARAH}, for finite sum optimization \eqref{problem}. Our algorithm is similar to the {\tt SARAH} algorithm \cite{Nguyen2017} and the {\tt PAGE} algorithm \cite{Li2021}, but a key difference is that  {\tt Scaled SARAH} includes the option of a preconditioner, $\hat D_t$ for all $t\geq 0$, with a preconditioned approximate gradient step. {\tt Scaled SARAH} is presented now as Algorithm~\ref{Scaled_PAGE}.

\begin{algorithm}[!h]
\caption{{\tt Scaled SARAH}}
\label{Scaled_PAGE}
	\begin{algorithmic}[1]
		\State \textbf{Input:} initial point $w_0$, learning rate $\eta$, preconditioner $\hat{D}_0$, probability $p$
		\State $v_0 = \nabla P(w_0)$
		\For{$t = 0,1,2,\ldots$}
		\State $w_{t+1} = w_t - \eta \hat{D}^{-1}_{t}v_t$\label{SARAHpreconditionedstep}
		\State Generate independently batches $i_{t+1}$ for $v_{t+1}$ and $\mathcal{J}_t$ for $\hat{D}_{t+1}$
		\State $v_{t+1} = \begin{cases}
                                \nabla P(w_{t+1}), & \text{with probability } p
                                    \\
                                v_{t} + \nabla f_{i_{t+1}}(w_{t+1}) - \nabla f_{i_{t+1}}(w_t), & \text{with probability } 1 - p
                            \end{cases}$\label{SARAHupdate}
		\State Update the preconditioner $\hat{D}_{t+1}$
		\EndFor
		\State \textbf{Output:} $\hat{w}_T$ chosen uniformly from $\{w_t\}^T_{t=0}$
	\end{algorithmic}
\end{algorithm}

In each iteration of Algorithm~\ref{Scaled_PAGE} an update is computed in Step~\ref{SARAHpreconditionedstep}. The point $w_t$ is adjusted by taking a step in the direction $\hat D_t^{-1}v_t$, of fixed step size $\eta$. The vector $v_t$ approximates the gradient, and the preconditioner scales that direction. A key difference between {\tt Scaled SARAH} and {\tt PAGE}/{\tt SARAH} is the inclusion of the preconditioner $\hat D_t^{-1}$ in this step.

Step~\ref{SARAHupdate} defines the next gradient estimator $v_{t+1}$, for which there are two options. With probability $p$ the full gradient is used. Alternately, with probability $1-p$, the new gradient estimate is the previous gradient approximation $v_t$, with an adjustment term that involves the difference between the gradient of $f_i$ evaluated at $w_{t+1}$ and at $w_t$. The search direction computed in {\tt Scaled SARAH} contains gradient information, while the preconditioner described in Section~\ref{Sec:Preconditioner} contains approximate second order information. When this preconditioner is applied to the gradient estimate, each dimension is scaled adaptively depending on the corresponding curvature. Intuitively, this amplifies dimensions with low curvature (shallow loss surfaces), while damping directions with high curvature (sharper loss surfaces). The aim is for $\hat D_t^{-1} v_t$ to point in a better, adjusted direction, compared with $v_t$.
\\[2pt]
{\tt Scaled SARAH} is a single loop algorithm so it is conceptually simple. If $p = 1$ then the algorithm always picks the first option in Step~\ref{SARAHupdate}, so that {\tt Scaled SARAH} reduces to a preconditioned {\tt GD} method. On the other hand, if $p = 0$, then only the second option in Step~\ref{SARAHupdate} is used. \\[2pt]
Notice that {\tt Scaled SARAH} is a combination of both the {\tt PAGE} and {\tt SARAH} algorithms, coupled with a preconditioner. {\tt SARAH} \cite{Nguyen2017} is a double loop algorithm, where the inner loop is defined in the same way as update in Step~\ref{SARAHupdate}. {\tt PAGE} \cite{Li2021} is based upon {\tt SARAH}, but {\tt PAGE} uses a single loop structure, and allows for minibatches to be used in the gradient approximation $v_{t+1}$ (rather than the single component as in Step~\ref{SARAHupdate}).\footnote{Note that, while {\tt PAGE}  allows minibatches for either option in the update Step~\ref{SARAHupdate}, most of the theoretical results presented in \cite{Li2021} require the full gradient to be computed as the first option in Step~\ref{SARAHupdate}.} {\tt Scaled SARAH} shares the same single loop structure as {\tt PAGE}, but also shares the same single component update for the gradient estimator as {\tt SARAH} (no minibatches). However, different from both {\tt PAGE} and {\tt SARAH}, {\tt Scaled SARAH} uses a preconditioner in Step~\ref{SARAHpreconditionedstep}.
\\[2pt]
In the remainder of this work we focus on a particular instance of {\tt Scaled SARAH}, which uses a fixed probability $p_t = p$, and uses the diagonal preconditioner presented in Section~\ref{Sec:Preconditioner}. These choices have been made because a central goal of this work is to understand the impact that a well chosen preconditioner has on poorly scaled problems. Convergence guarantees and the results of numerical experiments, will be presented using this set up.
\\[2pt]
Theoretical results for {\tt Scaled SARAH} are presented now. In particular, we present complexity bounds on the number of iterations required by {\tt Scaled SARAH} to obtain an $\varepsilon$-optimal solution for the non-convex problem \eqref{problem} (recall Section~\ref{Sec:Notation} and \eqref{epsoptsoln}). The first result holds under Assumption \ref{smoothness}, while the second theorem holds under both smoothness \emph{and} PL assumptions. First, we define the following step-size bound:
\begin{eqnarray}\label{stepsizebound}
\bar \eta = \frac{\alpha}{L\left(1 + \sqrt{\tfrac{1-p}{p}}\right)}.
\end{eqnarray}

\begin{theorem}\label{Thm:ScaledPageL}
Suppose that Assumption \ref{smoothness} holds, let $\epsilon >0$, let $p$ denote the probability, and let the step-size satisfy $\eta \leq \bar \eta$ \eqref{stepsizebound}.
Then, the number of iterations performed by {\tt Scaled SARAH}, starting from an initial point $w_0\in \mathbb{R}^d$ with $\Delta_0 = P(w_0)-P^*$, required to obtain an $\varepsilon$-approximate solution of the non-convex finite-sum problem \eqref{problem} can be bounded by
\begin{equation*}
    T =\mathcal{O}\left( \frac{\Gamma}{\alpha}\frac{\Delta_0 L}{\varepsilon^2}\left(1 + \sqrt{\frac{1-p}{p}}\right) \right).
\end{equation*}
\end{theorem}

\begin{theorem}\label{Thm:ScaledPageLPL}

Suppose that Assumptions \ref{smoothness} and \ref{PL} hold, let $\epsilon >0$, and let the step-size satisfy $\eta \leq \bar \eta$ \eqref{stepsizebound}.
Then the number of iterations performed by {\tt Scaled SARAH} sufficient for finding an $\varepsilon$-approximate solution of non-convex finite-sum problem \eqref{problem} can be bounded by
\begin{equation*}
    T = \mathcal{O}\left(\max\left\{\frac{1}{p}, \frac{L}{\mu}\frac{\Gamma}{\alpha}\left(1+ \sqrt{\frac{1-p}{p}}\right)\right\} \log\frac{\Delta_0}{\varepsilon}\right).
\end{equation*}
\end{theorem}
Note that this last theorem shows that {\tt Scaled SARAH} exhibits a linear rate of convergence under both the smoothness assumption and the PL-condition.

\section{{\tt Scaled L-SVRG}}\label{Sec:ScaledLSVRG}

{\tt SVRG} \cite{Johnson2013,Xiao2014} is a variance reduced stochastic gradient method that is very popular for finite sum optimization problems. However, the algorithm has a double loop structure, and careful tuning of hyper-parameters is required for good practical performance. \\[2pt]
Recently, \cite{Hofmann2015} proposed a Loopless {\tt SVRG} ({\tt L-SVRG}) variant, that has a simpler, single loop structure, which can be applied to problem \eqref{problem} in the convex and smooth case. This was extended in \cite{Qian2021} to cover the composite case with an arbitrary sampling scheme. With its single loop structure, and consequently fewer hyperparameters to tune, coupled with the fact that, unlike for {\tt PAGE} (recall Section~\ref{Scaled_PAGE}), {\tt L-SVRG} uses an \emph{unbiased} estimate of the gradient, {\tt L-SVRG} is a versatile and competitive algorithm for problems of the form \eqref{problem}.
\\[2pt]
However, as for the other previously mentioned gradient based methods, {\tt L-SVRG} can perform poorly when the problem is badly scaled and/or ill-conditioned. This provides the motivation for the {\tt Scaled L-SVRG} method that we propose in this work. Our {\tt Scaled L-SVRG} algorithm combines the positive features of {\tt L-SVRG}, with a preconditioner, to give a method that is loopless, has few hyperparameters to tune, uses an unbiased estimate of the gradient, and adaptively scales the search direction depending upon the local curvature. The {\tt Scaled L-SVRG} method is presented now as Algorithm~\ref{Scaled_LSVRG}.
\begin{algorithm}
\caption{{\tt Scaled L-SVRG}}
\label{Scaled_LSVRG}
	\begin{algorithmic}[1]
		\State \textbf{Input:} initial point $w_0$, learning rate $\eta$, preconditioner $\hat{D}_0$, probability $p$
		\State $z_0 = w_0$, $v_0 = \nabla P(w_0)$
		\For{$t = 0,1,2,\ldots$}
		\State $w_{t+1} = w_t - \eta \hat{D}^{-1}_{t}v_t$\label{LSVRGprecondstep}
		\State $z_{t+1} = \begin{cases}
                                z_t, & \text{with probability } p
                                    \\
                                w_t, & \text{with probability } 1 - p
                            \end{cases}$
        \State Generate independently batches $i_{t+1}$ for $v_{t+1}$ and $\mathcal{J}_t$ for $\hat{D}_{t+1}$
		\State $v_{t+1} = \nabla f_{i_{t+1}}(w_{t+1}) - \nabla f_{i_{t+1}}(z_{t+1}) + \nabla P(z_{t+1}) $
		\State Update the preconditioner $\hat{D}_{t+1}$
		\EndFor
		\State \textbf{Output:} $\hat{w}_T$ chosen uniformly from $\{w_t\}^T_{t=0}$
	\end{algorithmic}
\end{algorithm}

{\tt Scaled L-SVRG} can be described, in words, as follows. The algorithm is initialized with an initial point $w_0$, a learning rate $\eta$, an initial preconditioner $\hat D_0$, and probability $p$. At each iteration $t\geq 0$ of {\tt Scaled L-SVRG} (Algorithm~\ref{Scaled_LSVRG}) a search direction $v_t$ is generated. This is made up of the full gradient plus a small adjustment. Next, the new point $w_{t+1}$ is taken to be a step from $w_t$ in the \emph{scaled} direction $\hat{D}^{-1}_{t}v_t$, of size $\eta$. The new point $z_{t+1}$ is either the (unchanged) previous point $z_t$ with probability $p$, or the scaled approximate gradient step $w_{t+1}$ with probability $1-p$. Finally, the preconditioner is updated and the next iterate begins. The output, denoted by $\hat w_T$ is chosen uniformly from the points $w_t$, for $t=0,\dots, T$, generated by {\tt Scaled L-SVRG} (Algorithm~\ref{Scaled_LSVRG}).

Note that a key difference between {\tt L-SVRG} \cite{Hofmann2015,Qian2021} and our new {\tt Scaled L-SVRG} is the inclusion of the preconditioner in Step~\ref{LSVRGprecondstep}; recall that a competitive preconditioner is described in Section~\ref{Sec:Preconditioner}.

The following theorem presents a complexity bound on the number of iterations required by {\tt Scaled L-SVRG} to obtain an $\varepsilon$-optimal solution for the non-convex problem \eqref{problem}.
\begin{theorem}

Suppose that Assumption \ref{smoothness} holds, let $\epsilon >0$, let $p$ denote the probability and let the step-size satisfy $\eta \leq \min\left\{\tfrac{\alpha}{4L}, \tfrac{\sqrt{p}\alpha}{\sqrt{24}L}, \tfrac{p^{2/3}}{144^{2/3}}\tfrac{\alpha}{L}\right\}.$
Given an initial point $w_0\in \mathbb{R}^d$, let $\Delta_0 = P(w_0)-P^*$.
Then the number of iterations performed by {\tt Scaled L-SVRG}, starting from $w_0$, required to obtain an $\varepsilon$-approximate solution of non-convex finite-sum problem \eqref{problem} can be bounded by
\begin{equation*}
    T = \mathcal{O}\left(\frac{\Gamma}{\alpha}\frac{L\Delta_0}{p^{\nicefrac{2}{3}} \varepsilon^2}\right).
\end{equation*}
\end{theorem}
While the previous theorem held under a smoothness assumption, here we prove a complexity result for {\tt Scaled SARAH} under both smoothness \emph{and} PL assumptions.
\begin{theorem}\label{Thm:ScaledLSVRGLPL}
Suppose that Assumptions \ref{smoothness} and \ref{PL} hold, let $\epsilon >0$, let $p$ denote the probability and let the step-size satisfy $\eta \leq \min\left\{\frac{p\Gamma}{6\mu},\frac{1}{4}\frac{\alpha}{L}, \left(\frac{p}{6}\right)^{1/2}\frac{\alpha}{L}, \left(\frac{p}{6}\right)^{2/3}\frac{\alpha}{L}\right\}.$
Then the number of iterations performed by {\tt Scaled  L-SVRG} sufficient for finding an $\varepsilon$-approximate solution of non-convex finite-sum problem \eqref{problem} can be bounded by
\begin{equation*}
    T = \mathcal{O}\left(\max\left\{\frac{1}{p}, \frac{\Gamma}{\alpha}\frac{L}{p^{\nicefrac{2}{3}}\mu}\right\}\right).
\end{equation*}
\end{theorem}

\section{Numerical Experiments}\label{Sec:Numerical}
The purpose of these numerical experiments is to study the practical performance of our new {\tt Scaled SARAH} and {\tt Scaled L-SVRG} algorithms, and hence, to understand the advantages of using the proposed diagonal preconditioner on {\tt SARAH} and {\tt L-SVRG}. These results will also be compared with {\tt SGD}, both with and without the preconditioner described in Section~\ref{Sec:Preconditioner}, as well as the state-of-the-art (first order) preconditioned optimizer {\tt Adam}.
\\[2pt]
We test these algorithms on problem \eqref{problem} with two loss functions: (1) {\it logistic regression} loss function, which is convex, and (2) {\it non-linear least squares} loss function, which is nonconvex. The loss functions are described in details below. For further details and experimental results that support the findings of this section, please see Appendix \ref{App:experiments}. Note that all the experiments were initialized at the point $w_0 = 0$, and each experiment was run for 10 different random seeds.

\subsection{Loss Functions}
Let $P(w)$ be the empirical risk on a dataset $\{(x_i,y_i)\}_{i=1}^{n}$ where $x_i \in \mathbb{R}^d$ and $y_i \in \{-1,+1\}$. Then, the {\it logistic regression loss} is
\begin{equation}\label{eq:LogisticLoss}
    P_\text{logistic}(w) = \tfrac{1}{n} \textstyle{\sum}_{i=1}^{n} \log (1 + e^{-y_i x_i^T w})
\end{equation}
whereas for $y_i \in \{0,1\}$ the {\it non-linear least squares loss (NLLSQ)} is
\begin{equation}\label{eq:NLLSQ}
    P_\text{nllsq}(w) = \tfrac{1}{n} \textstyle{\sum}_{i=1}^{n} (y_i - 1/(1 + e^{-x_i^T w}))^2
\end{equation}
We consider two different loss functions to test our algorithms on both convex and nonconvex settings.

\subsection{Binary Classification on LibSVM Datasets}

We train the optimizers on three binary classification LibSVM datasets \footnote{https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/}, namely {\tt w8a}, {\tt rcv1}, and {\tt real-sim}. We also consider feature-scaled versions of these datasets, where the scaling is done as follows: we choose a minimum exponent $k_{min}$ and a maximum exponent $k_{max}$, and scale the features by values ranging from $10^{k_{min}}$ to $10^{k_{max}}$ in equal steps in the exponent according to the number of features and in random order. The setting $(k_{min}, k_{max}) = (0,0)$ corresponds to the original, unscaled version of the datasets. We consider combinations of $k_{min} = 0, -3$ and $k_{max} = 0, 3$. This scaling is done to check the robustness and overall effectiveness of the diagonal preconditioner in comparison with {\tt Adam}.
\begin{figure*}
    \centering
    \includegraphics[width=1\columnwidth]{figures/perf/perf_given_precond__loss_logistic__metric_error__corrupt_none.pdf}
\vskip-5pt
    \caption{Best performances of the optimizers, including {\tt Adam}, on the (unscaled) LibSVM datasets using the logistic loss. The {\tt Scaled} variants are shown as dashed lines sharing the same color. }
    \vskip-5pt
    \label{fig:best_perf_logistic}
\end{figure*}
\begin{figure*}
    \centering
    \includegraphics[width=1\columnwidth]{figures/perf/perf_given_precond__loss_nllsq__metric_error__corrupt_none.pdf}
    \vskip-5pt
    \caption{Best performances on the unscaled LibSVM datasets using the NLLSQ loss.}
    \label{fig:best_perf_nllsq}
    \vskip-5pt
\end{figure*}
\\[2pt]
Figure \ref{fig:best_perf_logistic} shows
the results of the first experiment, and presents three types of line plots for each of the datasets of interest where the loss function is the logistic regression loss \eqref{eq:LogisticLoss}. Figure \ref{fig:best_perf_nllsq} shows the same for the NLLSQ loss \eqref{eq:NLLSQ}. The first row corresponds to the loss, the second is the squared norm of the gradient, and the third is the error.
Tuning was performed in order to select the best hyperparameters (that minimize either the loss, gradient norm squared, or the error). The hyperparameter search grid is reported in Appendix, Table \ref{tab:hyperparam}, and a thorough discussion is below. We fixed the batch size to be $128$, in order to narrow the fine-tuned variables down to $\eta$, $\beta$, and $\alpha$. Figure \ref{fig:best_perf_logistic} shows the performances when minimizing the error on the unscaled datasets, $(k_{min}, k_{max}) = (0,0)$. Experiments on scaled datasets can be found in Appendix \ref{App:scaled_data}.

Consider the first column in Figure \ref{fig:best_perf_logistic}, which uses the {\tt w8a} dataset. While preconditioned {\tt SGD} performs better than {\tt SGD}, for {\tt SARAH} and {\tt L-SVRG} this is not the case. Notice that {\tt Adam} performs well initially, but then further effective data passes lead to small improvement (for all three metrics). While {\tt SARAH} and {\tt L-SVRG} perform the best on this dataset, after approximately 35 passes for  {\tt Scaled L-SVRG} and 60 passes for  {\tt Scaled SARAH}, performance is better than {\tt Adam}. For the remaining three datasets, preconditioning helps in all cases, with {\tt Scaled L-SVRG} and {\tt Scaled SARAH}, performing the best.

In order to understand the main factors that affect the preconditioner, we ran comparative studies, including studying the parameters $\beta$, and $\alpha$, as well as studying the initialization of preconditioner $D_0$, including a warm-up period, and studying how the number of samples, $z$, impacts performance. First, recalling \eqref{init_Hessian}, there did not appear to be any significant improvement from averaging across more samples of $z$ per minibatch, neither in the initialization nor in the update step. We also observed that initializing $D_0$ with a batch size of 100 was sufficiently good for non-sparse problems, and consistently resulted in a relative error of within 0.1 from the true diagonal. However, increasing the number of warm-up samples, proportionally to the number of features, led to observable improvements in convergence for sparse datasets.

We also investigated the role that $\beta$
\eqref{approx_Hessian_1} played in algorithm performance. We found that larger values lead to slightly slower but more stable convergence. The best $\beta$ highly depends on the dataset, but the value 0.999 appeared to be a good starting point in general. To ensure a fair comparison, we also optimized {\tt Adam}'s momentum parameter $\beta_2$ over the same range.

Aside from the batch size and learning rate, we found that, for ill-conditioned problems, the choice of $\alpha$ (recall \eqref{approx_Hessian_2} and Remark~\ref{Remark_Gammaalpha}) played an important role in determining the quality of the solution, convergence speed, and stability (which is not obvious from Figure \ref{fig:best_perf_logistic}). For example, if the features were scaled with $k_{min}=-3$ and $k_{max}=0$, the best $\alpha$ is often around $10^{-7}$ (very small), whereas if we scaled with $k_{min}=0$ and $k_{max}=3$, the best $\alpha$ becomes $10^{-1}$ (relatively large). Therefore, finding the best $\alpha$ might require some additional fine-tuning, depending on the choice of $\eta$ and $\beta$. However, we noticed that once we had tuned the learning rate for one scaled version of the dataset, the same learning rate transferred well to all the other scaled versions. In general, the optimal learning rate in our {\tt Scaled} algorithms is very robust to feature scaling, given that $\alpha$ is chosen well, whereas {\tt Adam}'s learning rate depends more heavily upon how ill-conditioned the problem is, so it requires fine-tuning across a potentially much wider range. In our case, tuning $\alpha$ and $\beta$ is straightforward, so we obtained state-of-the-art performance with minimal parameter tuning.

The choice $\beta = 1-1/(t+1)$ was investigated in Appendices~\ref{App:choosingbeta} and \ref{App:betat}. Preliminary results suggest that this choice virtually removes the dependence on $\alpha$, and is competitive with a fine-tuned $\beta$ across a large number of values. This makes fine-tuning much easier, even for strong feature scaling.

\section{Conclusion and Future Directions}\label{Sec:Conclusion}

In this paper we presented two novel algorithms for finite sum minimization problems: {\tt Scaled SARAH} and {\tt Scaled L-SVRG}. The algorithms combined existing stochastic reduced variance gradient based methods with a preconditioner, to give algorithms that are better able to adapt to local curvature. We presented theoretical iteration complexity guarantees to provide a bound on the number of iterations required to obtain an $\varepsilon$-optimal solution to \eqref{problem}, and we showed that the algorithms converge linearly when the PL-condition (in addition to smoothness) is assumed. Numerical experiments confirm the benefits of this approach.
\\[2pt]
{\bf Future work.} The {\tt Scaled SARAH} and {\tt Scaled L-SVRG} algorithms are deliberately general. This allows for user flexibility in the specific implementation strategy. The analysis presented in this paper considered a specific instance of each algorithm, where a full batch is taken $b=n$, the probability is fixed $p_t = p$ and the preconditioner described in Section~\ref{Sec:Preconditioner} is used. Future research directions include the development of theoretical guarantees under different parameter settings.

redpajama_set_name: RedPajamaArXiv


text:
TV Review: Backstrom 1.5 "Bogeyman"
By Olympus Athens | @ | Thursday, February 19th, 2015 at 5:00 pm
Season 1 Episode 5: "Bogeyman"
Directed by Michael Offer
Written by Eli Attie and Leif G.W. Persson (author)
Created by Hart Hanson
Starring Rainn Wilson, Beatrice Rosen, Page Kennedy, Genevieve Angelson, Dennis Haysbert, Thomas Dekker, and Kristoffer Polaha.
Air Date: Thursday, February 19, 2015, 9:00pm
Last week on Backstrom (spoilers!), our favorite cranky Special Crimes Unit detective investigated what he declared as a hate crime, in order to postpone his own hearing with the Civilian Oversight Committee. This case was wrapped up in the episode and Moto (Page Kennedy) was Backstrom's (Rainn Wilson) hero in the end. Last week's episode was good, but not the best of the episodes thus far.
How does Backstrom 1.5 "Bogeyman" measure up?
Much better. The case of the day looks like a runaway problem child, but Backstrom knows it's the same predator that captured another girl seven years ago – "Room full of rainbows…sea of black in the closet." This one really gets to him. He's almost ready to quit and we witness the biggest Backstrom vulnerability to date.
Almond (Dennis Haybert) is in danger of losing his church for financial reasons. This subplot was less interesting, but was necessary for the main plot.
Now, I don't know if Backstrom will be renewed. There is no word on that yet. What I do know is that I enjoy the show: the cases are interesting, the unorthodox methods of solving them bring it up another level, and Rainn Wilson really tries to make you dislike his character at face value while making you want to find the redeeming qualities within. Everett Backstrom has been deemed the "House" of detectives. House had a very successful run, but towards the end made you feel as if you were watching episodes on repeat – very well made repeat, but repeat nonetheless. It is still too early to tell on this one. Luckily, each member of his team is compelling in their own way.
FOX's press release:
THE SPECIAL CRIMES UNIT IS ASSIGNED THEIR MOST HARROWING CASE YET ON AN ALL-NEW "BACKSTROM" THURSDAY, FEBRUARY 19, ON FOX
FEB 19 9/8c
In the Special Crime Unit's most harrowing case yet, the team has three days to save a teenage girl who has been abducted by a slippery online predator. The team soon learns that this is a deeply personal case for Backstrom, who is jolted by the girl's resemblance to the victim of an unsolved case that he was assigned seven years ago. Meanwhile, Detective Sergeant John Almond's church faces eviction when he neglects to pay rent three consecutive months in the all-new "Bogeyman" episode of BACKSTROM airing Thursday, Feb. 19 (9:00-10:00 PM ET/PT) on FOX.
Topics: Reviews, Television, TV Reviews
Tags: Backstrom, Beatrice Rosen, Dennis Haysbert, Eli Attie, Fox, Genevieve Angelson, Hart Hanson, Kristoffer Polaha, Leif G.W. Persson, Michael Offer, Page Kennedy, Rainn Wilson, Thomas Dekker
TV Review: Vikings 3.1 "Mercenary"
Thrashback Thursday: Diamond Head "Am I Evil?"
• Jason Bateman In Talks To Direct and Star In New 'Clue' Movie With Ryan Reynolds
• 'Underwater' Trailer: Something Is After A Team Of Researchers 7 Miles Below Ocean Surface
• Disney Exec Worried That Taika Waititi's 'Jojo Rabbit' Could Alienate Disney Fans
• Disney To Stop 20th Century Fox Film Development and Focus More On Key Franchise Acquisitions

redpajama_set_name: RedPajamaCommonCrawl


text:
From plate to plough: Does anyone love the farmer?
The Union cabinet lacks a champion for agriculture
Written by Ashok Gulati | Updated: October 12, 2015 7:44:34 am
Since 2012-13, agriculture is limping, partly due to droughts and partly due to the collapse in commodity prices.
Policymakers in the corridors of power in Delhi are feeling upbeat. There is recovery and resurgence in India's stockmarkets. The Make in India campaign is getting more publicity and being noticed by foreign investors. FDI inflows are improving, and India's ranking in the Ease of Doing Business index seems to be improving, as per some selective ratings.
But agriculture, where almost half of India's workforce is engaged, continues to be in the doldrums. And no one seems to be perturbed about it. That's pathetic and tragic.
Between 2004 and 2011, domestic agricultural prices rose in line with global prices, which incentivised farmers to invest in agriculture. This, in turn, resulted in higher growth in agriculture, higher wages for farm labour, and the fastest decline in poverty since the initiation of reforms in 1991. The decline in poverty during this period was almost three times faster than during the 1993-2004 period. But the dream run seems to be over.
[related-post]
Government officials vie with the RBI in taking all the credit for taming inflation, especially food inflation. If their policy instruments are so powerful, how is it that they are helpless to control the prices of onions and pulses, which have gone up by more than 50 per cent in a single year? Our analysis shows that almost two-thirds of the decline in food inflation has resulted from the fall in global prices. This is leading to a decline in agri-exports, rising imports and falling food inflation at home. This is a result of sheer good luck for the Narendra Modi-led government — not a policy success.
But there is some bad luck too — in the form of back-to-back droughts. Monsoon rains (June 1 to September 30) in 2014 were less by 12 per cent compared to the long period average. That led to a drought, and agri-GDP growth collapsed to 1.1 per cent. This year's rain deficit is bigger at 14 per cent, and water storage in 91 reservoirs is also lower than last year. Unless a miracle happens, or statistics are cooked, all reports from the ground suggest that growth is going to be even lower. That would mean that, against a target of 4 per cent, the average growth of agriculture during the first four years of the 12th Five Year Plan is going to be only around 1.5 per cent. That's a massive failure in a sector that engages the largest number of people, especially those at the bottom of economic pyramid.
So the big political question that needs to be addressed is: What is the role of public policy? I will not recommend sacrificing growth to attain equality, but the nature of growth must be tweaked to get at least 4 per cent growth in agriculture.
Farmers are losing patience with each passing day. Punjab farmers are already up in arms, blocking trains because their cotton crop is heavily damaged and basmati prices have collapsed by more than 50 per cent. Soon farmers from Maharashtra, the interiors of north Karnataka and Uttar Pradesh are likely to rise up in protest. Can the Centre hear the rumblings? It is a wake-up call. Only the deaf can ignore it.
On August 15, the prime minister announced a change in nomenclature, adding "farmers welfare" to the name of the department of agriculture and cooperation. But, so far, there is no sign of any welfare measure for the farmers. We have only heard of the OROP for jawans, but kisans have been left to fend for themselves. What can the PM do to improve the economic situation of those engaged in farming so that their poverty can be eliminated in the next 10-15 years? A number of things can be done to achieve this.
First and foremost, we need a true champion of agriculture in the Union cabinet — someone who has a clear vision and the commitment and passion to tap the full potential of Indian agriculture in a global setting. Second, it is about time the Centre declared a drought in the worst-hit states, like Maharashtra, Karnataka, Madhya Pradesh, Gujarat, Uttar Pradesh, Bihar, Haryana and even Punjab. The Centre should ask the states to assess the damages in the next two weeks. Further, the assessments being made today are more political than scientific. That needs to change. And based on the degree of damage, the Centre should frontload the compensation package. Crop insurance needs to be resurrected. And farmers should be mainstreamed so that they avail of life insurance schemes, the Atal pension scheme, etc. Among other things, loans can be restructured and interest rates waived off. These measures will reveal the PM's concern and compassion for the farming community.
It would be good economics, as well as good politics.
The writer is Infosys chair professor for agriculture at Icrier
For all the latest Opinion News, download Indian Express App.
0 Comment(s)	*
* The moderation of comments is automated and not cleared manually by indianexpress.com.
EXPRESS OPINION
OpinionDigital Service Tax could offer an interim solution
OpinionAfter @realDonaldTrump, no easy answers
OpinionSociety's values need to be informed by a sense of justice
More Explained
Why Sensex at 50K presents an opportunity for investors
Experts Explain: How do vaccines work, and do they help?
Why stand-in Rahane is being seen as a permanent Test captain
Groaning under high electricity bills, Pune SME threatens to hit streets
Robert Lewandowski's penalty keeps Bayern Munich 4 points clear of Leipzig
Victorious Team India arrives home after series win against Australia
Explained: Why stand-in Rahane is being seen as a permanent Test captain
Priyanka Chopra, Sushmita Sen and others congratulate Joe Biden, Kamala Harris
Meet Astro Slide 5G, the world's first 5G smartphone with a full QWERTY keyboard
When Tom Holland thought he was going to get fired as Spider-Man
Ashok GulatiThe writer is chair professor for agriculture at ICRIER. Views are per... read more
Crop diversification policy must address nutritional challenges, bring agriculture in sync with environmental demands
To help farmers, right approach is through Farmer Producer Organisations, not APMC mandis
WTO rulebook must evolve to support food security, rural livelihoods in developing countries


text:
Jesus' Facebook Page
Date: September 6, 2011Author: Dan
Dan Gilgoff, CNN.com Religion Editor, reports
Take a guess: What Facebook page has a more highly engaged audience than any other? Justin Bieber's? Kim Kardashian's? Manchester United football club's?
No, it's Jesus Daily, a page that had 8.4 million "Likes" and belongs to a North Carolina-based diet doctor.
. . . The [New York] Times notes that Jesus Daily is hardly the only wildly popular religious page and that the page speaks to a trend of people connecting with their faith outside of traditional religious institutions:
What is new is that millions of people are also turning to Facebook pages, like the Jesus Daily, created by people unaffiliated with a religious leader or a specific house of worship. With 8.2 million fans, the Jesus Daily counted 3.4 million interactions last week, compared with about 630,000 interactions among Justin Bieber's 35 million fans, the AllFacebook.com analysis shows. The Bible Facebook page, run by the United Bible Societies in Reading, England, has eight million fans and also beat Mr. Bieber with about a million interactions.
Amid pages for Lady Gaga, Texas Hold'em Poker and Manchester United, Joyce Meyer Ministries is in the top 20, along with another page devoted to Jesus Christ, and the Spanish-language page Dios Es Bueno, or God Is Great.
. . . Your thoughts?
Thoughts? Yes, if we could only get that much attention for the Shroud of Turin. But at least we are getting over 1000 visitors a day viewing more than 2000 pages. See Jesus' Facebook fans are 'most engaged' – CNN Belief Blog – CNN.com Blogs
Previous Previous post: More on the Tablecloth of Turin: Linen Cloth Used for the Eucharist (Communion/Mass)
Next Next post: Catholic Archdiocese Gift to Washington National Cathedral
One thought on "Jesus' Facebook Page"
lemony grant says:
i find that a bit disrespectful putting jesus christ on facebook


text:
Q: How to make a datagrid see edits in a control? I have a user control that I am using to populate a datagrid.
I would like the user to be able to add items by editing the empty row at the bottom. (This is why I am using a datagrid rather than an itemscontrol)  However the datagrid does not realise that the last item is edited unless the user clicks the background of the control.  I would like the new item to be added when the user makes changes on the properties that the control exposes.
XAML of the control:
<UserControl x:Class="ControlTest.MyControl"
         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
         xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
         xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
         xmlns:local="clr-namespace:ControlTest"
         mc:Ignorable="d"
         d:DesignHeight="50" d:DesignWidth="300"
         DataContext="{Binding Path=., Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
         >
<StackPanel Orientation="Vertical">
        <TextBox Text="{Binding Path=p1, Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
           Width="300"
           Height="30"
           VerticalAlignment="Center"/>
    <ComboBox ItemsSource="{Binding Path=DropDownValues,
              RelativeSource={RelativeSource Mode=FindAncestor,
                AncestorType=local:MyControl}}"
              SelectedItem="{Binding Path=p2, Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
              Height="30"/>
    </StackPanel>
</UserControl>

cs:
public partial class MyControl : UserControl
{
    private static readonly DependencyProperty DropDownValuesProperty =
        DependencyProperty.Register(
        "DropDownValues",
        typeof(List<String>),
        typeof(MyControl),
        new FrameworkPropertyMetadata(new List<String>()
        ));
    public List<String> DropDownValues
    {
        get
        {
            return (List<String>)GetValue(DropDownValuesProperty);
        }
        set
        {
            SetValue(DropDownValuesProperty, value);
        }
    }

    public MyControl()
    {
        InitializeComponent();
    }
}

DataGrid XAML
    <DataGrid
        AutoGenerateColumns="False"
        ItemsSource="{Binding objs, Mode=TwoWay}"
        HeadersVisibility="None"
        Margin="0,0,0.4,0"
        CanUserAddRows="True"
        >
        <DataGrid.ItemsPanel>
            <ItemsPanelTemplate>
                <StackPanel Orientation="Horizontal"/>
            </ItemsPanelTemplate>
        </DataGrid.ItemsPanel>
        <DataGrid.Columns>
            <DataGridTemplateColumn Width="300">
                <DataGridTemplateColumn.CellTemplate>
                    <DataTemplate DataType="local:Measure">
                        <local:MyControl
                            DataContext="{Binding ., Mode=TwoWay, UpdateSourceTrigger=PropertyChanged}"
                            DropDownValues=
                        "{Binding DataContext.list, RelativeSource={RelativeSource FindAncestor, AncestorType={x:Type Window}}}"
                            Width="300"
                        />
                    </DataTemplate>
                </DataGridTemplateColumn.CellTemplate>
            </DataGridTemplateColumn>
        </DataGrid.Columns>
    </DataGrid>

Can I make this work, and/or is there a better way to do this?

A: I would like to suggest you a different way of doing that:
set CanUserAddRows=false on your DataGrid and then manually add rows to the ObservableCollection<Something> to which your DataGrid is bound to.
OR
If you are still interested in the approach that you follow:
In your xaml file:
<DataGrid x:Name="myDataGrid" CellEditEnding="DataGrid_CellEditEnding" .....>
    <!--Some Code-->
</DataGrid>

Then in the Code-Behind:
private void DataGrid_CellEditEnding(object sender, DataGridCellEditEndingEventArgs e)
{
    myDataGrid.CommitEdit();
}

If you don't understand anything then feel free to ask.
Update
If you are following the same approach:
In your DataGrid's Beginning edit event you can try:
private void DataGrid_BeginningEdit(object sender, DataGridBeginningEditEventArgs e)
{
    if ((selectedRow as DataGridRow).Item.ToString() != "{NewItemPlaceholder}")
    {
        //Here you can add the code to add new item. I don't know how but you should figure out a way
    }
}

Note: The code mentioned above is not tested.
I would also suggest you :
Not to use DataGrid. Instead use ListBox. Because, you are trying to add some data. At this time you never need sorting, searching and column-reordering fascilities. In such scenario, ListBox is useful as it is light-weight control than datagrid. I have a sample here: https://drive.google.com/open?id=0B5WyqSALui0bTXFGZWxQUWVRdkU

A: Is the problem that the UI is not being notified of changes to the objs collection? What I would do is try setting up whatever view model that contains objs to make objs an observable collection. I would also ensure that whatever objs is an observable collection of implements INotifyPropertyChanged and that properties p1 and p2 both fire OnPorpertyChanged when they are set.
public ObservableCollection<YourObject> objs

and
public class YourObject : INotifyPropertyChanged
{
    protected void OnPropertyChanged(string Name)
    {
        PropertyChangedEventHandler handler = PropertyChanged;
        if (handler != null)
        {
            handler(this, new PropertyChangedEventArgs(Name));
        }
    }

    private string _p1;
    public string p1
    {
        get { return _p1; }
        set
        {
            if (_p1 != value)
            {
                _p1 = value;
                OnPropertyChanged("p1");
            }
        }
    }
    private string _p2;
    public string p2
    {
        get { return _p2; }
        set
        {
            if (_p2 != value)
            {
                _p2 = value;
                OnPropertyChanged("p2");
            }
        }
    }
}

redpajama_set_name: RedPajamaStackExchange


text:
ʻUiha est une île appartenant au royaume des Tonga. Elle dépend du groupe insulaire de Ha'apai et du district de Lifuka.

L'île fut longtemps le lieu de sépulture des membres de la famille royale. Elle conserve un site sacré traditionnel (Makahokovalu) situé dans sa partie septentrionale et une église comptant parmi les plus anciennes du pays.

Notes et références

Île aux Tonga

redpajama_set_name: RedPajamaWikipedia


ansehen, blockieren, link zum Tweet kopieren, embed this Video. Registrieren zweiwege-Kurz-Codes (zum Senden und Empfangen land. Wexford: Up to 2-Night 4* Stay with Leisure Access Riverside Park Hotel Riverside Park Hotel.
Discover the best gift ideas with. Groupon : check out great deals for Gifts for Him, Gifts for Her, Gifts for Couples, Birthday Gifts and. Hotel deals in Dublin : Discover the best hotels in Dublin. 8- or 10-Day Ireland Vacation with Villa, Hotel and Air from Great Value Vacations.
Kerry: 1 to 3 Nights with Breakfast Kerry Coast Hotel Caherciveen Co Kerry. Buy and redeem Groupon deals directly from your mobile device, no need to print vouchers or clip coupons. Sligo: 1- or 2-Night 4* Spa Break Castle Dargan. Malta: Up to 7-Night 4* Stay with Flights. Donegal: Up to 2 Nights with Breakfast An Grianan Hotel Inishowen. With the Groupon app you can: Get promo codes and special savings alerts for deals near you, instantly on your mobile device. Status, online, latest check gets.4 of its traffic from Ireland where it is ranked #264. Shop for fun themed collections for holidays and events. Donegal: 4* 1- or 2-Night Break with Spa The RedCastle Hotel Spa Donegal Moville Portlaoise: 1- or 2-Night 4* Stay with Breakfast Midlands Park Hotel Portlaoise Six Nations Rugby: Up to 4-Night Stay with Tickets Independent World Choice Holidays.


The government needs to do more to support UK businesses developing low carbon technologies such as smart meters, heat pumps and renewable energy technologies, according to the cross-party Energy and Climate Change Committee.
Energy & Climate Change Select Committee chair Tim Yeo said: "Entrepreneurs developing exciting new sustainable technologies sometimes need help to bridge the 'valley of death' and bring products to market.
"We were surprised and disappointed to hear businesses and academic partners, among others, express continual frustration at the lack of consultation surrounding the government's new low carbon strategy.
"These innovators could hold the key to getting the UK over the line on our carbon emissions targets, but it's going to be much harder for them to do that without better coordination to get us all pulling in the same direction and making better use of limited public funds.
The Energy & Climate Change Select Committee scrutinised the government's performance in supporting firms developing new products for the £3.4 trillion international low carbon good and environmental services sector - following up on a National Audit Office report that had been critical of the Department for Energy & Climate Change's record in 2010.
The committee found that there has not been enough progress since then and the resources allocated by the government to support companies do not match its level of policy ambition in this area.


text:
Former Supreme Court Justice John Paul Stevens, a longtime supporter of LGBTQ rights, dies at 99
From striking down sodomy laws to supporting marriage equality, Stevens was a reminder of how much the Court changed over time.
Clarence Thomas suggests the Supreme Court's marriage equality ruling should be overturned
The Supreme Court punted on another case involving an anti-gay baker, but the biggest impact on marriage equality may have happened in an entirely different case.
The Supreme Court is going to rule on LGBTQ job discrimination. This could end badly.
The Supreme Court announced that it will be hearing three cases about anti-LGBTQ discrimination this year in what could be a dramatic blow against LGBTQ discrimination protections. The three federal cases all involve questions about how Title VII of the Civil Rights Act of 1964 applies to LGBTQ people. Title VII bans discrimination on the […]
A baker turned away a lesbian couple because of her 'spiritual conviction'
The baker told the lesbians: "I do love you in The Lord!"
A federal court just found a First Amendment right to force kids into conversion therapy
A federal court ruled that talk therapy is just speech, so it's probably unconstitutional to ban it.
Japan's supreme court rules in favor of forced sterilization of trans people
The court said that there might be "problems" for a child if a parent is transgender.
Supreme Court allows Trump's ban on trans military members to go into effect
Trump's ban on transgender people from the military can start while court cases challenging it work their way through the system.
Trump is planning to replace RBG on the Supreme Court & deplorables are celebrating
Trump has asked far right groups for advice on who should replace Ruth Bader Ginsburg on the Supreme Court.
The worst political moves of 2018 are all tied to Donald Trump
The president is in a category by himself, but there were plenty of other disastrous choices made by his followers.
Another prominent Republican just quit the party in disgust
"I felt compelled to make a choice now," she said. "It better suits what I do and how I approach issues."