Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and $λ$-Effectiveness

• URL: http://arxiv.org/abs/2511.07604v1
• Date: Wed, 12 Nov 2025 01:06:46 GMT
• Title: Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and $λ$-Effectiveness
• Authors: Halyun Jeong, Palle E. T. Jorgensen, Hyun-Kyoung Kwon, Myung-Sin Song,
• Abstract summary: We study the role of the relaxation parameter in generalized Kaczmarz algorithms.<n>We establish a priori regret bounds with explicit $$-dependence to quantify how much an algorithm's performance deviates from its optimal performance.
• Score: 2.1465871746452043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a variety of projection-based linear regression algorithms with a focus on modern machine-learning models and their algorithmic performance. We study the role of the relaxation parameter in generalized Kaczmarz algorithms and establish a priori regret bounds with explicit $λ$-dependence to quantify how much an algorithm's performance deviates from its optimal performance. A detailed analysis of relaxation parameter is also provided. Applications include: explicit regret bounds for the framework of Kaczmarz algorithm models, non-orthogonal Fourier expansions, and the use of regret estimates in modern machine learning models, including for noisy data, i.e., regret bounds for the noisy Kaczmarz algorithms. Motivated by machine-learning practice, our wider framework treats bounded operators (on infinite-dimensional Hilbert spaces), with updates realized as (block) Kaczmarz algorithms, leading to new and versatile results.

Related papers

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
  We consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation.<n>We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2024-01-26T20:45:40Z)
• Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits [5.847084649531299]
  Thompson sampling and Greedy demonstrate promising empirical performance, yet this contrasts with their pessimistic theoretical regret bounds.<n>We propose a new data-driven technique that tracks the geometric properties of the uncertainty ellipsoid around the main problem parameter.<n>This methodology enables us to formulate a data-driven frequentist regret bound, which incorporates the geometric information, for a broad class of base algorithms, including Greedy, OFUL, and Thompson sampling.
  arXiv  Detail & Related papers  (2023-06-26T17:38:45Z)
• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  We propose an online learning algorithm for a class of machine learning models under a separable approximation framework. We show that the proposed algorithm produces more robust and test performance when compared to other popular learning algorithms.
  arXiv  Detail & Related papers  (2023-05-12T13:53:03Z)
• GBOSE: Generalized Bandit Orthogonalized Semiparametric Estimation [3.441021278275805]
  We propose a new algorithm with a semi-parametric reward model with state-of-the-art complexity of upper bound on regret. Our work expands the scope of another representative algorithm of state-of-the-art complexity with a similar reward model by proposing an algorithm built upon the same action filtering procedures. We derive the said complexity of the upper bound on regret and present simulation results that affirm our methods superiority out of all prevalent semi-parametric bandit algorithms for cases involving over two arms.
  arXiv  Detail & Related papers  (2023-01-20T19:39:10Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Algorithms that Approximate Data Removal: New Results and Limitations [2.6905021039717987]
  We study the problem of deleting user data from machine learning models trained using empirical risk minimization. We develop an online unlearning algorithm that is both computationally and memory efficient.
  arXiv  Detail & Related papers  (2022-09-25T17:20:33Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  parameter-free algorithms are online learning algorithms that do not require setting learning rates. We propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties.
  arXiv  Detail & Related papers  (2022-03-19T13:39:49Z)
• Improved Model based Deep Learning using Monotone Operator Learning (MOL) [25.077510176642807]
  MoDL algorithms that rely on unrolling are emerging as powerful tools for image recovery. We introduce a novel monotone operator learning framework to overcome some of the challenges associated with current unrolled frameworks. We demonstrate the utility of the proposed scheme in the context of parallel MRI.
  arXiv  Detail & Related papers  (2021-11-22T17:42:27Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Learning outside the Black-Box: The pursuit of interpretable models [78.32475359554395]
  This paper proposes an algorithm that produces a continuous global interpretation of any given continuous black-box function. Our interpretation represents a leap forward from the previous state of the art.
  arXiv  Detail & Related papers  (2020-11-17T12:39:44Z)

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.