Adaptive Data Analysis for Growing Data

• URL: http://arxiv.org/abs/2405.13375v1
• Date: Wed, 22 May 2024 06:17:58 GMT
• Title: Adaptive Data Analysis for Growing Data
• Authors: Neil G. Marchant, Benjamin I. P. Rubinstein,
• Abstract summary: Reuse of data in adaptive poses challenges regarding overfitting and the statistical validity results. We present the first generalization bounds for adaptive analysis in the dynamic data setting.
• Score: 19.68686581348877
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reuse of data in adaptive workflows poses challenges regarding overfitting and the statistical validity of results. Previous work has demonstrated that interacting with data via differentially private algorithms can mitigate overfitting, achieving worst-case generalization guarantees with asymptotically optimal data requirements. However, such past work assumes data is static and cannot accommodate situations where data grows over time. In this paper we address this gap, presenting the first generalization bounds for adaptive analysis in the dynamic data setting. We allow the analyst to adaptively schedule their queries conditioned on the current size of the data, in addition to previous queries and responses. We also incorporate time-varying empirical accuracy bounds and mechanisms, allowing for tighter guarantees as data accumulates. In a batched query setting, the asymptotic data requirements of our bound grows with the square-root of the number of adaptive queries, matching prior works' improvement over data splitting for the static setting. We instantiate our bound for statistical queries with the clipped Gaussian mechanism, where it empirically outperforms baselines composed from static bounds.

Related papers

• Stochastic Gradient Descent with Adaptive Data [4.119418481809095]
  gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The influence of previous decisions on the data generated introduces bias in the gradient estimate, which presents a potential source of instability for online learning not present in the iid case. We show that the convergence speed of SGD with adaptive data is largely similar to the classical iid setting, as long as the mixing time of the policy-induced dynamics is factored in.
  arXiv  Detail & Related papers  (2024-10-02T02:58:32Z)
• Uncertainty Quantification of Data Shapley via Statistical Inference [20.35973700939768]
  The emergence of data markets underscores the growing importance of data valuation. Within the machine learning landscape, Data Shapley stands out as a widely embraced method for data valuation. This paper establishes the relationship between Data Shapley and infinite-order U-statistics.
  arXiv  Detail & Related papers  (2024-07-28T02:54:27Z)
• Geometry-Aware Instrumental Variable Regression [56.16884466478886]
  We propose a transport-based IV estimator that takes into account the geometry of the data manifold through data-derivative information. We provide a simple plug-and-play implementation of our method that performs on par with related estimators in standard settings.
  arXiv  Detail & Related papers  (2024-05-19T17:49:33Z)
• On the Performance of Empirical Risk Minimization with Smoothed Data [59.3428024282545]
  Empirical Risk Minimization (ERM) is able to achieve sublinear error whenever a class is learnable with iid data. We show that ERM is able to achieve sublinear error whenever a class is learnable with iid data.
  arXiv  Detail & Related papers  (2024-02-22T21:55:41Z)
• Adaptive Data Analysis with Correlated Observations [21.969356766737622]
  We show that, in some cases, differential privacy guarantees even when there are dependencies within the sample. We show that the connection between transcript-compression and adaptive data analysis can be extended to the non-iid setting.
  arXiv  Detail & Related papers  (2022-01-21T14:00:30Z)
• Debiasing In-Sample Policy Performance for Small-Data, Large-Scale Optimization [4.554894288663752]
  We propose a novel estimator of the out-of-sample performance of a policy in data-driven optimization. Unlike cross-validation, our approach avoids sacrificing data for a test set. We prove our estimator performs well in the small-data, largescale regime.
  arXiv  Detail & Related papers  (2021-07-26T19:00:51Z)
• FCMI: Feature Correlation based Missing Data Imputation [0.0]
  We propose an efficient technique to impute the missing value in the dataset based on correlation called FCMI. Our proposed algorithm picks the highly correlated attributes of the dataset and uses these attributes to build a regression model. Experiments conducted on both classification and regression datasets show that the proposed imputation technique outperforms existing imputation algorithms.
  arXiv  Detail & Related papers  (2021-06-26T13:35:33Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Multi-Source Causal Inference Using Control Variates [81.57072928775509]
  We propose a general algorithm to estimate causal effects from emphmultiple data sources. We show theoretically that this reduces the variance of the ATE estimate. We apply this framework to inference from observational data under an outcome selection bias.
  arXiv  Detail & Related papers  (2021-03-30T21:20:51Z)
• Time-Series Imputation with Wasserstein Interpolation for Optimal Look-Ahead-Bias and Variance Tradeoff [66.59869239999459]
  In finance, imputation of missing returns may be applied prior to training a portfolio optimization model. There is an inherent trade-off between the look-ahead-bias of using the full data set for imputation and the larger variance in the imputation from using only the training data. We propose a Bayesian posterior consensus distribution which optimally controls the variance and look-ahead-bias trade-off in the imputation.
  arXiv  Detail & Related papers  (2021-02-25T09:05:35Z)
• Identifying Statistical Bias in Dataset Replication [102.92137353938388]
  We study a replication of the ImageNet dataset on which models exhibit a significant (11-14%) drop in accuracy. After correcting for the identified statistical bias, only an estimated $3.6% pm 1.5%$ of the original $11.7% pm 1.0%$ accuracy drop remains unaccounted for.
  arXiv  Detail & Related papers  (2020-05-19T17:48:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.