論文の概要: Efficient Adaptive Data Analysis over Dense Distributions

• arxiv url: http://arxiv.org/abs/2602.07732v1
• Date: Sat, 07 Feb 2026 23:44:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.780923
• Title: Efficient Adaptive Data Analysis over Dense Distributions
• Title（参考訳）: 密度分布を用いた適応データ解析の効率化
• Authors: Joon Suk Huh,
• Abstract要約: 我々は,データ分布が既知値に対して密度が高い場合に,効率的なADA機構が最適な$O(log T)$サンプル複雑性を実現することを示す。 我々のアルゴリズムは差分プライバシーをベースとしていないが、Predicate Singling Out (PSO) と呼ばれる緩やかなプライバシー概念を満足している。
• 参考スコア（独自算出の注目度）: 3.7734715043126488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern data workflows are inherently adaptive, repeatedly querying the same dataset to refine and validate sequential decisions, but such adaptivity can lead to overfitting and invalid statistical inference. Adaptive Data Analysis (ADA) mechanisms address this challenge; however, there is a fundamental tension between computational efficiency and sample complexity. For $T$ rounds of adaptive analysis, computationally efficient algorithms typically incur suboptimal $O(\sqrt{T})$ sample complexity, whereas statistically optimal $O(\log T)$ algorithms are computationally intractable under standard cryptographic assumptions. In this work, we shed light on this trade-off by identifying a natural class of data distributions under which both computational efficiency and optimal sample complexity are achievable. We propose a computationally efficient ADA mechanism that attains optimal $O(\log T)$ sample complexity when the data distribution is dense with respect to a known prior. This setting includes, in particular, feature--label data distributions arising in distribution-specific learning. As a consequence, our mechanism also yields a sample-efficient (i.e., $O(\log T)$ samples) statistical query oracle in the distribution-specific setting. Moreover, although our algorithm is not based on differential privacy, it satisfies a relaxed privacy notion known as Predicate Singling Out (PSO) security (Cohen and Nissim, 2020). Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy.
• Abstract（参考訳）: 現代のデータワークフローは本質的に適応的であり、シーケンシャルな決定を洗練し検証するために同じデータセットを繰り返しクエリするが、そのような適応性は過度に適合し、無効な統計的推論につながる可能性がある。 適応データ分析(ADA)メカニズムはこの課題に対処するが、計算効率とサンプルの複雑さの間には根本的な緊張関係がある。 適応分析の$T$ラウンドの場合、計算効率のよいアルゴリズムは典型的には準最適$O(\sqrt{T})$サンプル複雑性を発生させるが、統計学的に最適な$O(\log T)$アルゴリズムは標準的な暗号的仮定の下で計算的に抽出可能である。 本研究では,計算効率と最適なサンプル複雑性の両方が達成可能なデータ分布の自然なクラスを同定することによって,このトレードオフに光を当てる。 本稿では,データ分布が既知値に対して密度が高い場合に,最適な$O(\log T)$サンプル複雑性を実現するための計算効率の高いADA機構を提案する。 この設定は、特に、分布固有の学習で生じる特徴ラベルデータ分散を含む。 結果として、我々のメカニズムは、分布固有の設定におけるサンプル効率(例えば$O(\log T)$サンプル)の統計的クエリオラクルも生成する。 さらに、我々のアルゴリズムは差分プライバシーに基づくものではないが、Predicate Singling Out(PSO)セキュリティ(Cohen and Nissim, 2020)として知られる緩やかなプライバシー概念を満足している。 以上の結果から,適応型データ分析と,差分プライバシーを超えたプライバシの関係が明らかとなった。

関連論文リスト

• Utility-Diversity Aware Online Batch Selection for LLM Supervised Fine-tuning [49.04912820721943]
  Supervised Fine-tuning (SFT) は計算コストが高く、時にはオーバーフィットやバイアス増幅に悩まされる。 本研究は、トレーニングプロセス中にサンプルを動的にスコア付け、フィルタリングするオンラインバッチ選択ファミリについて研究する。 SFTにおける効率的なオンラインバッチ選択のためのフレームワークである textbfUDS (Utility-Diversity Sampling) を開発した。
  論文  参考訳（メタデータ） (2025-10-19T15:32:01Z)
• Distributionally Robust Optimization with Adversarial Data Contamination [49.89480853499918]
  凸リプシッツ損失関数を持つ一般化線形モデルに対するワッサーシュタイン-1 DRO 目標の最適化に焦点をあてる。 私たちの主な貢献は、データ汚染のトレーニングに対するロバストネスと分散シフトに対するロバストネスを統合した、新しいモデリングフレームワークです。 この研究は、データ汚染と分散シフトという2つの課題の下で学習するために、効率的な計算によって支援される最初の厳密な保証を確立する。
  論文  参考訳（メタデータ） (2025-07-14T18:34:10Z)
• Learning-Based TSP-Solvers Tend to Be Overly Greedy [8.79364699260219]
  本研究では, ランダムに生成した学習型解法の性質を検証するため, 最近傍密度と呼ばれる統計的尺度を構築した。 学習に基づく解法の性能が、そのような拡張データに大きく依存していることを検証する。 要するに、学習ベースのTSPソルバの限界は、過度に欲求的になりがちであり、AIを活用した最適化ソルバに深く影響する可能性がある。
  論文  参考訳（メタデータ） (2025-02-02T12:06:13Z)
• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  大規模データの爆発はシングルマシンシステムの処理能力を上回っている。 分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。 そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-30T13:22:08Z)
• Prompt-Matcher: Leveraging Large Models to Reduce Uncertainty in Schema Matching Results [1.13107643869251]
  本稿では,大規模言語モデルの特定のプロンプトを用いた細粒度対応検証に基づく新しい手法を提案する。 本手法は,(1)対応選択アルゴリズム,(2)対応検証,(3)確率分布の更新の3つの主成分からなる反復ループである。 本稿では,計算効率においてブルートアルゴリズムを著しく上回る新しい$(1-1/e)$-approximationアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-24T16:54:08Z)
• Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them) [14.396431159723297]
  理論上,共形予測はテキスト共同データ分布に拡張可能であることを示す。 最も一般的なケースは計算に実用的でないが、具体的には特定の共形アルゴリズムを導出するための手順を概説する。
  論文  参考訳（メタデータ） (2024-05-10T17:40:24Z)
• On the Performance of Empirical Risk Minimization with Smoothed Data [59.3428024282545]
  経験的リスク最小化(Empirical Risk Minimization、ERM)は、クラスがiidデータで学習可能であれば、サブ線形誤差を達成できる。 We show that ERM can able to achieve sublinear error when a class are learnable with iid data。
  論文  参考訳（メタデータ） (2024-02-22T21:55:41Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。