Computing Fixpoints of Learned Functions: Chaotic Iteration and Simple Stochastic Games

• URL: http://arxiv.org/abs/2601.16142v1
• Date: Thu, 22 Jan 2026 17:36:19 GMT
• Title: Computing Fixpoints of Learned Functions: Chaotic Iteration and Simple Stochastic Games
• Authors: Paolo Baldan, Sebastian Gurke, Barbara König, Florian Wittbold,
• Abstract summary: We generalize an iteration scheme called dampened iteration Mann.<n>We show that dampened iteration Mann applies immediately to compute the expected payoff in various probabilistic models.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of determining the (least) fixpoint of (higher-dimensional) functions over the non-negative reals frequently occurs when dealing with systems endowed with a quantitative semantics. We focus on the situation in which the functions of interest are not known precisely but can only be approximated. As a first contribution we generalize an iteration scheme called dampened Mann iteration, recently introduced in the literature. The improved scheme relaxes previous constraints on parameter sequences, allowing learning rates to converge to zero or not converge at all. While seemingly minor, this flexibility is essential to enable the implementation of chaotic iterations, where only a subset of components is updated in each step, allowing to tackle higher-dimensional problems. Additionally, by allowing learning rates to converge to zero, we can relax conditions on the convergence speed of function approximations, making the method more adaptable to various scenarios. We also show that dampened Mann iteration applies immediately to compute the expected payoff in various probabilistic models, including simple stochastic games, not covered by previous work.

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)
• Approximating Fixpoints of Approximated Functions [0.31457219084519]
  We show how to approximate the least fixpoint of functions that are not known precisely, but represented by a sequence of approximating functions that converge to them.<n>Our results can be used to iterate to the least fixpoint almost surely for systems where the function of interest can be approximated with given probabilistic error bounds.
  arXiv  Detail & Related papers  (2025-01-15T16:52:21Z)
• 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)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods [0.6554326244334866]
  Sharpness is an assumption in continuous optimization that bounds the distance from minima by objective function suboptimality. Sharpness involves problem-specific constants that are typically unknown, and restart schemes typically reduce convergence rates. We consider the assumption of approximate sharpness, a generalization of sharpness that incorporates an unknown constant perturbation to the objective function error.
  arXiv  Detail & Related papers  (2023-01-05T19:01:41Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• The Stochastic Proximal Distance Algorithm [5.3315823983402755]
  We propose and analyze a class of iterative optimization methods that recover a desired constrained estimation problem as a penalty parameter. We extend recent theoretical devices to establish finite error bounds and a complete characterization of convergence rates. We validate our analysis via a thorough empirical study, also showing that unsurprisingly, the proposed method outpaces batch versions on popular learning tasks.
  arXiv  Detail & Related papers  (2022-10-21T22:07:28Z)
• On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
  We develop a deeper understanding of AdaGrad and its variants in the standard setting of smooth convex functions. First, we demonstrate new techniques to explicitly bound the convergence rate of the vanilla AdaGrad for unconstrained problems. Second, we propose a variant of AdaGrad for which we can show the convergence of the last iterate, instead of the average iterate.
  arXiv  Detail & Related papers  (2022-09-29T14:44:40Z)
• Cardinality-Minimal Explanations for Monotonic Neural Networks [25.212444848632515]
  In this paper, we investigate whether tractability can be regained by focusing on neural models implementing a monotonic function. Although the relevant decision problems remain intractable, we can show that they become solvable in favourable time.
  arXiv  Detail & Related papers  (2022-05-19T23:47:25Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  We develop a novel surrogate that can be optimized by closed-form solutions. We exploit upperwise correlation for completion, and thus an adaptive correlation learning model.
  arXiv  Detail & Related papers  (2022-03-04T08:50:50Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

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.