論文の概要: Subset-Based Instance Optimality in Private Estimation
- arxiv url: http://arxiv.org/abs/2303.01262v1
- Date: Wed, 1 Mar 2023 18:49:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 14:10:23.000342
- Title: Subset-Based Instance Optimality in Private Estimation
- Title（参考訳）: プライベート推定におけるサブセットベースインスタンス最適性
- Authors: Travis Dick, Alex Kulesza, Ziteng Sun, Ananda Theertha Suresh
- Abstract要約: 我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。
提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
- 参考スコア（独自算出の注目度）: 30.786484920552507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new definition of instance optimality for differentially private
estimation algorithms. Our definition requires an optimal algorithm to compete,
simultaneously for every dataset $D$, with the best private benchmark algorithm
that (a) knows $D$ in advance and (b) is evaluated by its worst-case
performance on large subsets of $D$. That is, the benchmark algorithm need not
perform well when potentially extreme points are added to $D$; it only has to
handle the removal of a small number of real data points that already exist.
This makes our benchmark significantly stronger than those proposed in prior
work. We nevertheless show, for real-valued datasets, how to construct private
algorithms that achieve our notion of instance optimality when estimating a
broad class of dataset properties, including means, quantiles, and
$\ell_p$-norm minimizers. For means in particular, we provide a detailed
analysis and show that our algorithm simultaneously matches or exceeds the
asymptotic performance of existing algorithms under a range of distributional
assumptions.
- Abstract（参考訳）: 微分プライベート推定アルゴリズムのインスタンス最適性の新たな定義を提案する。
私たちの定義では、各データセットの$d$と最高のプライベートベンチマークアルゴリズムを同時に競うために最適なアルゴリズムが必要です。
(a)事前にD$を知っており、
(b) は$d$ の大きなサブセットで最悪の場合の性能によって評価される。
つまり、ベンチマークアルゴリズムは、潜在的に極端なポイントが$d$に追加された場合、うまく機能しない。
これによってベンチマークは、以前の作業で提案されていたものよりも大幅に強化されました。
それにもかかわらず、実際の評価されたデータセットに対して、手段、量子化、および$\ell_p$-norm最小化を含む幅広いデータセット特性のクラスを推定する際に、インスタンス最適性の概念を達成するプライベートアルゴリズムを構築する方法を示す。
特に,詳細な解析を行い,分布的仮定の下で既存のアルゴリズムの漸近的性能を同時に満たしているか,あるいは超えていることを示す。
関連論文リスト
- Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex
Optimization [4.608510640547952]
我々は、Dy Searchのほぼ最適最適化誤差を保証する。
誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
論文 参考訳（メタデータ） (2022-08-13T19:57:04Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳（メタデータ） (2021-08-11T20:21:30Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。
提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文 参考訳（メタデータ） (2021-04-14T19:21:59Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。