論文の概要: Converting ADMM to a Proximal Gradient for Convex Optimization Problems
- arxiv url: http://arxiv.org/abs/2104.10911v1
- Date: Thu, 22 Apr 2021 07:41:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-23 13:47:40.592133
- Title: Converting ADMM to a Proximal Gradient for Convex Optimization Problems
- Title(参考訳): 凸最適化問題の近似勾配へのADMM変換
- Authors: Ryosuke Shimmura and Joe Suzuki
- Abstract要約: 融解ラッソや凸クラスタリングなどのスパース推定では、問題を解くために、近位勾配法またはマルチプライヤー(ADMM)の交互方向法のいずれかを適用します。
本論文では,制約と目的が強く凸であると仮定し,ADMM溶液を近位勾配法に変換する一般的な方法を提案する。
数値実験により, 効率の面で有意な改善が得られることを示した。
- 参考スコア(独自算出の注目度): 4.56877715768796
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In machine learning and data science, we often consider efficiency for
solving problems. In sparse estimation, such as fused lasso and convex
clustering, we apply either the proximal gradient method or the alternating
direction method of multipliers (ADMM) to solve the problem. It takes time to
include matrix division in the former case, while an efficient method such as
FISTA (fast iterative shrinkage-thresholding algorithm) has been developed in
the latter case. This paper proposes a general method for converting the ADMM
solution to the proximal gradient method, assuming that the constraints and
objectives are strongly convex. Then, we apply it to sparse estimation
problems, such as sparse convex clustering and trend filtering, and we show by
numerical experiments that we can obtain a significant improvement in terms of
efficiency.
- Abstract(参考訳): 機械学習とデータサイエンスでは、問題解決の効率性を考えることが多い。
混合ラッソや凸クラスタリングなどのスパース推定では、近似勾配法あるいは乗算器の交互方向法(ADMM)を適用し、この問題を解決する。
前者では行列分割を含めるのに時間がかかるが、後者ではfista(fast iterative shrinkage-thresholding algorithm)のような効率的な手法が開発されている。
本稿では,admm溶液を近位勾配法に変換する一般的な方法を提案する。
次に, スパース凸クラスタリングやトレンドフィルタリングといったスパース推定問題に適用し, 数値実験により, 効率の面で大きな改善が得られることを示す。
関連論文リスト
- Regularized Projection Matrix Approximation with Applications to Community Detection [1.3761665705201904]
本稿では,アフィニティ行列からクラスタ情報を復元するための正規化プロジェクション行列近似フレームワークを提案する。
3つの異なるペナルティ関数について検討し, それぞれが有界, 正, スパースシナリオに対応するように調整した。
合成および実世界の両方のデータセットで行った数値実験により、我々の正規化射影行列近似アプローチはクラスタリング性能において最先端の手法を著しく上回っていることが明らかとなった。
論文 参考訳(メタデータ) (2024-05-26T15:18:22Z) - Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。
数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
論文 参考訳(メタデータ) (2023-08-31T14:16:30Z) - Neural incomplete factorization: learning preconditioners for the conjugate gradient method [2.899792823251184]
我々は、効率的なプレコンディショナーの生成を加速するためのデータ駆動型アプローチを開発する。
一般的に手動のプリコンディショナーをグラフニューラルネットワークの出力に置き換える。
本手法は, 行列の不完全分解を発生させ, 神経不完全分解(NeuralIF)と呼ばれる。
論文 参考訳(メタデータ) (2023-05-25T11:45:46Z) - Nystrom Method for Accurate and Scalable Implicit Differentiation [25.29277451838466]
我々は,Nystrom法が他の手法と同等あるいは優れた性能を連続的に達成していることを示す。
提案手法は数値的な不安定さを回避し,反復を伴わない行列演算で効率的に計算できる。
論文 参考訳(メタデータ) (2023-02-20T02:37:26Z) - Computational Complexity of Sub-linear Convergent Algorithms [0.0]
小サンプルから始めて幾何的に拡大し、前のサンプルの解を用いて新しいEMMを計算する方法について検討する。
これにより、線形収束の1次最適化アルゴリズムの問題を解決するが、計算の複雑さは小さくなる。
論文 参考訳(メタデータ) (2022-09-29T05:38:06Z) - The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。
我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文 参考訳(メタデータ) (2022-09-27T09:27:29Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳(メタデータ) (2020-06-11T18:49:06Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。