論文の概要: Learning the Positions in CountSketch

• arxiv url: http://arxiv.org/abs/2306.06611v2
• Date: Thu, 11 Apr 2024 00:31:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-12 19:27:55.876746
• Title: Learning the Positions in CountSketch
• Title（参考訳）: CountSketchにおける位置学習
• Authors: Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff,
• Abstract要約: 本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 49.57951567374372
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider sketching algorithms which first 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 and regression. In the learning-based sketching paradigm proposed by~\cite{indyk2019learning}, the sketch matrix is found by choosing a random sparse matrix, e.g., CountSketch, and then the values of its non-zero entries are updated 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-based algorithms that also optimize the locations of the non-zero entries. Our first proposed algorithm is based on a greedy algorithm. However, one drawback of the greedy algorithm is its slower training time. We fix this issue and propose approaches for learning a sketching matrix for both low-rank approximation and Hessian approximation for second order optimization. The latter is helpful for a range of constrained optimization problems, such as LASSO and matrix estimation with a nuclear norm constraint. Both approaches achieve good accuracy with a fast running time. Moreover, our experiments suggest that our algorithm can still reduce the error significantly even if we only have a very limited number of training matrices.
• Abstract（参考訳）: 本稿では、まずランダムなスケッチ行列と乗算してデータを圧縮し、次にスケッチを適用して最適化問題、例えば低ランク近似と回帰を迅速に解決するスケッチアルゴリズムについて考察する。 ――\cite{indyk2019learning} が提唱する学習ベーススケッチのパラダイムでは、スケッチ行列はランダムなスパース行列,eg, CountSketch を選択して見出され、トレーニングデータセット上で勾配降下を実行することで、その非ゼロエントリの値が更新される。 このパラダイムに関する研究の活発化にもかかわらず、注目すべき省略点は、以前のアルゴリズムのゼロでないエントリの位置が固定され、それらの値のみが学習されたことである。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。 最初の提案アルゴリズムは欲求アルゴリズムに基づく。 しかし、greedyアルゴリズムの欠点の1つは、訓練時間が遅いことである。 この問題を修正し,2次最適化のための低ランク近似とヘッセン近似の両方に対するスケッチ行列の学習手法を提案する。 後者は、LASSOや核ノルム制約による行列推定など、様々な制約付き最適化問題に有用である。 どちらのアプローチも高速な実行時間で精度が良い。 さらに,本実験では,訓練行列数が極めて少ない場合でも,アルゴリズムが誤差を大幅に低減できることを示した。

関連論文リスト

• Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization [32.939120407900035]
  私たちのアルゴリズムは、イテレーション毎に1つの線形システムだけを解決する必要のある、単純な更新ルールを備えています。 また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。
  論文  参考訳（メタデータ） (2024-06-04T06:56:41Z)
• AdaSub: Stochastic Optimization Using Second-Order Information in Low-Dimensional Subspaces [0.0]
  本稿では,低次元部分空間における2階情報に基づく探索方向の探索アルゴリズムであるAdaSubを紹介する。 一階法と比較して、二階法は収束特性が優れているが、繰り返しごとにヘッセン行列を計算する必要があるため、計算コストが過大になる。 予備的な数値結果から、AdaSubは所定の精度に達するのに必要なイテレーションの時間と回数で、一般的なイテレーションを超越していることが示される。
  論文  参考訳（メタデータ） (2023-10-30T22:24:23Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Learning Sparsity and Randomness for Data-driven Low Rank Approximation [0.0]
  学習に基づく低階近似アルゴリズムは、スケッチ行列を用いたランダム化低階近似の性能を大幅に向上させることができる。 本稿では,より優れたスパーシリティパターンを学習し,スケッチ行列の値にランダム性を加えるための2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2022-12-15T23:12:53Z)
• Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals [8.140698535149042]
  本稿では,その隣接行列を推定することにより,スパース重み付きグラフを学習するアルゴリズムを提案する。 提案アルゴリズムは,本論文におけるいくつかの既存手法よりも,平均反復回数の観点から,より高速に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-06T17:06:13Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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