論文の概要: 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次法が実現可能なイテレートを生成すると仮定する。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
この定数は、近似最小子を見つけるためにより強固性(例えば、モデルクラスのノイズや緩和)をもたらす。
未知定数に対する新しいタイプの探索法を用いることで、一般的な一階法に適用し、実現可能なイテレートを生成する一階法を必要としないリスタートスキームを設計する。
我々のスキームは定数の知識を仮定するときと同じ収束率を維持する。
様々な一階法において得られる収束率を最適値に一致させるか、より幅広い問題に対して確立された速度を改善する。
いくつかの例でリスタートスキームを紹介し,今後の応用と枠組みと理論の展開を指摘する。
関連論文リスト
- Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳(メタデータ) (2023-10-19T13:57:38Z) - SCORE: Approximating Curvature Information under Self-Concordant
Regularization [0.0]
本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。
提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
論文 参考訳(メタデータ) (2021-12-14T13:03:04Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳(メタデータ) (2021-11-01T15:43:36Z) - 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) - COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic
Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。
問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。
また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文 参考訳(メタデータ) (2021-09-07T17:21:09Z) - 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) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。