論文の概要: BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory

• arxiv url: http://arxiv.org/abs/2010.13829v2
• Date: Wed, 26 May 2021 17:24:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 19:41:05.058016
• Title: BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
• Title（参考訳）: BEAR:サブリニアメモリにおける超高次元特徴選択のためのスケッチBFGSアルゴリズム
• Authors: Amirali Aghazadeh, Vipul Gupta, Alex DeWeese, O. Ozan Koyluoglu and Kannan Ramchandran
• Abstract要約: 現在の大規模スケッチアルゴリズムは、スケッチされた領域における不可逆的な衝突とノイズの蓄積により、メモリ精度のトレードオフが低いことを示す。 我々はBEARを開発し、著名なブロイデン=フレッチャー=ゴールドファーブ=シャノン(BFGS)アルゴリズムに2階勾配を格納することで余分な衝突を避ける。 実世界のデータセットの実験により、BEARは1次スケッチアルゴリズムと同一の分類精度を達成するために最大で3桁のメモリスペースを必要とすることが示された。
• 参考スコア（独自算出の注目度）: 13.596664481933875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider feature selection for applications in machine learning where the dimensionality of the data is so large that it exceeds the working memory of the (local) computing machine. Unfortunately, current large-scale sketching algorithms show poor memory-accuracy trade-off due to the irreversible collision and accumulation of the stochastic gradient noise in the sketched domain. Here, we develop a second-order ultra-high dimensional feature selection algorithm, called BEAR, which avoids the extra collisions by storing the second-order gradients in the celebrated Broyden-Fletcher-Goldfarb-Shannon (BFGS) algorithm in Count Sketch, a sublinear memory data structure from the streaming literature. Experiments on real-world data sets demonstrate that BEAR requires up to three orders of magnitude less memory space to achieve the same classification accuracy compared to the first-order sketching algorithms. Theoretical analysis proves convergence of BEAR with rate O(1/t) in t iterations of the sketched algorithm. Our algorithm reveals an unexplored advantage of second-order optimization for memory-constrained sketching of models trained on ultra-high dimensional data sets.
• Abstract（参考訳）: データの次元が大きすぎて、(ローカルな)コンピューティングマシンの動作メモリを超えるような、機械学習のアプリケーションにおける特徴選択について検討する。 残念なことに、現在の大規模スケッチアルゴリズムは、非可逆的な衝突とスケッチ領域における確率勾配ノイズの蓄積により、メモリ精度のトレードオフが低い。 そこで本研究では,ストリーミング文献のサブリニアメモリデータ構造であるcount sketchにおいて,ブロイデン・フレッチャー・ゴールドファーム・シャノン(bfgs)アルゴリズムに2次勾配を格納することにより,余分な衝突を回避する2次超高次元特徴選択アルゴリズム bearを開発した。 実世界のデータセットの実験により、BEARは1次スケッチアルゴリズムと同一の分類精度を達成するために最大で3桁のメモリスペースを必要とすることが示された。 理論的解析は、スケッチされたアルゴリズムの t 反復におけるレート O(1/t) の BEAR の収束を証明している。 提案アルゴリズムは,超高次元データセットで学習したモデルのメモリ制限スケッチにおける2次最適化の未探索の利点を明らかにする。

関連論文リスト

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Sketch and shift: a robust decoder for compressive clustering [17.627195350266796]
  圧縮学習は、大規模学習のメモリフットプリントを大幅に削減する、新たなアプローチである。 CL-OMPRよりも大幅に改善された代替デコーダを提案する。 提案アルゴリズムは,従来より10倍小さいMNISTデータセットのスケッチからクラスタリング情報を抽出することができる。
  論文  参考訳（メタデータ） (2023-12-15T16:53:55Z)
• Eva: A General Vectorized Approximation Framework for Second-order Optimization [16.647611352181574]
  メモリ効率と時間効率の2次アルゴリズムであるEvaを2つの新しい手法で提案する。 我々はシャーマン・モリソンの公式を使用する逆計算を明示的に行わずに効率的な更新式を導出する。 実験によると、Evaは1次SGDと2次アルゴリズムと比較して、エンドツーエンドのトレーニング時間を2.05倍と2.42倍に短縮する。
  論文  参考訳（メタデータ） (2023-08-04T03:51:38Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• SketchOGD: Memory-Efficient Continual Learning [9.372686529398859]
  機械学習モデルが一連のタスクで継続的にトレーニングされる場合、以前のタスクで学んだことを忘れる義務がある。 本稿では,OGD(勾配降下法)と呼ばれる確立されたアルゴリズムを改良した,破滅的忘れに対するメモリ効率のよい解を提案する。
  論文  参考訳（メタデータ） (2023-05-25T18:56:19Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning [3.0204520109309843]
  機械学習における連続最適化問題に対処する一階法と二階法を考察する。 一階述語の場合、半決定論的から二次正規化への遷移の枠組みを提案する。 本稿では,適応的なサンプリングと適応的なステップサイズを持つ新しい1次アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-29T18:10:00Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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