論文の概要: Entropy-Smooth Convex Optimization Cannot Be Accelerated
- arxiv url: http://arxiv.org/abs/2607.27476v1
- Date: Wed, 29 Jul 2026 21:34:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-31 21:37:00.324925
- Title: Entropy-Smooth Convex Optimization Cannot Be Accelerated
- Title（参考訳）: エントロピー-滑らかな凸最適化は加速できない
- Authors: Jacob M. Aguirre, Dmitrii M. Ostrovskii,
- Abstract要約: 負のエントロピーに対する凸函数のクラスにおける最小化の収束率に対して、$(L/T)$低い境界を証明します。
このことは、ミラー降下がこのクラスの対数係数に最適であることを示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We prove an $Ω(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = Ω(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this class. This may be surprising due to the fact that accelerated methods are readily available under the assumption of smoothness in $\ell_1$-norm. While Dragomir et al. (Mathematical Programming, 2022) have already showed that acceleration might be impossible under relative smoothness, their prox-function is pathological and constructed together with the hard instance. In contrast, we show non-acceleration for a specific prox-function with particularly favorable structure. We also extend the result to the quantum setting, proving the same lower bound in the class of functions $L$-smooth relative to negative von Neumann entropy on the spectrahedron of $d \times d$ Hermitian positive-semidefinite matrices with unit trace.
- Abstract（参考訳）: 標準$d$-シプレックス上の負のエントロピーに対して凸函数のクラスにおける最小化の収束率に対する$Ω(L/T)$下界を証明し、$d = Ω(T^2)$のときの任意の一階法に対して有効である。
特に、これは鏡面降下がこのクラスの対数係数まで最適であることを示している。
これは、加速されたメソッドが$\ell_1$-normの滑らかさの仮定で容易に利用できるという事実から驚くかもしれない。
Dragomir et al (Mathematical Programming, 2022) は既に、相対的な滑らかさの下で加速は不可能であることを示したが、それらのプロキシ関数は病理学的であり、ハードケースと一緒に構成されている。
対照的に、特に好意的な構造を持つ特定のプロキシ関数の非加速を示す。
また、この結果は量子設定にまで拡張され、負のフォン・ノイマンエントロピーに対して函数のクラス$L$-smoothで同じ下界を証明し、単位トレースを持つ$d \times d$エルミート正半有限行列のスペクトル上で証明する。
関連論文リスト
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。
このような悪条件下でSGDが確実に成功できるかどうかを精査する。
論文 参考訳（メタデータ） (2025-08-06T20:09:41Z) - A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization [3.8919212824749296]
提案したSFOMは,目的関数の高次滑らか度を$f$とすることで,最適化を高速化できることを示す。
我々の知る限りでは、これは対象関数の任意の次スムーズネスを加速度に利用した最初のSFOMである。
論文 参考訳（メタデータ） (2024-12-19T03:22:47Z) - Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。