論文の概要: Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints

• arxiv url: http://arxiv.org/abs/2212.11143v1
• Date: Wed, 21 Dec 2022 16:04:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-22 15:48:41.501248
• Title: Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints
• Title（参考訳）: 強凸関数制約付き凸最適化のための効率的一階法
• Authors: Zhenwei Lin, Qi Deng
• Abstract要約: 我々は,強い凸関数制約を持つ凸問題に対する高速化された原始双対一階法を開発した。 再起動した手法は,有限ステップで最適解のスパーシティパターン(アクティブセット)を効果的に同定できることを示す。 これは空間的制約付き最適化のための最初のアクティブセット識別結果である。
• 参考スコア（独自算出の注目度）: 2.7847784580193284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convex function constrained optimization has received growing research interests lately. For a special convex problem which has strongly convex function constraints, we develop a new accelerated primal-dual first-order method that obtains an $\Ocal(1/\sqrt{\vep})$ complexity bound, improving the $\Ocal(1/{\vep})$ result for the state-of-the-art first-order methods. The key ingredient to our development is some novel techniques to progressively estimate the strong convexity of the Lagrangian function, which enables adaptive step-size selection and faster convergence performance. In addition, we show that the complexity is further improvable in terms of the dependence on some problem parameter, via a restart scheme that calls the accelerated method repeatedly. As an application, we consider sparsity-inducing constrained optimization which has a separable convex objective and a strongly convex loss constraint. In addition to achieving fast convergence, we show that the restarted method can effectively identify the sparsity pattern (active-set) of the optimal solution in finite steps. To the best of our knowledge, this is the first active-set identification result for sparsity-inducing constrained optimization.
• Abstract（参考訳）: 凸関数制約最適化は近年研究の関心を集めている。 厳密な凸関数制約を持つ特別凸問題に対して,99Ocal(1/\sqrt{\vep})$複雑性バウンダリを求め,最先端の1次メソッドに対する$\Ocal(1/{\vep})$結果を改善する,新たなアクセラレーションされた原始双対1次法を開発する。 我々は,ラグランジュ関数の強凸性を漸進的に推定する新しい手法を提案し,適応的なステップサイズ選択とより高速な収束性能を実現する。 さらに,高速化手法を繰り返し呼び出す再起動スキームにより,問題パラメータへの依存度の観点から複雑性がさらに改善可能であることを示す。 アプリケーションとして,分離可能な凸目標と強い凸損失制約を有する空間的制約付き最適化を考える。 高速収束を実現することに加え、再起動した手法は有限ステップで最適解の空間パターン(アクティブセット)を効果的に識別できることが示される。 我々の知る限りでは、これはスパーシリティを誘導する制約付き最適化のための最初のアクティブセット識別結果である。

関連論文リスト

• 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)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Efficient Algorithms for High-Dimensional Convex Subspace Optimization via Strict Complementarity [19.24470467199451]
  目的が$realsn$, $k$の部分空間を見つけることにある最適化問題を考慮し、凸の滑らかな損失を最小限に抑える。 この問題は高次元のレジームでは高いが、大域的最適解を見つけることは困難である。 本稿では自然について述べる。 収束する最適な次元緩和を 決定するのです グローバルは単純です
  論文  参考訳（メタデータ） (2022-02-08T17:36:43Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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