We introduce two novel randomized iterative regularization frameworks, termed \texttt{RIGKT} and \texttt{RIAT}, for solving large-scale linear ill-posed inverse problems governed by systems of equations. The proposed methods combine randomized iterated Tikhonov regularization with Krylov subspace projection techniques, utilizing Golub--Kahan bidiagonalization for general rectangular systems (\texttt{RIGKT}) and Arnoldi decomposition for square systems (\texttt{RIAT}). Unlike existing deterministic schemes that rely on fixed iteration counts, our framework incorporates randomized equation selection, an adaptive step-size strategy, and a global, discrepancy-based a posteriori early-stopping rule tailored specifically to the stochastic setting. We present a comprehensive regularization analysis establishing Bregman-distance monotonicity, finite termination, exact-data convergence, and pathwise stability under noise. Furthermore, we prove that the stopped iterates converge almost surely and in the mean-square sense to the true solution, establishing a rigorous regularization property. To the best of our knowledge, this is the first theoretical framework to simultaneously account for randomization, Krylov-subspace dimension reduction, and implementable early stopping. Numerical experiments involving two-dimensional X-ray computed tomography (CT) and image deblurring demonstrate that \texttt{RIGKT} and \texttt{RIAT} reliably reconstruct structural features across various noise regimes.
Ada-BPSG is introduced, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate and yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces.
Chenhan Jin, Shengze Xu, Binghui Xie et al.· 0 citations
Cubic regularized Newton methods have the optimal $\mathcal{O}(\epsilon^{-3/2})$ global rate, but a dense subproblem solve limits the feasible block size. Scalable Cubic Newton variants replace the true block curvature with a diagonal, low-rank, Kronecker-factored, or sketched surrogate and, most often, give up the exact cubic step. We introduce a blockwise optimizer that minimizes an independent cubic model per parameter tensor over the true block Hessian, under a per-block adaptive cubic constant and a monotone guard on the full loss. Arbitrarily large tensors are handled matrix-free in a Lanczos-built Krylov subspace, where we prove that the step minimizes the cubic model. The theory also supplies the $\mathcal{O}(\epsilon^{-3/2})$ iteration complexity bound, a second-order guarantee, and monotone per-block descent. Four variants of this outer scheme are evaluated against the original adaptive regularization with cubics (ARC) optimizer, some other recent cubic Newton variants, Adam, SOAP, and L-BFGS. On a 91.4M-parameter implicit neural representation (INR), the variants introduced in this work are the only evaluated here cubic Newton methods whose steps stay exact on every block. Run to full convergence on FINER 2D image fitting, one of the ARC variants introduced here, ARC-$\varphi_1$, reaches 133.5 dB peak signal-to-noise ratio, while tuned Adam plateaus at 78.2 dB after about 70 minutes. In that time ARC-$\varphi_1$ reaches 95.6 dB.
A novel convergence analysis framework for the BPGM with the Shannon entropy kernel is developed, yielding strong convergence results for a broad class of objective functions under linear constraints.
A globally convergent regularized Newton method with positive definite regularization for solving nonsmooth optimization problems that replaces the identity matrix in traditional algorithms with a general positive-definite symmetric matrix to regularize the generalized Hessian.
We develop a unified analysis of inexact stochastic Riemannian proximal optimization for finite-sum nonsmooth composite problems over compact embedded submanifolds. The framework accommodates variance-reduced gradient estimators, projected momentum, and inexact tangent-space proximal solves under a single conditional error-dissipation condition, verified for projection-based SVRG, SARAH/SPIDER, SAGA, and SAG. A computable Fenchel-dual residual criterion, with tolerance prescribed before sampling and inner iterations, enables explicit control of the inner work. We establish conditional expected descent, subsequential stationarity, and an \(O(\epsilon^{-2})\) outer complexity. With SARAH/SPIDER and accumulative regularization, iRPMVR attains \(O(n+\sqrt n\,\epsilon^{-2})\) component-gradient and \(O(\epsilon^{-3})\) proximal-operator complexities. We further develop an abstract KL principle for conditional expected descent with memory and summable tails using only the ordinary pointwise KL property. A counterexample shows that a power-type expected-KL implication used in earlier stochastic analyses can fail. The principle yields almost-sure finite length, whole-sequence convergence, and deterministic KL rates.
The randomized Kaczmarz (RK) method is an efficient iterative projection algorithm with low computational complexity for solving consistent linear systems. However, noise is inevitable in real-world applications, and both the coefficient matrix and the right-hand side vector may be contaminated by noise. The convergence analysis of RK-type methods for doubly noisy linear systems, where both the system matrix and the measurement vector are perturbed, remains relatively limited. In this paper, we investigate the limiting behavior of the RK algorithm for solving doubly noisy inconsistent linear systems without imposing any additional initial assumptions. Furthermore, to the best of our knowledge, this work provides the first convergence analysis of the randomized extended Kaczmarz (REK), randomized block Kaczmarz (RBK), and randomized double block Kaczmarz (RDBK) algorithms for doubly noisy linear systems. We prove that these algorithms converge to a neighborhood of the least-squares solution of the underlying noiseless system. Compared with existing theoretical estimates, the proposed bounds effectively characterize the convergence behavior of these algorithms when applied to doubly noisy linear systems. Finally, numerical experiments are conducted to validate the theoretical results.
Yudan Gan, Gang Wu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
