論文の概要: Learning-Augmented Sketches for Hessians

• arxiv url: http://arxiv.org/abs/2102.12317v1
• Date: Wed, 24 Feb 2021 14:50:59 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-26 07:58:59.005520
• Title: Learning-Augmented Sketches for Hessians
• Title（参考訳）: ヘシアンのための学習型スケッチ
• Authors: Yi Li, Honghao Lin, David P. Woodruff
• Abstract要約: 第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。 学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
• 参考スコア（独自算出の注目度）: 54.97773807211337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sketching is a dimensionality reduction technique where one compresses a matrix by linear combinations that are typically chosen at random. A line of work has shown how to sketch the Hessian to speed up each iteration in a second order method, but such sketches usually depend only on the matrix at hand, and in a number of cases are even oblivious to the input matrix. One could instead hope to learn a distribution on sketching matrices that is optimized for the specific distribution of input matrices. We show how to design learned sketches for the Hessian in the context of second order methods, where we learn potentially different sketches for the different iterations of an optimization procedure. We show empirically that learned sketches, compared with their "non-learned" counterparts, improve the approximation accuracy for important problems, including LASSO, SVM, and matrix estimation with nuclear norm constraints. Several of our schemes can be proven to perform no worse than their unlearned counterparts. Additionally, we show that a smaller sketching dimension of the column space of a tall matrix is possible, assuming an oracle for predicting rows which have a large leverage score.
• Abstract（参考訳）: スケッチは、典型的にランダムに選択される線形結合によって行列を圧縮する次元還元技術である。 一連の作業では、ヘシアンが2階の方法で各イテレーションを高速化する方法が示されているが、そのようなスケッチは通常、手元の行列のみに依存しており、多くのケースでは入力行列にさえ従わない。 代わりに、入力行列の特定の分布に最適化されたスケッチ行列の分布を学ぶことができる。 我々は、最適化手順の異なるイテレーションのための潜在的に異なるスケッチを学習するセカンドオーダーメソッドの文脈でヘッシアンのための学習スケッチを設計する方法を示す。 学習したスケッチを「学習しない」スケッチと比較し、LASSO、SVM、および核ノルム制約による行列推定を含む重要な問題に対する近似精度を向上させることを実証的に示す。 私たちのスキームのいくつかは、未発見のスキームよりもパフォーマンスが良いことが証明できます。 さらに,大きなレバレッジスコアを持つ行を予測するためのオラクルを仮定して,高い行列の列空間のスケッチ次元が小さくなることを示す。

関連論文リスト

• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Accumulations of Projections--A Unified Framework for Random Sketches in Kernel Ridge Regression [12.258887270632869]
  n-by-n 経験的カーネル行列のスケッチを構築することは、多くのカーネルメソッドの計算を加速するための一般的なアプローチである。 カーネルリッジ回帰におけるスケッチ手法を構築するための統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-03-06T05:02:17Z)
• Effective and Sparse Count-Sketch via k-means clustering [17.26941311020711]
  我々は,k平均クラスタリングアルゴリズムを用いて,カウントスケッチの再構成誤差を低減し,低次元スケッチ行列を得る。 6つの実生活分類データセットに基づく実験結果から,提案手法は従来のカウントスケッチよりも精度が高いことを示した。
  論文  参考訳（メタデータ） (2020-11-24T11:44:02Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Localized sketching for matrix multiplication and ridge regression [29.61816941867831]
  局所的スケッチの新たな設定において,スケッチ化された近似行列乗法とリッジ回帰を考察する。 緩やかな条件下では、ブロック対角線スケッチ行列はO(安定ランク/エプシロン2)と$O(stat. dim. epsilon)$の値のみを必要とする。
  論文  参考訳（メタデータ） (2020-03-20T04:25:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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