論文の概要: Coordinate Descent Methods for Fractional Minimization

• arxiv url: http://arxiv.org/abs/2201.12691v3
• Date: Fri, 24 Mar 2023 05:30:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-27 19:01:06.905739
• Title: Coordinate Descent Methods for Fractional Minimization
• Title（参考訳）: 分数最小化のための座標降下法
• Authors: Ganzhao Yuan
• Abstract要約: 数値部の対象が微分可能凸非線型関数の和であるような構成された分数凸問題のクラスを考える。 この問題は非滑らか収束であるため難しい。 この問題を解決するための2つの方法を提案する。
• 参考スコア（独自算出の注目度）: 7.716156977428555
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a class of structured fractional minimization problems, in which the numerator part of the objective is the sum of a differentiable convex function and a convex non-smooth function, while the denominator part is a convex or concave function. This problem is difficult to solve since it is non-convex. By exploiting the structure of the problem, we propose two Coordinate Descent (CD) methods for solving this problem. The proposed methods iteratively solve a one-dimensional subproblem \textit{globally}, and they are guaranteed to converge to coordinate-wise stationary points. In the case of a convex denominator, under a weak \textit{locally bounded non-convexity condition}, we prove that the optimality of coordinate-wise stationary point is stronger than that of the standard critical point and directional point. Under additional suitable conditions, CD methods converge Q-linearly to coordinate-wise stationary points. In the case of a concave denominator, we show that any critical point is a global minimum, and CD methods converge to the global minimum with a sublinear convergence rate. We demonstrate the applicability of the proposed methods to some machine learning and signal processing models. Our experiments on real-world data have shown that our method significantly and consistently outperforms existing methods in terms of accuracy.
• Abstract（参考訳）: 目的の数値部が微分可能凸関数と凸非滑らか関数の和であり、分母部が凸あるいは凹関数であるような構成された分数最小化問題のクラスを考える。 非凸であるため、この問題は解決が難しい。 問題の構造を利用して,この問題を解決するための2つのコーディネートDescent法を提案する。 提案手法は1次元のsubproblem \textit{globally} を反復的に解き、座標の定常点に収束することが保証される。 凸分母の場合、弱 \textit{locally bounded non-convexity condition} の下では、座標次定常点の最適性が標準臨界点と方向点の最適点よりも強いことが証明される。 追加の適切な条件下では、cd法は座標的に静止点に q-線型収束する。 凹分母の場合、任意の臨界点が大域的最小値であり、cd法は大域的最小値に劣線形収束率で収束することを示す。 提案手法をいくつかの機械学習および信号処理モデルに適用する可能性を示す。 実世界のデータを用いた実験により,提案手法は精度において既存手法よりも著しく優れていた。

関連論文リスト

• Convergence of Some Convex Message Passing Algorithms to a Fixed Point [0.0]
  グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。 これは凸/収束メッセージパッシング(convex/convergent message passing)とも呼ばれる。 アルゴリズムは$mathcalO (1/varepsilon)$ iterationsで終了することを示す。
  論文  参考訳（メタデータ） (2024-03-07T13:14:21Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.716156977428555]
  一般性制約を伴う非滑らかな複合最適化は、統計学習とデータ科学に幅広い応用がある。 textittextbfOBCDは非滑らかな複合問題を解くための新しいブロック座標法である。
  論文  参考訳（メタデータ） (2023-04-07T13:44:59Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• Efficient Algorithms for High-Dimensional Convex Subspace Optimization via Strict Complementarity [19.24470467199451]
  目的が$realsn$, $k$の部分空間を見つけることにある最適化問題を考慮し、凸の滑らかな損失を最小限に抑える。 この問題は高次元のレジームでは高いが、大域的最適解を見つけることは困難である。 本稿では自然について述べる。 収束する最適な次元緩和を 決定するのです グローバルは単純です
  論文  参考訳（メタデータ） (2022-02-08T17:36:43Z)
• Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
  線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
  論文  参考訳（メタデータ） (2021-12-30T20:31:46Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Coordinate Descent Methods for DC Minimization [12.284934135116515]
  差分凸(英: difference-of-Convex、DC)とは、2つの凸関数の差を最小化する問題である。 本稿では,非次元の1次元サブプロブレムを世界規模で提案し,座標の定常点に収束することが保証される。
  論文  参考訳（メタデータ） (2021-09-09T12:44:06Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms [125.99533416395765]
  本稿では,サドル点問題の分散最適化に着目する。 本論文は,本研究における分散手法の有効性を実験的に示すものである。
  論文  参考訳（メタデータ） (2020-10-25T13:13:44Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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