論文の概要: A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization
- arxiv url: http://arxiv.org/abs/2207.05650v1
- Date: Tue, 12 Jul 2022 16:30:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-13 13:58:02.896445
- Title: A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization
- Title（参考訳）: 非凸関数制約最適化のための単一ループ勾配勾配及び摂動昇降アルゴリズム
- Authors: Songtao Lu
- Abstract要約: 制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 27.07082875330508
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Nonconvex constrained optimization problems can be used to model a number of
machine learning problems, such as multi-class Neyman-Pearson classification
and constrained Markov decision processes. However, such kinds of problems are
challenging because both the objective and constraints are possibly nonconvex,
so it is difficult to balance the reduction of the loss value and reduction of
constraint violation. Although there are a few methods that solve this class of
problems, all of them are double-loop or triple-loop algorithms, and they
require oracles to solve some subproblems up to certain accuracy by tuning
multiple hyperparameters at each iteration. In this paper, we propose a novel
gradient descent and perturbed ascent (GDPA) algorithm to solve a class of
smooth nonconvex inequality constrained problems. The GDPA is a primal-dual
algorithm, which only exploits the first-order information of both the
objective and constraint functions to update the primal and dual variables in
an alternating way. The key feature of the proposed algorithm is that it is a
single-loop algorithm, where only two step-sizes need to be tuned. We show that
under a mild regularity condition GDPA is able to find Karush-Kuhn-Tucker (KKT)
points of nonconvex functional constrained problems with convergence rate
guarantees. To the best of our knowledge, it is the first single-loop algorithm
that can solve the general nonconvex smooth problems with nonconvex inequality
constraints. Numerical results also showcase the superiority of GDPA compared
with the best-known algorithms (in terms of both stationarity measure and
feasibility of the obtained solutions).
- Abstract（参考訳）: 非凸制約最適化問題は、マルチクラスネイマン・ピアソン分類やマルコフ決定過程などの機械学習問題をモデル化するために用いられる。
しかし, 目的値と制約値がともに非凸であるため, 損失値の低減と制約違反の低減のバランスをとることは困難である。
このタイプの問題を解決する方法はいくつかあるが、いずれもダブルループまたはトリプルループのアルゴリズムであり、各イテレーションで複数のハイパーパラメータをチューニングすることで、ある程度の精度でいくつかのサブ問題をoracleが解決する必要がある。
本稿では,滑らかな非凸不等式制約問題のクラスを解くために,新しい勾配降下・摂動上昇法(gdpa)を提案する。
GDPAは原始双対アルゴリズムであり、目的関数と制約関数の両方の第一次情報のみを利用して、原始変数と双対変数を交互に更新する。
提案アルゴリズムの重要な特徴は、シングルループアルゴリズムであり、2つのステップサイズしか調整する必要のないことである。
軽度規則性条件下では、GDPAは収束率保証を伴う非凸関数制約問題のKKT(Karush-Kuhn-Tucker)点を見つけることができる。
我々の知る限りでは、非凸不等式制約による一般的な非凸スムーズな問題を解くことができる最初のシングルループアルゴリズムである。
計算結果はまた、最もよく知られたアルゴリズム(定常測度と解の実現可能性の両方の観点から)と比較してgdpaの優位を示す。
関連論文リスト
- Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
Invexプログラムは、固定点ごとに世界最小値が得られる特別な非制約問題である。
そこで我々は,超凸問題における一般収束率を解くために,新しい一階法アルゴリズムを提案する。
提案アルゴリズムは,制約付き凸プログラムを解く最初のアルゴリズムである。
論文 参考訳（メタデータ） (2023-07-10T10:11:01Z) - Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
本稿では,候補アルゴリズムの集合に有効な手法を提案する。
内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。
提案手法は,他のアルゴリズムのスコアを大幅に改善する。
論文 参考訳（メタデータ） (2023-05-26T21:49:37Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained
Optimization [13.170519806372075]
2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。
最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。
提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
論文 参考訳（メタデータ） (2021-07-14T08:01:30Z) - 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 Single-Loop Smoothed Gradient Descent-Ascent Algorithm for
Nonconvex-Concave Min-Max Problems [33.83671897619922]
非con-max問題は、このロバストな問題を解決するために、ポイントワイズな非函数の集合を最小化するなど、多くのアプリケーションで発生する。
A.A.アルゴリズムは、有限個の非函数の集合に対して$(/A-O-)の$(/A-O-)を達成できる。
論文 参考訳（メタデータ） (2020-10-29T17:13:46Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳（メタデータ） (2020-06-27T03:05:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。