論文の概要: Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles

• arxiv url: http://arxiv.org/abs/2607.17607v1
• Date: Mon, 20 Jul 2026 06:53:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.515749
• Title: Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
• Title（参考訳）: プレコンディショナの最適化 - 静的レギュレット最小化Oracleによるブラックボックスのオンライン-ノンコンベックス変換
• Abstract要約: 非最適化は、ブラックボックス方式でオンライン凸最適化において通常の静的に還元できる。 スムーズな非目的に対して、当社の削減は予測可能な勾配トラッカーを維持し、ブラックボックスは固定されたMをオンラインに選択する。 オンラインでブラックボックスがaを選択します。 オンラインのブラックボックスはグラデーショントラッカーを選択し、トラッカーがグラデーションにどのように変換されるかを決定する。 A。 Black-box Onlineは、トラッカーがグラデーションにどのように変換されるかを決定する固定されたMを選択する。 A。 オンラインのブラックボックスがグラデーショントラッカーを選択し、トラッカーがaに変換される方法を決定する
• 参考スコア（独自算出の注目度）: 15.386375612838371
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study whether stochastic nonconvex optimization can be reduced to ordinary static regret minimization in online convex optimization in a black-box manner. For smooth nonconvex objectives, our reduction maintains a predictable gradient tracker, while a black-box online learner selects a preconditioner that determines how this tracker is transformed into the update direction. The learner receives linear convex losses and is evaluated against a single fixed comparator over one undiscounted online game. For a $β$-smooth objective with range bounded by $M$ and an unbiased stochastic-gradient oracle with variance bounded by \(σ^2\), we establish $$\frac{1}{T}\sum_{t=1}^T \mathbb E\!\left[\|\nabla f(x_t)\|_2^2\right] \lesssim \frac{σ\sqrt{Mβ}}{\sqrt T} + \frac{\sqrt{Mβ}\, \mathscr R_T(\mathcal A,I_d)}{T} + \frac{Mβ}{T}.$$ Consequently, any black-box OCO algorithm with $\mathscr R_T(\mathcal A,I_d)=O(\sqrt T)$ recovers the classical $O(\frac{1}{\sqrt{T}})$ convergence rate. We further show that the same black-box framework extends beyond the smooth setting to Lipschitz nonconvex objectives without Lipschitz continuous gradients. Importantly, this extension continues to rely only on an ordinary static-regret guarantee and requires no stronger notion of online regret. When the OCO oracle admits square-root static regret, the resulting conversion achieves the optimal $O(T^{-2/7})$ convergence rate for the corresponding Goldstein stationary point. These results resolve the open problem posed by Chen and Hazan (2024). More broadly, our framework separates optimizer design into gradient prediction and online preconditioner selection, providing a principled perspective on how adaptive optimization methods such as AdaGrad and Shampoo may be understood through static regret and applied in nonconvex optimization.
• Abstract（参考訳）: ブラックボックス方式のオンライン凸最適化において,確率的非凸最適化が通常の静的後悔最小化に還元できるかどうかを検討する。 一方、ブラックボックスオンライン学習者は、このトラッカーを更新方向へ変換する方法を決定するプリコンディショナーを選択する。 学習者は、線形凸損失を受信し、1つの未公表オンラインゲームに対して1つの固定コンパレータに対して評価する。 M$で有界範囲を持つ$β$-smooth対象と、(σ^2\)で有界な非バイアス確率勾配オラクルに対して、$$$\frac{1}{T}\sum_{t=1}^T \mathbb E\! \left[\|\nabla f(x_t)\|_2^2\right] \lesssim \frac{σ\sqrt{Mβ}}{\sqrt T} + \frac{\sqrt{Mβ}\, \mathscr R_T(\mathcal A,I_d)}{T} + \frac{Mβ}{T} である。 その結果、$\mathscr R_T(\mathcal A,I_d)=O(\sqrt T)$の任意のブラックボックスOCOアルゴリズムは、古典的な$O(\frac{1}{\sqrt{T}})$収束率を回復する。 さらに、同じブラックボックスフレームワークが、リプシッツ連続勾配を持たないリプシッツ非凸目標への滑らかな設定を超えて拡張されることが示される。 重要なことは、この拡張は通常の静的な保証にのみ依存し続けており、オンライン後悔の強い概念を必要としないことである。 OCOオラクルが平方根の静的後悔を認めると、結果の変換は対応するゴールドスタイン定常点に対する最適$O(T^{-2/7})$収束率を達成する。 これらの結果は陳と破山(2024年)が提起した開問題を解く。 より広範に、我々のフレームワークは最適化設計を勾配予測とオンラインプレコンディショナー選択に分離し、AdaGradやShampooのような適応最適化手法が静的な後悔を通してどのように理解され、非凸最適化に適用されるかという原則的な視点を提供する。

関連論文リスト

• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
  論文  参考訳（メタデータ） (2026-05-21T08:57:38Z)
• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。 どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
  論文  参考訳（メタデータ） (2025-11-25T05:23:10Z)
• Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism [25.642618010943824]
  本稿では,2倍の楽観的ヒント関数に基づくオンラインの楽観的勾配法を提案する。 我々は1.75 + sigma2 varepsilon-3.5)$で統一されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2025-10-03T16:41:24Z)
• Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD [16.019880089338383]
  Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsff
  論文  参考訳（メタデータ） (2024-10-26T10:14:17Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  適応勾配法は、最も成功したニューラルネットワークトレーニングアルゴリズムの一つである。 これらの手法は凸SGD-ノルマリティよりも次元依存性が優れていることが知られている。 本稿では,構造物の滑らかさと勾配雑音の分散に関する新しい仮定を紹介する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization [33.346773349614715]
  本報告では,NonpsOmegaのための新しい確率勾配エストリマト(フラスト)を提案する。 小さなPAGEからバニラSGDへと設計されているため、実装が容易である。 トレーニングにおいてSGDよりもはるかに早く収束するだけでなく、高い精度を達成する。
  論文  参考訳（メタデータ） (2020-08-25T09:11:31Z)

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

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