論文の概要: Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods
- arxiv url: http://arxiv.org/abs/2301.02268v2
- Date: Mon, 22 Jul 2024 19:29:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 23:52:45.618998
- Title: Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods
- Title（参考訳）: 近似シャープネスを受ける再起動:一階法におけるパラメータフリーかつ最適スキーム
- Authors: Ben Adcock, Matthew J. Colbrook, Maksym Neyra-Nesterenko,
- Abstract要約: シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。
シャープネスは、通常不明な問題固有の定数を伴い、再起動スキームは通常収束率を減少させる。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
- 参考スコア（独自算出の注目度）: 0.6554326244334866
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sharpness is an almost generic assumption in continuous optimization that bounds the distance from minima by objective function suboptimality. It facilitates the acceleration of first-order methods through restarts. However, sharpness involves problem-specific constants that are typically unknown, and restart schemes typically reduce convergence rates. Moreover, these schemes are challenging to apply in the presence of noise or with approximate model classes (e.g., in compressive imaging or learning problems), and they generally assume that the first-order method used produces feasible iterates. We consider the assumption of approximate sharpness, a generalization of sharpness that incorporates an unknown constant perturbation to the objective function error. This constant offers greater robustness (e.g., with respect to noise or relaxation of model classes) for finding approximate minimizers. By employing a new type of search over the unknown constants, we design a restart scheme that applies to general first-order methods and does not require the first-order method to produce feasible iterates. Our scheme maintains the same convergence rate as when the constants are known. The convergence rates we achieve for various first-order methods match the optimal rates or improve on previously established rates for a wide range of problems. We showcase our restart scheme in several examples and highlight potential future applications and developments of our framework and theory.
- Abstract（参考訳）: シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化におけるほぼ一般的な仮定である。
再起動による1次メソッドのアクセラレーションを容易にする。
しかしながら、シャープネスは典型的には未知の問題固有の定数を伴い、再起動スキームは典型的には収束率を減少させる。
さらに、これらのスキームはノイズや近似モデルクラス(例えば、圧縮画像や学習問題)の存在下で適用することは困難であり、一般的に使用される一階法が実現可能な反復を生成すると仮定する。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
この定数は、近似最小値を見つけるためのより強い堅牢性(例えば、モデルクラスのノイズや緩和)を提供する。
未知定数に新しいタイプの探索を適用することで、一般的な一階法に適用し、実現可能なイテレートを生成するために一階法を必要としない再起動方式を設計する。
我々のスキームは定数が知られているときと同じ収束率を維持する。
様々な一階法で達成した収束率は、幅広い問題の最適値と一致するか、以前に確立された速度を改善する。
提案手法をいくつかの例で紹介し,今後のフレームワークと理論の応用と展開について紹介する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Last Iterate Convergence of Incremental Methods and Applications in Continual Learning [10.811735264028348]
連続学習における応用により、漸進的勾配法と漸進的近位法の両方の最後の繰り返しに対する収束保証を得る。
一般化を伴う連続学習のモデルとしての漸進的近位法について検討し,大惨な忘れ込みを防ぐために大量の正規化が不可欠であると主張している。
論文 参考訳（メタデータ） (2024-03-11T16:24:26Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳（メタデータ） (2023-11-04T11:12:24Z) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳（メタデータ） (2023-10-19T13:57:38Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - SCORE: Approximating Curvature Information under Self-Concordant
Regularization [0.0]
本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。
提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
論文 参考訳（メタデータ） (2021-12-14T13:03:04Z) - WARPd: A linearly convergent first-order method for inverse problems
with approximate sharpness conditions [0.0]
シャープネス条件は1次法のリスタートスキームのリカバリ性能を直接制御する。
重み付き, 加速度付き, 再起動されたプリマルデュアル(WARPd)の1次手法を提案する。
一般的な近似的シャープネス条件の下では、WARPd は所望のベクトルに対して安定な線形収束を達成する。
本稿では、WARPdが専門的な最先端手法と比較し、大規模問題の解決に最適であることを示す。
論文 参考訳（メタデータ） (2021-10-24T13:19:41Z) - A Two-Time-Scale Stochastic Optimization Framework with Applications in
Control and Reinforcement Learning [22.07834608976826]
本研究では, 時間変化勾配から試料が生成する問題を解くための2段階勾配法について検討した。
我々は$mathcal(k-2/3O)$の収束が達成されていることを示す。
論文 参考訳（メタデータ） (2021-09-29T23:15:23Z) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳（メタデータ） (2021-07-17T11:45:13Z) - Regret minimization in stochastic non-convex learning via a
proximal-gradient approach [80.59047515124198]
機械学習やオペレーションの応用によって動機づけられた私たちは、オンラインで制約された問題を最小化するために、一階のオラクルフィードバックを後悔しています。
我々は、近位複雑性低減技術を保証する新しいプロキシグレードを開発する。
論文 参考訳（メタデータ） (2020-10-13T09:22:21Z) - DeepInit Phase Retrieval [10.385009647156407]
本稿では,データ深層生成モデルを用いて位相探索問題の解法を提案する。
我々のハイブリッドアプローチは,低サンプリングレートで非常に高い再構成結果が得られることを示す。
論文 参考訳（メタデータ） (2020-07-16T09:39:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。