A First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex

Chee-Khian Sim · 2025

Read A First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex by Chee-Khian Sim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13302.txt.

Introduction

Chee-Khian Sim published a paper in 2025 speeding up a workhorse optimization algorithm for problems that might secretly be convex. The target problems add a possibly nonconvex smooth part to a convex, possibly jagged part, a shape common in modern data fitting. Sim modifies the accelerated method FISTA, built for exactly this split, and analyzes its worst-case effort to reach a stated accuracy.

In the general case the method needs effort growing like the inverse square of the tolerance, the standard grade. When the objective turns out convex, the same algorithm automatically improves to a far better rate, with matching asymptotic refinements. Practitioners gain a single method that is safe on hard problems and fast on kind ones, with proofs rather than hope.

Catalog record

CREATORChee-Khian Sim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-13302

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex Chee-Khian Sim Abstract We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is the sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of 𝒪 ⁡ ( ϵ − 2 ) \mathcal{O}(\epsilon^{-2}) to find an ϵ \epsilon -approximate solution to the problem, and this complexity improves to 𝒪 ( ϵ − 2 / 3 ) \mathcal{O}(\epsilon^{-2/3}) when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case o ⁡ ( ϵ − 2 ) o(\epsilon^{-2}) iterations to find an ϵ \epsilon -approximate solution to the problem, with worst case o ( ϵ − 2 / 3 ) o(\epsilon^{-2/3}) iterations when its objective function is convex. Keywords. Fast iterative shrinkage thresholding algorithm (FISTA); nonconvex optimization problem; convex optimization problem; iteration complexity; asymptotic convergence rate. 1 Introduction First order methods are frequently used to solve optimization problems, especially when these problems are large scale [ 1 ] . Fast iterative shrinkage thresholding algorithm (FISTA), a first order method, is proposed in [ 2 ] to solve a convex minimization problem whose objective function is the sum of two convex functions, where one function can be nonsmooth; see also [ 19 , 21 , 22 ] . Algorithms, including first order algorithms, to solve minimization problems whose objective functions are nonconvex are also studied in the literature (see for example [ 4 ] ). The objective function can be a sum of two functions, where one function is nonconvex, has Lipschitz continuous gradient, and the other function is convex, but nonsmooth. Solving this minimization problem has application in areas such as training a neural network, as discussed for example in [ 8 ] . Existing works that study first order algorithms on nonconvex optimization problems include [ 3 , 6 , 7 , 11 , 13 , 14 , 15 , 16 , 17 , 27 ] . In the works mentioned in the previous paragraph, such as [ 6 , 17 ] , the iteration complexity to find an \epsilon -approximate solution to the nonconvex optimization problem, whose objective function is the sum of two functions, where one function can be nonconvex, has Lipschitz continuous gradient, and the other function is convex, but nonsmooth, is shown to be \mathcal{O}(\epsilon^{-2}) . This is also the iteration complexity found for the first order algorithm, which is a modified version of FISTA, proposed in this paper on the optimization problem. Our algorithm also has the added feature that when the objective function to the problem turns out to be convex, it is able to “detect” this and its iteration complexity improves to \mathcal{O}(\epsilon^{-2/3}) . In [ 6 ] , the iteration complexity of the algorithm there also improves to \mathcal{O}(\epsilon^{-2/3}) when the objective function is convex, but the parameter inputs to the algorithm need to be adjusted accordingly. In [ 7 ] , the authors improve on [ 6 ] by introducing a parameter free accelerated gradient method to solve nonconvex optimization problems, although the authors only show optimal complexity on function values when the objective function is convex. In [ 17 ] , the accelerated composite gradient (ACG) variant introduced in the paper reduces to FISTA when the objective function is convex. The algorithm in this paper however is different from that in [ 17 ] in the way nonconvexity is handled, with different analysis as well. As with the algorithm in [ 17 ] , our algorithm performs exactly one resolvent evaluation of h in each iteration, unlike papers found in the literature such as [ 6 ] , where its ACG variant requires two resolvent evaluations of h in each iteration. We note that in [ 24 ] , Nesterov’s accelerated gradient method is shown to have the iteration complexity of \mathcal{O}(\epsilon^{-2/3}) when the objective function consists only of a single convex function with Lipschitz continuous gradient. The approach for analysis in the paper is via high-resolution differential equations. In this paper, we also provide asymptotic convergence rate 1 1 1 The study of asymptotic convergence is not new. For example, local superlinear convergence of interior point methods has been analyzed by researchers [ 10 , 18 , 20 , 23 , 25 , 26 ] . results for our algorithm, both when the objective function is nonconvex and convex. Our asymptotic convergence rate for the convex case is also found in [ 5 ] through high-resolution differential equations. In our case, we analyze our algorithm directly to obtain the result. In the recent published paper [ 9 ] , the authors show that it takes o(\epsilon^{-2}) iterations to find an \epsilon -approximate solution to a nonconvex optimization problem using steepest descent algorithm and other linesearch methods. In this paper, we add further to this by showing asymptotic convergence rate of o(n^{-1/2}) for our algorithm, a first order algorithm of the accelerated type 2 2 2 Examples of first order algorithms of the accelerated type on nonconvex optimization problems include accelerated composite gradient variants [ 17 ] and accelerated proximal gradient methods as found in [ 13 ] . , when we solve the nonconvex optimization problem we considered in the paper, under the assumption of convergence of iterates. To the best of our knowledge, this is the first time asymptotic convergence rate result is presented on first order algorithms of the accelerated type when solving nonconvex optimization problems. In the next section, Section 2 , we introduce the optimization problem we are solving in this paper, and also present the first order algorithm we are proposing to solve the problem. In Section 3 , we state and prove results that are needed for the iteration complexities and asymptotic convergence rate results in its next section and associated subsection. We conclude the paper with Section 5 . 1.1 Notations and facts Given \Omega a closed convex set of \Re^{n} , we denote the standard projection map from \Re^{n} onto \Omega by P_{\Omega}(\cdot) . We have the following result on P_{\Omega} : \displaystyle\|P_{\Omega}(x)-y\|\leq\|x-y\|, (1) where x\in\Re^{n} and y\in\Omega . The following is a simple fact used in this paper: \displaystyle\|a-b\|^{2}-2\langle a-b,a-c\rangle+\|a-c\|^{2}=\|b-c\|^{2}, (2) where a,b,c\in\Re^{n} . Given functions f:\mathcal{S}\rightarrow\mathbb{Z}_{++} and g:\mathcal{S}\rightarrow\Re_{++} , where \mathcal{S} is an arbitrary set. For a subset \hat{\mathcal{S}}\subseteq\mathcal{S} , we write f(w)=\mathcal{O}(g(w)) for all w\in\hat{\mathcal{S}} to mean that f(w)\leq Mg(w) for all w\in\hat{\mathcal{S}} , where M>0 is a positive constant. For \hat{\mathcal{S}}=(0,w_{0}] , where w_{0}>0 , we write f(w)=o(g(w)) to mean that f(w)/g(w)\rightarrow 0 , as w\rightarrow 0 . 2 An Optimization Problem and Modified FISTA We consider the following optimization problem: \displaystyle\min_{y\in\Re^{n}}\phi(y):=f(y)+h(y), (3) where f can be nonconvex on \Omega\subset\Re^{n} , has Lipschitz continuous gradient with Lipschitz constant L , and \Omega is a closed convex set in \Re^{n} . Hence, we have \displaystyle\|\nabla f(u_{1})-\nabla f(u_{2})\|\leq L\|u_{1}-u_{2}\|,\ \forall\ u_{1},u_{2}\in\Omega. As a consequence, the following holds: \displaystyle|f(u_{1})-l_{f}(u_{1};u_{2})|\leq\frac{L}{2}\|u_{1}-u_{2}\|^{2},\ \forall\ u_{1},u_{2}\in\Omega, (4) where \displaystyle\ell_{f}(u_{1};u_{2}):=f(u_{2})+\langle\nabla f(u_{2}),u_{1}-u_{2}\rangle. In particular, \displaystyle f(u_{1})-l_{f}(u_{1};u_{2})\leq\frac{L}{2}\|u_{1}-u_{2}\|^{2},\ \forall\ u_{1},u_{2}\in\Omega. (5) Furthermore, h is a proper

Read the complete text