論文の概要: Monotone Classification with Relative Approximations

• arxiv url: http://arxiv.org/abs/2506.10775v1
• Date: Thu, 12 Jun 2025 14:51:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 15:37:22.79625
• Title: Monotone Classification with Relative Approximations
• Title（参考訳）: 相対近似を用いたモノトン分類
• Authors: Yufei Tao,
• Abstract要約: 単調な分類では、入力は$mathbbRd$の複数セットの$P$であり、それぞれが$-1, 1$の隠れラベルに関連付けられている。 目標は、分類子として機能するモノトン関数 $h$ を、小さなエムエラーで $mathbbRd$ から $-1, 1$ にマッピングすることである。
• 参考スコア（独自算出の注目度）: 4.750077838548594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In monotone classification, the input is a multi-set $P$ of points in $\mathbb{R}^d$, each associated with a hidden label from $\{-1, 1\}$. The goal is to identify a monotone function $h$, which acts as a classifier, mapping from $\mathbb{R}^d$ to $\{-1, 1\}$ with a small {\em error}, measured as the number of points $p \in P$ whose labels differ from the function values $h(p)$. The cost of an algorithm is defined as the number of points having their labels revealed. This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most $(1 + \epsilon) \cdot k^*$ where $\epsilon \ge 0$ and $k^*$ is the minimum error achieved by an optimal monotone classifier -- in other words, the error is allowed to exceed the optimal by at most a relative factor. Nearly matching upper and lower bounds are presented for the full range of $\epsilon$. All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.
• Abstract（参考訳）: 単調な分類では、入力は$\mathbb{R}^d$ の点の多重集合 $P$ であり、それぞれ $\{-1, 1\}$ の隠れラベルに関連付けられる。 目的は、分類子として機能する単調関数 $h$ を $\mathbb{R}^d$ から $\{-1, 1\}$ に小さな誤差でマッピングすることであり、そのラベルが関数値 $h(p)$ と異なる点数 $p \in P$ として測定される。 アルゴリズムのコストは、ラベルが明示された点の数として定義される。 この記事では、最大誤差が 1 + \epsilon) \cdot k^*$ であるモノトン分類器を見つけるのに必要な最小コストに関する最初の研究を、最適なモノトン分類器によって達成される最小誤差である$\epsilon \ge 0$ と $k^*$ で示します。 ほぼ一致する上界と下界は、$\epsilon$の全範囲に対して提示される。 この問題に関するこれまでのすべての研究は、絶対係数によって最適値よりも高い誤差しか達成できない。

関連論文リスト

• Surrogate to Poincaré inequalities on manifolds for dimension reduction in nonlinear feature spaces [49.1574468325115]
  連続微分可能な関数 $u:mathbbRd rightarrow mathbbRm$ を $g:mathbbRd rightarrow mathbbRm$, $mleq d$, $f : mathbbRm rightarrow mathbbRR$ という関数の合成によって近似することを目指している。 固定された$g$に対して、評価を含む古典回帰法を用いて$f$を構築する。
  論文  参考訳（メタデータ） (2025-05-03T12:37:27Z)
• Bandit Multiclass List Classification [28.483435983018616]
  入力例を$K$のラベル集合のサブセットにマッピングする(セミバンドフィードバック)マルチクラスリスト分類の問題について検討する。 この結果は,より単純な単一ラベル設定(Erez et al. '24)における先行作業の一般化と拡張であり,より一般的には$s$スパース報酬を伴う文脈的半帯域問題に適用される。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)
• A Multiclass Classification Approach to Label Ranking [2.6905021039717987]
  マルチクラスの分類において、目標は、$mathcalY=1,; ldots,; K $ with $Kgeq 3$で値を値するランダムラベル$Y$の予測方法を学ぶことである。 本稿では,多クラス分類と後続確率推定の中間点である,この統計的学習問題の解析に焦点をあてる。
  論文  参考訳（メタデータ） (2020-02-21T17:12:43Z)

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

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