#  AN-SPS: Adaptive Sample Size Nonmonotone Line Search Spectral Projected
Subgradient Method for Convex Constrained Optimization Problems

Nataša Krklec Jerinkić111Department of Mathematics and Informatics, Faculty of
Sciences, University of Novi Sad, Trg Dositeja Obradovića 4, 21000 Novi Sad,
Serbia. e-mail<EMAIL_ADDRESS>Tijana Ostojić 222Department of
Fundamental Sciences, Faculty of Technical Sciences, University of Novi Sad,
Trg Dositeja Obradovića 6, 21000 Novi Sad, Serbia. e-mail:
<EMAIL_ADDRESS>333Corresponding author

(October 10, 2023)

###### Abstract

We consider convex optimization problems with a possibly nonsmooth objective
function in the form of a mathematical expectation. The proposed framework
(AN-SPS) employs Sample Average Approximations (SAA) to approximate the
objective function, which is either unavailable or too costly to compute. The
sample size is chosen in an adaptive manner, which eventually pushes the SAA
error to zero almost surely (a.s.). The search direction is based on a scaled
subgradient and a spectral coefficient, both related to the SAA function. The
step size is obtained via a nonmonotone line search over a predefined
interval, which yields a theoretically sound and practically efficient
algorithm. The method retains feasibility by projecting the resulting points
onto a feasible set. The a.s. convergence of AN-SPS method is proved without
the assumption of a bounded feasible set or bounded iterates. Preliminary
numerical results on Hinge loss problems reveal the advantages of the proposed
adaptive scheme. In addition, a study of different nonmonotone line search
strategies in combination with different spectral coefficients within AN-SPS
framework is also conducted, yielding some hints for future work.

Key words: Nonsmooth Optimization, Spectral Projected Gradient, Sample Average
Approximation, Adaptive Variable Sample Size Strategies, Nonmonotone Line
Search.

##  1 Introduction

The problem. We consider convex constrained optimization problem with the
objective function in the form of mathematical expectation, i.e.,

$\min_{x\in\Omega}f(x)=E(\tilde{f}(x,\xi)),$ (1.1)

where $\Omega\subset\mathbb{R}^{n}$ is a convex set,
$\tilde{f}:\mathbb{R}^{n}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ is
continuous and convex function with respect to $x$,
$\xi:\mathcal{A}\rightarrow\mathbb{R}^{d}$ is random vector on a probability
space $(\mathcal{A},\mathcal{F},P)$ and $f$ is continuous and bounded from
below on $\Omega$. We assume that it is possible to find an exact projection
onto the feasible set, so a typical representative of $\Omega$ is
$n$-dimensional ball, nonnegativity constraints, or generic box constraints.
We do not impose smoothness of $\tilde{f}$, so we are dealing with
nondifferentiable functions $\tilde{f}$ in general. This framework covers many
important optimization problems, [9, 34, 35, 43], such as Hinge loss within a
machine learning framework. Moreover, it is known that general constrained
optimization problems may be solved through penalty methods, where the
relevant subproblems are often transformed into nonnegativity-constrained
problems by introducing slack variables or semi-smooth unconstrained problems.
Both cases fall into the framework that we consider, provided that the
objective function is convex.

Variable sample size schemes. The objective function in (1.1) is usually
unavailable or too costly to be evaluated directly [40]. For instance, there
are many applications where the analytical form of the mathematical
expectation cannot be attained. Moreover, there are also online training
problems (e.g., optimization problems that come from time series analysis)
where the sample size grows as time goes by. However, even if the sample size
is finite and we are dealing with a finite sum problem, working with the full
sample throughout the whole optimization process is usually too costly or,
moreover, unnecessarily. This is the reason why Variable Sample Size (VSS)
schemes have been developed over the past few decades overlapping with the Big
Data era [2, 3, 14, 16, 24, 28, 30, 31], to name just a few. The idea is to
work with Sample Average Approximation (SAA) functions

$f_{\mathcal{N}}(x)=\frac{1}{N}\sum_{i\in\mathcal{N}}f_{i}(x),$ (1.2)

where $f_{i}(x)=\tilde{f}(x,\xi_{i})$ and $\xi_{i},i=1,2,...$ are usually
assumed to be independent and identically distributed (i.i.d.) [40].
$N=|\mathcal{N}|$ determines the size of a sample used for the approximation
and it is varied across the iterations, allowing cheaper approximations
whenever possible.

Nonmonotone line search. Line search methods are known as a powerful tool in
classical optimization, especially in smooth deterministic case. They provide
global convergence with a good practical performance. However, in a stochastic
nonsmooth framework, it is very hard to analyze them. In the stochastic case,
line search yields biased estimators of the function values in subsequent
iteration points, which complicates classical analysis and seeks alternative
approaches [10, 17, 23, 29, 37]. In the nonsmooth framework, even if strong
convexity holds, the lower bounding of the step size is very hard. In [23],
the steps are bounded from below, but not uniformly since they depend on the
tolerance parameter, which tends to zero if convergence towards the optimal
point is aimed instead of a nearly-optimal point. On the other hand, a
predefined step size sequence such as the harmonic one is enough to guarantee
the (a.s.) convergence under the standard assumptions [6, 22], even in the
mini-batch or SA (Stochastic Approximation) framework [39, 42]. Unfortunately,
this choice usually yields very slow convergence in practice [6]. SPS
(Spectral Projected Subgradient) framework [27] proposes a combination of line
search and predefined sequence by performing the line search on predefined
intervals, keeping the method both fast and theoretically sound.

Classical Armijo line search needs descent direction in order to be well
defined. While in smooth optimization it is easy to determine it, in the
nonsmooth case it is a much more challenging task [23, 44]. Moreover, allowing
more freedom for the step size selection may be beneficial, especially when
the search directions are of spectral type [5, 27, 33]. Finally, having in
mind that VSS schemes work with approximate functions, nonmonotone line search
seems like a reasonable choice in this setup.

Spectral coefficients. Although the considered problem (1.1) is not smooth,
including some second-order information seems to be beneficial according to
the existing results [26, 32, 44]. Moreover, spectral-like methods proved to
be efficient in the stochastic framework with increasing accuracy [4, 25]. We
present a framework that allows different spectral coefficients to be combined
with subgradient directions. Following [11], we test different choices of
Barzilai-Borwein (BB) rules in a stochastic environment.

One of the key points lies in an adaptive sample size strategy. Roughly
speaking, the main idea is to balance two types of errors - the one that
measures how far is the iterate from the current SAA function’s constrained
optimum, and the one that estimates the SAA error. More precisely, we present
an adaptive strategy that determines when to switch to the next level of
accuracy and prove that this pushes the sample size to infinity (or to the
full sample size in a finite sum case). In the SPS framework, the convergence
result was proved under the assumption of the sample size increase at each
iteration, while for AN-SPS the increase is a consequence of the algorithm’s
construction rather than the assumption.

We believe that one more important advantage with respect to SPS is a proposed
scaling of the subgradient direction. The scaling strategy is not new in
general [8], but it is a novelty with respect to the SPS framework. One of the
most important consequences of this modification is that the convergence
result is proved without boundedness assumptions - we do not impose any
assumption of uniformly bounded subgradients, feasible set, nor iterates.
Instead, we prove that AN-SPS provides the bounded sequence of iterates under
a mild sample size growth condition.

The main result - almost sure convergence of the whole sequence of iterates -
is proved under rather standard conditions for stochastic analysis. Moreover,
in the finite sum problem case, the convergence is deterministic, and it is
proved under a significantly reduced set of assumptions with respect to the
general case (1.1). Furthermore, we proved that the worst-case complexity can
achieve the order of $\varepsilon^{-1}$. Although the worst-case complexity
result stated in Theorem 3.5 is comparable to the complexity of standard
subgradient methods with a predefined step size sequence and its stochastic
variant (both of order $\varepsilon^{-2}$, see [7, 36] for instance), we
believe that the advantage of the proposed method lies in its ability to
accept larger steps and employ spectral coefficients combined with a
nonmonotone line search, which can significantly speed up the method.
Furthermore, the proposed method provides a wide framework for improving
computational cost complexity since it allows different sampling strategies to
be employed. Preliminary numerical tests on Hinge loss problems and common
data sets for machine learning show the advantages of the proposed adaptive
VSS strategy. We also present the results of a study that investigates how
different spectral coefficients combine with different nonmonotone rules.

Contributions. This paper may be seen as a continuation of the work presented
in [27] and further development of the algorithm LS-SPS (Line Search Spectral
Projected Subgradient Method for Nonsmooth Optimization) proposed therein. In
this light, the main contributions of this work are the following:

  * i)

An adaptive sample size strategy is proposed and we prove that this strategy
pushes the sample size to infinity (or to the maximal sample size in the
finite sum case);

  * ii)

We show that the scaling can relax the boundedness assumptions on
subgradients, iterates, and feasible set;

  * iii)

For finite sum problems, we provide the worst-case complexity analysis of the
proposed method;

  * iv)

The LS-SPS is generalized in the sense that we allow different nonmonotone
line search rules. Although important for the practical behavior of the
algorithm, this change does not affect the convergence analysis and it is
investigated mainly through numerical experiments;

  * v)

Considering the spectral coefficients, we investigate different strategies for
its formulation [11] in a stochastic framework. Different combinations of
spectral coefficients and nonmonotone rules are evaluated within numerical
experiments conducted on machine learning Hinge loss problems.

Paper organization. The algorithm is presented in Section 2. Convergence
analysis is conducted in Section 3, while preliminary numerical results are
reported in Section 4. Section 5 is devoted to the conclusions and some proofs
are delegated to the Appendix (Section 6).

Notation. The notation we use is the following. Vector $x\in\mathbb{R}^{n}$ is
considered as a column vector. $||\cdot||$ represents the Euclidean norm.
$x_{k}$ represents an iterate, i.e., an approximation of a solution of problem
(1.1) at iteration $k$. The sample used to approximate the objective function
via (1.2) at iteration $k$ is denoted by $\mathcal{N}_{k}$, while $N_{k}$
denotes its cardinality. The exact orthogonal projection of
$x\in\mathbb{R}^{n}$ onto $\Omega$ will be denoted as $P_{\Omega}(x)$. $X^{*}$
and $f^{*}$ denote a set of solutions and an optimal value of problem (1.1),
respectively. We denote a solution of the problem (1.1) by $x^{*}$.
Analogously, we denote by $x_{\cal{N}}^{*}$, $X_{\cal{N}}^{*}$ and
$f_{\cal{N}}^{*}$ a solution, set of all solutions and an optimal value of an
approximate problem $\min_{x\in\Omega}f_{\cal{N}}(x)$, respectively. Relevant
constants are denoted by capital $C$ (e.g., $C_{1}$), underlined letter (e.g.,
$\underline{\zeta}$) or overlined letter (e.g., $\bar{c}_{1}$). We denote by
$\bar{e}_{k}=|f_{\mathcal{N}_{k}}(x_{k})-f(x_{k})|+|f_{\mathcal{N}_{k}}(x^{*})-f(x^{*})|$
the relevant SAA errors at iteration $k$.

##  2 The Method

In this section, we state the proposed AN-SPS framework algorithm. In order to
define the rule for updating the sample size $N_{k}=|{\cal{N}}_{k}|$, we
introduce the SAA error measure $h(N_{k})$, i.e., a proxy for
$|f(x)-f_{\mathcal{N}_{k}}(x)|$, as follows. In the finite sum case with the
full sample size $N_{max}<\infty$ we define

$h(N_{k})=\frac{N_{max}-N_{k}}{N_{max}},$

while in general (unbounded sample size) case we define

$h(N_{k})=\frac{1}{N_{k}}.$

Notice that in both cases we have $h:\mathbb{N}\to[0,1]$ which is
monotonically decreasing and strictly positive if the full sample is not
attained. Moreover, in the finite sum case we have $h(N_{k})=0$ if and only if
$N_{k}=N_{max}$, while in unbounded sample case we have
$\lim_{N_{k}\rightarrow\infty}h(N_{k})=0.$ Other choices are eligible as well,
but we keep these ones for simplicity.

Let us define the upper bound of the predefined interval for the line search
by

$\bar{\alpha}_{k}=\min\\{1,C_{2}/k\\},$

where $C_{2}>0$ can be arbitrarily large.

Algorithm 1: AN-SPS (Adaptive Sample Size Nonmonotone Line Search Spectral
Projected Subgradient Method)

  * S0

Initialization. Given $N_{0},m\in\mathbb{N},$ $x_{0}\in\Omega,$ $C_{2}>0,$
$0<\underline{\zeta}\leq\overline{\zeta}<\infty,$
$\zeta_{0}\in\left[\underline{\zeta},\overline{\zeta}\right].$ Set $k=0$ and
$F_{0}=f_{\mathcal{N}_{0}}(x_{0})$.

  * S1

Search direction. Choose $\bar{g}_{k}\in\partial f_{\mathcal{N}_{k}}(x_{k})$.
Set $q_{k}=\max\\{1,\|\bar{g}_{k}\|\\}$, $v_{k}=\bar{g}_{k}/q_{k}$ and
$p_{k}=-\zeta_{k}v_{k}$.

  * S2

Step size.

If $k=0$, set $\alpha_{0}=1$.
Else, choose $m$ points
$\\{\tilde{\alpha}_{k}^{1},...,\tilde{\alpha}_{k}^{m}\\}$ such that

$\frac{1}{k}<\tilde{\alpha}_{k}^{1}<\tilde{\alpha}_{k}^{2}<\ldots<\tilde{\alpha}_{k}^{m}=\bar{\alpha}_{k}.$

    * If the condition

$f_{\mathcal{N}_{k}}(x_{k}+\tilde{\alpha}_{k}^{j}p_{k})\leq
F_{k}-\eta\tilde{\alpha}_{k}^{j}||p_{k}||^{2}$ (2.1)

is satisfied for some $j\in\\{m,m-1,\ldots,1\\}$, set
$\alpha_{k}=\tilde{\alpha}_{k}^{j}$ with the largest possible $j$.
Else, set $\alpha_{k}=\frac{1}{k}.$

  * S3

Main update. Set $z_{k+1}=x_{k}+\alpha_{k}p_{k}$,
$x_{k+1}=P_{\Omega}(z_{k+1})$, $s_{k}=x_{k+1}-x_{k}$ and
$\theta_{k}=\|s_{k}\|.$

  * S4

Spectral coefficient update. Choose
$\zeta_{k+1}\in[\underline{\zeta},\bar{\zeta}].$

  * S5

Sample size update. If $\theta_{k}<h(N_{k})$, choose $N_{k+1}>N_{k}$ and a new
sample $\mathcal{N}_{k+1}$. Else, $\mathcal{N}_{k+1}=\mathcal{N}_{k}$.

  * S6

Nonmonotone line search update. Determine $F_{k+1}$ such that

$f_{\mathcal{N}_{k+1}}(x_{k+1})\leq F_{k+1}<\infty.$

  * S7

Iteration update. Set $k:=k+1$ and go to S1.

First, notice that the initialization and Step S3 ensure the feasibility of
the iterates. In Step S1, we choose an arbitrary subgradient of the current
approximation function $f_{\mathcal{N}_{k}}$ at point $x_{k}$. Further,
scaling with $q_{k}$ implies that $\|v_{k}\|\leq 1$. Moreover, the boundedness
of the spectral coefficient $\zeta_{k}$ yields uniformly bounded search
directions $p_{k}$. This is very important from the theoretical point of view
since it helps us to overcome the boundedness assumptions mentioned in the
Introduction.

For the step size selection, we practically use a backtracking-type procedure
over the predefined interval $(\frac{1}{k},\bar{\alpha}_{k}]$. Notice that
$C_{2}$ can be arbitrarily large so that in practice $\bar{\alpha}_{k}$ is
equal to 1 in most of the iterations. However, the upper bound $C_{2}/k$ is
needed to ensure theoretical convergence results. The lower bound, $1/k$, is
known as a good choice from the theoretical point of view, and often a bad
choice in practice. Thus, roughly speaking, the line search checks if larger,
but still theoretically sound steps are eligible. Since the Armijo-like
condition (2.1) is checked in at most $m$ points, the procedure is well
defined since if none of these candidate points satisfies condition (2.1), the
step size is set to $1/k$. This allows us to use nondescent directions and
practically arbitrary nonmonotone (or monotone) rule determined by the choice
of $F_{k}$. For instance, $F_{k}$ can be set to
$f_{{\cal{N}}_{k}}(x_{k})+0.5^{k}$, but various other choices are possible as
well. The choice of nonmonotone rule does not affect the theoretical
convergence of the algorithm, but it can be very important in practice as we
will show in the Numerical results section. Parameter $m$ influences the per-
iteration cost of the algorithm since it upper bounds the number of the
function $f_{{\cal{N}}_{k}}$ evaluations within one line search procedure,
i.e., within one iteration. Having in mind that the function
$f_{{\cal{N}}_{k}}$ is just an estimate of the objective function in general,
we suggest that $m$ should be relatively small in order to avoid an
unnecessarily precise line search and high computational costs. On the other
hand, having $m$ too small may yield smaller step sizes since $1/k$ is more
likely to be accepted in general. Numerical results presented in Section 4 are
obtained by taking $m=2$ in all conducted experiments. However, tuning this
parameter or even making it adaptive may be an interesting topic to
investigate.

We will test the performance of some choices for the spectral coefficients,
where, from a theoretical point of view, the only requirement is the safeguard
stated in Step S4 of the algorithm - $\zeta_{k}$ must remain within a
positive, bounded interval $[\underline{\zeta},\bar{\zeta}]$.

Finally, the adaptive sample size strategy is determined within Step S5. The
overall step length $\theta_{k}$ may be considered as a measure of
stationarity related to the current objective function approximation
$f_{\mathcal{N}_{k}}$. In particular, we will show that, if the sample size is
fixed, $\theta_{k}$ tends to zero and the sequence of iterates is approaching
a minimizer of the current SAA function (see the proof of Theorem 3.1 in the
sequel). When $\theta_{k}$ is relatively small (smaller than the measure of
SAA error $h(N_{k})$), we decide that the two errors are in balance and that
we should improve the level of accuracy by enlarging the sample. Notice that
Step S5 allows a completely different sample $\mathcal{N}_{k+1}$ in general
with respect to $\mathcal{N}_{k}$ in the case when the sample size is
increased. However, if the sample size is unchanged, the sample is unchanged,
i.e., $\mathcal{N}_{k+1}=\mathcal{N}_{k}$, which allows non-cumulative samples
to fit within the proposed framework as well.

AN-SPS algorithm detects the iteration within which the sample size needs to
be increased, but it allows full freedom in the choice of the subsequent
sample size as long as it is larger than the current one. After some
preliminary tests, we end up with the following selection: when the sample
size is increased, it is done as

$N_{k+1}=\lceil\max\\{(1+\theta_{k})N_{k},rN_{k}\\}\rceil,$ (2.2)

with $r=1.1$. Although some other choices such as direct balancing of
$\theta_{k}$ and $h(N_{k+1})$ seemed more intuitive, they were all
outperformed by the choice (2.2). Disregarding the safeguard part where, in
case of $\theta_{k}=0$, the sample size is increased by 10$\%$, the relation
becomes

$1+\frac{N_{k+1}-N_{k}}{N_{k}}\approx 1+\theta_{k}.$

Thus, the relative increase in the sample size is balanced with the
stationarity measure. Furthermore, since we know that in these iterations
$\theta_{k}<h(N_{k})$, we obtain the relative increase bounded above by
$h(N_{k})$. Apparently, this helps the algorithm to overcome the problems
caused by the non-beneficiary fast growth of the sample size.

##  3 Convergence analysis

This section is devoted to the convergence analysis of the proposed method.
One of the main results lies in Theorem 3.1 where we prove that $h(N_{k})$
tends to zero. This means that the sample size tends to infinity in the
unbounded sample case, while in the finite sum case, it means that the full
sample is eventually reached. After that, we show that we can relax the common
assumption of uniformly bounded subgradients stated in the convergence
analysis in [27]. Normalized subgradients have been used in the literature,
but they represent a novelty with respect to the SPS framework. Hence, we need
to show that this kind of scaling does not deteriorate the relevant
convergence results. We state the boundedness of iterates within Proposition
3.2. Although the convergence result stated in Theorem 3.3 mainly follows from
the analysis of SPS [27] (see Theorem 3.1 therein), we provide the proof in
the Appendix (Section 6) since it is based on different foundations.
Therefore, we show that AN-SPS retains almost sure convergence under relaxed
assumptions with respect to LS-SPS proposed in [27], while, on the other hand,
it brings more freedom to the choice of nonmonotone line search and the
spectral coefficient. Finally, we formalize the conditions needed for the
convergence in the finite sum case within Theorem 3.4 and provide the worst-
case complexity analysis. We start the analysis by stating the conditions on
the function under the expectation in problem (1.1).

######  Assumption A 1.

Function $\tilde{f}(\cdot,\xi)$ is continuous and convex on $\Omega$ for any
given $\xi$ and there exists a solution $x_{\cal{N}}^{*}$ of problem
$\min_{x\in\Omega}f_{\cal{N}}(x)$ for any given ${\cal{N}}$.

The previous assumption implies that all the sample functions
$f_{\mathcal{N}_{k}}$ are also convex and continuous on $\Omega$. Moreover,
notice that the existence of a solution $x_{\cal{N}}^{*}$ of problem
$\min_{x\in\Omega}f_{\cal{N}}(x)$ is guaranteed if the feasible set $\Omega$
is compact or if the objective function is convex and coercive. We state the
first main result below.

######  Theorem 3.1.

Suppose that Assumption A1 holds and that $\Omega$ is closed and convex. Then
the sequence $\\{N_{k}\\}_{k\in\mathbb{N}}$ generated by AN-SPS satisfies

$\lim_{k\to\infty}h(N_{k})=0.$ (3.1)

###### Proof.

First, we show that retaining the same sample pushes $\theta_{k}$ to
zero444This part of the proof uses the elements of the analysis in [27], but
it also brings new steps and thus we provide it in a complete form.. Assume
that $N_{k}=N$ for all $k\geq\tilde{k}$ and some
$N<\infty,\;\tilde{k}\in\mathbb{N}$. According to Step S5 of AN-SPS algorithm,
this means that $\mathcal{N}_{k}=\mathcal{N}_{\tilde{k}}=:\mathcal{N}$ for all
$k\geq\tilde{k}$. Let us show that this implies boundedness of
$\\{x_{k}\\}_{k\in\mathbb{N}}$. Notice that for all $k$ the step size and the
search direction are bounded, more precisely,
$\alpha_{k}\leq\bar{\alpha}_{k}\leq 1$ and

$\|p_{k}\|=\|\zeta_{k}v_{k}\|\leq\bar{\zeta}\|v_{k}\|\leq\bar{\zeta}.$

Thus, the $\tilde{k}$ initial iterates must be bounded, i.e., there must exist
$C_{\tilde{k}}$ such that $\|x_{k}\|\leq C_{\tilde{k}}$ for all
$k=0,1,...,\tilde{k}.$ Now, let us observe the remaining sequence of iterates,
i.e., $\\{x_{\tilde{k}+j}\\}_{j\in\mathbb{N}}$. Let $x_{\mathcal{N}}^{*}$ be
an arbitrary solution of the problem $\min_{x\in\Omega}f_{\mathcal{N}}(x)$.
Notice that the convexity of $f_{\mathcal{N}}$ and the fact that
$\bar{g}_{k}\in\partial f_{\mathcal{N}}(x_{k})$ for all $k\geq\tilde{k}$ imply
that

$-\overline{g}^{T}_{k}\left(x_{k}-x\right)\leq
f_{\mathcal{N}}(x)-f_{\mathcal{N}}(x_{k})$

for all $k\geq\tilde{k}$ and all $x\in\mathbb{R}^{n}$. Then, by using
nonexpansivity of the projection operator and the fact that
$x_{\mathcal{N}}^{*}\in\Omega$, for all $k\geq\tilde{k}$ we obtain

$\displaystyle||x_{k+1}-x_{\mathcal{N}}^{*}||^{2}$ $\displaystyle=$
$\displaystyle||P_{\Omega}(z_{k+1})-P_{\Omega}(x_{\mathcal{N}}^{*})||^{2}$
(3.2) $\displaystyle\leq$
$\displaystyle||z_{k+1}-x_{\mathcal{N}}^{*}||^{2}=||x_{k}-\alpha_{k}\zeta_{k}v_{k}-x_{\mathcal{N}}^{*}||^{2}$
$\displaystyle=$
$\displaystyle||x_{k}-x_{\mathcal{N}}^{*}||^{2}-2\alpha_{k}\zeta_{k}\frac{1}{q_{k}}\overline{g}^{T}_{k}\left(x_{k}-x_{\mathcal{N}}^{*}\right)+\alpha_{k}^{2}\zeta^{2}_{k}||v_{k}||^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-x_{\mathcal{N}}^{*}||^{2}+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f_{\mathcal{N}_{k}}(x_{\mathcal{N}}^{*})-f_{\mathcal{N}_{k}}(x_{k}))+\alpha_{k}^{2}\bar{\zeta}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-x_{\mathcal{N}}^{*}||^{2}+\alpha_{k}^{2}\bar{\zeta}^{2}.$

In the last inequality, we use the fact that $\mathcal{N}_{k}=\mathcal{N}$ for
all $k\geq\tilde{k}$. Thus,

$f_{\mathcal{N}_{k}}(x_{\mathcal{N}}^{*})-f_{\mathcal{N}_{k}}(x_{k})=f_{\mathcal{N}}(x_{\mathcal{N}}^{*})-f_{\mathcal{N}}(x_{k})\leq
0$

and since $\alpha_{k}\zeta_{k}/q_{k}>0$ we obtain the result. Furthermore, by
using the induction argument, we obtain that for every $p\in\mathbb{N}$ there
holds

$\displaystyle||x_{\tilde{k}+p}-x_{\mathcal{N}}^{*}||^{2}$ $\displaystyle\leq$
$\displaystyle||x_{\tilde{k}}-x_{\mathcal{N}}^{*}||^{2}+\bar{\zeta}^{2}\sum_{j=0}^{p-1}\alpha_{\tilde{k}+j}^{2}\leq||x_{\tilde{k}}-x_{\mathcal{N}}^{*}||^{2}+\bar{\zeta}^{2}\sum_{j=0}^{\infty}\alpha_{j}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{\tilde{k}}-x_{\mathcal{N}}^{*}||^{2}+\bar{\zeta}^{2}C_{2}^{2}\sum_{j=0}^{\infty}\frac{1}{k^{2}}=:\bar{C}_{\tilde{k}}<\infty.$

Thus, we conclude that the sequence of iterates must be bounded, i.e., there
exists a compact set $\bar{\Omega}\subseteq\Omega$ such that
$\\{x_{k}\\}_{k\in\mathbb{N}}\subseteq\bar{\Omega}$. Since the function
$f_{\mathcal{N}}$ is convex due to Assumption A1, it follows that
$f_{\mathcal{N}}$ is locally Lipschitz continuous. Moreover, it is (globally)
Lipschitz continuous on the compact set $\bar{\Omega}$. Let us denote the
corresponding Lipschitz constant by $L_{\bar{\Omega}}$. Then, we know that
$\|g\|\leq L_{\bar{\Omega}}$ holds for any $g\in\partial f_{\mathcal{N}}(x)$
and any $x\in\bar{\Omega}$ (see for example [38] or [41]). Having in mind that
$\bar{g}_{k}\in\partial f_{\mathcal{N}}(x_{k})$ for all $k\geq\tilde{k}$, we
conclude that $\|\bar{g}_{k}\|\leq L_{\bar{\Omega}}$ for all $k\geq\tilde{k}$.

Now, we prove that

$\liminf_{k\to\infty}f_{\mathcal{N}}(x_{k})=f^{*}_{\mathcal{N}},$ (3.3)

where $f^{*}_{\mathcal{N}}=\min_{x\in\Omega}f_{\mathcal{N}}(x)$. Suppose the
contrary, i.e., there exists $\varepsilon_{\mathcal{N}}>0$ such that for all
$k\geq\tilde{k}$ there holds $f_{\mathcal{N}}(x_{k})-f^{*}_{\mathcal{N}}\geq
2\varepsilon_{\mathcal{N}}$. Recall that Assumption A1 implies that
$f^{*}_{\mathcal{N}}$ is finite and that $f_{\mathcal{N}}$ is continuous.
Therefore, there exists a sequence
$\\{y^{\mathcal{N}}_{j}\\}_{j\in\mathbb{N}}\in\Omega$ such that
$\lim_{j\to\infty}f_{\mathcal{N}}(y^{\mathcal{N}}_{j})=f^{*}_{\mathcal{N}}$.
Moreover, there exists a point $\tilde{y}_{\mathcal{N}}\in\Omega$ such that

$f_{\mathcal{N}}(\tilde{y}_{\mathcal{N}})<f^{*}_{\mathcal{N}}+\varepsilon_{\mathcal{N}}.$

Therefore, we conclude that for all $k\geq\tilde{k}$ there holds

$f_{\mathcal{N}}(x_{k})\geq
f^{*}_{\mathcal{N}}+2\varepsilon_{\mathcal{N}}=f^{*}_{\mathcal{N}}+\varepsilon_{\mathcal{N}}+\varepsilon_{\mathcal{N}}>f_{\mathcal{N}}(\tilde{y}_{\mathcal{N}})+\varepsilon_{\mathcal{N}},$

and thus for all $k\geq\tilde{k}$ we have

$-\overline{g}^{T}_{k}\left(x_{k}-\tilde{y}_{\mathcal{N}}\right)\leq
f_{\mathcal{N}}(\tilde{y}_{\mathcal{N}})-f_{\mathcal{N}}(x_{k})\leq-\varepsilon_{\mathcal{N}}.$

Following the same steps as in (3.2) and using the previous inequality, we
conclude that for all $k\geq\tilde{k}$ there holds

$\displaystyle||x_{k+1}-\tilde{y}_{\mathcal{N}}||^{2}$ $\displaystyle\leq$
$\displaystyle||z_{k+1}-\tilde{y}_{\mathcal{N}}||^{2}$ (3.4)
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}_{\mathcal{N}}||^{2}-2\alpha_{k}\zeta_{k}\frac{1}{q_{k}}\overline{g}^{T}_{k}\left(x_{k}-\tilde{y}_{\mathcal{N}}\right)+\alpha_{k}^{2}\zeta^{2}_{k}||v_{k}||^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}_{\mathcal{N}}||^{2}-2\alpha_{k}\frac{\zeta_{k}}{q_{k}}\varepsilon_{\mathcal{N}}+\alpha_{k}^{2}\bar{\zeta}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}_{\mathcal{N}}||^{2}-2\alpha_{k}\frac{1}{q_{k}}\underline{\zeta}\varepsilon_{\mathcal{N}}+\alpha_{k}^{2}\bar{\zeta}^{2}.$

Now, using the fact that

$q_{k}=\max\\{1,\|\bar{g}_{k}\|\\}\leq\max\\{1,L_{\bar{\Omega}}\\}:=q,$ (3.5)

we conclude that for all $k\geq\tilde{k}$ there holds

$||x_{k+1}-\tilde{y}_{\mathcal{N}}||^{2}\leq||x_{k}-\tilde{y}_{\mathcal{N}}||^{2}-2\alpha_{k}\frac{1}{q}\underline{\zeta}\varepsilon_{\mathcal{N}}+\alpha_{k}^{2}\bar{\zeta}^{2}=||x_{k}-\tilde{y}_{\mathcal{N}}||^{2}-\alpha_{k}(\frac{2}{q}\underline{\zeta}\varepsilon_{\mathcal{N}}-\alpha_{k}\bar{\zeta}^{2}).$

Since $\alpha_{k}\leq C_{2}/k$, there holds $\lim_{k\to\infty}\alpha_{k}=0$
and thus there must exist $\bar{k}\geq\tilde{k}$ such that
$\alpha_{k}\bar{\zeta}^{2}\leq\frac{1}{q}\underline{\zeta}\varepsilon_{\mathcal{N}}=:\underline{\varepsilon}_{\mathcal{N}}$.
Therefore, we have

$||x_{k+1}-\tilde{y}_{\mathcal{N}}||^{2}\leq||x_{k}-\tilde{y}_{\mathcal{N}}||^{2}-\alpha_{k}\underline{\varepsilon}_{\mathcal{N}}.$

Moreover, for any $p\in\mathbb{N}$ there holds

$||x_{\bar{k}+p}-\tilde{y}_{\mathcal{N}}||^{2}\leq||x_{\bar{k}}-\tilde{y}_{\mathcal{N}}||^{2}-\underline{\varepsilon}_{\mathcal{N}}\sum_{j=0}^{p-1}\alpha_{\bar{k}+j}$

and letting $p\to\infty$ we obtain the contradiction since
$\sum_{k=0}^{\infty}\alpha_{k}\geq\sum_{k=0}^{\infty}1/k=\infty.$ Thus, we
conclude that (3.3) must hold. Therefore there exists
$K_{1}\subseteq\mathbb{N}$ such that

$\lim_{k\in K_{1}}f_{\mathcal{N}}(x_{k})=f^{*}_{\mathcal{N}}$

and since the sequence of iterates is bounded, there exists $K_{2}\subseteq
K_{1}$ and a solution $\tilde{x}_{\mathcal{N}}^{*}$ of the problem
$\min_{x\in\Omega}f_{\mathcal{N}}(x)$ such that

$\lim_{k\in K_{2}}x_{k}=\tilde{x}_{\mathcal{N}}^{*}.$ (3.6)

Now, we show that the whole sequence of iterates converges. Let

$\\{{x_{k}\\}}_{k\in K_{2}}:=\\{{x_{k_{i}}\\}}_{i\in\mathbb{N}}.$ (3.7)

Following the steps of (3.2) we obtain that the following holds for any
$s\in\mathbb{N}$

$||x_{k_{i}+s}-\tilde{x}_{\mathcal{N}}^{*}||^{2}\leq||x_{k_{i}}-\tilde{x}_{\mathcal{N}}^{*}||^{2}+\bar{\zeta}^{2}\sum_{j=0}^{s-1}\alpha_{k_{i}+j}^{2}\leq||x_{k_{i}}-\tilde{x}_{\mathcal{N}}^{*}||^{2}+\bar{\zeta}^{2}\sum_{j=k_{i}}^{\infty}\alpha_{j}^{2}=:a_{i}.$

Thus, for any $s,m\in\mathbb{N}$ there holds

$||x_{k_{i}+s}-x_{k_{i}+m}||^{2}\leq
2||x_{k_{i}+s}-\tilde{x}_{\mathcal{N}}^{*}||^{2}+2||x_{k_{i}+m}-\tilde{x}_{\mathcal{N}}^{*}||^{2}\leq
4a_{i}.$

Since $\sum_{j=k_{i}}^{\infty}\alpha_{j}^{2}$ is a residual of convergent sum
and (3.6) holds, we have

$\lim_{i\to\infty}a_{i}=0.$

Therefore, for every $\varepsilon>0$ there exists $k_{i}\in\mathbb{N}$ such
that for all $t,l\geq k_{i}$ there holds $||x_{t}-x_{l}||\leq\varepsilon$,
i.e., the sequence $\\{x_{k}\\}_{k\in\mathbb{N}}$ is a Cauchy sequence and
thus convergent. This, together with (3.6), implies

$\lim_{k\to\infty}x_{k}=\tilde{x}_{\mathcal{N}}^{*},$

and Step S3 of AN-SPS algorithm implies

$\lim_{k\to\infty}\theta_{k}=\lim_{k\to\infty}\|s_{k}\|=\lim_{k\to\infty}\|x_{k+1}-x_{k}\|=0.$

This completes the first part of the proof, i.e., we have just proved that if
the sample is kept fixed, the sequence $\\{\theta_{k}\\}_{k\in\mathbb{N}}$
tends to zero.

Finally, we prove the main result (3.1). Assume the contrary. Since the
sequence $\\{h(N_{k})\\}_{k\in\mathbb{N}}$ is nonincreasing, this means that
we assume the existence of $\bar{h}>0$ such that $h(N_{k})\geq\bar{h}$ for all
$k\in\mathbb{N}$. This further implies that there exists $N<N_{\infty}$ and
$\bar{k}\in\mathbb{N}$ such that $N_{k}=N$ for all $k\geq\bar{k}$, where
$N_{\infty}=\infty$ in unbounded sample case and $N_{\infty}$ coincides with
the full sample size in the bounded sample (finite sum) case. Thus, according
to the Step S5 of AN-SPS algorithm, there holds that

$\theta_{k}\geq h(N_{k})=h(N)\geq\bar{h}>0$

for all $k\geq\bar{k}$, since we would have an increase of the sample size $N$
otherwise. On the other hand, we have just proved that if the sample size is
fixed, then

$\lim_{k\to\infty}\theta_{k}=0,$

which is in contradiction with $\theta_{k}\geq\bar{h}>0$. Thus, we conclude
that

$\lim_{k\to\infty}h(N_{k})=0,$

which completes the proof. ∎

Next, we analyze the conditions that provide a sequence of bounded iterates
generated by AN-SPS algorithm. Let us define the SAA error sequence as
follows, [27],

$\bar{e}_{k}=|f_{\mathcal{N}_{k}}(x_{k})-f(x_{k})|+|f_{\mathcal{N}_{k}}(x^{*})-f(x^{*})|,$
(3.8)

where $x^{*}$ is an arbitrary solution of (1.1). The proof of the following
proposition is similar to the proof of Proposition 3.4 of [27], but the
conditions are relaxed since we have $N_{k}\to\infty$ as a consequence of the
Theorem 3.1. Moreover, scaling of the subgradients relaxes the assumption of
uniformly bounded $\bar{g}_{k}$ sequence. Although the modifications are
mainly technical, we provide the proof in the Appendix (Section 6) for the
sake of completeness. Condition (3.9) in the sequel states the sample size
growth under which we achieve bounded iterates. For instance, in the
cumulative sample case, $N_{k}=k$ is sufficient to ensure this condition.
Although we believe that the condition is not too strong, it is still an
assumption and not the consequence of the algorithm, so this issue remains an
open question for future work.

######  Proposition 3.2.

Suppose that $\Omega$ is closed and convex, Assumption A1 holds and
$\\{x_{k}\\}_{k\in\mathbb{N}}$ is a sequence generated by Algorithm AN-SPS.
Then there exists a compact set $\bar{\Omega}\subseteq\Omega$ such that
$\\{x_{k}\\}\subseteq\bar{\Omega}$ provided that

$\sum_{k=0}^{\infty}\bar{e}_{k}/k\leq C_{4}<\infty,$ (3.9)

where $C_{4}$ is a positive constant.

As it can be seen from the proof, $\bar{\Omega}$ stated in the previous
proposition depends only on $x_{0}$ and given constants, so it can be
(theoretically) determined independently of the sample path. However, since we
consider unbounded samples in general, we need the following assumption.

######  Assumption A 2.

For every $x\in\Omega$ there exists a constant $L_{x}$ such that
$\tilde{f}(x,\xi)$ is locally $L_{x}$-Lipschitz continuous for any $\xi$.

This assumption implies that each SAA function is locally Lipschitz continuous
with a constant that depends only on a point $x$ and not on a random vector
$\xi$. In a bounded sample case this is obviously satisfied under assumption
A1, while in general, it holds for a certain class of functions - when $\xi$
is separable from $x$ for instance. Next, we prove the almost sure convergence
of AN-SPS algorithm under the stated assumptions. Notice that (3.9) does not
necessarily imply that $\lim_{k\to\infty}\bar{e}_{k}=0$. Thus, we add a common
assumption in stochastic analysis in order to ensure a.s. convergence of the
sequence $\\{\bar{e}_{k}\\}_{k\in\mathbb{N}}$.

######  Assumption A 3.

The function $\tilde{f}$ is dominated by a P-integrable function on any
compact subset of $\mathbb{R}^{n}$.

Under the stated assumptions, the Uniform Law of Large Numbers (ULLN) implies
(Theorem 7.48 in [40])

$\lim_{N\rightarrow\infty}\sup_{x\in S}|f_{N}(x)-f(x)|=0\quad\mbox{a.s.}$
(3.10)

for any compact subset $S\subseteq\mathbb{R}^{n}$. This will further imply the
a.s. convergence of the sequence $\\{\bar{e}_{k}\\}_{k\in\mathbb{N}}$. Notice
that $\lim_{k\to\infty}\bar{e}_{k}=0$ is satisfied in the bounded sample case,
as well as (3.9) since AN-SPS achieves the full sample eventually. In that
case, the assumptions A2 and A3 are not needed for the convergence result.

Remark: The following theorem states a.s. convergence of the proposed method.
Although it follows the same steps, the proof differs from the proof of
Theorem 3.1 of [27] in several places. Under the stated assumptions, we prove
that the sample size tends to infinity and that the iterates remain within a
compact set. After that, the proof follows the steps of the proof in [27]
completely, except for the scaling of the subgradient in Step S1 of AN-SPS
algorithm. This alters the inequalities, but the Assumption A2 implies that
$q_{k}$ can be uniformly bounded from above and below, thus the main flow
remains the same. We state the proof in the Appendix (Section 6) for
completeness.

######  Theorem 3.3.

Suppose that Assumptions A1-A3 and (3.9) hold and that $\Omega$ is closed and
convex. Then the sequence $\\{x_{k}\\}_{k\in\mathbb{N}}$ generated by AN-SPS
converges to a solution of problem (1.1) almost surely.

Finally, we state the results for the finite sum problem as an important class
of (1.1)

$\min_{x\in\Omega}\frac{1}{N}\sum_{i=1}^{N}f_{i}(x).$ (3.11)

As we mentioned before, Assumption A3 is redundant in this case as well as
(3.9) since $\bar{e}_{k}=0$ for all $k$ large enough. Moreover, Assumption A2
is also satisfied due to the fact that there are only finitely many functions
$f_{i}$. At the end, notice that under Assumption A1, the full sample is
eventually achieved and the proof of Theorem 3.1 also reveals that the
convergence is deterministic. We summarise this in the next theorem.

######  Theorem 3.4.

Suppose that Assumption A1 holds and that $\Omega$ is closed and convex. Then
the sequence $\\{x_{k}\\}_{k\in\mathbb{N}}$ generated by AN-SPS converges to a
solution of problem (3.11).

We also provide the worst-case complexity analysis for the relevant finite sum
problem (3.11).

######  Theorem 3.5.

Suppose that the assumptions of Theorem 3.4 hold and that the sample size
increases as in (2.2). Then, $\varepsilon$-vicinity of an optimal value
$f^{*}$ of problem (3.11) is reached after at most

$\hat{k}=2\bar{k}+\left(\frac{q(\bar{c}_{1}+||x_{\bar{k}}-x^{*}||^{2})}{\underline{\zeta}}\right)^{\frac{1}{1-\delta}}\varepsilon^{\frac{1}{\delta-1}}$

iterations, where

$\bar{k}:=(\lceil
C_{2}\bar{\zeta}N\rceil+1)\frac{\log(N/N_{0})}{\log(r)},\quad\bar{c}_{1}:=\sum_{k=0}^{\infty}\frac{C_{2}^{2}\bar{\zeta}^{2}}{k^{2}},$

provided that $\alpha_{k}\geq k^{-\delta},$ $\delta\in[0,1)$ for all
$k\in\\{\bar{k},\bar{k}+1,...,\hat{k}\\}$.

###### Proof.

Let us denote by $N^{1}<N^{2}<...<N^{d}$ all the sample sizes that are used
during the optimization process. Then, we have that $N^{1}=N_{0}$, where
$N_{0}$ is the initial sample size, and $N^{d}=N$ since we have proved that
the full sample is reached eventually. Furthermore, according to (2.2), we
know that $N^{d}\geq r^{d-1}N_{0}$ and thus we conclude that

$d-1\leq\frac{\log(N/N_{0})}{\log(r)}.$

Furthermore, notice that for any $k\in\mathbb{N}$ there holds

$\theta_{k}=\|x_{k+1}-x_{k}\|=\|P_{\Omega}(z_{k+1})-P_{\Omega}(x_{k})\|\leq\|z_{k+1}-x_{k}\|=\|\alpha_{k}p_{k}\|\leq\frac{C_{2}}{k}\bar{\zeta}.$

Suppose that we are at iteration $k$ with a sample size $N_{k}=N^{j}$, with
$j<d$. Then, according to Step S5 of Algorithm 1, the sample size $N^{j}$ is
changed after at most

$\lceil\frac{C_{2}\bar{\zeta}}{h(N^{j})}\rceil+1$

iterations. Moreover, since $N^{j}\leq N-1$ for all $j=1,...,d-1$, there must
hold that

$h(N^{j})\geq h(N-1)=\frac{N-(N-1)}{N}=\frac{1}{N}$

for all $j=1,...,d-1$ and thus the number of iterations with the same sample
size smaller than $N$ is uniformly bounded by $\lceil
C_{2}\bar{\zeta}N\rceil+1$. Thus, we conclude that after at most

$\bar{k}:=(\lceil C_{2}\bar{\zeta}N\rceil+1)\frac{\log(N/N_{0})}{\log(r)}$

iterations the full sample size is reached.

Now, let us observe the iterations $k\geq\bar{k}$ and denote the objective
function of problem (3.11) by $f$. Theorem 3.4 implies that
$\lim_{k\to\infty}f(x_{k})=f^{*}$ and thus there exists a finite iteration $k$
such that $f(x_{k})<f^{*}+\varepsilon.$ Let us denote by $\hat{j}$ the
smallest $j\in\mathbb{N}_{0}$ such that
$f(x_{\bar{k}+\hat{j}})<f(x^{*})+\varepsilon$, where $x^{*}$ is a solution of
problem (3.11). Using the same arguments as in (3.2), we obtain

$||x_{\bar{k}+\hat{j}}-x^{*}||^{2}\leq||x_{\bar{k}}-x^{*}||^{2}-\sum_{j=0}^{\hat{j}-1}2\alpha_{\bar{k}+j}\zeta_{\bar{k}+j}\frac{1}{q_{\bar{k}+j}}(f(x_{\bar{k}+j})-f(x^{*}))+\sum_{j=0}^{\hat{j}-1}\alpha^{2}_{\bar{k}+j}\zeta^{2}_{\bar{k}+j}.$
(3.12)

Notice that

$\sum_{j=0}^{\hat{j}-1}\alpha^{2}_{\bar{k}+j}\zeta^{2}_{\bar{k}+j}\leq\sum_{k=0}^{\infty}\frac{C_{2}^{2}\bar{\zeta}^{2}}{k^{2}}:=\bar{c}_{1}<\infty.$
(3.13)

Moreover, using (3.5), (3.13), $\zeta_{k}\geq\underline{\zeta}$ for all $k$,
and

$\alpha_{\bar{k}+j}\geq\frac{1}{(\bar{k}+j)^{\delta}}\geq\frac{1}{(\bar{k}+\hat{j})^{\delta}},\quad
f(x_{\bar{k}+j})-f(x^{*})\geq\varepsilon,\quad j=0,...,\hat{j}-1,$

from (3.12) we obtain

$0\leq||x_{\bar{k}}-x^{*}||^{2}-\frac{2\hat{j}\underline{\zeta}\varepsilon}{q(\bar{k}+\hat{j})^{\delta}}+\bar{c}_{1}.$

Finally, let us observe two cases: 1) $\hat{j}\leq\bar{k}$, and 2)
$\hat{j}>\bar{k}$. In the first case, the upper bound on $\hat{j}$ is obvious.
In the second case, we have

$0\leq||x_{\bar{k}}-x^{*}||^{2}-\frac{2\hat{j}\underline{\zeta}\varepsilon}{q\hat{j}^{\delta}2^{\delta}}+\bar{c}_{1}\leq||x_{\bar{k}}-x^{*}||^{2}-\frac{\hat{j}^{1-\delta}\underline{\zeta}\varepsilon}{q}+\bar{c}_{1},$

and thus

$\hat{j}\leq\left(\frac{q(\bar{c}_{1}+||x_{\bar{k}}-x^{*}||^{2})}{\underline{\zeta}}\right)^{\frac{1}{1-\delta}}\varepsilon^{\frac{1}{\delta-1}}=:\bar{c}_{2}.$

Combining both cases we conclude that

$\hat{j}\leq\max\\{\bar{c}_{2},\bar{k}\\}\leq\bar{c}_{2}+\bar{k}$

and thus $\hat{k}\leq\bar{k}+\bar{c}_{2}+\bar{k}=2\bar{k}+\bar{c}_{2},$ which
completes the proof. ∎

A few words are due to this result. The number of iterations $\hat{k}$ to
reach the $\varepsilon$-vicinity of the optimal value represents the worst-
case complexity and it is obtained by using very conservative bounds. In this
setup, the parameter $r$, which controls the increase of the sample size,
influences the number of iterations to reach the full sample size through
$\log(r)$. Higher $r$ yields smaller $\hat{k}$, but it also brings potentially
higher computational costs as larger samples are needed to compute the
approximate functions and the corresponding subgradients. Notice that the
proposed algorithm requires only one subgradient per iteration, while the
costs of evaluating the approximate objective function depend on the line
search. However, the per-iteration costs can be controlled by the parameter
$m$ which represents the maximal number of trial points at which the
approximate function is evaluated during the line search. In our experiments,
we set $m=2$, and we believe that this number should be modest to avoid
unnecessarily detailed line search. However, choosing an optimal value for
$m$, or even adaptive $m_{k}$, could be an interesting topic for some future
research since it influences the computational cost complexity.

The assumption $\alpha_{k}\geq k^{-\delta},\delta\in[0,1)$ for all
$k\in\\{\bar{k},\bar{k}+1,...,\hat{k}\\}$ actually indicates that the line
search condition (2.1) is satisfied in a finite number of iterations
$k\in\\{\bar{k},\bar{k}+1,...,\hat{k}\\}$. Since the step sizes are upper
bounded by $C_{2}/k$, this is possible only if we assume that $C_{2}$ is large
enough. Notice that the acceptance of a trial point can be controlled by
$F_{k}$. For instance, if $F_{k}$ is set to
$f_{{\cal{N}}_{k}}(x_{k})+C/2^{k}$, choosing large $C$ increases the chances
of successful line search and even of accepting the full step in finitely many
iterations. If this is the case, more precisely, if $\alpha_{k}\geq
k^{-\delta}$ with $\delta=0$ for all
$k\in\\{\bar{k},\bar{k}+1,...,\hat{k}\\}$, we achieve the complexity of order
$\varepsilon^{-1}$.

We end this section by noticing that the complexity result with respect to the
expected objective function’s value, as the one in Theorem 3.4 of [26], can be
achieved, but under additional sampling assumptions. Although this type of
result can be helpful, we believe that the advantage of the proposed AN-SPS
method lies in its ability to embed various sampling and nonmonotone line
search strategies, allowing the method to adapt to the problem at hand and
produce good practical behavior.

##  4 Numerical results

Within this section, we test the performance of AN-SPS algorithm on well-known
binary classification data sets listed in Table 1.

The problem that we consider is a constrained finite sum problem with
$L_{2}$-regularized hinge loss local cost functions, i.e.,

$\displaystyle\min_{x\in\Omega}f_{N}(x)$
$\displaystyle:=\delta||x||^{2}+\frac{1}{N}\sum_{i=1}^{N}\max\\{{0,1-z_{i}x^{T}w_{i}\\}},$
$\displaystyle\Omega$
$\displaystyle:=\\{{x\in\mathbb{R}^{n}\;:||x||^{2}\leq\frac{1}{\delta}\\}},$

where $\delta=10$ is the regularization parameter, $w_{i}\in\mathbb{R}^{n}$
are the attributes and $z_{i}\in\\{{1,-1\\}}$ are the corresponding labels.

| Data set | $N$ | $n$
---|---|---|---
1 | SPLICE [20] | 3175 | 60
2 | MUSHROOMS [21] | 8124 | 112
3 | ADULT9 [20] | 32561 | 123
4 | MNIST [18] | 70000 | 784
Table 1: Properties of the data sets used in the experiments.

AN-SPS algorithm is implemented with the following parameters:
$C_{2}=100,\eta=10^{-4},m=2,N_{0}=\lceil{0.1N\rceil}.$ The initial point
$x_{0}$ is chosen randomly from $\Omega$. We use the method proposed in [44,
Algorithm 2, p. 1155] with $B_{k}=I$ to find a descent direction
$-\overline{g}_{k}$ which is further scaled as in Step S1 of AN-SPS algorithm,
i.e., $p_{k}=-\zeta_{k}\overline{g}_{k}/q_{k}$. The sample size is updated
according to Step S5 of AN-SPS and (2.2). Recall that the sample size is
increased only if $\theta_{k}<h(N_{k})$.

We use cumulative samples, i.e., ${\cal{N}}_{k}\subseteq{\cal{N}}_{k+1}$ and
thus, following the conclusions in [4], we calculate the spectral coefficients
based on $s_{k}=x_{k+1}-x_{k}$ and the subgradient difference
$y_{k}=\tilde{g}_{k}-\bar{g_{k}}$, where $\tilde{g}_{k}\in\partial
f_{{\cal{N}}_{k}}(x_{k+1})$. This choice requires additional costs with
respect to the choice of $\tilde{g}_{k}=\bar{g}_{k+1}$, but it diminishes the
influence of the noise since the difference is calculated on the same
approximate function. Furthermore, we test four different choices for the
spectral coefficient (see [11] and the references therein for more details):

  * •

Barzilai-Borwein 1 (BB1) [1]:

$\lambda_{k}^{BB1}=\frac{s_{k}^{T}s_{k}}{s_{k}^{T}y_{k}};$

  * •

Barzilai-Borwein 2 (BB2) [1]:

$\lambda_{k}^{BB2}=\frac{y_{k}^{T}s_{k}}{y_{k}^{T}y_{k}};$

  * •

Adaptive Barzilai-Borwein (ABB) [46]:

$\lambda_{k}:=\left\\{\begin{array}[]{ll}\lambda_{k}^{BB2},&\frac{\lambda_{k}^{BB2}}{\lambda_{k}^{BB1}}<0.8,\\\
\lambda_{k}^{BB1},&\text{otherwise};\end{array}\right.$

  * •

Adaptive Barzilai-Borwein - minimum (ABBmin) [13]:

$\lambda_{k}:=\left\\{\begin{array}[]{ll}\min\\{{\lambda_{j}^{BB2}:j=\max\\{{1,k-m_{a}\\}},...,k\\}},&\frac{\lambda_{k}^{BB2}}{\lambda_{k}^{BB1}}<0.8,\\\
\lambda_{k}^{BB1},&\text{otherwise},\end{array}\right.$

where $m_{a}$ is a nonnegative integer set to 5 in our experiments.

For all the considered choices we take the following safeguard

$\zeta_{k}=\min\\{\overline{\zeta},\max\\{\underline{\zeta},\lambda_{k}\\}\\},\quad\underline{\zeta}=10^{-4},\quad\overline{\zeta}=10^{4}.$

Since the fixed step size such as $\alpha_{k}=1/k$ was already addressed in
[27] where the results show that it was clearly outperformed by the line
search LS-SPS method, we focus our attention on adaptive step size rules. The
value of $\tilde{\alpha}^{1}_{k}$ is chosen to be
$\tilde{\alpha}^{1}_{k}=\frac{1/k+\bar{\alpha}_{k}}{2}$, i.e., it is the
middle point of the interval $\left[\frac{1}{k},\bar{\alpha}_{k}\right]$.
Regarding the nonmonotone rule, we also test four choices (see [24] and the
references therein for more details):

  * •

Maximum (MAX) [15]:

$F_{k}=\max_{i\in[\max\\{1,k-5\\},k]}{f_{\mathcal{N}_{i}}(x_{i})};$

  * •

Convex combination (CCA) [45]:

$F_{k}=\max\\{f_{\mathcal{N}_{k}}(x_{k}),D_{k}\\},\;D_{k+1}=\frac{\eta_{k}q_{k}}{q_{k+1}}D_{k}+\frac{1}{q_{k+1}}f_{\mathcal{N}_{k+1}}(x_{k+1})$
$D_{0}=f_{\mathcal{N}_{0}}(x_{0}),\;q_{k+1}=\eta_{k}q_{k}+1,\;q_{0}=1,\;\eta_{k}=0.85;$

  * •

Monotone rule (MON):

$F_{k}=f_{\mathcal{N}_{k}}(x_{k});$

  * •

Additional term (ADA) [19]:

$F_{k}=f_{\mathcal{N}_{k}}(x_{k})+\frac{1}{2^{k}}.$

In order to find the best combination of the strategies proposed above, we
track the objective function value and plot it against the FEV - the number of
scalar products, which serves as a measure of computational cost. All the
plots are in the log scale. In the first phase of the experiments, we test AN-
SPS with different combinations of spectral coefficients and nonmonotone
rules, on four different data sets. The results reveal the benefits of the ADA
rule in almost all cases, as it can be seen on representative graphs on MNIST
data set (Figure 1). In particular, as expected, more ”nonmonotonicity”
usually yielded better results when combined with the spectral directions.

Figure 1:  AN-SPS algorithm with different nonmonotone rules and spectral
coefficients. Objective function value against the computational cost (FEV).
MNIST data set.

Furthermore, in order to see the benefits of the adaptive sample size
strategy, we compare AN-SPS with:

  * 1)

heuristic (HEUR) where the sample size is increased at each iteration by
$N_{k+1}=\lceil\min\\{1.1N_{k},N\\}\rceil$;

  * 2)

fixed sample strategy (FULL) where $N_{k}=N$ at each iteration.

We do the same tests for the HEUR and FULL to find the best-performing
combinations of BB and line search rules. Finally, we compare the best-
performing algorithms of each sample size strategy. The results for all the
considered data sets are presented in Figure 2 and they show clear advantages
of the adaptive sample size strategy in terms of computational costs.

Figure 2: Comparison of the best-performing combinations of spectral
coefficients and nonmonotone rules of AN-SPS, HEUR, and FULL sample size
strategies.

We also provide some results on problems that are convex, but not necessarily
strongly convex. In particular, we consider the same loss function, but
without the $L_{2}$-regularization part, i.e., the following problem

$\displaystyle\min_{x\in\Omega}f_{N}(x)$
$\displaystyle:=\frac{1}{N}\sum_{i=1}^{N}\max\\{{0,1-z_{i}x^{T}w_{i}\\}},\;\Omega:=\\{{x\in\mathbb{R}^{n}\;:||x||^{2}\leq
0.1\\}}.$

Instead of going through the phase of finding the best combination for each
method, we use the best-performing combinations obtained from testing the
strongly convex case. The results for convex case are presented in Figure 3
and they show that the proposed adaptive schemes are competitive even if the
regularization part is dropped.

Figure 3: Comparison of AN-SPS, HEUR, and FULL sample size strategies on
convex problems without the $L_{2}$-regularization part.

##  5 Conclusions

We provide an adaptive sample size algorithm for constrained nonsmooth convex
optimization problems, where the objective function is in the form of
mathematical expectation, and the feasible set allows exact projections. This
method allows an arbitrary (negative) subgradient direction related to the SAA
function, which is further scaled and multiplied by the spectral coefficient.
The coefficient can be defined in various ways and the only theoretical
requirement is to keep it bounded away from zero and infinity which can be
accomplished by using the standard safeguard rule. Scaling is important from a
theoretical point of view since it helps us to avoid boundedness assumptions
in the convergence analysis. We proved that the method pushes the sample size
to infinity and ensures that the SAA error tends to zero. On the other hand, a
numerical study on Hinge loss problems showed that the adaptive strategy is
efficient in terms of computational costs. Moreover, we proved that the almost
sure convergence toward a solution of the original problem is attained under
common assumptions in a stochastic environment. Furthermore, in the finite sum
case, the convergence is deterministic and is achieved under reduced
assumptions. Moreover, we provide the worst-case complexity analysis for this
case. Since spectral coefficients are employed, we propose a nonmonotone line
search over predefined intervals, although the monotone line search rule is
eligible from a theoretical point of view. The numerical study also examined
the performance of different line search rules and spectral coefficients. The
preliminary results provide some hints for future work that may include
adaptive nonmonotone strategies and inexact projections.

Acknowledgement. We are grateful to the associate editor and two anonymous
referees whose comments helped us improve the paper.

Funding. This work is supported by the Ministry of Education, Science and
Technological Development, Republic of Serbia.

Availability statement. The datasets analyzed during the current study are
available in the MNIST database of handwritten digits [18], LIBSVM Data:
Classification (Binary Class) [20] and UCI Machine Learning Repository [21].

Disclosure statement

Conflict of interest. The authors declare no competing interests.

## References

  * [1] J. Barzilai and J. M. Borwein, Two-point step size gradient method, IMA J. Numer. Anal. 8(1) (1988), pp. 141–148, https://doi.org/10.1093/imanum/8.1.141.
  * [2] F. Bastin, C. Cirillo, and P.L. Toint, An adaptive Monte Carlo algorithm for computing mixed logit estimators, Comput. Manag. Sci. 3(1) (2006), pp. 55-79, https://doi.org/10.1007/s10287-005-0044-y.
  * [3] S. Bellavia, N. Krejić, and N. Krklec Jerinkić, Subsampled inexact Newton methods for minimizing large sums of convex function, IMA J. Numer. Anal. 40(4) (2020), pp. 2309-2341, https://doi.org/10.1093/imanum/drz027.
  * [4] S. Bellavia, N. Krklec Jerinkić, and G. Malaspina, Subsampled nonmonotone spectral gradient methods, Commun. Appl. Ind. Math. 11(1) (2020), pp. 19-34, DOI: 10.2478/caim-2020-0002.
  * [5] E.G. Birgin, J.M. Martínez, and M. Raydan, Nonmonotone spectral projected gradients on convex sets, SIAM J. Optim. 10 (2000), pp. 1196-1211, https://doi.org/10.1137/S1052623497330963.
  * [6] S. Boyd and A. Mutapcic, Stochastic subgradient methods, Lecture Notes for EE364b, Stanford University (2008).
  * [7] S. Bubeck, Convex optimization: Algorithms and complexity, Found. Trends Mach. Learn. 8(3-4) (2015), pp. 231-357, https://doi.org/10.1561/2200000050.
  * [8] J. V. Burke, A. S. Lewis, and M. L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim. 15(3) (2005), pp. 751-779, https://doi.org/10.1137/030601296.
  * [9] V. Cevher, S. Becker, and M. Schmidt, Convex optimization for big data: Scalable, randomized, and parallel algorithms for big data analytics, IEEE Signal Process. Mag. 31(5) (2014), pp. 32-43, DOI: 10.1109/MSP.2014.2329397.
  * [10] D. di Serafino, N. Krejić, N. Krklec Jerinkić, and M. Viola, LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums, Math. Comput. 92(341) (2023), pp. 1273-1299, ISSN 0025-5718.
  * [11] D. Di Serafino, V. Ruggiero, G. Toraldo, and L. Zanni, On the steplength selection in gradient methods for unconstrained optimization, Appl. Math. Comput. 318 (2018), pp. 176-195, https://doi.org/10.1016/j.amc.2017.07.037.
  * [12] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., Ser. A 91 (2002), pp. 201-213, https://doi.org/10.1007/s101070100263.
  * [13] G. Frassoldati, L. Zanni, and G. Zanghirati, New adaptive stepsize selections in gradient methods, J. Ind. Manag. Optim. 4 (2) (2008), pp. 299–312, DOI: 10.3934/jimo.2008.4.299.
  * [14] M.P. Friedlander and M. Schmidt, Hybrid deterministic-stochastic methods for data fitting, SIAM J. Sci. Comput. 34(3) (2012), pp. 1380-1405, https://doi.org/10.1137/110830629.
  * [15] L. Grippo, F. Lampariello, and S. Lucidi, A nononotone line search technique for Newton’s method, SIAM J. Numer. Anal. 23(4) (1986), pp. 707-716, https://doi.org/10.1137/0723046.
  * [16] T. Homem-de-Mello, Variable-sample methods for stochastic optimization, ACM Trans. Model. Comput. Simul. 13(2) (2003), pp. 108–133, https://doi.org/10.1145/858481.858483.
  * [17] A. N. Iusem, A. Jofré, R. I. Oliveira, and P. Thompson, Variance-based extragradient methods with line search for stochastic variational inequalities, SIAM J. Optim. 29(1) (2019), pp. 175–206, https://doi.org/10.1137/17M1144799.
  * [18] Y. LeCun, C. Cortes, and C.J.C. Burges, The MNIST database of handwritten digits (1998), http://yann.lecun.com/exdb/mnist/
  * [19] D. H. Li and M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw. 13 (2000), pp. 181-201, DOI:10.1080/10556780008805782.
  * [20] LIBSVM Data: Classification (Binary Class), https://www.csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/datasets/binary.html
  * [21] M. Lichman, UCI machine learning repository (2013), https://archive.ics. uci.edu/ml/index.php
  * [22] A. Jalilzadeh, A. Nedić, U. V. Shanbhag, and F. Yousefian, A variable sample-size stochastic quasi-Newton Method for smooth and nonsmooth stochastic convex optimization, Proc. IEEE Conf. Decis. Control. (CDC), Miami Beach, FL, (2018), pp. 4097-4102, doi: 10.1109/CDC.2018.8619209.
  * [23] K. C. Kiwiel, Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim. 18(2) (2007), pp. 379-388, https://doi.org/10.1137/050639673.
  * [24] N. Krejić and N. Krklec Jerinkić, Nonmonotone line search methods with variable sample size, Numer. Algorithms 68(4) (2015), pp. 711-739, https://doi.org/10.1007/s11075-014-9869-1.
  * [25] N. Krejić and N. Krklec Jerinkić, Spectral projected gradient method for stochastic optimization, J. Glob. Optim. 73 (2018), pp. 59–81, https://doi.org/10.1007/s10898-018-0682-6.
  * [26] N. Krejić, N. Krklec Jerinkić, and T. Ostojić, An inexact restoration-nonsmooth algorithm with variable accuracy for stochastic nonsmooth convex optimization problems in machine learning and stochastic linear complementarity problems, J. Comput. Appl. Math. 423 (2023), 114943, https://doi.org/10.1016/j.cam.2022.114943.
  * [27] N. Krejić, N. Krklec Jerinkić, and T. Ostojić, Spectral projected subgradient method for nonsmooth convex optimization problems, Numer. Algorithms (2022), pp. 1-19, DOI : 10.1007/s11075-022-01419-3.
  * [28] N. Krejić, N. Krklec Jerinkić, and A. Rožnjik, Variable sample size method for equality constrained optimization problems, Optim. Lett. 12(3) (2018), pp. 485–497, https://doi.org/10.1007/s11590-017-1143-8.
  * [29] N. Krejić, Z. Lužanin, Z. Ovcin, and I. Stojkovska,  Descent direction method with line search for unconstrained optimization in noisy environment, Optim. Methods Softw. 30(6) 2015, pp. 1164-1184, https://doi.org/10.1080/10556788.2015.1025403.
  * [30] N. Krejić and J. M. Martinez, Inexact restoration approach for minimization with inexact evaluation of the objective function, Math. Comput. 85 (2016), pp. 1775-1791, https://doi.org/10.1090/mcom/3025.
  * [31] N. Krklec Jerinkić and A. Rožnjik, Penalty variable sample size method for solving optimization problems with equality constraints in a form of mathematical expectation, Numer. Algorithms 83 (2020), pp. 701-718https://doi.org/10.1007/s11075-019-00699-6.
  * [32] M. Loreto and A. Crema, Convergence analysis for the modified spectral projected subgradient method, Optim. Lett. 9(5) (2015), pp. 915-929, https://doi.org/10.1007/s11590-014-0792-0.
  * [33] M. Loreto, Y. Xu, and D. Kotval, A numerical study of applying spectral-step subgradient method for solving nonsmooth unconstrained optimization problems, Comput. Oper. Res. 104 (2019), pp. 90-97, https://doi.org/10.1016/j.cor.2018.12.006.
  * [34] K. Marti, Stochastic optimization methods, Springer, Heidelberg, third ed. (2015), Applications in engineering and operations research, https://doi.org/10.1007/978-3-662-46214-0.
  * [35] L. Martinez, R. Andrade, E. G. Birgin, and J. M. Martinez, Packmol: A package for building initial configurations for molecular dynamics simulations, J. Comput. Chem. 30 (2009), pp. 2157-2164, https://doi.org/10.1002/jcc.21224.
  * [36] A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, Wiley, New York (1983), https://doi.org/10.1137/1027074.
  * [37] C. Paquette and K. Scheinberg, A stochastic line search method with expected complexity analysis, SIAM J. Optim. 30(1) (2020), pp. 349-376, https://doi.org/10.1137/18M1216250.
  * [38] B. Polyak, Introduction to Optimization, Optim. Software, Inc., Publications Division, New York (1987).
  * [39] H. Robbins and D. Siegmund, A convergence theorem for non negative almost supermartingales and some applications, In Optimizing methods in statistics (1971), pp. 233-257, Academic Press, https://doi.org/10.1016/B978-0-12-604550-5.50015-8.
  * [40] A. Shapiro, D. Dentcheva, and A. Ruszczynski, Lectures on stochastic programming: modeling and theory. MPS-SIAM Series on Optimization (2009).
  * [41] N. Shor, Minimization methods for non-differentiable functions, Springer Series in Computational Mathematics, Springer, (1985).
  * [42] J. C. Spall, Introduction to stochastic search and optimization: estimation, simulation, and control, John Wiley & Sons (2005).
  * [43] D. Vicari, A. Okada, G. Ragozini, and C. Weihs, eds., Analysis and modeling of complex data in behavioral and social sciences, Springer, Cham, (2014), https://doi.org/10.1007/978-3-319-06692-9.
  * [44] J. Yu, S. Vishwanathan, S. Guenter, and N. Schraudolph, A quasi-Newton approach to nonsmooth convex optimization problems in machine learning, J. Mach. Learn. Res. 11 (2010), pp. 1145-1200.
  * [45] H. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim. 4 (2004), pp. 1043-1056, https://doi.org/10.1137/S1052623403428208.
  * [46] B. Zhou, L. Gao, and Y.H. Dai, Gradient methods with adaptive step-sizes, Comput. Optim. Appl. 35 (1) (2006), pp. 69–86, https://doi.org/10.1007/s10589-006-6446-0.

##  6 Appendix

Recall that $X^{*}$ and $f^{*}$ are the set of solutions and the optimal value
of problem (1.1), respectively.

Proof of Proposition 3.2.

###### Proof.

Let $x^{*}$ be an arbitrary solution of the problem (1.1). Following the steps
of (3.2) and the definition (3.8) we obtain for all $k=0,1,\ldots$

$\displaystyle||x_{k+1}-x^{*}||^{2}$ $\displaystyle=$
$\displaystyle||P_{\Omega}(z_{k+1})-P_{\Omega}(x^{*})||^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-x^{*}||^{2}+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f_{\mathcal{N}_{k}}(x^{*})-f_{\mathcal{N}_{k}}(x_{k}))+\alpha_{k}^{2}\bar{\zeta}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-x^{*}||^{2}+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f(x^{*})-f(x_{k})+\bar{e}_{k})+\alpha_{k}^{2}\bar{\zeta}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-x^{*}||^{2}+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f(x^{*})-f(x_{k}))+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}\bar{e}_{k}+\alpha_{k}^{2}\bar{\zeta}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-x^{*}||^{2}+2\alpha_{k}\bar{\zeta}\bar{e}_{k}+\alpha_{k}^{2}\bar{\zeta}^{2},$

where we use the fact that $x_{k}$ is feasible and thus $f(x^{*})-f(x_{k})\leq
0$ and that $q_{k}\geq 1$. Further, by the induction argument and the fact
that $\alpha_{k}\leq C_{2}/k$ we obtain

$||x_{k}-x^{*}||^{2}\leq||x_{0}-x^{*}||^{2}+2C_{2}\overline{\zeta}\sum_{k=0}^{\infty}\frac{\bar{e}_{k}}{k}+\overline{\zeta}^{2}\sum_{k=0}^{\infty}\frac{C^{2}_{2}}{k^{2}}\leq
C_{5}<\infty.$

This completes the proof. ∎

Proof of Theorem 3.3

###### Proof.

First, notice that Theorem 3.1 implies that $\lim_{k\to\infty}N_{k}=\infty$ in
ubounded sample case. Moreover, Proposition 3.2 implies that
$\\{x_{k}\\}\subseteq\bar{\Omega}$. Furthermore, Assumption A2 implies that
for any $\mathcal{N}$ we have locally $L_{x}$-Lipschitz continuous function
$f_{\mathcal{N}}(x)$. Thus, there exists a constant $L$ such that
$f_{\mathcal{N}}$ is $L$-Lipschitz continuous on $\bar{\Omega}$ for any
$\mathcal{N}$. This further implies that $\|\bar{g}_{k}\|\leq L$ for each $k$
and

$1\leq q_{k}\leq\max\\{1,L\\}:=\bar{q}.$ (6.2)

Denote by $\mathcal{W}$ the set of all possible sample paths of AN-SPS
algorithm. First we prove that

$\liminf_{k\to\infty}f(x_{k})=f^{*}\quad\mbox{a.s.,}$ (6.3)

where $f^{*}=\inf_{x\in\Omega}f(x).$ Suppose that
$\liminf_{k\to\infty}f(x_{k})=f^{*}$ does not happen with probability 1. In
that case there exists a subset of sample paths
$\tilde{\mathcal{W}}\subseteq\mathcal{W}$ such that $P(\tilde{\mathcal{W}})>0$
and for every $w\in\tilde{\mathcal{W}}$ there holds

$\liminf_{k\rightarrow\infty}f(x_{k}(w))>f^{*},$

i.e., there exists $\varepsilon(w)>0$ small enough such that
$f(x_{k}(w))-f^{*}\geq 2\varepsilon(w)$ for all $k$. Since $f$ is assumed to
be continuous and bounded from below on $\Omega$, $f^{*}$ is finite and we
conclude that there exists a point $\tilde{y}(w)\in\Omega$ such that
$f(\tilde{y}(w))<f^{*}+\varepsilon(w).$ This further implies

$f(x_{k}(w))-f(\tilde{y}(w))>f(x_{k}(w))-f^{*}-\varepsilon(w)\geq
2\varepsilon(w)-\varepsilon(w)=\varepsilon(w).$

Let us take an arbitrary $w\in\tilde{\mathcal{W}}.$ Denote
$z_{k+1}(w):=x_{k}(w)+\alpha_{k}(w)p_{k}(w)$. Notice that nonexpansivity of
orthogonal projection and the fact that $\tilde{y}\in\Omega$ together imply

$||x_{k+1}(w)-\tilde{y}(w)||=||P_{\Omega}(z_{k+1}(w))-P_{\Omega}(\tilde{y}(w))||\leq||z_{k+1}(w)-\tilde{y}(w)||.$
(6.4)

Using (6.2) and the fact that $\bar{g}_{k}$ is subgradient of convex function
$f_{\mathcal{N}_{k}}$, i.e., $\bar{g}_{k}\in\partial
f_{\mathcal{N}_{k}}(x_{k})$, we have
$f_{\mathcal{N}_{k}}(x_{k})-f_{\mathcal{N}_{k}}(\tilde{y})\leq\overline{g}^{T}_{k}(x_{k}-\tilde{y})$.
Dropping $w$ in order to facilitate the reading and defining

$e_{k}:=|f_{{\cal{N}}_{k}}(\tilde{y})-f(\tilde{y})|+\max_{x\in\bar{\Omega}}|f_{{\cal{N}}_{k}}(x)-f(x)|,$

we obtain

$\displaystyle||z_{k+1}-\tilde{y}||^{2}$ $\displaystyle=$
$\displaystyle||x_{k}+\alpha_{k}p_{k}-\tilde{y}||^{2}=||x_{k}-\alpha_{k}\zeta_{k}v_{k}-\tilde{y}||^{2}$
(6.5) $\displaystyle=$
$\displaystyle||x_{k}-\tilde{y}||^{2}-2\alpha_{k}\zeta_{k}\frac{\overline{g}^{T}_{k}}{q_{k}}\left(x_{k}-\tilde{y}\right)+\alpha_{k}^{2}\zeta^{2}_{k}||v_{k}||^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}||^{2}+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f_{\mathcal{N}_{k}}(\tilde{y})-f_{\mathcal{N}_{k}}(x_{k}))+\alpha_{k}^{2}\zeta_{k}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}||^{2}+2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f(\tilde{y})-f(x_{k})+e_{k})+\alpha_{k}^{2}\zeta_{k}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}||^{2}-2\alpha_{k}\frac{\zeta_{k}}{q_{k}}(f(x_{k})-f(\tilde{y}))+2e_{k}\alpha_{k}\overline{\zeta}+\alpha_{k}^{2}\overline{\zeta}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k}-\tilde{y}||^{2}-2\alpha_{k}\frac{\underline{\zeta}}{\bar{q}}\varepsilon+2e_{k}\alpha_{k}\overline{\zeta}+\alpha_{k}^{2}\overline{\zeta}^{2}$
$\displaystyle=$
$\displaystyle||x_{k}-\tilde{y}||^{2}-\alpha_{k}\left(2\frac{\underline{\zeta}}{\bar{q}}\varepsilon-2e_{k}\overline{\zeta}-\alpha_{k}\overline{\zeta}^{2}\right),$

Since, $\\{x_{k}\\}\subseteq\bar{\Omega}$, ULLN under the stated assumptions
implies $\lim_{k\rightarrow\infty}e_{k}(w)=0$ for almost every
$w\in\mathcal{W}$. Since $P(\tilde{\mathcal{W}})>0$, there must exist a sample
path $\tilde{w}\in\tilde{\mathcal{W}}$ such that

$\lim_{k\rightarrow\infty}e_{k}(\tilde{w})=0.$

This further implies the existence of $\tilde{k}(\tilde{w})\in\mathbb{N}$ such
that for all $k\geq\tilde{k}(\tilde{w})$ we have

$\alpha_{k}(\tilde{w})\overline{\zeta}^{2}+2e_{k}(\tilde{w})\overline{\zeta}\leq\varepsilon(\tilde{w})\frac{\underline{\zeta}}{\bar{q}}$
(6.6)

because Step S2 of AN-SPS algorithm implies that
$\lim_{k\to\infty}\alpha_{k}=0$ for any sample path. Furthermore, since (6.5)
holds for all $w\in\tilde{\mathcal{W}}$ and thus for $\tilde{w}$ as well, from
(6.4)-(6.6) we obtain

$||x_{k+1}(\tilde{w})-\tilde{y}(\tilde{w})||^{2}\leq||z_{k+1}(\tilde{w})-\tilde{y}(\tilde{w})||^{2}\leq||x_{k}(\tilde{w})-\tilde{y}(\tilde{w})||^{2}-\alpha_{k}(\tilde{w})\varepsilon(\tilde{w})\frac{\underline{\zeta}}{\bar{q}}$

and

$||x_{k+s}(\tilde{w})-\tilde{y}(\tilde{w})||^{2}\leq||x_{k}(\tilde{w})-\tilde{y}(\tilde{w})||^{2}-\varepsilon(\tilde{w})\frac{\underline{\zeta}}{\bar{q}}\sum_{j=0}^{s-1}\alpha_{j}(\tilde{w}).$

Letting $s\to\infty$ yields a contradiction since
$\sum_{k=0}^{\infty}\alpha_{k}\geq\sum_{k=0}^{\infty}1/k=\infty$ for any
sample path and we conclude that (6.3) holds.

Now, let us prove that

$\lim_{k\rightarrow\infty}x_{k}=x^{*}\quad\text{a.s.}$ (6.7)

Since (6.3) holds, we know that

$\liminf_{k\rightarrow\infty}f(x_{k}(w))=f^{*},$ (6.8)

for almost every $w\in\mathcal{W}$. In other words, there exists
$\overline{\mathcal{W}}\subseteq\mathcal{W}$ such that
$P(\overline{\mathcal{W}})=1$ and (6.8) holds for all
$w\in\overline{\mathcal{W}}$. Let us consider arbitrary
$w\in\overline{\mathcal{W}}$. We will show that
$\lim_{k\rightarrow\infty}x_{k}(w)=x^{*}(w)\in X^{*}$ which will imply the
result (6.7). Once again let us drop $w$ to facilitate the notation. Let
$K_{1}\subseteq\mathbb{N}$ be a subsequence of iterations such that

$\lim_{k\in K_{1}}f(x_{k})=f^{*}.$

Since $\\{{x_{k}\\}}_{k\in K_{1}}\subseteq\\{{x_{k}\\}}_{k\in\mathbb{N}}$ and
$\\{{x_{k}\\}}_{k\in\mathbb{N}}$ is bounded, there exist $K_{2}\subseteq
K_{1}$ and $\tilde{x}$ such that

$\lim_{k\in K_{2}}x_{k}=\tilde{x}.$ (6.9)

Then, we have

$f^{*}=\lim_{k\in K_{1}}f(x_{k})=\lim_{k\in K_{2}}f(x_{k})=f(\lim_{k\in
K_{2}}x_{k})=f(\tilde{x}).$

Therefore, $f(\tilde{x})=f^{*}$ and we have $\tilde{x}\in X^{*}$. Now, we show
that the whole sequence of iterates converges. Let $\\{{x_{k}\\}}_{k\in
K_{2}}:=\\{{x_{k_{i}}\\}}_{i\in\mathbb{N}}.$ Following the steps of (6) and
using the fact that $f(x_{k})\geq f(\tilde{x})$ for all $k$, we obtain that
the following holds for any $s\in\mathbb{N}$

$\displaystyle||x_{k_{i}+s}-\tilde{x}||^{2}$ $\displaystyle\leq$
$\displaystyle||x_{k_{i}}-\tilde{x}||^{2}+2\overline{\zeta}\sum_{j=0}^{s-1}\bar{e}_{k_{i}+j}\alpha_{k_{i}+j}+\overline{\zeta}^{2}\sum_{j=0}^{s-1}\alpha_{k_{i}+j}^{2}$
$\displaystyle\leq$
$\displaystyle||x_{k_{i}}-\tilde{x}||^{2}+2\overline{\zeta}\sum_{j=0}^{\infty}\bar{e}_{k_{i}+j}\alpha_{k_{i}+j}+\overline{\zeta}^{2}\sum_{j=0}^{\infty}\alpha_{k_{i}+j}^{2}$
$\displaystyle=$
$\displaystyle||x_{k_{i}}-\tilde{x}||^{2}+2\overline{\zeta}\sum_{j=k_{i}}^{\infty}\bar{e}_{j}\alpha_{j}+\overline{\zeta}^{2}\sum_{j=k_{i}}^{\infty}\alpha_{j}^{2}=:a_{i}.$

Moreover, for any $s,m\in\mathbb{N}$ there holds

$||x_{k_{i}+s}-x_{k_{i}+m}||^{2}\leq
2||x_{k_{i}+s}-\tilde{x}||^{2}+2||x_{k_{i}+m}-\tilde{x}||^{2}\leq 4a_{i}.$

Due to the fact that $\sum_{j=k_{i}}^{\infty}\bar{e}_{j}\alpha_{j}$ and
$\sum_{j=k_{i}}^{\infty}\alpha_{j}^{2}$ are the residuals of convergent sums,
and that (6.9) holds, we conclude that

$\lim_{i\to\infty}a_{i}=0.$

Thus, we have just proved that $\\{x_{k}\\}_{k\in\mathbb{N}}$ is a Cauchy
sequence and thus convergent, which together with (6.9) implies that
$\lim_{k\to\infty}x_{k}=\tilde{x}$. ∎