The paper analyzes the excess risk of PCA and provides a precise characterization.
problem Understanding the excess risk of principal component analysis (PCA).
method Established a central limit theorem for PCA error and derived the excess risk distribution.
result Obtained a non-asymptotic upper bound on the excess risk of PCA.
In statistical learning theory, convex surrogates of the 0-1 loss are highly preferred because of the computational and theoretical virtues that convexity brings in. This is of more importance if we consider smooth surrogates as witnessed by the fact that the smoothness is further beneficial both computationally- by at…
The paper explores the information-theoretic nature of excess risk in machine learning.
problem Understanding the excess risk in machine learning models.
method Formulates the minimax excess risk as a zero-sum game and modifies it to allow swapping of the order of play.
result Proves that under certain conditions, the duality gap is zero, allowing for the application of Bayesian results to provide bounds on minimax excess risk.
The paper analyzes the generalization performance of spectral clustering algorithms and proposes new methods to improve their effectiveness.
problem Theoretical analysis of spectral clustering's generalization performance.
method Theoretical analysis and development of new spectral clustering algorithms.
result The excess risk bounds of spectral clustering algorithms have a O ( 1 / n ) \mathcal{O}(1/\sqrt{n}) O ( 1/ n ) convergence rate. Gibbs-ERM learning is a natural idealized model of learning with stochastic optimization algorithms (such as Stochastic Gradient Langevin Dynamics and ---to some extent--- Stochastic Gradient Descent), while it also arises in other contexts, including PAC-Bayesian theory, and sampling mechanisms. In this work we study …
Study non-asymptotic bounds for robust estimators under misspecified models.
problem Evaluate performance of robust estimators under adversarial conditions.
method Propose a general approach to adversarial risk analysis, including investigations on generalization and approximation errors.
result Establish non-asymptotic upper bounds for adversarial excess risk under Lipschitz loss functions.
New method estimates model risk without knowing function class.
problem Evaluating model risk for complex, opaque models.
method Wild refitting with Bregman losses and randomized symmetrization.
result Valid upper bound on excess risk for opaque models.
The paper analyzes the generalization of deep neural networks for metric and similarity learning.
problem Lack of rigorous understanding of generalization performance in metric and similarity learning.
method Derive explicit form of true metric, construct structured deep ReLU neural network, establish excess risk bounds.
result Explicit excess risk bounds for metric and similarity learning are derived.
Lower bounds show OLS outperforms basis pursuit in overparameterized linear regression.
problem Excess risk of sparse interpolating procedures in overparameterized linear regression.
method Proved lower bounds on excess risk for OLS and basis pursuit.
result Excess risk of basis pursuit can converge at an exponentially slower rate than OLS.
Upper bounds and lower bounds show ERM outperforms DG methods in various settings.
problem Limitations of domain generalisation methods in various settings.
method Upper bounds and lower bounds on excess risk of ERM, and analysis of DG settings.
result It is not possible to significantly outperform ERM in DG settings.
Last SGD iterate bounds for overparameterized linear regression.
problem Analyzing the last iterate risk bounds of SGD with decaying stepsize for overparameterized linear regression.
method Problem-dependent analysis of last iterate risk bounds of SGD with geometrically decaying stepsize.
result Proved nearly matching upper and lower bounds on the excess risk for last iterate SGD with geometrically decaying stepsize.
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.
Deep linear networks can closely approximate interpolants without improving risk.
problem Understanding the risk bounds of deep linear networks compared to minimum ℓ 2 \ell_2 ℓ 2 -norm solutions. method Bounding excess risk of interpolating deep linear networks trained using gradient flow.
result Deep linear networks can closely approximate or match minimum ℓ 2 \ell_2 ℓ 2 -norm solutions in terms of risk. We consider the Hypothesis Transfer Learning (HTL) problem where one incorporates a hypothesis trained on the source domain into the learning procedure of the target domain. Existing theoretical analysis either only studies specific algorithms or only presents upper bounds on the generalization error but not on the exc…
Repeated self-distillation improves model performance significantly.
problem How much gain is possible by applying multiple steps of self-distillation?
method Investigated linear regression tasks, applied multiple steps of self-distillation, analyzed excess risk reduction.
result Multi-step self-distillation reduces excess risk by a factor as large as d d d , where d d d is the input dimension. Paper analyzes SGHMC for non-convex optimization with discontinuous gradients.
problem Training neural networks with ReLU activation.
method Non-asymptotic convergence analysis of SGHMC with discontinuous gradients.
result Explicit upper bounds for expected excess risk in non-convex optimization.
New framework analyzes deep learning optimization with finite width networks, revealing generalization gaps and excess risks.
problem Analyzing generalization error of deep learning with finite width networks.
method Formulating neural network training as transportation map estimation and analyzing via infinite dimensional Langevin dynamics.
result Achieves fast learning rate and minimax optimal rates for classification and regression problems.
Least squares estimator fails to achieve optimal risk in bounded distributions, but non-linear predictors can.
problem Optimal risk in bounded distributions for constrained least squares.
method Comparison of least squares and non-linear predictors.
result Non-linear predictors can achieve optimal risk O ( d / n ) O(d/n) O ( d / n ) in bounded distributions. Fine-tuning with pre-training data improves performance.
problem Limited training data for tasks.
method Theoretical analysis of excess risk bound and selection of pre-training data subset.
result Improvement in generalization performance with pre-training data.
Unified framework for ICL in causal and masked models.
problem Understanding ICL in masked language models and comparing it to causal models.
method Developed a statistical learning framework representing context by empirical measure and predicting using context and query.
result Upper bounds for masked and autoregressive objectives under Wasserstein-type regularity conditions.
Paper proposes a new framework to improve stability-based bounds in deep learning.
problem Explaining generalization in overparameterized neural networks.
method Decomposes excess risk dynamics into signal and noise components, applying stability-based bounds only to the noise.
result The decomposition framework improves stability-based bounds and explains generalization in neural networks.
This paper introduces Libra to analyze and optimize generalization in Federated Learning.
problem Inconsistent local optima in Federated Learning lead to poor generalization performance.
method Introduces Libra, a generalization dynamics analysis framework for algorithm-dependent excess risk minimization.
result Libra highlights the trade-offs between model stability and gradient norms in Federated Learning.
Researchers analyze the relationship between ML cost functions and the C-index in survival analysis.
problem Understanding the relationship between ML cost functions and the C-index in survival analysis.
method Provided C-index Fisher-consistency results and excess risk bounds for various cost functions in survival analysis.
result Identified conditions under which ML cost functions are consistent with the C-index.
New DP algorithm improves privacy and efficiency for convex optimization.
problem Efficient, DP algorithms for convex optimization with strong excess risk bounds.
method Output perturbation for a broad class of tilted loss functions.
result Near optimal DP excess risk and runtime bounds for convex optimization.
Improved algorithm reduces excess risk in selective learning.
problem Selective learning with windowed model selection.
method Hybrid Exponential Weights Algorithm and bounded-recall ERM.
result Achieves expected excess risk of O((log log |L| + log log n) / log n).
Gradient methods improve deep network training with tighter bounds and faster convergence.
problem Improving convergence and generalization of gradient methods for neural networks.
method Algorithmic stability analysis and novel bounds on excess risk.
result Gradient descent achieves optimal excess risk for deep nets with polynomial width conditions.
Deep learning with noisy gradient descent outperforms linear estimators in high dimensions.
problem Theoretical explanation of deep learning's superiority over linear methods.
method Theoretical analysis of excess risk of a deep learning estimator trained by noisy gradient descent.
result Deep learning achieves a faster learning rate than linear estimators, especially in high dimensions.
ERM performs well in feature learning with minimal feature maps.
problem Empirical risk minimization in feature learning with square loss.
method Asymptotic and non-asymptotic analysis of ERM performance.
result Excess risk quantiles of ERM match those of oracle procedure under certain conditions.
New tool detects 'fleeting modes' causing excess risk in financial markets.
problem Detecting portfolios with statistically significant excess risk in financial markets.
method Random Matrix Theory to identify 'fleeting modes' independent of underlying correlation structure.
result Fleeting modes exist in both futures and equity markets, and momentum is a source of excess risk.
We study the effect of imperfect training data labels on the performance of classification methods. In a general setting, where the probability that an observation in the training dataset is mislabelled may depend on both the feature vector and the true label, we bound the excess risk of an arbitrary classifier trained…
This work analyzes label embedding for large multiclass classification problems.
problem Label embedding for large multiclass classification problems.
method Analysis of label embedding in extreme multiclass classification, presenting an excess risk bound and showing a trade-off between computational and statistical efficiency.
result The statistical penalty for label embedding vanishes with sufficiently low coherence under the Massart noise condition.
Study excess risk in statistical inference with transformations.
problem Excess risk in estimating random variables from feature vectors and transformations.
method Characterize lossless transformations, develop test statistics, and information-theoretic bounds.
result Strongly consistent partitioning test statistic for lossless transformations.
Study analyzes EU in variational inference for Bayesian deep learning.
problem Analyzing epistemic uncertainty in variational inference for Bayesian deep learning.
method Theoretical analysis and derivation of relations between generalization error and EU measurements. Proposing a new objective function for VI.
result Proposed new objective function significantly improves EU evaluation over existing VI methods.
A framework is introduced for actively and adaptively solving a sequence of machine learning problems, which are changing in bounded manner from one time step to the next. An algorithm is developed that actively queries the labels of the most informative samples from an unlabeled data pool, and that adapts to the chang…
Defines MER for Bayesian learning, a gap between achievable and optimal performance.
problem Analyzing the best performance of Bayesian learning under generative models.
method Two methods for deriving upper bounds for MER: conditional mutual information and minimum estimation error.
result Quantifies the rate at which MER decays to zero with more data and relates it to model richness.
We simplify SSL by approximating redundant structural components with low-rank factorization.
problem Improving self-supervised learning performance with limited labeled data.
method Low-rank approximation of structural redundancy, introducing ε_s to measure approximation quality.
result The proposed method enhances SSL performance, as shown by theoretical and experimental validations.
New research shows that binary classification can be done with noisy data, but only if there are clean samples available.
problem Learning binary classification with instance and label dependent label noise.
method Theoretical analysis and empirical risk minimization.
result Empirical risk minimization achieves the optimal excess risk bound without additional assumptions.
The paper bounds the excess risk of deep neural networks for weakly dependent processes.
problem Learning with weakly dependent data using deep neural networks.
method Approximation of smooth functions by deep neural networks and a bound on excess risk.
result The excess risk bound for deep learning under weak dependence is close to O ( n − 1 / 2 ) \mathcal{O}(n^{-1/2}) O ( n − 1/2 ) for sufficiently smooth functions. New algorithm achieves optimal privacy and efficiency in non-Euclidean convex optimization.
problem Optimizing convex functions while maintaining privacy in non-Euclidean settings.
method Developed a linear-time algorithm for ℓ p \ell_p ℓ p -setups, leveraging geometric properties. result Optimal excess risk achieved in linear time for 1 < p ≤ 2 1 < p \leq 2 1 < p ≤ 2 . Paper addresses private online convex optimization with optimal algorithms in various geometries and high-dimensional bandits.
problem Private online convex optimization with streaming and continual release data.
method Proposes a private variant of online Frank-Wolfe algorithm with recursive gradients for variance reduction.
result Achieves optimal excess risk in linear time for 1 < p ≤ 2 1<p\leq 2 1 < p ≤ 2 and state-of-the-art excess risk for 2 < p ≤ ∞ 2<p\leq\infty 2 < p ≤ ∞ . New analysis shows diverse classes in pre-training boost NLP performance.
problem Improving sample efficiency in downstream NLP tasks.
method Proved that diverse classes in pre-training lead to better performance, using a large last linear layer singular value.
result Transfer learning excess risk improves with large i l d e ν ildeν i l d e ν and $O\left(\frac{1}{ ildeν \sqrt{n}}
ight)$ rate. Paper analyzes CRL generalization under non-i.i.d. settings, providing bounds for practical data reuse.
problem Limited theoretical understanding of CRL generalization under non-i.i.d. data conditions.
method Inspired by U-statistics, derives generalization bounds for CRL under non-i.i.d. settings.
result Required number of samples scales logarithmically with class covering number.
This paper analyzes multi-pass SGD for least squares, improving generalization bounds.
problem Improving generalization bounds for multi-pass SGD in the least squares problem.
method Develops an instance-dependent excess risk bound for least squares in the interpolation regime.
result SGD performs worse than GD instance-wise but saves computational time.
This study tightens bounds on how GD and SGD generalize in smooth convex optimization problems.
problem Understanding how GD and SGD generalize in smooth stochastic convex optimization problems.
method Provided tight excess risk lower bounds for GD and SGD under different conditions.
result Lower bounds suggest overfitting occurs and gaps remain in some cases.
Deep neural networks classify unbounded Gaussian mixture data without dimensionality issues.
problem Binary classification of unbounded Gaussian mixture data.
method Deep ReLU neural networks with non-asymptotic upper bounds and convergence rates.
result Deep ReLU networks can classify unbounded Gaussian mixture data without dimensionality constraints.
The study analyzes transfer learning using information theory.
problem Transfer learning in different distributions.
method Information-theoretic analysis, focusing on KL divergence.
result Upper bounds for general transfer learning algorithms and specific ERM.
New method for unbiased regression reduces excess risk.
problem Least squares regression with optimal solution and Hessian matrix.
method Averaged stochastic gradient descent with time-average estimator.
result Unbiased estimator with O(1/k) expected excess risk.
The paper analyzes kernel classifiers' performance in Sobolev spaces and proves their optimality.
problem Theoretical analysis of kernel classifiers' performance in Sobolev spaces.
method Deriving upper and lower bounds on classification excess risk using kernel regression theory and estimating interpolation smoothness.
result The proposed kernel classifier is optimal in Sobolev spaces, with theoretical bounds confirmed by real data.