論文の概要: Privately Estimating Monotone Statistics in Polynomial Time
- arxiv url: http://arxiv.org/abs/2605.27912v2
- Date: Thu, 28 May 2026 20:19:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-01 13:54:21.00106
- Title: Privately Estimating Monotone Statistics in Polynomial Time
- Title（参考訳）: ポリノミアル時間におけるモノトン統計のプライベート推定
- Authors: Gavin Brown, Ephraim Linder, Mahbod Majid, Vikrant Singhal,
- Abstract要約: 単調な統計量の推定に有効な差分法アルゴリズムについて検討する。
我々のアルゴリズムはサンプルの複雑さで$t$を節約し、実行時に$et$を支払う。
応用として、プライベート固有値推定、プライベート損失推定、高次元モデルの単一パラメータのプライベート推定の改善結果を得る。
- 参考スコア（独自算出の注目度）: 5.457331995994299
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting point for our investigation is subsample-and-aggregate: a classical paradigm that partitions the dataset into blocks, estimates the statistic on each block, and then privately aggregates the estimates. While practical and generically applicable, this approach is quite data-hungry. We improve upon this framework for the class of monotone statistics -- compared to subsample-and-aggregate, our algorithms save a factor of $t$ in sample complexity and pay a factor of $e^t$ in running time, where $t>0$ is a tunable parameter. We complement our results with a query-complexity lower bound, showing that our algorithms are essentially optimal for this task. As an application, we obtain improved results for private eigenvalue estimation, private loss estimation, and privately estimating a single parameter of a high-dimensional model, e.g., in linear regression.
- Abstract（参考訳）: 単調な統計量,すなわち単調な統計量を新しい観測法で推定するための効率的な微分プライベートアルゴリズムについて検討した。
データセットをブロックに分割し、各ブロックの統計を推定し、それからプライベートに見積を集約する古典的なパラダイムです。
実用的で汎用的に適用できるが、このアプローチは非常にデータ不足である。
サブサンプルとアグリゲートと比較して、我々のアルゴリズムはサンプルの複雑さにおいて$t$の係数を節約し、実行時に$e^t$の係数を支払う。
我々のアルゴリズムが本質的にこのタスクに最適であることを示すため、クエリ・複雑さの低いバウンダリで結果を補完する。
応用として, プライベート固有値推定, プライベート損失推定, および高次元モデルの1つのパラメータ, eg を線形回帰でプライベートに推定するための改良された結果を得る。
関連論文リスト
- High-dimensional estimation with missing data: Statistical and computational limits [13.480462575790334]
我々は,観測結果が欠落したデータである場合の集団パラメータの計算効率を考察する。
平均$ell$法則で推定すると、常に汚染される$in (0, 1)$, (大まかに)$n gtrsim d e1/2$のサンプルは必要となる。
観測結果の欠如により線形回帰に転換し、そのようなギャップが持続しないことを示す。
論文 参考訳（メタデータ） (2026-03-17T16:02:41Z) - Efficient Covariance Estimation for Sparsified Functional Data [51.69796254617083]
共分散関数のランダムノット(ランダムノット-空間)とB-スプライン(Bspline-Spatial)推定器は計算的に効率的である。
共分散の漸近的なポイントワイドは、ある規則性条件下でのスパース化された個々の軌跡に対して得られる。
論文 参考訳（メタデータ） (2025-11-23T00:50:33Z) - Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。
アルゴリズムは任意の外れ値の小さな部分に対して頑健であり、外れ値の小さな部分の関数として最適誤差率を達成する。
論文 参考訳（メタデータ） (2025-03-31T17:08:12Z) - Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。
最適率を達成するための情報重み付け回帰手法を提案する。
特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
論文 参考訳（メタデータ） (2025-02-18T18:35:24Z) - Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares [38.478776450327125]
通常の最小二乗に対するサンプルと時間効率の微分プライベートアルゴリズムを提案する。
私たちのほぼ最適精度は、条件番号または指数時間を持つデータセットに対して保持します。
論文 参考訳（メタデータ） (2024-04-23T18:00:38Z) - Robust Algorithms for GMM Estimation: A Finite Sample Viewpoint [30.839245814393724]
モーメントの一般化法(GMM)
我々はGMM推定器を開発し、一定の$ell$リカバリ保証を$O(sqrtepsilon)$で許容する。
我々のアルゴリズムと仮定は、機器変数の線形回帰とロジスティック回帰に適用できる。
論文 参考訳（メタデータ） (2021-10-06T21:06:22Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳（メタデータ） (2020-10-21T13:43:48Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。