Semi-Monotone Goldstein Line Search Strategy with Application in Sparse Recovery
Shima Shabani, Michael Breuß · 2025
Read Semi-Monotone Goldstein Line Search Strategy with Application in Sparse Recovery by Shima Shabani, Michael Breuß (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-2503-13099.txt.
Introduction
Shima Shabani and Michael Breuss present a new way to pick step sizes when a computer solves a hard math problem, in a paper from 2025. Their method builds on a classic rule but lets the search take larger steps when it is far from the best answer. The problems they target are curved in shape but not smooth.
The authors prove the method will reach a fixed point, and will do so at a steady rate when the problem is strongly curved. They test it on tasks where a signal must be rebuilt from few measures. In those tests it matched or beat leading methods, with strong speed. The work may help fields that rely on sparse data.
Catalog record
| CREATOR | Shima Shabani, Michael Breuß |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-13099
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Semi-Monotone Goldstein Line Search Strategy with Application in Sparse Recovery Shima Shabani, Michael Breuß Abstract Line search methods are a prominent class of iterative methods to solve unconstrained minimization problems. These methods produce new iterates utilizing a suitable step size after determining proper directions for minimization. In this paper we propose a semi-monotone line search technique based on the Goldstein quotient for dealing with convex non-smooth optimization problems. The method allows to employ large step sizes away from the optimum thus improving the efficacy compared to standard Goldstein approach. For the presented line search method, we prove global convergence to a stationary point and local R-linear convergence rate in strongly convex cases. We report on some experiments in compressed sensing. By comparison with several state-of-the-art algorithms in the field, we demonstrate the competitive performance of the proposed approach and specifically its high efficiency. 1 Introduction Line search methods are popular methods in unconstrained optimization [ 15 ] . They typically have the format of an iterative method combining a direction of the iteration with a suitable step size. Effective choices of both direction and step size are key to success and robustness of the line search approach. Given a suitable direction, monotone line search methods aim to ensure that a descent in the objective function takes place, while non-monotone line search methods permit some growth in the function value, see e.g. [ 11 ] . The non-monotone techniques represent a relaxation of monotone line searching in a way that beneficial properties related to monotone methods like global convergence may be preserved, while they help to improve the chance of finding a global optimum and in the convergence speed [ 23 ] . To select a practical step size, it is helpful to consider appropriate conditions to make sufficient decrease of the objective function. Popular conditions as discussed e.g. in [ 15 ] are the conditions proposed by Armijo [ 1 ] , Wolfe [ 21 ] , or Goldstein [ 10 ] . As it is well-known, the Armijo condition confirms the sufficient decrease for a given scheme even if the step size is very small, which may result in the scheme being inefficient. The Wolfe condition overcomes this problem by considering additionally the local curvature, but this comes at the expense of a considerably higher computational cost. The Goldstein condition prevents too small step sizes by making a possible lower bound explicit, which may eventually lead to higher computational efficiency compared to use of Wolfe condition. As the setting for line search methods we consider in this paper the unconstrained optimization problem \begin{array}[]{ll}\min&~F(x)=f(x)+\mu c(x)\\ \textrm{s.t.}&~x\in\mathbb{R}^{n}\end{array} (1) where the function f(x) is convex and smooth, the regularization c(x) is a convex and non-smooth function, and the parameter \mu\in\mathbb{R^{+}} realizes a trade-off specification between the objective terms. One particular form of ( 1 ) that is of high interest in some contexts is the basis pursuit denoising problem [ 5 , 6 , 8 ] , denoted as \begin{array}[]{ll}\min&~F(x)=\frac{1}{2}\|Ax-b\|^{2}+\mu\|x\|_{1}\\ \textrm{s.t.}&~x\in\mathbb{R}^{n}\end{array} (2) Here \|\cdot\| is the standard Euclidean norm, \|\cdot\|_{1} stands for the \ell_{1} -norm, and A\in\mathbb{R}^{m\times n} (m\ll n) and b\in\mathbb{R}^{m} are often called the measurement matrix and the observation vector, respectively. The model problem ( 2 ) gives the sparsest solution of the underdetermined linear system Ax=b when the measurements are noisy, meaning that it is desired that almost all the coefficients of the linear combination form are zero. Compressed sensing [ 6 , 8 ] , a technique for efficiently acquiring and reconstructing a signal, is an actual field of application for ( 2 ). Our contribution and relation to previous work. We build upon recent work on optimization methods relying on the Goldstein quotient [ 9 ] . The works [ 13 , 14 ] present an improved version of the Goldstein technique similarly to our underlying approach, but limited to smooth optimization problems. With respect to non-smooth optimization, the most important work related to this paper is given by [ 17 ] . There an efficient method utilizing a monotone Goldstein technique has been deviced for dealing with the basis pursuit denoising problem, proving global and R-linear local convergence in that setting. In the current paper, we propose a new extension of technique proposed in [ 17 ] that enables relaxation towards larger step sizes during minimization. As the novel technique keeps the lower bound of the monotone version of Goldstein’s condition at the same time, we denote it here as semi-monotone Goldstein strategy. For theoretical validation we prove global and R-linear local convergence of the resulting line search method in the setting of a general convex non-smooth regularization function as in ( 1 ). This is a considerably more general setting as in previous work [ 17 ] , as convergence proofs given there rely on a monotone Goldstein technique and are also limited to the shrinkage operation for regularization as in ( 2 ). In addition to our new theoretical results we present a detailed evaluation of randomized numerical experiments that show the beneficial properties of our approach compared to the scheme proposed in [ 17 ] as well as its competitive performance with several state-of-the-art optimization methods. 2 Review of Important Techniques We consider a general iterative method that seeks the minimum of ( 1 ) and produces to this end a sequence \{x_{k}\}_{k\geq 0} by the line search rule. In the following, the components of line search iteration and related concepts are briefly summarized for later use. The basic line search scheme at an iteration index k reads as x_{k+1}\,=\,x_{k}+\alpha_{k}d_{k} (3) and it features the direction d_{k} and a positive step size \alpha_{k} . For ( 1 ), the descent in the objective function in direction d_{k} from current iterate x_{k} can be measured by \Delta_{k}=d_{k}^{T}\nabla f_{k}+\mu\Big(c(x_{k}+d_{k})-c_{k}\Big)<0 (4) As for the notation in ( 4 ), for a function like h(x) , h_{k} is the function value at x_{k} or k th iterate, and \nabla h_{k} is the corresponding gradient value. The Goldstein condition for a non-smooth optimization strategy can be summarized, using 0<\theta_{1}<\theta_{2}<1 , as F_{k}+\theta_{2}\alpha_{k}\Delta_{k}\leq F_{k+1}\leq F_{k}+\theta_{1}\alpha_{k}\Delta_{k} (5) In [ 17 ] an efficient monotone line search technique for ( 1 ) is presented in the sense of Warth & Werner [ 19 ] . This means, in each iteration, the step size \alpha_{k} is chosen such that the following quotient has a fixed positive lower bound \gamma \Big(F_{k}-F_{k+1}\Big)\frac{\|d_{k}\|^{2}}{\Delta_{k}^{2}}>\gamma>0 (6) for all k\geq 0 with descent direction d_{k} as d_{k}=x_{k}^{+}-x_{k},~~~~x_{k}^{+}=\mathscr{P}_{c}(x_{k}-\tau_{k}\nabla f(x_{k}),\mu\tau_{k}) (7) Here \mathscr{P}_{c}(x,\vartheta)=\textrm{argmin}_{y}\Big\{\vartheta c(y)+\frac{1}{2}\|x-y\|^{2}\Big\} (8) is the proximal operator [ 16 ] of the scaled function c(y) at x with \vartheta>0 , and \tau_{k} is a dynamic parameter employed as a step size for the implicit gradient descent step such that 0<\tau_{\min}\leq\tau_{k}\leq\tau_{\max}<\infty (9) To estimate \alpha_{k} in ( 3 ), the authors of [ 17 ] consider the non-smooth Goldstein quotient \nu(\alpha_{k})=\frac{F_{k+1}-F_{k}}{\alpha_{k}\Delta_{k}} (10) by imposing the following monotone sufficient descent condition \nu(\alpha_{k})\left|\nu(\alpha_{k})-1\right|\,\geq\,\theta (11) for a fixed \theta>0 . Based on ( 11 ), \nu(\alpha_{k}) is supposed to be sufficiently positive and far from one to control the step size from below. 3 Semi-Monotone Goldstein Strategy As indicated, the idea presented in this paper extends the monotone line search method in