論文の概要: Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

• arxiv url: http://arxiv.org/abs/2610.12328v1
• Date: Thu, 08 Oct 2026 17:08:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:54.201396
• Title: Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
• Title（参考訳）: 最適Oracle複雑度を用いた複合オンライン・ノンコンベックス変換
• Abstract要約: 半径非滑らかな非線形合成最適化のオンライントレーニングについて検討する。 問題は、制約付き最適化と正規化されたニューラルネットワークを含む。 例えば、$-3 gradient$ query や $O(d-1-3)$ function-value query がある。
• 参考スコア（独自算出の注目度）: 15.092125124258592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with $O(δ^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(dδ^{-1}\varepsilon^{-3})$ function-value queries, where $δ$ is the Goldstein radius, $\varepsilon$ is the stationarity tolerance, and $d$ is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.
• Abstract（参考訳）: 我々は、制約付き最適化やニューラルネットワークの正規化訓練など、いくつかの重要な問題を含む確率的非滑らかな非凸合成最適化を考える。 目的は非滑らかな非凸リプシッツ関数と凸正則化器の和であり、その関数は確率勾配あるいは関数値を通してアクセスされる。 ゴールは、複合目的のために設計されたゴールドスタイン型定常条件を満たす点を見つけることである。 我々の知る限り、この設定に拘束されるオラクルの複雑さは1次アクセスでは知られておらず、ゼロ次アクセスでは既存の複雑さは最適以下である。 この問題に対処するために,オンライン学習者による更新方向の選択を行うオンライン-非凸変換の枠組みを用い,非合成問題に対して最適なレートを達成することが知られている。 我々は,学習者に対して線形化ではなく正規化子自体を含む新たな損失を導入し,オンラインミラー降下の変種が後悔の少ない複合シナリオに拡張する。 結果として得られたアルゴリズムは、$O(δ^{-1}\varepsilon^{-3})$確率勾配クエリまたは$O(dδ^{-1}\varepsilon^{-3})$関数値クエリでそのような点を見つけることを示し、$δ$はゴールドスタイン半径、$\varepsilon$は定常耐性、$d$は次元である。 これらの速度は非合成非滑らかな非凸最適化の最適値と一致し、追加の凸正則化器がオラクルの複雑さを悪化させることはないことを示した。 また、スムーズなケースに対するレートを与え、数値実験を行う。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。 代理オラクル関数に対するゼロ階量子推定器を構築する。
  論文  参考訳（メタデータ） (2024-10-21T16:52:26Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [46.46038357597395]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis [23.80683445944524]
  PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。 PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
  論文  参考訳（メタデータ） (2022-09-22T07:12:48Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)

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

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