論文の概要: Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
- arxiv url: http://arxiv.org/abs/2607.13414v1
- Date: Wed, 15 Jul 2026 03:33:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-16 16:39:12.63152
- Title: Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
- Title（参考訳）: 非拡張2時間スケール確率近似:固定スケジュール1量子バリアとバイアス補正加速度
- Abstract要約: 遅いクラスノセルスキイ-マンの不動点反復が支配する2次元近似について検討する。
ネストされたTikhonov-KMアルゴリズムでは、補正されていないオラクルは総サンプルレートが$T-1/4+o(1)$となる。
- 参考スコア（独自算出の注目度）: 46.80389197344682
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Non-expansive two-time-scale stochastic approximation is governed by a slow stochastic Krasnoselskii--Mann fixed-point iteration rather than by contraction to a unique equilibrium. We study this regime under a contractive fast map and a non-expansive reduced slow map. We first prove a finite-horizon lower bound showing that, for any prescribed slow stepsize schedule $(β_k)$, the classical KM residual scale $(\sum_{i<N}β_i(1-β_i))^{-1}$ is worst-case sharp for the corresponding unregularized KM update. Combined with the raw fast-tracking leakage scale, this explains the previously observed $k^{-1/4+o(1)}$ last-iterate mean-square residual exponent. We then introduce a residual-preconditioned slow oracle that cancels the first-order dependence on the fast tracking error. In a nested Tikhonov-KM algorithm, the uncorrected oracle yields total-sample rate $T^{-1/4+o(1)}$, while the corrected oracle yields $T^{-1/3+o(1)}$. This improvement comes from changing the slow-oracle bias from first order to second order in the fast error after all inner-loop samples are counted. Finally, we show that the repeated inner-loop cost of the nested method can be avoided in a smooth derivative-oracle model. A single-loop algorithm that tracks both the fast equilibrium and the leakage preconditioner online achieves $T^{-1/2+o(1)}$ with $O(1)$ primitive samples per iteration.
- Abstract（参考訳）: 非拡張的な2時間スケール確率近似は、一意平衡への縮約よりもむしろ遅い確率的クラスノセルスキイ-マンの不動点反復によって支配される。
我々は、この構造を、縮約高速写像と非拡張縮小低速写像の下で研究する。
まず、所定のスローステップ化スケジュール$(β_k)$に対して、古典的KM残差スケール$(\sum_{i<N}β_i(1-β_i))^{-1}$は、対応する非正規化KM更新に対して最悪のケースシャープであることを示す有限水平下界を証明する。
生の高速追尾リークスケールと組み合わせて、前述した$k^{-1/4+o(1)}$ストレート平均二乗残留指数を説明する。
次に、高速追従誤差に対する1次依存をキャンセルする残前提の遅いオラクルを導入する。
ネストされたTikhonov-KMアルゴリズムでは、補正されていないオラクルは総サンプルレート$T^{-1/4+o(1)}$、補正されたオラクルは$T^{-1/3+o(1)}$である。
この改善は、全てのインナーループサンプルがカウントされた後、高速エラーで1次から2次へ遅い軌道バイアスを変更することに起因する。
最後に,スムーズな導波管モデルでは,ネスト法において繰り返し発生するインナーループコストを回避可能であることを示す。
高速平衡と漏洩プリコンディショナーの両方をオンラインで追跡するシングルループアルゴリズムは、反復毎に$O(1)$のプリミティブサンプルで$T^{-1/2+o(1)$を達成する。
関連論文リスト
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities [8.350639529216876]
このアルゴリズムは、各イテレーションで演算子の1つのバイアスのないサンプルを使用し、ノイズのあるフィードバックでモノトーンゲームに適用できるため、シングルループでシングルコールである。
我々は、勾配マッピングノルムと制限されたギャップの両方に対して、いつでも$O(t-1/4)$の定数収束率を証明した。
論文 参考訳（メタデータ） (2026-09-14T09:17:23Z) - Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity [80.65200796386168]
このような問題を解決するための新しい微分自由法を提案し,解析する。
基礎となる雑音列の混合時間$$が問題の次元$d$より小さい場合、我々の手法の収束推定は$$に依存しないことを示す。
論文 参考訳（メタデータ） (2026-01-03T11:27:07Z) - A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications [3.6997773420183866]
我々は,非拡張作用素の固定点を近似するために,遅延不正確なオラクルを用いた固定点ベースのフレームワークを開発する。
本手法はネステロフ加速法とクラスノセル・スキーマン(KM)反復法の両方を利用する。
論文 参考訳（メタデータ） (2025-12-15T17:06:22Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - $O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation [0.0]
非線形2時間スケール近似に対して$O (1/k)$の勾配境界を改良した。
この結果は、降下度や2時間スケールのラグランジアン最適化などのアルゴリズムに適用できる。
論文 参考訳（メタデータ） (2025-04-27T22:45:00Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way [12.331596909999764]
マルコフ過程のレンズを通した等質化スキームについて検討する。
我々は、定段化によって導入された分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。
論文 参考訳（メタデータ） (2024-10-16T21:49:27Z) - Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
我々は,Halpern反復のオラクル複雑性をミニバッチで解析する。
我々は,平均値と割引値の報酬MDPに対する新しいモデルフリーアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-19T01:07:35Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - Finite Time Analysis of Linear Two-timescale Stochastic Approximation
with Markovian Noise [28.891930079358954]
線形2時間スケールSAスキームに対して有限時間解析を行う。
我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。
一致した下界を持つ予測誤差の拡張を示す。
論文 参考訳（メタデータ） (2020-02-04T13:03:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。