論文の概要: Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization

• arxiv url: http://arxiv.org/abs/2012.03503v6
• Date: Fri, 29 Nov 2024 00:04:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-02 15:15:58.399803
• Title: Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization
• Title（参考訳）: 制限付き非滑らかな非凸最適化のための縮小半径によるブロック偏極最小化
• Authors: Hanbaek Lyu, Yuchen Li,
• Abstract要約: BMM(Block Majorization-minimativeization)は、制約付き非負のサロゲートに対する単純な反復アルゴリズムである。 BMMは,様々なアルゴリズムに対して,新しい一階最適度尺度を生成する。 また, BMM の収束率を向上させるために, 減衰半径の付加的利用が有効であることを示す。
• 参考スコア（独自算出の注目度）: 8.386501595252
• License:
• Abstract: Block majorization-minimization (BMM) is a simple iterative algorithm for constrained nonconvex optimization that sequentially minimizes majorizing surrogates of the objective function in each block while the others 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 first establish that for general constrained nonsmooth nonconvex optimization, BMM with $\rho$-strongly convex and $L_g$-smooth surrogates can produce an $\epsilon$-approximate first-order optimal point within $\widetilde{O}((1+L_g+\rho^{-1})\epsilon^{-2})$ iterations and asymptotically converges to the set of first-order optimal points. Next, we show that BMM combined with trust-region methods with diminishing radius has an improved complexity of $\widetilde{O}((1+L_g) \epsilon^{-2})$, independent of the inverse strong convexity parameter $\rho^{-1}$, allowing improved theoretical and practical performance with `flat' surrogates. Our results hold robustly even when the convex sub-problems are solved as long as the optimality gaps are summable. Central to our analysis is a novel continuous first-order optimality measure, by which we bound the worst-case sub-optimality in each iteration by the first-order improvement the algorithm makes. We apply our general framework to obtain new results on various algorithms such as the celebrated multiplicative update algorithm for nonnegative matrix factorization by Lee and Seung, regularized nonnegative tensor decomposition, and the classical block projected gradient descent algorithm. Lastly, we numerically demonstrate that the additional use of diminishing radius can improve the convergence rate of BMM in many instances.
• Abstract（参考訳）: BMM(Block Majorization-minimization)は、制約付き非凸最適化のための単純な反復アルゴリズムであり、各ブロックの目的関数のサロゲートを逐次最小化し、他のブロックを固定する。 BMMは、ブロック座標降下とその近点変種、期待最小化、ブロック投影勾配勾配といった、多数の最適化アルゴリズムを必要とする。 一般化された非滑らかな非凸最適化に対して、BMMは$\rho$-strongly convexと$L_g$-smooth surrogatesで$\epsilon$-approximate 1次最適点を$\widetilde{O}((1+L_g+\rho^{-1})\epsilon^{-2})$反復と漸近的に一階最適点の集合に収束させることができることを最初に証明した。 次に, 半径が減少する信頼領域法と組み合わせたBMMは, 逆の強い凸性パラメータ$\rho^{-1}$とは独立に, $\widetilde{O}((1+L_g) \epsilon^{-2})$の複雑さが向上し, 「フラット」サロゲートを用いた理論的および実用的性能が向上することを示した。 最適性ギャップが和らげられる限り, 凸部分確率が解ける場合でも, 結果は頑健に保たれる。 我々の分析の中心は、アルゴリズムが行う一階改善によって、各イテレーションの最悪の部分最適度を拘束する、新しい一階最適度尺度である。 我々は,Lee と Seung による非負行列分解のための有望な乗算的更新アルゴリズム,正規化非負のテンソル分解,古典ブロック投影勾配降下アルゴリズムなど,様々なアルゴリズムの新しい結果を得るために,我々の一般フレームワークを適用した。 最後に, BMM の収束率を向上させるために, 減少半径の付加的利用が有効であることを示す。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。