論文の概要: Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias
- arxiv url: http://arxiv.org/abs/2408.13115v1
- Date: Tue, 20 Aug 2024 01:24:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-26 14:50:54.410706
- Title: Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias
- Title（参考訳）: 高次元における不調整ランゲヴィンの収束:バイアスの非局在化
- Authors: Yifan Chen, Xiaoou Cheng, Jonathan Niles-Weed, Jonathan Weare,
- Abstract要約: 問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。
私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
- 参考スコア（独自算出の注目度）: 13.642712817536072
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The unadjusted Langevin algorithm is commonly used to sample probability distributions in extremely high-dimensional settings. However, existing analyses of the algorithm for strongly log-concave distributions suggest that, as the dimension $d$ of the problem increases, the number of iterations required to ensure convergence within a desired error in the $W_2$ metric scales in proportion to $d$ or $\sqrt{d}$. In this paper, we argue that, despite this poor scaling of the $W_2$ error for the full set of variables, the behavior for a small number of variables can be significantly better: a number of iterations proportional to $K$, up to logarithmic terms in $d$, often suffices for the algorithm to converge to within a desired $W_2$ error for all $K$-marginals. We refer to this effect as delocalization of bias. We show that the delocalization effect does not hold universally and prove its validity for Gaussian distributions and strongly log-concave distributions with certain sparse interactions. Our analysis relies on a novel $W_{2,\ell^\infty}$ metric to measure convergence. A key technical challenge we address is the lack of a one-step contraction property in this metric. Finally, we use asymptotic arguments to explore potential generalizations of the delocalization effect beyond the Gaussian and sparse interactions setting.
- Abstract（参考訳）: 調整されていないランゲヴィンアルゴリズムは、非常に高次元の設定における確率分布のサンプリングに一般的に用いられる。
しかし、強い対数分布に対するアルゴリズムの既存の分析は、問題の次元$d$が増加するにつれて、$W_2$メートル法スケールにおいて所望の誤差内で収束を保証するために必要なイテレーションの数が$d$または$\sqrt{d}$に比例することを示している。
この論文では、変数の完全集合に対する$W_2$エラーのスケーリングが貧弱であるにもかかわらず、少数の変数に対する振る舞いは、はるかに良くなる:$K$に比例する多くの反復は、$d$の対数項まで、しばしばアルゴリズムが所望の$K$-marginalsに対して$W_2$エラーに収束するのに十分である。
この効果を偏見の非局在化と呼ぶ。
局所化効果は普遍的に保たないことを示すとともに,ガウス分布と強い対数圏分布に対する有効性を示す。
我々の分析は収束を測定するための新しい$W_{2,\ell^\infty}$メトリックに依存している。
私たちが取り組んだ重要な技術的課題は、この計量に一段階の収縮特性が欠如していることである。
最後に、漸近的議論を用いて、ガウス的およびスパース的相互作用設定を超えた非局在化効果の潜在的な一般化を探索する。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳（メタデータ） (2024-04-21T14:18:49Z) - Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
確率フローODEに基づく決定論的サンプリング器の収束特性を理論的・数値的両面から検討する。
連続時間レベルでは、ターゲットと生成されたデータ分布の総変動を$mathcalO(d3/4delta1/2)$で表すことができる。
論文 参考訳（メタデータ） (2024-04-15T12:29:28Z) - Compressed and distributed least-squares regression: convergence rates
with applications to Federated Learning [9.31522898261934]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳（メタデータ） (2023-08-02T18:02:00Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。
我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
論文 参考訳（メタデータ） (2021-10-27T08:01:17Z) - Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
ガウス下収束を考慮した新しい推定器を提案する。
我々の推定器はその分散に関する事前の知識を必要としない。
我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
論文 参考訳（メタデータ） (2020-11-17T02:47:24Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。