論文の概要: Adversarially Robust Distributed Count Tracking via Partial Differential
Privacy
- arxiv url: http://arxiv.org/abs/2311.00346v1
- Date: Wed, 1 Nov 2023 07:42:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 14:35:52.417191
- Title: Adversarially Robust Distributed Count Tracking via Partial Differential
Privacy
- Title（参考訳）: 部分差分プライバシによる逆ロバスト分散カウントトラッキング
- Authors: Zhongzheng Xiong, Xiaoyi Zhu, Zengfeng Huang
- Abstract要約: 分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。
このモデルは、各アイテムのストリームを受け取り、中央サーバと通信する、$k$のサイトを含む。
カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの通信に$sqrtk$ギャップがあることが知られている。
- 参考スコア（独自算出の注目度）: 17.43748116766233
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the distributed tracking model, also known as distributed functional
monitoring. This model involves $k$ sites each receiving a stream of items and
communicating with the central server. The server's task is to track a function
of all items received thus far continuously, with minimum communication cost.
For count tracking, it is known that there is a $\sqrt{k}$ gap in communication
between deterministic and randomized algorithms. However, existing randomized
algorithms assume an "oblivious adversary" who constructs the entire input
streams before the algorithm starts. Here we consider adaptive adversaries who
can choose new items based on previous answers from the algorithm.
Deterministic algorithms are trivially robust to adaptive adversaries, while
randomized ones may not. Therefore, we investigate whether the $\sqrt{k}$
advantage of randomized algorithms is from randomness itself or the oblivious
adversary assumption. We provide an affirmative answer to this question by
giving a robust algorithm with optimal communication. Existing robustification
techniques do not yield optimal bounds due to the inherent challenges of the
distributed nature of the problem. To address this, we extend the differential
privacy framework by introducing "partial differential privacy" and proving a
new generalization theorem. This theorem may have broader applications beyond
robust count tracking, making it of independent interest.
- Abstract（参考訳）: 分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。
このモデルは、各アイテムのストリームを受信し、中央サーバと通信する$k$サイトを含む。
サーバのタスクは、これまで受け取った全てのアイテムの機能を最小限の通信コストで追跡することである。
カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの間の通信に$\sqrt{k}$ギャップがあることが知られている。
しかし、既存のランダム化アルゴリズムは、アルゴリズムの開始前に入力ストリーム全体を構築する「未知の敵」を仮定する。
ここでは,アルゴリズムのこれまでの回答に基づいて新しい項目を選択できる適応的敵を考える。
決定論的アルゴリズムは適応的な敵に対して自明に堅牢であるが、ランダム化されたアルゴリズムはそうでないかもしれない。
そこで,ランダム化アルゴリズムの$\sqrt{k}$の利点が,ランダム性そのものか,あるいは不明瞭な敵意の仮定かを検討する。
最適な通信を行う頑健なアルゴリズムを提供することにより,この問題に対する肯定的な回答を提供する。
既存のロバスト化技術は、問題の分散した性質の固有の課題のために最適な境界を導き出さない。
そこで我々は,「偏微分プライバシー」を導入し,新たな一般化定理を証明し,差分プライバシーの枠組みを拡張した。
この定理は、ロバストなカウントトラッキングを超えた幅広い応用が可能であり、独立した関心を持つ。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳（メタデータ） (2024-02-12T03:31:34Z) - Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳（メタデータ） (2024-01-04T00:57:33Z) - Private Networked Federated Learning for Nonsmooth Objectives [7.278228169713637]
本稿では,非平滑な目的関数を解くためのネットワーク型フェデレーション学習アルゴリズムを提案する。
参加者の秘密性を保証するため、ゼロ集中型微分プライバシー概念(zCDP)を用いる。
プライバシ保証とアルゴリズムの正確な解への収束の完全な理論的証明を提供する。
論文 参考訳（メタデータ） (2023-06-24T16:13:28Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。
我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-16T00:10:35Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。
ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。
また、Impagliazzoのハードコアの改良版も証明した。
論文 参考訳（メタデータ） (2020-02-25T11:46:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。