Fugu-MT 論文翻訳(概要): Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step

論文の概要: Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step

arxiv url: http://arxiv.org/abs/2005.05158v1
Date: Mon, 11 May 2020 14:52:16 GMT
ステータス: 処理完了
システム内更新日: 2022-12-04 20:38:30.717134
Title: Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step
Title（参考訳）: 拡張ラグランジアンおよび近位ステップによる不正確かつ確率的一般化条件勾配
Authors: Antonio Silveti-Falls, Cesare Molinari, Jalal Fadili
Abstract要約: 我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
参考スコア（独自算出の注目度）: 2.0196229393131726
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper we propose and analyze inexact and stochastic versions of the CGALP algorithm developed in the authors' previous paper, which we denote ICGALP, that allows for errors in the computation of several important quantities. In particular this allows one to compute some gradients, proximal terms, and/or linear minimization oracles in an inexact fashion that facilitates the practical application of the algorithm to computationally intensive settings, e.g. in high (or possibly infinite) dimensional Hilbert spaces commonly found in machine learning problems. The algorithm is able to solve composite minimization problems involving the sum of three convex proper lower-semicontinuous functions subject to an affine constraint of the form $Ax=b$ for some bounded linear operator $A$. Only one of the functions in the objective is assumed to be differentiable, the other two are assumed to have an accessible prox operator and a linear minimization oracle. As main results, we show convergence of the Lagrangian to an optimum and asymptotic feasibility of the affine constraint as well as weak convergence of the dual variable to a solution of the dual problem, all in an almost sure sense. Almost sure convergence rates, both pointwise and ergodic, are given for the Lagrangian values and the feasibility gap. Numerical experiments verifying the predicted rates of convergence are shown as well.
Abstract（参考訳）: 本稿では,いくつかの重要な量の計算における誤りを許容するicgalpを記述し,著者らが先行する論文で開発したcgalpアルゴリズムの不正確かつ確率的なバージョンを提案する。特にこれは、いくつかの勾配、近位項、および/または線形最小化神託を、機械学習問題でよく見られる高(あるいは無限)次元ヒルベルト空間のような計算集約的な設定へのアルゴリズムの実用的な適用を容易にするような、見掛けのつかない方法で計算することができる。このアルゴリズムは、ある有界線型作用素に対して$Ax=b$という形のアフィン制約を受ける3つの凸固有半連続函数の和を含む合成最小化問題を解くことができる。目的の関数のうち1つだけが微分可能と仮定され、他の2つはアクセス可能なprox演算子と線形最小化オラクルを持つと仮定される。主な結果として、ラグランジアンをアフィン制約の最適かつ漸近的実現可能性に収束させ、双対変数を双対問題の解に弱収束させることをほぼ確実に示す。ほぼ確実に、ポイントワイズとエルゴードの両方の収束率は、ラグランジアン値と実現可能性ギャップに対して与えられる。また,予測収束率を検証した数値実験も行った。

関連論文リスト

Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文参考訳（メタデータ） (2023-10-18T10:29:58Z)
Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文参考訳（メタデータ） (2023-05-28T06:33:37Z)
High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文参考訳（メタデータ） (2023-02-02T10:37:23Z)
On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples [1.0650780147044159]
スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
論文参考訳（メタデータ） (2022-03-25T20:56:07Z)
Sharper Bounds for Proximal Gradient Algorithms with Errors [6.901159341430919]
凸複合問題に対する近位勾配アルゴリズムの収束度を、勾配と近位計算の不正確さの存在下で解析する。我々は、シミュレーション(MPC)と合成(LASSO)最適化問題を検証するために、より厳密な決定的および確率的境界を導出する。
論文参考訳（メタデータ） (2022-03-04T09:27:08Z)
A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
深層強化学習のための線形プログラミング(LP)の定式化について検討する。拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。深層パラメタライズされたラグランジアン法を提案する。
論文参考訳（メタデータ） (2021-05-20T13:08:06Z)
Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文参考訳（メタデータ） (2020-12-09T20:19:32Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)
Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文参考訳（メタデータ） (2020-06-24T07:40:31Z)
Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文参考訳（メタデータ） (2020-02-26T11:18:43Z)

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

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