論文の概要: A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

• arxiv url: http://arxiv.org/abs/2501.19214v1
• Date: Fri, 31 Jan 2025 15:18:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-03 13:57:48.008886
• Title: A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization
• Title（参考訳）: 期待制約付き非凸非平滑最適化のための単一ループSPIDER型確率次数法
• Authors: Wei Liu, Yangyang Xu,
• Abstract要約: 複雑な制約に対する新しい種類の下次アルゴリズムを提案する。 提案手法は, 2-of-the-artアルゴリズムよりもはるかに高速であることを示す。
• 参考スコア（独自算出の注目度）: 17.25924791071807
• License:
• Abstract: Many real-world problems, such as those with fairness constraints, involve complex expectation constraints and large datasets, necessitating the design of efficient stochastic methods to solve them. Most existing research focuses on cases with no {constraint} or easy-to-project constraints or deterministic constraints. In this paper, we consider nonconvex nonsmooth stochastic optimization problems with expectation constraints, for which we build a novel exact penalty model. We first show the relationship between the penalty model and the original problem. Then on solving the penalty problem, we present a single-loop SPIDER-type stochastic subgradient method, which utilizes the subgradients of both the objective and constraint functions, as well as the constraint function value at each iteration. Under certain regularity conditions (weaker than Slater-type constraint qualification or strong feasibility assumed in existing works), we establish an iteration complexity result of $O(\epsilon^{-4})$ to reach a near-$\epsilon$ stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an $(\epsilon,\epsilon)$-KKT point of the original problem is obtained. For a few scenarios, our complexity of either the {objective} sample subgradient or the constraint sample function values can be lower than the state-of-the-art results by a factor of $\epsilon^{-2}$. Moreover, on solving two fairness-constrained problems, our method is significantly (up to 466 times) faster than the state-of-the-art algorithms, including switching subgradient method and inexact proximal point methods.
• Abstract（参考訳）: 公正性の制約があるような現実の多くの問題は、複雑な予測制約と大きなデータセットを伴い、それらを解決するために効率的な確率的手法の設計を必要とする。 既存の研究のほとんどは、制約のないケースやプロジェクト間の制約、決定論的制約などに焦点を当てている。 本稿では,非凸な非滑らかな確率的最適化問題と予測制約について考察し,新しい厳密なペナルティモデルを構築する。 まず、ペナルティモデルと元の問題との関係を示す。 ペナルティ問題の解決にあたり,目的関数と制約関数の下位値と反復時の制約関数値を利用する単一ループSPIDER型確率勾配法を提案する。 一定の規則性条件(スレーター型制約条件や既存の作業で想定される強い実現可能性よりも弱い)の下では、予想されるペナル化問題の定点付近に到達するために$O(\epsilon^{-4})$の反復複雑性結果を確立し、そのようなタスクの下位境界と一致する。 正確なペナル化に基づいて、元の問題の$(\epsilon,\epsilon)$-KKT点を求める。 いくつかのシナリオでは、 {objective} のサンプル次数あるいは制約されたサンプル関数値の複雑さは、$\epsilon^{-2}$ の因子によって、最先端の結果よりも低くすることができる。 さらに, 2つのフェアネス制約問題の解法において, 提案手法は, 置換次数法や不正確な近点法を含む最先端アルゴリズムよりも有意に高速(最大466倍)である。

関連論文リスト

• Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees [1.2562458634975162]
  既存の方法は典型的には$epsilon$-stochasticの固定点を見つけることを目的としている。 多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$epsilon$-stochasticの定常点が望ましくない可能性がある。
  論文  参考訳（メタデータ） (2024-09-16T00:26:42Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• 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)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)

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

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