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. Optimal private ERM and SCO with subquadratic gradient complexity.
problem Private optimization of non-smooth convex functions.
method Subquadratic gradient complexity algorithm using subsampling and smoothing.
result Achieved optimal excess empirical risk and population loss.
We provide non-asymptotic excess risk guarantees for statistical learning in a setting where the population risk with respect to which we evaluate the target parameter depends on an unknown nuisance parameter that must be estimated from data. We analyze a two-stage sample splitting meta-algorithm that takes as input ar…
The paper analyzes SMOTE for imbalanced classification, providing theoretical bounds and guidelines.
problem The challenge of imbalanced classification problems, especially with minority classes.
method Theoretical analysis of SMOTE and related oversampling techniques for minority classes.
result Derives concentration and excess risk bounds for SMOTE and kernel-based classifiers.
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.
The paper addresses differentially private learning for neural networks, focusing on risk bounds and algorithm feasibility.
problem Achieving differentially private learning for neural networks with theoretical guarantees.
method Developed algorithms and theoretical analysis for differentially private stochastic optimization of neural networks.
result Established theoretical bounds for excess population risk in differentially private learning of neural networks.
Paper addresses DP-SCO on heavy-tailed data, providing methods and results.
problem Designing DP algorithms for SCO on heavy-tailed data.
method Sample-and-aggregate framework, gradient smoothing and trimming.
result Achieved DP guarantees for various loss functions with different excess population risks.
Paper improves privacy-preserving optimization rates for convex functions.
problem Differentially private stochastic convex optimization.
method Algorithmic improvements for convex and strongly convex functions under TNC and non-negative loss.
result Excess population risk bounds for DP-SCO are faster than previous results.
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 . Gradient descent methods for deep ReLU networks achieve optimal generalization rates.
problem Generalization of gradient descent methods for deep neural networks
method Establishing minimax-optimal rates for GD and SGD with deep ReLU networks
result Gradient descent methods for deep ReLU networks achieve optimal generalization rates
New algorithms for differentially private optimization in convex and non-convex settings with near-optimal rates.
problem Differentially private optimization in convex and non-convex settings.
method Developed algorithms for convex and non-convex settings with near-optimal excess population risk.
result Achieved near-optimal rates in near-linear time for convex settings and nearly dimension independent rates for non-convex settings.
Paper revisits DP-SCO in Euclidean and ℓ p d \ell_p^d ℓ p d spaces, focusing on constrained and bounded sets.
problem Differentially private stochastic convex optimization in constrained and bounded sets in Euclidean and ℓ p d \ell_p^d ℓ p d spaces. method Proposes methods achieving excess population risks dependent on Gaussian width of the constraint set, and novel algorithms for unconstrained and heavy-tailed data.
result Theoretical results for DP-SCO in ℓ p d \ell_p^d ℓ p d spaces, including optimal bounds for strongly convex functions. We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d. samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on th…
The classical asymptotic theory for parametric M M M -estimators guarantees that, in the limit of infinite sample size, the excess risk has a chi-square type distribution, even in the misspecified case. We demonstrate how self-concordance of the loss allows to characterize the critical sample size sufficient to guarantee …
Study optimizes data collection from biased, costly sources to minimize risk.
problem Estimating population means and group-conditional means from multiple sources with varying costs and biases.
method Develops a sampling plan that maximizes effective sample size, paired with a post-stratification estimator.
result Achieves budgeted minimax optimal risk for estimating population means and group-conditional means.
New algorithms help machines forget old data efficiently.
problem Machine learning models can retain old data, hindering new learning.
method Developed TV-stable algorithms based on noisy SGD for convex and non-convex functions.
result Achieved efficient unlearning with upper and lower bounds on risk.
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…
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.
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.
Paper analyzes IHT's performance in sparse recovery problems.
problem Generalization performance of Iterative Hard Thresholding (IHT).
method Sparse generalization theory under algorithmic stability.
result IHT achieves convergence rates in sparse excess risk.
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.
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.
AGCA approximates angular variation on the unit sphere, reducing extremal dependence problems to eigenanalysis.
problem Approximating angular variation in multivariate extremes.
method Anchored geodesic component analysis (AGCA) approximates angular variation by great subspheres constrained to pass through a chosen reference direction.
result AGCA finds concentrated tail directions in daily equity-portfolio losses, explaining about 91% of anchored variation.
The paper tackles machine unlearning by designing efficient algorithms for adaptive query classes.
problem Designing efficient unlearning algorithms for machine learning models.
method Formalizes the problem and gives efficient unlearning algorithms for linear and prefix-sum query classes.
result Improved guarantees for stochastic convex optimization with reduced unlearning query complexity.
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.
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.
Transformers can learn mixture of linear models efficiently.
problem Existence and generalization of in-context learning for mixture models.
method Theoretical analysis and gradient flow optimization.
result Transformers achieve a prediction error of O ( d / n ) \mathcal{O}(\sqrt{d/n}) O ( d / n ) with high probability. Recently, a marked Poisson process (MPP) model for life catastrophe risk was proposed in [6]. We provide a justification and further support for the model by considering more general Poisson point processes in the context of extreme value theory (EVT), and basing the choice of model on statistical tests and model compa…
The landscape of empirical risk has been widely studied in a series of machine learning problems, including low-rank matrix factorization, matrix sensing, matrix completion, and phase retrieval. In this work, we focus on the situation where the corresponding population risk is a degenerate non-convex loss function, nam…
Paper improves clustering risk bounds for kernel k-means.
problem Improving clustering risk bounds for kernel k-means.
method Analyzes kernel k-means and Nyström approximation.
result Achieves nearly optimal excess clustering risk bound.
Paper develops a two-population model to assess longevity basis risk.
problem Mismatch between hedger's liability and hedging instrument causes longevity basis risk.
method Develops a two-population mortality model using Lee-Carter model and renewal process.
result Proposed model provides significant risk reduction when mortality jumps and sampling risk are considered.
New stability analysis improves generalization of multipass SGD.
problem Improper preconditioning affects generalization in multipass SGD.
method Developed on-average stability analysis for multipass SGD.
result Proper preconditioning yields optimal effective dimension dependence.
A new DP algorithm for weighted ERM protects sensitive data in predictive models.
problem Protecting sensitive personal information in predictive models trained via ERM.
method Proposes the first differentially private algorithm for weighted ERM with formal privacy guarantees.
result Demonstrates strong DP guarantees while maintaining robust performance in real-world data.
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.
New algorithms achieve optimal robustness in stochastic convex optimization under contamination.
problem Determining optimal rates for robust stochastic convex optimization under ε ε ε -contamination. method Developed novel algorithms achieving minimax-optimal excess risk under ε ε ε -contamination model without stringent assumptions. result Achieved minimax-optimal excess risk (up to logarithmic factors) under ε ε ε -contamination model. Improved analysis for extreme multi-class CRL with better sample complexity.
problem Theoretical sample complexity of CRL in extreme multi-class settings is poorly understood.
method Improved U-Statistics estimator to capture class concentration, proving O ( k ) \mathcal{O}(k) O ( k ) sample complexity. result Sample complexity is O ( k ) \mathcal{O}(k) O ( k ) for extreme multi-class learning, independent of class distribution. Study on excess mortality in Germany during 2020-21.
problem Analyzing excess mortality during the pandemic in Germany.
method Empirical study using official death counts.
result Provided conclusions for insurance businesses.
Local SGD proves efficient in overparameterized linear regression.
problem Efficiently learning overparameterized linear models in distributed settings.
method Distributed SGD (DSGD) with overparameterized models.
result Excess risk of SGD is smaller than ridge regression in the same sample complexity.
Study finds high cyber risk stocks generate significant excess returns.
problem Understanding and quantifying cyber risk's impact on stock returns.
method Machine learning algorithm measuring cyber risk proximity to a corpus.
result High cyber risk stocks generate an excess return of 18.72% p.a.
Study uses spectral risk for learning with heavy-tailed data.
problem Learning with heavy-tailed loss distributions.
method Spectral risk with Lipschitz-continuous density, derivative-free learning.
result Excess risk guarantees and improved performance over traditional methods.
The paper analyzes the performance of empirical risk minimization for p p p -norm linear regression.
problem Empirical risk minimization on p p p -norm linear regression. method Analyzes performance under various conditions and moment assumptions.
result High probability excess risk bounds for empirical risk minimizer, matching asymptotic rates.
Currency volatility shocks predict lower excess returns, and buying weak transmitters outperforms selling strong ones.
problem Predicting currency returns using volatility shocks.
method Constructed a dynamic, directed network of volatility connections using option-implied volatilities.
result Currencies that transmit more volatility shocks earn lower excess returns.
Excessive leverage, i.e. the abuse of debt financing, is considered one of the primary factors in the default of financial institutions. Systemic risk results from correlations between individual default probabilities that cannot be considered independent. Based on the structural framework by Merton (1974), we discuss …
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.
Improved algorithm finds second-order stationary points in non-convex optimization.
problem Minimizing non-convex objectives while preserving training data privacy.
method SpiderBoost framework with two gradient oracles: precise and less precise.
result Improved rates for finding second-order stationary points.
New algorithms avoid non-monotonic risk curves in statistical learning.
problem Non-monotonic behavior of risk curves in statistical learning.
method Derive risk-monotonic algorithms under weak assumptions.
result Risk monotonicity does not necessarily lead to worse excess risk rates.
The paper develops a theory for one-step Wasserstein-guided models for PDE-induced measures.
problem Theoretical understanding of generative models' accuracy in scientific computing.
method Regularity theory for optimal transport between doubling measures, excess-risk bounds.
result One-step Wasserstein-guided generative models can approximate PDE-induced measures with Hölder continuity.
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.