論文の概要: Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates
- arxiv url: http://arxiv.org/abs/2608.09022v1
- Date: Mon, 10 Aug 2026 02:25:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-11 19:16:37.038685
- Title: Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates
- Title（参考訳）: 線形収束率をもつ確率パラメータフリー固定点アルゴリズム
- Abstract要約: 本研究では, パラメータフリーかつ適応的不動点アルゴリズムを開発した。
固定点残差と一意な固定点の距離の両方に対して、明示的な線形収束率を確立する。
いくつかの例における数値実験により、提案アルゴリズムは既存の適応的不動点法と競合し、しばしば優れることを示した。
- 参考スコア（独自算出の注目度）: 3.2919103562171865
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we develop provable parameter-free and adaptive fixed-point algorithms for contractive mappings, with an emphasis on automatically exploiting hidden contractivity without requiring prior knowledge of the contraction factor. Our first method is a completely parameter-free variant of the Halpern fixed-point iteration. It requires no line search, bisection, or prior estimate of the contraction factor, while retaining essentially the same per-iteration computational cost as classical fixed-point schemes. We establish explicit linear convergence rates for both the fixed-point residual and the distance to the unique fixed point. The second algorithm is an adaptive Halpern method that requires only an upper bound on the contraction factor and reduces to an existing adaptive Halpern scheme in the nonexpansive case. This method also enjoys explicit linear convergence guarantees. We further extend these ideas in two directions. First, by combining the proposed fixed-point schemes with Tikhonov regularization, we obtain a parameter-free method for solving co-coercive equations and establish an iteration complexity of $\mathcal{O}({ε^{-1}\ln(ε^{-1})})$ for computing an $ε$-solution. Second, using the relation between Halpern iterations and Nesterov's accelerated fixed-point schemes, we derive parameter-free Nesterov's accelerated variants that inherit linear convergence in the contractive setting. Numerical experiments on several examples demonstrate that the proposed algorithms are competitive with, and often outperform, existing adaptive fixed-point methods. In particular, the methods successfully exploit contractive behavior when it is present while remaining effective on nonexpansive problems.
- Abstract（参考訳）: 本稿では,制約係数の事前知識を必要とせず,隠れた制約性を自動的に活用することを重視し,パラメータフリーで適応的な固定点アルゴリズムを開発した。
最初の方法はハルパーン固定点反復の完全にパラメータフリーな変種である。
線形探索や分岐、あるいは事前の収縮係数の推定は必要とせず、古典的な定点スキームと基本的に同じ定点計算コストを保っている。
固定点残差と一意な固定点の距離の両方に対して、明示的な線形収束率を確立する。
第二のアルゴリズムは適応ハルパーン法であり、収縮係数の上限だけを必要とせず、既存の適応ハルパーンスキームに還元する。
この方法はまた、明示的な線形収束保証を享受する。
これらの考えをさらに2つの方向に拡張する。
まず、提案した固定点スキームとTikhonov正則化を組み合わせることで、コヒーレンシブ方程式を解くパラメータフリーな方法を求め、$\mathcal{O}({ε^{-1}\ln(ε^{-1})} の反復複雑性を$ε$解を計算するために確立する。
第二に、ハルパーン反復とネステロフの加速された不動点スキームの関係を利用して、パラメータフリーなネステロフの加速された変種を導出し、縮約条件における線型収束を継承する。
いくつかの例における数値実験により、提案アルゴリズムは既存の適応的不動点法と競合し、しばしば優れることを示した。
特に、この手法は、非拡張的問題に有効でありながら、それが存在するときの契約的挙動をうまく活用する。
関連論文リスト
- Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning [9.748884794669346]
モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。
これらの結果は、モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。
論文 参考訳（メタデータ） (2026-08-03T08:50:07Z) - Bridging the Gap Between Average and Discounted TD Learning [14.556544278062793]
平均回帰設定において,政策評価のために明示的に設計された新しいアルゴリズムを提案する。
提案手法は, 適切に定義されたベルマン方程式の一意解への収束を保証することによって, 従来の限界を克服する。
論文 参考訳（メタデータ） (2026-05-03T23:54:36Z) - Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
この研究は、一階法のみを用いた線形制約付き双レベル最適化に対する最初の有限時間収束保証を提供する。
線形制約、雑音、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。
論文 参考訳（メタデータ） (2025-11-13T00:59:20Z) - Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳（メタデータ） (2024-09-24T04:39:47Z) - Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization [8.879403568685499]
パラメータの平滑化に適応的な更新戦略を導入する。
この振る舞いは、アルゴリズムを数回繰り返した後に、効果的に問題を解決するものに変えます。
すべてのイテレーションが重要なものであることを保証し、グローバルに提案された実験を証明します。
論文 参考訳（メタデータ） (2024-06-22T02:37:13Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
論文 参考訳（メタデータ） (2020-07-13T17:39:35Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-03-30T20:44:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。