論文の概要: Subgradient methods near active manifolds: saddle point avoidance, local
convergence, and asymptotic normality
- arxiv url: http://arxiv.org/abs/2108.11832v1
- Date: Thu, 26 Aug 2021 15:02:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-27 13:49:06.931681
- Title: Subgradient methods near active manifolds: saddle point avoidance, local
convergence, and asymptotic normality
- Title（参考訳）: 活性多様体近傍の下位手法:サドル点回避、局所収束、漸近正規性
- Authors: Damek Davis, Dmitriy Drusvyatskiy, Liwei Jiang
- Abstract要約: 目的と段階的近似が問題のスムーズな部分構造を完全に表すことを示す。
コーン可逆/分解可能関数や一般半代数問題など、これらの性質が幅広い問題に対して成り立つことを証明している。
正規性の結果は、最も古典的な設定でも新しいように見える。
- 参考スコア（独自算出の注目度）: 4.709588811674973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonsmooth optimization problems arising in practice tend to exhibit
beneficial smooth substructure: their domains stratify into "active manifolds"
of smooth variation, which common proximal algorithms "identify" in finite
time. Identification then entails a transition to smooth dynamics, and
accommodates second-order acceleration techniques. While identification is
clearly useful algorithmically, empirical evidence suggests that even those
algorithms that do not identify the active manifold in finite time -- notably
the subgradient method -- are nonetheless affected by it. This work seeks to
explain this phenomenon, asking: how do active manifolds impact the subgradient
method in nonsmooth optimization?
In this work, we answer this question by introducing two algorithmically
useful properties -- aiming and subgradient approximation -- that fully expose
the smooth substructure of the problem. We show that these properties imply
that the shadow of the (stochastic) subgradient method along the active
manifold is precisely an inexact Riemannian gradient method with an implicit
retraction. We prove that these properties hold for a wide class of problems,
including cone reducible/decomposable functions and generic semialgebraic
problems. Moreover, we develop a thorough calculus, proving such properties are
preserved under smooth deformations and spectral lifts. This viewpoint then
leads to several algorithmic consequences that parallel results in smooth
optimization, despite the nonsmoothness of the problem: local rates of
convergence, asymptotic normality, and saddle point avoidance. The asymptotic
normality results appear to be new even in the most classical setting of
stochastic nonlinear programming. The results culminate in the following
observation: the perturbed subgradient method on generic, Clarke regular
semialgebraic problems, converges only to local minimizers.
- Abstract（参考訳）: 実際には非滑らかな最適化問題は有益な滑らかな部分構造を示す傾向があり、それらの領域は滑らかな変動の「アクティブ多様体」に階層化され、一般的な近位アルゴリズムは有限時間で「特定」される。
識別は滑らかなダイナミクスへの遷移を伴い、二階加速技術に対応する。
同定は明らかに有用なアルゴリズムであるが、経験的証拠は、有限時間で活性多様体を同定しないアルゴリズム(特に下次法)でさえその影響を受けていることを示唆している。
アクティブ多様体は、非滑らか最適化における劣勾配法にどのように影響するか?
本研究では,この問題の滑らかな部分構造を完全に露呈する2つのアルゴリズム的有用特性 -- 目標と下位勾配近似 -- を導入することで,この問題に答える。
これらの性質は、活性多様体に沿った(確率的)劣階法(英語版)の影が、暗黙の退化を伴う不正確なリーマン勾配法であることを示唆している。
これらの性質は、コーン可逆/分解可能関数や一般半代数問題など、幅広い問題に対して成り立つことを証明している。
さらに, 滑らかな変形とスペクトルリフトの下でその性質が保たれていることを証明した。
この視点は、局所収束率、漸近正規性、鞍点回避といった問題の非滑らかさにもかかわらず、並列がスムーズな最適化をもたらすいくつかのアルゴリズム的な結果をもたらす。
漸近的正規性の結果は、確率的非線形プログラミングの最も古典的な設定においても新しいように見える。
ジェネリックなクラーク正則半代数問題に対する摂動劣勾配法は、局所的な最小値にのみ収束する。
関連論文リスト
- Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification [11.495346367359037]
能動多様体同定特性を特徴とする非滑らかな最適化アルゴリズムのクラスについて検討する。
最適化問題が定常点に活性多様体を持つという仮定の下で、アンダーソン加速アルゴリズムの局所 R-線型収束速度を確立する。
論文 参考訳（メタデータ） (2024-10-12T07:55:06Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳（メタデータ） (2023-11-04T11:12:24Z) - Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。
本実験は, 勾配法よりも近似分散還元法の利点を実証する。
論文 参考訳（メタデータ） (2023-08-18T05:11:50Z) - Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。
解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
論文 参考訳（メタデータ） (2023-03-31T02:10:30Z) - Learning Globally Smooth Functions on Manifolds [94.22412028413102]
スムーズな関数の学習は、線形モデルやカーネルモデルなどの単純なケースを除いて、一般的に難しい。
本研究は,半無限制約学習と多様体正規化の技法を組み合わせることで,これらの障害を克服することを提案する。
軽度条件下では、この手法は解のリプシッツ定数を推定し、副生成物として大域的に滑らかな解を学ぶ。
論文 参考訳（メタデータ） (2022-10-01T15:45:35Z) - Gradient flows and randomised thresholding: sparse inversion and
classification [0.0]
スパースインバージョンと分類問題は、現代のデータサイエンスとイメージングにおいて至るところに存在している。
分類において、例えば、データの忠実度項と非滑らかなギンズバーグ-ランダウエネルギーの和を考える。
標準(サブ)勾配降下法はそのような問題にアプローチする際に非効率であることが示されている。
論文 参考訳（メタデータ） (2022-03-22T09:21:14Z) - Stability vs Implicit Bias of Gradient Methods on Separable Data and
Beyond [33.593203156666746]
分離線形分類に適用された非正規化勾配に基づく学習手順の一般化特性に着目する。
この一般化についてさらに統一的な説明をし、実現可能性と自己有界性(self-boundedness)と呼ぶ。
これらのケースのいくつかでは、文献における既存の一般化誤差境界に対して、我々の境界は著しく改善される。
論文 参考訳（メタデータ） (2022-02-27T19:56:36Z) - A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
最適化のための異なる手法を導出できる変分法を導入する。
我々は1対1の対応において最適化手法の2つのファミリを導出する。
自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
論文 参考訳（メタデータ） (2021-06-04T20:21:53Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic
Optimization Problems [12.010310883787911]
我々は、弱凸(おそらく非滑らかな)最適化問題の重要なクラスを解くための、適応的な段階的な新しい手法の族を解析する。
実験結果から,提案アルゴリズムが0次勾配降下と設計変動を経験的に上回ることを示す。
論文 参考訳（メタデータ） (2020-05-19T07:44:52Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。