論文の概要: Learning Large Scale Sparse Models
- arxiv url: http://arxiv.org/abs/2301.10958v1
- Date: Thu, 26 Jan 2023 06:29:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 14:10:23.532904
- Title: Learning Large Scale Sparse Models
- Title(参考訳): 大規模スパースモデルの学習
- Authors: Atul Dhingra, Jie Shen, Nicholas Kleene
- Abstract要約: サンプルの数や特徴次元が数百万から数十億にも達する大規模環境でスパースモデルを学習することを検討する。
ラッソのようなスパースモデルをオンライン的に学習し、ランダムに選択されたサンプルが1つだけ露呈してスパース勾配を更新することを提案する。
これにより、メモリコストはサンプルサイズに依存しず、1つのサンプルの勾配評価が効率的となる。
- 参考スコア(独自算出の注目度): 6.428186644949941
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we consider learning sparse models in large scale settings,
where the number of samples and the feature dimension can grow as large as
millions or billions. Two immediate issues occur under such challenging
scenario: (i) computational cost; (ii) memory overhead. In particular, the
memory issue precludes a large volume of prior algorithms that are based on
batch optimization technique. To remedy the problem, we propose to learn sparse
models such as Lasso in an online manner where in each iteration, only one
randomly chosen sample is revealed to update a sparse iterate. Thereby, the
memory cost is independent of the sample size and gradient evaluation for one
sample is efficient. Perhaps amazingly, we find that with the same parameter,
sparsity promoted by batch methods is not preserved in online fashion. We
analyze such interesting phenomenon and illustrate some effective variants
including mini-batch methods and a hard thresholding based stochastic gradient
algorithm. Extensive experiments are carried out on a public dataset which
supports our findings and algorithms.
- Abstract(参考訳): 本研究では,スパースモデルを大規模に学習し,サンプルの数と特徴次元を数百万から数十億に拡大する方法について検討する。
そのような困難なシナリオでは、すぐに2つの問題が発生する。
(i)計算コスト
(ii)メモリオーバーヘッド。
特に、メモリ問題は、バッチ最適化技術に基づく大量の事前アルゴリズムを妨げている。
そこで本研究では,sparse iterateを更新するために,各イテレーションにおいてランダムに選択されたサンプルが1つしかないことを明らかにするオンライン手法を用いて,lassoのようなスパースモデルを学ぶことを提案する。
これにより、メモリコストはサンプルサイズに依存しず、1つのサンプルの勾配評価が効率的となる。
おそらく驚くべきことに、同じパラメータでバッチメソッドによって促進されるスパーシティは、オンライン形式では保存されない。
このような興味深い現象を分析し、ミニバッチ法やハードしきい値に基づく確率勾配アルゴリズムなど、いくつかの有効な変種を示す。
我々の発見とアルゴリズムをサポートする公開データセットで広範な実験が行われます。
関連論文リスト
- Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing [2.542838926315103]
ランダム化ブロックKaczmarz法(RBK)のデータの一様サンプリング時の収束を解析し,その繰り返しがモンテカルロの感覚で$textit$ least-squaresの解に収束することを示す。
RBKに正規化を組み込むことで、これらの問題を解決する。
自然勾配最適化から生じる例を含む数値実験により、正規化アルゴリズムReBlocKは、高速特異値減衰を示す現実的な問題に対して、最小バッチ勾配勾配よりも優れていることが示唆された。
論文 参考訳(メタデータ) (2025-02-02T19:23:46Z) - Best-Subset Selection in Generalized Linear Models: A Fast and
Consistent Algorithm via Splicing Technique [0.6338047104436422]
ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。
軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。
我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
論文 参考訳(メタデータ) (2023-08-01T03:11:31Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳(メタデータ) (2023-07-26T16:19:19Z) - Accelerated Doubly Stochastic Gradient Algorithm for Large-scale
Empirical Risk Minimization [23.271890743506514]
本稿では,学習課題に対する大規模経験的リスク最小化問題を解くために,新たな高速化マルチモーメンタム手法を用いた二重アルゴリズムを提案する。
絶対的に優れた収束率を享受しながら、各イテレーションにおいて、そのようなアルゴリズムはサンプルの小さなバッチにのみアクセスし、変数座標の小さなブロックを更新する。
論文 参考訳(メタデータ) (2023-04-23T14:21:29Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。
KRRのストリーミング版であるStreaMRAKを提案する。
本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
論文 参考訳(メタデータ) (2021-08-23T21:03:09Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and
Personalized Federated Learning [56.17603785248675]
モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。
既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。
本稿では,MAMLのメモリベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-09T08:47:58Z) - DPER: Efficient Parameter Estimation for Randomly Missing Data [0.24466725954625884]
本稿では,1クラス・複数クラスのランダムに欠落したデータセットに対して,最大推定値(MLE)を求めるアルゴリズムを提案する。
我々のアルゴリズムは、データを通して複数のイテレーションを必要としないので、他の方法よりも時間のかかることを約束します。
論文 参考訳(メタデータ) (2021-06-06T16:37:48Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳(メタデータ) (2020-06-02T17:52:59Z) - Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
多次元回帰を用いた固定設計の基本問題について検討する。
我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。
提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
論文 参考訳(メタデータ) (2020-03-24T19:39:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。