論文の概要: 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法は最適点(座標方向静止点)に線形収束する。
凸分母の場合、結果として生じる問題は準凸であり、任意の臨界点が大域的極小であることを示す。
アルゴリズムが大域的最適解にサブリニア収束率で収束することを証明する。
提案手法をいくつかの機械学習および信号処理モデルに適用する可能性を示す。
実世界のデータを用いた実験により,提案手法は精度において既存手法よりも著しく優れていた。
関連論文リスト
- 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) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳(メタデータ) (2020-10-23T05:24:05Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳(メタデータ) (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。