論文の概要: The Price of Adaptivity in Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2402.10898v2
• Date: Wed, 13 Mar 2024 21:42:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-16 01:32:47.176263
• Title: The Price of Adaptivity in Stochastic Convex Optimization
• Title（参考訳）: 確率凸最適化における適応性の価格
• Authors: Yair Carmon, Oliver Hinder,
• Abstract要約: 非平滑凸最適化における適応性に対する不合理性を証明した。 我々は,不確実性による準最適性の乗算的増加を測定する「適応性の値」(PoA)を定義する。
• 参考スコア（独自算出の注目度）: 23.776027867314628
• 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（参考訳）: 非滑らかな確率凸最適化における適応性に対する不合理性を証明した。 適応したい問題パラメータのセットが与えられた場合、我々は、大まかに言えば、これらのパラメータの不確実性によるサブ最適性の乗法的増加を測定する「適応性(price of adaptivity)」(PoA)を定義する。 最適点への初期距離が不明で勾配ノルム境界が知られている場合、PoAは期待される準最適点に対して少なくとも対数的であり、中央値の準最適点に対して二重対数的であることを示す。 距離ノルムと勾配ノルムの両方に不確実性が存在する場合、PoA は不確実性のレベルにおける多項式でなければならないことを示す。 我々の下限は、既存の上限とほぼ一致し、パラメータフリーランチがないことを証明します。

関連論文リスト

• Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
  AdaGradは特定の条件下では$d$でSGDより優れていることを示す。 これを動機として、目的物の滑らかさ構造と勾配のばらつきを仮定する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• 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)
• Making SGD Parameter-Free [28.088227276891885]
  我々のアルゴリズムは概念的には単純で、高い確率保証を持ち、未知の勾配ノルム、滑らかさ、強い凸性に部分的に適応している。 結果の核心は,SGDステップサイズ選択のための新しいパラメータフリー証明書と,SGDのa-プリオリ境界が反復しないと仮定する時間一様濃度の結果である。
  論文  参考訳（メタデータ） (2022-05-04T16:29:38Z)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う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)
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
  我々は、勾配収束法を期待する適応勾配法を証明した。 解析では、非理解勾配境界の最適化において、より適応的な勾配法に光を当てた。
  論文  参考訳（メタデータ） (2018-08-16T20:25:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。