論文の概要: Privately Learning Decision Lists and a Differentially Private Winnow
- arxiv url: http://arxiv.org/abs/2602.07370v1
- Date: Sat, 07 Feb 2026 05:30:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-10 20:26:24.588337
- Title: Privately Learning Decision Lists and a Differentially Private Winnow
- Title（参考訳）: 個人学習型意思決定リストと差分学習型ウィノウ
- Authors: Mark Bun, William Fang,
- Abstract要約: 我々は、学習決定リストと大域半空間の古典的な問題に対して、新たな微分プライベートアルゴリズムを提案する。
PACモデルでは、最良な非私的アルゴリズムよりも最小限のサンプルオーバーヘッドで決定リストを学習するための計算効率の良いアルゴリズムを提供する。
オンラインモデルでは、類似次元における誤り有界な多対数性を持つハーフスペースを学習し、マージンにおける逆を学習するために、影響力のあるWinnowアルゴリズムのプライベートなアナログを与える。
- 参考スコア（独自算出の注目度）: 6.7839141352275645
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-private algorithms. In the online model, we give a private analog of the influential Winnow algorithm for learning halfspaces with mistake bound polylogarithmic in the dimension and inverse polynomial in the margin. As an application, we describe how to privately learn decision lists in the online model, qualitatively matching state-of-the art non-private guarantees.
- Abstract（参考訳）: 我々は、PACおよびオンラインモデルにおいて、学習決定リストと大きなマージンハーフスペースの古典的な問題に対して、新たな微分プライベートアルゴリズムを提供する。
PACモデルでは、最良な非私的アルゴリズムよりも最小限のサンプルオーバーヘッドで決定リストを学習するための計算効率の良いアルゴリズムを提供する。
オンラインモデルでは、有界なウィノウアルゴリズムのプライベートな類似で、辺辺の次元と逆多項式における誤差有界な多対数性を持つハーフスペースを学習する。
アプリケーションとして、オンラインモデルで意思決定リストをプライベートに学習する方法を述べる。
関連論文リスト
- Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。
提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文 参考訳（メタデータ） (2024-02-24T09:47:46Z) - Private PAC Learning May be Harder than Online Learning [14.180842831990999]
リトルストーン次元の任意の概念クラス$d$は、$mathrmpoly(d)$サンプルを用いてプライベートにPACが学習できることを示す。
これにより、オンライン学習者からプライベートPAC学習者への汎用的な変換が存在するかどうかという自然な疑問が提起される。
論文 参考訳（メタデータ） (2024-02-16T22:44:52Z) - Stochastic Differentially Private and Fair Learning [7.971065005161566]
我々は、収束することが保証されるフェアラーニングのための最初の微分プライベートアルゴリズムを提供する。
われわれのフレームワークは、人口格差や均等化オッズなど、さまざまな公平さを許容できるほど柔軟である。
本アルゴリズムは,複数の(非バイナリ)機密属性を持つ非バイナリ分類タスクに適用可能である。
論文 参考訳（メタデータ） (2022-10-17T06:54:57Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - A Graph Federated Architecture with Privacy Preserving Learning [48.24121036612076]
フェデレーション学習は、複数のエージェントと連携してグローバルモデルを見つける中央プロセッサを含む。
複数のクライアントに接続されたサーバの現在のアーキテクチャは、サーバの通信障害や計算過負荷に非常に敏感です。
暗号と差分プライバシーの概念を使用して、グラフ構造に拡張するフェデレーション学習アルゴリズムを民営化します。
論文 参考訳（メタデータ） (2021-04-26T09:51:24Z) - Learning Differentially Private Mechanisms [13.40946759638048]
特定の非プライベートプログラムの正確で微分的なプライベートバージョンを自動的に学習する手法を提案する。
本手法は, 差分プライバシー文献から基礎的アルゴリズムを学習し, 自然なプログラム合成ベースラインを著しく上回っていることを示す。
論文 参考訳（メタデータ） (2021-01-04T13:33:57Z) - Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms [95.73230376153872]
本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。
我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。
次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
論文 参考訳（メタデータ） (2020-07-18T09:12:03Z) - Efficient, Noise-Tolerant, and Private Learning via Boosting [15.62988331732388]
本研究では,大規模ハーフスペースのための耐雑音性とプライベートなPAC学習者を構築する方法について述べる。
この最初の境界は、プライバシからPAC学習者を取得するための一般的な方法論を示している。
2つ目の境界は、大きな有理半空間の微分プライベート学習において最もよく知られたサンプルの複雑さに適合する標準手法を使用する。
論文 参考訳（メタデータ） (2020-02-04T03:16:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。