論文の概要: On the Sample Complexity of Rank Regression from Pairwise Comparisons

• arxiv url: http://arxiv.org/abs/2105.01463v1
• Date: Tue, 4 May 2021 12:45:53 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-05 15:55:36.726880
• Title: On the Sample Complexity of Rank Regression from Pairwise Comparisons
• Title（参考訳）: 対数比較によるランク回帰のサンプル複雑性について
• Authors: Berkan Kadioglu, Peng Tian, Jennifer Dy, Deniz Erdogmus and Stratis Ioannidis
• Abstract要約: $mathbbRd$の機能を持つ$N$サンプルのデータセットは、$M$ペアワイズ比較を通じてオラクルによってランク付けされる。 学習者は、そのような比較のデータセットを観察し、その特徴からサンプルランクを回復したい。
• 参考スコア（独自算出の注目度）: 18.446233569137668
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a rank regression setting, in which a dataset of $N$ samples with features in $\mathbb{R}^d$ is ranked by an oracle via $M$ pairwise comparisons. Specifically, there exists a latent total ordering of the samples; when presented with a pair of samples, a noisy oracle identifies the one ranked higher with respect to the underlying total ordering. A learner observes a dataset of such comparisons and wishes to regress sample ranks from their features. We show that to learn the model parameters with $\epsilon > 0$ accuracy, it suffices to conduct $M \in \Omega(dN\log^3 N/\epsilon^2)$ comparisons uniformly at random when $N$ is $\Omega(d/\epsilon^2)$.
• Abstract（参考訳）: ランク回帰設定では、$\mathbb{R}^d$の特徴を持つ$N$サンプルのデータセットを、$M$ペアワイズ比較によってオラクルによってランク付けする。 特に、サンプルの潜在総順序は存在し、一対のサンプルを提示すると、ノイズオラクルは、基礎となる全順序に関して上位に位置するものを特定する。 学習者は、そのような比較のデータセットを観察し、その特徴からサンプルランクを回帰したい。 モデルパラメータを$\epsilon > 0$精度で学習するには、$M \in \Omega(dN\log^3 N/\epsilon^2)$の比較をランダムに行うだけで十分である。

関連論文リスト

• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Parallel Sampling via Counting [3.6854430278041264]
  任意の分布からのサンプリングを高速化するために並列化を用いる方法を示す。 我々のアルゴリズムは、$O(n2/3cdot operatornamepolylog(n,q))$ parallel timeである。 この結果は自己回帰モデルにおけるサンプリングに影響を及ぼす。
  論文  参考訳（メタデータ） (2024-08-18T11:42:54Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Testing with Non-identically Distributed Samples [20.74768558932617]
  本研究では,サンプルが独立に分布するが同一に分布しない設定に対して,サブ線形サンプル特性試験と推定が適用範囲について検討する。 それぞれのディストリビューションから$Theta(k/varepsilon2)$サンプルをサンプリングしても、$textbfp_mathrmavg$は、テレビ距離で$textbfp_mathrmavg$をエラー$varepsilon$内で学習するのに十分である。
  論文  参考訳（メタデータ） (2023-11-19T01:25:50Z)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• Robust Testing in High-Dimensional Sparse Models [0.0]
  2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。 回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
  論文  参考訳（メタデータ） (2022-05-16T07:47:22Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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