An accelerated randomized Bregman-Kaczmarz method for strongly convex linearly constraint optimization*
Lionel Tondji, Dirk A. Lorenz, Ion Necoara · 2025
Read An accelerated randomized Bregman-Kaczmarz method for strongly convex linearly constraint optimization* by Lionel Tondji, Dirk A. Lorenz, Ion Necoara (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-2504-01160.txt.
Introduction
Lionel Tondji, Dirk Lorenz, and Ion Necoara wrote this optimization paper, published in two thousand twenty-five, on minimizing a strongly convex function under linear constraints. Their method is of Kaczmarz type: each step uses just one of the constraint equations, picked at random.
Speed comes from a duality trick. The Kaczmarz method is the mirror image of coordinate descent, where acceleration schemes are well understood. The authors port a recent accelerated coordinate method across the mirror to the primal side. The new method keeps the source method's worst-case speed guarantees. A full convergence analysis is included. In numerical tests the method ran faster and more efficiently than existing rivals on the same problems. The paper suits huge problems where touching every constraint each step is out of the question.
Catalog record
| CREATOR | Lionel Tondji, Dirk A. Lorenz, Ion Necoara |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01160
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An accelerated randomized Bregman-Kaczmarz method for strongly convex linearly constraint optimization* Lionel Tondji, Dirk A. Lorenz, Ion Necoara Abstract In this paper, we propose a randomized accelerated method for the minimization of a strongly convex function under linear constraints. The method is of Kaczmarz-type, i.e. it only uses a single linear equation in each iteration. To obtain acceleration we build on the fact that the Kaczmarz method is dual to a coordinate descent method. We use a recently proposed acceleration method for the randomized coordinate descent and transfer it to the primal space. This method inherits many of the attractive features of the accelerated coordinate descent method, including its worst-case convergence rates. A theoretical analysis of the convergence of the proposed method is given. Numerical experiments show that the proposed method is more efficient and faster than the existing methods for solving the same problem. I Introduction We consider the fundamental problem of approximating solutions of large scale linear systems of the form: \mathbf{A}x=b (1) with matrix \mathbf{A}\in\mathbb{R}^{m\times n} and right hand side b\in\mathbb{R}^{m} . We consider the case that the full matrix is not accessible simultaneously, but that one can only work with single rows of the system ( 1 ) at a time. Such problems arise in several fields of engineering and physics problems, such as sensor networks, signal processing, partial differential equations, filtering, computerized tomography, optimal control, inverse problems and machine learning, to name just a few [ 28 , 20 , 23 , 9 , 10 , 21 ] . Given the possibility of multiple solutions of ( 1 ), we set out to find the unique solution, characterized by the function f , i.e. f^{*}\overset{\text{def}}{=}\min_{x\in\mathbb{R}^{n}}f(x)\quad\text{subject to}\quad\mathbf{A}x=b, (2) with a strongly convex function f . However, we will not assume smoothness of f . One possible example is f(x)=\lambda\cdot\|x\|_{1}+\frac{1}{2}\|x\|^{2}_{2} and it is known that this function favors sparse solutions for appropriate choices of \lambda>0 , see [ 2 , 29 , 13 , 14 , 24 ] . We assume throughout the paper that both m and n are large and that the system is consistent. We denote by a_{i}^{T} the rows of \mathbf{A} and assume a_{i}\neq 0 for all i\in[m]:=\{1,\dots,m\} . Since f is strongly convex, problem ( 2 ) has a unique solution \hat{x} . In applications, it is usually sufficient to find a point which is not too far from \hat{x} . In particular, one chooses the error tolerance \varepsilon>0 and aims to find a point x satisfying \|x-\hat{x}\|_{2}\leq\varepsilon . Since our method will be a stochastic method, and hence, the iterates x are random vectors. Hence, our goal will be to compute approximate solutions of ( 2 ) that fulfills \mathbb{E}[\|x-\hat{x}\|_{2}]\leq\varepsilon , where \mathbb{E}[\cdot] denotes the expectation w.r.t. randomness of the algorithm. I-A Related work The linear system ( 1 ) may be so large that full matrix operations are very expensive or even infeasible. Then, it appears desirable to use iterative algorithms with low computational cost and storage per iteration that produce good approximate solutions of ( 2 ) after relatively few iterations. The Kaczmarz method [ 11 ] and its randomized variants [ 26 , 8 , 7 , 16 ] are used to compute the minimum \ell_{2} -norm solutions of consistent linear systems. In each iteration k , a row vector a_{i}^{\top} of \mathbf{A} is chosen at random from the system ( 1 ) and the current iterate x_{k} is projected onto the solution space of that equation to obtain x_{k+1} . Note that this update rule requires low cost per iteration and storage of order \mathcal{O}(n) . Recently, a new variant of the randomized Kaczmarz (RK) method namely the randomized sparse Kaczmarz method (RSK) [ 14 , 24 ] with almost the same low cost and storage requirements has shown good performance in approximating sparse solutions of large consistent linear systems. The papers [ 13 , 24 ] analyze this method by interpreting it as a sequential, randomized Bregman projection method (where the Bregman projection is done with respect to the function f ) while [ 22 ] connects it with the coordinate descent method via duality. Variations of RSK including block/averaging variants [ 18 , 22 , 16 , 4 , 15 ] , averaging methods [ 27 ] and adaptions to least squares problems are given in [ 30 , 3 , 25 ] . In those variants, one usually needs to have access to more than one row of the matrix \mathbf{A} at the cost of increasing the memory. Coordinate descent methods are often considered in the context of minimizing composite convex objective functions [ 17 , 19 , 6 ] . At each iteration, they update only one coordinate of the vector of variable, hence using partial derivatives rather than the whole gradient. A randomized accelerated coordinate descent method was proposed in [ 19 ] for smooth functions. Accelerated methods transform the proximal coordinate descent, for which the optimality gap decreases as \mathcal{O}(1/k) , into an algorithm with optimal \mathcal{O}(1/k^{2}) complexity under mild additional computational cost [ 19 , 6 ] . I-B Contribution To the best of our knowledge, accelerated Bregman-Kaczmarz variants have not yet been proposed and analyzed in the literature. Specifically, we make the following contributions: • Beyond interpreting the Bregman-Kaczmarz method as a dual coordinate descent, we propose an accelerated variant using only one row of the matrix. We refer to it as Accelerated Randomized Bregman-Kaczmarz method (ARBK) with more details in Algorithm 3 . • By exploiting the connection between primal and dual updates, we obtain convergence as a byproduct and convergence rates which have not been available so far. We prove that our accelerated method leads to faster convergence than its standard counterpart. • We also validate this empirically and we provide implementations of our algorithm in Python . I-C Outline. The remainder of the paper is organized as follows. Section II provides notations, a brief overview on convexity and Bregman distances. In Section III we state our method and we give an interpretation of it in the dual space. Section IV provides convergence guarantees for our proposed method. In Section V , numerical experiments demonstrate the effectiveness of our method and provide insight regarding its behavior and its hyper-parameters. Finally, Section VI draws some conclusions. II Notation and basic notions For integers m we denote [m]\overset{\text{def}}{=}\{1,2,\dots,m\} . Given a symmetric positive definite matrix \mathbf{B}, we denote the induced inner product by \langle x,y\rangle_{\mathbf{B}}\overset{\text{def}}{=}\langle x,\mathbf{B}y\rangle=\sum_{i,j\in[n]}x_{i}\mathbf{B}_{ij}y_{j},\quad x,y\in\mathbb{R}^{n} and its induced norm by \|.\|_{\mathbf{B}}^{2}\overset{\text{def}}{=}\langle\cdot,\cdot\rangle_{\mathbf{B}} and use the short-hand notation \|.\|_{2} to mean \|.\|_{\mathbf{I}} . For an n\times m real matrix \mathbf{A} we denote by \mathcal{R}(\mathbf{A}),\|\mathbf{A}\|_{F} and a_{i}^{\top} its range space, its Frobenius norm and its i -th row, respectively. By e_{i} we denote the i th column of the identity matrix \mathbf{I}_{n}\in\mathbb{R}^{n\times n} . For a random vector x_{i} that depends on a random index i (where i is chosen with probability p_{i} ) we denote \mathbb{E}[x_{i}]\overset{\text{def}}{=}\sum_{i\in[q]}p_{i}x_{i} and we will just write \mathbb{E}[x_{i}] when the probability distribution is clear from the context. Given a vector x\in\mathbb{R}^{n} , we define the soft shrinkage operator, which acts componentwise on a vector x as \big(S_{\lambda}(x))_{j}=\max\{|x_{j}|-\lambda,0\}\cdot\sign(x_{j})\,. (3) Now we collect some basic notions on