Study optimal policies under budget and coverage constraints.
problem Optimal policy learning with budget and coverage constraints.
method Combination of knapsack structure, affine threshold rule, linear programming relaxation, Greedy-Lagrangian (GLC), and rank-and-cut (RC) algorithms.
result GLC closely approximates the optimal solution and achieves near-optimal performance in finite samples; RC is approximately optimal under certain conditions.
Develops optimal decision-making framework for uncertain counterfactuals.
problem Ensuring reliability of predictions in high-stakes decisions.
method Policy-Coupled Risk-Averse Conformal Prediction (PC-RACP).
result Optimal prediction sets for counterfactual decisions with valid coverage.
New model OPSS allows constant approximation for maximum coverage problem.
problem Optimizing coverage functions from samples is hard.
method Proposed OPSS model with structured samples.
result Achieved constant approximation for maximum coverage problem.
Improved conformal prediction for better conditional coverage of classifier predictions.
problem Achieving exact conditional coverage in finite samples for prediction sets.
method Developed a variant of conformal prediction targeting coverage conditional on confidence and trust score.
result Empirically improved conditional coverage properties compared to standard conformal prediction.
New L1-Coverage objective simplifies exploration in reinforcement learning.
problem Challenges in exploration for high-dimensional domains.
method Introduces L1-Coverage objective to enable efficient exploration and planning. result First computationally efficient algorithms for online reinforcement learning with low coverability.
Conformal methods create prediction bands that control average coverage under no assumptions besides i.i.d. data. Besides average coverage, one might also desire to control conditional coverage, that is, coverage for every new testing point. However, without strong assumptions, conditional coverage is unachievable. Giv…
A new convex loss function optimizes set predictions with balanced size and coverage.
problem Optimizing set predictions with balanced size and coverage.
method Proposes a convex loss function using Choquet integrals for nondecreasing subset-valued functions.
result Optimal trade-offs between conditional probabilistic coverage and set size.
MOPI optimizes flexible set-valued mappings to achieve superior shape adaptivity in conformal prediction.
problem Challenges in achieving valid conditional coverage in conformal prediction.
method Minimax Optimization Predictive Inference (MOPI) framework that optimizes over a flexible class of set-valued mappings.
result MOPI achieves superior shape adaptivity and maintains a principled connection to mean squared coverage error.
Oracle-efficient algorithm for offline RL with partial data coverage.
problem Offline reinforcement learning with partial data coverage and constraints.
method PDOCRL, a primal-dual algorithm with decomposed linear-programming formulation.
result Near-optimal, near-feasible policy with \(\widetilde{\mathcal O}(ε^{-2})\) sample guarantee.
We introduce the concept of coverage risk as an error measure for density ridge estimation. The coverage risk generalizes the mean integrated square error to set estimation. We propose two risk estimators for the coverage risk and we show that we can select tuning parameters by minimizing the estimated risk. We study t…
New algorithms estimate Q-functions under partial coverage and realizability, improving offline RL guarantees.
problem Offline RL with limited exploration and assumptions about data coverage and Q-function realizability.
method Proposes minimax learning algorithms to estimate soft or vanilla Q-functions with L2-convergence guarantees. result PAC guarantees for offline RL under partial coverage and realizability conditions.
Adaptive coverage policies improve conformal prediction accuracy.
problem Fixed coverage levels in traditional conformal prediction lead to uninformative predictions.
method Optimizes adaptive coverage policy using a neural network trained on leave-one-out calibration.
result Adaptive coverage policies produce more informative and flexible prediction sets.
Proposes methods for online conformal prediction with nested prediction sets across multiple confidence levels.
problem Need for uncertainty quantification with multiple confidence levels in diverse applications.
method Online optimization perspective to enforce nestedness of prediction sets while controlling quantile estimation error.
result Achieves stable coverage across all levels, strictly nested prediction sets, and improved efficiency.
New variational method solves submodular maximum coverage problem efficiently.
problem Submodular maximum coverage problem in various applications.
method Variational optimization using Nemhauser divergence, alternating E and M steps.
result Efficient solution to submodular maximum coverage problem.
Kandinsky conformal prediction expands conditional coverage guarantees.
problem Disparities in coverage guarantees across different subpopulations.
method Flexible handling of overlapping and fractional group memberships.
result Minimax-optimal high-probability conditional coverage bound.
Optimal decision-making using prediction sets to minimize risk.
problem Using prediction sets optimally for decision-making in uncertain scenarios.
method Decision-theoretic framework that seeks to minimize expected loss against a worst-case distribution.
result ROCP algorithm reduces critical mistakes compared to baselines, especially in costly out-of-set errors.
Optimal transport improves multivariate prediction uncertainty quantification.
problem Uncertainty quantification in multivariate learning tasks, especially in regression and classification.
method Introducing a novel Conformal Prediction procedure using optimal transport to handle multivariate score functions and construct flexible prediction regions.
result Ensures finite-sample, distribution-free coverage guarantees for multivariate prediction sets.
CPPO learns policies from partial offline data in MDPs with structural assumptions.
problem Offline Reinforcement Learning with partial coverage assumption.
method Constrained Pessimistic Policy Optimization (CPPO) using a function class and model class constraint.
result CPPO achieves PAC guarantee with partial coverage, learning competitive policies.
Sampling one or more effective solutions from large search spaces is a recurring idea in machine learning, and sequential optimization has become a popular solution. Typical examples include data summarization, sample mining for predictive modeling and hyper-parameter optimization. Existing solutions attempt to adaptiv…
Study shows offline RL with partial coverage and weak function classes is possible.
problem Learning optimal policies from logged data with function approximation.
method Marginalized Importance Sampling (MIS) with additional covering distribution.
result Finite-sample guarantees for sample-efficient offline RL for general MDPs.
Paper estimates area covered by a line-sweep sensor in robotics.
problem Accurately estimating the area covered by a line-sweep sensor.
method Relies on coverage measure and topological degree in the plane.
result Guaranteed characterization of the explored area using interval analysis.
CoCP optimizes prediction intervals by jointly learning center and radius, improving efficiency and coverage.
problem Inefficient conformal prediction intervals under heteroscedasticity and skewness.
method Co-optimization framework that learns center and radius through alternating optimization steps.
result CoCP yields consistently shorter intervals and state-of-the-art conditional coverage diagnostics.
SA-BCP combines long-term and local evidence for efficient, adaptive online prediction.
problem Balancing fast adaptation and stable coverage in online prediction.
method State-Adaptive Bayesian Conformal Prediction (SA-BCP) using gated convex combination of temporal inertia and spatial evidence.
result SA-BCP achieves at-or-above-nominal coverage with substantially sharper intervals compared to discounted Bayesian CP.
PAC-Bayes theory improves ICP efficiency and coverage.
problem Inefficient and unreliable uncertainty estimates in deep learning models.
method PAC-Bayes theory to optimize model and score function parameters for efficient and reliable prediction sets.
result Generalization bounds on coverage and efficiency of optimized prediction sets.
New conformal prediction methods for long-tailed classification problems.
problem Rare classes are systematically omitted in existing conformal prediction methods.
method Introduced a new conformal score function and a new interpolation procedure.
result Smoothly trade off set size and class-conditional coverage.
Method constructs uniformly valid prediction sets across multiple distributions.
problem Uniformly valid prediction sets across multiple distributions.
method Max-p aggregation scheme and optimization programs.
result Optimal and efficient prediction sets for multiple distributions.
Novel method for time-series prediction with tighter confidence intervals.
problem Improving prediction intervals for time-series data.
method Kernel-based Optimally Weighted Conformal Prediction Intervals (KOWCPI) using adaptive weights.
result KOWCPI achieves narrower confidence intervals with guaranteed coverage.
Pre-training improves model coverage, crucial for downstream performance.
problem Understanding why pre-training enhances model performance.
method Coverage principle, focusing on next-token prediction and model quality.
result Coverage generalizes faster than cross-entropy, improving downstream performance.
New method optimizes prediction set volume in conformal prediction.
problem Achieving volume optimality in conformal prediction without sacrificing coverage guarantees.
method Dynamic programming algorithm for finding near-optimal volume unions of k-intervals.
result Efficient algorithm finds unions of k-intervals with near-optimal volume for any distribution.
This work introduces COLA, a strategy to aggregate conformal prediction sets efficiently.
problem Efficiently combining multiple conformity scores to reduce prediction set size.
method Introduces COnfidence-Level Allocation (COLA) to optimally allocate confidence levels across sets.
result COLA achieves smaller prediction sets than state-of-the-art methods while maintaining valid coverage.
Bayesian optimization enhanced with conformal prediction for better outcome reliability.
problem Uncertainty and model misspecification in Bayesian optimization.
method Conformal prediction to provide coverage guarantees and Bayesian optimization to select queries.
result Significant improvement in query coverage without sacrificing sample-efficiency.
New online conformal prediction methods minimize strongly adaptive regret and achieve near-optimal coverage.
problem Uncertainty quantification in online settings with changing data distributions.
method Developed new online conformal prediction methods that minimize strongly adaptive regret.
result Achieve near-optimal strongly adaptive regret and approximately valid coverage.
Generalizes conformal prediction to multiple learnable parameters for efficient prediction sets.
problem Learning valid and efficient prediction sets with low-capacity function classes.
method Constrained empirical risk minimization (ERM) with gradient-based optimization of differentiable surrogate losses and Lagrangians.
result Achieves approximate valid population coverage and near-optimal efficiency within class.
MCP extends conformal prediction to vector-valued score functions without data splitting.
problem Fixed prediction set shapes in scalar score functions limit coverage guarantees.
method MCP uses a single optimization problem for prediction set design and calibration, eliminating data splitting.
result RemMCP and RelMCP achieve target coverage with smaller or comparable prediction set sizes, reducing variance.
New insights show coverage conditions are crucial for efficient online reinforcement learning.
problem The role of coverage conditions in determining sample complexity of offline reinforcement learning.
method Established a connection between coverage conditions and sample efficiency in online reinforcement learning.
result Coverability, a structural property of MDPs, enables sample-efficient exploration in online reinforcement learning.
A new method for active learning works well across all label budgets.
problem Active learning methods perform poorly in both low and high label budgets.
method Uncertainty Herding: a simple, computationally fast method that optimizes uncertainty coverage.
result Uncertainty Herding nearly optimizes distribution-level coverage and performs well across various active learning tasks.
The paper improves prediction intervals for non-parametric regression using histograms.
problem Computing accurate prediction intervals for non-parametric regression models.
method Uses conditional histograms to estimate conditional distributions and compute shortest prediction intervals.
result The method provides prediction intervals with provable marginal coverage and asymptotic conditional coverage.
We consider a scenario where the aim of a group of agents is to perform the optimal coverage of a region according to a sensory function. In particular, centroidal Voronoi partitions have to be computed. The difficulty of the task is that the sensory function is unknown and has to be reconstructed on line from noisy me…
This paper aims to optimize incident-specific cyber insurance design.
problem Complexity in determining optimal risk retention and transfer.
method Economic foundation for incident-specific cyber insurance with Pareto optimality.
result Illustrates feasibility of designing incident-specific indemnities for both parties.
Improved local explainer aggregation for interpretable machine learning models.
problem Improving the interpretability of black box machine learning models.
method Non-convex optimization and integer optimization framework for local explainer aggregation.
result Our method outperforms existing methods in terms of coverage and fidelity, particularly in multi-class settings.
Study optimal product assortment using historical data, proving item coverage suffices.
problem Offline assortment optimization under MNL model with limited historical data.
method Pessimistic Rank-Breaking (PRB) algorithm combining rank-breaking and pessimistic estimation.
result Optimal item coverage is both sufficient and necessary for efficient offline learning.
Sharp analysis improves RLHF sample complexity with KL-regularization.
problem Improving RLHF sample complexity with KL-regularization.
method Sharp analysis of KL-regularized contextual bandits and RLHF.
result Achieved an O(1/ε) sample complexity when ε is sufficiently small.
SURF steers scalarization weights to uniformly traverse the Pareto front.
problem Non-uniform coverage of the Pareto front when using scalarization weights.
method Geometric analysis and CDF mapping to select weights for uniform coverage.
result SURF converges to uniform Pareto front coverage under provable conditions.
Improves conformal prediction by combining multiple score functions and optimizing weights.
problem Limitations of single-score conformal predictors in multi-class classification.
method Combines multiple score functions and optimizes weights to minimize prediction set size.
result Consistently outperforms single-score conformal predictors while maintaining valid coverage.
Survey of reinforcement learning guarantees with data constraints.
problem Guaranteeing near-optimal policies with limited data in reinforcement learning.
method Coverage-Structure-Objective (CSO) framework to decompose sample complexity results.
result Progress on PAC guarantees for reinforcement learning, covering various models and settings.
Extends conformal prediction to contrastive learning for better coverage of positive samples.
problem Lack of principled guarantees on coverage in contrastive learning.
method Introduces minimum-volume covering sets with learnable constraints.
result Improves inclusion-exclusion trade-offs in positive and negative samples.
CTI produces efficient prediction intervals with guaranteed coverage.
problem Efficient and reliable uncertainty quantification in regression.
method CTI estimates conditional density for interval length, then thresholds intervals based on this density.
result CTI achieves smaller prediction sets with guaranteed coverage compared to existing methods.
An online framework optimizes efficiency in conformal prediction with a target miscoverage rate.
problem Achieving coverage and minimizing interval length in a sequential, online setting.
method Optimizes efficiency by directly optimizing the average length of intervals while maintaining coverage.
result Shows a gap between optimal performance for exchangeable and arbitrary sequences, and provides a matching algorithm for the Pareto-optimal settings.