An Accelerated Proximal Bundle Method with Momentum Zhuoqing Zheng, Junshan Yin, Shaofu Yang, Xuyang Wu Abstract Proximal bundle methods (PBM) are a powerful class of algorithms for convex optimization. Compared to gradient descent, PBM constructs more accurate surrogate models that incorporate gradients and function values from multiple past iterations, which leads to faster and more robust convergence. However, for smooth convex problems, PBM only achieves an O ⁡ ( 1 / k ) O(1/k) convergence rate, which is inferior to the optimal O ⁡ ( 1 / k 2 ) O(1/k^{2}) rate. To bridge this gap, we propose an accelerated proximal bundle method (APBM) that integrates Nesterov’s momentum into PBM. We prove that under standard assumptions, APBM achieves the optimal O ⁡ ( 1 / k 2 ) O(1/k^{2}) convergence rate. Numerical experiments demonstrate the effectiveness of the proposed APBM. I Introduction This article addresses the unconstrained convex optimization problem: \underset{x\in\mathbb{R}^{n}}{\operatorname{minimize}}~~f(x), (1) where f:\mathbb{R}^{n}\rightarrow\mathbb{R} is convex and differentiable. This problem has found numerous applications in machine learning [ 24 ] , control system [ 1 ] , and signal processing [ 17 ] . A large number of algorithms have been proposed to solve problem ( 1 ), among which a typical method is gradient descent (GD) [ 3 ] , which minimizes the proximal linear model (first-order Taylor expansion plus a proximal term) of the objective function f at each iteration. However, the proximal-linear model can be a crude approximation of the objective function, which further leads to slow convergence. To enhance GD, the proximal bundle method (PBM) [ 15 , 7 , 18 ] incorporates a proximal bundle model into the update. Compared to the proximal linear model, the proximal bundle model incorporates historical objective values and gradients to achieve a higher approximation accuracy [ 18 ] . Compared to GD, PBM not only converges fast but also exhibits extraordinary robustness in the step-size [ 12 ] . For this reason, a growing body of works extends PBM to solve optimization problems with different structures [ 26 , 4 , 11 , 6 ] . Another effective approach for improving GD is to incorporate Nesterov’s momentum scheme into the update, resulting in the accelerated gradient descent (AGD) [ 20 , 2 , 8 ] . Compared with GD, AGD employs the gradient descent step at the specific linear combination (controlled by momentum coefficient) of the previous two points, but rather at the most recent point. AGD achieves the O(1/k^{2}) convergence rate for convex smooth optimization, which is also the optimal rate that can attained by gradient-based methods under this setting [ 19 , Section 2.1.2] . Inspired by the extraordinary performance of momentum scheme, [ 2 ] extends it to solve the problem with composite structure, [ 25 ] applies it to primal-dual algorithms, and [ 13 ] adapts it to the distributed optimization. While PBM exhibits excellent convergence performance, its convergence rate, for convex smooth problems, is typically of O(1/k) [ 18 , 7 ] , rather than the optimal rate O(1/k^{2}) . On the other hand, AGD achieves the optimal rate but its update still relies on a gradient descent step that can potentially lead to slow convergence and lack of robustness. A natural idea is to combine PBM with AGD, taking advantage of both to obtain a better algorithm. Although this idea is also explored in the existing works [ 16 , 9 ] , they both include an internal loop that complicates the algorithm. This article incorporates the momentum scheme into the PBM, resulting in an accelerated proximal bundle method (APBM) that can attain the accelerated O(1/k^{2}) convergence rate while maintaining the robustness of PBM. The main contributions of this paper are as follows: 1) We propose an accelerated proximal bundle method that combines PBM with the momentum scheme. Compared to [ 16 , 9 ] , our method does not include any inner loop, which yields a simpler form. 2) We provide a convergence rate of O(1/k^{2}) for our algorithm under standard assumptions. 3) We demonstrate the practical advantages of our method by numerical experiments. The remaining part of this paper is organized as follows: Section II develops the algorithm and Section III analyses the convergence. Section IV illustrates the practical advantages of our method through numerical experiments, and Section V concludes the paper. Notations and definitions. We denote by \langle\cdot,\cdot\rangle the Euclidean inner product and use \|\cdot\| to represent the Euclidean norm for vectors and the spectral norm for matrices. For any differentiable f:\mathbb{R}^{n}\rightarrow\mathbb{R} , \nabla f(x)\in\mathbb{R}^{n} represents its gradient at x . We use \mathbf{1} to denote the all-one vector of proper dimensions. For a differentiable function f , we say it is L -smooth for some L>0 if \|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|\quad\forall x,y\in\mathbb{R}^{n}, and it is \mu -strongly convex for some \mu>0 if \langle\nabla f(x)-\nabla f(y),x-y\rangle\geq\mu\|x-y\|^{2}\quad\forall x,y\in\mathbb{R}^{n}. II Algorithm This section is organized into three parts. First, we develop the algorithm, which involves a surrogate model \hat{f}^{k} and a subproblem at each iteration. Next, we discuss options of \hat{f}^{k} . Finally, we show that the resulting subproblems can be solved efficiently via dual approaches.. II-A Algorithm development The algorithm is developed based on the proximal bundle method (PBM) and Nesterov’s momentum scheme. PBM : At each iteration k\geq 0 , it updates as [ 7 , 18 ] : x^{k+1}=\arg\min_{x}~\hat{f}^{k}(x)+\frac{1}{2\gamma}\|x-x^{k}\|^{2}, where \hat{f}^{k} is a minorant of f satisfying \hat{f}^{k}(x)\leq f(x) for all x\in{\mathbb{R}}^{n} and \gamma>0 is the step-size. A typical example of \hat{f}^{k} is the cutting-plane model [ 14 ] : \hat{f}^{k}(x)=\max_{t\in S^{k}}\{f(x^{t})+\langle\nabla f(x^{t}),x-x^{t}\rangle\}, where S^{k}\subseteq\{1,\dots,k\} is an index set that contains k . When S^{k}=\{k\} , the proximal bundle model reduces to the first-order Taylor expansion of f and PBM becomes gradient descent (GD). The use of multiple cutting planes yields a higher approximation accuracy of \hat{f}^{k} on f compared to the first-order Taylor expansion: since f(x)\geq\hat{f}^{k}(x)\geq f(x^{k})+\langle\nabla f(x^{k}),x-x^{k}\rangle , we have f(x)-\hat{f}^{k}(x)\leq f(x)-(f(x^{k})+\langle\nabla f(x^{k}),x-x^{k}\rangle), which is also clear from Fig. 1 (b). The higher approximation accuracy yields not only faster convergence but also stronger robustness in the step-size [ 12 ] . Nesterov’s momentum scheme : It is a powerful technique in enhancing the performance of first-order methods, and an example is accelerated gradient descent (AGD) [ 20 , 2 , 8 ] , which achieves the optimal O(1/k^{2}) convergence rate for smooth convex optimization. By assuming L -smooth f for some L>0 , the AGD in [ 2 ] updates as: Set y^{1}=x^{0} and t_{1}=1 . For each k\geq 1 , \displaystyle x^{k}=y^{k}-\frac{1}{L}\nabla f(y^{k}), (2) \displaystyle t_{k+1}=\frac{1+\sqrt{1+4t_{k}^{2}}}{2}, (3) \displaystyle y^{k+1}=x^{k}+\frac{t_{k}-1}{t_{k+1}}(x^{k}-x^{k-1}). (4) The algorithm maintains three sequences: the iterative sequence \{x^{k}\} , coefficient sequence \{t^{k}\} , and the extrapolated sequence \{y^{k}\} . Compared with GD, AGD performs a gradient descent step at the extrapolated point y^{k} rather than x^{k} . This extrapolation sequence \{y^{k}\} is generated by the linear combination of the two most recent iterations x^{k} and x^{k-1} , with the coefficient \{t_{k}\} controlling the momentum strength. Both the proximal bundle model and Nesterov’s momentum scheme can significantly improve the performance of GD. Therefore, a natural idea is to combine them for better performance. We keep the updates of the extrapolated sequence \{y^{k}\} and the coefficient sequence \{t_{k}\} in AGD ( 2 )–( 4 ), and incorporate the proximal bundle step into the update of x^{k} , leading to x^{k}=\arg\min_{x}~\hat{f}^{k}(x)+\frac{L}{2}\|x-y^{k}\|^{2}. (5) We refer to the algorithm with ( 5 ), ( 3 ), and ( 4 ) as the Accelerated Proximal Bundle Method (APBM), where a detailed implementation is described in Algorithm 1 . Remark 1 . The works [ 16 , 9 ] also incorporate Nesterov’s acceleration into PBM. However, both methods involve an inner loop that iterates until a prescribed condition is satisfied, which increases algorithmic complexity. In contrast, our method eliminates the need for such inner loops and admits a simpler structure. (a) Polyak (b) Cutting-plane (c) Polyak cutting-plane Fig. 1 : Surrogate functions in the Polyak model ( 6 ), cutting-plane model ( 7 ), and the Polyak cutting-plane model ( 8 ) Algorithm 1 Accelerated Proximal Bundle Method (APBM) 1: Initialization: x^{0}\in\mathbb{R}^{n},~y^{1}=x^{0},~t_{1}=1 . 2: for k=1,2,\ldots do 3: x^{k}=\arg\min_{x}~\hat{f}^{k}(x)+\frac{L}{2}\|x-y^{k}\|^{2} . 4: t_{k+1}=\frac{1+\sqrt{1+4t_{k}^{2}}}{2} . 5: y^{k+1}=x^{k}+\frac{t_{k}-1}{t_{k+1}}(x^{k}-x^{k-1}) . 6: end for II-B Candidates of the model \hat{f}^{k} The performance of APBM relies on the selection of the bundle model \hat{f}^{k} and, in general, we prefer models that yield a high approximation accuracy on f and a low computational cost of solving ( 5 ). In this subsection, we introduce several candidates of \hat{f}^{k} satisfying the following assumption, which requires \hat{f}^{k} to be a convex minorant of f and a majorant of the cutting plane at y^{k} and will be used in Section III for convergence analysis. Assumption 1 . The model \hat{f}^{k} satisfies (a) \hat{f}^{k} is convex; (b) \hat{f}^{k}(x)\geq f(y^{k})+\langle\nabla f(y^{k}),x-y^{k}\rangle for all x\in{\mathbb{R}}^{n} ; (c) \hat{f}^{k}(x)\leq f(x) for all x\in{\mathbb{R}}^{n} . Below, we provide several candidates of \hat{f}^{k} that satisfy Assumption 1 , where three of them are visualized in Fig. 1 . • Polyak model : This model originates from the Polyak step-size [ 22 ] for gradient descent and takes the form of \hat{f}^{k}(x)=\max\{f(y^{k})+\langle\nabla f(y^{k}),x-y^{k}\rangle,\ell_{f}\} (6) where \ell_{f} is a known lower bound of f . This model and its variants are shown to be particularly effective in stochastic optimization [ 23 ] . • Cutting-plane model : It takes the maximum of historical cutting planes [ 14 ] : \hat{f}^{k}(x)=\max_{t\in S^{k}}~f(y^{t})+\langle\nabla f(y^{t}),x-y^{t}\rangle (7) where S^{k}\subseteq\{0,1,\ldots,k\} is a subset of historical iteration indexes containing k . The model is adopted in the cutting-plane method [ 14 ] and is also typical in the proximal bundle method [ 4 ] . • Polyak cutting-plane model : It takes the maximum of the Polyak model and the cutting-plane model: \hat{f}^{k}(x)=\max\{\ell_{f},\max_{t\in S^{k}}~f(y^{t})+\langle\nabla f(y^{t}),x-y^{t}\rangle\} (8) where all the parameters are introduced below ( 6 ) and ( 7 ). • Two-cut model : This model is defined in an iterative way. It sets \hat{f}^{1}(x)=f(y^{1})+\langle\nabla f(y^{1}),x-y^{1}\rangle and takes the maximum of the cutting planes of f at y^{k} and \hat{f}^{k-1} at x^{k-1} for k\geq 2 : \begin{split}\hat{f}^{k}(x)=&\max\{\hat{f}^{k-1}(x^{k-1})+\langle\hat{g}^{k-1},x-x^{k-1}\rangle,\\ &f(y^{k})+\langle\nabla f(y^{k}),x-y^{k}\rangle\}\end{split} (9) where \hat{g}^{k-1}=L(y^{k-1}-x^{k-1})\in\partial\hat{f}^{k-1}(x^{k-1}) . The models ( 6 )–( 9 ) incorporate historical information or lower bounds to approximate f . Compared to the first-order Taylor expansion, they can yield a higher approximation accuracy (see Fig. 1 ). The following lemma shows that the models ( 6 )–( 9 ) satisfy Assumption 1 . Lemma 1 . Suppose that f is convex and differentiable. Then, the four models ( 6 )–( 9 ) satisfy Assumption 1 . Proof. See Appendix -A . ∎ II-C Solving the subproblem ( 5 ) The efficiency of the algorithm heavily relies on that of solving the subproblem ( 5 ). In this subsection, we show that for piece-wise linear \hat{f}^{k} , such as the four options in Section II-B , the subproblem ( 5 ) can be solved quickly. For simplicity, we rewrite the update ( 5 ) with a piece-wise linear \hat{f}^{k} as \underset{x}{\operatorname{minimize}}~\max_{i\in\{1,\dots,M\}}\{a_{i}^{T}x+b_{i}\}+\frac{L}{2}\|x-y^{k}\|^{2}, (10) where M is the number of affine functions in \hat{f}^{k} and a_{i}^{T}+b_{i} is the i -th affine function. Taking the cutting-plane model ( 7 ) as an example, \displaystyle a_{i}=\nabla f(y^{t_{i}}),~~~~~b_{i}=f(y^{t_{i}})-\langle\nabla f(y^{t_{i}}),y^{t_{i}}\rangle, where t_{i} is the i th element in S^{k} . By letting A=(a_{1},\ldots,a_{M})^{T}\in{\mathbb{R}}^{M\times n},\quad b=(b_{1};\ldots;b_{M})\in{\mathbb{R}}^{M}, (11) problem ( 10 ) can be equivalently transformed into \begin{split}\underset{x,\theta}{\operatorname{minimize}}~~&~\theta+\frac{L}{2}\|x-y^{k}\|^{2}\\ \operatorname{subject~to}~&~Ax+b\leq\theta\mathbf{1}.\end{split} (12) If the dimension n of x is small, then problem ( 12 ) can be easily solved by primal methods such as interior-point methods [ 10 ] . In case the dimension n of x is large, dual methods become more preferable for solving problem ( 12 ). By [ 12 , Lemma 2.4.1] , the dual problem of ( 12 ) is \begin{split}&\underset{\lambda\in\mathbb{R}^{M}}{\operatorname{maximize}}~~~~~~q(\lambda)\\ &\operatorname{subject~to}~~~~\lambda\geq 0,~\mathbf{1}^{T}\lambda=1,\end{split} (13) where q(\lambda)=-\frac{1}{2L}\|A^{T}\lambda\|^{2}+\langle\lambda,Ay^{k}+b\rangle . Problem ( 13 ) is a QP with dimension M , which is typically small (e.g., 5 or 10 ) in practical implementations. Therefore, compared to directly solving the primal problem ( 10 ), solving the dual problem ( 13 ) can admit a much low computational cost especially when M\ll n . Moreover, problem ( 13 ) can be solved by gradient-based approaches, such as projected gradient descent [ 3 ] , because both the gradient computation and the projection operation is simple. To see this, note that by letting x_{\lambda}=y^{k}-\frac{1}{L}A^{T}\lambda , we have \nabla q(\lambda)=Ax_{\lambda}+b. Moreover, the projection onto the simplex constraint set can be executed efficiently ( O(M) ) [ 5 ] . Once an optimum \lambda^{\operatorname{opt}} of ( 13 ) is solved, the optimum of ( 12 ) can be recovered by x^{\operatorname{opt}}=y^{k}-\frac{1}{L}A^{T}\lambda^{\operatorname{opt}}. When n=10,000 and M=10 , applying projected gradient descent to solve ( 13 ) only takes \approx 0.08 second to reach the x^{\operatorname{opt}} of ( 12 ) with 10^{-10} accuracy on a PC with the AMD Ryzen 7 CPU. III Convergence Analysis In this section, we analyse the convergence of APBM. To this end, we impose an assumption on problem ( 1 ). Assumption 2 . The following holds: (a) The function f:\mathbb{R}^{n}\rightarrow\mathbb{R} is convex and L -smooth for some L>0 . (b) Problem ( 1 ) has at least one optimal solution x^{\star} . Assumption 2 is standard in the analysis of gradient-based methods [ 3 , 2 , 16 ] . Under this problem setting, GD and PBM attain an O(1/k) convergence rate [ 3 , 18 , 7 ] , while AGD could achieve the O(1/k^{2}) convergence rate. The following theorem demonstrates that the function value error f(x^{k})-f(x^{\star}) can be upper bounded by t_{k} that generated by ( 3 ). Theorem 1 . Suppose that Assumptions 1 – 2 hold. Let \{x^{k}\} be generated by APBM (Algorithm 1 ). Then, for any k\geq 1 , f(x^{k})-f(x^{\star})\leq\frac{L\|x^{0}-x^{\star}\|^{2}}{2t_{k}^{2}}. (14) Proof. See Appendix -B . ∎ To establish the relationship between the function value error and the number of iterations, the following technical lemma provides a crucial lower bound of t_{k} , which implies that t_{k} grows linearly with the iteration number. Lemma 2 . [ 2 , Lemma 4.3] Let \{t_{k}\} be generated by ( 3 ) with t_{1}=1 . Then, for any k\geq 1 , t_{k}\geq\frac{k+1}{2}. (15) Based on the Theorem 1 and Lemma 2 , below we provide the final result. Corollary 1 . Suppose all the conditions in Theorem 1 hold. Then, for any k\geq 0 , f(x^{k})-f(x^{\star})\leq\frac{2L\|x^{0}-x^{\star}\|^{2}}{(k+1)^{2}}. (16) Proof. See Appendix -C . ∎ APBM achieves the optimal O(1/k^{2}) convergence rate for convex and smooth optimization [ 19 , Section 2.1.2] . APBM generalizes AGD and the convergence result is the same order as AGD [ 20 , 2 ] . However, due to the use of more accurate models, APBM can yield much faster convergence and stronger robustness, which will be shown numerically in Section IV . (a) Convergence of GD, PBM ( m=15 ), AGD, and APBM ( m=15 ) (b) Final optimality residual of APBM after 2000 iterations with the step-size \gamma=\alpha/L where L=\|E\|^{2}/N Fig. 2 : Convergence performance in solving the least squares problem ( 17 ) (a) Convergence of GD, PBM ( m=15 ), AGD, and APBM ( m=15 ) (b) Final optimality residual of APBM after 2000 iterations with the step-size \gamma=\alpha/L , where L=\|E\|^{2}/N Fig. 3 : Convergence performance (with restart scheme) in solving the least squares problem ( 17 ) IV Numerical Example We demonstrate the performance of our method in solving the following least squares problem: \underset{x\in\mathbb{R}^{n}}{\operatorname{minimize}}~~\frac{1}{2N}\|Ex-w\|^{2}, (17) where N=800 , n=800 , and E\in\mathbb{R}^{N\times n} , w\in\mathbb{R}^{N} are randomly generated. We compare GD, PBM, AGD, and APBM in solving ( 17 ). The experiment settings are as follows: Both PBM and APBM adopt the cutting-plane model ( 7 ) with S_{k}=[k-m+1,k] . For the updates ( 2 ) and ( 5 ) in AGD and APBM, we rewrite them as \displaystyle x^{k+1} \displaystyle=\operatorname{\arg\;\min}_{x}f(y^{k})\!+\!\langle\nabla f(y^{k}),x\!-\!y^{k}\rangle\!+\!\frac{1}{2\gamma}\|x\!-\!y^{k}\|^{2}, \displaystyle x^{k+1} \displaystyle=\operatorname{\arg\;\min}_{x}\hat{f}^{k}(x)+\frac{1}{2\gamma}\|x-y^{k}\|^{2}, respectively, where \gamma>0 is referred to as step-size and the above updates reduce to ( 2 ) and ( 5 ) when \gamma=1/L . We first compare the convergence speed where the step-size in all methods are fine-tuned for better performance and then test the robustness of the algorithms with respect to the step-size \gamma . The experimental results are plotted in Fig 2 , which demonstrate that APBM takes the advantages of AGD and PBM: 1) By utilizing the Nesterov’s momentum scheme, APBM converges faster than PBM (at least 3x faster); 2) Benefiting from the more accurate proximal bundle model, APBM has stronger robustness than AGD, which eases parameter selection. In particular, AGD is equivalent to APBM with m=1 and diverges when step-size \geq 1.4/L , whereas APBM with m=10 allows for 4/L . To further improve the performance, we incorporate a fixed-restart scheme [ 21 ] into both AGD and APBM, where t_{k} is set to 1 every 500 iterations. The results are displayed in Fig 3 . Compared with Fig. 2 , the restart scheme enhances the performance of both methods; however, the improvement is more substantial for APBM. This suggests that APBM benefits more from the restart scheme, leading to faster convergence than AGD. Moreover, the restart scheme preserves the strong robustness of APBM with respect to the step-size. V Conclusion We proposed an APBM that integrates Nesterov’s momentum scheme into the classical PBM. The proposed algorithm achieves the optimal O(1/k^{2}) convergence rate for convex and smooth problems while preserving the robustness and fast convergence properties of PBM. We provided the theoretical convergence guarantee under standard assumptions and demonstrated the fast convergence and robustness through numerical experiments. We consider further accelerating APBM by introducing additional mechanisms such as restart schemes and establishing their theoretical guarantees, as our future work. -A Proof of Lemma 1 Since \hat{f}^{k} in ( 6 )–( 9 ) are the maximum of affine functions, they are convex and satisfy Assumption 1 (a). Assumption 1 (b) is straightforward to see from the forms of \hat{f}^{k} in ( 6 )–( 9 ). To show Assumption 1 (c), note that since f is convex, f(x)\geq f(y^{t})+\langle\nabla f(y^{t}),x-y^{t}\rangle,\quad\forall t\in S^{k}, i.e., f(y^{t})+\langle\nabla f(y^{t}),x-y^{t}\rangle,t\in S^{k} are minorants of f . Moreover, \ell_{f}\leq\min_{x}f(x) . Therefore, the models ( 6 )–( 8 ) take the maximum of minorants of f , which yields \hat{f}^{k}(x)\leq f(x) . For \hat{f}^{k} in ( 9 ), we show \hat{f}^{k}\leq f by induction. By the convexity of f and y^{1}=x^{0} , the initial model \hat{f}^{1}(x)=f(x^{0})+\langle\nabla f(x^{0}),x-x^{0}\rangle\leq f(x). Assume that for some k\geq 1 , we have \hat{f}^{k}(x)\leq f(x) . By f(x)\geq\hat{f}^{k}(x) and the convexity of \hat{f}^{k} , we have that for any \hat{g}^{k}\in\partial\hat{f}^{k}(x^{k}) , f(x)\geq\hat{f}^{k}(x)\geq\hat{f}^{k}(x^{k})+\langle\hat{g}^{k},x-x^{k}\rangle, which, together with the convexity of f , yields \begin{split}\hat{f}^{k+1}(x)=&\max\{\hat{f}^{k}(x^{k})+\langle\hat{g}^{k},x-x^{k}\rangle,\\ &f(y^{k})+\langle\nabla f(y^{k}),x-y^{k}\rangle\}\\ \leq&f(x).\end{split} Concluding all the above, Assumption 1 (c) holds for all k\geq 1 . -B Proof of Theorem 1 For any k\geq 0 , define \phi^{k+1}(x)=\hat{f}^{k+1}(x)+\frac{L}{2}\|x-y^{k+1}\|^{2}. By Assumption 1 (a) and the L -strong convexity of \frac{L}{2}\|x-y^{k+1}\|^{2} , \phi^{k+1}(x) is L -strongly convex. This together with x^{k+1}=\arg\min_{x}\phi^{k+1}(x) yield \phi^{k+1}(x^{k+1})-\phi^{k+1}(x)\leq-\frac{L}{2}\|x^{k+1}-x\|^{2},~~\forall x\in\mathbb{R}^{n}. (18) By Assumption 1 (b) and the smoothness of f , we have \begin{split}&\phi^{k+1}(x^{k+1})\\ =&\hat{f}^{k+1}(x^{k+1})+\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}\\ \geq&f(y^{k+1})+\langle\nabla f(y^{k+1}),x^{k+1}-y^{k+1}\rangle\\ &+\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}\\ \geq&f(x^{k+1}).\end{split} (19) By Assumption 1 (c), \begin{split}\phi^{k+1}(x)&=\hat{f}^{k+1}(x)+\frac{L}{2}\|x-y^{k+1}\|^{2}\\ &\leq f(x)+\frac{L}{2}\|x-y^{k+1}\|^{2}.\end{split} (20) Substituting ( 19 ) and ( 20 ) into ( 18 ), we have f(x^{k+1})-f(x)\leq\frac{L}{2}\|x-y^{k+1}\|^{2}-\frac{L}{2}\|x-x^{k+1}\|^{2}. (21) Moreover, \begin{split}&\frac{L}{2}\|x-y^{k+1}\|^{2}-\frac{L}{2}\|x-x^{k+1}\|^{2}\\ =&\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}+L\langle x-x^{k+1},x^{k+1}-y^{k+1}\rangle.\end{split} Therefore, \begin{split}&f(x^{k+1})-f(x)\\ \leq&\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}+L\langle x-x^{k+1},x^{k+1}-y^{k+1}\rangle.\end{split} Letting x=x^{k} and x=x^{\star} respectively, we obtain \begin{split}&f(x^{k+1})-f(x^{k})\\ \leq&\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}+L\langle x^{k}-x^{k+1},x^{k+1}-y^{k+1}\rangle,\end{split} (22) \begin{split}&f(x^{k+1})-f(x^{\star})\\ \leq&\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}+L\langle x^{\star}-x^{k+1},x^{k+1}-y^{k+1}\rangle.\end{split} (23) For conciseness, let v^{k}=f(x^{k})-f(x^{\star}) . To get a relationship between v^{k+1} and v^{k} , we multiply ( 22 ) by (t_{k+1}-1) and add the resulting equation to ( 23 ), which yields \begin{split}&t_{k+1}v^{k+1}-(t_{k+1}-1)v^{k}\\ \leq&L\langle(t_{k+1}-1)(x^{k}-x^{k+1})+x^{\star}-x^{k+1},x^{k+1}-y^{k+1}\rangle\\ &+t_{k+1}\frac{L}{2}\|x^{k+1}-y^{k+1}\|^{2}.\end{split} Multiplying both sides of the above inequality by t_{k+1} and using t_{k}^{2}=t_{k+1}(t_{k+1}-1) , we obtain \begin{split}&t_{k+1}^{2}v^{k+1}-t_{k}^{2}v^{k}\leq\frac{L}{2}\|\underbrace{t_{k+1}(x^{k+1}-y^{k+1})}_{\mathbf{b}}\|^{2}\\ +&L\langle\underbrace{(t_{k+1}-1)x^{k}-t_{k+1}x^{k+1}+x^{\star}}_{\mathbf{a}},\underbrace{t_{k+1}(x^{k+1}-y^{k+1}}_{\mathbf{b}})\rangle.\end{split} By \|\mathbf{a}+\mathbf{b}\|^{2}-\|\mathbf{a}\|^{2}=2\langle\mathbf{a},\mathbf{b}\rangle+\|\mathbf{b}\|^{2} , it follows that \begin{split}&t_{k+1}^{2}v^{k+1}-t_{k}^{2}v^{k}\leq\frac{L}{2}\|x^{\star}+(t_{k+1}-1)x^{k}-t_{k+1}y^{k+1}\|^{2}\\ &-\frac{L}{2}\|x^{\star}+(t_{k+1}-1)x^{k}-t_{k+1}x^{k+1}\|^{2}.\end{split} (24) By ( 4 ), we have t_{k+1}y^{k+1}=t_{k+1}x^{k}+(t_{k}-1)(x^{k}-x^{k-1}) , substituting which into ( 24 ) gives \begin{split}&t_{k+1}^{2}v^{k+1}-t_{k}^{2}v^{k}\leq\frac{L}{2}\|x^{\star}+(t_{k}-1)x^{k-1}-t_{k}x^{k}\|^{2}\\ &-\frac{L}{2}\|x^{\star}+(t_{k+1}-1)x^{k}-t_{k+1}x^{k+1}\|^{2}.\end{split} Using t_{1}=1 and applying telescoping cancellation on the above equation yields that for all k\geq 1 , \displaystyle t_{k}^{2}v^{k}-v^{1} \displaystyle\leq\frac{L}{2}\|x^{\star}+(t_{1}-1)x^{0}-t_{1}x^{1}\|^{2} \displaystyle=\frac{L}{2}\|x^{\star}-x^{1}\|^{2}. By v^{k}=f(x^{k})-f(x^{\star}) , ( 21 ), and y^{1}=x^{0} , we have that for all k\geq 1 \begin{split}&t_{k}^{2}(f(x^{k})-f(x^{\star}))\\ \leq&f(x^{1})-f(x^{\star})+\frac{L}{2}\|x^{\star}-x^{1}\|^{2}\\ \leq&\frac{L}{2}\|x^{\star}-y^{1}\|^{2}-\frac{L}{2}\|x^{\star}-x^{1}\|^{2}+\frac{L}{2}\|x^{\star}-x^{1}\|^{2}\\ =&\frac{L}{2}\|x^{\star}-x^{0}\|^{2},\end{split} which implies ( 14 ). -C Proof for Corollary 1 Substituting ( 15 ) into ( 14 ) yields that for all k\geq 1 f(x^{k})-f(x^{\star})\leq\frac{2L\|x^{\star}-x^{0}\|^{2}}{(k+1)^{2}}. (25) Next, we discuss the case of f(x^{0})-f(x^{\star}) . By the smoothness of f , we obtain f(x^{0})-f(x^{\star})\leq\frac{L}{2}\|x^{0}-x^{\star}\|^{2}\leq 2L\|x^{0}-x^{\star}\|^{2}. (26) Combining ( 26 ) with ( 25 ) results in ( 16 ).