論文の概要: Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2404.09438v1
- Date: Mon, 15 Apr 2024 03:50:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-16 13:58:36.022373
- Title: Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization
- Title（参考訳）: 非滑らかな非凸最適化のためのラグランジアン法の開発
- Authors: Nachuan Xiao, Kuangyu Ding, Xiaoyin Hu, Kim-Chuan Toh,
- Abstract要約: 我々はラグランジュ的手法を開発するためのフレームワークを開発する。
予測制約で制約された問題を解くために,我々のフレームワークを拡張できることが示される。
- 参考スコア（独自算出の注目度）: 2.7998963147546148
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the minimization of a nonsmooth nonconvex objective function $f(x)$ over a closed convex subset $\mathcal{X}$ of $\mathbb{R}^n$, with additional nonsmooth nonconvex constraints $c(x) = 0$. We develop a unified framework for developing Lagrangian-based methods, which takes a single-step update to the primal variables by some subgradient methods in each iteration. These subgradient methods are ``embedded'' into our framework, in the sense that they are incorporated as black-box updates to the primal variables. We prove that our proposed framework inherits the global convergence guarantees from these embedded subgradient methods under mild conditions. In addition, we show that our framework can be extended to solve constrained optimization problems with expectation constraints. Based on the proposed framework, we show that a wide range of existing stochastic subgradient methods, including the proximal SGD, proximal momentum SGD, and proximal ADAM, can be embedded into Lagrangian-based methods. Preliminary numerical experiments on deep learning tasks illustrate that our proposed framework yields efficient variants of Lagrangian-based methods with convergence guarantees for nonconvex nonsmooth constrained optimization problems.
- Abstract（参考訳）: 本稿では、非滑らかな非凸対象函数 $f(x)$ の閉凸部分集合 $\mathcal{X}$ の $\mathbb{R}^n$ に対する最小化を考える。
ラグランジアンベースの手法を開発するための統一的なフレームワークを開発し、各イテレーションにおいて、いくつかの下位のメソッドによってプリミティブ変数を1ステップずつ更新する。
これらの下位段階のメソッドは、プリミティブ変数のブラックボックス更新として組み込まれているという意味で、私たちのフレームワークに‘組込み’されている。
提案手法は, 温和な条件下での組込み過次法からグローバル収束保証を継承することを証明する。
さらに,予測制約による制約付き最適化問題を解くために,我々のフレームワークを拡張可能であることを示す。
提案手法に基づいて, 近位SGD, 近位運動量SGD, 近位ADAMを含む, 既存の確率的下位段階法をラグランジアン法に組み込むことができることを示す。
ディープラーニングタスクに関する予備的な数値実験により,提案手法は非凸非滑らかな制約付き最適化問題に対する収束保証を伴うラグランジュ的手法の効率的な変種を導出することを示した。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.9047096855236125]
不等式制約を伴う非滑らかな複合最適化は、統計学習とデータ科学において重要である。
textbfOBCDは、これらの課題に対処するための、実現可能な小さな計算フットプリント手法である。
我々はtextbfOBCD がブロック$k$定常点に収束することを証明する。
論文 参考訳（メタデータ） (2023-04-07T13:44:59Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal
Oracle [16.290192687098383]
本稿では,アフィン制約を伴う凸複合最適化問題について考察する。
正確なプロジェクション/近距離計算が難解な高次元アプリケーションにより,テキスト投影のないラグランジアン型拡張手法を提案する。
論文 参考訳（メタデータ） (2022-10-25T12:51:43Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - A Stochastic Composite Augmented Lagrangian Method For Reinforcement
Learning [9.204659134755795]
深層強化学習のための線形プログラミング(LP)の定式化について検討する。
拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。
深層パラメタライズされたラグランジアン法を提案する。
論文 参考訳（メタデータ） (2021-05-20T13:08:06Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳（メタデータ） (2021-02-22T18:56:26Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。