論文の概要: Differential privacy and Sublinear time are incompatible sometimes
- arxiv url: http://arxiv.org/abs/2407.07262v1
- Date: Tue, 9 Jul 2024 22:33:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-11 18:31:06.378903
- Title: Differential privacy and Sublinear time are incompatible sometimes
- Title（参考訳）: 差分プライバシーとサブリニア時間は時として相容れない
- Authors: Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, Tamalika Mukherjee,
- Abstract要約: 片方向境界に基づく単純な問題は、差分プライベートアルゴリズムとサブ線形時間アルゴリズムの両方をもたらすことを示す。
我々は、微分プライベートである厳密な'サブ線形時間アルゴリズムを認めない。
- 参考スコア（独自算出の注目度）: 12.776401866635844
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differentially private sublinear algorithms for many problems including graph parameter estimation and clustering, little is known regarding hardness results on these algorithms. In this paper, we initiate the study of lower bounds for problems that aim for both differentially-private and sublinear-time algorithms. Our main result is the incompatibility of both the desiderata in the general case. In particular, we prove that a simple problem based on one-way marginals yields both a differentially-private algorithm, as well as a sublinear-time algorithm, but does not admit a ``strictly'' sublinear-time algorithm that is also differentially private.
- Abstract（参考訳）: 差分プライバシーとサブリニアアルゴリズムは、ビッグデータ分析の時代に急速に進化するアルゴリズムのテーマである。
近年の研究では、グラフパラメータ推定やクラスタリングを含む多くの問題に対して、微分プライベートなサブ線形アルゴリズムが存在することが示されているが、これらのアルゴリズムの硬さについてはほとんど分かっていない。
本稿では,差分プライベートアルゴリズムとサブ線形時間アルゴリズムの両方を対象とする問題に対する下位境界の研究を開始する。
我々の主な成果は、一般的な場合のデシダラタの相容れないことである。
特に,一方向境界に基づく単純な問題は,差分プライベートなアルゴリズムとサブ線形時間アルゴリズムの両方をもたらすが,差分プライベートな ` `strictly'' のサブ線形時間アルゴリズムは認めない。
関連論文リスト
- Making Old Things New: A Unified Algorithm for Differentially Private Clustering [6.320600791108065]
20年前のアルゴリズムは、いずれのモデルでも、わずかに修正可能であることを示す。
これは統一された図を提供する: ほとんどすべての既知結果とマッチングする一方で、いくつかの改善を可能にします。
論文 参考訳（メタデータ） (2024-06-17T15:31:53Z) - 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) - Differentially Private Clustering via Maximum Coverage [7.059472280274009]
我々は、個々のデータのプライバシーを維持しながら、計量空間におけるクラスタリングの問題を研究する。
一定の乗法誤差と低い加算誤差を持つ差分アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-27T22:11:18Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms [95.73230376153872]
本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。
我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。
次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
論文 参考訳（メタデータ） (2020-07-18T09:12:03Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳（メタデータ） (2020-06-16T10:49:27Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Differentially Private k-Means Clustering with Guaranteed Convergence [5.335316436366718]
反復的なクラスタリングアルゴリズムは、データの背後にある洞察を学習するのに役立ちます。
敵は、背景知識によって個人のプライバシーを推測することができる。
このような推論攻撃に対して個人のプライバシを保護するため、反復クラスタリングアルゴリズムの差分プライバシー(DP)を広く研究している。
論文 参考訳（メタデータ） (2020-02-03T22:53:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。