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.
Method estimates LLM error rates using Pareto optimization.
problem Quantifying error rates in text-generating models.
method Pareto optimization for generating risk scores.
result Risk scores correlate well with true error rates.
Study shows how classifiers can approach Bayes error in high-dimensional settings.
problem Generalization error in high-dimensional perceptrons.
method Proved a formula for generalization error using convex optimization and observed that logistic and hinge regression can approach Bayes error closely.
result Logistic and hinge regression can approach Bayes-optimal generalization error closely in high-dimensional settings.
This article analyzes the weak error of SGD optimization schemes.
problem Analyzing the error in SGD optimization schemes with respect to a test function.
method Weak error analysis for SGD type optimization schemes.
result The weak error decays at the same speed as in the strong sense.
Optimal classification rules control error rates in multiclass mixture models.
problem Classifying observations in multiclass mixture models while controlling error rates.
method Finding optimal classification rules by searching an optimal region in the observation space, using Maximum A Posteriori (MAP) rule and heuristic computation.
result The FDR-like optimal rule can be significantly less conservative than thresholded MAP rules.
We analyze errors in filtering algorithms using optimal transport.
problem Estimation errors in optimal transport-based filtering algorithms.
method Systematic analysis of estimation errors for conditional Brenier maps.
result Demonstrates effectiveness and practical potential of the optimal transport filtering algorithm.
Optimizes calibration error estimators for better classifier trustworthiness.
problem Lack of guidance on selecting and tuning calibration error estimators.
method Reformulates calibration estimation as a regression problem with i.i.d. input pairs.
result Demonstrates the effectiveness of optimized calibration estimators on image classification tasks.
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.
Optimal number of voters for a voting ensemble can be estimated from the distribution of classifier errors.
problem Finding the optimal number of voters for a voting ensemble to minimize error rate.
method Estimate the distribution of classifier errors and infer error rates for different numbers of voters.
result Lower-variance estimates of error rates can be obtained by inferring them for different numbers of voters.
LoCoV reduces portfolio optimization errors from sample covariance matrices.
problem Large errors in sample covariance matrix for optimal portfolio weights.
method LoCoV (low dimension covariance voting) algorithm to reduce these errors.
result LoCoV outperforms classical methods in portfolio optimization experiments.
Post-processing predictors reduces calibration errors for decision-making.
problem Predictors with low calibration error for machine learning may have high error for decision-making.
method Post-processing with ε distance to calibration adds noise to make predictions differentially private.
result Post-processing achieves O(√ε) ECE and CDL, asymptotically optimal.
This paper analyzes SGD with increasingly weighted averaging for optimization and generalization.
problem Improving optimization and generalization for non-strongly convex objectives.
method Comprehensive analysis of increasingly weighted averaging schemes for convex, strongly convex, and non-convex objectives.
result The weight α affects both optimization and generalization errors, revealing a trade-off. 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 shows how gradient concentration helps in learning from inexact data.
problem Learning from inexact and stochastic training data.
method Combines probabilistic gradient concentration with inexact optimization techniques.
result Derives sharp test error guarantees for learning.
MiMuon optimizer improves generalization for large models by reducing generalization error.
problem Improving generalization of Muon optimizer for large models.
method Enhanced Muon optimizer using orthogonalization of gradient, proving lower generalization error.
result MiMuon optimizer has a lower generalization error of O(N1) compared to Muon's O(NκT1). 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,…
We characterize the asymptotic performance of nonparametric one- and two-sample testing. The exponential decay rate or error exponent of the type-II error probability is used as the asymptotic performance metric, and an optimal test achieves the maximum rate subject to a constant level constraint on the type-I error pr…
Optimal AFs minimize RFR test error and sensitivity.
problem Finding optimal AFs for RFR to minimize test error and sensitivity.
method Closed-form solution for AFs minimizing test error and sensitivity under different functional parsimony.
result Optimal AFs can be linear, saturated linear, or Hermite polynomial expressions.
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).
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.
We find the optimal error for a constrained regression model under a linear model.
problem Minimizing error while adhering to demographic parity constraints.
method Proposed a minimax optimal error analysis for a demographic parity-constrained regression problem within a linear model.
result The minimax optimal error is characterized by $Θ( rac{dM}{n})$.
Optimal estimator derived for partially observable LTI systems.
problem Optimal estimator for partially observable LTI systems.
method State-space representation for derivation of optimal estimator.
result Derivation of minimum error variance estimator for partially observable LTI systems.
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.
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.
Optimizes prediction error method for time-varying models.
problem Achieving optimal prediction error rates for time-varying models.
method Nonlinear least squares method for time-varying parametric models.
result First rate-optimal non-asymptotic analysis for time-varying models.
New framework reduces private mean estimation error with optimal efficiency.
problem Locally private mean estimation of high-dimensional vectors.
method ProjUnit framework: random projections, normalization, and optimal algorithm execution in lower dimensions.
result Optimal error up to a 1+o(1)-factor with computational efficiency and low communication complexity.
Study model selection in batch policy optimization with three error sources.
problem Learn a policy competitive with the best model class in batch policy optimization.
method Formalized in contextual bandit setting with linear model classes, addressing approximation error, statistical complexity, and dataset shift.
result No algorithm can optimally trade-off all three error sources, but relaxing any one enables near-oracle inequalities for the others.
This study is aimed at answering the famous question of how the approximation errors at each iteration of Approximate Dynamic Programming (ADP) affect the quality of the final results considering the fact that errors at each iteration affect the next iteration. To this goal, convergence of Value Iteration scheme of ADP…
Applying deep neural networks (DNNs) in mobile and safety-critical systems, such as autonomous vehicles, demands a reliable and efficient execution on hardware. Optimized dedicated hardware accelerators are being developed to achieve this. However, the design of efficient and reliable hardware has become increasingly d…
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.
Optimal machine learning requires interpolating training data in high-dimensional linear regression.
problem Achieving optimal predictive risk in overparameterized linear regression models.
method Analyzing proportional asymptotics of random design and label noise variance.
result Optimal performance in linear regression requires fitting training data to higher accuracy than inherent noise.
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.
Bayes-optimal learning of deep random networks with Gaussian weights is studied.
problem Learning a target function corresponding to a deep, extensive-width, non-linear neural network with random Gaussian weights.
method Closed-form expressions for Bayes-optimal test error, ridge regression, kernel and random features regression are computed.
result Optimally regularized ridge regression and kernel regression achieve Bayes-optimal performances, while logistic loss yields a near-optimal test error for classification.
Robust estimators for Gaussian sparse tasks with optimal error under contamination.
problem Robust mean estimation, PCA, and linear regression in the presence of Huber contamination.
method Novel multidimensional filtering method for sparse regime.
result Optimal error guarantees within constant factors for Gaussian robust k-sparse mean estimation. Proposes a new framework to optimize portfolios with reduced estimation errors.
problem Estimation errors in multiperiod mean-variance portfolio optimization.
method Reference-regulated multiperiod mean-variance (RRMV) framework.
result Improves portfolio stability and out-of-sample Sharpe ratios.
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.
Meta learning of optimal classifier error rates allows an experimenter to empirically estimate the intrinsic ability of any estimator to discriminate between two populations, circumventing the difficult problem of estimating the optimal Bayes classifier. To this end we propose a weighted nearest neighbor (WNN) graph es…
Learning reward functions can lead to poor policy performance despite low error.
problem Low error in learned reward functions does not guarantee low regret in policy performance.
method Mathematical analysis of reward learning and policy optimization.
result A low expected test error of the reward model guarantees low worst-case regret, but error-regret mismatch can occur with certain data distributions.
Adversarial training augments the training set with perturbations to improve the robust error (over worst-case perturbations), but it often leads to an increase in the standard error (on unperturbed test inputs). Previous explanations for this tradeoff rely on the assumption that no predictor in the hypothesis class ha…
The paper investigates overfitting in hyperparameter optimization.
problem Overfitting in hyperparameter optimization (overtuning).
method Formal definition, large-scale reanalysis of HPO benchmark data, analysis of factors affecting overtuning.
result Overtuning is more common than previously assumed, leading to worse generalization error in 10% of cases.
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.
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.
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…
New method tackles composite optimization with error feedback.
problem Challenges in distributed machine learning training and message compression.
method Combines Dual Averaging with EControl for composite optimization.
result First strong convergence analysis for composite optimization with error feedback.
Proposes reducing random error in stochastic optimization by variance regularization.
problem Random error accumulation in stochastic optimization algorithms.
method Regularizes learning-rate based on mini-batch variances.
result Speeds up convergence and stabilizes stochastic optimization.
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. Paper optimizes clustering for multi-layer networks and discrete mixtures.
problem Optimizing clustering in multi-layer networks and discrete mixtures.
method Two-stage method: tensor-based initialization and likelihood-based refinement.
result Achieves minimax optimal error rate for multi-layer networks and discrete mixtures.
TCE measures calibration error with a test-based approach.
problem Measuring calibration error of probabilistic binary classifiers.
method TCE uses a novel loss function based on a statistical test.
result TCE offers clear interpretation, consistent scale, and enhanced visual representation.