Introduces MWLD to measure loss inequality across groups.
problem Machine learning's focus on average loss can lead to large group loss discrepancies.
method Defines MWLD, relates it to fairness and robustness, and provides estimation methods.
result MWLD can be estimated efficiently under certain weighting functions and reduces loss variance without significant accuracy loss.
New theoretical framework improves error rates for sparse learning with convex regularization.
problem Improving error rates for sparse learning with convex regularization.
method Proposed a new theoretical framework using common assumptions to derive high-dimensional estimation bounds.
result Improved error rates for L1, Slope, and Group L1-L2 regularizations, matching or exceeding existing results.
Loss minimization leads to multicalibration for neural networks.
problem Ensuring fairness in predictions across multiple protected groups.
method Minimizing squared loss over neural networks of size n.
result Minimizing loss over neural nets of size n implies multicalibration for most values of n.
We present a new machine learning approach to estimate personalized treatment effects in the classical potential outcomes framework with binary outcomes. To overcome the problem that both treatment and control outcomes for the same unit are required for supervised learning, we propose surrogate loss functions that inco…
Paper introduces a new robust method for estimating Pareto tail index from grouped data.
problem Limited robust methods for estimating Pareto tail index from grouped data.
method Method of Truncated Moments (MTuM)
result Inferential justification and validation of MTuM through simulation study.
The paper introduces fair regression methods to predict real-valued outcomes while ensuring fairness.
problem Predicting real-valued outcomes while ensuring fairness with respect to protected attributes.
method Proposes schemes for fair regression under statistical parity and bounded group loss, applicable to various losses.
result The schemes provide theoretical guarantees on the optimality and fairness of the obtained solutions.
Feature noise causes loss discrepancies across groups even with equal data.
problem Loss discrepancies observed in learning procedures across different groups.
method Characterized the effect of feature noise on loss discrepancy in linear regression.
result Feature noise leads to loss discrepancy even when groups have equal data.
Calibrating classifiers reduces grouping loss using sufficiency criteria.
problem Grouping loss in probabilistic classifier calibration is often overlooked.
method Revisited Langford & Zadrozny's probing reduction approach and introduced Brier curves.
result The probing reduction approach reduces grouping loss and supports sufficient calibration.
Paper improves PAC-Bayes bounds for various loss types.
problem Improving PAC-Bayes bounds for different types of losses.
method Introducing new high-probability PAC-Bayes bounds for bounded and general tail behaviors losses, and extending to anytime-valid bounds.
result New fast-rate and mixed-rate bounds for losses with bounded ranges, and parameter-free bounds for losses with general tail behaviors.
New method estimates grouping loss in neural networks to improve confidence scores.
problem Improving confidence scores in neural networks to reflect true posterior probabilities.
method Proposed an estimator to approximate the grouping loss.
result Modern neural networks exhibit grouping loss, especially in distribution shifts.
We establish linear regret bounds for convex smooth losses using Fenchel-Young losses.
problem Establishing linear regret bounds for convex smooth losses.
method Constructing a convex smooth surrogate loss using Fenchel-Young losses generated by the convolutional negentropy.
result We derive a smooth loss with a linear surrogate regret bound.
The paper analyzes and proposes methods for privately sharing individual privacy losses using per-instance differential privacy.
problem The standard differential privacy framework provides a worst-case bound that may not accurately reflect individual privacy losses.
method The paper analyzes per-instance differential privacy and proposes methods to privately and accurately publish per-instance privacy losses.
result The methods privately and accurately publish per-instance differential privacy losses with minimal additional privacy cost.
The paper improves PAC-Bayes bounds for losses with finite moments.
problem Bounding generalization for losses with heavy tails and finite moments.
method Truncation method and PAC-Bayes bounds for unbounded losses with heavy tails and bounded variance.
result Bounds interpolate between slow and fast rates depending on the moment.
Reduces the cost of making fair models using differential privacy.
problem Ensuring fairness in machine learning models while maintaining differential privacy.
method Information-theoretic reductions to solve constrained optimization problems.
result First polynomial-time algorithms for ( ε , δ ) (ε, δ) ( ε , δ ) differential privacy with tight sample complexity bounds. This research improves PAC-Bayesian bounds for classification tasks using convexified loss.
problem Deriving generalization bounds for classification tasks with non-convex loss functions.
method Shift focus to misclassification excess risk bounds for PAC-Bayesian classification using convex surrogate loss and leveraging PAC-Bayesian relative bounds in expectation.
result Improved PAC-Bayesian bounds for classification tasks with convex surrogate loss.
New PAC-Bayes bounds for heavy-tailed losses using supermartingales.
problem Extending PAC-Bayes bounds to heavy-tailed losses.
method Using supermartingales and bounded variance assumption.
result PAC-Bayes generalization bounds for heavy-tailed losses.
New framework for data-driven hyperparameter tuning with structured loss.
problem Statistical foundations for multi-dimensional hyperparameter tuning remain limited.
method General framework using real algebraic geometry for semi-algebraic function classes.
result First general guarantees for multi-dimensional hyperparameter tuning.
Study improves H H H -consistency bounds for regression analysis.
problem Improving H H H -consistency bounds for regression analysis. method Generalized theorems and novel H H H -consistency bounds for various surrogate loss functions. result Derives principled surrogate losses for adversarial regression.
Study on H H H -consistency bounds for machine learning surrogates.
problem Estimating target loss error relative to surrogate loss error in machine learning.
method Developed H H H -consistency bounds for various surrogates and loss functions. result Stronger guarantees than existing methods, offering distribution-dependent and -independent bounds.
New aggregation strategy handles unbounded losses with regret bounds.
problem Online optimization with unbounded loss functions.
method Follow The Regularized Leader (FTRL) with φ-divergence.
result Worst regret bound for unbounded losses with alternative divergences.
Paper establishes a universal growth rate for smooth surrogate losses in classification.
problem Analyzing growth rates of consistency bounds for various surrogate losses.
method Proves square-root growth rate for smooth margin-based losses; extends to multi-class classification.
result Demonstrates a universal square-root growth rate for smooth comp-sum and constrained losses.
New bounds on neural network test loss derived from conditional information measures.
problem Estimating test loss of neural networks trained on limited data.
method Framework based on conditional information density between hypothesis and training set.
result Tail bounds on test loss decay as 1/n, improving over previous 1/sqrt{n} bounds.
The stochastic linear bandit problem proceeds in rounds where at each round the algorithm selects a vector from a decision set after which it receives a noisy linear loss parameterized by an unknown vector. The goal in such a problem is to minimize the (pseudo) regret which is the difference between the total expected …
Study large deviations in life insurance portfolios without identical distributions.
problem Large deviations in life insurance portfolios with bounded losses and variances.
method Upper bound from standard large deviations, counterexample for full large deviation principle.
result Exponential bound for average loss exceeding a threshold.
We use surrogate losses to obtain several new regret bounds and new algorithms for contextual bandit learning. Using the ramp loss, we derive new margin-based regret bounds in terms of standard sequential complexity measures of a benchmark class of real-valued regression functions. Using the hinge loss, we derive an ef…
We present surrogate regret bounds for arbitrary surrogate losses in the context of binary classification with label-dependent costs. Such bounds relate a classifier's risk, assessed with respect to a surrogate loss, to its cost-sensitive classification risk. Two approaches to surrogate regret bounds are developed. The…
Theoretical analysis of cross-entropy loss functions and their robustness.
problem Guarantees for using cross-entropy as a surrogate loss function.
method Theoretical analysis of a broad family of loss functions, including cross-entropy.
result First H H H -consistency bounds for comp-sum losses and smooth adversarial comp-sum losses. Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for m \mathbf{m} m -BAI. The paper sets lower bounds for adversarial robustness in multiclass classification.
problem Adversarial robustness in multiclass classification with arbitrary loss functions.
method Dual and barycentric reformulations for robust risk minimization.
result Sharp lower bounds for adversarial risks are computed efficiently.
Paper develops proper, lower-bounded losses for weakly supervised classification.
problem Weakly supervised classification with corrupted labels.
method Representation theorem for proper losses, derived condition for lower-boundedness, generalized logit squeezing.
result Proper and lower-bounded losses for weak-label learning.
Unified surrogate loss framework for multi-label learning with strong consistency guarantees.
problem Improving consistency and accounting for label correlations in multi-label learning.
method Introducing multi-label logistic loss and extending it to comprehensive multi-label comp-sum losses, proving strong consistency guarantees for any multi-label loss.
result Unified surrogate loss framework benefiting from strong consistency guarantees for any multi-label loss.
The overarching goal of this paper is to derive excess risk bounds for learning from exp-concave loss functions in passive and sequential learning settings. Exp-concave loss functions encompass several fundamental problems in machine learning such as squared loss in linear regression, logistic loss in classification, a…
New PAC-Bayes bounds for unbounded loss functions.
problem Generalization bounds for learning problems with unbounded loss functions.
method Introducing HYPE, a new notion for loss range, and deriving a novel PAC-Bayesian generalization bound.
result PAC-Bayes framework extended to unbounded loss functions.
New PAC-Bayes bounds for unbounded losses using Cramér-Chernoff techniques.
problem Developing bounds for unbounded losses in PAC-Bayesian settings.
method Introducing a new PAC-Bayes oracle bound using Cramér-Chernoff bounds and controlling random variable tails.
result Our bounds generalize and improve upon previous results, providing more informative and potentially tighter bounds.
Proposes Group Loss for deep metric learning to improve clustering and image retrieval.
problem Improving deep metric learning for better clustering and image retrieval.
method Group Loss based on label-propagation method enforcing embedding similarity across all samples of a group.
result Shows state-of-the-art results on clustering and image retrieval on several datasets.
Study of estimation errors in surrogate loss minimizers, providing stronger guarantees than existing methods.
problem Estimation errors in surrogate loss minimizers for various hypothesis sets.
method Detailed study of H \mathscr{H} H -consistency estimation error bounds, proving general theorems for distribution-dependent and independent settings. result Explicit bounds for zero-one and adversarial losses, showing enhancements under distributional assumptions.
New framework explains data augmentation's role in machine learning.
problem Understanding how data augmentation affects generalization and invariance learning.
method Information-theoretic framework based on mutual information bounds and orbit-averaged loss functions.
result Derives a new generalization bound decomposing the generalization gap into three interpretable terms.
This paper explains why distributional reinforcement learning is better than vanilla RL using small-loss bounds.
problem Understanding when and why distributional reinforcement learning (DistRL) is superior to vanilla reinforcement learning (RL).
method The paper uses small-loss bounds to explain the benefits of DistRL, proposing algorithms and proving bounds for different RL settings.
result Distributional reinforcement learning (DistRL) outperforms vanilla RL when optimal costs are small, as shown by small-loss bounds.
New bounds for bandits with graph feedback, improving previous results.
problem Adversarial multi-armed bandits with graph feedback, focusing on small-loss bounds.
method Developed algorithms with regret bounds i l d e O ( κ L ∗ ) \mathcal{ ilde{O}}(\sqrt{κL_*}) i l d e O ( κ L ∗ ) and i l d e O ( min { α T , κ L ∗ } ) \mathcal{ ilde{O}}(\min\{\sqrt{αT}, \sqrt{κL_*}\}) i l d e O ( min { α T , κ L ∗ }) . result Significant improvement and extension of previous results by Lykouris et al. (2018).
New bounds show polyhedral surrogates are optimal for generalization.
problem Proving generalization rates for polyhedral loss functions.
method Developed two general results for polyhedral surrogates.
result Polyhedral surrogates provide linear surrogate regret bounds, translating directly to target rates.
We study online aggregation of the predictions of experts, and first show new second-order regret bounds in the standard setting, which are obtained via a version of the Prod algorithm (and also a version of the polynomially weighted average algorithm) with multiple learning rates. These bounds are in terms of excess l…
PAC-Bayesian bounds for MLPs with cross entropy loss validated.
problem Generalization bounds for MLPs with cross entropy loss.
method Introduced probabilistic explanations and proved PAC-Bayesian bounds using ELBO.
result MLPs with cross entropy loss inherently guarantee PAC-Bayesian generalization bounds.
Enhanced H H H -consistency bounds derived under relaxed conditions.
problem Quantifying the relationship between zero-one estimation error and surrogate loss estimation error.
method Relaxing the condition on the surrogate loss conditional regret and presenting a general framework for establishing enhanced H H H -consistency bounds. result Derivation of more favorable H H H -consistency bounds in various scenarios. New bound relaxes uniform gradient norm assumptions for PAC-Bayesian bounds.
problem Generalization bounds with strict assumptions like uniformly bounded loss.
method Relax uniform bounds assumptions to on-average bounded loss and gradient norm.
result Proposes a new generalization bound with a surrogate of model complexity.
Optimal sampling bounds for various classification losses under different regularization terms.
problem Achieving optimal sampling complexity for classification losses under different regularization terms.
method Proved optimal sampling bounds for a broad class of Lipschitz continuous classification loss functions under various regularization terms.
result Proved k 2 / ε 2 k^2/\varepsilon^2 k 2 / ε 2 upper and lower bounds for ∥ ⋅ ∥ 2 / k \|\cdot\|_2/k ∥ ⋅ ∥ 2 / k regularization, and k / ε 2 k/\varepsilon^2 k / ε 2 upper and lower bounds for ∥ ⋅ ∥ 1 / k \|\cdot\|_1/k ∥ ⋅ ∥ 1 / k regularization. New algorithms avoid a dominant lower-order term in heavy-tailed loss settings.
problem Prediction with heavy-tailed losses without prior knowledge.
method Adaptive algorithms that avoid the maximum of losses as a lower-order term in regret.
result Improved regret bounds of O ( θ T log ( K ) ) \mathcal{O}(\sqrt{θT\log(K)}) O ( θ T log ( K ) ) and O ( θ log ( K T ) / Δ min ) \mathcal{O}(θ\log(KT)/Δ_{\min}) O ( θ log ( K T ) / Δ m i n ) . In this paper we refine the process of computing calibration functions for a number of multiclass classification surrogate losses. Calibration functions are a powerful tool for easily converting bounds for the surrogate risk (which can be computed through well-known methods) into bounds for the true risk, the probabili…
Optimizes exp-concave losses with a new risk bound.
problem Optimizing exp-concave losses with stochastic convex optimization.
method Empirical Risk Minimization with a unified geometric assumption and local norms.
result Provides an O ( d / n + log ( 1 / δ ) / n ) O( d / n + \log( 1 / δ) / n ) O ( d / n + log ( 1/ δ ) / n ) excess risk bound.