論文の概要: Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates
- arxiv url: http://arxiv.org/abs/2201.01652v3
- Date: Tue, 21 Mar 2023 07:35:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 05:32:47.571302
- Title: Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates
- Title（参考訳）: 弱凸および多重凸代理を持つ確率正則化偏極化
- Authors: Hanbaek Lyu
- Abstract要約: 提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic majorization-minimization (SMM) is a class of stochastic
optimization algorithms that proceed by sampling new data points and minimizing
a recursive average of surrogate functions of an objective function. The
surrogates are required to be strongly convex and convergence rate analysis for
the general non-convex setting was not available. In this paper, we propose an
extension of SMM where surrogates are allowed to be only weakly convex or block
multi-convex, and the averaged surrogates are approximately minimized with
proximal regularization or block-minimized within diminishing radii,
respectively. For the general nonconvex constrained setting with non-i.i.d.
data samples, we show that the first-order optimality gap of the proposed
algorithm decays at the rate $O((\log n)^{1+\epsilon}/n^{1/2})$ for the
empirical loss and $O((\log n)^{1+\epsilon}/n^{1/4})$ for the expected loss,
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+\epsilon}/n^{1/2})$. As a corollary, we obtain the first convergence rate
bounds for various optimization methods under general nonconvex dependent data
setting: Double-averaging projected gradient descent and its generalizations,
proximal point empirical risk minimization, and online matrix/tensor
decomposition algorithms. We also provide experimental validation of our
results.
- Abstract（参考訳）: Stochastic Majorization-minimization (SMM) は、新しいデータポイントをサンプリングし、目的関数のサロゲート関数の再帰平均を最小化する確率最適化アルゴリズムのクラスである。
サーロゲートは強い凸であることが求められ、一般的な非凸設定の収束率解析は利用できなかった。
本稿では, サロゲートが弱凸あるいはブロック多凸のみを許容するsmmの拡張と, 平均サロゲートが近似正規化やブロック最小化によって略最小化されるsmmの拡張を提案する。
非i.i.d.データサンプルを含む一般の非凸制約設定の場合、提案アルゴリズムの一階の最適性ギャップは、経験的損失に対して$o((\log n)^{1+\epsilon}/n^{1/2})、期待損失に対して$o(((\log n)^{1+\epsilon}/n^{1/4})$で減衰する。
別の仮定では、後者の収束率は$O((\log n)^{1+\epsilon}/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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。