論文の概要: Online Active Regression
- arxiv url: http://arxiv.org/abs/2207.05945v1
- Date: Wed, 13 Jul 2022 03:53:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-14 14:22:58.405841
- Title: Online Active Regression
- Title(参考訳): Online Active Regression
- Authors: Cheng Chen, Yi Li, Yiming Sun
- Abstract要約: 学習者はデータポイントを1つずつ受け取り、対応するラベルを収集すべきかを判断する。
目標は、ラベルクエリの少ない予算で、受信したデータポイントのレグレッションを効率的に維持することである。
- 参考スコア(独自算出の注目度): 8.397196353612042
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Active regression considers a linear regression problem where the learner
receives a large number of data points but can only observe a small number of
labels. Since online algorithms can deal with incremental training data and
take advantage of low computational cost, we consider an online extension of
the active regression problem: the learner receives data points one by one and
immediately decides whether it should collect the corresponding labels. The
goal is to efficiently maintain the regression of received data points with a
small budget of label queries. We propose novel algorithms for this problem
under $\ell_p$ loss where $p\in[1,2]$. To achieve a $(1+\epsilon)$-approximate
solution, our proposed algorithms only require
$\tilde{\mathcal{O}}(\epsilon^{-2} d \log(n\kappa))$ queries of labels, where
$n$ is the number of data points and $\kappa$ is a quantity, called the
condition number, of the data points. The numerical results verify our
theoretical results and show that our methods have comparable performance with
offline active regression algorithms.
- Abstract(参考訳): アクティブ回帰は、学習者が大量のデータポイントを受信するが、少数のラベルしか観測できない線形回帰問題を考える。
オンラインアルゴリズムは、インクリメンタルなトレーニングデータを扱うことができ、低計算コストを生かすことができるため、アクティブ回帰問題のオンライン拡張を考える: 学習者はデータポイントを1つずつ受け取り、対応するラベルを収集すべきかどうかを即座に決定する。
目標は、受信したデータポイントのレグレッションをラベルクエリの少ない予算で効率的に維持することである。
この問題に対する新しいアルゴリズムを$\ell_p$ Los, $p\in[1,2]$で提案する。
1+\epsilon)$-approximate 解を得るためには、提案するアルゴリズムはラベルのクエリに対して $\tilde{\mathcal{o}}(\epsilon^{-2} d \log(n\kappa))$ のみを必要とする。
その結果,提案手法はオフラインアクティブ回帰アルゴリズムと同等の性能を持つことがわかった。
関連論文リスト
- Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。
この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
論文 参考訳(メタデータ) (2023-10-30T19:52:43Z) - Streaming Sparse Linear Regression [1.8707139489039097]
本稿では,データポイントが逐次到着したときのストリーミングデータを解析する新しいオンライン疎線形回帰フレームワークを提案する。
提案手法はメモリ効率が高く,厳密な制約付き凸性仮定を必要とする。
論文 参考訳(メタデータ) (2022-11-11T07:31:55Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳(メタデータ) (2022-06-29T01:40:38Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - Oblivious sketching for logistic regression [72.42202783677811]
本稿では,ロジスティック回帰のための最初のデータ難読スケッチを示す。
私たちのスケッチは速く、シンプルで、実装も簡単です。
論文 参考訳(メタデータ) (2021-07-14T11:29:26Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Semi-supervised Active Regression [21.51757844385258]
本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。
学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
論文 参考訳(メタデータ) (2021-06-12T03:28:43Z) - Active Covering [37.525977525895605]
我々は,学習者がラベルのないデータセットを与えられ,クエリの事例を逐次ラベル付けできる,アクティブカバーの問題を分析する。
目的は,最少数のラベルクエリにおいて,肯定的な例をすべてラベル付けすることである。
論文 参考訳(メタデータ) (2021-06-04T15:32:39Z) - How to distribute data across tasks for meta-learning? [59.608652082495624]
タスクごとのデータポイントの最適な数は予算に依存しますが、それは大きな予算のためのユニークな一定の値に収束します。
この結果から,データ収集の簡便かつ効率的な手順が示唆された。
論文 参考訳(メタデータ) (2021-03-15T15:38:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。