An optimal randomized incremental gradient method

Introduction

The basic problem of interest in this paper is the convex programming (CP) problem given by

and $\mu\geq 0$ is a given constant. Hence, the objective function $\Psi$ is strongly convex whenever $\mu>0$. For notational convenience, we also denote $f(x)\equiv\textstyle{\sum}_{i=1}^{m}f_{i}(x)$ and $L\equiv\textstyle{\sum}_{i=1}^{m}L_{i}$. It is easy to see that for some $L_{f}\geq 0$,

Throughout this paper, we assume subproblems of the form

are easy to solve. CP given in the form of (1.1) has recently found a wide range of applications in machine learning, statistics, and image processing, and hence becomes the subject of intensive studies during the past few years.

Stochastic (sub)gradient descent (SGD) (a.k.a. stochastic approximation (SA)) type methods have been proven useful to solve problems given in the form of (1.1). SGD was originally designed to solve stochastic optimization problems given by

Note however, that there is a significant gap on the complexity bounds between SGDs and deterministic FOMs if $f_{i}$’s are smooth convex functions. For the sake of simplicity, let us focus on the strongly convex case when $\mu>0$ and let $x^{*}$ be the optimal solution of (1.1). In order to find a solution $\bar{x}\in X$ s.t. $\|\bar{x}-x^{*}\|^{2}\leq\epsilon$, the total number of gradient evaluations for $f_{i}$’s performed by optimal FOMs can be bounded by

which was first achieved by the well-known Nesterov’s accelerated gradient method Nest83-1 ; Nest04 , see also relevant extensions in Nest13-1 ; BecTeb09-2 ; tseng08-1 . On the other hand, a direct application of optimal SGDs to the aforementioned stochastic optimization reformulation of (1.1) would yield an

iteration complexity bound on the number of gradient evaluations for $f_{i}$’s, which was first achieved by the accelerated stochastic approximation method (Lan10-3 ; GhaLan12-2a ; GhaLan13-1 ). Here $\sigma>0$ denotes variance of the stochastic gradients. Clearly, the latter bound is significantly better than the one in (1.7) in terms of its dependence on $m$, but much worse in terms of its dependence on accuracy $\epsilon$ and a few other problem parameters (e.g., $L$ and $\mu$).

It should be noted that the optimality of (1.8) for general stochastic programming (1.6) does not preclude the existence of more efficient algorithms for solving (1.1), because (1.1) is a special case of (1.6) with finite support $\Xi$. Last few years have seen very active and fruitful research in this field (e.g., SchRouBac13-1 ; JohnsonZhang13-1 ; DefBacLac14-1 ; ShaZhang15-1 ; Yuchen14 ). In particular, Schmidt, Roux and Bach SchRouBac13-1 presented a stochastic average gradient (SAG) method, which recursively computes an estimator of $\nabla f$ by aggregating the gradient of a randomly selected $f_{i}$ with some other previously computed gradient information. They proved that the complexity of SAG is bounded by ${\cal O}\left((m+L/\mu)\log\tfrac{1}{\epsilon}\right)$, see also Johnson and Zhang JohnsonZhang13-1 and Defazio et al. DefBacLac14-1 for similar complexity results for solving (1.1). In a related but different line of research, Shalev-Shwartz and Zhang ShaZhang15-1 studied a special class of CP problems given in the form of (1.1) with $f_{i}(x)$ given by $\phi_{i}(a_{i}^{T}x)$, where $a_{i}$ denotes an affine mapping. Under the assumption that $\omega(x)=\|x\|^{2}_{2}$, they presented an accelerated stochastic dual coordinate ascent (A-SDCA) method, obtained by properly restarting a stochastic coordinate ascent method in ShaZhang13-1 applied to the dual of (1.1). Shalev-Shwartz and Zhang show that the iteration complexity of this method can be bounded by ${\cal O}\left\{\left(m+\sqrt{\tfrac{mL}{\mu}}\right)\log\tfrac{1}{\epsilon}\right\}.$ However, each iteration of A-SDCA requires, instead of the computation of $\nabla f_{i}$, the solution of a subproblem given in the form of

where $\phi_{i}^{*}$ denotes the conjugate function of $\phi_{i}$. Moreover, these methods were also designed for solving a more special class of problems than (1.1). More recently, Lin, Lu, and Xiao LinLuXiao14-1 proposed to apply the accelerated coordinate descent methods by Nesterov Nest10-1 , and Fercoq and Richtárik’s fr13 to obtain similar results for solving these “regularized empirical loss functions” as in ShaZhang15-1 . Zhang and Xiao Yuchen14 had also obtained similar results by using different stochastic primal-dual coordinate decomposition techniques.

In this paper, we focus on randomized incremental gradient methods that can access the first-order information of only one randomly selected smooth component $f_{i}$ at each iteration (see Bertsekas Bertsekas10-1 for an introduction to incremental gradient methods). It should be noted that while the algorithms in SchRouBac13-1 ; JohnsonZhang13-1 ; DefBacLac14-1 belong to incremental gradient methods, generally speaking, the dual coordinate algorithms in LinLuXiao14-1 ; ShaZhang15-1 ; Yuchen14 cannot be considered as incremental gradient methods because they require the solutions of a different subproblem rather than the computation of the gradient of $f_{i}$. The previous attempts to improve the complexity of the existing incremental gradient methods, e.g., based on the extrapolation idea in Nesterov Nest83-1 , however, turned out to be tricky and unsuccessful, see Section 1.2 of Bertsekas Bertsekas10-1 and Section 5 of Agarwal and Bottou AgrBott14-1 for more discussions. Another important yet unresolved issue is that there does not exist a valid lower complexity bound for randomized incremental gradient methods in the literature. Hence, it remains unknown what would be the best possible performance that one can expect for these types of methods. Regarding this question, Agarwal and Bottou AgrBott14-1 recently suggested a lower complexity bound for solving problems given in the form of (1.1). However, as pointed out by them in a recent ISMP talk in 2015, the lower complexity bound in AgrBott14-1 is deterministic by construction, and hence cannot be used to justify the optimality or suboptimality for the randomized incremental gradient methods in SchRouBac13-1 ; JohnsonZhang13-1 ; DefBacLac14-1 or dual coordinate methods in LinLuXiao14-1 ; ShaZhang15-1 ; Yuchen14 .

Our contribution in this paper mainly lies on the following several aspects. Firstly, we present a new class of deterministic FOMs, referred to as the primal-dual gradient (PDG) methods, which can achieve the optimal black-box iteration complexity in (1.7) for solving (1.1). The novelty of these methods exists in: 1) a proper reformulation of (1.1) as a primal-dual saddle point problem and 2) the incorporation of a new non-differentiable prox-function (or Bregman distance) based on the conjugate functions of $f_{i}$ in the dual space. As a consequence, we are able to show that the PDG method covers a variant of the well-known Nesterov’s accelerated gradient method as a special case. In particular, the computation of the gradient at the extrapolation point of the accelerated gradient method is equivalent to a primal prediction step combined with a dual ascent step (employed with the aforementioned dual prox-function) in the PDG method. While it is often difficult to interpret Nesterov’s method, the development of the PDG method allows us to view this method as a natural iterative buyer-supplier game. Such a game-theoretic view of the accelerated gradient method seems to be new in the literature. In fact, the obtained complexity results for the PDG method are slightly stronger than the one in (1.7) and those in Nest83-1 ; Nest04 for Nesterov’s accelerated gradient method, because a stronger primal-dual termination criterion has been used in our analysis.

Secondly, we develop a randomized primal-dual gradient (RPDG) method, which is an incremental gradient method using only one randomly selected component $\nabla f_{i}$ at each iteration. A variant of PDG, this algorithm incorporates an additional dual prediction step before performing the primal descent step (with a properly defined primal prox-function). We prove that the number of iterations (and hence the number of gradients) required by RPDG is bounded by

both in expectation and with high probability. The complexity bounds of the RPDG method are established in terms of not only the distance from the iterate $x^{k}$ to the optimal solution, but also the primal optimality gap based on the ergodic mean of the iterates. In comparison with the accelerated stochastic dual coordinate ascent method in ShaZhang15-1 , RPDG deals with a wider class of problems and can be applied to the cases when $f_{i}$’s involve a more complicated composite structure (see examples in Bertsekas10-1 ) and/or a more general regularization term $\omega$ that is strongly convex with respect to an arbitrary norm (see open problems in Section 7 of ShaZhang15-1 ). Moreover, each iteration of RPDG only involves the computation $\nabla f_{i}$, rather than the more complicated subproblem in (1.9), which sometimes may not have explicit solutions ShaZhang15-1 (e.g., the logistics regression problem). The RPDG method also admits an interesting game theoretic interpretation, implying that by properly incorporating randomization, the buyer and supplier can reach the equilibrium with possibly fewer price changes at the expense of more order transactions.

whenever the dimension $n$ is sufficiently large. This bound is obtained by carefully constructing a special class of separable quadratic programming problems and tightly bounding the expected distance to the optimal solution for any arbitrary distribution used to choose $f_{i}$ at each iteration. Comparing (1.10) with (1.11), we conclude that the complexity of the RPDG method is optimal if $n$ is large enough. To the best of our knowledge, this is the first time that such a lower complexity bound has been presented for randomized incremental gradient methods in the literature. As a byproduct, we also derived a lower complexity bound for randomized block coordinate descent methods by utilizing the separable structure of the aforementioned worst-case instances. These methods have been intensively studied recently, but a valid lower complexity bound is still missing in the literature.

Finally, we generalize RPDG for problems which are not necessarily strongly convex (i.e., $\mu=0$) and/or involve structured nonsmooth terms $f_{i}$. We show that for all these cases, the RPDG can save ${\cal O}(\sqrt{m})$ times gradient computations (up to certain logarithmic factors) in comparison with the corresponding optimal deterministic FOMs. In particular, we show that when both the primal and dual of (1.1) are not strongly convex, the total number of iterations performed by the RPDG method can be bounded by ${\cal O}(\sqrt{m}/\epsilon)$ (up to some logarithmic factors), which is ${\cal O}(\sqrt{m})$ times better, in terms of the total number of dual subproblems to be solved, than Nesterov’s smoothing technique Nest05-1 , Nemirovski’s mirror-prox method Nem05-1 , or Chambolle and Pock’s primal-dual method ChamPoc11-1 . It seems that this complexity result has not been obtained before in the literature.

It is worth mentioning a few relevant works to our development. The most two related ones are conducted independently by Dang and Lan DangLan14-1 , and Zhang and Xiao Yuchen14 . Both of these papers deal with randomized variants of the primal-dual method presented by Chambolle and Pock ChamPoc11-1 (see also extensions in CheLanOu13-1 ) for solving saddle point problems. Zhang and Xiao’s development Yuchen14 was based on a variant of the primal-dual method for solving strongly convex saddle point problems ChamPoc11-1 . They were able to show that a block-wise randomized version of the algorithm can achieve similar complexity as the A-SDCA method in ShaZhang15-1 . Since Zhang and Xiao’s algorithm targets for solving a similar class of problems and requires the solutions of a similar subproblem to ShaZhang15-1 , it appears that the aforementioned possible advantages of RPDG over A-SDCA are also applicable to the stochastic primal-dual coordinate method in Yuchen14 . Moreover, the complexity bound of Zhang and Xiao’s algorithm is only established in terms of the Euclidean distances of the iterate $x^{k}$, $y^{k}$ to the optimal solution. They did not deal with the convergence of the ergodic mean of iterates. On the other hand, Dang and Lan’s work was motivated by the observation in ChenHeYeYuan13-1 that a direct extension of the alternating direction method of multiplier (ADMM) does not converge for multi-block problems. Their work in DangLan14-1 then focuses on the non-strongly convex case and shows that a randomized primal-dual method, which is equivalent to a randomized pre-conditioned ADMM for linear constrained problems, does converge for multi-block problems. Without incorporating the aforementioned dual prediction step, the complexity obtained in DangLan14-1 is ${\cal O}(\sqrt{m})$ times worse than Chambolle and Pock’s method. Nevertheless, this is the first time that randomized algorithms for saddle point optimization with an ${\cal O}(1/\epsilon)$ complexity has been presented in the literature. More recently, close to the end of the preparation of this paper, we notice that Lin, Mairal, and Harchaoui LinMaiHar15-1 in a concurrent work presented a catalyst scheme that can be used to accelerate the SAG method in SchRouBac13-1 and thus possibly achieve the complexity bound in (1.10) (under the Euclidean setting). While their approach is an indirect one obtained by properly restarting SAG (or other “non-accelerated” first-order methods), the proposed randomized primal-dual gradient method is a direct approach with a “built-in” acceleration. Also none of these works DangLan14-1 ; Yuchen14 ; LinMaiHar15-1 discussed the lower complexity bound for randomized methods.

This paper is organized as follows. We first study the deterministic primal-dual method in Section 2. Section 3 is devoted to the design and analysis of the randomized primal-dual method for the strongly convex case, as well as the development of the lower complexity bound in (1.11). In Section 4, we generalize the RPDG method to different classes of CP problems that are not necessarily strongly convex. Important technical results and proofs of the main theorems in Sections 2 and 3 are provided in Section 5. Some brief concluding remarks are made in Section 6.

An optimal primal-dual gradient method

Our goal in this section is to present a novel primal-dual gradient (PDG) method for solving (1.1), which will also provide a basis for the development of the randomized primal-dual gradient methods in later sections. We establish the optimal convergence of this algorithm in terms of the primal-dual optimality gap under the assumption that the gradient of $f$ is computed at each iteration. We show that PDG generalizes one variant of the well-known Nesterov’s accelerated gradient method, and allows a natural game interpretation, and hence that the latter algorithm also admits a similar interpretation.

In this subsection, we discuss both primal and dual prox-functions (proximity control functions) in the primal and dual spaces, respectively.

where $\omega^{\prime}(x^{0})\in\partial\omega(x^{0})$ is an arbitrary subgradient of $\omega$ at $x^{0}$. Clearly, by the strong convexity of $\omega$, we have

Note that the prox-function $P(\cdot,\cdot)$ described above generalizes the Bregman’s distance in the sense that $\omega$ is not necessarily differentiable (see Breg67 ; AuTe06-1 ; BBC03-1 ; Kiw97-1 and references therein). Throughout this paper, we assume that the prox-mapping associated with $X$, $\omega$, and $h$, given by

where ${\cal N}_{X}$ denotes the normal cone of $X$ at $x^{1}$. Once such a $\omega^{\prime}(x^{1})$ satisfying the above relation is identified, we will use it as a subgradient when defining $P(x^{1},x)$ in the next iteration.

It is clear that $J_{f}$ is strongly convex with modulus $1/L_{f}$ w.r.t. $\|\cdot\|_{*}$. Therefore, we can define its associated dual prox-functions and dual prox-mappings as

for any $g^{0},g\in{\cal G}$. Again, $D_{f}$ may not be uniquely defined since $J_{f}$ is not necessarily differentiable. Instead of choosing $J^{\prime}_{f}\in\partial J_{f}$ similarly to $\omega^{\prime}$, we can explicitly specify such selections as will be discussed later in this paper.

The following simple result shows that the computation of the dual prox-mapping associated with $D_{f}$ is equivalent to the computation of $\nabla f$.

In view of the definition of $D_{f}$ in (2.5), we have

2 Primal-dual gradient method, Nesterov’s method, and a game interpretation

By the definition of $J_{f}$ in (2.4), problem (1.1) is equivalent to:

In order to implement the above primal-dual gradient method, it is more convenient to rewrite step (2.9) in a form involving the computation of gradient rather than the dual prox-mapping ${{\cal M}}_{{\cal G}}$. In order to do so, we shall specify explicitly the selection of the subgradient $J_{f}^{\prime}$ in (2.9). Denoting $\underline{x}^{0}=x^{0}$, we can easily see from $g^{0}=\nabla f(x^{0})$ that $\underline{x}^{0}\in\partial J_{f}(g^{0})$. Using this relation and letting $J_{f}^{\prime}(g^{t-1})=\underline{x}^{t-1}$ in $D_{f}(g^{t-1},g)$ (see (2.5)), we then conclude from Lemma 1 that for any $t\geq 1$, (2.9) reduces to

With the above selection of the dual prox-function, we can specialize the primal-dual gradient method as follows.

The above PDG method is related to the well-known Nesterov’s accelerated gradient (AG) method. Let us focus on a simple variant of the AG method that has been extensively studied in the literature (e.g., Nest04 ; tseng08-1 ; Lan10-3 ; GhaLan12-2a ; GhaLan13-1 ; GhaLan13-2 ). Given $(x^{t-1},\bar{x}^{t-1})\in X\times X$, this AG algorithm updates $(x^{t},\bar{x}^{t})$ by

for some $\lambda_{t}\in$. By (2.15) and (2.17), we have

Therefore, (2.15) is equivalent to (2.11) and (2.12) with $\tau_{t}=(1-\lambda_{t})/\lambda_{t}$ and $\alpha_{t}=\lambda_{t-1}(1-\lambda_{t})/\lambda_{t}$. Moreover, (2.16) is identical to (2.14)(and (2.10)), and (2.17) basically defines the output of the AG algorithm as an ergodic mean of the iterates $x^{t}$. We then conclude that the above variant of Nesterov’s AG method is a special case of Algorithm 2 (and Algorithm 1). It should be noted, however, that Algorithm 1 provides more flexibility in the specification of parameters, which will be used later in the development of the RPDG method. Moreover, the presentation of the PDG method helps us to reveal a natural game interpretation out of the intertwined and somehow mysterious updating of the three search sequences in the AG method.

Algorithm 1 is also closely related to Chambolle and Pock’s primal-dual method for solving saddle point problems ChamPoc11-1 , which explains the origin of its name. Two versions of primal-dual methods were discussed in ChamPoc11-1 . One is designed for solving general saddle point problems without assuming the strong convexity of $J_{f}$ and the other one is to deal with the case when $J_{f}$ is strongly convex by incorporating an additional extrapolation step. As pointed out in Remark 3 of ChamPoc11-1 , the rate of convergence for the latter primal-dual method is only suboptimal for solving (1.1) as it uses a weaker termination criterion. On the other hand, the PDG method does not involve any additional extrapolation steps and so it shares a similar scheme to the basic version of the primal-dual method in ChamPoc11-1 . Moreover, the original primal-dual methods in ChamPoc11-1 do not employ general prox-functions, which, as shown in Lemma 1, is crucial to relate the dual step (2.9) to the computation of the gradients. It should be noted that some recent extensions of the primal-dual method in CheLanOu13-1 ; DangLan14-1 ; ChamPoc14-1 indeed consider the incorporation of prox-functions, but restricted to problems without strong convexity. Hence, none of these earlier primal-dual methods can be viewed as a generalized accelerated gradient method.

3 Convergence properties of the primal-dual gradient method

Our goal in this subsection is to show that Algorithm 1 exhibits an optimal rate of convergence for solving problem (1.1). It is worth mentioning that our analysis significantly differs from the previous studies on optimal gradient methods and those on primal-dual methods for saddle point problems.

Given a pair of feasible solutions $\bar{z}=(\bar{x},\bar{g})$ and $z=(x,g)$ of (2.7), we define the primal-dual gap function $Q_{f}(\bar{z},z)$ by

It can be easily seen that $\bar{z}$ (resp., $z$) is an optimal solution of (2.7) if and only if $Q_{f}(\bar{z},z)\leq 0$ for any $z\in X\times{\cal G}$ (resp., $Q_{f}(\bar{z},z)\geq 0$ for any $\bar{z}\in X\times{\cal G}$). Therefore, one can assess the solution quality of $\bar{z}$ by the primal-dual optimality gap:

It should be noted that ${\rm gap}(\bar{z})$ may not be well-defined, for example, when $X$ is unbounded and $h$ is not strictly convex. In these cases, we can define a slightly modified primal-dual gap

for an arbitrary optimal solution $x^{*}$ of (1.1). Since $J_{f}$ is strongly convex, ${\rm gap}^{*}$ is well-defined.

The following result establishes some relationship between the primal optimality gap $\Psi(\bar{z})-\Psi^{*}$ and the above primal-dual optimality gaps.

Let $\bar{z}=(\bar{x},\bar{g})\in X\times\mathcal{G}$ be a given pair of feasible solutions of (2.7) and denote $\bar{g}^{*}=\nabla f(\bar{x})$. Also let $z^{*}=(x^{*},g^{*})$ be a pair of optimal solutions of (2.7). Then we have

It follows from the definitions of $\bar{g}^{*}$, ${\rm gap}^{*}$ and the gap function $Q_{f}$ that

Relation (2.22) follows directly from the definitions of ${\rm gap}^{*}$ and ${\rm gap}$.

Theorem 2.1 below describes the main convergence properties of the PDG method. More specifically, we provide in Theorem 2.1.a) a constant stepsize policy which works for the strongly convex case where $\mu>0$, and a different parameter setting that works for the non-strongly convex case with $\mu=0$ in Theorem 2.1.b). Note that for the strongly convex case, we estimate the solution quality for the iterates $x^{t},t=1,\ldots,k$, as well as that for their ergodic mean

for some $\theta_{t}\geq 0$, while only establishing the error bounds for $\bar{x}^{k}$ for the non-strongly convex case. We put the proof of Theorem 2.1 in Section 5 since it shares many basic elements with the convergence analysis of the RPDG method.

Let $x^{*}$ be an optimal solution of (1.1), $x^{k}$ and $\bar{x}^{k}$ be defined in (2.10) and (2.23), respectively.

Suppose that $\mu>0$ and that $\{\tau_{t}\}$, $\{\eta_{t}\}$, $\{\alpha_{t}\}$ and $\{\theta_{t}\}$ are set to

Suppose that $\{\tau_{t}\}$, $\{\eta_{t}\}$, $\{\alpha_{t}\}$ and $\{\theta_{t}\}$ are set to

Observe that when the algorithmic parameters are set to (2.24), by using an inductive argument, we can easily show that

In other words, $\underline{x}^{k}$ can be written as a convex combination of $x^{0},\ldots,x^{k-1}$ and hence $\underline{x}^{k}\in X$ for any $k\geq 1$. Similarly, when the algorithmic parameters are set to (2.28), we can show by using induction that

In view of the results obtained in Theorem 2.1, the primal-dual gradient method is an optimal method for convex optimization. In fact, the rates of convergence in (2.26), (2.27), (2.29) and (2.30) associated with the ergodic mean $\bar{z}^{k}$ have employed the primal-dual optimality gaps $g^{*}(\bar{z}^{k})$ and $g(\bar{z}^{k})$, which are stronger than the primal optimality gap $\Psi(\bar{x}^{k})-\Psi(x^{*})$ used in the previous studies for accelerated gradient methods. Moreover, whenever $X$ is bounded, the primal-dual optimality gap $g(\bar{z}^{k})$ gives us a computable online accuracy certificates to check the quality of the solution $\bar{z}^{k}$ (see lns11 ; GhaLan12-2a for some related discussions). Also observe that each iteration of the PDG method requires the computation of $\nabla f$, and hence all the $m$ components $\nabla f_{i}$. In the next section, we will develop a randomized PDG method that can possibly save the number of gradient evaluations for $\nabla f_{i}$ by utilizing the finite-sum structure of problem (1.1).

Randomized primal-dual gradient methods

In this section, we present a randomized primal-dual gradient (RPDG) method which needs to compute the gradient of only one randomly selected component function $f_{i}$ at each iteration. We show that RPDG can possibly achieve a better complexity than PDG in terms of the total number of gradient evaluations.

It is well-known that $\bar{z}\in Z\equiv X\times{\cal Y}$ is an optimal solution of (3.1) if and only if $Q(\bar{z},z)\leq 0$ for any $z\in Z$.

Since $J_{i},i=1,\ldots,m$, are strongly convex with modulus $\sigma_{i}=1/L_{i}$ w.r.t. $\|\cdot\|_{*}$, we can define their associated dual prox-functions and dual prox-mappings as

for any $y^{0}_{i},y_{i}\in{\cal Y}_{i}$. Accordingly, we define

Again, $D_{i}$ may not be uniquely defined since $J_{i}$ are not necessarily differentiable. However, we will discuss how to specify the particular selection of $J^{\prime}_{i}\in\partial J_{i}$ later in this subsection.

In other words, $\hat{y}_{i}^{t}$, $i=1,\ldots,m$, denote the prices that all the suppliers can possibly set up at iteration $t$. Then we can see that

In order to implement the above RPDG method, we shall explicitly specify the selection of the subgradient $J^{\prime}_{i_{t}}$ in the definition of the dual prox-mapping in (3.8). Denoting $\underline{x}^{0}_{i}=x^{0}$, $i=1,\ldots,m$, we can easily see from $y^{0}_{i}=\nabla f_{i}(x^{0})$ that $\underline{x}^{0}_{i}\in\partial f_{i}^{*}(y_{i}^{0})$, $i=1,\ldots,m$. Using this relation and letting $J_{i}^{\prime}(y_{i}^{t-1})=\underline{x}^{t-1}_{i}$ in the definition of $D_{i}(y_{i}^{t-1},y_{i})$ in (3.8) (see (3.4)), we then conclude from Lemma 1 (with $J_{f}=J_{i_{t}}$ and $D_{f}=D_{i_{t}}$) and (3.8) that for any $t\geq 1$,

Also, by the definition of $g^{t}$ and (3.9), we have

Incorporating these two ideas mentioned above, we present an efficient implementation of the RPDG method in Algorithm 4.

Clearly, the RPDG method is an incremental gradient type method since each iteration of this algorithm involves the computation of the gradient $\nabla f_{i_{t}}$ of only one component function. As shown in the following Subsection, such an randomization scheme can lead to significantly savings on the total number of gradient evaluations, at the expense of more primal prox-mappings.

2 The convergence of the RPDG algorithm

Our goal in this subsection is to describe the convergence properties of the RPDG method for the strongly convex case when $\mu>0$. Generalization of the RPDG method for the non-strongly convex case will be discussed in Section 4.

Suppose that $\{\tau_{t}\}$, $\{\eta_{t}\}$, and $\{\alpha_{t}\}$ in the RPDG method are set to

for some $\alpha\in(0,1)$. Then, for any $k\geq 1$, we have

where $\bar{x}^{k}=(\textstyle{\sum}_{t=1}^{k}\theta_{t})^{-1}\textstyle{\sum}_{t=1}^{k}(\theta_{t}x^{t})$ with $\{\theta_{t}\}$ defined as in (2.24), and $x^{*}$ denotes the optimal solution of problem (1.1), and the expectation is taken w.r.t. $i_{1},\ldots,i_{k}$.

The following corollary shows the convergence of RPDG under a non-uniform distribution for the random variables $i_{t}$, $t=1,\ldots,k$.

Suppose that $\{i_{t}\}$ in the RPDG method are distributed over $\{1,\ldots,m\}$ according to

Also assume that $\{\tau_{t}\}$, $\{\eta_{t}\}$, and $\{\alpha_{t}\}$ are set to (3.19) with

and hence that the conditions in (3.20)-(3.22) are satisfied. Notice that by the fact that $\alpha\geq 3/4,\ \ \forall m\geq 1$ and (3.26), we have

Using the above bound in (3.23), we obtain (3.28). It follows from the facts $(1-\alpha)\eta\leq\alpha\mu$, $1/2\leq\alpha\leq 1,\forall m\geq 1$, and $\eta\geq\mu\sqrt{C}>2\mu$ that

Using the above bound in (3.24), we obtain (3.29). Denoting $D\equiv(1+\tfrac{3L_{f}}{\mu})P(x^{0},x^{*})$, we conclude from (3.28) and the fact that $\log x\leq x-1$ for any $x\in(0,1)$ that

Moreover, by Markov’s inequality, (3.28) and the fact that $\log x\leq x-1$ for any $x\in(0,1)$, we have

The proofs for the complexity bounds in terms of the primal optimality gap is similar and hence the details are skipped.

The non-uniform distribution in (3.25) requires the estimation of the Lipschitz constants $L_{i}$, $i=1,\ldots,m$. In case such information is not available, we can use a uniform distribution for $i_{t}$, and as a result, the complexity bounds will depend on a larger condition number given by $m\max_{i=1,\ldots,m}L_{i}/\mu$. However, if we do have $L_{1}=L_{2}=\cdots=L_{m}$, then the results obtained by using a uniform distribution is slightly sharper than the one by using a non-uniform distribution in Corollary 1.

Suppose that $\{i_{t}\}$ in the RPDG method are uniformly distributed over $\{1,\ldots,m\}$ according to

Also assume that $\{\tau_{t}\}$, $\{\eta_{t}\}$, and $\{\alpha_{t}\}$ are set to (3.19) with

and hence that the conditions in (3.20)-(3.22) are satisfied. By the identity $(1-\alpha)\eta=\alpha\mu$, we have

Using the above bound in (3.23), we obtain (3.35). Moreover, note that $\eta\geq\mu\sqrt{\bar{C}}\geq 2\mu$ and $2/3\leq\alpha\leq 1,\forall m\geq 1$ we have

Using the above bound in (3.24), we obtain (3.36). The proofs for the complexity bounds are similar to those in Corollary 1 and hence the details are skipped.

Comparing the complexity bounds obtained from Corollaries 1 and 2 with those of any optimal deterministic first-order method, they differ in a factor of ${\cal O}(\sqrt{mL_{f}/L})$, whenever $\sqrt{mC}\log(1/\epsilon)$ is dominating in (3.30). Clearly, when $L_{f}$ and $L$ are in the same order of magnitude, RPDG can save up to ${\cal O}(\sqrt{m})$ gradient evaluations for the component function $f_{i}$ than the deterministic first-order methods. However, it should be pointed out that $L_{f}$ can be much smaller than $L$. In particular, when $L_{f}=L_{i},i=1,\ldots,m$, $L_{f}=L/m$. In the next subsection, we will construct examples in such extreme cases to obtain the lower complexity bound for general randomized incremental gradient methods.

3 Lower complexity bound for randomized methods

Our goal in this subsection is to demonstrate that the complexity bounds obtained in Theorem 3.1, and Corollaries 1 and 2 for the RPDG method are essentially not improvable. Observe that although there exist rich lower complexity bounds in the literature for deterministic first-order methods (e.g. nemyud:83 ; Nest04 ), the study on lower complexity bounds for randomized methods are still quite limited. Recently Agarwal and Bottou AgrBott14-1 suggested a lower complexity bound for minimizing the finite-sum convex optimization problem given in the form of (1.1). However, their bounds are developed for deterministic algorithms and hence not applicable to randomized incremental gradient methods.

To derive the performance limit of the incremental gradient methods, we consider a special class of unconstrained and separable strongly convex optimization problems given in the form of

where the last inequality follows from the fact that $\kappa\leq 3$. Therefore, for any ${\cal Q}>1$, the component functions $f_{i}$ in (3.38) are convex and their gradients are Lipschitz continuous with constant bounded by $L_{i}=\mu({\cal Q}-1)$, $i=1,\ldots,m$.

We consider a general class of randomized incremental gradient methods which sequentially acquire the gradients of a randomly selected component function $f_{i_{t}}$ at iteration $t$. More specifically, we assume that the independent random variables $i_{t}$, $t=1,2,\ldots$, satisfy

Similar to Nest04 , we assume that these methods generate a sequence of test points $\{x^{k}\}$ such that

where $\rm{Lin}$ denotes the linear span.

Theorem 3.2 below describes the performance limit of the above randomized incremental gradient methods for solving (3.37).

Let $x^{*}$ be the optimal solution of problem (3.37) and denote

Then the iterates $\{x^{k}\}$ generated by any randomized incremental gradient method must satisfy

As an immediate consequence of Theorem 3.2, we obtain a lower complexity bound for randomized incremental gradient methods.

if $n$ is sufficiently large, where ${\cal C}=L/\mu$ and $L=\textstyle{\sum}_{i=1}^{m}L_{i}$.

It follows from (3.43) that the number of iterations $k$ required by any randomized incremental gradient methods to find an approximate solution $\bar{x}$ must satisfy

Noting that for the worst-case instance in (3.37), we have $L_{i}=\mu({\cal Q}-1)$, $i=1,\ldots,m$, and hence that $L=\textstyle{\sum}_{i=1}^{m}L_{i}=m\mu(Q-1)$. Using this relation, we conclude that

The above bound holds when $n\geq\underline{n}(m,\underline{k})$.

In view of Theorem 3.2, we can also derive a lower complexity bound for randomized block coordinate descent methods, which update one randomly selected block of variables at each iteration for $\min_{x\in X}\Psi(x)$. Here $\Psi$ is smooth and strongly convex such that

if $n$ is sufficiently large, where ${\cal Q}_{\Psi}=L_{\Psi}/\mu_{\Psi}$ denotes the condition number of $\Psi$.

The worst-case instances in (3.37) have a block separable structure. Therefore, any randomized incremental gradient methods are equivalent to randomized block coordinate descent methods. The result then immediately follows from (3.45).

Generalization of randomized primal-dual gradient methods

In this section, we generalize the RPDG method for solving a few different types of convex optimization problems which are not necessarily smooth and strongly convex.

Our goal in this subsection is to generalize RPDG for solving smooth problems without strong convexity (i.e., $\mu=0$). Different from the deterministic PDG method, it is difficult to develop a simple stepsize policy for $\{\tau_{t}\}$, $\{\eta_{t}\}$, and $\{\alpha_{t}\}$ which can guarantee the convergence of this method unless a weaker termination criterion is used (see DangLan14-1 ). In order to obtain stronger convergence results, we will discuss a different approach obtained by applying the RPDG method to a slightly perturbed problem of (1.1).

In order to apply this perturbation approach, we will assume that $X$ is bounded (see Subsection 4.3 for possible extensions), i.e., given $x_{0}\in X$, $\exists\Omega_{X}\geq 0$ s.t.

Now we define the perturbation problem as

for some fixed $\delta>0$. It is well-known that an approximate solution of (4.2) will also be an approximate solution of (1.1) if $\delta$ is sufficiently small. More specifically, it is easy to verify that

The following result describes the complexity associated with this perturbation approach for solving smooth problems without strong convexity (i.e., $\mu=0$).

Let us apply the RPDG method with the parameter settings in Corollary 1 to the perturbation problem (4.2) with

iterations. Moreover, we can find a solution $\bar{x}\in X$ s.t. ${\hbox{\rm Prob}}\{\Psi(\bar{x})-\Psi^{*}>\epsilon\}\leq\lambda$ for any $\lambda\in(0,1)$ in at most

Let $x^{*}_{\delta}$ be the optimal solution of (4.2). Denote $C:=16L\Omega_{X}^{2}/\epsilon$ and

Note that problem (4.2) is given in the form of (1.1) with the strongly convex modulus $\mu=\delta$, and $h(x)=h(x)-\delta\langle\omega^{\prime}(x_{0}),x\rangle$. Hence by applying Corollary 1, we have

Observe that if we apply a deterministic optimal first-order method (e.g., Nesterov’s method or the PDG method), the total number of gradient evaluations for $\nabla f_{i}$, $i=1,\ldots,m$, would be given by

Comparing this bound with (4.6), we can see that the number of gradient evaluations performed by the RPDG method can be ${\cal O}\left(\sqrt{m}\log^{-1}(mL_{f}\Omega_{X}/\epsilon)\right)$ times smaller than these deterministic methods when $L$ and $L_{f}$ are in the same order of magnitude.

2 Structured nonsmooth problems

In this subsection, we assume that the smooth components $f_{i}$ are nonsmooth but can be approximated closely by smooth ones. More specifically, we assume that

Nesterov in an important work Nest05-1 shows that we can approximate $f_{i}(x)$ and $f$, respectively, by

where $v_{i}(y_{i})$ is a strongly convex function with modulus $1$ such that

for any $x\in X$, where $\Omega_{Y}^{2}=\textstyle{\sum}_{i=1}^{m}\Omega_{Y_{i}}^{2}$. Moreover, $f_{i}(\cdot,\delta)$ and $f(\cdot,\delta)$ are continuously differentiable and their gradients are Lipschitz continuous with constants given by

respectively. As a consequence, we can apply the RPDG method to solve the approximation problem

The following result provides complexity bounds of the RPDG method for solving the above structured nonsmooth problems for the case when $\mu>0$.

Let us apply the RPDG method with the parameter settings in Corollary 1 to the approximation problem (4.13) with

iterations. Moreover, we can find a solution $\bar{x}\in X$ s.t. ${\hbox{\rm Prob}}\{\Psi(\bar{x})-\Psi^{*}>\epsilon\}\leq\lambda$ for any $\lambda\in(0,1)$ in at most

The following result holds for the RPDG method applied to the above structured nonsmooth problems when $\mu=0$.

iterations. Moreover, we can find a solution $\bar{x}\in X$ s.t. ${\hbox{\rm Prob}}\{\Psi(\bar{x})-\Psi^{*}>\epsilon\}\leq\lambda$ for any $\lambda\in(0,1)$ in at most

Similarly to the arguments used in the proof of Proposition 2, our results follow from (4.17), and an application of Proposition 1 to problem (4.13).

3 Unconstrained smooth problems

We assume that the set of optimal solutions $X^{*}$ of this problem is nonempty.

We will still use the perturbation-based approach as described in Subsection 4.1 by solving the perturbation problem given by

We are now ready to establish the complexity of the RPDG method applied to (4.18) in terms of ${R_{ac}}(\bar{x},x^{0},f^{*})$.

Let us apply the RPDG method with the parameter settings in Corollary 1 to the perturbation problem (4.19) with

iterations. Moreover, we can find a solution $\bar{x}\in X$ s.t. ${\hbox{\rm Prob}}\{{R_{ac}}(\bar{x},x^{0},f^{*})>\epsilon\}\leq\lambda$ for any $\lambda\in(0,1)$ in at most

Let $x^{*}_{\delta}$ be the optimal solution of (4.19). Also let $x^{*}$ be the optimal solution of (4.18) that is closest to $x^{0}$, i.e., $x^{*}={\rm argmin}_{u\in X^{*}}\|x^{0}-u\|_{2}$. It then follows from the strong convexity of $f_{\delta}$ that

Moreover, using the definition of $f_{\delta}$ and the fact that $x^{*}$ is feasible to (4.19), we have

Now suppose that we run the RPDG method applied to (4.19) for $K$ iterations. Then by Corollary 1, we have

where the last inequality follows from (4.24) and $\alpha$ is defined in (3.26) with $C=8L_{\delta}/\delta=\tfrac{8(L+\delta)}{\delta}=8(2/\epsilon+1)$. Combining the above two relations, we have

Dividing both sides of the above inequality by $L(1+\|x^{0}-x^{*}\|_{2}^{2})/2$, we obtain

which clearly implies the bound in (4.22). The bound in (4.23) also follows from the above inequality and the Markov’s inequality.

By Proposition 4, the total number of gradient evaluations for the component functions $f_{i}$ required by the RPDG method can be ${\cal O}(\sqrt{m}\log^{-1}(m/\epsilon))$ times smaller than those performed by deterministic optimal first-order methods.

Complexity analysis

Our main goal in this section is to prove the main theorems in Sections 2 and 3. After introducing some basic tools and general results about PDG and RPDG methods in Subsection 5.1 and 5.2, respectively, we provide the proofs for Theorem 2.1 and Theorem 3.1, which describe the main convergence properties for the PDG and RPDG methods, in Subsection 5.3. Moreover, in Subsection 5.4, we provide the proof for the lower complexity bound in Theorem 3.2.

The following result provides a few different bounds on the diameter of the dual feasible sets ${\cal G}$ and ${\cal Y}$ in (2.7) and (3.1).

Let $x^{0}\in X$ be given, $y^{0}_{i}=\nabla f_{i}(x^{0})$, $i=1,\ldots,m$, and $g^{0}=\nabla f(x^{0})$. Assume that $J_{i}^{\prime}(y^{0})=x^{0}$ and $J_{f}^{\prime}(g^{0})=x^{0}$ in the definition of $D(y^{0},y)$ and $D_{f}(g^{0},g)$ in (3.4) and (2.5), respectively.

For any $x\in X$ and $y_{i}=\nabla f_{i}(x)$, $i=1,\ldots,m$, we have

If $x^{*}\in X$ is an optimal solution of (1.1) and $y^{*}_{i}=\nabla f_{i}(x^{*})$, $i=1,\ldots,m$, then

For any $x\in X$ and $g=\nabla f(x)$, we have

We first show part a). It follows from the definition of $J_{i}$, (3.4), and (3.6) that

where the last inequality follows from (2.2). We now show part b). By the above relation, the convexity of $h$ and $\omega$, and the optimality of $(x^{*},y^{*})$, we have

The proof of part c) is similar to part a) and hence the details are skipped.

The following lemma gives an important bound for the primal optimality gap $\Psi(\bar{x})-\Psi(x^{*})$ for some $\bar{x}\in X$.

Let $(\bar{x},\bar{y})\in Z$ be a given pair of feasible solutions of (3.1), and $z^{*}=(x^{*},y^{*})$ be a pair of optimal solutions of (3.1). Then, we have

Let $\bar{y}_{*}=(\nabla f_{1}(\bar{x});\nabla f_{2}(\bar{x});\dots;\nabla f_{m}(\bar{x}))$, and by the definition of $Q(\cdot,\cdot)$ in (3.3), we have

where the second equality follows from the fact that $J_{i},i=1,\dots,m$, are the conjugate functions of $f_{i}$.

2 General results for both PDG and RPDG

We will establish some general convergence results in Proposition 5 which holds for both deterministic and randomized PDG methods by viewing PDG as a special case of RPDG with $m=1$. Then both Theorems 2.1 and 3.1 follow as some immediate consequences of Proposition 5.

Before showing Proposition 5 we will develop a few technical results. Lemma 5 below characterizes the solutions of the prox-mapping in (2.3) and (3.5). This result generalizes some previous results (e.g., Lemma 6 of LaLuMo11-1 and Lemma 2 of GhaLan12-2a ).

for some $\mu_{0}\geq 0$. Also assume that the scalars $\mu_{1}$ and $\mu_{2}$ are chosen such that $\mu_{0}+\mu_{1}+\mu_{2}\geq 0$. If

Using these relations and (5.6), we conclude that

for any $u_{1},u_{2}\in Y$, which together with the fact that $\mu_{0}+\mu_{1}+\mu_{2}\geq 0$ then imply that $\phi$ is convex. Since $u^{*}$ is an optimal solution of (5.7), we have $\langle\phi^{\prime}(u^{*}),u-u^{*}\rangle\geq 0$. Combining this inequality with (5.8), we conclude that

from which the result immediately follows.

(5.9) follows immediately from the facts that ${\hbox{\rm Prob}}_{t}\{y_{i}^{t}=\hat{y}_{i}^{t}\}={\hbox{\rm Prob}}_{t}\{i_{t}=i\}=p_{i}$ and ${\hbox{\rm Prob}}_{t}\{y_{i}^{t}=y_{i}^{t-1}\}=1-p_{i}$. Here ${\hbox{\rm Prob}}_{t}$ denotes the conditional probability w.r.t. $i_{t}$ given $i_{1},\ldots,i_{t-1}$. Similarly, we can show (5.10).

We now prove an important recursion about the RPDG method.

Let the gap function $Q$ be defined in (3.3). Also let $x^{t}$ and $\hat{y}^{t}$ be defined in (3.10) and (3.11), respectively. Then for any $t\geq 1$, we have

It follows from Lemma 5 applied to (3.10) that $\forall x\in X$,

Moreover, by Lemma 5 applied to (3.11), we have, for any $i=1,\ldots,m$ and $t=1,\ldots,k$,

Summing up these inequalities over $i=1,\ldots,m$, we have, $\forall y\in{\cal Y}$,

Using the definition of $Q$ in (3.3), (5.12), and (5.13), we have

Also observe that by (3.8), (3.12), (5.9), and (5.10),

Taking expectation on both sides of (5.14) and using the above observations, we obtain (5.11).

We are now ready to establish a general convergence result which holds for both PDG and RPDG.

Suppose that $\{\tau_{t}\}$, $\{\eta_{t}\}$, and $\{\alpha_{t}\}$ in the RPDG method satisfy

for some $\theta_{t}\geq 0$, $t=1,\ldots,k$. Then, for any $k\geq 1$ and any given $z\in Z$, we have

Multiplying both sides of (5.11) by $\theta_{t}$ and summing the resulting inequalities, we have

which, in view of the assumptions in (5.16) and (5.15), then implies that

We now provide a bound on $\textstyle{\sum}_{t=1}^{k}\theta_{t}\Delta_{t}$ in (5.22). Note that by (3.7), we have

where the last identity follows from the observation that by (3.8) and (3.9),

Using relation (5.24) in the definition of $\Delta_{t}$ in (5.23), we have

Observe that by (5.20) and the fact that $x^{-1}=x^{0}$,

Using the previous three relations in (5.25), we have

Regrouping the terms in the above relation, and the fact that $x^{-1}=x^{0}$, we obtain

where the second inequality follows from the simple relation that

and the last inequality follows from (5.17) and (5.18). Plugging the bound (5.26) into (5.22), we have

The result then immediately follows by combining the above two conclusion.

3 Proof of main convergence results

We now provide a proof for Theorem 2.1 which describes the main convergence properties of the deterministic PDG method.

We first specialize Proposition 5 for the PDG method applied to (2.7).

Suppose that $\{\tau_{t}\}$, $\{\eta_{t}\}$, and $\{\alpha_{t}\}$ in the PDG method satisfy

for some $\theta_{t}\geq 0$, $t=1,\ldots,k$. Also let us denote $z^{t}=(x^{t},g^{t})$, and

Then, for any $k\geq 1$ and any given $(x,g)\in X\times{\cal G}$, we have

Notice that in the deterministic PDG method, we have $m=1$, $p_{i}=1$, and $\hat{y}^{t}=g^{t}$. It can be easily seen that the assumptions in (5.15)-(5.20) are implied by those in (5.28)-(5.32). It then follows from (5.21) that

Dividing both sides of the above inequality by $\textstyle{\sum}_{t=1}^{k}\theta_{t}$ and using the convexity of $Q(\bar{z},z)$ w.r.t. $\bar{z}$, we have

Rearranging the terms in the above relation, we obtain (5.34).

Proof of Theorem 2.1 We first show part a). It can be easily checked that (5.28)-(5.32) are satisfied with the selection of $\{\tau_{t}\}$, $\{\eta_{t}\}$, $\{\alpha_{t}\}$, and $\{\theta_{t}\}$ in (2.24). Using (5.34) (with $x=x^{*}$ and $y=y^{*}$), (5.3), and the fact that $Q_{f}(\bar{z},z^{*})\geq 0$, we have

Using the parameter settings in (2.24), we conclude that

Also using (5.34) and the fact that $P(x^{k},x)\geq 0$, we have

Denoting $\bar{g}^{k}_{*}:=(\nabla f_{1}(\bar{x}^{k});\ldots;\nabla f_{m}(\bar{x}^{k}))$, we conclude from (5.3) that

where the second inequality follows from the convexity of $\|\cdot\|^{2}$, the third inequality follows from the triangular inequality, the fourth inequality follows from $\|x^{t}-x^{*}\|^{2}\leq 2P(x^{t},x^{*})$ and (2.25), and the last inequality follows from $\|x^{0}-x^{*}\|^{2}\leq 2P(x^{0},x^{*})$. Also note that by the definition of $\theta_{t}$, we have

where the last inequality follows from the fact that $\alpha\leq 1$ due to (2.24). Fixing $g=\bar{g}^{k}_{*}$ in (5.35) and using the above two relations, we obtain

The result in (2.26) then directly follows from the above relation and (2.21). If $X$ is bounded, the result in (2.27) then follows from the above relation, (2.21), and (2.22).

We now show part b). It is trivial to check that the conditions in (5.28)-(5.32) hold by using our selection of $\{\tau_{t}\}$, $\{\eta_{t}\}$, $\{\alpha_{t}\}$, and $\{\theta_{t}\}$. Using (5.34) and the facts $\tau_{1}=0$ and $P(x^{k},x)\geq 0$, we have

which, in view of (2.20) and (2.21) and the fact that $\textstyle{\sum}_{t=1}^{k}\theta_{t}=k(k+1)/2$, clearly implies (2.29). In case $X$ is bounded, the result in (2.30) immediately follows from (2.21), (2.22), and the above inequality.

We are now ready to provide a proof for Theorem 3.1, which describes the main convergence properties of the RPDG method applied to strongly convex problems with $\mu>0$.

Proof of Theorem 3.1. It can be easily checked that the conditions in (5.15)-(5.20) are satisfied with our requirements (3.19)-(3.22) of $\{\tau_{t}\}$, $\{\eta_{t}\}$, $\{\alpha_{t}\}$, and $\{\theta_{t}\}$. Using the fact that $Q((x^{t},\hat{y}^{t}),z^{*})\geq 0$ , we then conclude from (5.21) (with $x=x^{*}$ and $y=y^{*}$) that, for any $k\geq 1$,

where the first inequality follows from (3.19) and (3.20), and the second inequality follows from (3.21) and (5.1).

Let us denote $\bar{y}^{k}\equiv(\textstyle{\sum}_{t=1}^{k}\theta_{t})^{-1}\textstyle{\sum}_{t=1}^{k}(\theta_{t}\hat{y}^{t})$, $\bar{z}^{k}=(\bar{x}^{k},\bar{y}^{k})$. In view of (5.4), the convexity of $\|\cdot\|$, and (2.2), we have

Using (5.21) (with $x=x^{*}$ and $y=y^{*}$), the fact that $P(x^{k},x)\geq 0$, and (5.36), we obtain

We conclude from (3.23) and the definition of $\{\theta_{t}\}$ that

Using the above two relations, and (5.3), we obtain

4 Proof of the lower complexity bound

This subsection is devoted to the proof of Theorem 3.2, which describes the performance limit for randomized incremental gradient methods.

The following result provides an explicit expression for the optimal solution of (3.37).

Let $q$ be defined in (3.42), $x^{*}_{i,j}$ is the $j$-th element of $x_{i}$, and define

Then $x^{*}$ is the unique optimal solution of (3.37).

It can be easily seen that $q$ is the smallest root of the equation

Note that $x^{*}$ satisfies the optimality condition of (3.37), i.e.,

Indeed, we can write the coordinate form of (5.40) as

where the first two equations follow directly from the definition of $x^{*}$ and relation (5.39), and the last equation is implied by the definitions of $\kappa$ and $x^{*}$ in (3.39) and (5.38), respectively.

We also need a few technical results to establish the lower complexity bounds.

Let $\rho,q,\bar{q}\in(0,1)$ be given. If we have

We first show part a). Denote $\phi(x)=\log(1-\tfrac{1}{x})+\tfrac{1}{x-1}$. It can be easily seen that $\lim_{x\to+\infty}\phi(x)=0$. Moreover, for any $x>1$, we have

which implies that $\phi$ is a strictly decreasing function for $x>1$. Hence, we must have $\phi(x)>0$ for any $x>1$. Part b) follows from the following simple calculation.

Proof of Theorem 3.2 Without loss of generality, we may assume that the initial point $x^{0}_{i}=0$, $i=1,\ldots,m$. Indeed, the incremental gradient methods described in Subsection 3.3 are invariant with respect to a simultaneous shift of the decision variables. In other words, the sequence of iterates $\{x^{k}\}$, which is generated by such a method for minimizing the function $\Psi(x)$ starting from $x^{0}$, is just a shift of the sequence generated for minimizing $\bar{\Psi}(x)=\Psi(x+x^{0})$ starting from the origin.

Noting that $[1-(1-q^{2})p_{i}]^{k}$ is convex w.r.t. $p_{i}$ for any $p_{i}\in$ and $k\geq 1$, by minimizing the RHS of the above bound w.r.t. $p_{i}$, $i=1,\ldots,m$, subject to $\sum_{i=1}^{m}p_{i}=1$ and $p_{i}\geq 0$, we conclude that

for any $n\geq\underline{n}(m,k)$ (see (3.44)) and possible selection of $p_{i}$, $i=1,\ldots,m$ satisfying (3.40), where the last inequality follows from Lemma 9.b). Noting that

we then conclude from (5.46) and Lemma 9.a) that

Concluding remarks

References