論文の概要: Fast Incremental Expectation Maximization for finite-sum optimization:
nonasymptotic convergence
- arxiv url: http://arxiv.org/abs/2012.14670v1
- Date: Tue, 29 Dec 2020 09:11:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 20:50:06.055295
- Title: Fast Incremental Expectation Maximization for finite-sum optimization:
nonasymptotic convergence
- Title（参考訳）: 有限サム最適化のための高速増分期待最大化:漸近収束
- Authors: Gersende Fort (IMT), P. Gach (IMT), E. Moulines (CMAP, XPOP)
- Abstract要約: 本稿では,EM フレームワーク内の em 近似において,Fast Incremental expectation Maximization (FIEM) およびその他のインクリメンタル EM 型アルゴリズムを再放送する。
私たちは、例の$n$とイテレーションの最大数$kmax$の関数として期待の収束のための非漸近境界を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Fast Incremental Expectation Maximization (FIEM) is a version of the EM
framework for large datasets. In this paper, we first recast FIEM and other
incremental EM type algorithms in the {\em Stochastic Approximation within EM}
framework. Then, we provide nonasymptotic bounds for the convergence in
expectation as a function of the number of examples $n$ and of the maximal
number of iterations $\kmax$. We propose two strategies for achieving an
$\epsilon$-approximate stationary point, respectively with $\kmax =
O(n^{2/3}/\epsilon)$ and $\kmax = O(\sqrt{n}/\epsilon^{3/2})$, both strategies
relying on a random termination rule before $\kmax$ and on a constant step size
in the Stochastic Approximation step. Our bounds provide some improvements on
the literature. First, they allow $\kmax$ to scale as $\sqrt{n}$ which is
better than $n^{2/3}$ which was the best rate obtained so far; it is at the
cost of a larger dependence upon the tolerance $\epsilon$, thus making this
control relevant for small to medium accuracy with respect to the number of
examples $n$. Second, for the $n^{2/3}$-rate, the numerical illustrations show
that thanks to an optimized choice of the step size and of the bounds in terms
of quantities characterizing the optimization problem at hand, our results
desig a less conservative choice of the step size and provide a better control
of the convergence in expectation.
- Abstract（参考訳）: Fast Incremental expectation Maximization (FIEM)は、大規模なデータセットのためのEMフレームワークのバージョンである。
本稿では, EM フレームワーク内での確率近似において, FIEM などの漸進的 EM 型アルゴリズムを最初に再放送する。
すると、予想の収束に対する漸近的境界は、例数$n$と反復の最大数$\kmax$の関数として与えられる。
我々は,それぞれ$\kmax = o(n^{2/3}/\epsilon)$と$\kmax = o(\sqrt{n}/\epsilon^{3/2})$の2つの定常点を達成する戦略を提案する。
私たちの限界は文学にいくつかの改善をもたらす。
まず、$\kmax$が$\sqrt{n}$としてスケールすることを許可し、これはこれまでで最高のレートであった$n^{2/3}$よりも優れている。
第2に、$n^{2/3}$レートの場合、数値的な図解は、手元の最適化問題を特徴づける量の観点から、ステップサイズと境界の最適化された選択により、ステップサイズに対する保守的な選択が減り、期待値の収束の制御がより良くなることを示している。
関連論文リスト
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。
我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Further Understanding of a Local Gaussian Process Approximation: Characterising Convergence in the Finite Regime [1.3518297878940662]
非常に正確かつ大規模に拡張可能なGPnn回帰モデルに対するカーネル関数の一般的な選択は、データセットサイズ$n$の増加に伴って徐々に振る舞いに収束することを示す。
同様の境界はモデルの不特定の下で見出され、MSEと重要な校正計量の総合的な収束率を与えるために組み合わせられる。
論文 参考訳（メタデータ） (2024-04-09T10:47:01Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - A Stochastic Path-Integrated Differential EstimatoR Expectation
Maximization Algorithm [19.216497414060658]
予測最大化(EM)アルゴリズムは、回帰器と専門家の混在を含む潜在変数モデルにおける推論において重要な要素である。
本稿では,条件予測推定器からの推測のための新しいEMであるtextttSPを提案する。
論文 参考訳（メタデータ） (2020-11-30T15:49:31Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。