論文の概要: Restarts subject to approximate sharpness: A parameter-free and optimal
scheme for first-order methods
- arxiv url: http://arxiv.org/abs/2301.02268v1
- Date: Thu, 5 Jan 2023 19:01:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 23:32:19.203325
- 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)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。
シャープネスは、通常不明な問題固有の定数を伴い、以前の再起動スキームは収束率を減少させる。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
- 参考スコア（独自算出の注目度）: 2.513785998932353
- 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 leads
to the acceleration of first-order methods via restarts. However, sharpness
involves problem-specific constants that are typically unknown, and previous
restart schemes reduce convergence rates. Moreover, such schemes are
challenging to apply in the presence of noise or approximate model classes
(e.g., in compressive imaging or learning problems), and typically 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 assuming knowledge of the constants. The rates of convergence we
obtain for various first-order methods either match the optimal rates or
improve on previously established rates for a wide range of problems. We
showcase our restart scheme on several examples and point to 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) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳（メタデータ） (2023-10-19T13:57:38Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - 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) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳（メタデータ） (2021-07-17T11:45:13Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。