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 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.
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).
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.
Adversarial training achieves optimal test error for shallow networks.
problem Achieving optimal adversarial test error for general data distributions.
method Applying new Rademacher complexity bounds and properties of optimal adversarial predictors.
result Adversarial training can achieve optimal adversarial test error for general data distributions.
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…
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.
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
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.
In this paper we study the stability and its trade-off with optimization error for stochastic gradient descent (SGD) algorithms in the pairwise learning setting. Pairwise learning refers to a learning task which involves a loss function depending on pairs of instances among which notable examples are bipartite ranking,…
New method improves privacy in linear regression with optimal error bounds.
problem Differentially private linear regression with suboptimal error bounds.
method One-pass mini-batch stochastic gradient descent (DP-AMBSSGD) with adaptive clipping.
result Nearly optimal error bounds in terms of key parameters like dimensionality, number of points, and noise standard deviation.
Full-batch GD achieves generalization close to any stationary point with fewer assumptions.
problem Generalization and excess risk bounds for smooth losses, including non-Lipschitz and nonconvex cases.
method Path-dependent analysis of GD's generalization error, focusing on optimization error and stability.
result Generalization error is tightly bound in terms of optimization error and iteration count, bypassing common assumptions.
The paper provides global optimization algorithms for two particularly difficult nonconvex problems raised by hybrid system identification: switching linear regression and bounded-error estimation. While most works focus on local optimization heuristics without global optimality guarantees or with guarantees valid only…
The paper tackles deep learning from dependent data, achieving optimal performance.
problem Deep learning from strongly mixing observations, especially with regularization and optimality.
method Sparse-penalized regularization for deep neural networks, oracle inequality for expected excess risk.
result Deep neural network estimator achieves minimax optimal rate for nonparametric autoregression.
New algorithm optimally evaluates policies with linear approximations.
problem Policy evaluation with linear function approximation.
method Accelerated, variance-reduced fast temporal difference algorithm (VRFTD).
result VRFTD matches both deterministic and stochastic lower bounds.
Simpler majority vote of three classifiers achieves optimal error bounds.
problem Developing an optimal PAC learning algorithm in the realizable setting.
method Returning the majority vote of three ERM classifiers.
result Achieves optimal in-expectation bound on error.
Sharp 2-Wasserstein bounds for DDPMs derived from Föllmer process.
problem Sampling error bounds for DDPMs in 2-Wasserstein distance.
method Lipschitz-type conditions on score function, Föllmer process, and log-concave target distributions.
result Sharp upper bounds for DDPMs in 2-Wasserstein distance, optimal in dimension and steps.
Improved bounds for proximal gradient algorithms with computational errors.
problem Analyzing convergence of proximal gradient algorithms with inaccuracies.
method Deriving new tighter deterministic and probabilistic bounds for convex composite problems.
result Probabilistic bounds are more robust and accurate for algorithm verification and performance guarantees.
The stochastic gradient descent (SGD) optimization algorithm plays a central role in a series of machine learning applications. The scientific literature provides a vast amount of upper error bounds for the SGD method. Much less attention as been paid to proving lower error bounds for the SGD method. It is the key cont…
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.
EBUCB framework achieves optimal regret with bounded approximate inference error.
problem Theoretical gap between practical performance and theoretical justification of Bayesian bandit algorithms with approximate inference.
method Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that accommodates bandit problems with approximate inference.
result EBUCB achieves optimal regret order O(logT) under certain conditions on inference error. Study error bounds and optimal schedules for Masked Diffusions with factorized approximations.
problem Analyzing trade-offs between computation and accuracy in Masked Diffusion Models.
method Provided general error bounds and identified optimal schedules based on data distribution information profiles.
result Identified optimal schedule sizes for Masked Diffusion Models.
Improved estimator for least squares using random projections achieves smaller error.
problem Improving the accuracy of least squares solutions for large-scale problems.
method James-Stein estimator applied to Gaussian sketching of least squares problems.
result Upper and lower bounds match when SNR is small and data matrix is well-conditioned.
The study sets limits on how robust classifiers can be against adversarial attacks.
problem Understanding the limits of robustness in classification models against adversarial attacks.
method Utilized optimal transport theory to derive variational formulae and explicit lower-bounds on Bayes-optimal error.
result Explicit lower-bounds on the Bayes-optimal error for distance-based attacks, universal in geometry of class-conditional distributions.
Optimal a priori estimates are derived for the population risk, also known as the generalization error, of a regularized residual network model. An important part of the regularized model is the usage of a new path norm, called the weighted path norm, as the regularization term. The weighted path norm treats the skip c…
We consider the mixed regression problem with two components, under adversarial and stochastic noise. We give a convex optimization formulation that provably recovers the true solution, and provide upper bounds on the recovery errors for both arbitrary noise and stochastic noise settings. We also give matching minimax …
We address the problem of learning to benchmark the best achievable classifier performance. In this problem the objective is to establish statistically consistent estimates of the Bayes misclassification error rate without having to learn a Bayes-optimal classifier. Our learning to benchmark framework improves on previ…
Efficiently learns a single neuron with adversarial noise, improving on prior work.
problem Learning a single neuron with adversarial label noise.
method Efficient algorithm using local error bounds from optimization theory.
result Approximates optimal L22-error within a constant factor. New bounds for SGLD show error decreases with more data.
problem Establishing generalization error bounds for SGLD in non-convex settings.
method Using dissipativity, smoothness, and uniform stability, time-independent bounds are derived.
result Error bounds decay to zero as sample size increases.
New methods bound estimation error in high-dimensional statistical problems.
problem Fundamental limits of first order methods in high-dimensional estimation.
method Introduces general first order methods for high-dimensional regression and low-rank matrix estimation.
result Derives optimal lower bounds on estimation error for these methods.
Estimates convex hulls of smooth function images with error bounds.
problem Estimating the convex hull of the image of a smooth boundary set.
method Using submersion properties and sampling inputs, derive bounds on Hausdorff distance.
result New tighter and more general error bounds for geometric inference.
Novel bounds for SGLD show generalization error decreases with more samples.
problem Understanding the generalization error of SGLD in non-convex optimization.
method Information-theoretic approach focusing on Kullback-Leibler divergence and sub-exponential loss function.
result Time-independent generalization bounds for SGLD, independent of step size and number of iterations.
The paper analyzes kNN density estimation's convergence rates under different conditions.
problem Analyzing convergence rates of kNN density estimation under bounded and unbounded support conditions.
method Examined two cases: bounded support with known and unknown support sets, and unbounded support with smooth density function.
result kNN density estimation is minimax optimal under certain conditions and better than kernel density estimation in some cases.
Score-based diffusion models achieve optimal error bounds under non-parametric assumptions.
problem Improving the minimax optimality of score-based diffusion models.
method Kernel-based score estimation and early stopping strategy.
result Achieves minimax optimal error bounds under sub-Gaussian and Sobolev space assumptions.
Study problem-dependent rates in statistical learning theory, achieving optimal generalization error bounds.
problem Generalization error in statistical learning theory.
method Uniform localized convergence framework.
result Optimal generalization error bounds for various learning problems.
New bounds show current methods overestimate system parameter errors.
problem Current bounds overestimate parameter errors in system identification.
method Utilized asymptotic normality and second-order decomposition.
result Obtained finite-sample bounds matching optimal rates up to constants.
New method gives provable error bounds for neural nets under distribution shift.
problem Proving reliable error bounds for neural networks under distribution shift.
method Optimizing a classifier to disagree with another, using a new 'disagreement loss'.
result Valid error bounds with comparable accuracy to competitive methods.
The paper provides mean-square error bounds for stochastic approximation algorithms.
problem Error bounds for recursive equations with Markovian disturbances.
method Analysis of mean-square error for stochastic approximation algorithms.
result Mean-square error achieves the optimal rate of O(1/n) under certain conditions. Many machine learning tasks can be formulated as Regularized Empirical Risk Minimization (R-ERM), and solved by optimization algorithms such as gradient descent (GD), stochastic gradient descent (SGD), and stochastic variance reduction (SVRG). Conventional analysis on these optimization algorithms focuses on their conv…
Optimal Gaussian noise mechanisms achieve nearly optimal error in unbiased mean estimation.
problem Efficiently estimating the mean of high-dimensional data while preserving privacy.
method Differential privacy mechanisms with Gaussian noise, focusing on optimal covariance.
result Gaussian noise mechanisms achieve nearly optimal error among all private unbiased mean estimation mechanisms.
Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generalization bounds is that they hold only in expectation. Generalization with high probability has been established in a landmark paper of Bousque…
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.
New research shows many batch selection methods for training work just as well as full batch training.
problem Finding optimal batch selection methods for training.
method Analysis of mini-batch Gradient Descent (GD) and Stochastic GD (SGD) with various batch selection rules.
result All mini-batch schedules, including deterministic ones, generalize optimally for smooth Lipschitz-convex/nonconvex/strongly-convex loss functions.
This research evaluates generalization measures in deep learning.
problem Understanding why deep learning models generalize well despite small training error.
method Empirical evaluation of generalization bounds and measures.
result Generalization measures should be evaluated using distributional robustness.
New error bound for diffusion models without dimensionality constraints.
problem Error estimation in diffusion generative models without dimensionality constraints.
method Derive dimension-free error bound using a smooth test functional.
result Explicit, dimension-free bound on generated vs true data distributions.
In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the…
Unified learning bound for covariate and concept shifts.
problem Generalization under distribution shift in machine learning.
method Support-agnostic definitions of covariate and concept shifts using entropic optimal transport, leading to a unified error bound applicable to various loss functions and label spaces.
result Development of estimators for shifts with concentration guarantees and the DataShifts algorithm for quantifying and estimating the error bound.
Develops bounds predicting deep learning generalization using optimal transport.
problem Discrepancy between theoretical error bounds and empirical observations in deep learning.
method Margin-based generalization bounds with optimal transport costs.
result Theoretical bounds robustly predict generalization error on large datasets.