論文の概要: Accelerated First-Order Optimization under Nonlinear Constraints

• arxiv url: http://arxiv.org/abs/2302.00316v1
• Date: Wed, 1 Feb 2023 08:50:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-02 13:15:09.020366
• Title: Accelerated First-Order Optimization under Nonlinear Constraints
• Title（参考訳）: 非線形制約下での高速化一階最適化
• Authors: Michael Muehlebach and Michael I. Jordan
• Abstract要約: 制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。 これらのアルゴリズムの重要な性質は制約の数である。 我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
• 参考スコア（独自算出の注目度）: 97.16266088683061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. We prove convergence to stationary points even in a nonconvex setting and we derive rates for the convex setting. An important property of these algorithms is that constraints are expressed in terms of velocities instead of positions, which naturally leads to sparse, local and convex approximations of the feasible set (even if the feasible set is nonconvex). Thus, the complexity tends to grow mildly in the number of decision variables and in the number of constraints, which makes the algorithms suitable for machine learning applications. We apply our algorithms to a compressed sensing and a sparse regression problem, showing that we can treat nonconvex $\ell^p$ constraints ($p<1$) efficiently, while recovering state-of-the-art performance for $p=1$.
• Abstract（参考訳）: 制約付き最適化のための一階アルゴリズムと非スムース力学系との類似性を生かして、制約付き最適化のための新しい加速一階アルゴリズムのクラスを設計する。 フランクウルフや投影勾配とは異なり、これらのアルゴリズムは各イテレーションで実現可能な集合全体の最適化を避ける。 非凸設定においても定常点への収束を証明し、凸設定のレートを導出する。 これらのアルゴリズムの重要な性質は、制約が位置ではなく速度で表現されることであり、これは自然に実現可能な集合のスパース、局所、凸近似をもたらす(実現可能な集合が非凸であっても)。 したがって、複雑性は決定変数の数や制約の数で緩やかに増大する傾向にあり、機械学習アプリケーションに適したアルゴリズムとなっている。 圧縮センシングとスパース回帰問題に適用し,非凸$\ell^p$制約(p<1$)を効率的に扱えるとともに,最先端性能を$p=1$で回復できることを示す。

関連論文リスト

• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [8.59102802625914]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合、分散と還元のアルゴリズムも検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization [13.170519806372075]
  2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。 最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。 提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
  論文  参考訳（メタデータ） (2021-07-14T08:01:30Z)
• Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
  我々は,後悔最適アルゴリズムの存在,一意性,一貫性について検討する。 制御問題に対する一階最適条件を提供することにより、後悔最適アルゴリズムはそれらの力学において特定の構造を満たす必要があることを示す。 それらを近似する高速な数値法を提案し,長期的後悔を直接最適化する最適化アルゴリズムを生成する。
  論文  参考訳（メタデータ） (2020-12-31T19:13:53Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization [73.38702974136102]
  アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。 本論文では,非滑らかな問題を解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:06:27Z)

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

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