論文の概要: ALS: Augmented Lagrangian Sketching Methods for Linear Systems
- arxiv url: http://arxiv.org/abs/2208.06152v1
- Date: Fri, 12 Aug 2022 07:49:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-15 13:53:32.685042
- Title: ALS: Augmented Lagrangian Sketching Methods for Linear Systems
- Title（参考訳）: ALS: 線形システムのための拡張ラグランジアンスケッチ法
- Authors: Md Sarowar Morshed
- Abstract要約: 我々は、ペナルティ・スケッチ(PS)と拡張ラグランジアン・スケッチ(ALS)の2つの基本的なスケッチ技術を開発した。
提案手法は,ラグランジアンペナルティスケッチを導入し,Sketch & Project(SP)法の範囲を拡張・一般化する。
我々はPS法とALS法のグローバル収束率とCesaro平均反復率のサブ線形$mathcalO(frac1k)$レートを証明した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop two fundamental stochastic sketching techniques; Penalty Sketching
(PS) and Augmented Lagrangian Sketching (ALS) for solving consistent linear
systems. The proposed PS and ALS techniques extend and generalize the scope of
Sketch & Project (SP) method by introducing Lagrangian penalty sketches. In
doing so, we recover SP methods as special cases and furthermore develop a
family of new stochastic iterative methods. By varying sketch parameters in the
proposed PS method, we recover novel stochastic methods such as Penalty Newton
Descent, Penalty Kaczmarz, Penalty Stochastic Descent, Penalty Coordinate
Descent, Penalty Gaussian Pursuit, and Penalty Block Kaczmarz. Furthermore, the
proposed ALS method synthesizes a wide variety of new stochastic methods such
as Augmented Newton Descent, Augmented Kaczmarz, Augmented Stochastic Descent,
Augmented Coordinate Descent, Augmented Gaussian Pursuit, and Augmented Block
Kaczmarz into one framework. Moreover, we show that the developed PS and ALS
frameworks can be used to reformulate the original linear system into
equivalent stochastic optimization problems namely the Penalty Stochastic
Reformulation and Augmented Stochastic Reformulation. We prove global
convergence rates for the PS and ALS methods as well as sub-linear
$\mathcal{O}(\frac{1}{k})$ rates for the Cesaro average of iterates. The
proposed convergence results hold for a wide family of distributions of random
matrices, which provides the opportunity of fine-tuning the randomness of the
method suitable for specific applications. Finally, we perform computational
experiments that demonstrate the efficiency of our methods compared to the
existing SP methods.
- Abstract（参考訳）: 我々は,一貫した線形系を解くために,Penalty Sketching(PS)とAugmented Lagrangian Sketching(ALS)の2つの基本的な確率的スケッチ技術を開発した。
提案手法は,ラグランジアンペナルティスケッチを導入し,Sketch & Project(SP)法の範囲を拡張し,一般化する。
そこで我々はSP法を特殊事例として回収し,さらに新しい確率的反復法を考案した。
提案手法におけるスケッチパラメータの変化により,Penalty Newton Descent, Penalty Kaczmarz, Penalty Stochastic Descent, Penalty Coordinate Descent, Penalty Gaussian Pursuit, Penalty Block Kaczmarzなどの新しい確率的手法を復元する。
さらに, ALS法は, Augmented Newton Descent, Augmented Kaczmarz, Augmented Stochastic Descent, Augmented Coordinate Descent, Augmented Gaussian Pursuit, Augmented Block Kaczmarzなどの新しい確率的手法を一つのフレームワークに合成する。
さらに,開発したPSおよびALSフレームワークを用いて,元の線形系を等価な確率的最適化問題,すなわちPinalty Stochastic ReformulationとAugmented Stochastic Reformulationに書き換えることができることを示す。
我々は,ps および als 法に対する大域収束率,および cesaro 平均イテレートに対する sub-linear $\mathcal{o}(\frac{1}{k})$ rate を証明した。
提案する収束結果は、ランダム行列の分布の幅広い族を対象とし、特定の用途に適した方法のランダム性を微調整する機会を提供する。
最後に,既存のsp法と比較して,提案手法の効率性を示す計算実験を行う。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。
本稿では,直感的に設計を記述し,設計選択について説明する。
本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
論文 参考訳（メタデータ） (2023-10-31T16:15:13Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Adaptive Learning Rates for Faster Stochastic Gradient Methods [6.935471115003109]
いくつかの2次凸勾配法を改善するための適応的なステップサイズ戦略を提案する。
最初の方法は古典的なPolyakのステップサイズ(Polyak, 1987)に基づいており、この手法の最近の発展の延長である。
第2の手法であるGraDSは「勾配の多様性」によってステップサイズを再スケールする
論文 参考訳（メタデータ） (2022-08-10T11:36:00Z) - A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction [2.048226951354646]
弱凸, 複合最適化問題に対する実装可能な近位点(SPP)法を開発した。
提案アルゴリズムは分散低減機構を組み込んでおり、その結果の更新は不正確なセミスムース・ニュートン・フレームワークを用いて解決される。
論文 参考訳（メタデータ） (2022-04-01T13:08:49Z) - Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient
Methods [73.35353358543507]
SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。
本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。
本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
論文 参考訳（メタデータ） (2022-02-15T09:17:39Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Minibatch and Momentum Model-based Methods for Stochastic Non-smooth
Non-convex Optimization [3.4809730725241597]
モデルベース手法に対する2つの重要な拡張を行う。
まず,各イテレーションのモデル関数を近似するために,サンプルの集合を用いる新しいミニバッチを提案する。
第二に、運動量法の成功により、新しい凸モデルを提案する。
論文 参考訳（メタデータ） (2021-06-06T05:31:57Z) - Accelerated, Optimal, and Parallel: Some Results on Model-Based
Stochastic Optimization [33.71051480619541]
凸最適化問題を解決するためのモデルベース手法の近似近位点(aProx)ファミリを拡張します。
我々は、非漸近収束保証と、ミニバッチサイズの線形スピードアップを提供する加速スキームを提供する。
我々は,「補間」問題に対する新しい基本定数を同定し,収束率の改善と下界の整合性を示す。
論文 参考訳（メタデータ） (2021-01-07T18:58:39Z) - State Space Expectation Propagation: Efficient Inference Schemes for
Temporal Gaussian Processes [21.22700483305901]
非時間的時間的および時間的共役過程モデルにおけるベイズ推定を近似する。
我々はこれらのアルゴリズムについて統一的な視点を提供し、パワーEPモーメントマッチングのステップを線形化に置き換えることで、古典的なスムースラーをいかに回復するかを示す。
論文 参考訳（メタデータ） (2020-07-12T13:59:25Z) - Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。
大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
論文 参考訳（メタデータ） (2020-02-16T08:35:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。