論文の概要: 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)$の比較をランダムに行うだけで十分である。
関連論文リスト
- 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) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24: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) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文 参考訳(メタデータ) (2020-10-07T01:43:07Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳(メタデータ) (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。