論文の概要: Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers
- arxiv url: http://arxiv.org/abs/2410.01979v1
- Date: Wed, 2 Oct 2024 19:36:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 09:44:41.934890
- Title: Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers
- Title（参考訳）: 自己条件付き原始-双対ハイブリッド勾配法と乗算器の交互方向法
- Authors: Guanghui Lan, Tianjiao Li,
- Abstract要約: 線形サーチ手順は、双線形サドル点問題に対する原始双対法でよく用いられる。
双線形サドル点問題を解くのに最適な複雑性を実現するために, 自動条件付きプライマリ・デュアル・ハイブリッド勾配法(AC-PDHG)を導入する。
また、目的と制約の両方が2つの部分に分解される線形制約問題の重要なクラスについても検討する。
- 参考スコア（独自算出の注目度）: 9.280355951055865
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Line search procedures are often employed in primal-dual methods for bilinear saddle point problems, especially when the norm of the linear operator is large or difficult to compute. In this paper, we demonstrate that line search is unnecessary by introducing a novel primal-dual method, the auto-conditioned primal-dual hybrid gradient (AC-PDHG) method, which achieves optimal complexity for solving bilinear saddle point problems. AC-PDHG is fully adaptive to the linear operator, using only past iterates to estimate its norm. We further tailor AC-PDHG to solve linearly constrained problems, providing convergence guarantees for both the optimality gap and constraint violation. Moreover, we explore an important class of linearly constrained problems where both the objective and constraints decompose into two parts. By incorporating the design principles of AC-PDHG into the preconditioned alternating direction method of multipliers (ADMM), we propose the auto-conditioned alternating direction method of multipliers (AC-ADMM), which guarantees convergence based solely on one part of the constraint matrix and fully adapts to it, eliminating the need for line search. Finally, we extend both AC-PDHG and AC-ADMM to solve bilinear problems with an additional smooth term. By integrating these methods with a novel acceleration scheme, we attain optimal iteration complexities under the single-oracle setting.
- Abstract（参考訳）: 線形サーチ手順は、特に線形作用素のノルムが大きい場合や計算が難しい場合、双線型サドル点問題の原始双対法でよく用いられる。
本稿では, 線形サドル点問題の解法として最適に複雑化を図り, 自動条件付きプリマル・デュアル・ハイブリッド勾配法(AC-PDHG)を導入することで, 線探索が不要であることを示す。
AC-PDHGは線形作用素に完全に適応し、過去の反復だけを用いてノルムを推定する。
我々はさらに、線形制約された問題を解くためにAC-PDHGを調整し、最適性ギャップと制約違反の両方に対する収束保証を提供する。
さらに、目的と制約の両方が2つの部分に分解される線形制約問題の重要なクラスについて検討する。
本稿では,AC-PDHGの設計原則を乗算器の事前条件付き交互方向法(ADMM)に取り入れることにより,制約行列の一部分のみに基づいて収束を保証し,行探索の不要さを解消する乗算器の自動条件交互方向法(AC-ADMM)を提案する。
最後に,AC-PDHG と AC-ADMM の双方を拡張して,さらにスムーズな項で双線形問題を解く。
これらの手法を新しい加速度スキームと統合することにより、単一軌道条件下での最適反復複雑性を実現する。
関連論文リスト
- Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria
for Robust Phase Retrieval [6.407536646154451]
本稿では,非平滑かつ非最適化問題であるロバスト検索問題を考察する。
本稿では,2つのコントリビューションでサブプロブレムを解くことを目的とした,新しい不正確な近位線形アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T02:29:33Z) - Linear Convergence of Natural Policy Gradient Methods with Log-Linear
Policies [115.86431674214282]
我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。
両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
論文 参考訳（メタデータ） (2022-10-04T06:17:52Z) - Accelerated nonlinear primal-dual hybrid gradient algorithms with
applications to machine learning [0.0]
原始双対ハイブリッド勾配(PDHG)は、サドル点構造を持つ凸最適化問題をより小さなサブプロブレムに分割する一階法である。
PDHGは、手前の問題に対して微調整されたステップサイズパラメータを必要とする。
我々は,機械学習に関連する幅広い最適化問題に対して,PDHGアルゴリズムの高速化された非線形変種を導入する。
論文 参考訳（メタデータ） (2021-09-24T22:37:10Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Adaptive Gradient Methods Converge Faster with Over-Parameterization
(but you should do a line-search) [32.24244211281863]
データを補間するのに十分なパラメータ化モデルを用いて、スムーズで凸的な損失を簡易に設定する。
一定のステップサイズと運動量を持つ AMSGrad がより高速な$O(1/T)$レートで最小値に収束することを証明する。
これらの手法により,タスク間の適応勾配法の収束と一般化が向上することを示す。
論文 参考訳（メタデータ） (2020-06-11T21:23:30Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Solution Path Algorithm for Twin Multi-class Support Vector Machine [6.97711662470035]
本論文は, ツインマルチクラスサポートベクトルマシンの高速正規化パラメータチューニングアルゴリズムについて述べる。
新たなサンプルデータセット分割法を採用し,ラグランジアン乗算器は分数線形であることが証明された。
提案手法は,グリッド探索手法の計算コストを指数レベルから定数レベルに削減し,優れた分類性能を実現する。
論文 参考訳（メタデータ） (2020-05-30T14:05:46Z) - A Gradient-Aware Search Algorithm for Constrained Markov Decision
Processes [9.728259735794987]
まず,有限CMDPの双対線型計画における最適化目標が,ラグランジュのペナルティ乗算器に対する一方向線型凸関数であることを証明した。
有限CMDPの最適状態値関数とラグランジュペナルティ乗算器を求めるために,PWLC構造を利用した2レベルグラディエント・アウェア・サーチ(GAS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-07T19:38:09Z) - Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める
近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。
両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
論文 参考訳（メタデータ） (2020-03-30T08:40:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。