論文の概要: 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}$レートの場合、数値的な図解は、手元の最適化問題を特徴づける量の観点から、ステップサイズと境界の最適化された選択により、ステップサイズに対する保守的な選択が減り、期待値の収束の制御がより良くなることを示している。
関連論文リスト
- Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Asymptotic Convergence Rate and Statistical Inference for Stochastic
Sequential Quadratic Programming [59.36379287247961]
制約付き非線形最適化問題を解くために、逐次2次アルゴリズム(StoSQP)を適用する。
分布関数の収束度を定量的に測定するために、$(x_t, lambda_t)$に対してベリー・エスキーを確立する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain [11.562923882714093]
Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。
我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
論文 参考訳（メタデータ） (2021-10-08T07:46:18Z) - The Convergence Rate of SGD's Final Iterate: Analysis on Dimension
Dependence [2.512827436728378]
Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。
定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
論文 参考訳（メタデータ） (2021-06-28T11:51:04Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Stochastic Path-Integrated Differential EstimatoR Expectation
Maximization Algorithm [19.216497414060658]
予測最大化(EM)アルゴリズムは、回帰器と専門家の混在を含む潜在変数モデルにおける推論において重要な要素である。
本稿では,条件予測推定器からの推測のための新しいEMであるtextttSPを提案する。
論文 参考訳（メタデータ） (2020-11-30T15:49:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。