論文の概要: Learning the Positions in CountSketch
- arxiv url: http://arxiv.org/abs/2007.09890v3
- Date: Mon, 7 Jun 2021 07:30:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 13:30:36.103974
- Title: Learning the Positions in CountSketch
- Title（参考訳）: CountSketchにおける位置学習
- Authors: Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff
- Abstract要約: 本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。
このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
- 参考スコア（独自算出の注目度）: 51.15935547615698
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider sketching algorithms which first quickly compress data by
multiplication with a random sketch matrix, and then apply the sketch to
quickly solve an optimization problem, e.g., low rank approximation. In the
learning-based sketching paradigm proposed by Indyk et al. [2019], the sketch
matrix is found by choosing a random sparse matrix, e.g., the CountSketch, and
then updating the values of the non-zero entries by running gradient descent on
a training data set. Despite the growing body of work on this paradigm, a
noticeable omission is that the locations of the non-zero entries of previous
algorithms were fixed, and only their values were learned. In this work we
propose the first learning algorithm that also optimizes the locations of the
non-zero entries. We show this algorithm gives better accuracy for low rank
approximation than previous work, and apply it to other problems such as
$k$-means clustering for the first time. We show that our algorithm is provably
better in the spiked covariance model and for Zipfian matrices. We also show
the importance of the sketch monotonicity property for combining learned
sketches. Our empirical results show the importance of optimizing not only the
values of the non-zero entries but also their positions.
- Abstract（参考訳）: まずランダムなスケッチ行列を乗算してデータを高速に圧縮するスケッチアルゴリズムについて検討し、そのスケッチを用いて最適化問題、例えば低ランク近似を高速に解く。
Indykらによる学習に基づくスケッチのパラダイム。
[2019]では、スケッチ行列はランダムなスパース行列、例えばCountSketchを選択し、トレーニングデータセット上で勾配降下を実行することで、ゼロでないエントリの値を更新することによって見つかる。
このパラダイムへの取り組みが増えているにもかかわらず、注目すべきは、以前のアルゴリズムのゼロでないエントリの位置が固定され、その値のみが学習されたことである。
本研究では,非ゼロエントリの位置を最適化する最初の学習アルゴリズムを提案する。
このアルゴリズムは,従来よりも低ランク近似の精度が向上することを示すとともに,k$-meansクラスタリングなどの他の問題にも初めて適用する。
本アルゴリズムはスパイク共分散モデルおよびジップフィアン行列においてより優れていることを示す。
また、学習したスケッチを組み合わせるために、スケッチ単調性の重要性を示す。
実験の結果,ゼロでないエントリの値だけでなく,その位置も最適化することが重要であることがわかった。
関連論文リスト
- Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Learning Sparsity and Randomness for Data-driven Low Rank Approximation [0.0]
学習に基づく低階近似アルゴリズムは、スケッチ行列を用いたランダム化低階近似の性能を大幅に向上させることができる。
本稿では,より優れたスパーシリティパターンを学習し,スケッチ行列の値にランダム性を加えるための2つの新しい手法を提案する。
論文 参考訳（メタデータ） (2022-12-15T23:12:53Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Accumulations of Projections--A Unified Framework for Random Sketches in
Kernel Ridge Regression [12.258887270632869]
n-by-n 経験的カーネル行列のスケッチを構築することは、多くのカーネルメソッドの計算を加速するための一般的なアプローチである。
カーネルリッジ回帰におけるスケッチ手法を構築するための統一フレームワークを提案する。
論文 参考訳（メタデータ） (2021-03-06T05:02:17Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。
学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-02-24T14:50:59Z) - Effective and Sparse Count-Sketch via k-means clustering [17.26941311020711]
我々は,k平均クラスタリングアルゴリズムを用いて,カウントスケッチの再構成誤差を低減し,低次元スケッチ行列を得る。
6つの実生活分類データセットに基づく実験結果から,提案手法は従来のカウントスケッチよりも精度が高いことを示した。
論文 参考訳（メタデータ） (2020-11-24T11:44:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。