論文の概要: Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners

• arxiv url: http://arxiv.org/abs/2104.14101v1
• Date: Thu, 29 Apr 2021 04:36:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-30 12:55:20.225874
• Title: Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners
• Title（参考訳）: 適応型スケッチベースプレコンディショナーを用いた高速凸2次最適化法
• Authors: Jonathan Lacotte and Mert Pilanci
• Abstract要約: 二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 効果的な寸法の観点からスケッチサイズを選択する際の大きな困難は、後者が実際には通常不明であるという事実にあります。
• 参考スコア（独自算出の注目度）: 37.03247707259297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider least-squares problems with quadratic regularization and propose novel sketching-based iterative methods with an adaptive sketch size. The sketch size can be as small as the effective dimension of the data matrix to guarantee linear convergence. However, a major difficulty in choosing the sketch size in terms of the effective dimension lies in the fact that the latter is usually unknown in practice. Current sketching-based solvers for regularized least-squares fall short on addressing this issue. Our main contribution is to propose adaptive versions of standard sketching-based iterative solvers, namely, the iterative Hessian sketch and the preconditioned conjugate gradient method, that do not require a priori estimation of the effective dimension. We propose an adaptive mechanism to control the sketch size according to the progress made in each step of the iterative solver. If enough progress is not made, the sketch size increases to improve the convergence rate. We prove that the adaptive sketch size scales at most in terms of the effective dimension, and that our adaptive methods are guaranteed to converge linearly. Consequently, our adaptive methods improve the state-of-the-art complexity for solving dense, ill-conditioned least-squares problems. Importantly, we illustrate numerically on several synthetic and real datasets that our method is extremely efficient and is often significantly faster than standard least-squares solvers such as a direct factorization based solver, the conjugate gradient method and its preconditioned variants.
• Abstract（参考訳）: 二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 しかしながら、実効次元の観点でスケッチサイズを選択することの難しさは、一般的にはスケッチサイズが未知であるという事実にある。 正規化された最小二乗数に対する現在のスケッチベースの解法はこの問題を解決するのに不足している。 本研究の主な貢献は,有効次元の事前推定を必要としない,標準的なスケッチに基づく反復解法,すなわち反復的ヘッセンスケッチと事前条件付き共役勾配法を適応的に提案することである。 本稿では,反復解法の各ステップの進捗に応じて,スケッチサイズを適応的に制御する機構を提案する。 十分な進捗が得られなければ、スケッチサイズが増加して収束率が向上する。 適応的スケッチサイズは,有効次元の点で最大にスケールし,適応的手法が線形に収束することが保証されていることを証明した。 その結果, 適応手法は, 密で不条件の最小二乗問題を解くために, 最先端の複雑さを改善する。 重要なことは、我々の手法は極めて効率的であり、直接分解に基づく解法、共役勾配法、および事前条件付き変種など、標準的な最小二乗解法よりもはるかに高速である。

関連論文リスト

• Distributed Least Squares in Small Space via Sketching and Bias Reduction [0.0]
  マトリックススケッチは、大きなデータ行列のサイズを減らす強力なツールである。 誤差よりも推定器のバイアスを最小限に抑えるスケッチ手法を設計することで,これらの制限を分散環境で回避できることを示す。 特に、最適空間と現在の行列乗算時間で動作するスパーススケッチ法を提案し、2つのパスデータを用いて、ほぼ偏りのない最小二乗推定器を復元する。
  論文  参考訳（メタデータ） (2024-05-08T18:16:37Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality [32.292481678592544]
  自己整合性,複合性,強凸客観的関数を用いた凸最適化問題に対する二次収束率を有するランダム化アルゴリズムを提案する。 私たちの最初の貢献は、各イテレーションにおいて、埋め込み次元はヘッセン行列の有効次元と同じくらい小さくできることを示すことである。 この結果は、最先端のサブサンプリングニュートン法の古典線形-四次収束率を劇的に改善する。
  論文  参考訳（メタデータ） (2021-05-15T20:24:26Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。