論文の概要: New Lower Bounds for Private PAC Learning

• arxiv url: http://arxiv.org/abs/2610.41980v1
• Date: Fri, 30 Oct 2026 16:28:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.809017
• Title: New Lower Bounds for Private PAC Learning
• Title（参考訳）: プライベートPAC学習のための新しい下界
• Abstract要約: 我々は、近似微分プライバシーの下で実現可能なPAC学習を研究し、サンプルの複雑さの低い境界を証明するためのフレームワークを提供する。 同一のVCとLittlestone次元を持つクラスを構築するが、共通のプライバシーと精度パラメータで異なるプライベートサンプルの複雑さを持つ。 また、製品クラス、より一般的には、同じクラスが$mathcalH$にまとめられ、そのドメインをカバーする場合、ICPは、対数因子まで、プライベートなPACサンプルの複雑さを特徴付けます。
• 参考スコア（独自算出の注目度）: 16.60783483597989
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in $\mathcal{G}$ that can be packed independently into a class $\mathcal{H}$, and prove that every $(\varepsilon, δ)$-DP, $(α, β)$-PAC learner for $\mathcal{H}$, possibly improper, uses $Ω\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(α\varepsilon)\right)$ examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into $\mathcal{H}$ and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.
• Abstract（参考訳）: 我々は、近似微分プライバシーの下で実現可能なPAC学習を研究し、サンプルの複雑さの低い境界を証明するためのフレームワークを提供する。 同一のVC次元とLittlestone次元を持つクラスを構築するが、共通プライバシーと精度パラメータで異なるプライベートサンプル複雑度を持つクラスを構築し、これらの次元が不適切な学習者であってもサンプル複雑度を決定できないことを示す。 これを解決するために、Independent Class Packing (ICP)パラメータを導入し、$\mathcal{G}$のクラスを独立して$\mathcal{H}$に詰め込むことができ、すべての$(\varepsilon, δ)$-DP, $(α, β)$-PAC learner for $\mathcal{H}$、おそらく不適切な場合には$Ω\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(α\varepsilon)\right)$例を証明します。 この枠組みを用いて、軸方向の矩形に対する厳密な下界、間隔と線型部分空間の和、半空間と凸多角形に対する下界の改善を証明した。 最後に、製品クラス、そしてより一般的には、同じクラスが$\mathcal{H}$にまとめられ、ターゲットラベルを直接使用できるようにそのドメインをカバーするとき、ICPは、対数要素までプライベートなPACサンプルの複雑さを特徴づける。

関連論文リスト

• Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness [0.0]
  本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。 決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
  論文  参考訳（メタデータ） (2026-10-18T05:17:14Z)
• PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting [46.089126569274676]
  本研究では,マルチクラスPAC学習における帯域幅フィードバックによる課題について検討する。 このフレームワークでは、インスタンススペース$mathcalX$とラベルスペース$mathcalY$に未知のデータ分散があります。 我々は、この問題の最適サンプルの一般的な特徴を与え、すべての概念クラスを複雑さまで鋭くする。
  論文  参考訳（メタデータ） (2026-05-25T10:35:16Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms [10.66048003460524]
  構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
  論文  参考訳（メタデータ） (2021-02-11T21:28:55Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
  適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。 双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
  論文  参考訳（メタデータ） (2020-05-24T18:11:57Z)
• Private Query Release Assisted by Public Data [96.6174729958211]
  本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
  論文  参考訳（メタデータ） (2020-04-23T02:46:37Z)

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

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