論文の概要: Asymptotic Behaviors and Phase Transitions in Projected Stochastic
Approximation: A Jump Diffusion Approach
- arxiv url: http://arxiv.org/abs/2304.12953v1
- Date: Tue, 25 Apr 2023 15:57:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 19:45:26.192177
- Title: Asymptotic Behaviors and Phase Transitions in Projected Stochastic
Approximation: A Jump Diffusion Approach
- Title（参考訳）: 射影確率近似における漸近的挙動と相転移:ジャンプ拡散アプローチ
- Authors: Jiadong Liang, Yuze Han, Xiang Li, Zhihua Zhang
- Abstract要約: 線形制約付き最適化問題を考察し、ループレス投影近似(LPSA)を提案する。
実現可能性を保証するために、$n$-thの確率$p_n$でプロジェクションを実行する。
このアルゴリズムは興味深いバイアス分散トレードオフを示し、位相遷移現象を生じさせる。
- 参考スコア（独自算出の注目度）: 20.1003622916701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider linearly constrained optimization problems and
propose a loopless projection stochastic approximation (LPSA) algorithm. It
performs the projection with probability $p_n$ at the $n$-th iteration to
ensure feasibility. Considering a specific family of the probability $p_n$ and
step size $\eta_n$, we analyze our algorithm from an asymptotic and continuous
perspective. Using a novel jump diffusion approximation, we show that the
trajectories connecting those properly rescaled last iterates weakly converge
to the solution of specific stochastic differential equations (SDEs). By
analyzing SDEs, we identify the asymptotic behaviors of LPSA for different
choices of $(p_n, \eta_n)$. We find that the algorithm presents an intriguing
asymptotic bias-variance trade-off and yields phase transition phenomenons,
according to the relative magnitude of $p_n$ w.r.t. $\eta_n$. This finding
provides insights on selecting appropriate ${(p_n, \eta_n)}_{n \geq 1}$ to
minimize the projection cost. Additionally, we propose the Debiased LPSA
(DLPSA) as a practical application of our jump diffusion approximation result.
DLPSA is shown to effectively reduce projection complexity compared to vanilla
LPSA.
- Abstract（参考訳）: 本稿では,線形制約付き最適化問題を考察し,ループレス射影確率近似(LPSA)アルゴリズムを提案する。
実行可能性を確保するために、n$-thイテレーションで確率$p_n$でプロジェクションを実行する。
確率 $p_n$ とステップサイズ $\eta_n$ の特定の族を考えると、漸近的かつ連続的な観点からアルゴリズムを分析する。
新しいジャンプ拡散近似を用いて、それらの再スケールされた最後のイテレートを特定の確率微分方程式(sdes)の解に弱収束させる軌道を示す。
SDEを解析することにより、LPSAの漸近挙動を$(p_n, \eta_n)$の異なる選択に対して同定する。
このアルゴリズムは興味深い漸近バイアス分散トレードオフを示し、相対等級$p_n$ w.r.t.$\eta_n$に従って位相遷移現象を生じる。
この発見は射影コストを最小化するために${(p_n, \eta_n)}_{n \geq 1}$を選択するための洞察を与える。
さらに,ジャンプ拡散近似の実用的応用として,脱バイアスLPSA(DLPSA)を提案する。
DLPSAはバニラLPSAと比較してプロジェクションの複雑さを効果的に減少させる。
関連論文リスト
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。
我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Closed-form Filtering for Non-linear Systems [83.91296397912218]
我々は密度近似と計算効率の面でいくつかの利点を提供するガウスPSDモデルに基づく新しいフィルタのクラスを提案する。
本研究では,遷移や観測がガウスPSDモデルである場合,フィルタリングを効率的にクローズド形式で行うことができることを示す。
提案する推定器は, 近似の精度に依存し, 遷移確率の正則性に適応する推定誤差を伴って, 高い理論的保証を享受する。
論文 参考訳（メタデータ） (2024-02-15T08:51:49Z) - Exponential Concentration in Stochastic Approximation [0.8192907805418583]
我々は,各ステップで目標に向かって反復的に進行する近似アルゴリズムの挙動を解析する。
我々はマルコフ近似アルゴリズム、具体的には射影勾配 Descent, Kiefer-Wolfowitz および Frank-Wolfe アルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-08-15T14:57:26Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳（メタデータ） (2021-05-11T08:09:31Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。