論文の概要: First-order Methods for Affinely Constrained Composite Non-convex
Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods
- arxiv url: http://arxiv.org/abs/2307.07605v1
- Date: Fri, 14 Jul 2023 19:59:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-18 19:08:09.698658
- Title: First-order Methods for Affinely Constrained Composite Non-convex
Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods
- Title（参考訳）: アフィン拘束型非凸非スムース問題の一階法:低複雑性境界法と近最適法
- Authors: Wei Liu, Qihang Lin, Yangyang Xu
- Abstract要約: 合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。
本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
- 参考スコア（独自算出の注目度）: 23.948126336842634
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many recent studies on first-order methods (FOMs) focus on \emph{composite
non-convex non-smooth} optimization with linear and/or nonlinear function
constraints. Upper (or worst-case) complexity bounds have been established for
these methods. However, little can be claimed about their optimality as no
lower bound is known, except for a few special \emph{smooth non-convex} cases.
In this paper, we make the first attempt to establish lower complexity bounds
of FOMs for solving a class of composite non-convex non-smooth optimization
with linear constraints. Assuming two different first-order oracles, we
establish lower complexity bounds of FOMs to produce a (near)
$\epsilon$-stationary point of a problem (and its reformulation) in the
considered problem class, for any given tolerance $\epsilon>0$. In addition, we
present an inexact proximal gradient (IPG) method by using the more relaxed one
of the two assumed first-order oracles. The oracle complexity of the proposed
IPG, to find a (near) $\epsilon$-stationary point of the considered problem and
its reformulation, matches our established lower bounds up to a logarithmic
factor. Therefore, our lower complexity bounds and the proposed IPG method are
almost non-improvable.
- Abstract（参考訳）: 第一次法(FOMs)に関する最近の多くの研究は、線形および/または非線形関数の制約を伴う 'emph{composite non-convex non-smooth} 最適化に焦点を当てている。
これらの方法では、上(または最悪の)複雑性境界が確立されている。
しかし、下限が知られていないため、それらの最適性については、いくつかの特別な \emph{smooth non-convex} の場合を除いて、ほとんど主張できない。
本稿では,線形制約付き合成非凸非平滑最適化のクラスを解くために,FOMのより低い複雑性境界を確立するための最初の試みを行う。
2つの異なる一階オラクルを仮定すると、FOM のより低い複雑性境界を確立して、任意の許容値 $\epsilon>0$ に対して、考慮された問題クラスにおける問題(およびその改革)の(近傍)$\epsilon$-定常点を生成する。
さらに, より緩和された2つの第一次オラクルの1つを用いて, 不正確な近位勾配(IPG)法を提案する。
提案したIGGのオラクル複雑性は、検討された問題の(近く)$\epsilon$-stationary点とその修正を求めるために、確立された下界を対数係数に一致させる。
したがって、より低い複雑性境界と提案したIPG法はほとんど改善不可能である。
関連論文リスト
- 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) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.1044138971639734]
強い凸関数制約を受ける凸関数を最小化するために,高速化された原始双対アルゴリズムを導入する。
特にGoogleのパーソナライズされたPageRank問題では、スパシティ誘導最適化におけるメソッドのパフォーマンスが優れています。
論文 参考訳（メタデータ） (2022-12-21T16:04:53Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。
本稿では,最適化と平滑化次元とのトレードオフを実証する。
論文 参考訳（メタデータ） (2021-04-14T10:42:45Z) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳（メタデータ） (2021-03-29T18:53:57Z) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳（メタデータ） (2021-03-15T11:20:31Z) - On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum
Optimization [1.6973426830397942]
平滑な非有限和最適化における高階法の下限を証明する。
pth-order regularized method は有限和の目的から利益を得ることができないことを示す。
新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
論文 参考訳（メタデータ） (2021-03-08T23:33:58Z) - Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
論文 参考訳（メタデータ） (2021-02-07T21:46:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。