論文の概要: The Price of Adaptivity in Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2402.10898v1
- Date: Fri, 16 Feb 2024 18:56:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-19 14:41:50.801484
- Title: The Price of Adaptivity in Stochastic Convex Optimization
- Title(参考訳): 確率凸最適化における適応性の価格
- Authors: Yair Carmon and Oliver Hinder
- Abstract要約: 非平滑凸最適化における適応性に対する不合理性を証明した。
我々は,不確実性による準最適性の乗算的増加を測定する「適応性の値」(PoA)を定義する。
- 参考スコア(独自算出の注目度): 28.088227276891885
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove impossibility results for adaptivity in non-smooth stochastic convex
optimization. Given a set of problem parameters we wish to adapt to, we define
a "price of adaptivity" (PoA) that, roughly speaking, measures the
multiplicative increase in suboptimality due to uncertainty in these
parameters. When the initial distance to the optimum is unknown but a gradient
norm bound is known, we show that the PoA is at least logarithmic for expected
suboptimality, and double-logarithmic for median suboptimality. When there is
uncertainty in both distance and gradient norm, we show that the PoA must be
polynomial in the level of uncertainty. Our lower bounds nearly match existing
upper bounds, and establish that there is no parameter-free lunch.
- Abstract(参考訳): 非滑らかな確率凸最適化における適応性に対する不合理性を証明した。
適応したい問題パラメータの組が与えられると、大まかに言えば、これらのパラメータの不確かさによる部分最適性の乗法的な増加を測定する「適応性の価格」(poa)を定義する。
最適点への初期距離が不明で勾配ノルム境界が知られている場合、PoAは期待される準最適点に対して少なくとも対数的であり、中央値準最適点に対して二重対数的であることを示す。
距離ノルムと勾配ノルムの両方に不確実性が存在する場合、PoA は不確実性のレベルにおける多項式でなければならないことを示す。
我々の下限は既存の上限とほぼ一致し、パラメータフリーのランチが存在しないことを立証する。
関連論文リスト
- Parameter-free projected gradient descent [0.0]
我々は、射影勾配 Descent (PGD) を用いて、閉凸集合上の凸関数を最小化する問題を考える。
本稿では,AdaGradのパラメータフリーバージョンを提案する。これは初期化と最適化の距離に適応し,下位段階の平方ノルムの和に適応する。
提案アルゴリズムはプロジェクションステップを処理でき、リスタートを伴わず、従来のPGDと比較して軌道に沿ってリウィーディングや追加評価を行うことができる。
論文 参考訳(メタデータ) (2023-05-31T07:22:44Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax
Optimization [24.784754071913255]
AdaGradやAMSのような適応アルゴリズムは、非特異なパラメータの堅牢性に成功している。
我々はNeAdaが最適に近いレベルの知識を実現できることを示す。
論文 参考訳(メタデータ) (2022-06-01T20:11:05Z) - The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded
Gradients and Affine Variance [46.15915820243487]
AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。
AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。
論文 参考訳(メタデータ) (2022-02-11T17:37:54Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳(メタデータ) (2021-11-01T15:43:36Z) - Adaptive first-order methods revisited: Convex optimization without
Lipschitz requirements [34.70493893170415]
リプシッツの連続性や滑らか性に欠ける凸最小化問題に対する適応的な一階法の一群を提案する。
適応ミラー降下法 (AdaMir) は, 比較的連続的あるいは滑らかな問題において, min-max 最適率を同時に達成することにより, このギャップを埋めることを目的としている。
論文 参考訳(メタデータ) (2021-07-16T16:59:40Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Implicit differentiation for fast hyperparameter selection in non-smooth
convex learning [87.60600646105696]
内部最適化問題が凸であるが非滑らかである場合の一階法を研究する。
本研究では, ヤコビアンの近位勾配降下と近位座標降下収率列の前方モード微分が, 正確なヤコビアンに向かって収束していることを示す。
論文 参考訳(メタデータ) (2021-05-04T17:31:28Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - GradientDICE: Rethinking Generalized Offline Estimation of Stationary
Values [75.17074235764757]
対象ポリシーの状態分布とサンプリング分布の密度比を推定するグラディエントDICEを提案する。
GenDICEはそのような密度比を推定するための最先端技術である。
論文 参考訳(メタデータ) (2020-01-29T22:10:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。