論文の概要: Block majorization-minimization with diminishing radius for constrained
nonconvex optimization
- arxiv url: http://arxiv.org/abs/2012.03503v5
- Date: Tue, 7 Nov 2023 04:45:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 23:15:46.519413
- Title: Block majorization-minimization with diminishing radius for constrained
nonconvex optimization
- Title（参考訳）: 制限付き非凸最適化のための縮小半径によるブロック偏極最小化
- Authors: Hanbaek Lyu and Yuchen Li
- Abstract要約: BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。
凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
- 参考スコア（独自算出の注目度）: 9.907540661545328
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Block majorization-minimization (BMM) is a simple iterative algorithm for
nonconvex constrained optimization that sequentially minimizes majorizing
surrogates of the objective function in each block coordinate while the other
coordinates are held fixed. BMM entails a large class of optimization
algorithms such as block coordinate descent and its proximal-point variant,
expectation-minimization, and block projected gradient descent. We establish
that for general constrained nonconvex optimization, BMM with strongly convex
surrogates can produce an $\epsilon$-stationary point within
$O(\epsilon^{-2}(\log \epsilon^{-1})^{2})$ iterations and asymptotically
converges to the set of stationary points. Furthermore, we propose a
trust-region variant of BMM that can handle surrogates that are only convex and
still obtain the same iteration complexity and asymptotic stationarity. These
results hold robustly even when the convex sub-problems are inexactly solved as
long as the optimality gaps are summable. As an application, we show that a
regularized version of the celebrated multiplicative update algorithm for
nonnegative matrix factorization by Lee and Seung has iteration complexity of
$O(\epsilon^{-2}(\log \epsilon^{-1})^{2})$. The same result holds for a wide
class of regularized nonnegative tensor decomposition algorithms as well as the
classical block projected gradient descent algorithm. These theoretical results
are validated through various numerical experiments.
- Abstract（参考訳）: BMM(Block Majorization-minimization)は、非凸制約最適化のための単純な反復アルゴリズムであり、各ブロック座標における目的関数のサロゲートを逐次最小化し、他の座標を固定する。
bmmはブロック座標降下とその近点変種、期待最小化、ブロック投影勾配降下といった大きな最適化アルゴリズムを含んでいる。
一般に制約のある非凸最適化では、強凸サロゲートを持つ bmm は $o(\epsilon^{-2}(\log \epsilon^{-1})^{2})$ の反復内に $\epsilon$-stationary point を生成でき、漸近的に定常点の集合に収束する。
さらに, コンベックスのみのサロゲートを処理し, 繰り返しの複雑さと漸近的な定常性が得られるBMMの信頼領域変種を提案する。
これらの結果は、最適性ギャップが要約可能である限り、凸部分問題が不必要に解かれた場合でも頑健に保たれる。
応用として、Lee と Seung による非負行列因数分解のための有名な乗法更新アルゴリズムの正規化バージョンが、反復複雑性$O(\epsilon^{-2}(\log \epsilon^{-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) - Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。
提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。
決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文 参考訳（メタデータ） (2023-11-18T23:06:33Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。
本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。
私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
論文 参考訳（メタデータ） (2022-10-06T17:50:42Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。