論文の概要: Accelerated nonlinear primal-dual hybrid gradient algorithms with
applications to machine learning
- arxiv url: http://arxiv.org/abs/2109.12222v1
- Date: Fri, 24 Sep 2021 22:37:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-01 07:31:52.861613
- Title: Accelerated nonlinear primal-dual hybrid gradient algorithms with
applications to machine learning
- Title（参考訳）: 非線形初等二次ハイブリッド勾配アルゴリズムの高速化と機械学習への応用
- Authors: J\'er\^ome Darbon and Gabriel Provencher Langlois
- Abstract要約: 原始双対ハイブリッド勾配(PDHG)は、サドル点構造を持つ凸最適化問題をより小さなサブプロブレムに分割する一階法である。
PDHGは、手前の問題に対して微調整されたステップサイズパラメータを必要とする。
我々は,機械学習に関連する幅広い最適化問題に対して,PDHGアルゴリズムの高速化された非線形変種を導入する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The primal-dual hybrid gradient (PDHG) algorithm is a first-order method that
splits convex optimization problems with saddle-point structure into smaller
subproblems. Those subproblems, unlike those obtained from most other splitting
methods, can generally be solved efficiently because they involve simple
operations such as matrix-vector multiplications or proximal mappings that are
easy to evaluate. In order to work fast, however, the PDHG algorithm requires
stepsize parameters fine-tuned for the problem at hand. Unfortunately, the
stepsize parameters must often be estimated from quantities that are
prohibitively expensive to compute for large-scale optimization problems, such
as those in machine learning. In this paper, we introduce accelerated nonlinear
variants of the PDHG algorithm that can achieve, for a broad class of
optimization problems relevant to machine learning, an optimal rate of
convergence with stepsize parameters that are simple to compute. We prove
rigorous convergence results, including for problems posed on
infinite-dimensional reflexive Banach spaces. We also provide practical
implementations of accelerated nonlinear PDHG algorithms for solving several
regression tasks in machine learning, including support vector machines without
offset, kernel ridge regression, elastic net regularized linear regression, and
the least absolute shrinkage selection operator.
- Abstract（参考訳）: 原始双対ハイブリッド勾配(PDHG)アルゴリズムは、サドルポイント構造を持つ凸最適化問題をより小さなサブプロブレムに分割する一階法である。
これらのサブプロブレムは、他のほとんどの分割法とは異なり、行列ベクトル乗法や近位写像のような単純な操作が容易に評価できるため、一般に効率的に解ける。
しかし、高速に動作させるためには、PDHGアルゴリズムは手前の問題に対して微調整された段階的なパラメータを必要とする。
残念なことに、ステップサイズパラメータは、機械学習のような大規模最適化問題に対する計算に不当にコストがかかる量から推定されなければならない。
本稿では,PDHGアルゴリズムの高速化された非線形変量を導入し,機械学習に関連する幅広い最適化問題に対して,計算が容易な段差パラメータによる収束率を最適化する手法を提案する。
無限次元反射的バナッハ空間上の問題を含む厳密な収束結果を証明する。
また,オフセットのないサポートベクターマシン,カーネルリッジ回帰,弾性ネット正規化線形回帰,最小絶対収縮選択演算子など,機械学習における複数の回帰タスクを解決するための高速化非線形pdhgアルゴリズムの実装も提供する。
関連論文リスト
- A Natural Primal-Dual Hybrid Gradient Method for Adversarial Neural Network Training on Solving Partial Differential Equations [9.588717577573684]
偏微分方程式(PDE)を解くためのスケーラブルな事前条件付き原始ハイブリッド勾配アルゴリズムを提案する。
本稿では,提案手法の性能を,一般的なディープラーニングアルゴリズムと比較する。
その結果,提案手法は効率的かつ堅牢に動作し,安定に収束することが示唆された。
論文 参考訳（メタデータ） (2024-11-09T20:39:10Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Fast Screening Rules for Optimal Design via Quadratic Lasso
Reformulation [0.135975510645475]
本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。
新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。
本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
論文 参考訳（メタデータ） (2023-10-13T08:10:46Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Continuation Path with Linear Convergence Rate [18.405645120971496]
経路追従アルゴリズムは、一連のサブプロブレムを順次解決する合成最適化問題によく用いられる。
本稿では,経路追従アルゴリズムの一次双対解析と,対象問題に対する線形収束率を保証するために,各サブプロブレムがどの程度正確に解けるかを決定する。
スパーシリティ誘導ペナルティによる最適化を考慮し、正規化パラメータに対するアクティブセットの変化を分析する。
論文 参考訳（メタデータ） (2021-12-09T18:42:13Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。