論文の概要: Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

• arxiv url: http://arxiv.org/abs/2610.13787v1
• Date: Fri, 09 Oct 2026 16:04:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.66476
• Title: Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
• Title（参考訳）: 制約付き非滑らかな非凸確率最適化のための最適アルゴリズム
• Abstract要約: 凸制約セットを対象とし,目的が滑らかでも凸でもない最適化問題に対する新しいアルゴリズムを提案する。 我々の分析は、制約のない最適化から関連する手法であるオンライン複雑性最適化への還元に基づく。
• 参考スコア（独自算出の注目度）: 8.966143663102798
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a $(δ,\varepsilon)$-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a $\widetilde O(δ^{-1}\varepsilon^{-3})$ rate using stochastic gradients, which we show to be optimal, and a $\widetilde O(dδ^{-1}\varepsilon^{-3})$ rate using zeroth-order queries, which is also optimal in its dependence on the dimension $d$ and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.
• Abstract（参考訳）: 本稿では, 対象が滑らかでも凸でもない確率的最適化問題に対して, 凸制約セットを対象とする新しいアルゴリズムを提案する。 我々のアルゴリズムは、Liu et al (2024) による制約付き問題に対して最近定義されたような $(δ,\varepsilon)$-Goldstein 定常点を返す。 特に、最適な確率勾配を用いて$\widetilde O(δ^{-1}\varepsilon^{-3})$レートを達成できる射影型および射影型アルゴリズムを設計し、$\widetilde O(dδ^{-1}\varepsilon^{-3})$レートをゼロ次クエリを用いて設計する。 特に、我々の下界はフランク=ウルフギャップの点で与えられ、独立した関心を持つ滑らかな問題に対しても成り立つ。 これらの結果は、非凸確率最適化において、収束速度は制約の有無や非滑らかさによっても劣化しないことを示している。 我々の分析は、オンライン線形最適化への還元に基づいており、関連する手法を制約のない最適化から拡張している。

関連論文リスト

• Zeroth-Order Methods for Stochastic Nonconvex Nonsmooth Composite Optimization [51.63258496873442]
  合成最適化問題に関するこれまでの研究は、滑らか性の主要な部分、あるいはこれら2つの近似滑らか性点をそれぞれ除外した機械学習の例を必要とする。 本研究では,この問題に対する2つの新しいアルゴリズムを提案する。 これらのアルゴリズムは数値実験により有効であることを示す。
  論文  参考訳（メタデータ） (2025-10-06T02:35:42Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• 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)

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

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