Conformal Predictions under Markovian Data

• URL: http://arxiv.org/abs/2407.15277v1
• Date: Sun, 21 Jul 2024 22:01:09 GMT
• Title: Conformal Predictions under Markovian Data
• Abstract summary: We study the split Conformal Prediction method when applied to Markovian data. We quantify the gap in terms of coverage induced by the correlations in the data. We present $K$-split CP, a method that adapts to the mixing properties of the chain.
• Score: 50.24983453990065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the split Conformal Prediction method when applied to Markovian data. We quantify the gap in terms of coverage induced by the correlations in the data (compared to exchangeable data). This gap strongly depends on the mixing properties of the underlying Markov chain, and we prove that it typically scales as $\sqrt{t_\mathrm{mix}\ln(n)/n}$ (where $t_\mathrm{mix}$ is the mixing time of the chain). We also derive upper bounds on the impact of the correlations on the size of the prediction set. Finally we present $K$-split CP, a method that consists in thinning the calibration dataset and that adapts to the mixing properties of the chain. Its coverage gap is reduced to $t_\mathrm{mix}/(n\ln(n))$ without really affecting the size of the prediction set. We finally test our algorithms on synthetic and real-world datasets.

Related papers

• How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL [8.929322780616545]
  An unbounded gap between the update maps can coexist with vanishing predictive KL for every fixed finite $Kge2$ in a stationary symmetric Gaussian HMM.<n>The construction is fixed in $K$ and does not provide a universal criterion for when compression is harmless or characterize when internal gaps must incur task loss.
  arXiv  Detail & Related papers  (2026-09-10T06:22:53Z)
• Reducing cross-sample prediction churn in scientific machine learning [0.155963096715749]
  Cross-sample prediction deserves a column alongside predictive performance in scientific-ML benchmark reports, because without it the parameter-side and data-side methods are indistinguishable on the metric they actually differ on.
  arXiv  Detail & Related papers  (2026-05-13T17:50:57Z)
• Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence [6.908972852063454]
  Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners.<n>We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting.<n>Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions.
  arXiv  Detail & Related papers  (2026-04-15T02:32:30Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Phase-space entropy at acquisition reflects downstream learnability [54.4100065023873]
  We propose an acquisition-level scalar $S_mathcal B$ based on instrument-resolved phase space.<n>We show theoretically that (S_mathcal B) correctly identifies the phase-space coherence of periodic sampling.<n>$|S_mathcal B|$ consistently ranks sampling geometries and predicts downstream reconstruction/recognition difficulty emphwithout training.
  arXiv  Detail & Related papers  (2025-12-22T10:03:51Z)
• Non-Asymptotic Analysis of Efficiency in Conformalized Regression [17.873283539065387]
  We establish non-asymptotic bounds on the deviation of the prediction set length from the oracle interval length for conformalized quantile and median regression trained via SGD.<n>The results identify phase transitions in convergence rates across different regimes of $alpha$, offering guidance for allocating data to control excess prediction set length.
  arXiv  Detail & Related papers  (2025-10-08T14:50:35Z)
• Anchor-MoE: A Mean-Anchored Mixture of Experts For Probabilistic Regression [0.0]
  We present an Anchored Mixture of Experts (Anchor-MoE) model that handles both probabilistic and point regression.<n>We show that Anchor-MoE attains the minimax-optimal $L2$ risk rate.<n>It consistently matches or surpasses the strong NG baseline in RMSE and NLL.
  arXiv  Detail & Related papers  (2025-08-22T21:12:41Z)
• Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression [0.0]
  We provide non-asymptotic bounds on the associated mixing times on Gibbs samplers for log-concave targets.<n>The bounds depend explicitly on the design matrix and the prior precision, while they hold uniformly over the vector of responses.<n>An empirical analysis based on coupling techniques suggests that the bounds are effective in predicting practically observed behaviours.
  arXiv  Detail & Related papers  (2025-05-20T13:29:01Z)
• Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization [19.261178173399784]
  Learning models have been shown to rely on spurious correlations between non-predictive features and the associated labels in the training data. We quantify the amount of spurious correlations $C$ learned via linear regression, in terms of the data covariance and the strength $lambda$ of the ridge regularization.
  arXiv  Detail & Related papers  (2025-02-03T13:38:42Z)
• Semiparametric conformal prediction [79.6147286161434]
  We construct a conformal prediction set accounting for the joint correlation structure of the vector-valued non-conformity scores. We flexibly estimate the joint cumulative distribution function (CDF) of the scores. Our method yields desired coverage and competitive efficiency on a range of real-world regression problems.
  arXiv  Detail & Related papers  (2024-11-04T14:29:02Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• 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)
• On Rate-Optimal Partitioning Classification from Observable and from Privatised Data [0.0]
  We revisit the classical method of partitioning classification and study its convergence rate under relaxed conditions. The privacy constraints mean that the data $(X_i$), dots,(X_n,Y_n)$ cannot be directly observed. We add Laplace distributed noises to the discontinuations of all possible locations of the feature vector $X_i$ and to its label $Y_i$.
  arXiv  Detail & Related papers  (2023-12-22T18:07:18Z)
• Tailoring Mixup to Data for Calibration [12.050401897136501]
  Mixup is a technique for improving calibration and predictive uncertainty. In this work, we argue that the likelihood of manifold intrusion increases with the distance between data to mix. We propose to dynamically change the underlying distributions of coefficients depending on the similarity between samples to mix.
  arXiv  Detail & Related papers  (2023-11-02T17:48:28Z)
• Compressed and distributed least-squares regression: convergence rates with applications to Federated Learning [9.31522898261934]
  We investigate the impact of compression on gradient algorithms for machine learning. We highlight differences in terms of convergence rates between several unbiased compression operators. We extend our results to the case of federated learning.
  arXiv  Detail & Related papers  (2023-08-02T18:02:00Z)
• DenseHybrid: Hybrid Anomaly Detection for Dense Open-set Recognition [1.278093617645299]
  Anomaly detection can be conceived either through generative modelling of regular training data or by discriminating with respect to negative training data. This paper presents a novel hybrid anomaly score which allows dense open-set recognition on large natural images. Experiments evaluate our contributions on standard dense anomaly detection benchmarks as well as in terms of open-mIoU - a novel metric for dense open-set performance.
  arXiv  Detail & Related papers  (2022-07-06T11:48:50Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  This paper tackles the problem of missing data imputation for noisy and non-Gaussian data. A new EM algorithm is investigated for mixtures of elliptical distributions with the property of handling potential missing data. Experimental results on synthetic data demonstrate that the proposed algorithm is robust to outliers and can be used with non-Gaussian data.
  arXiv  Detail & Related papers  (2022-01-28T10:01:37Z)
• Predict then Interpolate: A Simple Algorithm to Learn Stable Classifiers [59.06169363181417]
  Predict then Interpolate (PI) is an algorithm for learning correlations that are stable across environments. We prove that by interpolating the distributions of the correct predictions and the wrong predictions, we can uncover an oracle distribution where the unstable correlation vanishes.
  arXiv  Detail & Related papers  (2021-05-26T15:37:48Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  We give the first outlier-robust efficient algorithm for clustering a mixture of $k$ statistically separated d-dimensional Gaussians (k-GMMs) Our results extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the $d$-dimensional unit sphere.
  arXiv  Detail & Related papers  (2020-05-06T17:24:27Z)

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.