\section{Introduction}

\texttt{SGD} (stochastic gradient descent) can be efficient at training large machine learning models if one  carefully tunes a step size scheduler.
However, tuning step sizes is tedious and costly, especially with large-scale deep learning models. For this reason, a fruitful line of research has focused on
developing \emph{adaptive} methods, that require little to no tuning of the step sizes. A popular family of methods are those that use coordinate-wise (i.e., feature-wise) scaling, such as \texttt{Adagrad}~\cite{ADAGRAD}, \texttt{ADAM}~\cite{ADAM} and \texttt{AMSgrad}~\cite{AMSgrad}. More recently, a new family of methods called \texttt{SPS} (SGD with Polyak Stepsizes) has been proposed \cite{ALI-G,SPS}.
These methods make use of both the loss values and gradient norms at the sampled points, to automatically adjust the step size.
This allows to use a step size that changes from iteration to another depending on the current progress, and also adapts to the particular scaling of
the loss function at hand.

Variants of \texttt{SPS} have been shown to work very well on models that interpolate the data, and even have competitive convergence guarantees in convex~\cite{SPS} and some non-convex settings~\cite{SGDstruct}. The  effectiveness of \texttt{SPS} in the interpolated setting is not surprising, given that
\texttt{SPS} directly  solves the interpolation equations~\cite{ALI-G,TASPS}. However, when the model is far from interpolation, \texttt{SPS} and its variants can fail to converge, unless additional safe guards are put in place. As a consequence \texttt{SPS} methods tend to be less efficient when using regularization (weight decay), data augmentation (such as image rotations), and generally only work well on models with many more parameters than data.

In this paper, we develop new \emph{slack} variants of \texttt{SPS} that are less sensitive to interpolation.
Specifically,
we make the following contributions:

\paragraph{Extending (PA) Passive-Aggressive Methods.} We first show that \texttt{SPS} can be seen as a natural extension of the  \emph{Passive-Aggressive} (PA) methods~\cite{Crammer06} to nonlinear models.

\paragraph{Variational Viewpoint of Stochastic Polyak Methods.} Building upon this viewpoint, we then show that  \texttt{SPS}$_{\max}$~\cite{SPS} and \texttt{ALI-G}~\cite{ALI-G}, two recent variants of the \texttt{SPS} method, can be interpreted as \emph{slack} variants of the PA methods. That is, they allow for a margin of \emph{slack} in the interpolation equations. This in turn
provides a
\emph{variational formulation} of \texttt{SPS}$_{\max}$ and \texttt{ALI-G}. This viewpoint also gives  meaning to the tunable parameter $\lambda$ of \texttt{SPS}$_{\max}$ and \texttt{ALI-G}, namely, it can be interpreted as controlling the strength of a {slack variable}. The higher $\lambda$, the less slack we allow in the interpolation equations.

\paragraph{Max loss Viewpoint.} We also show that all slack variants of the PA methods, including  \texttt{SPS}$_{\max}$ and \texttt{ALI-G}, are in fact solving an auxiliary problem, whereby the objective is to have the \textbf{smallest maximum loss} over the data.

\paragraph{New Slack Polyak Methods.} The variational formulation then leads to the insight of further \emph{regularizing} the slack variable. This enables the slack variable to track the loss function across iterations and set a stable step size. We call our proposed variants \emph{\texttt{SPSL1}} and \emph{\texttt{SPSL2}}.

\paragraph{Convergence Theory.}  We study the \emph{convergence} of our methods, and prove convergence at ${\cal O}(1/t +\mbox{\small constant})$ rate for both \texttt{SPSL1} and \texttt{SPSL2}, where constant is zero under interpolation.

\paragraph{Experimental Validation.}  We conclude with extensive experimental results, where we test the sensitivity of each of the slack methods  \texttt{SPS}$_{\max}$, \texttt{ALI-G}, \texttt{SPSL1} and \texttt{SPSL2} to how far the underlying problem is to interpolation. We also show that the new methods  \texttt{SPSL1} and \texttt{SPSL2} are \emph{competitive} on the benchmark vision classification problems, despite \emph{not using any additional safe guards} as required to make \texttt{SPS}$_{\max}$ and \texttt{ALI-G} stable and competitive.

\section{Related work}
\label{sec:related_work}

\paragraph{ Setup and Notation.}
Let $(x_i,y_i)$ denote the  $i$\textsuperscript{th} data point, where $x_i$ is an input and $y_i$ is an output.
We use $\ell_i(w) \coloneqq \ell(w ; (x_i,y_i))$ to denote the loss evaluated at parameters $w \in \R^d$ over the $i$\textsuperscript{th} data point.
Our objective is to minimize the \emph{average loss} $\ell(w) \coloneqq \frac{1}{n} \sum_{i=1}^n \ell_i(w)$ over a given data set with $n$ data examples. We note that our results also hold for a true expectation where $\ell(w) = \EE{(x,y) \sim {\cal D}}{\ell(w ; (x,y)}$, also known as the test error. Furthermore, our results hold verbatim for an \emph{online regret} given by $\frac{1}{T}\sum_{t=1}^T \ell_{t}(w),$ where $\ell_t$ is an online loss that could be chosen adversarially, which is the original setting of \texttt{PA} methods. For  simplicity, we use the average loss.

\paragraph{ Passive-Aggressive for linear models.}
The Passive-Aggressive (\texttt{PA}) methods \cite{Crammer06} are online learning algorithms that update a model only when the loss on a new example is greater than zero. They do this by introducing the minimal perturbation into the parameters so that this new example is correctly labelled. This is the \emph{aggressive} step. On the other hand, if the example is correctly labelled already, then the methods are \emph{passive} and do nothing.
A similar online algorithm, but using Kullback-Leibler projections instead of Euclidean ones, was proposed in \cite{Herbster01}.
\texttt{PA} methods have been especially successful in natural language processing \cite{mcdonald_2005,blitzer_2006,chechik_2010}.

To formally introduce the \texttt{PA} methods, suppose  that the loss is non-negative and that $\ell_i(w) =0$ if our model correctly labels the $i$\textsuperscript{th} example. Let $w^t \in \R^d$ be the current parameters of our model at some time $t$.
At iteration $t+1$, \texttt{PA} methods update the parameters to $w^{t+1}$ such that the $i$\textsuperscript{th} example, usually randomly sampled, is correctly classified, that is $\ell_i(w^{t+1})=0$.
They do this by making the smallest possible perturbation to the current parameter vector $w^t$ by solving the projection
\begin{equation}
    w^{t+1} = \mbox{argmin}_{w\in\R^d} \norm{w-w^t}^2
    \mbox{subject to} ~ \ell_i(w) = 0 \enspace. \label{eq:PAproj}
\end{equation}
For simple loss functions, the update~\eqref{eq:PAproj} often enjoys a closed-form solution.
For instance, let us consider binary classification problems where data points $(x_i,y_i)$ are such that $y_i\in \{-1,  1\}$. If one minimizes the hinge-loss $\ell_i(w) = (1- y_i\dotprod{w,x_i})_+$ over a linear model, where $a_+ \coloneqq \max\{0, a\}$ denotes the non-negative part, then the closed-form solution to~\eqref{eq:PAproj} is given by
\begin{equation} \label{eq:PA}
    w^{t+1} = w^t +\frac{\ell_i(w^t)}{\norm{x_i}^2} y_i \, x_i \enspace.
\end{equation}
See Appendix A in~\cite{Crammer06} for the proof.
The \texttt{PA} method~\eqref{eq:PAproj} is appealing because it does not require learning rates and the update~\eqref{eq:PA} adapts to the \emph{scale} of $x_i$. Unfortunately for most nonlinear models and loss functions there is no closed form solution to the projection in~\eqref{eq:PAproj}, greatly restricting the applications of \texttt{PA} methods.

\paragraph{ Passive-Aggressive extensions.}
The \texttt{PA} methods \cite{Crammer06} were initially applied to regression, classification and structured prediction problems, but always with an underlying linear model. \texttt{PA} methods have subsequently been adapted to solving the non-negative matrix factorization (NMF) problem ~\cite{BlondelKU14}. NMF can be cast as solving a nonlinear matrix equation, which is bilinear in the two unknown matrices. In \cite{BlondelKU14} the authors proposed to solve this bilinear problem by alternating between freezing one of the two unknown matrices and applying a \texttt{PA} step. This approach cannot be extended to general nonlinear models and problems since it relies on the bilinear nature of NMF.

The \texttt{PA} framework has also been very recently used in conjunction with a class of quadratic models given by a difference-of-squares (DoS)~\cite{Saul2021}. Although there is no closed-form update for~\eqref{eq:PAproj} for these DoS models, the authors propose a simple bounded one-dimensional search based on the S-procedure to find an approximate solution.

\paragraph{ \texttt{SGD} with Polyak stepsize (\texttt{SPS}).} \texttt{SPS} methods use both the gradient norm and the loss value of the sampled points. The vanilla \texttt{SPS} update is
\begin{align}
    w^{t+1} = w^t -\frac{\ell_i(w^t)}{\norm{\nabla \ell_i(w^t)}^2} \nabla \ell_i(w^t) \enspace. \label{eq:SPS}
\end{align}
\texttt{SPS} methods have drawn much attention recently as an effective method for training deep neural networks, even though to work effectively in practice, the update above needs some additional alterations and safe-guards; otherwise the method can diverge when $\norm{\nabla \ell_i(w^t)}$ in the denominator is near zero.

A practical update to avoid this issue is that of \texttt{ALI-G} \cite{ALI-G}:
\begin{equation}
     w^{t+1} = w^t - \min\left\{\frac{\ell_i(w^t)}{\norm{\nabla \ell_i(w^t)}^2+\varepsilon}, \; \eta \right\} \nabla \ell_i(w^t) \enspace,
\label{eq:exact_ALIG}
\end{equation}
where $\varepsilon \geq 0$ and $\eta > 0$ are tunable parameters.
If $\varepsilon$ is set to $0$ and $\ell_i (w^t) - \ell_i^*$, with nonzero $\ell_i^*$, is used in the numerator of the Polyak step size of~\eqref{eq:exact_ALIG}, then one recovers \texttt{SPS}$_{\max}$ later introduced in~\cite{SPS}.

In~\cite{TASPS}, the authors showed that \texttt{SPS} is formally a subsampled Newton-Raphson method~\cite{SNR}  for solving the nonlinear equations
\begin{equation}\label{eq:interpolate}
    \ell_i(w) = 0 \; , \quad \mbox{for }i=1,\ldots, n \enspace.

\end{equation}
There only exists a solution to~\eqref{eq:interpolate} if we are in the \emph{interpolation regime}, that is to say, that our model has sufficient degrees of freedom that it can \emph{perfectly fit} all of the given examples.
This assumption is typically met with over-parametrized deep neural networks~\cite{ZhangBHRV17,MaBB18} or in non-parametric regression models~\cite{belkin2019does,liang2020just}.
In~\cite{TASPS} the authors develop a weaker type of interpolation assumption that rests on knowing the total optimal loss $\ell(w^\star)= \frac{1}{n}\sum_{i=1}^n\ell_i(w^\star)$ and using this as a \emph{target} value.

\paragraph{ Adaptive methods.}
The ultimate goal of adaptive methods is to have a method that works well with little to no parameter tuning.
One such adaptive method is \texttt{ADAM}~\cite{ADAM}, which works remarkably well on a wide range of DNNs with default parameter settings.
The practical success of \texttt{ADAM} has inspired a large number of papers that attempts to improve upon \texttt{ADAM}~\cite{AMSgrad}, understand \texttt{ADAM}~\cite{balles2018dissecting,AMSgrad}, or extend it~\cite{Zaheer2018}.
Due to the vast number of variants of \texttt{ADAM} that now exist in the literature, we cannot do the literature justice, since it would require a dedicated survey paper.
Here, we restrict ourselves to the admittedly limited scope of developing a foundation for adaptive methods based on Polyak step sizes.
\texttt{SPS} has an intuitive and mathematically grounded motivation, one that we further develop here.
Though our methods share the same overarching objective as adaptive methods such as \texttt{ADAM} and its variants, our methods represent a distinct approach, and enjoy a formal derivation.

Model-based methods \cite{asi2019importance, Chada-accel-model-2021}  also make use of linearizations in combination with proximal operators to derive new stochastic gradient methods. In fact, the \texttt{SPS} and \texttt{ALI-G} methods can be understood as a model based method~\cite{TASPS}.
For an excellent introduction to  online learning, with connections to model based and  PA methods we recommend the monograph~\cite{Orabona:2019} and its related blog.
Finally, another approach that is being actively researched recently is the use of \texttt{SGD} in combination with a line search~\cite{vaswani2019painless}.

\section{Variational perspective of SPS}
\label{sec:slack}
We now present our novel insights into viewing SPS and its variants as
an extension of the PA (Passive-Aggressive) methods. In doing so, we also give new variational perspectives on SPS methods, show that the new variants of the SPS methods can be interpreted as methods that solve a weaker form of interpolation, and as consequence, also as methods that solve a certain \emph{max} loss problem.

\subsection{Passive-Aggressive for general nonlinear models}

Although Passive-Aggressive methods have been developed for some nonlinear models
(cf.\ Section \ref{sec:related_work}), we are not aware of an efficient approach
that works for general nonlinear models.
Indeed, for most nonlinear models, such as Deep Neural Networks (DNNs), there is no closed-form solution to the projection~\eqref{eq:PAproj}. To retain much of the appeal of \texttt{PA} methods and make use of nonlinear models, we propose to linearize the loss around $w^t$ and project
\begin{align}
    w^{t+1} =  & \mbox{argmin}_{w\in\R^d} \norm{w-w^t}^2 \label{eq:PAprojlin} \;\;  \mbox{ s.t. }\ell_i(w^t)+ \dotprod{\nabla \ell_i(w^t), w-w^t}=0 \enspace.
\end{align}
The linearization in~\eqref{eq:PAprojlin} is a reasonable approximation to $\ell_i(w)$ when $w$ is close to $w^t$, and because of the projection, we choose $w$ to be as close as possible to $w^t$. It turns out that the closed-form solution of \eqref{eq:PAprojlin} is exactly given by the SPS update in \eqref{eq:SPS}.

Using this connection between the \texttt{SPS} and \texttt{PA} methods, we first formalize typical
safe-guarded variants of \texttt{SPS} as \texttt{PA} methods that make use of a \emph{slack} variable. We
 use these  insights to develop new and efficient slack \texttt{SPS} variants.

\subsection{Adding slack}

In most settings, the \texttt{PA} methods are in fact too aggressive. In particular,
outside of the interpolation regime, where there exists no solution to~\eqref{eq:interpolate}, setting all losses to zero is not possible, and thus eventually forcing a particular $\ell_i(w) =0$ will deviate other losses from zero. To better control the trade-off between losses over different examples, in \cite{Crammer06} a slack variable $s \in \R$ was introduced and finding $w \in \R^d$ such that
\begin{equation}\label{eq:slackconstraint}
    \ell_i(w) \leq s, \quad \mbox{for }i=1,\ldots, n \enspace,
\end{equation}
while simultaneously forcing $s$ to be as small as possible. To make $s$ small, we can either
minimize what we call the \emph{L1 slack formulation} given by
\begin{align}
    &\min_{w\in\R^d, \, s \geq 0} s  \label{eq:slackobjmax} \quad\mbox{s.t.} \quad \ell_i(w)  \leq s, \quad \mbox{for }i=1,\ldots, n \enspace,
\end{align}
or the \emph{L2 slack formulation} given by
\begin{align}
    \label{eq:slackobjL2}
    &\min_{w \in \R^d, \, s \in \R} s^2 \quad \mbox{s.t.} \quad \ell_i(w)  \leq s, \quad \mbox{for }i=1,\ldots, n \enspace.
\end{align}
The slack variable allows us to control the global trade-off between different losses.

When $\ell_i(w)$ is a relatively simple function, such as the hinge loss over a linear model, then after sampling the $i$\textsuperscript{th} constraint in either~\eqref{eq:slackobjmax} or~\eqref{eq:slackobjL2}, there is a closed-form solution to the resulting variational problem as shown in~\cite{Crammer06}.
For most nonlinear losses and models, however, there is no solution, and thus we resort to linearization once again.
But first, we present an alternative interpretation of~\eqref{eq:slackobjmax} and~\eqref{eq:slackobjL2}.

\subsection{Max loss Viewpoint}
\label{sec:maxloss}
The slack formulations can also be seen through the lens of robust learning.
Indeed, we can substitute out the slack variable in~\eqref{eq:slackobjmax} by
observing that the smallest possible $s$ that is greater than every $\ell_i(w)$
is necessarily $\displaystyle s = \max_{i=1,\ldots, n} \ell_i(w).$
Thus~\eqref{eq:slackobjmax}  and~\eqref{eq:slackobjL2} are equivalent to
\begin{equation}
    \min_{w \in \R^d} \max_{i=1,\ldots, n} \ell_i(w) \enspace. \label{eq:minmax}
\end{equation}
We refer to~\eqref{eq:minmax}
as the max loss.
 The max loss~\eqref{eq:minmax}
can be seen as robust learning tasks, where the aim is to find $w$ such that no single example is badly classified. Contrast this with the Empirical Risk Minimization (ERM) task where the goal is to minimize the average of the losses. In particular~\eqref{eq:minmax} is a conservative upper bound on the ERM since
\begin{equation} \label{eq:maxbound}
    \ell(w) = \frac{1}{n} \sum_{i=1}^n \ell_i(w) \leq \max_{i=1,\ldots, n} \ell_i(w) \enspace.
\end{equation}
If interpolation holds, then the above is a tight over-approximation, in that the ERM and the robust objective have the same solution set. Next, we propose methods for approximately solving~\eqref{eq:slackobjmax} and~\eqref{eq:slackobjL2}.

\subsection{A Variational form of \texttt{SPS}$_{\max}$}

Let  $\lambda>0$ be a  \emph{slack} parameter.
Our first method for solving~\eqref{eq:slackobjmax} proceeds by
by sampling the $i$\textsuperscript{th} constraint, linearizing and projecting as follows
\begin{align}
    w^{t+1}, s^{t+1} =& \mbox{argmin}_{w\in\R^d, s \geq 0} \tfrac{1}{2}\norm{w - w^t}^2 +\lambda s, \nonumber \\
    &\; \; \mbox{s.t. } \ell_i(w^t) + \dotprod{\nabla \ell_i(w^t), w - w^t} \leq s \enspace. \label{eq:SPSmaxproj}
\end{align}
Fortunately this method has a simply closed form solution.
\begin{lemma}\label{lem:SPSmax}
The closed-form solution to~\eqref{eq:SPSmaxproj} is
\begin{align}
    w^{t+1} &= w^t - \min\left\{\frac{\ell_i(w^t)}{\norm{\nabla \ell_i(w^t)}^2}, \; \lambda \right\} \nabla \ell_i(w^t) \enspace, \quad  \label{eq:SPSmax}\\
s^{t+1} &= \max\{\ell_i(w^t)- \lambda \norm{\nabla \ell_i(w^t)}^2 , \; 0 \} \enspace.
\end{align}
\end{lemma}
\begin{proof}
    The proof follows by applying Lemma~\ref{lem:slackL1ineqconst}
\end{proof}

Update~\eqref{eq:SPSmax} was recently introduced in an adhoc manner in~\cite{SPS} as a practical variant of the SPS method that caps the step size and named the \texttt{SPS}$_{\max}$ method.
Lemma~\ref{lem:SPSmax} thus gives a novel formalization of \texttt{SPS}$_{\max}$ as a projection method, and as an extension of the \texttt{PA-I} method
proposed in~\cite{Crammer06} to nonlinear models.
Analogously, the ALI-G method~\cite{ALI-G} can also be seen as an extension of the \texttt{PA-II} method proposed in~\cite{Crammer06}, as we show next.

\section{A Variational form of \emph{Almost} \texttt{ALI-G}}
\label{sec:ALI-G-almost}
Analogously to the previous section, we derive an iterative method for solving~\eqref{eq:slackobjL2} by sampling a single constraint, linearizing and projecting.
\begin{align}
    w^{t+1}, s^{t+1} =& \mbox{argmin}_{w\in\R^d} \tfrac{1}{2}\norm{w - w^t}^2 +\lambda s^2 \nonumber  \\
    &\; \; \mbox{s.t. } \ell_i(w^t) + \dotprod{\nabla \ell_i(w^t), w - w^t} \leq s \enspace.
    \label{eq:ALIGproj}
\end{align}

The key difference with \eqref{eq:SPSmaxproj} is that $s$ is squared. The closed-form solution is given as follows.
\begin{lemma}
Let $\lambda  \geq 0$.
The solution to~\eqref{eq:ALIGproj} is
\begin{align} \nonumber
    w^{t+1} & =  w^t -  \frac{\ell_i(w^t)}{ \lambda^{-1} + \norm{\nabla \ell_i(w^t)}^2} \nabla \ell_i(w^t) \enspace, \\
    s^{t+1} & =   \frac{ \ell_i(w^t)}{ 1 +\lambda \norm{\nabla \ell_i(w^t)}^2} \enspace. \label{eq:SPSdam}
\end{align}
We refer to this method as \texttt{SPS}$_{dam}$.
\end{lemma}
\begin{proof}
The solution follows by Lemma~\ref{lem:slackL2ineqconst}.
\end{proof}
We call~\eqref{eq:SPSdam} the \texttt{SPS}$_{dam}$ method because it is equivalent to \texttt{SPS} but with an additional dampening term $\lambda^{-1}$.
\texttt{SPS}$_{dam}$  is an extension of the \texttt{PA-II} method given in~\cite{Crammer06} to nonlinear models. It is also very similar to the \texttt{ALI-G} update in \eqref{eq:exact_ALIG} with $\varepsilon = \lambda^{-1}$.
The only difference being that \texttt{ALI-G}  caps the step size at a prescribed maximum $\eta$.

From the perspective of \texttt{SPS} methods, both slack variants help stabilize the \texttt{SPS} method~\eqref{eq:SPS}, and avoid a large step size by capping it as in~\eqref{eq:SPSmax}, or by dampening it in~\eqref{eq:SPSdam}.
But both methods still need to carefully choose
$\lambda$ to work well in practice.
Indeed, $\lambda$ here plays much the same role as a step size. If $\lambda$ is small, or converges to zero, both \texttt{SPS}$_{\max}$~\eqref{eq:SPSmax} and \texttt{SPS}$_{dam}$~\eqref{eq:SPSdam} halt.
On the other extreme, if $\lambda$ is large, both methods can diverge.
In \cite{SPS} the authors propose a rule of thumb that chooses a different $\lambda$ at each iteration for~\eqref{eq:SPSmax}. As for~\eqref{eq:SPSdam}, in \cite{ALI-G} the authors cap the step size, which requires another tunable parameter.

In the next section, we propose new \texttt{SPS} variants that iteratively update the slack variable and then use it to adjust the step size.

\section{Regularizing the Slack}

Both variational forms~\eqref{eq:SPSmaxproj} and~\eqref{eq:ALIGproj} rely on linearizing around $w^t$ and $s^t$ the constraints~\eqref{eq:slackconstraint} that depend on both $w$ and $s$. These linearizations are only accurate when both $w$ and $s$ are close to $w^t$ and $s^t$. Yet, the objective in both~\eqref{eq:SPSmaxproj} and~\eqref{eq:ALIGproj}
only incentivises $w$ to be close to $w^t$, but allows $s$ to be far from $s^t.$ We find this to be a cause of instability in these methods.
Furthermore, because of this,  both in \eqref{eq:SPSmax} and \eqref{eq:SPSdam}, the slack variable $s^{t+1}$ plays no direct role in updating $w^{t+1}$. This is a missed opportunity, because the slack variable can be used to track the progress towards the solution and ultimately help halt the method.

\subsection{L1-Regularized Slack}

Suppose we have a current estimate of the slack variable $s^t$.
We can use our current estimate of the slack to add some regularization to the variational form of \texttt{SPS}$_{\max}$ in~\eqref{eq:SPSmaxproj} as follows
\begin{align}
    w^{t+1},  s^{t+1}& = \underset{w\in\R^d, s\geq 0}{\mbox{argmin}} \tfrac{1}{2}\norm{w - w^t}^2  + \tfrac{1}{2} (s-s^t)^2+ \lambda s \nonumber \\ \,  &\quad  \mbox{s.t. } \;\ell_i(w^t) + \dotprod{\nabla \ell_i(w^t), w - w^t} \leq s \enspace.     \label{eq:SPSL1proj}
\end{align}
With this small change, the resulting method now makes use of the slack variable to set the step size, as can be seen in the following closed-form solution to~\eqref{eq:SPSL1proj}.
\begin{lemma} \label{lem:ProjL1pludL2}
The closed-form solution to~\eqref{eq:SPSL1proj} is given by~\eqref{eq:SPSL1} . We call this the \texttt{SPSL1} method.
\begin{align}
    \gamma_t^{L1} &= \frac{(\ell_i(w^t)-s^t+\lambda)_+}{1+ \norm{\nabla \ell_i(w^t)}^2} \nonumber  \\
    \gamma_t &= \min\left\{ \gamma_t^{L1}, \; \frac{ \ell_i(w^t)}{\norm{\nabla \ell_i(w^t)}^2} \right\}\nonumber \\
    w^{t+1} &= w^t - \gamma_t \nabla \ell_i(w^t) \\
    s^{t+1} &= \left(s^t - \lambda + \gamma_t^{L1}\right)_+ +\label{eq:SPSL1}
\end{align}

\end{lemma}
Missing proofs can  be found in the appendix.

What sets the \texttt{SPSL1} update~\eqref{eq:SPSL1} apart from the previous two slack methods in Section~\ref{sec:slack} is that the slack variable is now being updated iteratively and is used to update the step size adaptively.
For instance,  starting from $s^0 = 0$ and if $\lambda$ is small enough\footnote{Specifically if $\lambda \leq \tfrac{\ell_i(w^t)}{\norm{\nabla \ell_i(w^t)}^2}$, which in the convex and $L_{\max}$--smooth setting occurs if $\lambda \leq \frac{1}{2L_{\max}}.$ This is exactly the restriction we apply to $\lambda$ in the forthcoming Theorem~\ref{theo:SPSL1smooth}. }, the  \texttt{SPSL1} takes the more aggressive \texttt{SPS} updates in $w^t$~\eqref{eq:SPS} since then $\gamma_t = \ell_i(w^t)/\norm{\nabla \ell_i(w^t)}^2$.
As $s^t$ starts to increase, the more conservative smaller step sizes $\gamma_t = \gamma_t^{L1}$ will be used. Finally if $s^t$ is too large, then $\gamma_t = \gamma_t^{L1} =0$ and the method will not update $w^t$, but will instead decrease $s^t$ since in this case $s^{t+1} = (s^t -\lambda)_+$
We can observe this behavior experimentally  in Figure~{\bf a)}.

\begin{minipage}[l]{0.5\textwidth}
Regularizing the slack variable can also smooth the trajectory of $s^t$, as we see
in Figure~{\bf a)} where we show how $s^t$ for both \texttt{SPSL1} and \texttt{SPS}$_{\max}$ converge to the same value, but the slack variable of \texttt{SPSL1} takes a smoother route.
Finally, we can also see that  \texttt{SPS}$_{\max}$ is more sensitive to the tuning of $\lambda$ as compared to \texttt{SPSL1} by comparing the two update formulas~\eqref{eq:SPSmax} and~\eqref{eq:SPSL1}.
When $\lambda$ is small for \texttt{SPS}$_{\max}$ the method necessarily slows down, and in the extreme when $\lambda \rightarrow 0$ the \texttt{SPS}$_{\max}$ stops.
In contrast, for $\lambda$ small, we have that $\gamma_t = \gamma_t^{L1}$ and \texttt{SPSL1} switches to a more conservative update but does not stop.
\end{minipage}
\begin{minipage}[r]{0.5\textwidth}
    \centering
     \includegraphics[width=3.0cm]{colon-cancer-l-01-slack-reg-1.00e-01} \hspace{0.2cm}

     \includegraphics[width=3.0cm]{mushrooms-l-01-slack-reg-1.00e-01}\\

    { {\bf Figure a).} Slack variable $s^t$ for \texttt{SPS}$_{\max}$, \texttt{SPS}$_{dam}$, \texttt{SPSL2} and \texttt{SPSL1} all with $\lambda =0.01$ on logistic regression. Left: \texttt{colon-cancer} dataset. Right:  \texttt{mushrooms} dataset.}

\end{minipage}

\subsection{L2-Regularized Slack}

We can also regularize the slack variable in the variational form of \texttt{SPS}$_{dam}$ in~\eqref{eq:ALIGproj} as follows
\begin{align}

    \underset{w \in \R^d, s \in \R}{\min}&  \;\norm{w - w^t}^2 +(s-s^t)^2 + \lambda s^2,\, \mbox{  s.t.  } \ell_i(w^t) + \dotprod{\nabla \ell_i(w^t), w - w^t} \leq s \enspace,    \label{eq:SPSL2proj}
\end{align}
where again $\lambda >0$ is a regularization parameter.
\begin{lemma}\label{lem:SPSdam}
The closed-form update of~\eqref{eq:SPSL2proj} is given by
\begin{align}

    w^{t+1} &= w^t - \frac{(\ell_i(w^t) - \hat{\lambda} s^t)_+}{\norm{\nabla \ell_i(w^t)}^2 +\hat{\lambda}} \nabla \ell_i(w^t)\\
    s^{t+1} &= \hat{\lambda}\left(s^t + \frac{(\ell_i(w^t) - \hat{\lambda}s^t)_+}{\norm{\nabla \ell_i(w^t)}^2 +\hat{\lambda}}\right). \label{eq:SPSL2}
\end{align}
where  $\hat{\lambda} \coloneqq 1/(1 + \lambda)$.
We refer to~\eqref{eq:SPSL2}  as \texttt{SPSL2}.

\end{lemma}

This new \texttt{SPSL2} method now uses the slack variables $s^t$ to adjust the step size, which helps integrate information across iterations.
As we start from $s^0 = 0$, the \texttt{SPSL2} update in $w$ is similar to the \texttt{ALI-G} method~\eqref{eq:exact_ALIG} (with $\eta$ very large).
As the slack variable increases,  the resulting step size  decreases, which in turn makes $s^t$ decrease, thus making an effective feedback between slack and step size. See Figure~{\bf a)} for a sample trajectory of the slack, and this ``increase then decrease'' phenomenon.

Furthermore, as $\lambda$ increases,  \texttt{SPSL2}  is closer  to the \texttt{SPS} update~\eqref{eq:SPS}.
In the extreme where $\lambda \rightarrow \infty$ (thus $\hat{\lambda} \rightarrow 0$) we have that  \texttt{SPSL2} is equivalent to \texttt{SPS}.

\section{Convergence of \texttt{SPSL1}}
\label{sec:sonv_spspl1_main}

To prove convergence of \texttt{SPSL1}, we consider a small simplifying change to the method: we remove the explicit non-negativity constraint on the slack variable and add relaxation. That is, by dropping $s \geq 0$ in~\eqref{eq:SPSL1proj} we have
\begin{align}
    w^{t+\tfrac{1}{2}}, s^{t+\tfrac{1}{2}} &= \! \underset{w\in\R^d, s \in \R}{ \mbox{argmin}}  \tfrac{1}{2}\norm{w - w^t}^2 + \tfrac{1}{2}(s-s^t)^2 +\lambda s, \;
    \mbox{s.t. }  \ell_i(w^t) + \dotprod{\nabla \ell_i(w^t), w - w^t} \leq s \enspace.  \nonumber \\
    [ w^{t+1},s^{t+1} ] &= (1-\gamma)[ w^{t}, s^t] + \gamma [w^{t+\tfrac{1}{2}}, s^{t+\tfrac{1}{2}}]

    \label{eq:SPSL1noposproj-main}
\end{align}
where the second step is the relaxation and $\gamma \in (0,  1)$ is the relaxation parameter.
The closed-form solution of~\eqref{eq:SPSL1noposproj-main} can be found in detail in Section~\ref{sec:SPSL1nopos}.
This version of \texttt{SPSL1} in~\eqref{eq:SPSL1noposproj-main} is equivalent to~\eqref{eq:SPSL1proj} for non-negative losses that are convex and smooth, since  these assumptions guarantee the non-negativity of the slack variables $s^t$.
We use this property to establish the next theorem.
\begin{theorem} \label{theo:SPSL1smooth}
Fix $(w^\star,s^{\star}) \in \R^{d+1}$ and consider the $(w^t,s^t)$ iterates given by~\eqref{eq:SPSL1noposproj-main}.
Let $\bar{w}^T = \frac{1}{T} \sum_{t=0}^{T-1} w^t$, let $\ell_i$ be non-negative and let $s^0 \geq 0.$
If $\ell_i$ is convex, $L_{\max}$--smooth,  and $\lambda \leq 1/2L_{\max}$, then $s^t \geq 0 $  and
\begin{align}
  \E{ \ell (\bar{w}^T)}
   & \leq \frac{1}{2 \gamma \lambda T}\frac{\norm{w^{0} -w^\star}^2  + (s^{0} -s^{\star})^2}{(1-\gamma )(1- \lambda L_{\max})}  +  \frac{1}{n} \sum_{i=1}^n\frac{(\ell_i(w^\star)+\lambda)^2 - \lambda^2  }{2\gamma \lambda (1-\gamma) (1- \lambda L_{\max}) } \enspace. \label{eq:SPSL1convsmooth}
\end{align}
Furthermore, if there exists a solution $w^\star$ to the interpolation equations~\eqref{eq:interpolate} and $\lambda = 1/2L_{\max}$ we have that
\begin{align} \label{eq:SPSL1convsmoothLmax}
 \E{ \ell (\bar{w}^T)}
   & \leq \frac{2L_{\max}}{T}\frac{\norm{w^{0} -w^\star}^2  + (s^{0} -s^{\star})^2}{\gamma(1-\gamma )} \enspace. \quad
\end{align}
\end{theorem}
This convergence in~\eqref{eq:SPSL1convsmooth} gives a rate of ${\cal O}(\frac{1}{T} + \mbox{constant})$, where this constant depends on $w^\star$ and the parameters. Under these same assumptions this is also the convergence rate of  \texttt{SPS}$_{\max}$ (Theorem 3.4~\cite{SPS}) and \texttt{SGD} (Theorem 4.1~\cite{SPS} and Corollary 4.4~\cite{KSLGR2020unifiedsgm}).
 What is different is this constant  term on the right hand side of~\eqref{eq:SPSL1convsmooth}. Though this term is different, under interpolation we have that this constant term is zero giving~\eqref{eq:SPSL1convsmoothLmax}, which excluding the factor of $\frac{1}{\gamma(1-\gamma)}$,  is identical to the convergence of both \texttt{SPS}$_{\max}$ (Theorem 3.4~\cite{SPS}) and \texttt{SGD} (Theorem 4.1~\cite{SPS} and Corollary 4.4~\cite{KSLGR2020unifiedsgm}).

Next we prove  convergence for nonsmooth functions.

\begin{theorem}\label{theo:SPSL1lip}
Let $w^* \in \mbox{argmin}_{w \in \R^d} \max_{i=1,\ldots, n} \ell_i(w)$ and $s^* = \ell_i(w^*) +  \lambda$.
Consider the $(w^t,s^t)$ iterates given by~\eqref{eq:SPSL1noposproj-main}.
Let $\bar{w}^T = \frac{1}{T} \sum_{t=0}^{T-1} w^t$ and let $\ell_i$ be non-negative.

      If  $\ell_i$ is $\sigma$--Lipschitz, convex  and $s^0 \geq -\lambda \sigma^2$, then
\begin{align}
    &\E{\frac{1 }{n} \sum_{i=1}^n \ell_i(\bar{w}^T) }
    \leq \frac{\norm{w^{0} -w^*}^2 +(s^0-s^*)^2 }{2\gamma (1-\gamma) \lambda T} + \frac{\lambda}{2} \frac{1  + \sigma^2 (1 + \gamma)}{ 1-\gamma }
    + \frac{\max_{i=1,\ldots, n} \ell_i(w^\star) }{1-\gamma} \; . \label{eq:SPSL1convLip}
\end{align}
\end{theorem}
In Theorem~\ref{theo:SPSL1lip} we can see that $\lambda$ trades off speed of convergence and the \emph{radius of convergence}.
In some ways, it plays the same role as constant step size for \texttt{SGD}.
On the one hand, when $\lambda$ goes to infinity \texttt{SPSL1} escapes faster from the initial conditions as the convergence rate is ruled by ${\cal O} (1/\lambda T)$.
On the other hand, when $\lambda$ goes to zero, the first term of~\eqref{eq:SPSL1convLip} goes to infinity, whereas the second term, the constant error one, goes to zero.
Furthermore, the radius of convergence also depends on the remaining term $\max_{i=1,\ldots, n} \ell_i(w^\star)$, which vanishes in the interpolated setting as it is close to zero or can be controlled for $\gamma$ small.

\section{Convergence of \texttt{SPSL2}}
\label{sec:sonv_spspl2_main}

To prove convergence of \texttt{SPSL2} we also introduce a relaxation parameter $\gamma \in [0, 1]$ and a relaxation step analogously to the relaxation we introduced in~\eqref{eq:SPSL1noposproj-main}. The details of this change can be found in Section~\ref{sec:spsl2_convergence_theory} and specifically formula~\eqref{eq:SPSL2SGD}.
With this one additional change, we can  prove the convergence of \texttt{SPSL2} in terms of the average of the square of the losses, as we show in the next theorem.

\begin{theorem}
\label{theo:SPSDAMfmax_main}
Fix $(w^\star,s^{\star}) \in \R^{d+1}$ and consider the $(w^t,s^t)$ iterates given by~\eqref{eq:SPSL2} with a relaxation parameter $\gamma \in (0,  1)$.
Let $\bar{w}^T = \tfrac{1}{T} \sum_{t=0}^{T-1} w^t$ and let $\ell_i$ be non-negative.

If $\ell_i$ is  $\sigma$--Lipschitz for every $i\in \{1,\ldots, n\}$ then
\begin{align*}
    \tfrac{1}{n} \sum_{i=1}^n\E{\ell_i(\bar{w}^T)^2}
    & \leq \frac{1}{C (\hat{\lambda})}\frac{\norm{w^{0} -w^\star}^2+(s^0 -s^{\star})^2}{\gamma(1-\gamma)  T} +  \frac{1}{C (\hat{\lambda})} \frac{1-\hat{\lambda}}{\hat{\lambda}^2 (1-\gamma)} \max_{i=1,\ldots, n} \ell_i(w^\star)^2 \enspace.

\end{align*}
\begin{equation}
    \label{eq:Capp_main}
    \mbox{where     }  \bar{w}^T = \sum_{t=0}^{T-1} w^k/T, \; \hat{\lambda} = 1/(1+\lambda)\mbox{   and   }
    C (\hat{\lambda}) \coloneqq \frac{1 - \hat{\lambda}}{\hat{\lambda}^2 + (1 - \hat{\lambda}) \left(\hat{\lambda} + L_{\max}^2 \right)} \enspace.
\end{equation}
\end{theorem}

This last result in Theorem~\eqref{theo:SPSDAMfmax_main} shows that \texttt{SPSL2} converges to a minimizer of $\tfrac{1}{n} \sum_{i=0}^n \ell_i(w)^2$ up to an additive constant error proportional to $\max_{i=1,\ldots, n} \ell_i(w^\star)^2.$
This is perhaps not so surprising given that \texttt{SPSL2} is indeed solving the max squared loss~\eqref{eq:slackobjL2}, which in turn is an over-approximation of the average squared loss.
As in Theorems~\ref{theo:SPSL1lip} and~\ref{theo:SPSL1smooth}, the slack parameter $\lambda$ (through $\hat{\lambda}$) trades off the speed of convergence and the constant error term. Furthermore, under interpolation we have again that the constant error term is zero.

In the appendix in Theorem~\ref{theo:SPSDAMregret} we also provide an extension of the regret analysis for \texttt{PA} methods, given in Theorem 5 in~\cite{Crammer06}, from hinge loss over linear models to a more general class of nonlinear convex models.

\section{Numerical Experiments}

We perform several numerical experiments for validating the usefulness of the proposed SPS variants on logistic regression and DNNs. Specifically, we compare: \texttt{ADAM} \cite{ADAM};
 \texttt{ALI-G}, i.e., update \eqref{eq:exact_ALIG};
\texttt{SPS}$_{\max}$, i.e., update \eqref{eq:SPSmaxproj};
\texttt{SPS}$_{dam}$ (proposed), i.e., update \eqref{eq:SPSdam};
\texttt{SPSL1} (proposed), i.e., update \eqref{eq:SPSL1};
\texttt{SPSL2} (proposed), i.e., update \eqref{eq:SPSL2}.
Apart from \texttt{ADAM}, all methods are SPS variants.

\begin{figure*}
\centering\includegraphics[width=\linewidth]{figures/fig1.pdf}
\centering\includegraphics[width=0.5\linewidth]{figures/fig2.pdf}
\includegraphics[width=0.23\linewidth]{colon-cancer-compare-0.01-loss-reg-1.00e-01}
 \includegraphics[width=0.23\linewidth]{mushrooms-compare-0.01-loss-reg-1.00e-01}
\caption{Comparison of the proposed and related methods on different computer vision problems in terms of both error in a validation set and loss in the train set. With the same set of parameters, the new slack variants are competitive throughout different datasets and models. In terms of validation error, \texttt{SPSL1} achieves the best result in the MNIST and arrives at a close second on the CIFAR-10.}
\label{figure:deep_results}
\end{figure*}

We compared the aforementioned methods on 4 different deep learning vision problems and one convex logistic regression problem.
The datasets for the vision problem we used are the MNIST dataset (60,000  $28\times28$ images, 10 classes) \cite{lecun2010mnist}, the CIFAR10, and \mbox{CIFAR-100} datasets (60,000 32$\times$32 color images in 10 and 100 classes respectively) \cite{krizhevsky2009learning}  We use 3 different models that are known to work well on these datasets: a multi-layer perceptron (MLP) with one hidden layer on the MNIST dataset, a ResNet18 \cite{he2016deep} on CIFAR-10, and a ResNet34 on the CIFAR-100 dataset.
For our logistic regression problem we used the  colon-cancer (    $d =2001$ and  $n =62$)~\cite{uci} data set.

Because of the importance of momentum in speeding up \texttt{ALI-G} and \texttt{SPS}$_{\max}$ for DNNs~\cite{ALI-G-vs-SPS},  we also use momentum in our implementations of \texttt{SPSL1} and \texttt{SPSL2}.
Formally, we replace $w_{t+1} = w_t - u_t$, where $u_t$ corresponds to the method-specific update, by
$v_{t+1} = \beta v_t - u_t$ and
$w_{t+1} = w_t + v_{t+1}$.
We fix the momentum parameter to $\beta =0.5$ in the following experiments.

All methods were implemented in PyTorch. For the \texttt{SPS}$_{\max}$ method, we used the authors' implementation,\footnote{https://github.com/IssamLaradji/sps} which derives from the analyzed method in that it uses a ``step size smoothing'' technique that prevents the step size from increasing too rapidly. The Adam method uses the default PyTorch parameters (lr=0.001, betas=(0.9, 0.999)).
All methods use batch-size of 128 and relaxation parameter $\gamma = 2$. We report the validation error and train loss averaged over 3 runs.

Our results, shown in Figure \ref{figure:deep_results}, confirm that both $\texttt{SPSL1}$ and $\texttt{SPSL2}$ are highly competitive. In terms of validation error, \texttt{SPSL1} achieves the best result in the MNIST dataset (0.0159 vs 0.0165 for the second-best, \texttt{ALI-G}), arrives second on the CIFAR-10 dataset (0.075 vs 0.070 for \texttt{ALI-G}), and third on the CIFAR-100 (0.31 vs 0.27 for \texttt{SPS}$_{\max}$).

\section{Conclusion}

We studied in this paper SPS (SGD with Polyak step size), a family of stochastic algorithms with step size adaptive to the gradient norm and loss value at the sampled points.
Our first contribution was a novel connection with Passive-Aggressive methods, leading to a variational perspective of not only vanilla \texttt{SPS} but also recently-proposed variants \texttt{SPS}$_{\max}$ and \texttt{ALI-G}. Based on this viewpoint, our second contribution was two new SPS variants, \texttt{SPSL1} and \texttt{SPSL2}, that regularize the slack variable, for which we provide a convergence-rate analysis.
Experiments confirmed that \texttt{SPSL1} and \texttt{SPSL2}, are competitive, both on logistic regression and DNN tasks.

\bibliographystyle{abbrv}