論文の概要: Convergence and Complexity of Stochastic Block Majorization-Minimization
- arxiv url: http://arxiv.org/abs/2201.01652v1
- Date: Wed, 5 Jan 2022 15:17:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-06 15:43:40.227546
- Title: Convergence and Complexity of Stochastic Block Majorization-Minimization
- Title(参考訳): 確率的ブロック最大化最小化の収束と複雑性
- Authors: Hanbaek Lyu
- Abstract要約: Relaxing Majorization-minimization (SMM)は、Majorization-minimizationの原則のオンライン拡張である。
本稿では,後者の収束ブロックの最大化最小化について述べる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic majorization-minimization (SMM) is an online extension of the
classical principle of majorization-minimization, which consists of sampling
i.i.d. data points from a fixed data distribution and minimizing a recursively
defined majorizing surrogate of an objective function. In this paper, we
introduce stochastic block majorization-minimization, where the surrogates can
now be only block multi-convex and a single block is optimized at a time within
a diminishing radius. Relaxing the standard strong convexity requirements for
surrogates in SMM, our framework gives wider applicability including online
CANDECOMP/PARAFAC (CP) dictionary learning and yields greater computational
efficiency especially when the problem dimension is large. We provide an
extensive convergence analysis on the proposed algorithm, which we derive under
possibly dependent data streams, relaxing the standard i.i.d. assumption on
data samples. We show that the proposed algorithm converges almost surely to
the set of stationary points of a nonconvex objective under constraints at a
rate $O((\log n)^{1+\eps}/n^{1/2})$ for the empirical loss function and
$O((\log n)^{1+\eps}/n^{1/4})$ for the expected loss function, where $n$
denotes the number of data samples processed. Under some additional assumption,
the latter convergence rate can be improved to $O((\log n)^{1+\eps}/n^{1/2})$.
Our results provide first convergence rate bounds for various online matrix and
tensor decomposition algorithms under a general Markovian data setting.
- Abstract(参考訳): Stochastic Majorization-minimization (SMM) は、固定データ分布からデータポイントをサンプリングし、目的関数の再帰的に定義されたMajorization surrogateを最小化する古典的なMajorization-minimizationのオンライン拡張である。
本稿では,サロゲートが多重凸のみをブロックし,単一ブロックが縮小半径内で一度に最適化される確率的ブロック偏化最小化を提案する。
SMMにおけるサロゲートの標準凸性要件を緩和し、オンラインCANDECOMP/PARAFAC(CP)辞書学習を含む幅広い適用性を提供し、特に問題次元が大きい場合の計算効率を向上する。
提案手法は,データサンプルに対する標準i.i.d.仮定を緩和し,潜在的に依存するデータストリームを導出する。
提案アルゴリズムは,実験損失関数に対して$O((\log n)^{1+\eps}/n^{1/2})$,期待損失関数に対して$O((\log n)^{1+\eps}/n^{1/4})$で制約の下で,非凸対象の定常点の集合にほぼ確実に収束することを示す。
追加の仮定の下では、後者の収束率は$o((\log n)^{1+\eps}/n^{1/2})$に改善できる。
本研究では,オンライン行列およびテンソル分解アルゴリズムに対して,一般マルコフデータ設定下で最初の収束率境界を与える。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds [12.699376765058137]
勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
論文 参考訳(メタデータ) (2023-06-21T18:14:44Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。
本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。
私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
論文 参考訳(メタデータ) (2022-10-06T17:50:42Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳(メタデータ) (2021-11-12T01:51:50Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - Block majorization-minimization with diminishing radius for constrained
nonconvex optimization [9.907540661545328]
BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。
凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
論文 参考訳(メタデータ) (2020-12-07T07:53:09Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。