論文の概要: A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates
- arxiv url: http://arxiv.org/abs/2003.01322v3
- Date: Thu, 28 Oct 2021 14:32:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 23:09:40.392332
- Title: A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates
- Title（参考訳）: 最適反復率をもつ凸最適化のためのランダム化原始双対アルゴリズム
- Authors: Quoc Tran-Dinh and Deyi Liu
- Abstract要約: 我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
- 参考スコア（独自算出の注目度）: 16.54912614895861
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a novel unified randomized block-coordinate primal-dual algorithm
to solve a class of nonsmooth constrained convex optimization problems, which
covers different existing variants and model settings from the literature. We
prove that our algorithm achieves optimal $\mathcal{O}(n/k)$ and
$\mathcal{O}(n^2/k^2)$ convergence rates (up to a constant factor) in two
cases: general convexity and strong convexity, respectively, where $k$ is the
iteration counter and n is the number of block-coordinates. Our convergence
rates are obtained through three criteria: primal objective residual and primal
feasibility violation, dual objective residual, and primal-dual expected gap.
Moreover, our rates for the primal problem are on the last iterate sequence.
Our dual convergence guarantee requires additionally a Lipschitz continuity
assumption. We specify our algorithm to handle two important special cases,
where our rates are still applied. Finally, we verify our algorithm on two
well-studied numerical examples and compare it with two existing methods. Our
results show that the proposed method has encouraging performance on different
experiments.
- Abstract（参考訳）: 本研究では,非滑らかな制約付き凸最適化問題のクラスを解くために,新しい統一型ランダム化ブロック座標主元-双対アルゴリズムを開発した。
一般凸性および強い凸性という2つの場合において、このアルゴリズムが最適$\mathcal{O}(n/k)$と$\mathcal{O}(n^2/k^2)$収束率(定数係数まで)を達成することを証明している。
我々の収束率は,主観的残差と主観的実現可能性違反,二重目的的残差と主観的期待ギャップの3つの基準によって得られる。
さらに、原始問題に対する我々の割合は、最後の反復シーケンスにある。
我々の双対収束保証は、さらにリプシッツ連続性仮定を必要とする。
当社のアルゴリズムは、2つの重要な特別なケースに対処するために指定します。
最後に、2つのよく研究された数値例でアルゴリズムを検証し、2つの既存手法と比較する。
その結果,提案手法は異なる実験において有意な性能を有することがわかった。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文 参考訳（メタデータ） (2021-09-20T21:48:19Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳（メタデータ） (2021-06-22T07:24:17Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。