論文の概要: 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})$に改善できる。
本研究では,オンライン行列およびテンソル分解アルゴリズムに対して,一般マルコフデータ設定下で最初の収束率境界を与える。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - 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 [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。