論文の概要: On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems

• arxiv url: http://arxiv.org/abs/2107.08225v1
• Date: Sat, 17 Jul 2021 11:45:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-21 06:34:43.079564
• Title: On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• Title（参考訳）: 一階最適化における制約について--非スムース力学系からの考察
• Authors: Michael Muehlebach and Michael I. Jordan
• Abstract要約: 本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
• 参考スコア（独自算出の注目度）: 99.59934203759754
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a class of first-order methods for smooth constrained optimization that are based on an analogy to non-smooth dynamical systems. Two distinctive features of our approach are that (i) projections or optimizations over the entire feasible set are avoided, in stark contrast to projected gradient methods or the Frank-Wolfe method, and (ii) iterates are allowed to become infeasible, which differs from active set or feasible direction methods, where the descent motion stops as soon as a new constraint is encountered. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear, and is suitable for large-scale constrained optimization problems in which the feasible set fails to have a simple structure. The key underlying idea is that constraints are expressed in terms of velocities instead of positions, which has the algorithmic consequence that optimizations over feasible sets at each iteration are replaced with optimizations over local, sparse convex approximations. The result is a simplified suite of algorithms and an expanded range of possible applications in machine learning.
• Abstract（参考訳）: 非スムース力学系に類似した滑らかな制約付き最適化のための一階法のクラスを導入する。 提案手法の2つの特徴は, (i) 提案した勾配法やフランク・ウルフ法とは対照的に, (i) 適用可能な集合全体の投影や最適化は避けられ, (ii) 有効セットや実現可能な方向法と異なり, 新たな制約に遭遇した時点で降下動作が停止する。 得られたアルゴリズムの手順は、制約が非線形であっても実装が簡単であり、実現可能な集合が単純な構造を持たないような大規模制約付き最適化問題に適合する。 鍵となる考え方は、制約は位置ではなく速度で表され、各反復における実現可能な集合に対する最適化が局所凸近似上の最適化に置き換えられるというアルゴリズム的な結果である。 その結果、アルゴリズムの簡易化と、機械学習の応用範囲の拡大がもたらされた。

関連論文リスト

• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  一階最適化法は、未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。
  論文  参考訳（メタデータ） (2023-05-27T18:16:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。 我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
  論文  参考訳（メタデータ） (2021-07-23T13:43:34Z)
• A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians [11.03311584463036]
  滑らかな非線形等式制約最適化問題の解法として, 逐次2次最適化アルゴリズムを提案する。 数値実験の結果、このアルゴリズムは一般的な代替品と比較して優れた性能を示すことが示された。
  論文  参考訳（メタデータ） (2021-06-24T13:46:52Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints [8.643249539674612]
  本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。 まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。 さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
  論文  参考訳（メタデータ） (2020-06-30T23:49:38Z)

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

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