論文の概要: Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization
- arxiv url: http://arxiv.org/abs/2212.09513v1
- Date: Mon, 19 Dec 2022 14:48:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 19:00:12.117268
- Title: Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization
- Title(参考訳): 非凸予測制約最適化のための確率的不変ラグランジアン法
- Authors: Zichong Li, Pin-Yu Chen, Sijia Liu, Songtao Lu, Yangyang Xu
- Abstract要約: 多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
- 参考スコア(独自算出の注目度): 88.0031283949404
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many real-world problems not only have complicated nonconvex functional
constraints but also use a large number of data points. This motivates the
design of efficient stochastic methods on finite-sum or expectation constrained
problems. In this paper, we design and analyze stochastic inexact augmented
Lagrangian methods (Stoc-iALM) to solve problems involving a nonconvex
composite (i.e. smooth+nonsmooth) objective and nonconvex smooth functional
constraints. We adopt the standard iALM framework and design a subroutine by
using the momentum-based variance-reduced proximal stochastic gradient method
(PStorm) and a postprocessing step. Under certain regularity conditions
(assumed also in existing works), to reach an $\varepsilon$-KKT point in
expectation, we establish an oracle complexity result of $O(\varepsilon^{-5})$,
which is better than the best-known $O(\varepsilon^{-6})$ result. Numerical
experiments on the fairness constrained problem and the Neyman-Pearson
classification problem with real data demonstrate that our proposed method
outperforms an existing method with the previously best-known complexity
result.
- Abstract(参考訳): 多くの実世界の問題は複雑な非凸関数制約を持つだけでなく、多数のデータポイントを使用する。
これは有限和あるいは期待制約問題に対する効率的な確率的手法の設計を動機付ける。
本稿では,非凸複合(smooth+nonsmooth)目的と非凸滑らかな関数制約に関する問題を解くために,確率的不拡張ラグランジアン法(stoc-ialm)を設計し,解析する。
モーメントベース分散型近位確率勾配法(PStorm)と後処理ステップを用いて,標準iALMフレームワークを採用し,サブルーチンを設計する。
ある種の正則性条件(既存の研究でも仮定される)の下では、期待されるときに$\varepsilon$-KKT点に達するために、$O(\varepsilon^{-5})$のオラクル複雑性結果を確立し、最もよく知られた$O(\varepsilon^{-6})$の結果より優れている。
実データを用いたフェアネス制約問題とネイマン・ピアソン分類問題に関する数値実験により,提案手法が従来最もよく知られた複雑性結果の既存手法よりも優れていることを示す。
関連論文リスト
- Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳(メタデータ) (2023-05-28T06:33:37Z) - Efficient First-order Methods for Convex Optimization with Strongly
Convex Function Constraints [3.667453772837954]
強い凸関数制約を受ける凸関数を最小化する方法を示す。
有限個の結果に独立な意味を持つような空間パターンを同定する。
論文 参考訳(メタデータ) (2022-12-21T16:04:53Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。
本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文 参考訳(メタデータ) (2021-06-12T10:59:02Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。
本稿では,最適化と平滑化次元とのトレードオフを実証する。
論文 参考訳(メタデータ) (2021-04-14T10:42:45Z) - Stochastic Compositional Gradient Descent under Compositional
constraints [13.170519806372075]
目的関数と制約関数が凸であり,関数の合成として表される制約最適化問題について検討する。
この問題は、公平な分類/回帰とキューシステムの設計に生じる。
提案手法は最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
論文 参考訳(メタデータ) (2020-12-17T05:38:37Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳(メタデータ) (2020-10-23T05:24:05Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳(メタデータ) (2020-06-27T03:05:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。