論文の概要: Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy
- arxiv url: http://arxiv.org/abs/2011.05934v1
- Date: Wed, 11 Nov 2020 17:48:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-26 23:51:36.474293
- Title: Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy
- Title（参考訳）: 微分プライバシーの非対話的局所モデルにおける経験的リスク最小化
- Authors: Di Wang and Marco Gaboardi and Adam Smith and Jinhui Xu
- Abstract要約: 本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
- 参考スコア（独自算出の注目度）: 26.69391745812235
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: In this paper, we study the Empirical Risk Minimization (ERM) problem in the
non-interactive Local Differential Privacy (LDP) model. Previous research on
this problem \citep{smith2017interaction} indicates that the sample complexity,
to achieve error $\alpha$, needs to be exponentially depending on the
dimensionality $p$ for general loss functions. In this paper, we make two
attempts to resolve this issue by investigating conditions on the loss
functions that allow us to remove such a limit. In our first attempt, we show
that if the loss function is $(\infty, T)$-smooth, by using the Bernstein
polynomial approximation we can avoid the exponential dependency in the term of
$\alpha$. We then propose player-efficient algorithms with $1$-bit
communication complexity and $O(1)$ computation cost for each player. The error
bound of these algorithms is asymptotically the same as the original one. With
some additional assumptions, we also give an algorithm which is more efficient
for the server. In our second attempt, we show that for any $1$-Lipschitz
generalized linear convex loss function, there is an $(\epsilon, \delta)$-LDP
algorithm whose sample complexity for achieving error $\alpha$ is only linear
in the dimensionality $p$. Our results use a polynomial of inner product
approximation technique. Finally, motivated by the idea of using polynomial
approximation and based on different types of polynomial approximations, we
propose (efficient) non-interactive locally differentially private algorithms
for learning the set of k-way marginal queries and the set of smooth queries.
- Abstract（参考訳）: 本稿では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
この問題に関する以前の研究は、誤差$\alpha$を達成するためには、一般損失函数の次元$p$に依存する指数関数的な複雑さが必要であることを示唆している。
本稿では,このような制限を解消できる損失関数の条件を調査することにより,この問題を解決する試みを2つ行う。
最初の試みで、損失関数が$(\infty, t)$-smoothである場合、ベルンシュタイン多項式近似を用いることで、$\alpha$という項での指数依存性を避けることができることを示した。
次に,1ビット通信の複雑さと各プレイヤーの計算コストが$O(1)$であるプレーヤ効率のアルゴリズムを提案する。
これらのアルゴリズムの誤差境界は、漸近的に元のものと同じである。
追加の仮定では、サーバに対してより効率的なアルゴリズムも提供します。
第2の試行では、任意の1ドルLipschitz一般化線型凸損失関数に対して、誤差を達成するためのサンプル複雑性が$(\epsilon, \delta)$-LDPアルゴリズムは次元$p$でのみ線型であることを示す。
結果は内積近似手法の多項式を用いる。
最後に, 多項式近似を用いて, 様々な種類の多項式近似に基づいて, k-way境界クエリの集合とスムーズなクエリの集合を学習するための非インタラクティブな局所微分プライベートアルゴリズムを提案する。
関連論文リスト
- Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。
最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文 参考訳（メタデータ） (2025-01-09T18:31:35Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - 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) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。