Fugu-MT 論文翻訳(概要): Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality

論文の概要: Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality

arxiv url: http://arxiv.org/abs/2207.04173v2
Date: Sun, 31 Dec 2023 05:36:49 GMT
ステータス: 処理完了
システム内更新日: 2024-01-03 03:19:47.453490
Title: Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality
Title（参考訳）: 決定依存分布をもつ確率近似:漸近正規性と最適性
Authors: Joshua Cutler, Mateo D\'iaz, Dmitriy Drusvyatskiy
Abstract要約: 我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
参考スコア（独自算出の注目度）: 8.411514688735185
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We analyze a stochastic approximation algorithm for decision-dependent problems, wherein the data distribution used by the algorithm evolves along the iterate sequence. The primary examples of such problems appear in performative prediction and its multiplayer extensions. We show that under mild assumptions, the deviation between the average iterate of the algorithm and the solution is asymptotically normal, with a covariance that clearly decouples the effects of the gradient noise and the distributional shift. Moreover, building on the work of H\'ajek and Le Cam, we show that the asymptotic performance of the algorithm with averaging is locally minimax optimal.
Abstract（参考訳）: 決定依存問題に対する確率近似アルゴリズムを解析し,アルゴリズムが使用するデータ分布は反復列に沿って進化する。このような問題の主な例は、性能予測とそのマルチプレイヤー拡張である。穏やかな仮定の下では、アルゴリズムの平均反復値と解の偏差は漸近的に正常であり、勾配ノイズと分布シフトの影響を明確に分離する共分散が存在する。さらに, h\'ajek と le cam の研究に基づいて, 平均化を伴うアルゴリズムの漸近的性能は局所的 minimax 最適であることを示した。

関連論文リスト

Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文参考訳（メタデータ） (2024-04-16T20:01:10Z)
Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。 SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文参考訳（メタデータ） (2023-07-04T06:06:10Z)
First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文参考訳（メタデータ） (2023-05-25T11:11:31Z)
Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文参考訳（メタデータ） (2023-02-13T19:57:17Z)
Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文参考訳（メタデータ） (2022-10-23T23:23:23Z)
Exponential Concentration in Stochastic Approximation [0.8192907805418583]
我々は,各ステップで目標に向かって反復的に進行する近似アルゴリズムの挙動を解析する。我々はマルコフ近似アルゴリズム、具体的には射影勾配 Descent, Kiefer-Wolfowitz および Frank-Wolfe アルゴリズムに適用する。
論文参考訳（メタデータ） (2022-08-15T14:57:26Z)
Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文参考訳（メタデータ） (2021-09-20T21:48:19Z)
Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文参考訳（メタデータ） (2020-06-11T19:40:38Z)
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)
Sparse recovery by reduced variance stochastic approximation [5.672132510411465]
雑音観測によるスパース信号回復問題に対する反復2次最適化ルーチンの適用について論じる。本稿では,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法について述べる。
論文参考訳（メタデータ） (2020-06-11T12:31:20Z)
Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文参考訳（メタデータ） (2020-03-16T17:15:28Z)

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