論文の概要: Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

• arxiv url: http://arxiv.org/abs/2006.05874v2
• Date: Fri, 23 Oct 2020 12:05:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 04:40:27.215147
• Title: Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
• Title（参考訳）: 正則化最小二乗最適化のための有効次元適応スケッチ法
• Authors: Jonathan Lacotte and Mert Pilanci
• Abstract要約: スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
• 参考スコア（独自算出の注目度）: 56.05635751529922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT). While current randomized solvers for least-squares optimization prescribe an embedding dimension at least greater than the data dimension, we show that the embedding dimension can be reduced to the effective dimension of the optimization problem, and still preserve high-probability convergence guarantees. In this regard, we derive sharp matrix deviation inequalities over ellipsoids for both Gaussian and SRHT embeddings. Specifically, we improve on the constant of a classical Gaussian concentration bound whereas, for SRHT embeddings, our deviation inequality involves a novel technical approach. Leveraging these bounds, we are able to design a practical and adaptive algorithm which does not require to know the effective dimension beforehand. Our method starts with an initial embedding dimension equal to 1 and, over iterations, increases the embedding dimension up to the effective one at most. Hence, our algorithm improves the state-of-the-art computational complexity for solving regularized least-squares problems. Further, we show numerically that it outperforms standard iterative solvers such as the conjugate gradient method and its pre-conditioned version on several standard machine learning datasets.
• Abstract（参考訳）: スケッチに基づくl2正規化最小二乗問題を解くための新しいランダム化アルゴリズムを提案する。 最も一般的なランダム埋め込み(gaussian embeddeds)とサブサンプリングランダムアダマール変換(subsampled randomized hadamard transform:srht)の2つを考える。 最小二乗最適化のための現在のランダム化解法は、少なくともデータ次元よりも大きい埋め込み次元を規定するが、埋め込み次元は最適化問題の有効次元に還元でき、高確率収束保証を保っていることを示す。 この観点から、ガウスおよびSRHTの埋め込みにおける楕円体上の鋭い行列偏差不等式を導出する。 具体的には、古典ガウス濃度境界の定数を改善する一方、SRHT埋め込みでは、偏差の不等式は、新しい技術的アプローチを含む。 これらの境界を利用することで、事前に有効次元を知る必要のない実用的かつ適応的なアルゴリズムを設計できる。 我々の手法は初期埋め込み次元が 1 に等しいことから始まり、反復によって、埋め込み次元が最大で有効なものまで増加する。 したがって,本アルゴリズムは正規化最小二乗問題を解くための最先端計算量を改善する。 さらに,いくつかの標準機械学習データセットにおいて,共役勾配法や事前条件付きバージョンなど,標準的な反復解法よりも優れていることを示す。

関連論文リスト

• 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)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality [32.292481678592544]
  自己整合性,複合性,強凸客観的関数を用いた凸最適化問題に対する二次収束率を有するランダム化アルゴリズムを提案する。 私たちの最初の貢献は、各イテレーションにおいて、埋め込み次元はヘッセン行列の有効次元と同じくらい小さくできることを示すことである。 この結果は、最先端のサブサンプリングニュートン法の古典線形-四次収束率を劇的に改善する。
  論文  参考訳（メタデータ） (2021-05-15T20:24:26Z)
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners [37.03247707259297]
  二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 効果的な寸法の観点からスケッチサイズを選択する際の大きな困難は、後者が実際には通常不明であるという事実にあります。
  論文  参考訳（メタデータ） (2021-04-29T04:36:41Z)
• 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)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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