論文の概要: A Deterministic Streaming Sketch for Ridge Regression

• arxiv url: http://arxiv.org/abs/2002.02013v4
• Date: Wed, 10 Mar 2021 07:47:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-03 21:20:45.998266
• Title: A Deterministic Streaming Sketch for Ridge Regression
• Title（参考訳）: リッジ回帰のための決定論的ストリーミングスケッチ
• Authors: Benwei Shi and Jeff M. Phillips
• Abstract要約: リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。 これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。 合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
• 参考スコア（独自算出の注目度）: 15.256452294422294
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a deterministic space-efficient algorithm for estimating ridge regression. For $n$ data points with $d$ features and a large enough regularization parameter, we provide a solution within $\varepsilon$ L$_2$ error using only $O(d/\varepsilon)$ space. This is the first $o(d^2)$ space deterministic streaming algorithm with guaranteed solution error and risk bound for this classic problem. The algorithm sketches the covariance matrix by variants of Frequent Directions, which implies it can operate in insertion-only streams and a variety of distributed data settings. In comparisons to randomized sketching algorithms on synthetic and real-world datasets, our algorithm has less empirical error using less space and similar time.
• Abstract（参考訳）: リッジ回帰推定のための決定論的空間効率アルゴリズムを提案する。 d$機能と十分な正規化パラメータを持つn$データポイントに対して、$o(d/\varepsilon)$スペースのみを使用して、$\varepsilon$ l$_2$エラーの解を提供する。 これは最初の$o(d^2)$空間決定論的ストリーミングアルゴリズムであり、この古典的な問題に対する解誤差とリスクが保証されている。 このアルゴリズムは、共分散行列を周波数方向の変種でスケッチし、挿入専用ストリームとさまざまな分散データ設定で操作することができる。 合成および実世界のデータセット上でのランダム化されたスケッチアルゴリズムと比較すると,空間と類似時間が少なく,経験的誤差が少ない。

関連論文リスト

• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization [16.346069386394703]
  定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。 単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
  論文  参考訳（メタデータ） (2020-10-27T15:22:49Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
  論文  参考訳（メタデータ） (2020-03-24T19:39:34Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions [2.2940141855172036]
  我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。 $delta$-correctアルゴリズムの下位境界はよく知られている。 我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
  論文  参考訳（メタデータ） (2019-08-24T05:31:49Z)

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

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