論文の概要: Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints

• arxiv url: http://arxiv.org/abs/2504.07607v1
• Date: Thu, 10 Apr 2025 09:59:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-11 12:24:24.270785
• Title: Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints
• Title（参考訳）: 線形不等式制約付き非凸最適化のための確率滑らかな原始双対アルゴリズム
• Authors: Ruichuan Huang, Jiawei Zhang, Ahmet Alacaoglu,
• Abstract要約: 線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。 我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。 既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
• 参考スコア（独自算出の注目度）: 12.624604051853657
• License:
• Abstract: We propose smoothed primal-dual algorithms for solving stochastic and smooth nonconvex optimization problems with linear inequality constraints. Our algorithms are single-loop and only require a single stochastic gradient based on one sample at each iteration. A distinguishing feature of our algorithm is that it is based on an inexact gradient descent framework for the Moreau envelope, where the gradient of the Moreau envelope is estimated using one step of a stochastic primal-dual augmented Lagrangian method. To handle inequality constraints and stochasticity, we combine the recently established global error bounds in constrained optimization with a Moreau envelope-based analysis of stochastic proximal algorithms. For obtaining $\varepsilon$-stationary points, we establish the optimal $O(\varepsilon^{-4})$ sample complexity guarantee for our algorithms and provide extensions to stochastic linear constraints. We also show how to improve this complexity to $O(\varepsilon^{-3})$ by using variance reduction and the expected smoothness assumption. Unlike existing methods, the iterations of our algorithms are free of subproblems, large batch sizes or increasing penalty parameters and use dual variable updates to ensure feasibility.
• Abstract（参考訳）: 線形不等式制約を伴う確率的および滑らかな非凸最適化問題の解法として,スムーズな原始双対アルゴリズムを提案する。 我々のアルゴリズムはシングルループであり、各イテレーションで1つのサンプルに基づいて1つの確率勾配しか必要としない。 本アルゴリズムの特徴は,モローエンベロープの勾配を確率的原始二重拡張ラグランジアン法の一段階を用いて推定する,モローエンベロープの不正確な勾配降下フレームワークに基づくことである。 不等式制約と確率性を扱うために、制約付き最適化における最近確立された大域的誤差境界と、確率的近似アルゴリズムのモローエンベロープに基づく解析を組み合わせる。 $\varepsilon$-定常点を得るには、我々のアルゴリズムに対して最適な$O(\varepsilon^{-4})$サンプル複雑性を保証し、確率線形制約の拡張を提供する。 また、この複雑さを$O(\varepsilon^{-3})$にどのように改善するかを、分散還元と期待される滑らか性仮定を用いて示す。 既存の方法とは異なり、アルゴリズムのイテレーションにはサブプロブレムや大きなバッチサイズ、ペナルティパラメータの増大がなく、実現可能性を保証するためにデュアル変数更新を使用する。

関連論文リスト

• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• 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)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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