論文の概要: Strategic PAC Learnability via Geometric Definability
- arxiv url: http://arxiv.org/abs/2605.13426v2
- Date: Thu, 14 May 2026 04:07:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-15 15:19:49.923479
- Title: Strategic PAC Learnability via Geometric Definability
- Title（参考訳）: 幾何学的定義可能性による戦略PAC学習可能性
- Authors: Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich,
- Abstract要約: 戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。
中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。
仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。
難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
- 参考スコア（独自算出の注目度）: 69.34283267701421
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension $1$ on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $\mathbb{R}_{\mathtt{exp}}$. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including $\ell_p$ distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.
- Abstract（参考訳）: 戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。
中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。
以前の研究は、ノルムコストの線形分類器のようないくつかの自然条件において、誘導された複雑さを制御できることを示してきた。
単純な場合でさえ、最も単純な区間近傍でも誘導クラスは無限のVC次元を持つようなVC次元の仮説クラスが実数直線上に存在し、そのような保証は一般に失敗することを示すことから始める。
したがって、戦略的行動は、簡単な学習問題を学習不可能な問題に変えることができる。
これを克服するために、幾何学的定義可能性仮定(英語版)を通して構造を導入する:仮説クラスとコスト誘起近傍関係は、$\mathbb{R}_{\mathtt{exp}}$上の一階式で定義できる。
これは直感的には、算術演算、指数演算、対数、比較を用いて仮説とコストを記述することができることを意味する。
これは、$\ell_p$ 距離、ワッサーシュタイン距離、情報理論の発散など、幅広い自然クラスとコスト関数をキャプチャする。
この仮定の下では、定義公式の複雑さによって、サンプルの複雑さが制御され、学習可能性が維持されることが証明される。
関連論文リスト
- Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。
一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。
一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
論文 参考訳（メタデータ） (2026-02-24T06:15:59Z) - Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。
バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。
ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
論文 参考訳（メタデータ） (2025-11-16T15:47:47Z) - Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
ハーフスペースの交叉学習は計算学習理論における中心的な問題である。
たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。
本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-11-13T00:28:24Z) - Fundamental computational limits of weak learnability in high-dimensional multi-index models [30.501140910531017]
本稿では, 1次反復アルゴリズムを用いて低次元構造を弱めに復元するために必要な最小サンプル複雑性に着目した。
i) 自明な部分空間が任意の$alpha!>!0$; (ii) 自明な部分空間が空であれば、簡単な部分空間の存在に必要な必要十分条件を提供する。
限定的だが興味深い厳密な方向の集合において、-パリティ問題に似て-$alpha_c$が見つかる
論文 参考訳（メタデータ） (2024-05-24T11:59:02Z) - Learnability, Sample Complexity, and Hypothesis Class Complexity for
Regression Models [10.66048003460524]
この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。
提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。
これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
論文 参考訳（メタデータ） (2023-03-28T15:59:12Z) - Comparative Learning: A Sample Complexity Theory for Two Hypothesis
Classes [5.194264506657145]
比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。
たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。
比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
論文 参考訳（メタデータ） (2022-11-16T18:38:24Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。