論文の概要: Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems
with Convex Constraints
- arxiv url: http://arxiv.org/abs/2311.09065v1
- Date: Wed, 15 Nov 2023 16:05:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-16 15:18:24.785687
- Title: Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems
with Convex Constraints
- Title（参考訳）: 凸制約付き弱凸問題に対する減衰近距離ラグランジアン法
- Authors: Hari Dahal, Wei Liu, Yangyang Xu
- Abstract要約: 弱拘束的目的と凸・非拘束的制約の問題を解くために、減衰した近位グランジアン法(DPALM)を提案する。
DPALM は APG を用いて各サブプロブレムを線形に滑らかに解くことで,約$varepsilon$-KK 点を生成可能であることを示す。
- 参考スコア（独自算出の注目度）: 17.25924791071807
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a damped proximal augmented Lagrangian method (DPALM) for solving
problems with a weakly-convex objective and convex linear/nonlinear
constraints. Instead of taking a full stepsize, DPALM adopts a damped dual
stepsize to ensure the boundedness of dual iterates. We show that DPALM can
produce a (near) $\vareps$-KKT point within $O(\vareps^{-2})$ outer iterations
if each DPALM subproblem is solved to a proper accuracy. In addition, we
establish overall iteration complexity of DPALM when the objective is either a
regularized smooth function or in a regularized compositional form. For the
former case, DPALM achieves the complexity of
$\widetilde{\mathcal{O}}\left(\varepsilon^{-2.5} \right)$ to produce an
$\varepsilon$-KKT point by applying an accelerated proximal gradient (APG)
method to each DPALM subproblem. For the latter case, the complexity of DPALM
is $\widetilde{\mathcal{O}}\left(\varepsilon^{-3} \right)$ to produce a near
$\varepsilon$-KKT point by using an APG to solve a Moreau-envelope smoothed
version of each subproblem. Our outer iteration complexity and the overall
complexity either generalize existing best ones from unconstrained or
linear-constrained problems to convex-constrained ones, or improve over the
best-known results on solving the same-structured problems. Furthermore,
numerical experiments on linearly/quadratically constrained non-convex
quadratic programs and linear-constrained robust nonlinear least squares are
conducted to demonstrate the empirical efficiency of the proposed DPALM over
several state-of-the art methods.
- Abstract（参考訳）: 我々は、弱凸目的と凸線型・非線形制約の問題を解くために、減衰した近似ラグランジアン法(DPALM)を提案する。
完全なステップサイズを取る代わりに、DPALMは二重反復の有界性を保証するためにダンプされた双対ステップサイズを採用する。
DPALMは、各DPALMサブプロブレムが適切な精度で解ける場合、$O(\vareps^{-2})$外反復で(ほぼ)$\vareps$-KKTの点を生成できることを示す。
さらに, 目的が正規化された滑らかな関数か正規化された構成形式である場合, DPALMの全体的な反復複雑性を確立する。
前者の場合、DPALM は $\widetilde{\mathcal{O}}\left(\varepsilon^{-2.5} \right)$ の複雑さを達成し、各 DPALM サブプロブレムに加速された近位勾配 (APG) 法を適用して $\varepsilon$-KKT 点を生成する。
後者の場合、DPALMの複雑さは$\widetilde{\mathcal{O}}\left(\varepsilon^{-3} \right)$で、各サブプロブレムのモロー・エンベロープ滑らかなバージョンを解くためにAPGを用いて、ほぼ$\varepsilon$-KKT点を生成する。
外部のイテレーションの複雑さと全体的な複雑さは、制約のない問題や線形制約のある問題から凸制約のある問題へと、既存のベストを一般化するか、あるいは同じ構造の問題を解決する上で最もよく知られた結果よりも改善するかのどちらかです。
さらに, 線形/四進法制約の非凸二乗計画と線形制約の頑健な非線形最小二乗の数値実験を行い, 提案手法によるDPALMの実証的効率を示す。
関連論文リスト
- Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳（メタデータ） (2024-06-27T18:38:42Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Variance-reduced accelerated methods for decentralized stochastic
double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。
我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。
我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
論文 参考訳（メタデータ） (2023-07-14T01:32:16Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Functional Constrained Optimization for Risk Aversion and Sparsity
Control [7.561780884831967]
リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。
本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。
提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
論文 参考訳（メタデータ） (2022-10-11T02:51:51Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Manifold Proximal Point Algorithms for Dual Principal Component Pursuit
and Orthogonal Dictionary Learning [32.87704663543739]
様々な機械学習アプリケーションで発生する球面上の線形写像を最大化する問題を考える。
球面をスティーフェル行列に置き換える問題に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-05T17:40:03Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。