Tight Lower Bounds and Improved Convergence in Performative Prediction

• URL: http://arxiv.org/abs/2412.03671v1
• Date: Wed, 04 Dec 2024 19:06:19 GMT
• Title: Tight Lower Bounds and Improved Convergence in Performative Prediction
• Authors: Pedram Khorsandi, Rushil Gupta, Mehrnaz Mofakhami, Simon Lacoste-Julien, Gauthier Gidel,
• Abstract summary: We extend the Repeated Risk Minimization (RRM) framework by utilizing historical datasets from previous snapshots. We introduce a new upper bound for methods that use only the final iteration of the dataset. We empirically observe faster convergence to the stable point on various performative prediction benchmarks.
• Score: 29.169972807928
• License:
• Abstract: Performative prediction is a framework accounting for the shift in the data distribution induced by the prediction of a model deployed in the real world. Ensuring rapid convergence to a stable solution where the data distribution remains the same after the model deployment is crucial, especially in evolving environments. This paper extends the Repeated Risk Minimization (RRM) framework by utilizing historical datasets from previous retraining snapshots, yielding a class of algorithms that we call Affine Risk Minimizers and enabling convergence to a performatively stable point for a broader class of problems. We introduce a new upper bound for methods that use only the final iteration of the dataset and prove for the first time the tightness of both this new bound and the previous existing bounds within the same regime. We also prove that utilizing historical datasets can surpass the lower bound for last iterate RRM, and empirically observe faster convergence to the stable point on various performative prediction benchmarks. We offer at the same time the first lower bound analysis for RRM within the class of Affine Risk Minimizers, quantifying the potential improvements in convergence speed that could be achieved with other variants in our framework.

Related papers

• Likelihood-Ratio Regularized Quantile Regression: Adapting Conformal Prediction to High-Dimensional Covariate Shifts [35.16750653336608]
  We introduce the likelihood ratio regularized quantile regression algorithm, which combines the pinball loss with a novel choice of regularization. We show that the LR-QR method has coverage at the desired level in the target domain, up to a small error term. Our experiments demonstrate that the LR-QR algorithm outperforms existing methods on high-dimensional prediction tasks.
  arXiv  Detail & Related papers  (2025-02-18T16:46:44Z)
• Risk and cross validation in ridge regression with correlated samples [72.59731158970894]
  We provide training examples for the in- and out-of-sample risks of ridge regression when the data points have arbitrary correlations. We demonstrate that in this setting, the generalized cross validation estimator (GCV) fails to correctly predict the out-of-sample risk. We further extend our analysis to the case where the test point has nontrivial correlations with the training set, a setting often encountered in time series forecasting.
  arXiv  Detail & Related papers  (2024-08-08T17:27:29Z)
• Consensus-Adaptive RANSAC [104.87576373187426]
  We propose a new RANSAC framework that learns to explore the parameter space by considering the residuals seen so far via a novel attention layer. The attention mechanism operates on a batch of point-to-model residuals, and updates a per-point estimation state to take into account the consensus found through a lightweight one-step transformer.
  arXiv  Detail & Related papers  (2023-07-26T08:25:46Z)
• Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization [52.7137956951533]
  We argue that devising simpler methods for learning predictors on existing features is a promising direction for future research. We introduce Domain-Adjusted Regression (DARE), a convex objective for learning a linear predictor that is provably robust under a new model of distribution shift. Under a natural model, we prove that the DARE solution is the minimax-optimal predictor for a constrained set of test distributions.
  arXiv  Detail & Related papers  (2022-02-14T16:42:16Z)
• RIFLE: Imputation and Robust Inference from Low Order Marginals [10.082738539201804]
  We develop a statistical inference framework for regression and classification in the presence of missing data without imputation. Our framework, RIFLE, estimates low-order moments of the underlying data distribution with corresponding confidence intervals to learn a distributionally robust model. Our experiments demonstrate that RIFLE outperforms other benchmark algorithms when the percentage of missing values is high and/or when the number of data points is relatively small.
  arXiv  Detail & Related papers  (2021-09-01T23:17:30Z)
• 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)
• The Risks of Invariant Risk Minimization [52.7137956951533]
  Invariant Risk Minimization is an objective based on the idea for learning deep, invariant features of data. We present the first analysis of classification under the IRM objective--as well as these recently proposed alternatives--under a fairly natural and general model. We show that IRM can fail catastrophically unless the test data are sufficiently similar to the training distribution--this is precisely the issue that it was intended to solve.
  arXiv  Detail & Related papers  (2020-10-12T14:54:32Z)
• Learning Invariant Representations and Risks for Semi-supervised Domain Adaptation [109.73983088432364]
  We propose the first method that aims to simultaneously learn invariant representations and risks under the setting of semi-supervised domain adaptation (Semi-DA) We introduce the LIRR algorithm for jointly textbfLearning textbfInvariant textbfRepresentations and textbfRisks.
  arXiv  Detail & Related papers  (2020-10-09T15:42:35Z)
• Meta Learning as Bayes Risk Minimization [18.76745359031975]
  We use a probabilistic framework to formalize what it means for two tasks to be related. In our formulation, the BRM optimal solution is given by the predictive distribution computed from the posterior distribution of the task-specific latent variable conditioned on the contextual dataset. We show that our approximation of the posterior distributions converges to the maximum likelihood estimate with the same rate as the true posterior distribution.
  arXiv  Detail & Related papers  (2020-06-02T09:38:00Z)

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.