論文の概要: Block majorization-minimization with diminishing radius for constrained
nonconvex optimization
- arxiv url: http://arxiv.org/abs/2012.03503v4
- Date: Fri, 25 Aug 2023 05:48:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-28 18:31:47.654558
- 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})$であることを示す。
同じ結果は、正規化された非負のテンソル分解アルゴリズムと古典的ブロック投影勾配勾配アルゴリズムの幅広いクラスに当てはまる。
これらの理論結果は様々な数値実験によって検証される。
関連論文リスト
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。
この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-11-21T22:06:25Z) - 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) - Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization [18.425648833592312]
ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
論文 参考訳（メタデータ） (2023-12-16T05:40:19Z) - Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。
提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。
決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文 参考訳（メタデータ） (2023-11-18T23:06:33Z) - 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) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。