In this paper, we derive generic bounds on the maximum deviations in prediction errors for sequential prediction via an information-theoretic approach. The fundamental bounds are shown to depend only on the conditional entropy of the data point to be predicted given the previous data points. In the asymptotic case, the…
Two-step conformal prediction method for adaptive bounding box uncertainties in multi-object detection.
problem Quantifying predictive uncertainty for multi-object detection in safety-critical applications.
method Developed a two-step conformal prediction approach to propagate uncertainty in predicted class labels into bounding box uncertainties, ensuring coverage for incorrectly classified objects.
result Desired coverage levels are satisfied with practically tight predictive uncertainty intervals on real-world datasets.
In this paper, we obtain generic bounds on the variances of estimation and prediction errors in time series analysis via an information-theoretic approach. It is seen in general that the error bounds are determined by the conditional entropy of the data point to be estimated or predicted given the side information or p…
Simple bounds show most cross-sectional predictability findings are likely true.
problem Determining the validity of cross-sectional return predictability findings.
method Developed simple and intuitive bounds on the false discovery rate (FDR).
result Bounds show the FDR is small, indicating most findings are likely true.
The paper finds a fundamental trade-off between confidence and efficiency in transductive conformal prediction.
problem The challenge is to balance confidence and efficiency in predicting multiple data points.
method The authors derive a strict finite-sample bound and introduce a practical algorithm to approach this bound.
result Any non-trivial confidence level leads to exponential growth in prediction set size, with a linear scaling in the number of samples.
Develops conformalized prediction intervals for bounded continuous outcomes.
problem Predicting continuous outcomes within bounded ranges, especially when models are misspecified.
method Conformal prediction intervals based on transformation regression models, accounting for heteroscedasticity and asymmetry.
result Valid finite-sample coverage confirmed in simulations and real data applications.
This paper considers the quantification of the prediction performance in Gaussian process regression. The standard approach is to base the prediction error bars on the theoretical predictive variance, which is a lower bound on the mean square-error (MSE). This approach, however, does not take into account that the stat…
Paper proves a new lower bound on calibration error for binary prediction.
problem Proving a strong lower bound on calibration error for binary prediction.
method Developed two new techniques: early stopping and sidestepping.
result Proves an Ω(T0.528) lower bound on calibration error. New bounds estimate learning algorithm performance using prediction information.
problem Estimating the performance of black-box learning algorithms.
method Information-theoretic bounds based on prediction information.
result Improved bounds applicable to deterministic algorithms and easier to estimate.
Paper develops conformalized survival analysis method for better prediction.
problem Survival analysis models often misspecify and require strong assumptions.
method Uses conformal prediction to wrap around any survival prediction algorithm.
result Lower predictive bounds provide guaranteed coverage without strong assumptions.
The paper derives uniform stability-based coverage bounds for conformal prediction methods.
problem Establishing theoretical guarantees for conformal prediction methods.
method Uniform stability perspective applied to full-conformal, jackknife+, and CV+ prediction regions.
result Coverage bounds for finite-dimensional models derived using a concentration argument.
This work uses PAC-Bayes for structured prediction with ILE, yielding insights and algorithms.
problem Structured prediction with interdependent outputs and implicit loss embeddings.
method PAC-Bayes perspective applied to ILE framework, deriving generalization bounds and learning algorithms.
result Two learning algorithms derived from PAC-Bayes bounds, analyzed and implemented.
Paper proposes a cost-sensitive conformal training method with provably controllable learning bounds.
problem Uncertainty quantification and learning bounds in conformal prediction.
method Cost-sensitive conformal training algorithm that minimizes the expected size of prediction sets using rank weighting.
result Theoretical analysis shows tightness between weighted objective and expected size of conformal prediction sets.
The paper develops bounds for predictive values in binary classification.
problem Lack of confidence intervals for positive and negative predictive values.
method Bi-criterion framework and distribution-free large deviation and uniform convergence bounds.
result New bounds for predictive values without relying on concentration inequalities.
Paper tightens optimization bounds using conformal prediction.
problem Lack of practical informiveness in dual bounds from optimization solvers.
method Introduces conformal prediction framework to tighten loose primal and dual bounds.
result Proposed method produces tighter, more informative prediction intervals.
Variational Prediction simplifies Bayesian inference without test time costs.
problem Bayesian inference's computational costs and posterior predictive distribution marginalization.
method Variational Prediction learns a variational approximation to the posterior predictive distribution using a variational bound.
result Directly learns a variational approximation to the posterior predictive distribution without test time marginalization costs.
We study online prediction of bounded stationary ergodic processes. To do so, we consider the setting of prediction of individual sequences and build a deterministic regression tree that performs asymptotically as well as the best L-Lipschitz constant predictors. Then, we show why the obtained regret bound entails the …
Proposes a method to compute valid lower confidence bounds for multiple models selected based on their performance.
problem Model selection and evaluation in machine learning.
method Interprets model selection as a simultaneous inference problem, uses bootstrap tilting and maxT-type multiplicity correction.
result Yields valid lower confidence bounds that are at least as good as standard approaches and reliably reach nominal coverage probability.
New bounds on efficiency for conformalized regression methods.
problem Efficiency of conformal prediction in regression models.
method Non-asymptotic bounds on prediction set length for conformalized quantile and median regression.
result Identifies phase transitions in convergence rates across different regimes of miscoverage level.
This paper improves entropy bounds for ranking time-series complexity.
problem Ranking the complexity of time series processes.
method Building on information theoretic bounds, the paper improves the upper bound of conditional differential entropy using Hadamard's inequality and covariance matrix properties.
result The improved bounds can be used to rank the complexity of time series processes.
Paper derives PAC-Bayesian bounds for LTI systems learning from empirical data.
problem Characterizing predictive power of LTI systems learned from data.
method PAC-Bayesian bounds for LTI stochastic dynamical systems with inputs.
result Finite-sample error bounds for learning algorithms of LTI systems.
Improved asset pricing using uncertainty-adjusted sorting in machine learning models.
problem Ignoring asset-specific estimation uncertainty in portfolio construction.
method Uncertainty-adjusted prediction bounds for sorting assets.
result Improves portfolio performance across various ML models and equity panels.
PAC-Bayesian framework for fairness in stochastic and deterministic classifiers.
problem Theoretical guarantees on fairness for balancing predictive risk and fairness constraints.
method PAC-Bayesian framework for both stochastic and deterministic classifiers, covering a broad class of fairness measures.
result Derives generalization bounds for fairness, demonstrating tightness with empirical evaluation.
Improved BO algorithms reduce prediction error under Gaussian noise.
problem Reducing prediction error in Bayesian optimization with Gaussian noise.
method Established new prediction error bounds for Gaussian process under frequentist setting.
result Proved improved convergence rates of cumulative regret for GP-UCB and GP-TS.
This paper improves risk bounds and calibration for smart predict-then-optimize method.
problem Improving risk bounds and calibration for smart predict-then-optimize method.
method Develops risk bounds and uniform calibration results for the SPO+ loss relative to the SPO loss.
result Empirical minimizer of the SPO+ loss achieves low excess true risk with high probability.
Paper proposes a new time series prediction method using weighted past data and optimization.
problem Predicting time series data with improved accuracy considering both deterministic and stochastic assumptions.
method The approach uses a weighted sum of past data, solving a constrained linear optimization problem to minimize an outer bound of prediction error.
result The method can outperform existing non-parametric methods in short-term forecasts.
A new method combines multiple bounds and betting strategies for selective prediction, improving risk coverage in data-scarce settings.
problem Selective prediction with risk control in data-scarce domains.
method Combines concentration inequalities, multiple-testing corrections, and betting-based confidence sequences.
result Transfer-Informed Betting achieves tighter bounds and better coverage in data-scarce settings.
WR-CP reduces prediction set size and coverage gap under distribution shift.
problem Guaranteed coverage under distribution shift not achievable with i.i.d. assumption.
method Wasserstein distance, probability measure pushforwards, importance weighting, regularized representation learning.
result Reduces coverage gap to 3.2% across different confidence levels.
Flexible framework for bounding high-loss predictions using quantiles.
problem Need for rigorous guarantees in risk-sensitive applications.
method Order statistics of loss values, flexible quantile-based metrics.
result Ability to rigorously control loss quantiles on real-world datasets.
We present methods for online linear optimization that take advantage of benign (as opposed to worst-case) sequences. Specifically if the sequence encountered by the learner is described well by a known "predictable process", the algorithms presented enjoy tighter bounds as compared to the typical worst case bounds. Ad…
The paper tackles stock prediction models by improving their generalizability to out-of-sample domains using causal representation learning.
problem Low signal-to-noise ratio and nonstationary nature of financial markets lead to poor performance of stock prediction models.
method The paper investigates Domain Generalization techniques, focusing on causal representation learning to improve model generalizability. It introduces a novel error bound and a causal discovery technique to mitigate spurious correlations.
result The proposed approach enhances the generalizability of stock prediction models, as demonstrated by numerical results.
Bayesian sequence prediction is a simple technique for predicting future symbols sampled from an unknown measure on infinite sequences over a countable alphabet. While strong bounds on the expected cumulative error are known, there are only limited results on the distribution of this error. We prove tight high-probabil…
In this paper, we obtain fundamental Lp bounds in sequential prediction and recursive algorithms via an entropic analysis. Both classes of problems are examined by investigating the underlying entropic relationships of the data and/or noises involved, and the derived lower bounds may all be quantified in…
The study assesses low-rank approximations in Gaussian Process regression.
problem Improving the efficiency of Gaussian Process regression while maintaining accuracy.
method Analyzes two low-rank approximations: random Fourier features and Mercer expansion truncation, and bounds the divergence and error between exact and approximate models.
result Theoretical bounds on the divergence and error between exact and approximate Gaussian Process models are provided.
Improves conditional coverage of regression models using conformal prediction.
problem Lack of conditional coverage guarantees in conformal prediction methods.
method Proposes a novel algorithm to train a regression function to improve conditional coverage after split conformal prediction.
result Establishes an upper bound for miscoverage gap and proposes an end-to-end algorithm to control it.
ST-BCP narrows the coverage gap in BCP by transforming nonconformity scores.
problem The looseness in BCP's coverage guarantee due to Markov's inequality.
method Introduces a data-dependent transformation of nonconformity scores.
result Reduces the average coverage gap from 4.20% to 1.12% on benchmarks.
The predict-then-optimize framework is fundamental in many practical settings: predict the unknown parameters of an optimization problem, and then solve the problem using the predicted values of the parameters. A natural loss function in this environment is to consider the cost of the decisions induced by the predicted…
The goal of predictive sparse coding is to learn a representation of examples as sparse linear combinations of elements from a dictionary, such that a learned hypothesis linear in the new representation performs well on a predictive task. Predictive sparse coding algorithms recently have demonstrated impressive perform…
Online prediction improves with abstention, reducing regret to a fixed bound.
problem Sequential prediction with expert advice.
method Introducing abstention with a cost smaller than 0.5, achieving independent regret bounds.
result Achieves expected regret bounds independent of time horizon, with bounds of order log(N)/(1-2c).
The paper presents a method to compute trusted confidence bounds for LECs in CPS.
problem Non-transparent predictions of LECs make CPS safety challenging.
method Inductive Conformal Prediction (ICP) and Triplet Network architecture.
result Efficient real-time computation of trusted confidence bounds.
Efficient classifier with uncertainty bounds for safety-critical applications.
problem Lack of uncertainty bounds in high-accuracy classifiers for safety-critical tasks.
method Nadaraya-Watson estimator with frequentist bounds.
result Competitive accuracy and uncertainty bounds at reduced computational cost.
Novel risk bound for structured prediction tackles non-i.i.d. data.
problem Structured prediction challenges due to non-factorizable target objects.
method PAC-Bayesian risk bound with explicit structure distillation.
result Generalization rate scales with data size and structure.
A smart method predicts and optimizes decisions online with resource constraints.
problem Online decision-making with resource constraints.
method Combines prediction and optimization with dual update using mirror descent.
result Regret bounds and convergence rates for general convex feasible regions.
Improves Bayesian predictive performance in misspecified models.
problem Misspecification gap between inferential and predictive risks.
method Develops a multi-sample loss (PACm) to bridge the gap. result Empirical study shows improved predictive distribution.
In the framework of prediction with expert advice, we consider a recently introduced kind of regret bounds: the bounds that depend on the effective instead of nominal number of experts. In contrast to the Normal- Hedge bound, which mainly depends on the effective number of experts but also weakly depends on the nominal…
Proposes a non-crossing deep neural network quantile regression method.
problem Quantile crossing in nonparametric quantile regression.
method Non-crossing constraints via rectified linear unit penalty function.
result Established non-asymptotic upper bounds for excess risk.
Standard methods in supervised learning separate training and prediction: the model is fit independently of any test points it may encounter. However, can knowledge of the next test point x⋆ be exploited to improve prediction accuracy? We address this question in the context of linear prediction, show…
In this paper, we examine the fundamental performance limits of prediction, with or without side information. More specifically, we derive generic lower bounds on the Lp norms of the prediction errors that are valid for any prediction algorithms and for any data distributions. Meanwhile, we combine the ent…