論文の概要: Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization

• arxiv url: http://arxiv.org/abs/2006.08426v4
• Date: Wed, 30 Aug 2023 17:19:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-31 18:32:43.839572
• Title: Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
• Title（参考訳）: 影の中を歩く--制約付き最小化のための降下方向の新しい視点
• Authors: Hassan Mortagy, Swati Gupta, Sebastian Pokutta
• Abstract要約: 影内移動の連続時間ダイナミクスは、投影勾配降下(PGD)のダイナミクスと等価であることを示す。 我々はこれらの知見を,線形収束を楽しみながらFWとシャドウステップを利用する新しいシャドウ-CG手法に組み合わせる。 単純なポリトープに対するブレークポイント数に対する線形境界と、一般的なポリトープに対するスケーリング不変な上限を与える。
• 参考スコア（独自算出の注目度）: 29.861939940760898
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Descent directions such as movement towards Descent directions, including movement towards Frank-Wolfe vertices, away-steps, in-face away-steps and pairwise directions, have been an important design consideration in conditional gradient descent (CGD) variants. In this work, we attempt to demystify the impact of the movement in these directions towards attaining constrained minimizers. The optimal local direction of descent is the directional derivative (i.e., shadow) of the projection of the negative gradient. We show that this direction is the best away-step possible, and the continuous-time dynamics of moving in the shadow is equivalent to the dynamics of projected gradient descent (PGD), although it's non-trivial to discretize. We also show that Frank-Wolfe (FW) vertices correspond to projecting onto the polytope using an "infinite" step in the direction of the negative gradient, thus providing a new perspective on these steps. We combine these insights into a novel Shadow-CG method that uses FW and shadow steps, while enjoying linear convergence, with a rate that depends on the number of breakpoints in its projection curve, rather than the pyramidal width. We provide a linear bound on the number of breakpoints for simple polytopes and present scaling-invariant upper bounds for general polytopes based on the number of facets. We exemplify the benefit of using Shadow-CG computationally for various applications, while raising an open question about tightening the bound on the number of breakpoints for general polytopes.
• Abstract（参考訳）: フランク=ウルフの頂点への移動, 後ステップ, 内ステップ, 対方向など, 未成年方向への移動は, 条件勾配降下(CGD)変種において重要な設計上の考慮事項となっている。 本研究は,制約最小化に向けて,これらの方向における運動の影響を減らそうとするものである。 降下の最適局所方向は、負勾配の投影の方向微分(すなわち影)である。 我々は,この方向が最善逆行であり,影内移動の連続時間ダイナミクスは,離散化は容易ではないが,投影勾配降下(PGD)のダイナミクスと等価であることを示した。 また,frank-wolfe(fw)頂点は,負勾配方向の"無限"ステップを用いてポリトープへの射影に対応し,これらのステップに対する新たな視点を提供する。 我々はこれらの知見を,FWとシャドウステップを用いた新しいシャドウCG法と,ピラミッドの幅よりも射影曲線のブレークポイント数に依存する速度で線形収束を楽しみながら組み合わせた。 単純なポリトープに対するブレークポイント数に対する線形境界と、ファセット数に基づく一般的なポリトープに対するスケーリング不変な上限を与える。 一般のポリトープのブレークポイント数に対する制限の厳密化について,オープンな疑問を提起しながら,Shadow-CGを様々なアプリケーションに利用することのメリットを実証する。

関連論文リスト

• Level Set Teleportation: An Optimization Perspective [21.84775414778289]
  勾配法を高速化する最適化サブルーチンであるレベルセットテレポーテーションについて検討する。 ヘッセン安定度を満たす凸関数に対して、レベルセットのテレポーテーションを持つ GD が標準 GD よりも厳密に高速な結合線型/線形収束率を得ることを示す。 これは、レベルセットのテレポーテーションが改善せず、収束率を悪化させるような標準(強く)凸設定とは対照的である。
  論文  参考訳（メタデータ） (2024-03-05T23:16:13Z)
• Corridor Geometry in Gradient-Based Optimization [11.177186975058047]
  廊下は、勾配降下と勾配流が同じ軌跡をたどる領域であることを示す。 廊下における損失線形減少を利用して、勾配降下に対する学習率適応方式を考案する。
  論文  参考訳（メタデータ） (2024-02-13T21:54:15Z)
• How to guess a gradient [68.98681202222664]
  我々は、勾配が以前考えられていたよりもより構造化されていることを示す。 この構造をエクスプロイトすると、勾配のない最適化スキームが大幅に改善される。 厳密な勾配の最適化と勾配の推測の間に大きなギャップを克服する上での新たな課題を強調した。
  論文  参考訳（メタデータ） (2023-12-07T21:40:44Z)
• Neural Gradient Learning and Optimization for Oriented Point Normal Estimation [53.611206368815125]
  本研究では,3次元点雲から勾配ベクトルを一貫した向きで学習し,正規推定を行うためのディープラーニング手法を提案する。 局所平面幾何に基づいて角距離場を学習し、粗勾配ベクトルを洗練する。 本手法は,局所特徴記述の精度と能力の一般化を図りながら,グローバル勾配近似を効率的に行う。
  論文  参考訳（メタデータ） (2023-09-17T08:35:11Z)
• Parameter-free projected gradient descent [0.0]
  我々は、射影勾配 Descent (PGD) を用いて、閉凸集合上の凸関数を最小化する問題を考える。 本稿では,AdaGradのパラメータフリーバージョンを提案する。これは初期化と最適化の距離に適応し,下位段階の平方ノルムの和に適応する。 提案アルゴリズムはプロジェクションステップを処理でき、リスタートを伴わず、従来のPGDと比較して軌道に沿ってリウィーディングや追加評価を行うことができる。
  論文  参考訳（メタデータ） (2023-05-31T07:22:44Z)
• The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minima [41.961056785108845]
  我々は、ディープネットワークの勾配に基づく最適化手法であるシャープネス認識最小化について検討する。 SAM に凸2次対象を施すと、最も大きい曲率で最小方向の両辺の間で振動するサイクルに収束することを示す。 非二次的の場合、そのような振動は、ヘッセンのスペクトルノルムに基づいて、より小さなステップサイズで勾配降下を効果的に実行することを示す。
  論文  参考訳（メタデータ） (2022-10-04T10:34:37Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。 本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
  論文  参考訳（メタデータ） (2021-12-08T08:23:37Z)
• On Training Implicit Models [75.20173180996501]
  ファントム勾配(ファントム勾配)と呼ばれる暗黙モデルに対する新しい勾配推定法を提案し、正確な勾配の計算コストを抑える。 大規模タスクの実験では、これらの軽量ファントム勾配が暗黙の訓練モデルの後方通過を約1.7倍加速することを示した。
  論文  参考訳（メタデータ） (2021-11-09T14:40:24Z)
• Projective Manifold Gradient Layer for Deep Rotation Regression [49.85464297105456]
  ディープニューラルネットワークを用いたSO(3)多様体上の回帰回転は重要な問題であるが未解決である。 ネットワーク重みに直接逆伝搬する多様体対応勾配を提案する。
  論文  参考訳（メタデータ） (2021-10-22T08:34:15Z)
• Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
  滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。 スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。 バイリニアゲームに最適なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-02T19:21:48Z)

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

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