Abstract
Our main goal in this paper is to show that one can skip gradient computations for gradient descent type methods applied to certain structured convex programming (CP) problems. To this end, we first present an accelerated gradient sliding (AGS) method for minimizing the summation of two smooth convex functions with different Lipschitz constants. We show that the AGS method can skip the gradient computation for one of these smooth components without slowing down the overall optimal rate of convergence. This result is much sharper than the classic black-box CP complexity results especially when the difference between the two Lipschitz constants associated with these components is large. We then consider an important class of bilinear saddle point problem whose objective function is given by the summation of a smooth component and a nonsmooth one with a bilinear saddle point structure. Using the aforementioned AGS method for smooth composite optimization and Nesterov’s smoothing technique, we show that one only needs \({{\mathcal{O}}}(1/\sqrt{\varepsilon })\) gradient computations for the smooth component while still preserving the optimal \({{\mathcal{O}}}(1/\varepsilon )\) overall iteration complexity for solving these saddle point problems. We demonstrate that even more significant savings on gradient computations can be obtained for strongly convex smooth and bilinear saddle point problems.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In this paper, we show that one can skip gradient computations without slowing down the convergence of gradient descent type methods for solving certain structured convex programming (CP) problems. To motivate our study, let us first consider the following classic bilinear saddle point problem (SPP):
Here, \(X\subseteq \mathbb {R}^n\) and \(Y\subseteq \mathbb {R}^m\) are nonempty, closed, and convex sets, \(K: \mathbb {R}^n \rightarrow \mathbb {R}^m\) is a linear operator, J is a relatively simple convex function, and \(f:X\rightarrow \mathbb {R}\) is a continuously differentiable convex function satisfying
for some \(L>0\), where \(l_f(u,x):=f(u) + \langle \nabla f(u), x-u\rangle\) denotes the first-order Taylor expansion of f at u. Since \(\psi\) is a nonsmooth convex function, traditional nonsmooth optimization methods, e.g., the subgradient method, would require \(\mathcal{O} (1/\varepsilon ^2)\) iterations to find an \(\varepsilon\)-solution of (1.1), i.e., a point \({{\bar{x}}} \in X\) s.t. \(\psi ({{\bar{x}}}) - \psi ^* \le \varepsilon\). In a landmark work [30], Nesterov suggests to approximate \(\psi\) by a smooth convex function
with
for some \(\rho > 0\), where \(y_0\in Y\) and \(W(y_0,\cdot )\) is a strongly convex function. By properly choosing \(\rho\) and applying the optimal gradient method to (1.3), he shows that one can compute an \(\varepsilon\)-solution of (1.1) in at most
iterations. Following [30], much research effort has been devoted to the development of first-order methods utilizing the saddle-point structure of (1.1) (see, e.g., the smoothing technique [2, 3, 11, 20, 22, 24, 29, 30, 36], the mirror-prox methods [9, 17, 21, 27], the primal-dual type methods [6, 10, 13, 19, 36, 37] and their equivalent form as the alternating direction method of multipliers [15, 16, 18, 26, 33, 34]). Some of these methods (e.g., [9, 10, 19, 22, 34]) can achieve exactly the same complexity bound as in (1.5). Recently, in [35] it is proved that the complexity bound in (1.5) is theoretically unimprovable. Specifically, for any first-order method that calls oracle \(\mathcal{O} (x,y)\mapsto (\nabla f(x), Kx, K^Ty)\) at inquiry point (x, y) to access information of f and K in the saddle point problem (1.1), the number of oracle inquiries to compute an \(\varepsilon\)-solution is at least (1.5). In other words, if each iteration of a first-order method requires both the computation of \(\nabla f\) and the evaluation of the linear operators (K and \(K^T\)), the total numbers of gradient and linear operator evaluations will both be no less than \(\mathcal{O} (1/\varepsilon )\). Therefore, Nesterov’s smooth scheme is an optimal method among all first-order methods that performs gradient and linear operator evaluations in each iteration.
One problem associated with Nesterov’s smoothing scheme and the related methods mentioned above is that each iteration of these methods requires both the computation of \(\nabla f\) and the evaluation of the linear operators (K and \(K^T\)). As a result, the total number of gradient and linear operator evaluations will both be bounded by \({{\mathcal{O}}}(1/\varepsilon )\). However, in many applications the computation of \(\nabla f\) is often much more expensive than the evaluation of the linear operators K and \(K^T\). This happens, for example, when the linear operator K is sparse (e.g., total variation, overlapped group lasso and graph regularization), while f involves a more expensive data-fitting term (see Sect. 4 and [23] for some other examples). In [23], Lan considered some similar situation and proposed a gradient sliding (GS) algorithm to minimize a class of composite problems whose objective function is given by the summation of a general smooth and nonsmooth component. He shows that one can skip the computation of the gradient for the smooth component from time to time, while still maintaining the \({{\mathcal{O}}}(1/\varepsilon ^2)\) iteration complexity bound. More specifically, by applying the GS method in [23] to problem (1.1), we can show that the number of gradient evaluations of \(\nabla f\) will be bounded by
which is significantly better than (1.5). Unfortunately, the total number of evaluations for the linear operators K and \(K^T\) will be bounded by
which is much worse than (1.5). An important yet unresolved research question is whether one can still preserve the optimal \({{\mathcal{O}}}(1/\varepsilon )\) complexity bound in (1.5) for solving (1.1) by utilizing only \({{\mathcal{O}}}(1/\sqrt{\varepsilon })\) gradient computations of \(\nabla f\) to find an \(\varepsilon\)-solution of (1.1). If so, we could be able to keep the total number of iterations relatively small, but significantly reduce the total number of required gradient computations.
In order to address the aforementioned issues associated with existing solution methods for solving (1.1), we pursue in this paper a different approach to exploit the structural information of (1.1). Firstly, instead of concentrating solely on nonsmooth optimization as in [23], we study the following smooth composite optimization problem:
Here f and h are smooth convex functions satisfying (1.2) and
respectively. It is worth noting that problem (1.6) can be viewed as a special case of either (1.1) or (1.3) (with \(J=h^*\) being a strongly convex function, \(Y=\mathbb {R}^n\), \(K=I\) and \(\rho =0\)). Under the assumption that \(M\ge L\), we present a novel accelerated gradient sliding (AGS) method which can skip the computation of \(\nabla f\) from time to time. We show that the total number of required gradient evaluations of \(\nabla f\) and \(\nabla h\), respectively, can be bounded by
to find an \(\varepsilon\)-solution of (1.6). Observe that the above complexity bounds are sharper than the complexity bound obtained by Nesterov’s optimal method for smooth convex optimization, which is given by
In particular, for the AGS method, the Lipschitz constant M associated with \(\nabla h\) does not affect at all the number of gradient evaluations of \(\nabla f\). Clearly, the higher ratio of M/L will potentially result in more savings on the gradient computation of \(\nabla f\). Moreover, if f is strongly convex with modulus \(\mu\), then the above two complexity bounds in (1.8) can be significantly reduced to
respectively, which also improves Nesterov’s optimal method applied to (1.6) in terms of the number of gradient evaluations of \(\nabla f\). Observe that in the classic black-box setting [28, 32] the complexity bounds in terms of gradient evaluations of \(\nabla f\) and \(\nabla h\) are intertwined, and a larger Lipschitz constant M will result in more gradient evaluations of \(\nabla f\), even though there is no explicit relationship between \(\nabla f\) and M. In our development, we break down the black-box assumption by assuming that we have separate access to \(\nabla f\) and \(\nabla h\) rather than \(\nabla \phi\) as a whole. To the best of our knowledge, these types of separate complexity bounds as in (1.8) and (1.9) have never been obtained before for smooth convex optimization.
Secondly, we apply the above AGS method to the smooth approximation problem (1.3) in order to solve the aforementioned bilinear SPP in (1.1). By choosing the smoothing parameter properly, we show that the total number of gradient evaluations of \(\nabla f\) and operator evaluations of K (and \(K^T\)) for finding an \(\varepsilon\)-solution of (1.1) can be bounded by
respectively. In comparison with Nesterov’s original smoothing scheme and other existing methods for solving (1.1), our method can provide significant savings on the number of gradient computations of \(\nabla f\) without increasing the complexity bound on the number of operator evaluations of K and \(K^T\). In comparison with the GS method in [23], our method can reduce the number of operator evaluations of K and \(K^T\) from \({{\mathcal{O}}}(1/ \varepsilon ^2)\) to \({{\mathcal{O}}}(1/\varepsilon )\). Moreover, if f is strongly convex with modulus \(\mu\), the above two bounds will be significantly reduced to
respectively. To the best of our knowledge, this is the first time that these tight complexity bounds were obtained for solving the classic bilinear saddle point problem (1.1).
It should be noted that, even though the idea of skipping the computation of \(\nabla f\) is similar to [23], the AGS method presented in this paper significantly differs from the GS method in [23]. In particular, each iteration of the GS method consists of one accelerated gradient iteration together with a bounded number of subgradient iterations. On the other hand, each iteration of the AGS method is composed of an accelerated gradient iteration nested with a few other accelerated gradient iterations to solve a different subproblem. The development of the AGS method seems to be more technical than GS and its convergence analysis is also highly nontrivial.
This paper is organized as follows. We first present the AGS method and discuss its convergence properties for minimizing the summation of two smooth convex functions (1.6) in Sect. 2. Utilizing this new algorithm and its associated convergence results, we study the properties of the AGS method for minimizing the bilinear saddle point problem (1.1) in Sect. 3. We then demonstrate the effectiveness of the AGS method throughout preliminary numerical experiments for solving certain image reconstruction problems in Sect. 4. Some brief concluding remarks are made in Sect. 5.
1.1 Notation, assumption and terminology
We use \(\Vert \cdot \Vert\), \(\Vert \cdot \Vert _*\), and \(\langle \cdot ,\cdot \rangle\) to denote an arbitrary norm, the associated dual norm, and the inner product in an Euclidean space, respectively. It should be noted that there are two Euclidean spaces \(\mathbb {R}^n\) and \(\mathbb {R}^m\) in problem (1.1) that may be equipped with different norms. Nonetheless, since it is easy to distinguish the norm of \(x\in \mathbb {R}^n\) and \(y\in \mathbb {R}^m\) by noticing their respective spaces, we will sightly abuse the notation and use the same norm notation \(\Vert x\Vert\) and \(\Vert y\Vert\) to denote their norms in \(\mathbb {R}^n\) and \(\mathbb {R}^m\) respectively. We will also use \(\Vert K\Vert\) to denote the operator norm of an operator \(K:\mathbb {R}^n\rightarrow \mathbb {R}^m\) induced by norms \(\Vert \cdot \Vert\) in \(\mathbb {R}^n\) and \(\mathbb {R}^m\).
For any set X, we say that \(V(\cdot ,\cdot )\) is a prox-function associated with \(X \subseteq \mathbb {R}^n\) modulus \(\nu\) if there exists a strongly convex function \(\zeta (\cdot )\) with strong convexity parameter \(\nu\) such that
The above prox-function is also known as the Bregman divergence [4] (see also [27, 30]), which generalizes the Euclidean distance \(\Vert x-u\Vert _2^2/2\). It can be easily seen from (1.10) and the strong convexity of \(\zeta\) that
Moreover, we say that the prox-function grows quadratically if there exists a constant C such that \(V(x,u)\le C\Vert x-u\Vert ^2/2\). Without loss of generality, we assume that \(C=1\) whenever this happens, i.e.,
In this paper, we associate sets \(X\subseteq \mathbb {R}^n\) and \(Y \subseteq \mathbb {R}^m\) with prox-functions \(V(\cdot ,\cdot )\) and \(W(\cdot ,\cdot )\) with moduli \(\nu\) and \(\omega\) w.r.t. their respective norms in \(\mathbb {R}^n\) and \(\mathbb {R}^m\).
For any real number r, \(\lceil r\rceil\) and \(\lfloor r\rfloor\) denote the nearest integer to r from above and below, respectively. We denote the set of nonnegative and positive real numbers by \(\mathbb {R}_+\) and \(\mathbb {R}_{++}\), respectively.
2 Accelerated gradient sliding for composite smooth optimization
In this section, we present an accelerated gradient sliding (AGS) algorithm for solving the smooth composite optimization problem in (1.6) and discuss its convergence properties. Our main objective is to show that the AGS algorithm can skip the evaluation of \(\nabla f\) from time to time and achieve better complexity bounds in terms of gradient computations than the classical optimal first-order methods applied to (1.6) (e.g., Nesterov’s method in [31]). Without loss of generality, throughout this section we assume that \(M\ge L\) in (1.2) and (1.7).
2.1 The accelerated gradient sliding algorithm
The AGS method evolves from the gradient sliding (GS) algorithm in [23], which was designed to solve a class of composite convex optimization problems with the objective function given by the summation of a smooth and nonsmooth component. The basic idea of the GS method is to keep the nonsmooth term inside the projection (or proximal mapping) in the accelerated gradient method and then to apply a few subgradient descent iterations to solve the projection subproblem. Inspired by [23], we suggest to keep the smooth term h whose gradient has a larger Lipschitz constant in the proximal mapping in the accelerated gradient method, and then to apply a few accelerated gradient iterations to solve this smooth subproblem. As a consequence, the proposed AGS method involves two nested loops (i.e., outer and inner iterations), each of which consists of a set of modified accelerated gradient descent iterations (see Algorithm 1). At the k-th outer iteration, we first build a linear approximation \(l_f({\underline{x}}_k,u)\) of f at the search point \({\underline{x}}_k \in X\) and then call the ProxAG procedure in (2.5) to compute a new pair of search points \((x_k, {\tilde{x}}_k) \in X \times X\). The ProxAG procedure can be viewed as a subroutine to compute a pair of approximate solutions to
where \(g_k(\cdot )\) is defined in (2.4). Here \(x_{k-1}\) is called the prox-center at the k-th outer iteration. It is worth mentioning that there are two essential differences associated with the steps (2.3–2.7) from the standard Nesterov’s accelerated gradient iterations. Firstly, we use two different search points, i.e., \(x_k\) and \({\overline{x}}_k\), respectively, to update \({\underline{x}}_k\) to compute the linear approximation and \({\overline{x}}_k\) to compute the output solution in (2.6). Secondly, we employ two parameters, i.e., \(\gamma _k\) and \(\lambda _k\), to update \({\underline{x}}_k\) and \({\overline{x}}_k\), respectively, rather than just one single parameter. For the purpose of understanding the intuition behind the proposed AGS method, with some plausible reasoning, the proposed AGS methods can also be understood as an implementation of Nesterov’s accelerated gradient method in which the proximal subproblem is solved approximately. Namely, iterations (2.3) through (2.6) can also be interpreted as follows:
Clearly, if the above proximal subproblem is solved exactly and \({\tilde{x}}_k = x_k\), then AGS becomes Nesterov’s accelerated gradient method. However, note that a caveat of the above interpretation is that \({\tilde{x}}_k\) and \(x_k\) need to be different in order to achieve proper convergence results.
Based on the above plausible interpretation, the ProxAG procedure in Algorithm 1 solves the proximal subproblem (2.2) approximately. Specifically, it performs \(T_k\) inner accelerated gradient iterations to solve (2.1) with certain properly chosen starting points \({\tilde{u}}_0\) and \(u_0\). It should be noted, however, that the accelerated gradient iterations in (2.7)–(2.9) also differ from the standard Nesterov’s accelerated gradient iterations in the sense that the definition of the search point \({\underline{u}}_t\) involves a fixed search point \({\overline{x}}\). Since each inner iteration of the ProxAG procedure requires one evaluation of \(\nabla h\) and no evaluation of \(\nabla f\), the number of gradient evaluations of \(\nabla h\) will be greater than that of \(\nabla f\) as long as \(T_k > 1\). On the other hand, if \(\lambda _k\equiv \gamma _k\) and \(T_k\equiv 1\) in the AGS method, and \(\alpha _t\equiv 1\), and \(p_t\equiv q_t\equiv 0\) in the ProxAG procedure, then (2.5) becomes
In this case, the AGS method reduces to a variant of Nesterov’s optimal gradient method (see, e.g., [32, 36]). Note that concept of Nesterov’s accelerated gradient method (with some modification) is applied twice in both the \(k=1,\ldots ,N\) iterations for solving the original problem and in solving the proximal subproblem (2.2) approximately. The idea may lead to different combinations such as non-accelerated + accelerated, accelerated + non-accelerated, and accelerated + accelerated. In this paper, we show that the total number of gradient evaluations of \(\nabla f\) and \(\nabla h\) can be bounded by \(\mathcal{O} (\sqrt{L/\varepsilon })\) and \(\mathcal{O} (\sqrt{M/\varepsilon })\) respectively. To the best of our knowledge, such complexity can only be achieved through the last combination. It is possible to adapt the convergence analysis to the former two; however, for these two combinations, the bound of one of the gradient evaluations will deteriorate to a worse \(\mathcal{O} (1/\varepsilon )\) order.
Our goal in the remaining part of this section is to establish the convergence of the AGS method and to provide theoretical guidance to specify quite a few parameters, including \(\{\gamma _k\}\), \(\{\beta _k\}\), \(\{T_k\}\), \(\{\lambda _k\}\), \(\{\alpha _t\}\), \(\{p_t\}\), and \(\{q_t\}\), used in the generic statement of this algorithm. In particular, we will provide upper bounds on the number of outer and inner iterations, corresponding to the number of gradient evaluations of \(\nabla f\) and \(\nabla h\), respectively, performed by the AGS method to find an \(\varepsilon\)-solution to (1.6). It should be noted that, although we use several notations for different parameters, we are not leaving the task of choosing parameters to the readers. Actually, the several notations of different parameters are only used to describe the framework of the proposed AGS method. The exact values of all the parameters will be provided in the sequel, and AGS requires no more than the knowledge of two Lipschitz constants L and M.
2.2 Approximate error measure and technical lemmas
In our convergence analysis, we measure the quality of the output solution computed at the k-th call to the ProxAG procedure by the following (approximate) error measure:
Indeed, if \(x^*\) is an optimal solution to (1.6), then \(Q_k(x,x^*)\) provides a linear approximation for the functional optimality gap \(\phi (x) - \phi (x^*)=f(x)-f(x^*)+h(x)-h(x^*)\) obtained by replacing f with \(g_k\). The following result describes some relationship between \(\phi (x)\) and \(Q_k(\cdot ,\cdot )\).
Lemma 2.1
For any \(u\in X\), we have
Proof
By the Lipschitz smoothness assumption (1.2), definition of \(\phi\) and \(g_k\) in (1.6) and (2.4) respectively, and the convexity of \(f(\cdot )\), we have
\(\square\)
For convergence analysis, we need the following two technical results. The first one below characterizes the solution of optimization problems involving prox-functions. The proof of this result can be found, for example, in Lemma 2 of [14].
Lemma 2.2
Suppose that a convex set \(Z\subseteq \mathbb {R}^n\), a convex function \(q:Z\rightarrow \mathbb {R}\), points \(z,z'\in Z\) and scalars \(\mu _1,\mu _2\in \mathbb {R}_+\) are given. Also let V(z, u) be a prox-function. If
then for any \(u\in Z\), we have
The second technical result slightly generalizes Lemma 3 of [22] to provide a convenient way to study sequences with sublinear rates of convergence.
Lemma 2.3
Let \(c_k\in (0,1)\), \(k=2,3,\ldots\) and \(C_1>0\) be given, and define
If the sequence \(\{\delta _k\}_{k\ge 0}\) satisfies
then for any \(k\ge 1\) we have
In particular, the above inequality becomes equality when the relations in (2.12) are all equality relations.
Proof
The result follows from dividing both sides of (2.12) by \(C_k\) and then summing up the resulting inequalities or equalities. \(\square\)
It should be noted that, although (2.12) and (2.13) are stated in the form of inequalities, we can derive some useful formulas by setting them to be equalities. For example, let \(\{\alpha _t\}\) be the parameters used in the ProxAG procedure (see (2.7) and (2.9)) and consider the sequence \(\{\varLambda _t\}_{t\ge 1}\) defined by
By Lemma 2.3 (with \(k=t\), \(C_k=\varLambda _t\), \(c_k=\alpha _t\), \(\delta _k\equiv 1\), and \(B_k=\alpha _t\)) and observing that \(\varLambda _1=1\), we have the following weighted sum result regarding the sum of \(\alpha _i/\varLambda _i\)’s:
Similarly, applying Lemma 2.3 to each component of the recursion \({\tilde{u}}_t = (1-\alpha _t){\tilde{u}}_{t-1}+ \alpha _tu_t\) in (2.9) (with \(k=t\), \(C_k=\varLambda _t\), \(c_k=\alpha _t\), \(\delta _k={\tilde{u}}_t\), and \(B_k=\alpha _tu_t\)), we have a weighted sum description of \({\tilde{u}}_t\) below:
In view of (2.15) and the fact that \({\tilde{u}}_0 = {\overline{x}}\) in the description of the ProxAG procedure, the above relation indicates that \({\tilde{u}}_t\) is a convex combination of \({\overline{x}}\) and \(\{u_i\}_{i=1}^t\).
2.3 Convergence properties of the ProxAG procedure
With the help of the technical results in the previous subsection, we are now ready to derive some important convergence properties for the ProxAG procedure in terms of the error measure \(Q_k(\cdot ,\cdot )\). For the sake of notational convenience, when we work on the k-th call to the ProxAG procedure, we drop the subscript k in (2.10) and just denote
In a similar vein, we also define
Comparing the above notations with (2.3) and (2.6), we can observe that \({\underline{x}}\) and \({\overline{x}}^+\), respectively, represent \({\underline{x}}_k\) and \({\overline{x}}_k\) in the k-th call to the ProxAG procedure.
Lemma 2.4
Consider the k-th call to the ProxAG procedure in Algorithm 1 and let \(\varLambda _t\) and \({\overline{x}}^+\) be defined in (2.14) and (2.18) respectively. If the parameters satisfy
then
where
Proof
Let us fix any arbitrary \(u\in X\) and denote
Our proof consists of two major parts. We first prove that
and then estimate the right-hand-side of (2.23) through the following recurrence property:
The result in (2.20) then follows as an immediate consequence of (2.23) and (2.24). Indeed, by Lemma 2.3 applied to (2.24) (with \(k=t\), \(C_k=\varLambda _t\), \(c_k=\alpha _t\), \(\delta _k=Q({\overline{u}}_t,v)\), and \(B_k=\varUpsilon _t(u)\)), we have
where last inequality follows from (2.19) and the fact that \(\varLambda _1=1\) in the definition of \(\varLambda _t\) in (2.14). The above relation together with (2.23) then clearly imply (2.20).
We start with the first part of the proof regarding (2.23). By the definition of Q in (2.17) and the linearity of \(g(\cdot )\), we have
Now, noting that by the relation between u and v in (2.22), we have
In addition, by (2.22) and the convexity of \(h(\cdot )\), we obtain
or equivalently,
Applying (2.26) and (2.27) to (2.25), and using the definition of Q in (2.17), we obtain
Noting that \({\tilde{u}}_0={\overline{x}}\) and \({\tilde{x}}^+ = {\tilde{u}}_T\) in the description of the ProxAG procedure, by the definitions of \({\overline{x}}^+\) and \({\overline{u}}_t\) in (2.18) and (2.22) we have \({\overline{x}}^+ = {\overline{u}}_T\) and \({\overline{u}}_0={\overline{x}}\) respectively. Therefore, the above relation is equivalent to (2.23), and we conclude the first part of the proof.
For the second part of the proof regarding (2.24), first note that by the definitions of \({\underline{u}}_t\), \({\tilde{u}}_t\), and v in (2.7), (2.9), and (2.22) respectively,
By a similar argument as the above, we also have
Now observe that by the definition of Q in (2.17), the convexity of \(h(\cdot )\), and the smoothness inequality (1.7) regarding constant M,
Summarizing the above three relations, we have
Moreover, it follows from Lemma 2.2 applied to the optimization problem in the definition of \(u_t\) in (2.8) that
Also by the relation between the prox-function V and norm in (1.11) and our assumption (2.19), we have
Combining the above three relations, we conclude (2.24). \(\square\)
In the following proposition, we provide certain sufficient conditions under which the right-hand-side of (2.20) can be properly bounded. As a consequence, we obtain a recurrence relation for the ProxAG procedure in terms of \(Q({\overline{x}}_k,u)\).
Proposition 2.1
Consider the k-th call to the ProxAG procedure. If (2.19) holds, and
for any \(1 \le t \le T-1\), then we have
where \({\overline{x}}^+\) and \({\underline{x}}\) are defined in (2.18).
Proof
To prove the proposition it suffices to estimate the right-hand-side of (2.20). We make three observations regarding the results (2.20) and (2.21) of Lemma 2.4. First, by the weight sum result of \(\alpha _i/\varLambda _i\)’s in (2.15),
Second, by the prox-function and norm relation (1.11), the weighted sum results (2.15) and (2.16), the assumption of parameters in (2.19), the convexity of \(\Vert \cdot \Vert ^2\), and the fact that \({\tilde{u}}_0={\overline{x}}\) and \({\tilde{x}}^+={\tilde{u}}_T\) in the ProxAG procedure, we have
where the last equality follows from the definitions of \({\underline{x}}\) and \({\overline{x}}^+\) in (2.18). Third, by the assumption of parameters in (2.28), the fact that \(\varLambda _1=1\) in (2.14), and the relations that \(u_0 = x\) and \(u_T=x^+\) in the ProxAG procedure, we have
Using the above three observations in the result of Lemma 2.4 in (2.20), we have
Comparing the above equation with our goal (2.29), it suffices to show that
By the last relation in our assumption (2.28), the weighted sum result of \(\alpha _i/\varLambda _i\)’s in (2.15), and the fact that \(\varLambda _1=1\), we have
The above implies that \(\alpha _t(1+p_t) = \varLambda _t\alpha _1p_1 + 1-\varLambda _t(1-\alpha _1)\) for any \(1 \le t \le T\). \(\square\)
2.4 Main convergence results of the AGS method
With the help of the above proposition and Lemma 2.1, we are now ready to establish the convergence of the AGS method. The following sequence will the used in the analysis of the AGS method:
Theorem 2.1
Suppose that the parameters of the k-th call to the ProxAG procedure in Algorithm 1 satisfy
for any \(1 \le t \le T-1\). If
then
where \(\varGamma _k\) is defined in (2.30).
Proof
Note that (2.31) is simply a summary of assumptions (2.19) and (2.28) for Proposition 2.1. It follows from Proposition 2.1 that for all \(u\in X\),
Substituting the above bound to the result (2.11) in Lemma 2.1, and using the assumption (2.32), we have
which, in view of Lemma 2.3 (with \(c_k=\gamma _k\), \(C_k = \varGamma _k\), and \(\delta _k = \phi ({\overline{x}}_k) - \phi (u)\)), then implies that
where the last equality follows from the fact that \(\gamma _1=1\) in (2.32). \(\square\)
There are many possible selections of parameters that satisfy the assumptions of the above theorem. In the following corollaries we describe two different ways to specify the parameters of Algorithm 1 that lead to the optimal complexity bounds in terms of the number of gradient evaluations of \(\nabla f\) and \(\nabla h\).
Corollary 2.1
Consider problem (1.6) with the Lipschitz constants in (1.2) and (1.7) satisfing \(M\ge L\). Suppose that the parameters of Algorithm 1 are set to
Also assume that the parameters in the first call to the ProxAG procedure (\(k=1\)) are set to
and the parameters in the remaining calls to the ProxAG procedure (\(k>1\)) are set to
Then the numbers of gradient evaluations of \(\nabla f\) and \(\nabla h\) performed by the AGS method to compute an \(\varepsilon\)-solution of (1.6) can be bounded by
and
respectively, where \(x^*\) is a solution to (1.6).
Proof
Let us start with verification of (2.31) and (2.32) for the purpose of applying Theorem 2.1. We will consider the first call to the ProxAG procedure (\(k=1\)) and the remaining calls (\(k>1\)) separately.
When \(k=1\), by (2.34) we have \(\lambda _1=\gamma _1=1\), and \(\beta _1=3L/\nu\), hence (2.32) holds immediately. By (2.35) we can observe that \(\varLambda _t=2/(t(t+1))\) satisfies (2.14), and that
In addition, by (2.34) and (2.35) we have \(\lambda =\gamma =1\) and \(\alpha _1=1\) in (2.31), and that
Therefore (2.31) holds.
For the case when \(k>1\), from (2.34) and noting that \(k, T\ge 1\), we have
Applying the above relation to the definition of \(\beta _k\) in (2.34) we have (2.32). It now suffices to verify (2.31) in order to apply Theorem 2.1. We can observe from (2.36) that \(\varLambda _t=6/(t+1)(t+2)\) satisfies (2.14), \({\alpha _tq_t}/{\varLambda _t}\equiv {2M}/{(\nu k)}\), and that
Applying (2.34), (2.36), (2.39), and noting that \(k\ge 2\) and that \(\varLambda _T=6/(T+1)(T+2)\) with \(T\ge 1\), we can verify in (2.31) that
Therefore, the conditions in (2.31) are satisfied.
We are now ready to apply Theorem 2.1. In particular, noting that \(\alpha _t(1+p_t)\equiv 1\) from (2.35) and (2.36), we obtain from the result (2.33) of Theorem 2.1 (with \(u=x^*\)) that
where
Substituting (2.34) and (2.35) to (2.41), and noting that \(\varGamma _i=2/(i(i+1))\) by (2.30), we have
Applying the above two results regarding \(\xi _i\) to (2.40), and noting that \(\xi _1>\xi _2\), we have
where the last inequality is due to the fact that \(T\ge \sqrt{M/L}\).
From the above inequality, the number of calls to the ProxAG procedure for computing an \(\varepsilon\)-solution of (1.6) is bounded by \(N_{f}\) in (2.37). This is also the bound for the number of gradient evaluations of \(\nabla f\). Moreover, the number of gradient evaluations of \(\nabla h\) is bounded by
\(\square\)
In the above corollary, the constant factors in (2.37) and (2.38) are both \(\sqrt{30}\). In the following corollary, we provide a slightly different set of parameters for Algorithm 1 that results in a smaller constant factor for (2.37).
Corollary 2.2
Consider problem (1.6) with the Lipschitz constants in (1.2) and (1.7) satisfing \(M\ge L\). Suppose that the parameters in the first call to the ProxAG procedure (\(k=1\)) are set to
and that the parameters in the k-th call (\(k>1\)) are set to
If the other parameters in Algorithm 1 satisfy
where \(\alpha\) is defined in (2.43), then the numbers of gradient evaluations of \(\nabla f\) and \(\nabla h\) performed by the AGS method to find an \(\varepsilon\)-solution to problem (1.6) can be bounded by
and
respectively.
Proof
Let us verify (2.31) and (2.32) first, so that we could apply Theorem 2.1. We consider the case when \(k=1\) first. By the definition of \(\gamma _k\) and \(\beta _k\) in (2.44), it is clear that (2.32) is satisfied when \(k=1\). Also, by (2.42) we have that \(\varLambda _t=2/(t(t+1))\) in (2.14),
Moreover, by (2.42) and (2.44), we can verify in (2.31) that
Therefore the relations in (2.31) are all satisfied.
Now we consider the case when \(k>1\). By the definition of \(\varLambda _t\) in (2.14) and our setting of parameters in (2.43), we observe that \(\varLambda _t = (1-\alpha )^{t-1}\) for all \(t\ge 1\). Moreover, from the definition of \(T_k\) in (2.44), we can also observe that
Four relations can be derived based on the aforementioned two observations, (2.43), and (2.44). First,
which leads to (2.32). Second,
Third, noting that \(k\ge 2\), we have
Fourth,
The last three relations imply that (2.31) holds.
Summarizing the above discussions regarding both the cases \(k=1\) and \(k>1\), applying Theorem 2.1, and noting that \(\alpha _t(1+p_t)\equiv 1\), we have
It should be observed from the definition of \(\gamma _k\) in (2.44) that \(\varGamma _i:=2/(i(i+1))\) satisfies (2.30). Using this observation, applying (2.42), (2.43), and (2.44) to the above equation we have
Therefore, (2.47) becomes
Setting \(u=x^*\) in the above inequality, we observe that the number of calls to the ProxAG procedure for computing an \(\varepsilon\)-solution of (1.6) is bounded by \(N_{f}\) in (2.45). This is also the bound for the number of gradient evaluations of \(\nabla f\). Moreover, by (2.43), (2.44), and (2.45) we conclude that the number of gradient evaluations of \(\nabla h\) is bounded by
Here the second inequity is from the property of logarithm functions that \(-\ln (1-\alpha )\ge \alpha\) for \(\alpha \in [0,1)\). \(\square\)
The major difference between the convergence results of Corollaries 2.1 and 2.2 are their constants in the bound of number of gradient and operator evaluations. In particular, Corollary 2.1 has a slightly better bound in \(N_h\) and Corollary 2.2 has a slightly better bound in \(N_f\), while both the bounds are in the same order. Since \(M\ge L\) in (1.2) and (1.7), the results obtained in Corollaries 2.1 and 2.2 indicate that the number of gradient evaluations of \(\nabla f\) and \(\nabla h\) that Algorithm 1 requires for computing an \(\varepsilon\)-solution of (1.6) can be bounded by \(\mathcal{O} (\sqrt{L/\varepsilon })\) and \(\mathcal{O} (\sqrt{M/\varepsilon })\), respectively. Such a result is particularly useful when M is significantly larger, e.g., \(M=\mathcal{O} (L/\varepsilon )\), since the number of gradient evaluations of \(\nabla f\) would not be affected at all by the large Lipschitz constant of the whole problem. It is interesting to compare the above result with the best known so-far complexity bound under the traditional black-box oracle assumption. If we treat problem (1.6) as a general smooth convex optimization and study its oracle complexity, i.e., under the assumption that there exists an oracle that outputs \(\nabla \phi (x)\) for any test point x (and \(\nabla \phi (x)\) only), it has been shown that the number of calls to the oracle cannot be smaller than \(\mathcal{O} (\sqrt{(L+M)/\varepsilon })\) for computing an \(\varepsilon\)-solution [28, 32]. Under such “single oracle” assumption, the complexity bounds in terms of gradient evaluations of \(\nabla f\) and \(\nabla h\) are intertwined, and a larger Lipschitz constant M will result in more gradient evaluations of \(\nabla f\), even though there is no explicit relationship between \(\nabla f\) and M. However, the results in Corollaries 2.1 and 2.2 suggest that we can study the oracle complexity of problem (1.6) based on the assumption of two separate oracles: one oracle \(\mathcal{O} _{f}\) to compute \(\nabla f\) for any test point x, and the other one \(\mathcal{O} _{h}\) to compute \(\nabla h(y)\) for any test point y. In particular, these two oracles do not have to be called at the same time, and hence it is possible to obtain separate complexity bounds \(\mathcal{O} (\sqrt{L/\varepsilon })\) and \(\mathcal{O} (\sqrt{M/\varepsilon })\) on the number of calls to \(\mathcal{O} _{f}\) and \(\mathcal{O} _{h}\), respectively.
2.5 Strongly convex extensions
We now consider a special case of (1.6) where f is strongly convex. More specifically, we assume that there exists \(\mu >0\) such that
Under the above assumption, we develop a multi-stage AGS algorithm that can skip computation of \(\nabla f\) from time to time, and compute an \(\varepsilon\)-solution of (1.6) with
gradient evaluations of \(\nabla f\) (see Alagorithm 2). It should be noted that, under the traditional black-box setting [28, 32] where one could only access \(\nabla \phi (x)\) for each inquiry x, the number of evaluations of \(\nabla \phi (x)\) required to compute an \(\varepsilon\)-solution is bounded by
Theorem 2.2 below describes the main convergence properties of the M-AGS algorithm.
Theorem 2.2
Suppose that \(M\ge L\) in (1.7) and (2.49), and that the prox-function \(V(\cdot ,\cdot )\) grows quadratically (i.e., (1.12) holds). If the parameters in Algorithm 2 are set to
then its output \(v_S\) must be an \(\varepsilon\)-solution of (1.1). Moreover, the total number of gradient evaluations of \(\nabla f\) and \(\nabla h\) performed by Algorithm 2 can be bounded respectively by
and
Proof
With input \(x_0=v_{s-1}\) and \(N=N_0\), we conclude from (2.48) in the proof of Corollary 2.2 (with \(u=x^*\) a solution to problem (1.6)) that
where the last inequality follows from (2.52). Using the facts that the input of the AGS algorithm is \(x_0=v_{s-1}\) and that the output is set to \(v_s={\overline{x}}_N\), and the relation (1.12), we conclude
where the last inequality is due to the strong convexity of \(\phi (\cdot )\). It then follows from the above relation, the definition of \(\varDelta _0\) in Algorithm 2, and (2.52) that
Comparing Algorithms 1 and 2, we can observe that the total number of gradient evaluations of \(\nabla f\) in Algorithm 2 is bounded by \(N_0S\), and hence we have (2.53). Moreover, comparing (2.45) and (2.46) in Corollary 2.2, we conclude (2.54). \(\square\)
In view of Theorem 2.2, the total number of gradient evaluations of \(\nabla h\) required by the M-AGS algorithm to compute an \(\varepsilon\)-solution of problem (1.6) is the same as the traditional result (2.51). However, by skipping the gradient evaluations of \(\nabla f\) from time to time in the M-AGS algorithm, the total number of gradient evaluations of \(\nabla f\) is improved from (2.51) to (2.50). Such an improvement becomes more significant as the ratio M/L increases.
3 Application to composite bilinear saddle point problems
Our goal in this section is to show the advantages of the AGS method when applied to our motivating problem, i.e., the composite bilinear saddle point problem in (1.1). In particular, we show in Sect. 3.1 that the AGS algorithm can be used to solve (1.1) by incorporating the smoothing technique in [30] and derive new complexity bounds in terms of the number of gradient computations of \(\nabla f\) and operator evaluations of K and \(K^T\). Moreover, we demonstrate in Sect. 3.2 that even more significant saving on gradient computation of \(\nabla f\) can be obtained when f is strongly convex in (1.1) by incorporating the multi-stage AGS method.
3.1 Saddle point problems
Our goal in this section is to extend the AGS algorithm from composite smooth optimization to nonsmooth optimization. By incorporating the smoothing technique in [30], we can apply AGS to solve the composite saddle point problem (1.1). Throughout this section, we assume that the dual feasible set Y in (1.1) is bounded, i.e., there exists \(y_0\in Y\) such that
is finite, where \(W(\cdot ,\cdot )\) is the prox-function associated with Y with modulus \(\omega\).
Let \(\psi _\rho\) be the smooth approximation of \(\psi\) defined in (1.3). It can be easily shown (see [30]) that
Therefore, if \(\rho =\varepsilon /(2\varOmega )\), then an \((\varepsilon /2)\)-solution to (1.3) is also an \(\varepsilon\)-solution to (1.1). Moreover, it follows from Theorem 1 in [30] that problem (1.3) is given in the form of (1.6) (with \(h(x)=h_{\rho }(x)\)) and satisfies (1.7) with \(M=\Vert K\Vert ^2/(\rho \omega )\). Using these observations, we are ready to summarize the convergence properties of the AGS algorithm for solving problem (1.1).
Proposition 3.1
Let \(\varepsilon > 0\) be given and assume that \(2\Vert K\Vert ^2\varOmega >\varepsilon \omega L\). If we apply the AGS method in Algorithm 1 to problem (1.3) (with \(h=h_{\rho }\) and \(\rho =\varepsilon /(2\varOmega )\)), in which the parameters are set to (2.42)–(2.44) with \(M=\Vert K\Vert ^2/(\rho \omega )\), then the total number of gradient evaluations of \(\nabla f\) and linear operator evaluations of K (and \(K^T\)) in order to find an \(\varepsilon\)-solution of (1.1) can be bounded by
and
respectively.
Proof
By (3.1) we have \(\psi _\rho ^*\le \psi ^*\) and \(\psi (x)\le \psi _\rho (x)+\rho \varOmega\) for all \(x\in X\), and hence
Using the above relation and the fact that \(\rho =\varepsilon /(2\varOmega )\) we conclude that if \(\psi _\rho (x) - \psi _\rho ^*\le \varepsilon /2\), then x is an \(\varepsilon\)-solution to (1.1). To finish the proof, it suffices to consider the complexity of AGS for computing an \(\varepsilon /2\)-solution of (1.3). By Corollary 2.2, the total number of gradient evaluations of \(\nabla f\) is bounded by (3.2). By Theorem 1 in [30], the evaluation of \(\nabla h_{\rho }\) is equivalent to 2 evaluations of linear operators: one computation of form Kx for computing the maximizer \(y^*(x)\) for problem (1.4), and one computation of form \(K^Ty^*(x)\) for computing \(\nabla h_{\rho }(x)\). Using this observation, and substituting \(M=\Vert K\Vert ^2/(\rho \omega )\) to (2.46), we conclude (3.3). \(\square\)
According to Proposition 3.1, the total number of gradient evaluations of \(\nabla f\) and linear operator evaluations of both K and \(K^T\) are bounded by
and
respectively, for computing an \(\varepsilon\)-solution of the saddle point problem (1.1). Therefore, if \(L\le \mathcal{O} (\Vert K\Vert ^2/\varepsilon )\), then the number of gradient evaluations of \(\nabla f\) will not be affected by the dominating term \(\mathcal{O} (\Vert K\Vert /\varepsilon )\). This result significantly improves the best known so-far complexity results for solving the bilinear saddle point problem (1.1) in [30] and [23]. Specifically, it improves the complexity regarding number of gradient computations of \(\nabla f\) from \(\mathcal{O} (1/\varepsilon )\) in [30] to \(\mathcal{O} (1/\sqrt{\varepsilon })\), and also improves the complexity regarding operator evaluations involving K from \(\mathcal{O} (1/\varepsilon ^2)\) in [23] to \(\mathcal{O} (1/\varepsilon )\).
3.2 Strongly convex composite saddle point problems
In this subsection, we still consider the SPP in (1.1), but assume that f is strongly convex (i.e., (2.49) holds). In this case, it has been shown previously in the literature that \(\mathcal{O} (\Vert K\Vert /\sqrt{\varepsilon })\) first-order iterations, each one of them involving the computation of \(\nabla f\), and the evaluation of K and \(K^T\), are needed in order to compute an \(\varepsilon\)-solution of (1.1) (e.g., [29]). However, we demonstrate in this subsection that the complexity with respect to the gradient evaluation of \(\nabla f\) can be significantly improved from \(\mathcal{O} (1/\sqrt{\varepsilon })\) to \(\mathcal{O} (\log (1/\varepsilon ))\).
Such an improvement can be achieved by properly restarting the AGS method applied to to solve a series of smooth optimization problem of form (1.3), in which the smoothing parameter \(\rho\) changes over time. The proposed multi-stage AGS algorithm with dynamic smoothing is stated in Algorithm 3.
Theorem 3.1 describes the main convergence properties of Algorithm 3.
Theorem 3.1
Let \(\varepsilon > 0\) be given and suppose that the Lipschitz constant L in (2.49) satisfies
Also assume that the prox-function \(V(\cdot ,\cdot )\) grows quadratically (i.e., (1.12) holds). If the parameters in Algorithm 3 are set to
then the output \(v_S\) of this algorithm must be an \(\varepsilon\)-solution (1.1). Moreover, the total number of gradient evaluations of \(\nabla f\) and operator evaluations involving K and \(K^T\) performed by Algorithm 3 can be bounded by
and
respectively.
Proof
Suppose that \(x^*\) is an optimal solution to (1.1). By (2.48) in the proof of Corollary 2.2, in the s-th stage of Algorithm 3 (calling AGS with input \(x_0=v_{s-1}\), output \(v_{s}={\overline{x}}_N\), and iteration number \(N=N_0\)), we have
where the last two inequalities follow from (3.6) and (1.12), respectively. Moreover, by (3.1) we have \(\psi (v_s)\le \psi _\rho (v_s)+\rho \varOmega\) and \(\psi ^*=\psi (x^*)\ge \psi _\rho (x^*)\), hence
Combing the above two equations and using the strong convexity of \(\psi (\cdot )\), we have
where the last equality is due to the selection of \(\rho\) in Algorithm 3. Reformulating the above relation as
and summing the above inequalities from \(s=1,\ldots ,S\), we have
where the first inequality follows from the fact that \(\psi (v_0)-\psi ^*\le \varDelta _0\) and the last equality is due to (3.6). By (3.6) and the above result, we have \(\psi (v_S)-\psi ^*\le \varepsilon\). Comparing the descriptions of Algorithms 1 and 3, we can clearly see that the total number of gradient evaluations of \(\nabla f\) in Algorithm 3 is given \(N_0S\), hence we have (3.7).
To complete the proof it suffices to estimate the total number of operator evaluations involving K and \(K^T\). By Theorem 1 in [30], in the s-th stage of Algorithm 3, the number of operator evaluations involving K is equivalent to twice the number of evaluations of \(\nabla h_\rho\) in the AGS algorithm, which, in view of (2.46) in Corollary 2.2, is given by
where we used the relation \(M=\Vert K\Vert ^2/(\rho \omega )\) (see Sect. 3.1) in the first equality and relations \(\rho =2^{-s/2}\rho _0\) and \(N=N_0\) from Algorithm 3 in the last equality. It then follows from the above result and (3.6) that the total number of operator evaluations involving K in Algorithm 3 can be bounded by
\(\square\)
By Theorem 3.1, the total number of operator evaluations involving K performed by Algorithm 3 to compute an \(\varepsilon\)-solution of (1.6) can be bounded by
which matches with the best-known complexity result (e.g., [29]). However, the total number of gradient evaluations of \(\nabla f\) is now bounded by
which drastically improves existing results from \(\mathcal{O} (1/\sqrt{\varepsilon })\) to \(\mathcal{O} (\log (1/\varepsilon ))\).
4 Numerical experiments
For preliminary numerical experiments of the proposed AGS method, we consider the following total-variation (TV) regularized image reconstruction problem:
Here \(x\in \mathbb {R}^n\) is the n-vector form of a two-dimensional image to be reconstructed, \(\Vert Dx\Vert _{2,1}\) is the discrete form of the TV semi-norm where D is the finite difference operator, A is a measurement matrix describing the physics of data acquisition, and b is the observed data. It should be noted that problem (4.1) is equivalent to
where \(Y:=\{y\in \mathbb {R}^{2n}:\Vert y\Vert _{2,\infty }:=\max _{i=1,\ldots ,n}\Vert (y^{(2i-1)}, y^{(2i)})^T\Vert _2\le 1\}\). The above form can be viewed as a special case of the bilinear SPP (1.1) with
and the associated constants are \(L=\lambda _{max}(A^TA)\) and \(\Vert K\Vert =\eta \sqrt{8}\) (see, e.g., [5]). Therefore, as discussed in Sect. 3.1, such problem can be solved by AGS after incorporating the smoothing technique in [30] and approximate the above problem to the form (1.3).
In this experiment, the dimension of \(A\in \mathbb {R}^{m\times n}\) is set to \(m=\lceil n/3\rceil\). Each component of A is generated from a Bernoulli distribution, namely, it takes equal probability for the values \(1/\sqrt{m}\) and \(-1/\sqrt{m}\) respectively. We generate b from a ground truth image \(x_{true}\) with \(b=Ax_{true}+\varepsilon\), where \(\varepsilon \sim N(0,0.001I_n)\). Two ground truth images \(x_{true}\) are used in the experiment, namely, the 256 by 256 (\(n=65536\)) image “Cameraman” and the 135 by 198 (\(n=26730\)) image “Onion”. Both of them are built-in test images in the MATLAB image processing toolbox.
The parameters of Algorithm 1 are set to Proposition 3.1 for solving the above bilinear SPP through smoothing. In order to demonstrate the efficiency of the AGS algorithm, we compare it with Nesterov’s accelerated gradient method (NEST) in [32]. Note that AGS and NEST are both applied to the smoothed problem (1.3). We compare the performance of AGS and NEST for each test image with different smoothing parameter \(\rho\) in (1.3), and TV regularization parameter \(\eta\) in (4.1). For both algorithms, the prox-functions V(x, u) and W(y, v) are set to Euclidean distances \(\Vert x-u\Vert _2^2/2\) and \(\Vert y-v\Vert _2^2/2\) respectively. In order to perform a fair comparison, we run NEST for 200 iterations first, and then run AGS with the same amount of CPU time. The performances of AGS and NEST are compared through their respective relative errors \((\psi _{AGS}-\psi ^*)/{\psi ^*}\) and \((\psi _{NEST}-\psi ^*)/{\psi ^*}\), where \(\psi _{AGS}\) and \(\psi _{NEST}\) are the objective values of (4.1) corresponding to the approximated solutions computed by AGS and NEST respectively. Here the optimal objective value \(\psi ^*\) is approximated by running AGS with 2000 evaluation of \(\nabla f\).
Tables 1 and 2 show the comparison between AGS and NEST in terms of gradient evaluations of \(\nabla f\), operator evaluations of K and \(K^T\), and objective values (4.1). It should be noted that in 200 iterations of the NEST algorithm, the number of gradient evaluations of \(\nabla f\) and operator evaluations of K and \(K^T\) are given by 200 and 400, respectively. We can make a few observations about the results reported in these tables. First, by skipping gradient evaluations of \(\nabla f\), AGS is able to perform more operator evaluation of K and \(K^T\) during the same amount of CPU time. Noting the complexity bounds (3.4) and (3.5), we can observe that the extra amount of operator evaluations K and \(K^T\) can possibly result in better approximate solutions obtained by CGS in terms of objective values. It should be noted that in problem (4.1), A is a dense matrix while D is a sparse matrix. Therefore, a very large number of extra evaluations of K and \(K^T\) can be performed for each skipped gradient evaluation of \(\nabla f\). Second, for the smooth approximation problem (1.3), the Lipschitz constant M of \(h_{\rho }\) is given by \(M=\Vert K\Vert ^2/{\rho \omega }\). Therefore, for the cases with \(\rho\) being fixed, larger values of \(\eta\) result in larger norm \(\Vert K\Vert\), and consequently larger Lipschitz constant M. Moreover, for the cases when \(\eta\) is fixed, smaller values of \(\rho\) also lead to larger Lipschitz constant M. For both cases, as the ratio of M/L increases, we would skip more and more gradient evaluations of \(\nabla f\), and allocate more CPU time for operator evaluations of K and \(K^T\), which results in more significant performance improvement of AGS over NEST. Such observations are also consistent with our previous theoretical complexity analysis regarding AGS and NEST for solving composite bilinear saddle point problems.
Noting that problem (4.1) is a common problem in imaging science, we also compare AGS and NEST with the best result among a few commonly used primal-dual (PD) algorithms in the field. Specifically, we use \(\psi _{PD}\) to denote the best objective value computed by the following algorithms: a modified version of primal-dual hybrid gradient (PDHG) method [1, 37] (see, e.g., [7] for an introduction on PDHG algorithms), an overrelaxed primal-dual method [12, 15], and an inertial primal-dual method [25]. Our implementation of the PD algorithms is based on [8] since it studies all the aforementioned algorithms (see Algorithms 1–3 within).Footnote 1 Since our main objective in this experiment is to demonstrate the effectiveness of AGS over NEST on evaluations of \(\nabla f\) and \(\nabla h\), we do not list all the results computed by the aforementioned PD algorithms, but only simply use \(\psi _{PD}\) to denote the smallest objective value computed by all PD algorithms among all possible relaxation and inertial parameters under either ergodic or non-ergodic iterates. We can observe that AGS outperforms PD algorithms significantly in all the experiments.
5 Concluding remarks
We propose an accelerated gradient sliding (AGS) method for solving certain classes of structured convex optimization. The main feature of the proposed AGS method is that it could skip gradient computations of a smooth component in the objective function from time to time, while still maintaining the overall optimal rate of convergence for these probems. In particular, for minimizing the summation of two smooth convex functions, the AGS method can skip the gradient computation of the function with a smaller Lipschitz constant, resulting in sharper complexity results than the best known so-far complexity bound under the traditional black-box assumption. Moreover, for solving a class of bilinear saddle-point problem, by applying the AGS algorithm to solve its smooth approximation, we show that the number of gradient evaluations of the smooth component may be reduced to \(\mathcal{O} (1/\sqrt{\varepsilon })\), which improves the previous \(\mathcal{O} (1/\varepsilon )\) complexity bound in the literature. More significant savings on gradient computations can be obtained when the objective function is strongly convex, with the number of gradient evaluations being reduced further to \(\mathcal{O} (\log (1/\varepsilon ))\). Numerical experiments further confirm the potential advantages of these new optimization schemes for solving structured convex optimization problems.
A few potential future works are in place. First, although the theoretical performance of the proposed AGS method is better than Nesterov’s accelerated gradient method when \(M\gg L\), the complexities developed in Corollaries 2.1 and 2.2 have slightly worse universal constant factors than that of Nesterov’s method. Specifically, for the non-strongly convex smooth case of problem (1.6), applying a version of Nesterov’s method to solve problem (e.g., Theorem 2.2.2 in [32]) we can obtain an \(\varepsilon\)-solution within \(2\sqrt{(M+L)V(x_0,x^*)/(\nu \varepsilon )}\) gradient evaluations of both f and h. Theoretically, the bounds for gradient evaluations of f from Nesterov’s method is worse than that in Corollary 2.1 when \(M\ge 8L\). However, when \(M\le 7L\), the bounds for both gradient evaluations of f and h from Nesterov’s method are better than that of the proposed AGS method. Similar observations can be made for Corollary 2.1 and also later for Corollary 3.1. Since the main purpose of this paper is to develop a theoretical possibility of solving composite convex optimization using two separated gradient oracles instead of treating them jointly, the authors leave it as a future work to study whether the proposed AGS method can be further improved so that its performance is similar or better than that of Nesterov’s method when \(M\le 7L\). Second, it should be noted that the proposed AGS method does not address the sliding of strongly convex smooth optimization problems in the most straightforward way. Specifically, the proposed M-AGS algorithm described in Algorithm 2 is a multi-stage restarting scheme that applies the AGS algorithms \(\mathcal{O} (\log (1/\varepsilon ))\) times. It is a potential future work to study whether one could directly exploit the strong convexity and develop an algorithm that incorporates the strong convexity parameters into the update rules of the parameters. Third, in Algorithm 3 we use an adaptive strategy for choosing the smoothing parameter \(\rho\). Such strategy is a key factor that contributes to the improved convergence properties of Algorithm 3 in strongly convex problems. It is interesting to study whether such adaptive smoothness parameter strategy can also be applied to the non-strongly convex cases to improve practical performance while maintaining the same theoretical convergence properties.
Notes
See Sect. s 7.1.3 in [8] for the settings on relaxation and inertial parameters; note that \(\rho =2\) and \(\alpha =1/3\) are not applicable for problem (4.1). The stepsize parameter in [8] are chosen as the following: \(\sigma =1/\Vert K\Vert\), and \(\tau\) is the largest value that satisfies convergence conditions (16), (23), or (26) in [8].
References
Arrow, K., Hurwicz, L., Uzawa, H.: Studies in Linear and Non-linear Programming. Stanford Mathematical Studies in the Social Sciences. Stanford University Press (1958). http://books.google.com/books?id=jWi4AAAAIAAJ
Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16(3), 697–725 (2006)
Becker, S., Bobin, J., Candès, E.: NESTA: a fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4(1), 1–39 (2011)
Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3), 200–217 (1967)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89–97 (2004)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)
Chambolle, A., Pock, T.: An introduction to continuous optimization for imaging. Acta Numerica 25, 161–319 (2016)
Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159(1), 253–287 (2016)
Chen, Y., Lan, G., Ouyang, Y.: Accelerated schemes for a class of variational inequalities. arXiv preprint arXiv:1403.4164 (2014)
Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optim. 24(4), 1779–1814 (2014)
d’Aspremont, A.: Smooth optimization with approximate gradient. SIAM J. Optim. 19(3), 1171–1183 (2008)
Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1–3), 293–318 (1992)
Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015–1046 (2010)
Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: a generic algorithmic framework. SIAM J. Optim. 22(4), 1469–1492 (2012)
He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci. 5(1), 119–149 (2012)
He, B., Yuan, X.: On the O(1/n) convergence rate of the Douglas-Rdachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700–709 (2012)
He, N., Juditsky, A., Nemirovski, A.: Mirror prox algorithm for multi-term composite minimization and alternating directions. arXiv preprint arXiv:1311.1098 (2013)
He, Y., Monteiro, R.D.: Accelerating block-decomposition first-order methods for solving generalized saddle-point and nash equilibrium problems. Optimization-online preprint (2013)
He, Y., Monteiro, R.D.: An accelerated hpe-type algorithm for a class of composite convex-concave saddle-point problems. Submitt. SIAM J. Optim. (2014)
Hoda, S., Gilpin, A., Pena, J., Sandholm, T.: Smoothing techniques for computing nash equilibria of sequential games. Math. Oper. Res. 35(2), 494–512 (2010)
Juditsky, A., Nemirovski, A., Tauvel, C.: Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011)
Lan, G.: Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Math. Program. 149(1), 1–45 (2015)
Lan, G.: Gradient sliding for composite optimization. Math. Program. 159(1–2), 201–235 (2016)
Lan, G., Lu, Z., Monteiro, R.D.: Primal-dual first-order methods with \(\cal{O}(1/\epsilon )\) iteration-complexity for cone programming. Math. Program. 126(1), 1–29 (2011)
Lorenz, D.A., Pock, T.: An inertial forward-backward algorithm for monotone inclusions. J. Math. Imaging Vis. 51(2), 311–325 (2015)
Monteiro, R.D., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475–507 (2013)
Nemirovski, A.: Prox-method with rate of convergence \({O}(1/t)\) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1), 229–251 (2004)
Nemirovski, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics, Wiley, New York (1983)
Nesterov, Y.: Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16(1), 235–249 (2005)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127–152 (2005)
Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence \(O(1/k^2)\). Doklady AN SSSR 269, 543–547 (1983)
Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwell (2004)
Ouyang, H., He, N., Tran, L., Gray, A.G.: Stochastic alternating direction method of multipliers. In: Proceedings of the 30th International Conference on Machine Learning (ICML-13), pp. 80–88 (2013)
Ouyang, Y., Chen, Y., Lan, G., Eduardo Pasiliao, J.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644–681 (2015)
Ouyang, Y., Xu, Y.: Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Program. 185(1), 1–35 (2021)
Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Submitt. SIAM J. Optim. (2008)
Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Report, pp. 08–34 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Guanghui Lan is partially supported by National Science Foundation Grants 1319050, 1637473 and 1637474, and Office of Naval Research Grant N00014-16-1-2802. Yuyuan Ouyang is partially supported by US Dept. of the Air Force Grant FA9453-19-1-0078 and Office of Naval Research Grant N00014-19-1-2295.
Rights and permissions
About this article
Cite this article
Lan, G., Ouyang, Y. Accelerated gradient sliding for structured convex optimization. Comput Optim Appl 82, 361–394 (2022). https://doi.org/10.1007/s10589-022-00365-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-022-00365-z