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

• arxiv url: http://arxiv.org/abs/2006.08426v3
• Date: Mon, 11 Oct 2021 13:51:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 05:12:13.079488
• Title: Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
• Title（参考訳）: 影の中を歩く--制約付き最小化のための降下方向の新しい視点
• Authors: Hassan Mortagy, Swati Gupta, Sebastian Pokutta
• Abstract要約: シャドウ内移動の連続時間ダイナミクスは条件勾配降下(CGD)と等価であることを示す。 シャドーステップは、あらゆる可能な後段の凸殻から発せられる最も良い降下方向を与えると主張する。
• 参考スコア（独自算出の注目度）: 23.547944058374867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Descent directions such as 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 movement in these directions towards attaining constrained minimizers. The best local direction of descent is the directional derivative of the projection of the gradient, which we refer to as the $\textit{shadow}$ of the gradient. We show that the continuous-time dynamics of moving in the shadow are equivalent to those of PGD however non-trivial to discretize. By projecting gradients in PGD, one not only ensures feasibility but is also able to "wrap" around the convex region. We show that Frank-Wolfe (FW) vertices in fact recover the maximal wrap one can obtain by projecting gradients, thus providing a new perspective on these steps. We also claim that the shadow steps give the best direction of descent emanating from the convex hull of all possible away-steps. Viewing PGD movements in terms of shadow steps gives linear convergence, dependent on the number of faces. We combine these insights into a novel $S\small{HADOW}$-$CG$ method that uses FW steps (i.e., wrap around the polytope) and shadow steps (i.e., optimal local descent direction), while enjoying linear convergence. Our analysis develops properties of the curve formed by projecting a line on a polytope, which may be of independent interest, while providing a unifying view of various descent directions in the CGD literature.
• Abstract（参考訳）: フランク=ウルフの頂点への移動, 退行ステップ, 面内退行ステップ, 対方向方向といった未熟な方向は, 条件勾配勾配(CGD)の変種において重要な設計上の考慮事項となっている。 本研究は,制約最小化に向けて,これらの方向の運動の影響を減らそうとするものである。 降下の最良の局所方向は勾配の射影の方向微分であり、これは勾配の$\textit{shadow}$ と呼ばれる。 シャドウ内の移動の連続時間ダイナミクスはpgdのそれと同値であるが、非自明な離散化である。 PGDの勾配を投影することで、実現可能性を保証するだけでなく、凸領域を「ラップ」することができる。 FW(Frank-Wolfe)頂点が実際に勾配を投影することで得られる最大包みを復元できることを示し、これらのステップについて新たな視点を提供する。 我々はまた、シャドウステップはすべての可能な遠方ステップの凸殻から放出される降下の最良の方向を与えると主張する。 影のステップでpgdの動きを見ることは、顔の数に依存する線形収束をもたらす。 これらの知見を、新しい$s\small{hadow}$-$cg$メソッドに組み合わせることで、線形収束を楽しみながら、fwステップ(ポリトープを包む)とシャドーステップ(最適な局所降下方向)を使用する。 解析は,ポリトープ上に直線を投影することによって形成される曲線の特性を解析し,CGD文献における様々な方向の統一的なビューを提供する。

関連論文リスト

• 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)

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

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