Fugu-MT 論文翻訳(概要): The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model

論文の概要: The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model

arxiv url: http://arxiv.org/abs/2103.15690v1
Date: Mon, 29 Mar 2021 15:26:02 GMT
ステータス: 処理完了
システム内更新日: 2021-03-30 19:36:53.979762
Title: The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model
Title（参考訳）: ロバストシャッフルモデルにおける分布自由パリティ学習のサンプル複雑性
Authors: Kobbi Nissim and Chao Yan
Abstract要約: 我々は$d$-bitパリティ関数の学習のサンプル複雑さが$Omega (2d/2)$であることを示した。また、単純なシャッフルモデルプロトコルをスケッチし、その結果が$poly(d)$ factorにきついことを示す。
参考スコア（独自算出の注目度）: 11.821892196198457
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We provide a lowerbound on the sample complexity of distribution-free parity learning in the realizable case in the shuffle model of differential privacy. Namely, we show that the sample complexity of learning $d$-bit parity functions is $\Omega(2^{d/2})$. Our result extends a recent similar lowerbound on the sample complexity of private agnostic learning of parity functions in the shuffle model by Cheu and Ullman. We also sketch a simple shuffle model protocol demonstrating that our results are tight up to $poly(d)$ factors.
Abstract（参考訳）: 微分プライバシーのシャッフルモデルにおいて実現可能な場合において,分布自由パリティ学習のサンプル複雑性を低く評価する。すなわち、$d$-bitパリティ関数を学習する際のサンプルの複雑さは$\Omega(2^{d/2})$である。その結果、cheu と ullman によるシャッフルモデルにおけるパリティ関数のプライベート非依存学習のサンプル複雑性について、最近の類似した下限が拡張された。また、単純なシャッフルモデルプロトコルをスケッチし、その結果が$poly(d)$ factorにきついことを示す。

関連論文リスト

Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文参考訳（メタデータ） (2024-05-10T09:58:47Z)
Transductive Learning Is Compact [10.168670899305232]
一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。我々は、無知の場合においてより大きなギャップが可能であると推測する。
論文参考訳（メタデータ） (2024-02-15T23:10:45Z)
The sample complexity of multi-distribution learning [17.45683822446751]
サンプル複雑性$widetildeO((d+k)epsilon-2) cdot (k/epsilon)o(1)$は、Awasthi, Haghtalab, Zhao の COLT 2023 開放問題を解く。
論文参考訳（メタデータ） (2023-12-07T03:53:17Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文参考訳（メタデータ） (2023-02-26T01:15:32Z)
On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文参考訳（メタデータ） (2022-10-22T19:07:26Z)
Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文参考訳（メタデータ） (2022-05-12T14:40:18Z)
Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
論文参考訳（メタデータ） (2021-07-12T17:00:59Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。当社のメソッドは、最大50,000ドルという問題でテストしています。
論文参考訳（メタデータ） (2020-06-15T21:55:34Z)

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