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

• arxiv url: http://arxiv.org/abs/2201.12691v1
• Date: Sun, 30 Jan 2022 00:47:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-02 12:14:50.842955
• Title: Coordinate Descent Methods for Fractional Minimization
• Title（参考訳）: 分数最小化のための座標降下法
• Authors: Ganzhao Yuan
• Abstract要約: 数値部が微分凸関数の和であるような構成された分数分数問題について考察する。 元の分数関数を利用するための2つの協調Descent(CD)手法を提案する。 提案手法が既存の手法よりも精度的に優れていることを示す。
• 参考スコア（独自算出の注目度）: 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 nonsmooth function, while the denominator part is a concave or convex function. This problem is difficult to solve since it is nonconvex. By exploiting the structure of the problem, we propose two Coordinate Descent (CD) methods for solving this problem. One is applied to the original fractional function, the other is based on the associated parametric 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, we prove that the proposed CD methods using sequential nonconvex approximation find stronger stationary points than existing methods. Under suitable conditions, CD methods with an appropriate initialization converge linearly to the optimal point (also the coordinate-wise stationary point). In the case of a concave denominator, we show that the resulting problem is quasi-convex, and any critical point is a global minimum. We prove that the algorithms converge to the global optimal solution 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つは元の分数関数に適用され、もう1つは関連するパラメトリック問題に基づいている。 提案手法は1次元のsubproblem \textit{globally} を反復的に解き、座標の定常点に収束することが保証される。 凸分母の場合、シーケンシャルな非凸近似を用いたcd法が既存の方法よりも強い定常点を求めることが証明される。 適切な条件下では、適切な初期化を持つcd法は最適点(座標方向静止点)に線形収束する。 凸分母の場合、結果として生じる問題は準凸であり、任意の臨界点が大域的極小であることを示す。 アルゴリズムが大域的最適解にサブリニア収束率で収束することを証明する。 提案手法をいくつかの機械学習および信号処理モデルに適用する可能性を示す。 実世界のデータを用いた実験により,提案手法は精度において既存手法よりも著しく優れていた。

関連論文リスト

• ADMM for Structured Fractional Minimization [7.9047096855236125]
  我々は、数値化器が微分可能な関数を含むような、構造化された分数問題のクラスを考える。 本稿では,このクラスの問題に対して,最初の乗算器の交換法であるsf FADMMを紹介する。
  論文  参考訳（メタデータ） (2024-11-12T02:50:12Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• 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)
• 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)

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

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