論文の概要: Optimal Randomized First-Order Methods for Least-Squares Problems

• arxiv url: http://arxiv.org/abs/2002.09488v2
• Date: Wed, 26 Feb 2020 00:34:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 01:57:04.193987
• Title: Optimal Randomized First-Order Methods for Least-Squares Problems
• Title（参考訳）: 最小二乗問題に対する最適ランダム化一階法
• Authors: Jonathan Lacotte, Mert Pilanci
• Abstract要約: このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
• 参考スコア（独自算出の注目度）: 56.05635751529922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-conditioned by an approximation of the Hessian, based on a subspace embedding of the data matrix. This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled randomized Hadamard transforms (SRHT). Our key technical innovation is the derivation of the limiting spectral density of SRHT embeddings. Leveraging this novel result, we derive the family of normalized orthogonal polynomials of the SRHT density and we find the optimal pre-conditioned first-order method along with its rate of convergence. Our analysis of Gaussian embeddings proceeds similarly, and leverages classical random matrix theory results. In particular, we show that for a given sketch size, SRHT embeddings exhibits a faster rate of convergence than Gaussian embeddings. Then, we propose a new algorithm by optimizing the computational complexity over the choice of the sketching dimension. To our knowledge, our resulting algorithm yields the best known complexity for solving least-squares problems with no condition number dependence.
• Abstract（参考訳）: 過決定最小二乗問題を解くためのランダム化アルゴリズムのクラスを正確に解析する。 本稿では,データ行列の部分空間埋め込みに基づいて,勾配をヘッセン近似で事前条件付けする一階法について考察する。 このアルゴリズムのクラスは、最小二乗問題に対する最速解法のうち、いくつかのランダム解法を含んでいる。 ガウス射影とランダム化アダマール変換(SRHT)の2つの古典的埋め込みに焦点を当てる。 我々の重要な技術的革新は、SRHT埋め込みのスペクトル密度の制限の導出である。 この新たな結果を利用して、srht密度の正規化直交多項式の族を導出し、その収束率とともに最適な事前条件付き一階法を求める。 ガウス埋め込みの解析も同様に進み、古典的ランダム行列理論の結果を利用する。 特に、与えられたスケッチサイズに対して、SRHT埋め込みはガウス埋め込みよりも高速な収束率を示すことを示す。 次に,スケッチ次元の選択よりも計算複雑性を最適化する新しいアルゴリズムを提案する。 我々の知る限り、我々のアルゴリズムは条件数に依存しない最小二乗問題を解くのに最もよく知られた複雑さをもたらす。

関連論文リスト

• Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees [23.614074988517864]
  本稿では,非正規化関数によって正規化あるいは凸化される最小二乗問題に対する高速近似を提案する。 スケッチされた凸や非近似問題を解くことにより、推定のための最小値率を初めて示す。
  論文  参考訳（メタデータ） (2023-11-03T09:35:01Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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