論文の概要: Efficient First-order Methods for Convex Optimization with Strongly
Convex Function Constraints
- arxiv url: http://arxiv.org/abs/2212.11143v3
- Date: Mon, 6 Nov 2023 02:41:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 01:16:47.210189
- Title: Efficient First-order Methods for Convex Optimization with Strongly
Convex Function Constraints
- Title(参考訳): 強凸関数制約付き凸最適化のための効率的一階法
- Authors: Zhenwei Lin, Qi Deng
- Abstract要約: 強い凸関数制約を受ける凸関数を最小化する方法を示す。
有限個の結果に独立な意味を持つような空間パターンを同定する。
- 参考スコア(独自算出の注目度): 3.667453772837954
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we introduce faster first-order primal-dual algorithms for
minimizing a convex function subject to strongly convex function constraints.
Before our work, the best complexity bound was $\mathcal{O}(1/{\varepsilon})$,
and it remains unclear how to improve this result by leveraging the strong
convexity assumption. We address this issue by developing novel techniques to
progressively estimate the strong convexity of the Lagrangian function. Our
approach yields an improved complexity of $\mathcal{O}(1/\sqrt{\varepsilon})$,
matching the complexity lower bound for strongly-convex-concave saddle point
optimization. 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 sparsity pattern of the optimal solution
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問題では,スパーシリティを誘導する制約付き最適化において,メソッドの優れたパフォーマンスを示す。
さらに, 提案手法の再開版では, 最適解のスパーシティパターンを, 有限ステップ内で効果的に識別できることを示した。
関連論文リスト
- An Accelerated Gradient Method for Simple Bilevel Optimization with
Convex Lower-level Problem [17.926211159845224]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳(メタデータ) (2024-02-12T22:34:53Z) - First-order Methods for Affinely Constrained Composite Non-convex
Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。
本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
論文 参考訳(メタデータ) (2023-07-14T19:59:18Z) - 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) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。