New bounds on machine learning model generalization error moments.
problem Understanding the performance of machine learning models.
method Information-theoretic bounds on the moments of the generalization error of learning algorithms.
result Proposed bounds on generalization error moments and their high-probability bounds.
This work bounds classification error in machine learning for low Bayes error conditions.
problem Understanding the error mismatch between Bayes error and model-based classification error.
method Applying classification error bounds to study the relationship with Kullback-Leibler divergence and proposing a linear approximation for low Bayes error conditions.
result A linear approximation of the classification error bound for low Bayes error conditions is proposed.
PAC-Bayesian bounds for stochastic LTI systems derived.
problem Error bounds for stochastic LTI systems.
method PAC-Bayesian theory applied to autonomous stochastic LTI models.
result Error bounds for stochastic LTI systems derived.
Upper bounds for CV errors apply to lasso and other models.
problem Bounding CV errors for lasso and similar models.
method Rademacher complexity and Orlicz-Ψν norm. result Upper bounds are tight and stable for lasso.
This paper examines error bounds for deep learning classifiers with noisy labels.
problem Understanding the performance of classifiers trained on noisy data.
method Derives error bounds for excess risk, decomposing it into statistical and approximation errors. Uses independent block construction for statistical dependencies and vector-valued setting for approximation error.
result Established theoretical results for error bounds in deep learning with noisy labels, mitigating the impact of high-dimensional input spaces.
We introduce the speculate-correct method to derive error bounds for local classifiers. Using it, we show that k nearest neighbor classifiers, in spite of their famously fractured decision boundaries, have exponential error bounds with O(sqrt((k + ln n) / n)) error bound range for n in-sample examples.
The paper bounds the mean absolute error in DNN vector-to-vector regression.
problem Bounding the mean absolute error in deep neural network based vector-to-vector regression.
method Error decomposition techniques in statistical learning theory and non-convex optimization theory were used to derive upper bounds for approximation, estimation, and optimization errors.
result Theoretical upper bounds for mean absolute error in DNN vector-to-vector regression were derived and validated experimentally.
Paper derives an error bound for stochastic LTI systems.
problem Stochastic LTI systems with inputs in control engineering and econometrics.
method PAC-Bayesian-Like error bound derivation.
result Derived an error bound for stochastic LTI systems.
A new error bound improves safety in Bayesian optimization.
problem Ensuring safety in Bayesian optimization with probabilistic models.
method Introducing a novel error bound using Wiener kernel regression for Gaussian processes and noise.
result The new error bound provides larger safety regions than previous methods.
The paper provides tighter error bounds for GPR under bounded support noise.
problem Rigorous error quantification for safety-critical applications with bounded noise.
method Using concentration inequalities and low complexity assumptions in RKHS, the paper derives probabilistic and deterministic error bounds for GPR.
result The derived error bounds are substantially tighter than existing state-of-the-art bounds and are particularly well-suited for GPR with neural network kernels.
This paper tackles worst-class error rate in classification tasks.
problem Minimizing worst-class error rate in classification tasks, especially in medical image classification.
method Designing a boosting approach to bound the worst-class error rate using Deep Neural Networks (DNNs).
result The proposed boosting approach lowers worst-class test error rates while avoiding overfitting.
Derives error bounds for stochastic iterative algorithms using Stein's method.
problem Bounding errors in stochastic iterative algorithms like SGD and SGLD.
method Uses infinite-dimensional Stein's method of exchangeable pairs to derive functional approximation error bounds.
result Establishes non-asymptotic error bounds for algorithm sample paths and variance of iterate averages.
In this paper, we improve the PAC-Bayesian error bound for linear regression derived in Germain et al. [10]. The improvements are twofold. First, the proposed error bound is tighter, and converges to the generalization loss with a well-chosen temperature parameter. Second, the error bound also holds for training data t…
New PAC-Bayes bound controls multiple error types simultaneously.
problem Current PAC-Bayes bounds are limited to scalar metrics.
method Bounding KL divergence between empirical and true probabilities of multiple error types.
result First PAC-Bayes bound for rich information-rich certificates.
The paper offers error bounds for quantized dynamical models.
problem Accuracy of dynamical models from dependent data sequences.
method Developed uniform error bounds for quantized models and imperfect optimization algorithms.
result Unified bounds for slow and fast rates, scaling with model encoding bits.
This note provides an error bound for the Hartman-Watson integral's leading term.
problem Bounding the error of the leading term of the Hartman-Watson integral.
method Asymptotic expansion analysis focusing on the regime rt=ρ constant. result The error term is bounded uniformly as ∣ϑ(t,ρ)∣≤701t. This paper addresses error bounds and posterior variance for Gaussian process regression.
problem Deriving performance guarantees for Gaussian process regression without prior knowledge.
method Lipschitz continuity and analysis of posterior variance function.
result Uniform error bounds for Gaussian process regression are derived.
Study error bounds in evaluating distributional computational graphs.
problem Error analysis in evaluating graphs with inputs as probability distributions.
method Establish non-asymptotic error bounds using Wasserstein-1 distance.
result Non-asymptotic error bounds for discretization errors in distributional computational graphs.
Crowdsourcing is an effective tool for human-powered computation on many tasks challenging for computers. In this paper, we provide finite-sample exponential bounds on the error rate (in probability and in expectation) of hyperplane binary labeling rules under the Dawid-Skene crowdsourcing model. The bounds can be appl…
New bound on machine learning model performance using Jensen-Shannon information.
problem Understanding the performance of machine learning models.
method Proposes a new information-theoretic bound on generalization error.
result Shows that the new bound can be tighter than mutual information-based bounds under certain conditions.
Proposes a new bound on generalization error using conditional mutual information.
problem Improving the generalization error bound in machine learning.
method Combines error decomposition and conditional mutual information techniques.
result New bound is order-wise better than previous ones in a simple Gaussian setting.
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.
New bound matches exact generalization error for quadratic Gaussian problem.
problem Understanding generalization error in quadratic Gaussian problems.
method Information-theoretic approach with new ingredients.
result Exact tight bound for generalization error.
New error bounds for flow matching methods using deterministic sampling.
problem Improving the accuracy of flow matching methods for generating probability distributions.
method Derived error bounds for flow matching methods under deterministic sampling conditions.
result Presented error bounds for flow matching methods using L2 loss and regularity conditions. Data-driven models are subject to model errors due to limited and noisy training data. Key to the application of such models in safety-critical domains is the quantification of their model error. Gaussian processes provide such a measure and uniform error bounds have been derived, which allow safe control based on thes…
Error bounds based on worst likely assignments use permutation tests to validate classifiers. Worst likely assignments can produce effective bounds even for data sets with 100 or fewer training examples. This paper introduces a statistic for use in the permutation tests of worst likely assignments that improves error b…
Bounds on factual and counterfactual distributions under measurement error in discrete models.
problem Measurement errors in discrete data and their impact on inference.
method Expressing modeling assumptions as linear constraints and using linear programming to derive bounds.
result Sharp bounds on factual and counterfactual distributions for various models, including instrumental variable scenarios.
We consider active, semi-supervised learning in an offline transductive setting. We show that a previously proposed error bound for active learning on undirected weighted graphs can be generalized by replacing graph cut with an arbitrary symmetric submodular function. Arbitrary non-symmetric submodular functions can be…
New bounds quantify estimation error in kernel-based system identification with unknown hyperparameters.
problem Inaccurate error bounds for kernel-based system identification with unknown hyperparameters.
method Construct a high-probability set for true hyperparameters from marginal likelihood, then find worst-case posterior covariance.
result Proposed bounds contain true model with high probability and verified in simulations.
This article studies the achievable guarantees on the error rates of certain learning algorithms, with particular focus on refining logarithmic factors. Many of the results are based on a general technique for obtaining bounds on the error rates of sample-consistent classifiers with monotonic error regions, in the real…
In this work, we present a novel upper bound of target error to address the problem for unsupervised domain adaptation. Recent studies reveal that a deep neural network can learn transferable features which generalize well to novel tasks. Furthermore, a theory proposed by Ben-David et al. (2010) provides a upper bound …
New bounds tighten the generalization error of Gibbs algorithm.
problem Bounding the generalization error of Gibbs algorithm.
method Characterization of generalization error in terms of symmetrized KL information.
result Exact characterization of Gibbs algorithm's expected generalization error.
Paper improves risk bounds for nonconvex-strongly-concave minimax problems.
problem Achieving sharper risk bounds for nonconvex-strongly-concave minimax problems.
method Using uniform localized convergence to derive high probability generalization error bounds.
result Derives n times faster excess primal risk bounds for popular algorithms.
The study examines how equivariance in networks affects generalization error using PAC-Bayesian bounds.
problem Understanding how equivariance in networks impacts generalization error.
method Utilized PAC-Bayesian analysis for equivariant networks, deriving norm-based bounds for generalization error.
result The bound indicates that using larger group size in the model improves generalization error.
Paper analyzes Gibbs and Langevin Monte Carlo for interpolation regime, showing generalization from low errors.
problem Analyzing Gibbs and Langevin Monte Carlo in overparameterized interpolation regime.
method Data-dependent bounds and stability under approximation with Langevin Monte Carlo.
result Generalization is signaled by small training errors in noisy regime, with bounds stable under approximation.
In this paper we consider the cluster estimation problem under the Stochastic Block Model. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. The error bound implies weak recovery in the sparse graph regime with bou…
Paper addresses generalization error bounds for learning with censored feedback.
problem Impact of censored feedback on generalization error bounds.
method Derives an extension of DKW inequality for non-IID data due to censored feedback and uses it to bound generalization error.
result Existing generalization error bounds fail to account for censored feedback, necessitating new bounds.
Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establis…
Establishes upper bounds on generalization error in active learning.
problem Improving query algorithms in active learning.
method Derives upper bounds on generalization error using informativeness and representativeness query strategies.
result Validates the use of regularization techniques to ensure bounds' validity.
Optimal multiclass U-calibration error found to be Θ(√KT).
problem Online multiclass U-calibration with low regret for all bounded proper losses.
method Follow-the-Perturbed-Leader algorithm and lower bound construction.
result Optimal U-calibration error is Θ(√KT).
The paper bounds generalization error for iterative learning with bounded updates.
problem Generalization error of iterative learning algorithms with bounded updates for non-convex loss functions.
method Information-theoretic techniques, reformulating mutual information as update uncertainty, variance decomposition.
result Improved generalization error bounds for iterative learning algorithms with bounded updates.
An information-theoretic upper bound on the generalization error of supervised learning algorithms is derived. The bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm. The bound is derived under more general conditions on the loss func…
New bounds on generalization error using information density moments.
problem Bounding the generalization error of randomized learning algorithms.
method Derives bounds on average and tail probabilities of generalization error using mth central moments of the information density.
result Explicit bounds on generalization error are derived, showing better dependence on confidence level with higher-order information density moments.
New bounds study class-specific generalization error in machine learning.
problem Existing generalization theories assume uniform class performance, but in practice, classes vary significantly.
method Developed novel information-theoretic bounds using KL divergence and CMI.
result Theoretical bounds accurately capture complex class-generalization error behavior.
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…
Sharp bounds found on expert error in binary advice aggregation.
problem Aggregating binary advice from conditionally independent experts.
method Sharp upper and lower bounds on optimal error probability in asymmetric case.
result Sharp bounds recover and sharpen known results in symmetric case.
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher…
The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in…