On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences

I Introduction

The use of stochastic gradient and subgradient schemes for the solution of stochastic convex optimization problems has a long tradition, beginning with an iterative scheme, first proposed by Robbins and Monro , that relied primarily on noisy gradient observations. Research by Ermoliev and his coauthors focused largely on quasigradient (subgradient) methods and considered a host of stochastic programming problems, amongst them being two-period recourse-based problems (see ). To accelerate the convergence of stochastic subgradient methods, ergodic sequences, arising from the averaging of iterates, have been employed in . Often gradient computations are either costly or unavailable; in such instances, a finite-difference approximation of the gradient can be constructed as first observed by Kiefer and Wolfowitz . While standard finite-difference techniques perturb one direction at a time to obtain gradient estimates, simultaneous perturbation stochastic approximation techniques simultaneously perturb all directions and general require fewer function evaluations . More recently, there has been a significant interest in the application of ODE-based methods for investigating the stability and convergence of the associated stochastic approximation schemes . An elegant exposition of these methods may be found in the monographs by Polyak , Kushner and Yin , and Borkar .

Sample-average approximation (SAA) techniques are often viewed as an alternative to stochastic approximation techniques and are particularly attractive when approximate solutions to the problem are desired in an offline manner. This approach relies on using a sample from the underlying distribution to construct a deterministic sample-average problem, which can be subsequently solved via standard nonlinear programming solvers, as seen in . In , the authors demonstrate that stochastic approximation schemes are shown to be competitive with SAA techniques. Importantly in , Nemirovski et al. develop a robust SA scheme that determines an optimal constant steplength for minimizing the theoretical error over a pre-specified number of steps. Mirror-descent generalizations of SA, that rely on a suitably defined prox-mapping, are also presented in (also see ), while validation analysis is provided in .

Stochastic gradient algorithms have also been found to be effective in solving large deterministic problems such as convex feasibility problems , feasibility problems arising in control and some specially structured large-scale convex problems in . Distributed consensus-based stochastic subgradient methods for minimizing a convex objective over a network have been recently developed and studied in . The success of gradient-based methods in solving monotone variational inequalities has prompted the study of similar techniques for contending with stochastic variational inequalities. In fact, Jiang and Xu develop precisely such a scheme for the solution of strongly monotone stochastic variational inequalities and regularized variants were presented in to allow for application to monotone stochastic variational inequalities. Finally, stochastic generalizations of the mirror-prox schemes were examined in and allowed for the solution of monotone variational inequalities.

While stochastic approximation schemes have proved successful, other avenues exist for addressing stochastic programs. For instance, an alternate approach lies in using sample-average approximation methods, that obtain estimators to the optimal value and solution of the problem through the solution of deterministic problem in which the expectation is replaced by a sample-average. Convergence theory for the obtained estimators is examined by Shapiro . Decomposition schemes, that leverage cutting-plane methods, have also been particularly successful in addressing two-period stochastic linear , convex and nonconvex programs while a scalable matrix-splitting decomposition scheme is presented in for two-period stochastic Nash games.

In this paper, we consider adaptive stochastic gradient and subgradient methods for solving constrained stochastic convex optimization problems. The novelty of our work can be categorized as follows: (1) the development and analysis of two adaptive stepsize rules; and (2) the development of a local function smoothing technique. Next, we provide some motivation and a more elaborate description of each.

In stochastic gradient methods (cf. ), the almost-sure convergence of such methods is guaranteed assuming that the stepsize is diminishing but not too rapidly, i.e., the stepsize is proportional to $\frac{1}{k^{a}}$ with $\frac{1}{2}<a\leq 1$. Typically, there is no guidance on the specific choice of the sequence and problem parameters play little role in refining this choice. In contrast, in this paper, we propose specific (adaptive) rules for the stepsize values that exploit the information about the objective function. Accordingly, our first goal lies in examining whether one can construct a convergent scheme under an adaptive stepsize rule that is more reflective of the problem setting. Through out this part of the paper, we assume that the integrand of the expectation is a random convex differentiable function. Under a Lipschitzian assumption on the gradient, we propose two different adaptive stepsize rules:

Recursive stepsize rule: In attempting to minimize the bound on the expected error, we develop a recursive scheme for specifying the stepsize that requires only the steplength at the previous parameter and some problem parameters. Global convergence and rate estimates for this scheme are developed.

Cascading stepsize rule: It is well-known that under suitable assumptions, fixed-stepsize schemes are guaranteed to converge to a compact region containing the solution set of the original problem. We consider a modified version of such a scheme where the trajectory moves to successively smaller compact regions containing the solution sets. Furthermore, as soon as the trajectory of iterates reaches within a bound of the solution set, the steplength is updated allowing the sequence to make further progress. Effectively, we consider a method in which the steplength sequence can be viewed as one where the stepsize is maintained constant with drops or cascades in stepsize occurring at particular epochs. While the scheme has intuitive appeal, we provide a theoretical support for the convergence of such an algorithmic framework.

When the random integrands arising in such stochastic problems are nonsmooth, direct application of known SA schemes is impossible. Contending with nonsmoothness in mathematical programming is often managed through avenues that rely on the solution of a sequence of smoothed problems (cf. ). In a stochastic regime, an approach for addressing such problems is through a technique of global smoothing, as considered in and more recently in .See for a scheme that develops an approximation method for addressing a class of separable piecewise-linear stochastic optimization problems with integer breakpoints. This involves modifying the original problem by adding a random variable with possibly unbounded support. However, such a technique is not feasible in when the objective is defined over a restricted domain. We present a local smoothing technique which leads to a globally differentiable approximation of the original function with Lipschitz continuous gradients. Furthermore, through such a smoothing, we derive a Lipschitz constant for the gradients and show that the constant grows at the rate of $\sqrt{n}$ where $n$ is the dimensionality of the problem space. Importantly, this Lipschitzian property facilitates the construction of a stochastic approximation framework. Consequently, the second part of the paper focuses on computing solutions to approximations with smoothed integrands whose gradients are shown to be provably Lipschitz continuous.

The remainder of the paper is organized as follows. In Section II, we establish the almost-sure convergence of the classical stochastic approximation algorithm for a constrained problem with a differentiable convex function with Lipschitz gradients. In Sections III and IV, for a strongly convex function, we propose and analyze two different stepsize rules, each motivated by a minimization of an estimate on the expected error per iteration of the method. In Section V, we introduce a local randomized smoothing technique for nondifferentiable convex optimization, and derive its approximation properties as well as a bound on the Lipschitz constant of the gradients. In Section VI, we report some numerical results obtained by applying our proposed stepsize rules and the smoothing technique to three test problems and conclude with a discussion in Section VII.

Notation and basic terminology: We view vectors as columns, and write $x^{T}$ to denote the transpose of a vector $x$. We use $\|x\|$ to denote the Euclidean vector norm, i.e., $\|x\|=\sqrt{x^{T}x}$. We write $\Pi_{X}(x)$ to denote the Euclidean projection of a vector $x$ on a set $X$. i.e., $\|x-\Pi_{X}(x)\|=\min_{y\in X}\|x-y\|$. For a convex function $f$ with domain ${\rm dom}f$, a vector $g$ is a subgradient of $f$ at $\bar{x}\in{\rm dom}f$ if the following relation holdsFor a differentiable convex $f$, the inequality holds with $g=\nabla f(\bar{x})$.:

The subdifferential set of $f$ at $x=\bar{x}$, denoted by $\partial f(\bar{x})$, is the set of all subgradients of $f$ at $x=\bar{x}$. Finally, we write a.s. for “almost surely”, and use $\hbox{Prob}(\mathcal{Z})$ and $\mathsf{E}\!\left[Z\right]$ to denote the probability of an event $\mathcal{Z}$ and the expectation of a random variable $Z$, respectively.

II Problem Formulation and Background

In this section, we begin by describing the problem and iterative scheme of interest (Section II-A). This is followed by Section II-B where we provide a short description on various adaptive schemes in the realm of stochastic approximation.

We consider the following stochastic optimization problem

The set $X\subset\mathcal{D}$ is convex and closed. The function $F(\cdot,\xi)$ is convex on $\mathcal{D}$ for every $\xi\in\Omega$, and the expected value $\mathsf{E}\!\left[F(x,\xi)\right]$ is finite for every $x\in\mathcal{D}$.

Under Assumption 1, the function $f$ is convex over $X$ and the following relation holds

First, we will consider problem (1) where $f$ is a differentiable function with Lipschitz gradients. Later, we will allow the function $f$ to be nondifferentiable and we will consider a local smoothing technique yielding a differentiable function that approximates $f$ over $X$. For this reason, we start our discussion by focusing on a differentiable problem (1) and the following iterative algorithm:

Here, $x_{0}\in X$ is a random initial point, $\gamma_{k}>0$ is a (deterministic) stepsize, and $w_{k}$ is the random vector given by the difference between the sampled gradient $\nabla_{x}F(x,\xi_{k})$ and its expectation $\mathsf{E}\!\left[\nabla_{x}F(x,\xi)\right]$ evaluated at $x=x_{k}$. Throughout the paper, we assume that $\mathsf{E}\!\left[\|x_{0}\|^{2}\right]<\infty$.

We let $\mathcal{F}_{k}$ denote the history of the method up to time $k$, i.e., $\mathcal{F}_{k}=\{x_{0},\xi_{0},\xi_{1},\ldots,\xi_{k-1}\}$ for $k\geq 1$ and $\mathcal{F}_{0}=\{x_{0}\}$. By Assumption 1 and relation (2), it follows that $\nabla f(x_{k})=\mathsf{E}\!\left[\nabla_{x}F(x_{k},\xi)\right]$ for a differentiable $F$, implying that $w_{k}$ has zero-mean, i.e.,

Next, we state some additional assumptions on the stochastic gradient error $w_{k}$ and the stepsize $\gamma_{k}$.

The stepsize is such that $\gamma_{k}>0$ for all $k$. Furthermore, the following hold:

$\sum_{k=0}^{\infty}\gamma_{k}=\infty$ and $\sum_{k=0}^{\infty}\gamma_{k}^{2}<\infty$.

The stochastic errors $w_{k}$ satisfy $\sum_{k=0}^{\infty}\gamma_{k}^{2}\mathsf{E}\!\left[\|w_{k}\|^{2}\mid\mathcal{F}_{k}\right]<\infty$ almost surely.

Assumption 2(b) is satisfied, for example, when $\sum_{k=0}^{\infty}\gamma_{k}^{2}<\infty$ and the error $w_{k}$ is bounded almost surely, i.e., $\|w_{k}\|\leq c$ for all $k$ and some scalar $c$ almost surely.

We use the following Lemma in establishing the convergence of method (3) (see , page 50).

(Robbins-Siegmund) Let $v_{k},$ $u_{k},$ $\alpha_{k},$ and $\beta_{k}$ be nonnegative random variables, and let the following relations hold almost surely:

We also make use of the following result, which can be found in (see Lemma 11 in page 50).

Let $\{v_{k}\}$ be a sequence of nonnegative random variables, where $\mathsf{E}\!\left[v_{0}\right]<\infty$, and let $\{\alpha_{k}\}$ and $\{\beta_{k}\}$ be deterministic scalar sequences such that:

Then, $v_{k}\rightarrow 0$ almost surely, $\lim_{k\to\infty}\mathsf{E}\!\left[v_{k}\right]=0$, and for any $\epsilon>0$,

In Sections III and IV, we examine adaptive steplength schemes for a strongly convex function $f$ whose gradients $\nabla f$ are Lipschitz continuous over $X$ with constant $L$. $X$ is defined as

II-B Adaptive Stochastic Approximation Schemes

Robbins and Monro proposed the first stochastic approximation algorithm in 1951 while Kiefer and Wolfowitz proposed a variant of this scheme in which finite differences were employed to estimate the gradient. Asymptotic distributions of the Robbins-Monro scheme were first examined by Chung , leading to an asymptotic normality result in the one-dimensional regime while generalizations were subsequently studied by Sacks .

A potential challenge in developing efficient implementations of stochastic approximation implementations lies in choosing an appropriate steplength sequence. Kesten , in 1957, suggested a technique where the steplength sequence adapts to the observed data, which was further extended by Kushner and Gavin to the multi-dimensional regime, while its accelerations were studied in . Sacks proved that, under suitable conditions, a choice of the form $a/k$ (where $k$ is the iterate index) is optimal from the standpoint of minimizing the asymptotic variance. Yet, the challenge lies in estimating the “optimal” $a$. Subsequently, Ventner in what is possibly amongst the first adaptive steplength SA schemes, considered sequences of the form $a_{k}/k$ where $a_{k}$ is updated by leveraging past information. Notably, Chung also examined the asymptotic variance properties of SA when steplength choices of the form $a/k^{1-\alpha}$ with $\alpha<{1\over 2}$ are used. In related work on adaptive schemes, Lai and Robbins considered schemes of the form $a_{k}/k$ where $a_{k}$ is a strongly consistent estimator of $\nabla f(x)$ in a stochastic root-finding problem. One choice for obtaining $a_{k}$ is through the use of least-squares estimators. Multivariate generalizations of this analysis were suggested by Wei in 1987 and again, it was observed that the Jacobian of the vector function assumes relevance in constructing efficient steplength sequences.

An alternative to using a single sample was suggested by Spall and relied on obtaining gradient estimates through a simultaneous perturbation of all the parameters. An adaptive generalization of this scheme, proposed by the same author , employed an additional recursion to the standard projected gradient step that attempted to estimate the Jacobian in root finding problems or the Hessian in optimization problems. Accordingly, the modified update rule is of the form

where $H_{k}$ is an estimate of the Hessian matrix of the objective. Clearly, this also falls under the regime of an adaptive steplength scheme. Related adaptive schemes may also be found in the work by Bhatnagar .

A final remark is in order regarding the key difference between our proposed schemes and past work. A majority of the adaptive schemes in the literature employ past information to update the steplength. One such avenue involves developing estimates of the Hessian which is subsequently used in scaling the gradient step appropriately. In the sections to appear, we consider two very different approaches that are linked by a crucial property: they rely on using algorithm and problem parameters, and not sample points, to develop adaptive steplength schemes.

II-C Smoothing Techniques

One of the goals of this paper is to address stochastic optimization problems with nonsmooth integrands. Here, we provide some background for accommodating nonsmoothness in optimization problems. In deterministic regimes, subgradient methods and their incremental variants have proved popular (see ), as have bundle methods , amongst others. One approach for managing nonsmoothness is through smoothing approaches. For instance, such avenues have allowed for the solution of variational inequalities and complementarity problems as well as mathematical programs with equilibrium constraints .

In this paper, we also adopt a smoothing technique which bears little similarity to such approaches. We adopt a framework that can be traced back to a class of averaged functions introduced by Steklov in 1907. A general definition of such an averaging over possibly discontinuous functions is provided next .

We pursue an alternative to solving a sequence of smoothed problems and obtain an approximate solution by solving a single smoothed problem with a fixed $\epsilon$ akin to that employed by Lakshmanan and Farias . However, since we intend to leverage stochastic approximation schemes of the form described earlier in this paper, Lipschitz constants associated with the gradients are a requiem. In , the authors obtain Lipschitz constants assuming that the averaging is achieved through a normal distribution that requires the function be defined everywhere. Instead of “globally smoothing” the function, we employ a uniform distribution, referred to as “local smoothing.”

III A recursive steplength stochastic approximation scheme

In this section, we introduce an adaptive stochastic approximation scheme that overcomes certain challenges associated with implementing standard diminishing steplength schemes and relies on the use of a recursive rule for prescribing steplengths. We begin by examining the standard stochastic gradient method for problem (1) in Section III-A. In general, the convergence of this scheme is guaranteed under the requirement that $\sum_{k=1}^{\infty}\gamma_{k}=\infty$ and $\sum_{k=0}^{\infty}\gamma_{k}^{2}<\infty.$ A host of choices exists with one possible choice being $\gamma_{k}=\theta/k.$ Yet, the choice of the appropriate $\theta$ can have a significant impact on the performance of the algorithm. Motivated by the desire to minimize the “expected error,” we develop a recursive stochastic approximation algorithm (referred to as the RSA scheme) in which the steplength at a particular iteration is a function of the steplength at the previous iteration and some problem parameters. In Section III-B, we motivate and introduce such a scheme and proceed to develop the associated convergence theory in Section III-C.

We consider method (3) as applied to problem (1) where $f$ has Lipschitz gradients. The method generates a sequence of iterates that converge to an optimal solution almost-surely, as shown in the forthcoming proposition. This result is a straightforward extension of Theorem 1 in [16, Pg. 51] which pertains to an unconstrained problem.

Let Assumptions 1–2 hold, and let $f$ be differentiable over the set $X$ with Lipschitz gradients. Assume that the optimal set $X^{*}$ of problem (1) is nonempty. Then, the sequence $\{x_{k}\}$ generated by (3) converges almost surely to some random point in $X^{*}$.

By definition of the method and the nonexpansive property of the projection operation, we obtain for any $x^{*}\in X^{*}$ and $k\geq 0$,

By the convexity of $f$ and the gradient inequality, we have

Taking the conditional expectation given $\mathcal{F}_{k}$, using $\mathsf{E}\!\left[w_{k}\mid\mathcal{F}_{k}\right]=0$ (see Eq. (4)) and the Lipschitzian property of the gradient, we have

Under Assumption 2, the conditions of Lemma 1 are satisfied. Therefore, almost surely, the sequence $\{\|x_{k+1}-x^{*}\|\}$ is convergent for any $x^{*}\in X^{*}$ and $\sum_{k=0}^{\infty}\gamma_{k}(f(x_{k})-f^{*})<\infty$. The former relation implies that $\{x_{k}\}$ is bounded a.s., while the latter implies $\liminf_{k\to\infty}f(x_{k})=f^{*}$ a.s. in view of the condition $\sum_{k=0}^{\infty}\gamma_{k}=\infty$. Since the set $X$ is closed, all accumulation points of $\{x_{k}\}$ lie in $X$. Furthermore, since $f(x_{k})\to f^{*}$ along a subsequence a.s., by continuity of $f$ it follows that $\{x_{k}\}$ has a subsequence converging to some random point in $X^{*}$ a.s. Moreover, since $\{\|x_{k+1}-x^{*}\|\}$ is convergent for any $x^{*}\in X^{*}$ a.s., the entire sequence $\{x_{k}\}$ converges to some random point in $X^{*}$ a.s. ∎

Under the Lipschitz continuity of the gradient and the strong convexity of the objective, an expected error bound may also be provided for the method. During the development of the error bound, the following intermediate result assumes relevance.

Let Assumption 1 hold, and let $f$ be differentiable over the set $X$ with Lipschitz gradients with constant $L>0$. Also, assume that the optimal set $X^{*}$ of problem (1) is nonempty. Let the sequence $\{x_{k}\}$ be generated by algorithm (3) with any (deterministic) stepsize $\gamma_{k}>0$. Then, for any $x^{*}\in X^{*}$ and any $k\geq 0$, the following holds almost surely:

By the first-order optimality conditions, a vector $x^{*}$ is optimal for the problem if and only if $x^{*}$ satisfies

By the definition of the method and the nonexpansive property of the projection operation, we obtain for all $k\geq 0$,

Taking the expectation conditioned on the past, and using $\mathsf{E}\!\left[w_{k}\mid\mathcal{F}_{k}\right]=0$ (cf. Eq. (4)), we have

The Lipschitz gradient property for a convex function is equivalent to co-coercivity of the gradient map with constant $1/L$, (see [16, Pg. 24, Lemma 2]), i.e., for all $x,y\in X$,

Therefore, for any $x^{*}\in X^{*}$ and any $k\geq 0$,

In what follows, we will often use a stronger version of Assumption 2(b), given as follows.

The errors $w_{k}$ are such that for some $\nu>0$,

Next, we provide an error bound for algorithm (3) under the assumption that $f(x)$ is a strongly convex function with Lipschitz gradients. Note that requiring that $f(x)$ is strongly convex over a set $K$ follows if $F(x,\xi(\omega))$ is a strongly convex function for $\omega\in\bar{\Omega}$, where $\bar{\Omega}$ is a set of positive measure defined as

Less formally, we merely require that $F(.,\xi)$ is a strongly convex function with positive, but arbitrarily small, probability to ensure that $f(x)$ is strongly convex over $K$ (see ).

Let Assumptions 1–2 hold. Also, let $f$ be differentiable over the set $X$ with Lipschitz gradients with constant $L>0$ and strongly convex with constant $\eta>0$. Then, the sequence $\{x_{k}\}$ generated by algorithm (3) converges almost surely to the unique optimal solution of problem (1). Furthermore, if the stepsize satisfies $0<\gamma_{k}\leq\frac{2}{L}$ for all $k\geq 0$, we then have:

The following relation holds almost surely:

If Assumption 2(b) is replaced with Assumption 3, then the following relation holds almost surely:

Moreover, $\lim_{k\to\infty}\mathsf{E}\!\left[\|x_{k}-x^{*}\|^{2}\right]=0$, and for every $\epsilon>0$,

The existence and uniqueness of the optimal solution of problem (1) is guaranteed by the strong convexity of $f(x)$. The convergence of the method follows by Proposition 1. To establish the relation in part (a) for the expected value $\mathsf{E}\!\left[\|x_{k+1}-x^{*}\|^{2}\right]$, we use Lemma 3, which implies for the optimal $x^{*}$ and all $k\geq 0$,

By the strong convexity of $f(x)$, we have $(x-y)^{T}(\nabla f(x)-\nabla f(y))\geq\eta\|x-y\|^{2}$ for all $x,y\in X$, which when combined with the preceding relation implies for all $k\geq 0$,

The relation in part (b), follows from inequality (6) by using Assumption 3 and by taking the total expectation. To show the other results in part (b), we apply Lemma 2. For this, we need to verify that all the conditions of Lemma 2 hold. Since $0<\gamma_{k}\leq\frac{2}{L}$, it follows $\eta\gamma_{k}(2-\gamma_{k}L)\geq 0$. Also, in view of $\eta\leq L$, we have $\eta\gamma_{k}(2-\gamma_{k}L)\leq 1$. Obviously, $\nu^{2}\gamma_{k}^{2}\geq 0$ for all $k$. Since Assumption 2(a) holds, we have $\sum_{k=0}^{\infty}\eta\gamma_{k}(2-\gamma_{k}L)=\infty$ and $\sum_{k=0}^{\infty}\eta\gamma_{k}^{2}<\infty$. Furthermore, since $\gamma_{k}\to 0$, we have

Hence, the conditions of Lemma 2 hold and the stated results follow. ∎

Lemma 4 will be employed in developing our adaptive stepsize schemes. Before proceeding, we make the following comment regarding the lemma.

Remark 1: The result in part (a) of Lemma 4 is similar to a result in , which was derived by requiring only the strong convexity of the function $f$. Here, we make the additional assumption that the gradients are Lipschitz continuous and this assumption gains relevance when we employ local random smoothing in Section V. Furthermore, our result depends on the expectation of gradient errors, $\mathsf{E}\!\left[\|w_{k}\|^{2}\right]$, with $w_{k}$ defined in (3). Note that, in contrast, the result in depends on the expectation of the subgradient norms, $\mathsf{E}\!\left[\|G(x,\xi)\|^{2}\right]$, where $G(x,\xi)\in\partial_{x}F(x,\xi)$.

III-B A recursive steplength scheme

A challenge associated with the implementation of diminishing steplength schemes lies in determining an appropriate sequence $\{\gamma_{k}\}$. The key result of this section is the motivation and introduction of a scheme that adaptively optimizes the steplength from iteration to iteration. Our adaptive scheme relies on the minimization of a suitably defined error function at each step. We start with the relation in part (b) of Lemma 4:

When the stepsize is further restricted so that $0<\gamma_{k}\leq\frac{1}{L}$, we have

Thus, for $0<\gamma_{k}\leq\frac{1}{L}$, inequality (7) yields

We now use relation (8) to develop an adaptive stepsize procedure. Loosely speaking for the moment, let us view the quantity $\mathsf{E}\!\left[\|x_{k+1}-x^{*}\|^{2}\right]$ as an error $e_{k+1}$ of the method arising from the use of the stepsize values $\gamma_{0},\gamma_{1},\ldots,\gamma_{k}$. Also, consider the worst case error which is the case when (8) holds with equality. Thus, in the worst case, the error satisfies the following recursive relation:

Then, it seems natural to investigate if the stepsizes $\gamma_{0},\gamma_{1}\ldots,\gamma_{k}$ can be selected so as to minimize the error $e_{k+1}$. It turns out that this can indeed be achieved and minimizing the error $e_{k+2}$ at the next iteration can also be done by selecting $\gamma_{k+1}$ as a function of only the most recent stepsize $\gamma_{k}$. To formalize the above discussion, we define real-valued error functions $e_{k}(\gamma_{0},\ldots,\gamma_{k-1})$ as follows:

where $e_{0}$ is a positive scalar, $\eta$ is the strong convexity parameter and $\nu^{2}$ is the upper bound for the second moments of the error norms $\|w_{k}\|$.

In what follows, we consider the sequence $\{\gamma^{*}_{k}\}$ given by

We often abbreviate $e_{k}(\gamma_{0},\ldots,\gamma_{k-1})$ by $e_{k}$ whenever this is unambiguous. We show that the stepsizes $\gamma_{i}$, $i=0,\ldots,k-1,$ minimize the errors $e_{k}$ over an $(0,\frac{1}{L}]^{k}$, where $L$ is the Lipschitz constant. In particular, we have the following result.

Let $e_{k}(\gamma_{0},\ldots,\gamma_{k-1})$ be defined as in (9), where $e_{0}>0$ is such that $\frac{\eta}{2\nu^{2}}\,e_{0}\leq\frac{1}{L}$, with $L$ being the Lipschitz constant for the gradients of $f$. Let the sequence $\{\gamma^{*}_{k}\}$ be given by (10)–(11). Then, the following hold:

For each $k\geq 1$, the vector $(\gamma_{0}^{*},\gamma_{1}^{*},\ldots,\gamma_{k-1}^{*})$ is the minimizer of the function $e_{k}(\gamma_{0},\ldots,\gamma_{k-1})$ over the set

(a) We use induction on $k$ to prove our result. Note that the result holds trivially for $k=0$ from (10). Next, assume that we have $e_{k}(\gamma_{0}^{*},\ldots,\gamma_{k-1}^{*})=\frac{2\nu^{2}}{\eta}\,\gamma_{k}^{*}$ for some $k$, and consider the case for $k+1$. By the definition of the error $e_{k}$ in (9), we have

where the second equality follows by the inductive hypothesis. Hence,

where the last equality follows by the definition of $\gamma^{*}_{k+1}$ in (11).

(b) We now show that $(\gamma^{*}_{0},\gamma_{1}^{*},\ldots,\gamma_{k-1}^{*})$ minimizes the error $e_{k}$ for all $k\geq 1$. We again use mathematical induction on $k$. By the definition of the error $e_{1}$ and the relation $e_{1}(\gamma_{0}^{*})=\frac{2\nu^{2}}{\eta}\gamma_{1}^{*}$ shown in part (a), we have

Using $\gamma_{1}^{*}=\gamma_{0}^{*}\left(1-\frac{\eta}{2}\gamma_{0}^{*}\right)$, we obtain

where the last equality follows from $e_{0}=\frac{2\nu^{2}}{\eta}\,\gamma_{0}^{*}.$ Thus, we have

Under the inductive hypothesis, we have $e_{k}\geq e_{k}^{*}$. Using this, the relation $e_{k}^{*}=\frac{2\nu^{2}}{\eta}\gamma_{k}^{*}$ of part (a) and the definition of $\gamma_{k+1}^{*}$, we obtain

Now, we proceed by induction on $k$. For $k=1$, we have

From the definition of $e_{k}$ in (9) we can see that

Finally, we consider the partial derivative of $e_{k+1}$ with respect to $\gamma_{k}$, for which we have

III-C Convergence theory

We next show that the proposed RSA approximation scheme discussed in Section III-B leads to a convergent algorithm. We prove this in a more general setting for a stepsize with a form similar to that seen in constructing the optimal choice. The following proposition holds for any stepsize of a form similar to the optimal scheme of (11).

Let Assumptions 1 and 3 hold. Let the function $f$ be differentiable over the set $X$ with Lipschitz gradients and the optimal solution set of problem (1) be nonempty. Assume that the stepsize sequence $\{\gamma_{k}\}$ is generated by the following self-adaptive scheme:

where $c>0$ is a scalar and the initial stepsize is such that $0<\gamma_{0}<\frac{1}{c}$. Then, the sequence $\{x_{k}\}$ generated by algorithm (3) converges almost surely to a random point that belongs to the optimal set.

We employ Proposition 1. To apply this proposition, it suffices to verify that Assumption 2 holds. First we show that $\sum_{i=0}^{\infty}{\gamma_{i}}=\infty$. From (14) we obtain

By dividing both sides by $\left(\prod_{i=1}^{k}\gamma_{i}\right)$, it follows that

Since $\gamma_{0}\in(0,\frac{1}{c})$, from (14) it follows that $\{\gamma_{k}\}$ is positive nonincreasing sequence. Therefore, the limit $\lim_{k\to\infty}\gamma_{k}$ exists and it is less than $\frac{1}{c}$. Thus, by taking the limit in (14), we obtain $\lim_{k\to\infty}\gamma_{k}=0$. Then, by taking limits in (15), we further obtain

To arrive at a contradiction suppose that $\sum_{i=0}^{\infty}{\gamma_{i}}<\infty$. Then, there is an $\epsilon\in(0,1)$ such that for $j$ sufficiently large, we have

Since $\prod_{i=j}^{k}(1-c\gamma_{i})\geq 1-c\sum_{i=j}^{k}\gamma_{i}$ for all $j<k$, by letting $k\rightarrow\infty$, we obtain for all $j$ sufficiently large,

This, however, contradicts the fact $\lim_{k\rightarrow\infty}\prod_{i=0}^{k}(1-c\gamma_{i})=0.$ Therefore, we conclude that $\sum_{i=0}^{\infty}{\gamma_{i}}=\infty$.

Now we show that $\sum_{i=0}^{\infty}{\gamma_{i}}^{2}<\infty$. From (14) we have

Summing the preceding relations, we obtain

By taking limits and recalling that $\lim_{k\to\infty}\gamma_{k}=0$, we obtain

Assumption 3 and relation $\sum_{i=0}^{\infty}{\gamma_{i}}^{2}<\infty$ yield $\sum_{k=0}^{\infty}\gamma_{k}^{2}\mathsf{E}\!\left[\|w_{k}\|^{2}\mid\mathcal{F}_{k}\right]<\infty$. Hence, Assumption 2 holds. ∎

Note that Proposition 3 applies to algorithm (3) with the stepsize sequence $\{\gamma_{k}^{*}\}$ generated by the recursive scheme (11). Thus, we immediately have the following corollary.

Let Assumptions 1 and 3 hold. Let the function $f$ be differentiable over the set $X$ with Lipschitz gradients with constant $L>0$ and strongly convex with parameter $\eta>0$. Let the stepsize sequence $\{\gamma_{k}^{*}\}$ be generated by the recursive scheme (11) with $e_{0}=\mathsf{E}\!\left[\|x_{0}-x^{*}\|^{2}\right]$. If $\frac{\eta}{2\nu^{2}}\mathsf{E}\!\left[\|x_{0}-x^{*}\|^{2}\right]<\frac{1}{L},$ then the sequence $\{x_{k}\}$ generated by algorithm (3) converges almost surely to the unique optimal solution $x^{*}$ of problem (1).

The existence and uniqueness of the optimal solution follows by the strong convexity assumption. Almost sure convergence follows by Proposition 3. ∎

Note that when the set $X$ is bounded, in Proposition 1 we may use $e_{0}=\max_{x,y\in X}\|x-y\|^{2}$ and the results will hold as long as $\frac{\eta}{2\nu^{2}}\max_{x,y\in X}\|x-y\|^{2}<\frac{1}{L}.$

In the following, we discuss a recursive stepsize for algorithm (3) as applied to a nonsmooth but strongly convex function $f(x)=\mathsf{E}\!\left[F(x,\xi)\right]$. Let $G(x,\xi)$ be a subgradient vector of $F(x,\xi)$ with respect to $x$, i.e., $G(x,\xi)\in\partial F(x,\xi)$. Assume that there is a positive number $M$ such that

We have the following convergence result, which obviously also holds for smooth problems.

Consider problem (1) and let Assumption 1 hold. Also, let the set $X$ be compact and the function $f$ be strongly convex over $X$ with constant $\eta$. Assume that there is a scalar $M>0$ such that $\mathsf{E}\!\left[\|G(x,\xi)\|^{2}\right]\leq M^{2}$ for all $x\in X$. Consider the following algorithm:

where $x_{0}\in X$ is a random initial point independent of $\{\xi_{k}\}$ and $\gamma_{k}$ is a (deterministic) stepsize. Consider the self-adaptive stepsize sequence $\{\gamma_{k}^{*}\}$ defined by

where $D=\max_{x,y\in X}\|x-y\|$. Assuming that $\frac{\eta D^{2}}{M^{2}}<\frac{1}{2}$, we have

The proof is based on verifying that, for the algorithm in (16), Proposition 2 holds, where $2\nu^{2}$ is replaced by $M^{2}$ and $e_{0}=D^{2}$. Then, the rest of the proof is similar to that of Proposition 1. ∎

IV A cascading steplength stochastic approximation scheme

In Section III, we presented a stochastic approximation scheme in which the sequence of steplengths is determined via a recursion that relies on optimizing the error estimates. A key benefit of such a recursion is that the steplength choice is not left to the user. In this section, we introduce an alternate avenue for specifying steplengths that also considers a diminishing steplength framework but uses a markedly different approach for determining the steplength. In particular, the scheme relies on reducing the steplength at a set of epochs while the steplengths are maintained as constant between these epochs. The details of this stochastic approximation scheme (called the cascading steplength stochastic approximation (CSA) scheme) are presented in Section IV-A while convergence theory is provided in Section IV-B.

Our technique is based on the properties derived from problems possessing strongly convex objectives. Specifically, we obtain the following result from the inequality in Lemma 4 when the stepsize is maintained as constant.

Let Assumptions 1 and 3 hold. Also, let $f$ be differentiable over the set $X$ with Lipschitz gradients with constant $L>0$ and strongly convex with constant $\eta>0$. Let the sequence $\{x_{k}\}$ be generated by (3) with constant stepsize $\gamma_{k}=\gamma$ for all $k\geq 0$, where $\gamma\in(0,\frac{2}{L})$. Then, we have

where $q(\gamma)=1-\eta\gamma(2-\gamma L)$ and $x^{*}$ is the optimal solution of problem (1).

Follows from the inequality in part (b) of Lemma 4. ∎

From inequality (17), we obtain the following relation

where the expected distance $\mathsf{E}\!\left[\|x_{k}-x^{*}\|^{2}\right]$ is bounded by the sum of two error terms:

Transient error: The transient error, given by $q(\gamma)^{k}\mathsf{E}\!\left[\|x_{0}-x^{*}\|^{2}\right]$, decays to zero as $k\to\infty.$ In effect, the contractive nature of this error, as arising from $q(\gamma)<1$, ensures that the transient error can be reduced to an arbitrarily small level.

Persistent error: The persistent error, given by ${\frac{\gamma^{2}\nu^{2}}{1-q(\gamma)}}$, is invariant to increasing the number of iterations, denoted by $k$. Its reduction, as we proceed to show, necessitates reducing $\gamma.$

Our cascading steplength scheme basically requires specifying a rule for deciding at what iteration to decrease the steplength and to what extent it should be decreased. The iterations during which the stepsize is kept fixed is referred to as a constant steplength regime or just a regime. Given the two error terms, our scheme can be loosely represented as an infinite sequence of regimes of finite duration. In fact, we proceed to show that the duration of the regimes is an increasing function. Entering a new regime is marked by a reduction in the steplength. In fact, since a finite reduction in the steplength occurs between consecutive regimes, the steplength sequence would naturally converge to zero if there is an infinite number of the regimes. Suppose one is at the beginning of the $t$th regime, where the steplength is $\gamma_{t}$ and the current iteration number is $K$. The steplength $\gamma_{t}$ is maintained constant during regime $t$. Furthermore, suppose that at the beginning of the $t$th regime, the transient error is greater than the persistent error for $\gamma_{t}$, i.e., $\mathsf{E}\!\left[\|x_{K}-x^{*}\|^{2}\right]>\frac{\gamma_{t}^{2}\nu^{2}}{1-q(\gamma_{t})}$. Since $0<q(\gamma_{t})<1$, $\mathsf{E}\!\left[\|x_{K}-x^{*}\|^{2}\right]$ decreases when multiplied with $q(\gamma_{t})^{k}$ for $k\geq 0$. The larger $k$, the smaller $q(\gamma_{t})^{k}\mathsf{E}\!\left[\|x_{K}-x^{*}\|^{2}\right]$, so there exists $k>0$ for which $q(\gamma_{t})^{k}\mathsf{E}\!\left[\|x_{K}-x^{*}\|^{2}\right]$ will drop and remain below the persistent error $\frac{\gamma_{t}^{2}\nu^{2}}{1-q(\gamma_{t})}$. We let $K_{t}$ be the index $k$ just before this drop takes place, i.e., $K_{t}$ is the largest $k$ for which the following inequality holds:

Therefore, $K_{t}$ specifies the duration of regime $t$, during which the stepsize is fixed at $\gamma_{t}$.

The next question is how one should go about reducing the persistent error. We observe through the next result that by reducing $\gamma_{t}$, the persistent error does indeed reduce.

Consider the persistent error given by $P(\gamma)=\frac{\gamma^{2}\nu^{2}}{1-q(\gamma)}$, where $q(\gamma)=1-\eta\gamma(2-\gamma L)$ and $\gamma\in(0,\frac{2}{L})$. Then, this error is an increasing function of $\gamma.$

By using $q(\gamma)=1-\eta\gamma(2-\gamma L)$, for the persistent error we obtain $P(\gamma)=\frac{\gamma\nu^{2}}{\eta(2-\gamma L)}$. Therefore, the derivative of the persistent error with respect to $\gamma$ is given by $P^{\prime}(\gamma)=\frac{\nu^{2}}{\eta}\,\frac{2}{(2-\gamma L)^{2}}>0$ for all $\gamma\neq\frac{2}{L}$. ∎

Therefore, when $\gamma_{t}$ is reduced to $\gamma_{t+1}$, the persistent error does indeed reduce. This drop in steplength is referred to as the cascading step and marks the commencement of a new regime. As earlier, in this regime, the persistent error will be smaller than the transient error and the process of determining $K_{t+1}$ can be repeated. Therefore, we may view the scheme as a diminishing steplength scheme where the steplength is reduced at a sequence of time epochs and between these epochs, it is maintained constant.

We now proceed to describe the scheme more formally. It can be viewed as having two stages, of which the second stage repeats infinitely often in a consecutive fashion. The first of these is an initialization phase. We assume throughout that the constraint set $X$ is bounded, so that $\mathsf{E}\!\left[\|x_{0}-x^{*}\|^{2}\right]\leq D^{2}$ with $D=\max_{x,y\in X}\|x-y\|$. Next, we describe each of the stages in cascading scheme in some detail.

Cascading steplength stochastic approximation (CSA) scheme:

Finally, we exit this phase by defining $\bar{K}_{-1}=0$, setting $t=0$, and going to Phase IIt.

Constant steplength phase (Phase IIt): Define $\bar{K}_{t}=\sum_{j=0}^{t}K_{t}$. For the iteration indices $k$ with $k\in\{\bar{K}_{t-1}+1,\ldots,\bar{K}_{t}\}$, the stepsize is kept constant and equal to $\gamma_{t}$, i.e.,

Then, we increase $t$ by setting $t=t+1$, reduce the stepsize by letting $\gamma_{t}\triangleq\gamma_{t-1}\theta$, compute $q_{t}=q(\gamma_{t})$ and determine the integer $K_{t}$ as follows:

We then repeat phase IIt until the number $k$ of iterations (i.e., gradient steps) exceeds a pre-specified threshold, in case of which the algorithm terminates.

We provide a graphical representation of these phases in Figure 1 where the circles around $x^{*}$ represent thresholds beyond which the transient error is less than the persistent error. For instance, in Figure 1 (plot to the left), phase II0 requires $K_{0}$ steps to reach the first circle. Once, the steplength is reduced by a factor $\theta$, the phase II1 commences and requires $K_{1}$ steps to reach an analogous error threshold where the transient error is equal to the persistent error; this is illustrated in Figure 1 (plot in the center). Finally, phase II2 requires $K_{2}$ to reach an even smaller level of persistent error, as depicted in Figure 1 (plot to the right). Note that whenever the steplength is reduced, the persistent error is immediately reduced (Lemma 5). Thus, the stepsize is essentially a piecewise constant decreasing function of the iteration index $k$.

The next result establishes the correctness of the cascading scheme by showing that $K_{t}$ in Phase IIt is finite, so the scheme is well defined.

Let Assumptions 1 and 3 hold. Also, let $f$ be differentiable over the set $X$ with Lipschitz gradients with constant $L>0$ and strongly convex with constant $\eta>0$. Assume that the set $X$ is compact and let $D=\max_{x,y\in X}\|x-y\|$. Then, $K_{t}$ is finite for all $t\geq 0$.

We use induction on $t$ to show that $K_{t}$ is well defined and for all $t\geq 0$,

First note that, since $\gamma_{0}\in(0,\frac{2}{L})$ and the steplength $\gamma_{k}$ is non-increasing in $k$, we have $q(\gamma_{t})\in(0,1)$ for all $t\geq 0$.

For $t=0$, from Proposition 5 and the boundedness of the set $X$ we have

where we use the fact $\bar{K}_{0}=K_{0}$ (see Phase IIt for $t=0$).

Now assume that $K_{t}$ is well defined and relation (22) holds for $t$. We next show that $K_{t+1}$ is also well defined and relation (22) holds for $t+1$. Note that the steplength $\gamma_{k}=\gamma_{t+1}$ is used for $k\geq\bar{K}_{t}$. From Proposition 5 where we replace $x_{0}$ with $x_{\bar{K}_{t}}$, by replacing $\gamma$ by $\gamma_{t+1}$ letting $q_{t+1}=q(\gamma_{t+1})$, we have for $k\geq\bar{K}_{t}$,

By inductive hypothesis relation (22) holds, so it follows

Consequently, $K_{t+1}$ is defined as the largest positive integer $k$ for which term 1 is strictly greater than term 2, i.e.,

(see the definition of $K_{t}$ in (21)). Noting that $\bar{K}_{t+1}=\bar{K}_{t}+K_{t+1}$ (see Phase IIt) and $q_{t+1}^{k}2^{t+1}\left(\prod_{j=0}^{t}q_{j}^{K_{j}}\right)D^{2}>\frac{\gamma_{t+1}^{2}\nu^{2}}{1-q_{t+1}}$ for $k=\bar{K}_{t}+1,\ldots,\bar{K}_{t+1}$, from (24) with $k=\bar{K}_{t+1}$, we obtain

thus showing relation (22) for $t+1$ and completing the proof. ∎

The transient and persistent error trajectories are illustrated in in Figure 2 for a problem discussed later in Section VI-A1. In Figure 2a, the transient and persistent terms of the error are plotted. The persistent error, as expected, is a piecewise constant decreasing function of the iteration count with the jumps occurring whenever the steplengths are reduced. The transient error is a plot of $q_{t}^{k}2^{t}\prod_{j=0}^{t-1}q_{j}^{K_{j}}D^{2}$ with respect to $k$. This function is a decreasing function when $k\in\{\bar{K}_{t-1},\ldots,\bar{K}_{t}-1\}.$ As soon as $k=\bar{K}_{t}$, in the transient error the factor $2^{t}$ is replaced with $2^{t+1}$, leading to the increase in transient error at that juncture. The total error, which is the summation of two terms, is showed in Figure 2b.

Remark on choice of $\theta$: Recall that $\theta$ specifies the rate at which the steplength is dropped over consecutive steps in the cascading scheme. It can be readily observed from the bounds derived on $K_{t}$ that if $\theta\to 1$, then $K_{t}\to 0$ thus implying that the steplength is kept constant for a very short period. This is intuitive since a conservative drop in steplengths would imply that these drops have to occur more frequently to ensure that the sequence is driven to zero. Conversely, if $\theta\to 0$, then $K_{t}$ can grow to be quite large.

IV-B Global convergence theory

In this section, we prove that algorithm (3) using the cascading steplength scheme is indeed convergent to the optimal solution of problem (1).

Let $q(\gamma)=1-2\eta\gamma+\eta L\gamma^{2}$ and let $\eta<L$. Then, we have

Let $r(\gamma)=\frac{-\ln(q(\gamma))}{\gamma}$. Note that the function $q(\gamma)=1-2\eta\gamma+\eta L\gamma^{2}$ is nonnegative for all $\gamma$ since $0<\eta\leq L$. Furthermore $q(\gamma)<1$ for $\gamma<\frac{2}{L}$. Thus, $r(\gamma)>0$ for $0<\gamma<\frac{2}{L}$. We next show that $r(\gamma)$ is bounded from above as stated. To show that the sequence is bounded, we employ the Taylor expansion of $\ln(q(\gamma))$. First, we write

Noting that $\beta(\gamma)=1-q(\gamma)\in(0,1)$, we then use the fact $\ln(1-x)=-\sum_{k=1}^{\infty}\frac{x^{k}}{k}$ for $|x|<1$, and obtain

Using $\beta(\gamma)\leq 2\eta\gamma$, we further obtain

The relation for the limit is obtained by applying L’Hôpital’s rule, as follows:

Let Assumptions 1 and 3 hold. Also, let $f$ be differentiable over the set $X$ with Lipschitz gradients with constant $L>0$ and strongly convex with constant $\eta>0$, where $L>\eta$. Assume that the set $X$ is compact and let $D=\max_{x,y\in X}\|x-y\|$. Let the sequence $\{x_{k}\}$ be generated by algorithm (3) and cascading steplength scheme with $\gamma_{0}\in\left(0,\frac{2}{L}\right)$ and $\theta\in(0,1)$. Then, $\{x_{k}\}$ converges almost surely to the unique optimal solution of problem (1).

The result will follow from Proposition 1 provided we verify that Assumption 2 holds, i.e., $\sum_{k=0}^{\infty}\gamma_{k}=\infty$ and $\sum_{k=0}^{\infty}\gamma_{k}^{2}<\infty$. According to Phase IIt of the cascading scheme, we have $\gamma_{k}=\gamma_{t}$ for $k=\bar{K}_{t-1}+1,\ldots,\bar{K}_{t}$ with $\gamma_{t}=\theta^{t}\gamma_{0}$ and $\bar{K}_{t}=\bar{K}_{t-1}+K_{t}$. Therefore

From the definition of $K_{t}$ in (21) we have

Relation (26) and the fact $\gamma_{t}=\theta^{t}\gamma_{0}$ (see Phase IIt of the cascading scheme) yield

Therefore, by multiplying and dividing by $\gamma_{0}\theta^{j}$, we obtain

Note that $q_{j}=1-2\eta\gamma_{0}\theta^{j}+\eta L(\gamma_{0}\theta^{j})^{2}$ with $\gamma_{0}\in(0,2/l)$ and $\theta\in(0,1)$. Thus, by Lemma 6 we have $\frac{-\ln(q_{j})}{\gamma_{0}\theta^{j}}\leq 2\eta L/(L-\eta)$, implying

Taking limits on both sides, we have that

The limit on the right can be simplified by substituting $q_{t}=1-2\eta\gamma_{0}\theta^{t}+\eta L\gamma_{0}^{2}\theta^{2t}$, leading to

implying that $\sum_{j=0}^{\infty}K_{j}\theta^{j}=\infty.$

It remains to show that $\sum_{t=0}^{\infty}{K_{t}\theta^{2t}}<\infty.$ From (25) and the fact $q_{j}\in(0,1)$ for all $j$, we have that

This allows for obtaining an upper bound on $K_{t}$, given by

The desired result will follow by the Cauchy root test, if we show that

By noting that $(K_{t}\theta^{2t})^{1/t}=\theta^{2}(K_{t})^{1/t}$, it suffices to use the upper bound on $K_{t}$ in (27). We proceed to analyze this bound, for which by letting $\beta(\gamma)=1-q(\gamma)$ and recalling that $q_{t}=q(\gamma_{t})$ we have

Noting that $\beta(\gamma)\in(0,1)$ for all $\gamma$ when $\eta<L$, we have $\ln(\beta(\gamma))<0$, implying

Since $\beta(\gamma)\in(0,1)$, the denominator can be expanded in Taylor series as follows:

Furthermore, since $\beta(\gamma_{t})=\eta\gamma_{t}(2-L\gamma_{t})$ and $\gamma_{t}=\gamma_{0}\theta^{t}$ with $\theta\in(0,1)$, we have $\gamma_{0}\theta^{t}\leq 1$ for $t$ large enough, implying $\beta(\gamma_{t})\geq\eta\gamma_{0}\theta^{t}$. Thus,

By combining (28) and (29), we obtain for $t$ large enough,

By recalling that $\lim_{t\to\infty}{t^{1/t}}=1$ and $\lim_{t\to\infty}{c^{1/t}}=1$ for any $c>0$, it follows that

We next examine the limit on the right hand side. Letting $a=-\ln(\theta/2)$ and $b=-\ln\left(\frac{\gamma_{0}^{2}\nu^{2}}{D^{2}}\right)$, we can write

Therefore, $\lim_{t\to\infty}K_{t}^{1/t}\leq\frac{1}{\theta},$ implying that

As a consequence, the Cauchy-root test is satisfied and $\sum_{t=0}^{\infty}K_{t}\theta^{2t}<\infty.$ ∎

V Addressing nondifferentiability through Local Randomized Smoothing

In this section, we develop a smoothing approach for solving stochastic optimization problem with nonsmooth integrands. In Section V-A, given a nondifferentiable function $f(x)$, we introduce a smooth approximation for $f(x)$, denoted by ${\hat{f}}(x)$ by using local random perturbations. In Section V-B, we derive Lipschitz constants for the gradients associated with this smooth approximation when the smoothing is introduced via a uniform distribution. Finally, in Section V-C, the convergence theory of stochastic approximation schemes is examined in this modified regime.

We let $f$ be nondifferentiable and consider its approximation $\hat{f}$, defined by

We discuss our local smoothing technique under the assumption that the function $f$ has uniformly bounded subgradients over the set $X_{\epsilon}$, given as follows.

The subgradients of $f$ over $X_{\epsilon}$ are uniformly bounded, i.e., there is a scalar $C>0$ such that $\|g\|\leq C$ for all $g\in\partial f(x)$ and $x\in X_{\epsilon}$.

Assumption 4 is satisfied, for example, when $X$ is bounded. In the sequel, we let $\mathsf{E}\!\left[g(x+z)\right]$ denote the vector-valued integral of an element from the set of subdifferentials, which is given by

The following lemma presents properties of the randomized technique (30) with an arbitrary local random distribution over a ball. It states that, under the boundedness of the subgradients of $f$, the set $\mathsf{E}\!\left[g(x+z)\right]$ defined above is a singleton. In particular, the lemma shows that $\hat{f}$ is convex and differentiable approximation of $f$.

$\hat{f}$ is convex and differentiable over $X$, with gradient

where the vector $\mathsf{E}\!\left[g(x+z)\right]$ is as defined in (31). Furthermore, $\|\nabla\hat{f}(x)\|\leq C$ for all $x\in X$.

$f(x)\leq\hat{f}(x)\leq f(x)+\epsilon C$ for all $x\in X$.

(b) By definition of random vector $z$, it has zero mean, i.e., $\mathsf{E}\!\left[x+z\right]=x$, so that $f(\mathsf{E}\!\left[x+z\right])=f(x)$. Therefore, by Jensen’s inequality and the definition of $\hat{f}$, we have

To show relation $\hat{f}(x)\leq f(x)+\epsilon C$, we use the subgradient inequality for $f$, which in particular implies that, for every $\bar{x}\in X_{\epsilon}$ and $g\in\partial f(\bar{x})$, we have

Since $\bar{x}\in X_{\epsilon}$, we have $\bar{x}=x+z$ for some $x\in X$ and $z$ with $\|z\|\leq\epsilon$. Using this and the subgradient boundedness, from the preceding relation we obtain

Thus, by taking the expectation, we get $\hat{f}(x)=\mathsf{E}\!\left[f(x+z)\right]\leq f(x)+\epsilon C$ for all $x\in X.$ ∎

V-B Smoothing via random variables with uniform distributions

In this subsection, we consider a local smoothing technique wherein $z$ is generated via a uniform distribution. Other distributions may also work such as normal, considered in . However, distributions with finite support seem more appropriate for capturing local behavior of a function, as well as to deal with the problems where the function itself has a restricted domain. Our choice to work with a uniform distribution is due to the uniform distribution lending itself readily for computation of resulting Lipschitz constant and for assessment of the growth of the Lipschitz constant with the size of the problem.

The key result of this section is an examination of the Lipschitz continuity of the gradients of the smooth approximation, particularly in terms of the rate that such a constant grows with problem size.

where $c_{n}=\dfrac{\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}$, and $\Gamma$ is the gamma function given by

The following lemma shows that $\hat{f}$ is convex and differentiable approximation of $f$ with Lipschitz gradients, where the Lipschitz constant for $\nabla\hat{f}$ is related to the norm bound for the subgradients of $f$.

where $\kappa=\frac{2}{\pi}$ if $n$ is even, and otherwise $\kappa=1$.

From Lemma 7(a) and relation (31), for any $x\in X$, there is a vector $g(z+x)$ such that $g(z+x)\in\partial f(x+z)$ a.s. and

where the last equality follows by letting $v=x+z$. Therefore, for any $x,y\in X$,

where the last inequality follows by using the boundedness of the subgradients of $f$ over $X_{\epsilon}$.

Now, we let $x,y\in X$ be arbitrary but fixed, and we estimate $\int_{X_{\epsilon}}|p{{}_{u}}(z-x)-p{{}_{u}}(z-y)|dz$ in (34). For this we consider the cases where $\|x-y\|>2\epsilon$ and $\|x-y\|\leq 2\epsilon$.

Case 1 ($\|x-y\|>2\epsilon$): For every $z$ with $\|z-x\|\leq\epsilon$, we have $\|z-y\|>\epsilon$, implying that $p{{}_{u}}(z-y)=0$, so that $\int_{\|z-x\|\leq\epsilon}|p{{}_{u}}(z-x)-p{{}_{u}}(z-y)|dz=1$. Likewise, for every $z$ with $\|z-y\|\leq\epsilon$, we have $p{{}_{u}}(z-x)=0$, implying

Since $2<\|x-y\|/\epsilon$, it follows that

It can be further seen that $\kappa\frac{n!!}{(n-1)!!}\geq 1$ for all $n\geq 1$, which combined with (37) and (34) yields the result.

Case 2 ($\|x-y\|\leq 2\epsilon$): We decompose the integral in (34) over several regions, as follows:

where $V_{S}$ denotes the volume of the set $S$.

Now we want to find an upper bound for $V_{S}$ in terms of $\|y-x\|$. Let $V_{cap}(d)$ denote the volume of the spherical cap with the distance $d$ from the center of the sphere. Therefore,

The volume of the $n$-dimensional spherical cap with distance $d$ from the center of the sphere can be calculated in terms of the volumes of $(n-1)$-dimensional spheres, as follows:

with $c_{n}=\dfrac{\pi^{n/2}}{\Gamma(\frac{n}{2}+1)}$ for $n\geq 1$. We have for $d\in[0,\epsilon]$,

where $V_{cap}^{\prime}$ and $V_{cap}^{\prime\prime}$ denote the first and the second derivative, respectively, with respect to $d$. Hence, $V_{cap}(d)$ is convex over $[0,\varepsilon]$, and by the subgradient inequality we have