Simple analysis for fast rates in empirical minimization with concave losses and convex regularization.
problem Fast rates in empirical minimization with concave losses and convex regularization.
method Simple analysis using covering number and concentration inequality.
result First result of fast rates with high probability for exponential concave empirical risk minimization.
Improved sample complexity for diffusion models without needing empirical risk minimizers.
problem Theoretical limitations in sample complexity for diffusion models.
method Structured decomposition of score estimation error, eliminating dependence on neural network parameters.
result Achieved sample complexity bound of O(ε^(-4)) without empirical risk minimizer access.
Paper analyzes time series prediction using empirical risk minimization.
problem Optimizing 1-step-ahead prediction for time series.
method Empirical risk minimization applied to recursive algorithms for time series forecasting.
result Empirical risk minimization achieves optimal predictive performance.
The paper analyzes the performance of empirical risk minimization for p-norm linear regression.
problem Empirical risk minimization on 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.
New learning algorithm for real analytic functions without gradient descent.
problem Learning real analytic functions without gradient descent.
method Taylor approximation and sampling data distribution.
result Nonuniform learning result for real analytic functions.
New method estimates Schrödinger bridge potentials via empirical risk minimization.
problem Estimating Schrödinger bridge potentials from samples.
method Rewriting Schrödinger system as a fixed-point equation and estimating the potential via empirical risk minimization.
result Uniform concentration of empirical risk around population counterpart under sub-Gaussian assumptions.
Prove non-asymptotic bounds for minimal risk in statistical learning
problem Estimating minimal risk in statistical learning
method Using concentration inequalities
result Non-asymptotic bounds for minimal risk
Sharp bounds derived for minimizing empirical variance.
problem Minimizing empirical variance over functional classes.
method Sharp non-asymptotic bounds derived under mild conditions.
result Fast convergence rates achieved including optimal non-parametric rates.
Corrects sample selection bias in empirical risk minimization using importance sampling.
problem Statistical learning with biased training data.
method Weighted empirical risk minimization using importance sampling.
result Generalization capacity preserved with estimated importance weights.
Solves empirical risk minimization for relational data using graph sampling.
problem Empirical risk minimization for relational data.
method Graph sampling theory, stochastic gradient descent, automatic differentiation.
result Automatic unbiased stochastic gradients for relational data.
Paper shows robust estimators converge to true risk minimizers at optimal rates.
problem Understanding asymptotic properties of robust risk minimizers.
method Investigates robust analogues of empirical risk minimization, focusing on median of means estimator.
result Robust minimizers converge to true minimizers at optimal rates and have similar asymptotic variance.
Study on estimating class probabilities using empirical risk minimization.
problem Estimating class probabilities within binary classification.
method Empirical risk minimization (ERM) for class probability estimation.
result The estimator converges to true class probabilities under certain conditions.
Empirical Bayes minimizes average regret over problem instances.
problem Designing bandit algorithms with strong theoretical guarantees that perform well in practice.
method Minimizing empirical Bayes regret by optimizing over a sample distribution.
result Significant reductions in Bayes regret for state-of-the-art bandit algorithms.
A new SGD framework reduces empirical risk by favoring higher loss observations.
problem Minimizing empirical risk in machine learning problems.
method Develops a biased gradient estimator for stochastic optimization.
result Minimizes an ordered modification of the empirical average loss.
Paper tackles heavy-tailed data without finite variance, proposing robust risk minimization.
problem Empirical risk minimization under heavy-tailed data with finite p-th moment. method Minimizes risk values robustly estimated via Catoni's method, using generalized generic chaining.
result Shows better performance of optimizer based on empirical risks via Catoni-style estimation.
The paper tackles fairness in machine learning by incorporating it into empirical risk minimization.
problem Ensuring fairness in classifier outcomes by preventing sensitive variables from unfairly influencing results.
method Empirical risk minimization with a fairness constraint that maintains approximately constant conditional risk with respect to the sensitive variable.
result The approach is statistically consistent and can be applied to kernel methods and linear models with simple preprocessing steps.
Paper studies convergence rates from surrogate risk minimizers to Bayes optimal classifier.
problem Analyzing the convergence rates of surrogate risk minimizers to the Bayes optimal classifier.
method Introducing consistency intensity to characterize surrogate loss functions and using it to derive convergence rates.
result Empirical surrogate risk minimizers converge faster to the Bayes optimal classifier under certain conditions.
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.
Paper bounds excess risk in robust empirical risk minimization for heavy-tailed distributions.
problem Risk bounds for robust empirical risk minimization in heavy-tailed distributions.
method Proposes robust proxies for expectation to bound excess risk.
result Excess risk of robust estimators can converge to 0 at fast rates.
STORM enables edge computing for empirical risk minimization.
problem Training models on edge devices for streaming data.
method Online sketching for empirical risk minimization.
result STORM can estimate least-squares objective accurately.
Study shows convergence rate for empirical minimizer of unbounded functions with fast growth.
problem Convergence rate of empirical minimizer for unbounded functions with fast growth.
method Analyzes L1-distance convergence rate of the empiric minimizer for coercive functions sampled with noise. result Convergence rate is bounded above by ann−1/q, where q is the dimension and an=o(nε) for every ε>0. Sharp bounds on ERM's minimal error in regression.
problem Understanding ERM's performance in regression tasks.
method Sharp lower bounds for ERM in random and fixed design settings.
result ERM's performance depends on the global or local complexity of the model.
Recently theoretical guarantees have been obtained for matrix completion in the non-uniform sampling regime. In particular, if the sampling distribution aligns with the underlying matrix's leverage scores, then with high probability nuclear norm minimization will exactly recover the low rank matrix. In this article, we…
We develop a family of accelerated stochastic algorithms that minimize sums of convex functions. Our algorithms improve upon the fastest running time for empirical risk minimization (ERM), and in particular linear least-squares regression, across a wide range of problem settings. To achieve this, we establish a framewo…
The paper evaluates biased methods for alpha-divergence minimization.
problem The impact of bias on solutions found for alpha-divergence minimization.
method Empirical evaluation of biased methods for alpha-divergence minimization, focusing on bias effects and dimensionality.
result Solutions are biased towards KL-divergence minimizers and require impractical computation in high dimensions to minimize alpha-divergence.
New regularization method reduces support of empirical risk minimization solutions.
problem Regularization in empirical risk minimization with relative entropy.
method Introduces Type-II regularization, characterizes solutions, analyzes properties of relative entropy.
result Type-II regularization collapses solution support into reference measure's support.
We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sa…
ERM with f-divergence regularization yields unique solution.
problem Optimizing empirical risk with f-divergence. method Mild conditions on f lead to unique optimal measure. result Equivalence of ERM-fDR to different f-divergence regularization. Optimizes bilevel empirical risk minimization with improved oracle calls.
problem Optimizing bilevel empirical risk minimization problems.
method Proposes a bilevel extension of the SARAH algorithm.
result Demonstrates improved oracle calls to achieve stationarity.
Noise-ignorant empirical risk minimization achieves state-of-the-art performance on noisy data.
problem Learning with noisy labels in multi-class classification problems.
method Introducing relative signal strength (RSS) to quantify transferability and applying Noise Ignorant Empirical Risk Minimization (NI-ERM).
result NI-ERM achieves state-of-the-art performance on CIFAR-N data challenge.
Improved multi-group learning with group-realizable concepts.
problem Enhancing multi-group learning efficiency.
method Empirical risk minimization over group-realizable concepts.
result Improved sample complexity in group-realizable settings.
Accelerates machine learning algorithms for sparse data.
problem Efficiently solving composite convex minimization problems.
method Accelerated dual-averaging primal-dual method for composite convex minimization.
result Demonstrates advantages in handling sparse data both theoretically and empirically.
We develop an approach to risk minimization and stochastic optimization that provides a convex surrogate for variance, allowing near-optimal and computationally efficient trading between approximation and estimation error. Our approach builds off of techniques for distributionally robust optimization and Owen's empiric…
New approach avoids excess empirical risk in domain generalization.
problem Learning models that generalize to unseen distributions from diverse data sets.
method Minimizes penalty under constraint of optimal empirical risk, leveraging rate-distortion theory.
result Significant improvements in domain generalization performance across multiple methods.
Empirical risk minimizers can be non-monotonic in learning curves.
problem Understanding the behavior of learning curves for empirical risk minimizers.
method Introducing risk monotonicity and analyzing its implications for various learners.
result Standard learners that minimize empirical risk can be non-monotonic regardless of training sample size.
The paper proves deep learning can be robust with certain loss functions.
problem The robustness of deep learning models under flawed data.
method Empirical-risk minimization with unbounded, Lipschitz-continuous loss functions.
result These loss functions provide efficient prediction under minimal data assumptions.
A method for classification using pairwise similarities and unlabeled data.
problem Handling pairwise similarities and unlabeled data for classification.
method Empirical risk minimization approach to create an unbiased risk estimator.
result Derives an unbiased risk estimator for handling both similarities and unlabeled data.
Online TERM improves robustness and fairness in streaming data.
problem Streaming data's lack of worst-case fairness and robustness in ERM.
method Proposes an online TERM formulation to balance average-case accuracy with worst-case fairness and robustness.
result Negative tilting effectively suppresses outlier influence, positive tilting improves recall with minimal precision loss.
PF-based FSO methods improve on SGD and IPM for large-scale empirical risk minimization.
problem Optimizing large-scale empirical risk minimization problems efficiently.
method Developed PF-based stochastic optimizers (PFSOs) based on FSO methods.
result PFSOs outperform SGD, vanilla IPM, and KF-type FSO methods in stability, speed, and flexibility.
Analyzes empirical risk minimization in finance, showing effectiveness and generalization issues.
problem Analyzing empirical risk minimization in finance for optimal hedging and investment decisions.
method Classical statistical machine learning techniques and non-asymptotic estimates based on Rademacher complexity.
result Over-training leads to anticipative decisions, but non-asymptotic estimates show convergence for large training sets.
Empirical study of IRMv1, an invariant risk minimization framework.
problem Learning predictors invariant to spurious correlations across different training environments.
method Extending ColoredMNIST experiment to various settings.
result IRMv1 performs better as spurious correlation varies more widely.
The paper analyzes local minima in high-dimensional empirical risk minimization.
problem Understanding local minima in high-dimensional data models.
method Using Kac-Rice formula and proportional asymptotics, the paper derives bounds on local minima.
result Sharp asymptotics on estimation and prediction errors are derived.
New method uses robust estimators for Newton's method in empirical risk minimization.
problem Improving robustness in empirical risk minimization.
method Robust Newton's method with gradient and Hessian replaced by robust estimators.
result Faster convergence rates in high-dimensional settings.
Optimal bounds for exp-concave stochastic minimization in terms of effective dimension.
problem Finding optimal statistical and computational complexity for exp-concave stochastic minimization.
method Derives optimal bounds using effective dimension and sketching techniques.
result Reveals connections between algorithmic stability and ridge leverage scores.
Dual optimization connects ERM-fDR to normalization function.
problem Empirical risk minimization with f-divergence regularization.
method Dual formulation, Legendre-Fenchel transform, implicit function theorem, nonlinear ODE.
result Computational method to calculate normalization function efficiently.
Simplified screening tests for data points in optimization.
problem Discarding irrelevant data points in empirical risk minimization.
method Designing loss functions and regularizing convex losses to induce sparsity, using ellipsoidal approximations.
result Automatic discarding of data samples without losing optimization guarantees.
New algorithms achieve uniform stability for empirical risk minimization.
problem Designing uniformly stable optimization algorithms for empirical risk minimization.
method Black-box conversion of smooth optimization algorithms and development of Mirror Descent for smooth optimization.
result Optimal algorithms with uniform stability and convergence rates for smooth optimization.
Paper improves privacy in ERM with faster algorithms and broader applicability.
problem Privacy-preserving machine learning with empirical risk minimization.
method Develops faster algorithms for differentially private ERM in various settings.
result Achieves optimal or near-optimal utility bounds with less gradient complexity.