論文の概要: Learning Half-Spaces from Perturbed Contrastive Examples

• arxiv url: http://arxiv.org/abs/2602.02080v1
• Date: Mon, 02 Feb 2026 13:27:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.164991
• Title: Learning Half-Spaces from Perturbed Contrastive Examples
• Title（参考訳）: 摂動型コントラスト例からハーフスペースを学習する
• Authors: Aryan Alavi Razavi Ravari, Farnam Mansouri, Yuxin Chen, Valentio Iverson, Adish Singla, Sandra Zilles,
• Abstract要約: マンスーリらが導入した2段階のコントラスト学習の事例を考察した。 我々は,非遅延雑音関数$f$でパラメータ化されたメカニズムを解析し,この理想的なコントラスト例を摂動する。 F$の条件下では、対照的な例の存在は、クエリの複雑さの観点から学習をスピードアップさせる。
• 参考スコア（独自算出の注目度）: 26.103944279495654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study learning under a two-step contrastive example oracle, as introduced by Mansouri et. al. (2025), where each queried (or sampled) labeled example is paired with an additional contrastive example of opposite label. While Mansouri et al. assume an idealized setting, where the contrastive example is at minimum distance of the originally queried/sampled point, we introduce and analyze a mechanism, parameterized by a non-decreasing noise function $f$, under which this ideal contrastive example is perturbed. The amount of perturbation is controlled by $f(d)$, where $d$ is the distance of the queried/sampled point to the decision boundary. Intuitively, this results in higher-quality contrastive examples for points closer to the decision boundary. We study this model in two settings: (i) when the maximum perturbation magnitude is fixed, and (ii) when it is stochastic. For one-dimensional thresholds and for half-spaces under the uniform distribution on a bounded domain, we characterize active and passive contrastive sample complexity in dependence on the function $f$. We show that, under certain conditions on $f$, the presence of contrastive examples speeds up learning in terms of asymptotic query complexity and asymptotic expected query complexity.
• Abstract（参考訳）: We study study under a two-step contrastive example oracle, as as Mansouri et al (2025), where each queried ( or sampled) labeled example is paired with an additional contrastive example of other label。 マンスーリらは、コントラスト的な例が元々のクエリされた/サンプリングされた点の最小距離にある理想化された設定を仮定する一方で、この理想的なコントラスト的な例が摂動する非減少雑音関数$f$でパラメータ化されたメカニズムを導入・分析する。 摂動の量は$f(d)$で制御され、$d$はクエリされた/サンプリングされたポイントから決定境界までの距離である。 直感的には、これは決定境界に近い点に対する高品質な対照的な例をもたらす。 このモデルを2つの設定で研究する。 一 最大摂動等級が固定されたとき、 (二)確率的であるとき。 一次元のしきい値と有界領域上の一様分布下の半空間に対して、関数の$f$に依存する能動的かつパッシブなサンプル複雑性を特徴付ける。 F$の条件下では、対照的な例の存在は、漸近的なクエリの複雑さと漸近的なクエリの複雑さの観点から学習をスピードアップさせる。

関連論文リスト

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
  差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。 $n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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