論文の概要: Computing Approximated Fixpoints via Dampened Mann Iteration

• arxiv url: http://arxiv.org/abs/2501.08950v1
• Date: Wed, 15 Jan 2025 16:52:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 15:51:26.813690
• Title: Computing Approximated Fixpoints via Dampened Mann Iteration
• Title（参考訳）: ダンプマン反復による近似固定点の計算
• Authors: Paolo Baldan, Sebastian Gurke, Barbara König, Tommaso Padoan, Florian Wittbold,
• Abstract要約: 正確には知られていないが、それらに収束する近似関数列で表される関数の最小固定点を近似する方法を示す。 この結果は,確率的誤差境界で関心関数を近似できるシステムに対して,最小の固定点にほぼ確実に反復することができる。
• 参考スコア（独自算出の注目度）: 0.31457219084519
• License:
• Abstract: Fixpoints are ubiquitous in computer science and when dealing with quantitative semantics and verification one is commonly led to consider least fixpoints of (higher-dimensional) functions over the nonnegative 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 (MDPs), showing that the proposed iteration scheme instantiates to MDPs 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, that can be explored via sampling.
• Abstract（参考訳）: 固定点はコンピュータ科学においてユビキタスであり、定量的意味論や検証を扱う際には、非負の実数に対して(高次元の)関数の最小の固定点を考えることが一般的である。 そのような関数の最小固定点をいかに近似するかを示し、それらが正確には知られていないが、それらに収束する近似関数列によって表される場合に焦点を当てる。 固定点の特異性が保証されず、標準の固定点反復スキームが最小限ではない固定点で立ち往生してしまうような、単調な関数と非拡張的な関数に集中する。 我々の主な貢献は反復スキームの同定であり、適切な条件下では、関心の関数の最小固定点への収束を保証するマン反復の変分である。 次に、これらの結果はマルコフ決定過程(MDP)のモデルベース強化学習(MDP)の文脈において重要であり、提案した反復方式がMDPにインスタンス化され、最適に期待されたリターンへの収束を導出できることを示す。 より一般に、我々の結果は、サンプリングによって探索できる単純な確率ゲームのような確率的システムの場合のように、興味のある関数が与えられた確率的誤差境界に近似できるシステムに対して、ほぼ確実に最小の固定点に反復することができることを示す。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。 分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。 実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Bayesian sequential design of computer experiments for quantile set inversion [0.0]
  複素数値シミュレータのようなシステムを表現する未知の多変量関数を考える。 我々の目的は、確率が与えられた閾値未満の出力につながる決定論的入力のセットを推定することである。
  論文  参考訳（メタデータ） (2022-11-02T10:14:05Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  本研究では,ニュアンス関数が存在しない場合でも,関数を強く識別するための新しい条件について検討する。 本稿では,プライマリおよびデバイアスのニュアンス関数に対するペナル化ミニマックス推定器を提案する。
  論文  参考訳（メタデータ） (2022-08-17T13:38:31Z)
• Reliability analysis of discrete-state performance functions via adaptive sequential sampling with detection of failure surfaces [0.0]
  本稿では,レアイベント確率推定のための新しい効率的でロバストな手法を提案する。 この手法は、複数の障害タイプの確率を推定することができる。 この情報に対応して、推定確率の精度を高めることができる。
  論文  参考訳（メタデータ） (2022-08-04T05:59:25Z)
• Cross-validation for change-point regression: pitfalls and solutions [0.0]
  その結果,2乗誤差損失を伴うクロスバリデーションの問題はより深刻であり,変更点数の体系的過小評価や過大評価につながる可能性が示唆された。 本稿では,これらの問題を解決するための2つの簡単なアプローチを提案する。 これらの条件は, 変更点数の誤った値が供給された場合, 性能上の新しい結果を用いて, 少なくとも2乗推定で満たされることを示す。
  論文  参考訳（メタデータ） (2021-12-06T18:23:12Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  推定対象の偏りを伴わずに高い重なりを生じさせる,デコンファウンディングスコアを導入する。 分離スコアは観測データで識別可能なゼロ共分散条件を満たすことを示す。 特に,この手法が標準正規化の魅力的な代替となることを示す。
  論文  参考訳（メタデータ） (2021-04-12T18:50:11Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Probabilistic selection of inducing points in sparse Gaussian processes [1.2617078020344619]
  ポイントの誘導は、モデルの複雑さへの主要な貢献となります。 誘導点に先立って点を設定し、変分推論により関連する後部を近似する。 実験により, ポイントが情報量が少なくなるにつれて, インジェクションポイントの減少がモデルに好まれることを示す。
  論文  参考訳（メタデータ） (2020-10-19T10:29:30Z)
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control [28.679167097106813]
  本稿では,各反復で関数値を1回クエリし,2つの連続点間の残差を用いて勾配を推定する新しい一点フィードバック方式を提案する。 提案アルゴリズムは,制御不能なデータサンプルを持つ2点スキームと同じ収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-06-18T19:31:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。