Randomized batch-sampling Kaczmarz methods for general linear systems

• URL: http://arxiv.org/abs/2511.09872v1
• Date: Fri, 14 Nov 2025 01:14:34 GMT
• Title: Randomized batch-sampling Kaczmarz methods for general linear systems
• Authors: Dong-Yue Xie, Xi Yang,
• Abstract summary: We adopt a unified randomized batch-sampling Kaczmarz framework with per-iteration costs as low as cyclic block methods.<n>We develop a general analysis technique to establish its convergence guarantee.
• Score: 4.909043927828085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To conduct a more in-depth investigation of randomized solvers for general linear systems, we adopt a unified randomized batch-sampling Kaczmarz framework with per-iteration costs as low as cyclic block methods, and develop a general analysis technique to establish its convergence guarantee. With concentration inequalities, we derive new expected linear convergence rate bounds. The analysis applies to any randomized non-extended block Kaczmarz methods with static stochastic samplings. In addition, the new rate bounds are scale-invariant which eliminate the dependence on the magnitude of the data matrix. In most experiments, the new bounds are significantly tighter than existing ones and better reflect the empirical convergence behavior of block methods. Within this new framework, the batch-sampling distribution, as a learnable parameter, provides the possibility for block methods to achieve efficient performance in specific application scenarios, which deserves further investigation.

Related papers

• Learnable Chernoff Baselines for Inference-Time Alignment [64.81256817158851]
  We introduce Learnable Chernoff Baselines as a method for efficiently and approximately sampling from exponentially tilted kernels.<n>We establish total-variation guarantees to the ideal aligned model, and demonstrate in both continuous and discrete diffusion settings that LCB sampling closely matches ideal rejection sampling.
  arXiv  Detail & Related papers  (2026-02-08T00:09:40Z)
• Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees [70.88473359544084]
  We introduce a new analytical approach for discrete diffusion models that removes the need for regularity assumptions.<n>For the standard $tau$-leaping method, we establish convergence guarantees in KL divergence that scale linearly with vocabulary size.<n>Our approach is also more broadly applicable: it provides the first convergence guarantees for other widely used samplers.
  arXiv  Detail & Related papers  (2025-09-20T17:42:29Z)
• Distances for Markov chains from sample streams [16.443304244634767]
  Bisimulation metrics are powerful tools for measuring similarities between processes, and specifically Markov chains.<n>Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees.<n>This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available.<n>We propose a new optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models.
  arXiv  Detail & Related papers  (2025-05-23T15:09:04Z)
• Discretization-free Multicalibration through Loss Minimization over Tree Ensembles [22.276913140687725]
  We propose a discretization-free multicalibration method over an ensemble of depth-two decision trees.<n>Our algorithm provably achieves multicalibration, provided that the data distribution satisfies a technical condition we term as loss saturation.
  arXiv  Detail & Related papers  (2025-05-23T03:29:58Z)
• Randomized Kaczmarz Methods with Beyond-Krylov Convergence [8.688801614519988]
  We introduce Kaczmarz++, an accelerated randomized block Kaczmarz algorithm that exploits outlying singular values in the input to attain a fast Krylov-style convergence.<n>We show that Kaczmarz++ captures large outlying singular values provably faster than popular Krylov methods, for both over- and under-determined systems.
  arXiv  Detail & Related papers  (2025-01-20T18:55:51Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  gradient, clipping is one of the key algorithmic ingredients to derive good high-probability guarantees. Clipping can spoil the convergence of the popular methods for composite and distributed optimization.
  arXiv  Detail & Related papers  (2023-10-03T07:49:17Z)
• Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints [7.936519714074615]
  The Kaczmarz matrix (KZ) and its variants have been extensively studied due to their simplicity and efficiency in solving sub linear equation systems. We provide the first theoretical convergence guarantees for KHT by showing that it converges linearly to the solution of a system with sparsity constraints.
  arXiv  Detail & Related papers  (2023-04-20T07:14:24Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  We propose a new distributed dynamic safe screening (DDSS) method for sparsity regularized models and apply it on shared-memory and distributed-memory architecture respectively. We prove that the proposed method achieves the linear convergence rate with lower overall complexity and can eliminate almost all the inactive features in a finite number of iterations almost surely.
  arXiv  Detail & Related papers  (2022-04-23T02:45:55Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning [27.775096437736973]
  We show that the independent sampling scheme tends to improve performance of the commonly-used uniform sampling scheme. Our new analysis also derives a speed for the sampling than best one available so far.
  arXiv  Detail & Related papers  (2020-09-14T16:41:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.