Approximating Fixpoints of Approximated Functions

• URL: http://arxiv.org/abs/2501.08950v2
• Date: Fri, 13 Jun 2025 13:11:34 GMT
• Title: Approximating Fixpoints of Approximated Functions
• Authors: Paolo Baldan, Sebastian Gurke, Barbara König, Tommaso Padoan, Florian Wittbold,
• Abstract summary: 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.
• Score: 0.31457219084519
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fixpoints are ubiquitous in computer science and when dealing with quantitative semantics and verification one often considers least fixpoints of (higher-dimensional) functions over the non-negative reals. We show how to approximate the least fixpoint of such functions, focusing on the case in which they are not known precisely, but represented by a sequence of approximating functions that converge to them. We concentrate on monotone and non-expansive functions, for which uniqueness of fixpoints is not guaranteed and standard fixpoint iteration schemes might get stuck at a fixpoint that is not the least. Our main contribution is the identification of an iteration scheme, a variation of Mann iteration with a dampening factor, which, under suitable conditions, is shown to guarantee convergence to the least fixpoint of the function of interest. We then argue that these results are relevant in the context of model-based reinforcement learning for Markov decision processes, showing how the proposed iteration scheme instantiates and allows us to derive convergence to the optimal expected return. More generally, we show that 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, as it happens for probabilistic systems, such as simple stochastic games, which can be explored via sampling.

Related papers

• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  Reinforcement learning with outcome-based feedback faces a fundamental challenge.<n>How do we assign credit to the right actions?<n>This paper provides the first comprehensive analysis of this problem in online RL with general function approximation.
  arXiv  Detail & Related papers  (2025-05-26T17:44:08Z)
• 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)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  This research presents a method to meet requirements through the minimization objective function of the RPM algorithm. A branch-and-bound (BnB) algorithm is devised, which solely branches over the parameters, thereby boosting convergence rate. Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, when compared with prevailing state-of-the-art transformations.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• $f$-Divergence Based Classification: Beyond the Use of Cross-Entropy [4.550290285002704]
  We adopt a Bayesian perspective and formulate the classification task as a maximum a posteriori probability problem. We propose a class of objective functions based on the variational representation of the $f$-divergence. We theoretically analyze the objective functions proposed and numerically test them in three application scenarios.
  arXiv  Detail & Related papers  (2024-01-02T16:14:02Z)
• Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach [7.059472280274009]
  We present an exact Bayesian inference method for discrete statistical models. We use a probabilistic programming language that supports discrete and continuous sampling, discrete observations, affine functions, (stochastic) branching, and conditioning on discrete events. Our inference method is provably correct and fully automated.
  arXiv  Detail & Related papers  (2023-05-26T16:09:59Z)
• Nuisance Function Tuning and Sample Splitting for Optimal Doubly Robust Estimation [5.018363990542611]
  We consider the problem of how to estimate nuisance functions to obtain optimal rates of convergence for a doubly robust nonparametric functional. We show that plug-in and first-order biased-corrected estimators can achieve minimax rates of convergence across all H"older smoothness classes of the nuisance functions.
  arXiv  Detail & Related papers  (2022-12-30T18:17:06Z)
• Bayesian sequential design of computer experiments for quantile set inversion [0.0]
  We consider an unknown multivariate function representing a system-such as a complex numerical simulator. Our objective is to estimate the set of deterministic inputs leading to outputs whose probability is less than a given threshold.
  arXiv  Detail & Related papers  (2022-11-02T10:14:05Z)
• Sequential Decision Making on Unmatched Data using Bayesian Kernel Embeddings [10.75801980090826]
  We propose a novel algorithm for maximizing the expectation of a function. We take into consideration the uncertainty derived from the estimation of both the conditional distribution of the features and the unknown function. Our algorithm empirically outperforms the current state-of-the-art algorithm in the experiments conducted.
  arXiv  Detail & Related papers  (2022-10-25T01:27:29Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  We study a novel condition for the functional to be strongly identified even when the nuisance function is not. We propose penalized minimax estimators for both the primary and debiasing nuisance functions.
  arXiv  Detail & Related papers  (2022-08-17T13:38:31Z)
• Reliability analysis of discrete-state performance functions via adaptive sequential sampling with detection of failure surfaces [0.0]
  The paper presents a new efficient and robust method for rare event probability estimation. The method can estimate the probabilities of multiple failure types. It can accommodate this information to increase the accuracy of the estimated probabilities.
  arXiv  Detail & Related papers  (2022-08-04T05:59:25Z)
• Cross-validation for change-point regression: pitfalls and solutions [0.0]
  We show that the problems of cross-validation with squared error loss are more severe and can lead to systematic under- or over-estimation of the number of change-points. We propose two simple approaches to remedy these issues, the first involving the use of absolute error rather than squared error loss. We show these conditions are satisfied for at least squares estimation using new results on its performance when supplied with the incorrect number of change-points.
  arXiv  Detail & Related papers  (2021-12-06T18:23:12Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  We introduce deconfounding scores, which induce better overlap without biasing the target of estimation. We show that deconfounding scores satisfy a zero-covariance condition that is identifiable in observed data. In particular, we show that this technique could be an attractive alternative to standard regularizations.
  arXiv  Detail & Related papers  (2021-04-12T18:50:11Z)
• Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approach [84.29777236590674]
  We study the estimation of causal parameters when not all confounders are observed and instead negative controls are available. Recent work has shown how these can enable identification and efficient estimation via two so-called bridge functions.
  arXiv  Detail & Related papers  (2021-03-25T17:59:19Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Probabilistic selection of inducing points in sparse Gaussian processes [1.2617078020344619]
  inducing points act as main contributor towards model complexity. We place a point prior on the inducing points and approximate the associated posterior through variational inference. We experimentally show that fewer inducing points are preferred by the model as the points become less informative.
  arXiv  Detail & Related papers  (2020-10-19T10:29:30Z)
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control [28.679167097106813]
  We propose a novel one-point feedback scheme that queries the function value once at each iteration and estimates the gradient using the residual between two consecutive points. We show that the proposed algorithm achieves the same convergence rate as that of two-point scheme with uncontrollable data samples.
  arXiv  Detail & Related papers  (2020-06-18T19:31:13Z)

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.