論文の概要: An \tilde{O}ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

• arxiv url: http://arxiv.org/abs/2505.06581v1
• Date: Sat, 10 May 2025 09:51:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-13 20:21:48.925514
• Title: An \tilde{O}ptimal Differentially Private Learner for Concept Classes with VC Dimension 1
• Title（参考訳）: VC次元を持つ概念クラスのための最適個人学習者
• Authors: Chao Yan,
• Abstract要約: 本稿では,VC次元1とLittlestone次元が$d$の任意の概念クラスに対して,ほぼ最適にプライベートなPAC学習器を初めて提示する。 我々のアルゴリズムは、$tildeO_varepsilon,delta,alpha,delta(log* d)$のサンプル複雑さを、Alonらによって証明された$Omega(log* d)$の下位境界にほぼ一致する。 我々の研究に先立ち、最もよく知られている上限は一般的なVCクラスに対して$tildeO(VCcdot d5)$である。
• 参考スコア（独自算出の注目度）: 4.834749573193387
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension $d$. Our algorithm achieves the sample complexity of $\tilde{O}_{\varepsilon,\delta,\alpha,\delta}(\log^* d)$, nearly matching the lower bound of $\Omega(\log^* d)$ proved by Alon et al. [STOC19]. Prior to our work, the best known upper bound is $\tilde{O}(VC\cdot d^5)$ for general VC classes, as shown by Ghazi et al. [STOC21].
• Abstract（参考訳）: 本稿では,VC次元 1 とLittlestone 次元 $d$ の任意の概念クラスに対して,ほぼ最適な偏微分プライベート PAC 学習器を提案する。 我々のアルゴリズムは、$\tilde{O}_{\varepsilon,\delta,\alpha,\delta}(\log^* d)$のサンプル複雑性を達成し、Alonらによって証明された$\Omega(\log^* d)$の下位境界にほぼ一致する。 我々の研究に先立ち、最もよく知られている上限は Ghazi et al [STOC21] で示されているように、一般的な VC クラスに対して $\tilde{O}(VC\cdot d^5)$ である。

関連論文リスト

• Lower Bounds for Greedy Teaching Set Constructions [12.186950360560145]
  我々は、小さな$k$に対してgreedyアルゴリズムの性能の低いバウンダリを証明した。 ほとんどの場合、我々の下界は小さな定数$c>0$に対して$k le lceil c d rceil$まで伸びる。
  論文  参考訳（メタデータ） (2025-05-06T06:30:01Z)
• 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)
• The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
  マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。 本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
  論文  参考訳（メタデータ） (2023-07-22T18:02:53Z)
• \~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization [23.547605262139957]
  しきい値関数の学習問題は、機械学習の基本的な問題である。 Kaplan et al による $tildeO(log* |X|)1.5) のほぼタイトな上界を提供する。 また、プライベート準凹の加法誤差(関連するより一般的な問題)に対して$tildeTheta(2log*|X|)$の上限と下限のマッチングも提供する。
  論文  参考訳（メタデータ） (2022-11-11T18:16:46Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• 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)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)
• Closure Properties for Private Classification and Online Prediction [31.115241685486392]
  オンライン学習とプライベートPAC学習のための閉鎖特性を導出する。 実現可能な場合において、関数のクラスを学習する任意のプライベートアルゴリズムは、その場合のクラスを学習するプライベートアルゴリズムに変換可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-10T02:34:16Z)

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

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