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

• arxiv url: http://arxiv.org/abs/2212.11143v4
• Date: Wed, 27 Nov 2024 04:54:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-28 15:22:44.697957
• Title: Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints
• Title（参考訳）: 強い凸関数制約を持つ凸最適化のための高速化一階法
• Authors: Zhenwei Lin, Qi Deng,
• Abstract要約: 強い凸関数制約を受ける凸関数を最小化するために,高速化された原始双対アルゴリズムを導入する。 特にGoogleのパーソナライズされたPageRank問題では、スパシティ誘導最適化におけるメソッドのパフォーマンスが優れています。
• 参考スコア（独自算出の注目度）: 3.1044138971639734
• License:
• Abstract: In this paper, we introduce faster accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex function constraints. Prior to our work, the best complexity bound was $\mathcal{O}(1/{\varepsilon})$, regardless of the strong convexity of the constraint function. It is unclear whether the strong convexity assumption can enable even better convergence results. To address this issue, we have developed novel techniques to progressively estimate the strong convexity of the Lagrangian function. Our approach, for the first time, effectively leverages the constraint strong convexity, obtaining an improved complexity of $\mathcal{O}(1/\sqrt{\varepsilon})$. This rate matches the complexity lower bound for strongly-convex-concave saddle point optimization and is therefore order-optimal. We show the superior performance of our methods in sparsity-inducing constrained optimization, notably Google's personalized PageRank problem. Furthermore, we show that a restarted version of the proposed methods can effectively identify the optimal solution's sparsity pattern within a finite number of steps, a result that appears to have independent significance.
• Abstract（参考訳）: 本稿では,強い凸関数制約を受ける凸関数を最小化するための高速化された原始双対アルゴリズムを提案する。 私たちの研究の前には、制約関数の強い凸性にかかわらず、最も複雑な境界は$\mathcal{O}(1/{\varepsilon})$であった。 強い凸性仮定がより良い収束結果をもたらすかどうかは不明である。 この問題に対処するため、我々はラグランジュ関数の強い凸性を段階的に推定する新しい手法を開発した。 我々のアプローチは、初めて、制約強い凸性を効果的に活用し、$\mathcal{O}(1/\sqrt{\varepsilon})$の複雑さを改善した。 この値は、強凸凹サドル点最適化の複雑さの低い値と一致し、従順最適である。 特にGoogleのパーソナライズされたPageRank問題では,スパーシリティを誘導する制約付き最適化において,メソッドの優れたパフォーマンスを示す。 さらに,提案手法の復号化により,有限ステップで最適解のスパーシティパターンを効果的に同定できることを示す。

関連論文リスト

• 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)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• 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)
• 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)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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