論文の概要: Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism

• arxiv url: http://arxiv.org/abs/2510.03167v1
• Date: Fri, 03 Oct 2025 16:41:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.49566
• Title: Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism
• Title（参考訳）: 二重最適化によるスムース最適化のためのオンライン・ノンコンベックス変換の改善
• Authors: Francisco Patitucci, Ruichen Jiang, Aryan Mokhtari,
• Abstract要約: 最近の非最適化のブレークスルーは、オンラインから非最適化フレームワークcitecutkosky2023である。 オンラインの楽観的勾配法は,新しい楽観的ヒント関数をベースとして提案する。
• 参考スコア（独自算出の注目度）: 25.642618010943824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent breakthrough in nonconvex optimization is the online-to-nonconvex conversion framework of \cite{cutkosky2023optimal}, which reformulates the task of finding an $\varepsilon$-first-order stationary point as an online learning problem. When both the gradient and the Hessian are Lipschitz continuous, instantiating this framework with two different online learners achieves a complexity of $\mathcal{O}(\varepsilon^{-1.75}\log(1/\varepsilon))$ in the deterministic case and a complexity of $\mathcal{O}(\varepsilon^{-3.5})$ in the stochastic case. However, this approach suffers from several limitations: (i) the deterministic method relies on a complex double-loop scheme that solves a fixed-point equation to construct hint vectors for an optimistic online learner, introducing an extra logarithmic factor; (ii) the stochastic method assumes a bounded second-order moment of the stochastic gradient, which is stronger than standard variance bounds; and (iii) different online learning algorithms are used in the two settings. In this paper, we address these issues by introducing an online optimistic gradient method based on a novel \textit{doubly optimistic hint function}. Specifically, we use the gradient at an extrapolated point as the hint, motivated by two optimistic assumptions: that the difference between the hint and the target gradient remains near constant, and that consecutive update directions change slowly due to smoothness. Our method eliminates the need for a double loop and removes the logarithmic factor. Furthermore, by simply replacing full gradients with stochastic gradients and under the standard assumption that their variance is bounded by $\sigma^2$, we obtain a unified algorithm with complexity $\mathcal{O}(\varepsilon^{-1.75} + \sigma^2 \varepsilon^{-3.5})$, smoothly interpolating between the best-known deterministic rate and the optimal stochastic rate.
• Abstract（参考訳）: 非凸最適化の最近のブレークスルーは、オンライン学習問題として$\varepsilon$-first-orderの定常点を見つけるタスクを改革した、‘cite{cutkosky2023optimal} のオンラインから非凸変換フレームワークである。 勾配とヘシアンの両方がリプシッツ連続であるとき、このフレームワークを2つの異なるオンライン学習者とインスタンス化すると、決定論的ケースでは$\mathcal{O}(\varepsilon^{-1.75}\log(1/\varepsilon)$、確率的ケースでは$\mathcal{O}(\varepsilon^{-3.5})$となる。 しかし、このアプローチにはいくつかの制限があります。 一 決定論的手法は、楽観的なオンライン学習者のためのヒントベクトルを構築するための固定点方程式を解く複雑な二重ループスキームに依存し、余分な対数係数を導入する。 (ii)確率法は、標準分散境界よりも強い確率勾配の有界二階モーメントを仮定する。 (iii)異なるオンライン学習アルゴリズムが2つの設定で使用される。 本稿では,新しい「textit{doubly optimistic hint function」に基づくオンラインの楽観的勾配法を導入することで,これらの問題に対処する。 具体的には、2つの楽観的な仮定により、ヒントと目標勾配の差がほぼ一定であり、連続的な更新方向は滑らかさによってゆっくりと変化するという仮定が導かれる。 本手法では,二重ループの必要性を排除し,対数係数を除去する。 さらに、全勾配を確率勾配に置き換えるだけで、それらの分散が$\sigma^2$で有界であるという標準的な仮定の下で、複雑性を持つ統一アルゴリズムを$\mathcal{O}(\varepsilon^{-1.75} + \sigma^2 \varepsilon^{-3.5})$で得られる。

関連論文リスト

• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。 我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。 既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
  論文  参考訳（メタデータ） (2025-04-10T09:59:43Z)
• A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
  本稿では、上層関数が非定常で、潜在的に非有界な滑らかさを持ち、下層関数が凸であるような二層最適化の問題を考察する。 既存のアルゴリズムはネストループに依存しており、これは重要なチューニング作業を必要とし、実用的ではない。
  論文  参考訳（メタデータ） (2024-12-28T04:40:27Z)
• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods [18.47705532817026]
  本研究では,スムーズな関数を持つ$epsilon$firstorder stationary point (FOSP) を求める問題について検討する。 本稿では,このオンライン学習問題を解決するために,新しい楽観的な準勾配近似法を提案する。
  論文  参考訳（メタデータ） (2024-12-03T05:20:05Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• 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)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [46.46038357597395]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• 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 Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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