This paper improves active learning for Gaussian process regression to handle distributional uncertainty.
problem Active learning for Gaussian process regression does not guarantee accurate predictions for target distributions.
method Proposes two methods to reduce worst-case expected error for Gaussian process regression.
result Shows an upper bound of the worst-case expected squared error, suggesting finite data labels can achieve arbitrarily small error.
Hardness proof for agnostically learning halfspaces from worst-case lattice problems.
problem Agnostically learning halfspaces in the presence of noise.
method Reduction to worst-case lattice problems (GapSVP, SIVP).
result No efficient algorithm can achieve misclassification error better than 1/2 - γ under given hardness assumptions.
New framework assesses extreme errors in machine learning models.
problem Current validation methods fail to quantify extreme errors in high-stakes domains.
method Uses Extreme Value Theory (EVT) to estimate worst-case failures.
result Establishes EVT as a fundamental tool for assessing model reliability.
DRCS selects a subset of data to minimize worst-case test error under covariate shift.
problem Selecting a subset of data that performs well across different deployment scenarios when data distributions differ.
method DRCS derives an upper bound for the worst-case test error assuming covariate shift and selects instances to minimize this bound.
result DRCS achieves distributionally robust training instance selection.
Efficient learning of minimax risk classifiers in high dimensions.
problem Efficient learning of classifiers in high-dimensional data.
method Iterative algorithm leveraging constraint generation methods for minimax risk classifiers.
result The algorithm provides efficient learning and feature selection in high-dimensional scenarios.
The study assesses ML model robustness under worst-case subpopulations.
problem ML model performance degradation under non-training population.
method Two-stage estimation procedure for evaluating worst-case robustness over subpopulations.
result The method certifies model robustness and prevents unreliable deployments.
Robust hypothesis testing designs a test for worst-case distributions using kernel methods.
problem Design a robust test for hypothesis testing under uncertainty sets.
method Data-driven uncertainty sets constructed using kernel mean embeddings and maximum mean discrepancy (MMD). Bayesian and Neyman-Pearson settings investigated.
result Proposed robust kernel tests are exponentially consistent and asymptotically optimal.
Optimal recovery framework for non-IID data in Hilbert spaces.
problem Generalization in non-IID data scenarios.
method Optimal recovery perspective, semidefinite programming, kernel ridgeless regression.
result Optimal recovery formula coincides with kernel ridgeless regression in some cases.
Improved kernel quadrature with convex weights using subsampling.
problem Constructing quadrature rules with small worst-case error.
method Combining spectral properties of the kernel with recombination results.
result Effective algorithms for constructing convex quadrature rules with i.i.d. samples.
Bayesian optimization for function-valued responses, addressing worst case deviations.
problem Optimizing expensive functions with functional responses, focusing on worst case performance.
method Min-Max Functional Bayesian Optimization (MM-FBO) using Gaussian process surrogates and functional principal component analysis.
result MM-FBO consistently outperforms existing methods in synthetic and real-world applications.
SRO optimizes decisions against worst-case sampler induced by generative models.
problem Operational uncertainty shifts from explicit probability law to sampler induced by learned generators.
method SRO optimizes decisions against the worst-case sampler induced by perturbing the learned generator.
result Empirical worst-case objective provides high-probability upper certificate for true population objective.
Given a task of predicting Y from X, a loss function L, and a set of probability distributions Γ on (X,Y), what is the optimal decision rule minimizing the worst-case expected loss over Γ? In this paper, we address this question by introducing a generalization of the principle of maximum entropy. Applying t…
New framework improves worst-case generalization bounds for stochastic optimization.
problem Challenges in providing generalization guarantees for stochastic optimization algorithms.
method Introduces random set stability and empirically relevant complexity measures to avoid intractable mutual information terms.
result Bounded worst-case generalization error in terms of random set stability and empirically relevant complexity measures.
ISMCTS-BR learns best responses in large games, approximating worst-case performance.
problem Learning robustness to worst-case outcomes in large games.
method ISMCTS-BR, a scalable search-based algorithm for deep reinforcement learning.
result ISMCTS-BR approximates worst-case performance in large games.
We study high-dimensional asymptotic performance limits of binary supervised classification problems where the class conditional densities are Gaussian with unknown means and covariances and the number of signal dimensions scales faster than the number of labeled training samples. We show that the Bayes error, namely t…
A new method for survival analysis models that ensures fairness without using sensitive demographic data.
problem Ensuring fairness in survival analysis models without relying on sensitive demographic information.
method A worst-case error minimization approach using a training loss function that does not know sensitive demographic information.
result The proposed method often scores better on fairness metrics without a significant drop in prediction accuracy compared to baselines.
New method warns of counterfactual non-identifiability in DSCMs.
problem Counterfactual inference from observational data is non-identifiable even without unobserved confounding.
method Prove counterfactual identifiability for monotonic generation mechanisms, provide impossibility result for general mechanisms, propose method for estimating worst-case errors.
result Non-identifiability of counterfactual inference from observational data, even in absence of unobserved confounding.
Paper proves higher-order flow matching preserves optimality in generative modeling.
problem Theoretical guarantees for higher-order flow matching in generative modeling.
method Neural network approximations with controlled depth, width, and sparsity.
result Proves worst case optimality for second-order flow matching.
Optimizes kernel discrepancies by selecting subsets efficiently.
problem Improving kernel discrepancies for QMC methods.
method Introduces a novel subset selection algorithm for kernel discrepancies.
result Efficiently generates low-discrepancy samples from various distributions.
New approach for pricing evaluation improves on existing methods.
problem Improving off-policy evaluation for personalized pricing.
method Balanced policy evaluation framework with worst-case optimization.
result Empirical advantage over existing methods in pricing applications.
Paper introduces DOO models to outperform SAA out-of-sample.
problem Outperforming SAA in out-of-sample performance.
method Introduces DOO models that consider both worst-case and best-case scenarios.
result DOO models can always outperform SAA out-of-sample.
The study bounds errors in learning smooth functions online.
problem Investigating worst-case error bounds for online learning of smooth functions.
method Analyzing the class of absolutely continuous functions with smoothness constraints and proving bounds on prediction errors.
result Proved bounds on the sum of the pextth powers of absolute prediction errors for any number of trials. In experimental design, we are given a large collection of vectors, each with a hidden response value that we assume derives from an underlying linear model, and we wish to pick a small subset of the vectors such that querying the corresponding responses will lead to a good estimator of the model. A classical approach …
We analyze MDL for binary classification, quantifying overfitting and underfitting.
problem Understanding the trade-off between underfitting and overfitting in MDL for binary classification.
method Complete characterization of the regularization curve for MDL, extending previous work to all λ. result Precise quantitative description of the worst case limiting error as a function of λ and noise level. Method identifies shifts leading to large model performance differences.
problem Detecting shifts in distribution that affect model performance.
method Parametric changes in causal mechanisms define robustness sets; worst-case optimization problem approximated as non-convex quadratic.
result Second-order approximation of worst-case loss for small shifts, leading to efficient algorithms.
Data-independent pruning method reduces neural network size with accuracy guarantees.
problem Limited computational and memory resources for neural networks.
method Structured pruning using coresets.
result First efficient algorithm with worst-case guarantees on compression and accuracy.
Model-free approach to hedge path-dependent options using min-max optimization.
problem Hedging path-dependent options with maturity T using a static portfolio of vanilla options.
method Model-free approach based on primal-dual Martingale Optimal Transport (MOT) problem, solving a min-max optimization problem.
result Provides theoretical bounds on hedging error at maturity T.
New method reveals good classifiers are common in over-parameterized models.
problem Understanding how over-parameterized models generalize well.
method Developed a methodology to compute the full distribution of test errors.
result Test errors concentrate around a small typical value ε* rather than the worst-case model.
This work provides theoretical and empirical evidence that invariance-inducing regularizers can increase predictive accuracy for worst-case spatial transformations (spatial robustness). Evaluated on these adversarially transformed examples, we demonstrate that adding regularization on top of standard or adversarial tra…
The goal of regression and classification methods in supervised learning is to minimize the empirical risk, that is, the expectation of some loss function quantifying the prediction error under the empirical distribution. When facing scarce training data, overfitting is typically mitigated by adding regularization term…
Paper simplifies balancing weights by relaxing outcome assumptions.
problem Estimating missing outcomes in a target population.
method Relaxes outcome assumptions to simplify balancing weights.
result Balancing weights can be simplified with convex loss and minimum worst-case bias.
Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
We introduce a framework for statistical estimation that leverages knowledge of how samples are collected but makes no distributional assumptions on the data values. Specifically, we consider a population of elements [n]=1,…,n with corresponding data values x1,…,xn. We observe the values for a "sample…
There has been a large amount of interest, both in the past and particularly recently, into the power of different families of universal approximators, e.g. ReLU networks, polynomials, rational functions. However, current research has focused almost exclusively on understanding this problem in a worst-case setting, e.g…
We analyze a simple prefiltered variation of the least squares estimator for the problem of estimation with biased, semi-parametric noise, an error model studied more broadly in causal statistics and active learning. We prove an oracle inequality which demonstrates that this procedure provably mitigates the variance in…
Efficient kernel method learns differential equations with fewer data.
problem Learning differential equations with limited data and computational resources.
method Kernel-based framework for differential equations with theoretical error bounds.
result Significant improvements in accuracy and computational efficiency.
We study a recent model of collaborative PAC learning where k players with k different tasks collaborate to learn a single classifier that works for all tasks. Previous work showed that when there is a classifier that has very small error on all tasks, there is a collaborative algorithm that finds a single classifi…
The paper introduces a new measure of robustness for partially identifiable risks.
problem Achieving robustness when the robust risk is only partially identified.
method Introduces the worst-case robust risk and evaluates existing methods.
result Existing robustness methods are suboptimal in the partially identifiable case.
We develop a worst-case analysis of aggregation of classifier ensembles for binary classification. The task of predicting to minimize error is formulated as a game played over a given set of unlabeled data (a transductive setting), where prior label information is encoded as constraints on the game. The minimax solutio…
New study shows mean estimation algorithms can't beat sub-Gaussian rate in general.
problem Improving mean estimation beyond worst-case scenarios.
method Constructing counterexamples and introducing neighborhood optimality.
result No reasonable estimator can achieve better than sub-Gaussian error rate for any distribution.
We consider the problem of learning a dictionary matrix from a number of observed signals, which are assumed to be generated via a linear model with a common underlying dictionary. In particular, we derive lower bounds on the minimum achievable worst case mean squared error (MSE), regardless of computational complexity…
The paper uses EVT to improve tail risk measures under ambiguity sets.
problem Misspecification of tail risk measures leads to inflated risk estimates.
method Applies Extreme Value Theory to derive worst-case tail risk under ambiguity sets.
result Proposes a tail-calibrated ambiguity design that preserves nominal tail asymptotic scaling.
This work precisely characterizes and improves the tradeoff between robustness and accuracy in linear regression.
problem Tradeoff between robustness and accuracy in adversarial training.
method Characterizes the effect of augmentation on standard error in linear regression; proves RST improves robust error without sacrificing standard error.
result RST improves both standard and robust error for neural networks under various perturbations.
Sharp analysis of out-of-distribution error in overparameterized models with importance weights.
problem Understanding and quantifying the degradation of performance in overparameterized models when faced with underrepresented data.
method Sharp analysis of an overparameterized Gaussian mixture model with spurious features and cost-sensitive interpolating solutions incorporating importance weights.
result Characterization of a novel tradeoff between worst-case robustness and average accuracy as a function of importance weight magnitude.
Worst-Case Sensitivity measures model sensitivity to uncertainty set size.
problem Model sensitivity to uncertainty set size in Distributionally Robust Optimization.
method Introducing Worst-Case Sensitivity as a measure of model sensitivity, and deriving closed-form expressions for various uncertainty sets.
result DRO solutions can be sensitive to the family and size of the uncertainty set, and worst-case sensitivity reflects these properties.
We give two provably accurate feature-selection techniques for the linear SVM. The algorithms run in deterministic and randomized time respectively. Our algorithms can be used in an unsupervised or supervised setting. The supervised approach is based on sampling features from support vectors. We prove that the margin i…
An important task in structural design is to quantify the structural performance of an object under the external forces it may experience during its use. The problem proves to be computationally very challenging as the external forces' contact locations and magnitudes may exhibit significant variations. We present an e…
Study of supervised learning from multiple non-independent sequences.
problem Efficient learning from many non-independent sequences.
method Generalizes conditions for efficient learning from independent examples and single auto-correlated sequences.
result Error rate changes from Θ(n/mT) to Ω(n2/m2T) as the number of trajectories increases.