New bounds for LDP with heterogeneous privacy levels guaranteeing high probability of accuracy.
problem Statistical estimation under LDP with users having varying privacy levels.
method Developed finite sample upper bounds in ℓ_2-norm with high probability, complemented by lower bounds.
result Optimal guarantees for heterogeneous LDP in terms of probability and constants.
Sharp bounds for high-probability estimation of discrete distributions.
problem Estimating discrete distributions with high probability under χ2-divergence. method Sharp upper and lower bounds for the classical Laplace estimator, and characterization of minimax high-probability risk for any estimator.
result Sharp bounds for high-probability estimation of discrete distributions can be achieved through a simple smoothing strategy.
Wavelet-based online learning adapts to noisy Besov spaces with high probability.
problem Minimizing integrated squared error in Besov spaces with noisy observations.
method Adaptive wavelet-based online learning algorithm that dynamically adjusts to gradient noise.
result Achieves minimax-optimal integrated squared error with high probability.
This note shows how to transform high-probability to in-expectation guarantees in machine learning.
problem The challenge of constructing reliable machine learning models due to sampling randomness.
method Transforming high-probability to in-expectation guarantees using a witness condition for unbounded loss functions.
result A technical transformation method for generalization guarantees in machine learning.
New algorithm FLUTE achieves uniform-PAC convergence in RL with linear approx.
problem RL with linear function approximation lacks uniform-PAC guarantees.
method FLUTE algorithm with minimax value function estimator and multi-level partition scheme.
result Uniform-PAC convergence to optimal policy with high probability.
The study optimizes distribution estimation from samples with relative entropy error, adapting to sparse distributions.
problem Estimating discrete distributions with high-probability accuracy in relative entropy.
method Analysis of Laplace estimator and confidence-dependent smoothing techniques, including data-dependent smoothing.
result Optimal high-probability risk bounds for various estimators, including a new data-dependent smoothing method.
This work addresses the problem of regret minimization in non-stochastic multi-armed bandit problems, focusing on performance guarantees that hold with high probability. Such results are rather scarce in the literature since proving them requires a large deal of technical effort and significant modifications to the sta…
We derive concentration inequalities for differentially private median and mean estimators building on the "Propose, Test, Release" (PTR) mechanism introduced by Dwork and Lei (2009). We introduce a new general version of the PTR mechanism that allows us to derive high probability error bounds for differentially privat…
Active seriation recovers item order from noisy pairwise similarity measurements.
problem Recovering an unknown item ordering from noisy pairwise similarity measurements.
method Proposes an active seriation algorithm that provably recovers the latent ordering with high probability.
result Establishes optimal performance guarantees for successful recovery under a uniform separation condition.
The paper develops SGD for estimating operators from data.
problem Estimating operators from data in infinite-dimensional spaces.
method Regularized SGD with operator-valued kernels.
result Near-optimal convergence rates for prediction and estimation.
Improved SGD bounds for machine learning models with Markovian noise.
problem Uniform high-probability bounds for SGD under PL condition with Markovian noise.
method Combining Poisson equation for Markovian noise and probabilistic induction for almost-sure bounds.
result Matching 1/k decay rate for expected suboptimality. Develops model selection for bandits balancing adversarial and stochastic guarantees.
problem Model selection in bandit scenarios with simultaneous adversarial and stochastic high-probability regret.
method Nested policy classes, balanced candidate regret bounds, mis-specification tests.
result Best of both world guarantees in linear bandits with simultaneous adversarial and stochastic environments.
TD(0) with Polyak-Ruppert averaging achieves robust and fast convergence rates
problem TD(0) learning under Markovian sampling
method Polyak-Ruppert averaging with a single stepsize
result Simultaneous high-probability convergence guarantees for TD(0) iterates and PR average
Unified high-probability regret bounds for online convex optimisation with randomised gradient estimators.
problem Online convex optimisation with randomised gradient estimators for ℓq-Lipschitz losses. method FTRL with randomised two-point finite-difference gradient estimators based on cone-measure sampling from ℓr-spheres. result Unified high-probability regret bounds for all p,q,r∈[1,∞]. RS-NSGD improves SGD convergence for heavy-tailed noise.
problem Nonconvex optimization with heavy-tailed noise.
method Integrates direction normalization into subspace updates.
result Achieves better oracle complexity than full-dimensional normalized SGD.
A new algorithm solves semidefinite programs using Langevin diffusion.
problem Optimizing semidefinite programs with diagonal constraints.
method Langevin diffusion on a product manifold of spheres.
result Langevin algorithm achieves ε accuracy in Ω(ε^-5) iterations.
Paper provides statistical guarantees for GNNs in link prediction.
problem Link prediction accuracy in graph neural networks.
method Proposes a linear GNN architecture (LG-GNN) and derives statistical guarantees.
result LG-GNN produces consistent estimators for edge probabilities and has better detection of high-probability edges.
The paper extends conformal risk control to be valid with high probability over a growing calibration dataset.
problem Valid risk control over a growing calibration dataset.
method Quantile-based arguments for anytime-valid control.
result Guarantees remain valid with high probability over a cumulatively growing calibration dataset.
New stability framework relaxes boundedness assumptions for generalization bounds.
problem Overly restrictive assumptions for modern learning settings with heavy-tailed or unbounded losses.
method Develops a stability-based framework requiring only finite Lp moment conditions. result Sharp generalization bounds derived for various learning paradigms.
Paper proves robust estimators' generalization guarantees without dimensionality issues.
problem Generalization guarantees for Wasserstein distributionally robust models.
method Analyzes and extends existing guarantees to broader classes of models and regularized versions.
result Generalization guarantees hold without dimensionality issues and cover distribution shifts.
New algorithms improve stopping time for best arm identification.
problem Efficiently identifying the best alternative in experiments.
method Proposed algorithms with exponential-tailed stopping time.
result Proved that some algorithms never stop, leading to new methods.
For a certain class of distributions, we prove that the linear programming relaxation of k-medoids clustering---a variant of k-means clustering where means are replaced by exemplars from within the dataset---distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn a…
New algorithm accelerates optimization in non-convex problems with heavy-tailed noise.
problem Optimizing non-convex functions with heavy-tailed noise.
method Proposes a variance-reduced accelerated algorithm for optimization problems in the form of F(x)=EΞ∼D[f(x,Ξ)]. result Achieves a high-probability convergence rate of O(log(T/δ)T2p−11−p), faster than the lower bound Ω(T3p−21−p). Stochastic gradient methods converge for training wide PINNs.
problem Convergence of stochastic gradient descent in training over-parameterized PINNs.
method Established linear convergence of stochastic gradient descent/flow in training over-parameterized two-layer PINNs.
result Linear convergence with high probability for general activation functions.
Tensor CANDECOMP/PARAFAC (CP) decomposition is an important tool that solves a wide class of machine learning problems. Existing popular approaches recover components one by one, not necessarily in the order of larger components first. Recently developed simultaneous power method obtains only a high probability recover…
Paper develops PAC-Bayes bounds for unknown linear systems.
problem Learning controllers for unknown stochastic linear discrete-time systems.
method PAC-Bayes framework for data-dependent high probability bounds.
result Proposes efficient learning algorithms with theoretical guarantees.
This manuscript provides optimization guarantees, generalization bounds, and statistical consistency results for AdaBoost variants which replace the exponential loss with the logistic and similar losses (specifically, twice differentiable convex losses which are Lipschitz and tend to zero on one side). The heart of the…
We reformulate data-dependent constraints to ensure they are always met with high probability.
problem Ensuring fairness and stability in machine learning models with data-dependent constraints.
method Calibrated reformulation of constraints to guarantee satisfaction with a specified probability.
result Our method guarantees that fairness constraints are met at test time with high probability.
The paper analyzes Adam and SGD in nonstationary optimization, revealing tradeoffs between noise and drift.
problem Analyzing Adam and SGD in nonstationary optimization problems.
method Theoretical analysis of Adam and SGD under non-stationary stochastic objectives, separating two regimes.
result Characterizes the tradeoff between noise and drift in Adam and SGD, revealing when adaptive step-sizing is beneficial or harmful.
VSPS creates flexible prediction regions for multi-target regression with guaranteed coverage.
problem Uncertainty quantification in multi-target regression with complex distributions.
method Conditional normalizing flows with conformal calibration to identify dense regions.
result VSPS produces smaller, more informative prediction regions with robust coverage guarantees.
The paper analyzes the sample complexities for policy evaluation with linear function approximation.
problem Policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes.
method Investigates sample complexities for two policy evaluation algorithms: TD and TDC.
result Establishes high-probability sample complexity bounds for policy evaluation algorithms.
SyncRank recovers global ranking from noisy comparisons with theoretical guarantees.
problem Recovering a global ranking from noisy pairwise comparisons.
method Complex-valued data model and SDP relaxation for exact ranking recovery.
result SyncRank achieves exact ranking recovery with high probability above a critical noise threshold of O(sqrt(n / log n)).
Proposes sparse local and regional counterfactual rules for robust recourses.
problem Challenges in counterfactual explanations, especially stability, synthesis, and implementation.
method Probabilistic framework using Random Forest to derive sparse local and regional counterfactual rules.
result Effective recourses derived from high-density regions, providing sparse and robust counterfactual rules.
New algorithm finds critical points in non-convex optimization with heavy-tailed gradients.
problem Non-convex stochastic optimization with heavy-tailed gradient estimates.
method Gradient clipping, momentum, and normalized gradient descent.
result High-probability convergence to critical points with best-known rates.
PRS improves rejection sampling by learning better proposals.
problem High rejection rate in traditional rejection sampling.
method PRS uses a kernel estimator to learn better sampling proposals.
result PRS guarantees a low number of accepted samples.
New methods ensure feature importance rankings are correct with high probability.
problem Stability issues in feature importance scores due to random sampling.
method Hypothesis testing-based techniques to assess and verify the stability of top-ranked features.
result Ensures the most important features are correct with high-probability guarantees.
Paper defines and solves a problem in representation learning to ensure fairness with high confidence.
problem Learning fair representations with high confidence guarantees for all downstream tasks.
method Formally defines the problem, introduces FRG framework, proves high probability fairness, and demonstrates effectiveness empirically.
result FRG framework provides high-confidence guarantees for limiting unfairness across all downstream models and tasks.
New method reduces variance in stochastic optimization with high confidence.
problem Achieving high-probability guarantees in stochastic optimization with weaker noise assumptions.
method Stochastic proximal point method combining proximal subproblem solver and probability booster.
result Demonstrates convergence with low sample complexity under bounded variance assumptions.
Paper develops bounds for stochastic approximation with averaging.
problem Establish high-probability bounds for averaged stochastic approximation.
method Develops a general framework for non-asymptotic concentration bounds.
result Derives sharp bounds for averaged iterates and tightens existing results.
New method for predicting paths of unpredictable objects with high confidence.
problem Need for dependable uncertainty estimates in motion planning with diverse unpredictable objects.
method Blend online conformal prediction, multiple time series techniques, and heteroscedasticity addressing.
result Simultaneous forecasting bands that cover entire paths with high probability.
We propose an algorithm combining calibrated prediction and generalization bounds from learning theory to construct confidence sets for deep neural networks with PAC guarantees---i.e., the confidence set for a given input contains the true label with high probability. We demonstrate how our approach can be used to cons…
In this paper, we consider efficient differentially private empirical risk minimization from the viewpoint of optimization algorithms. For strongly convex and smooth objectives, we prove that gradient descent with output perturbation not only achieves nearly optimal utility, but also significantly improves the running …
In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension n×p and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components v1,…,vr has at most s0 non-zero entries. We a…
PAC-Bayesian theory applied to learning optimization algorithms with generalization guarantees.
problem Learning optimization algorithms with provable generalization guarantees and explicit trade-offs.
method PAC-Bayes theory applied to learning-to-optimize, reformulating the learning procedure into a one-dimensional minimization problem.
result Learned optimization algorithms outperform deterministic worst-case analysis algorithms, even in the limit case of guaranteed convergence.
Algorithm constructs prediction sets with PAC guarantees in label shift settings.
problem Reliable uncertainty quantification in the face of distribution shift.
method Estimates predicted probabilities and confusion matrix, then propagates uncertainty through Gaussian elimination to compute confidence intervals and construct prediction sets.
result Satisfies PAC guarantees and produces smaller, more informative prediction sets.
The paper shows how to efficiently generate large Gaussian process samples with reliability guarantees.
problem Generating large-scale Gaussian process samples efficiently and with reliability.
method Demonstrates scaling data generation to large \(n\) while providing high probability guarantees.
result Efficiently generates large Gaussian process samples with reliability guarantees.
Study merges datasets to improve AI model performance.
problem Improving machine learning models with diverse datasets.
method Developed an algorithm using oracle inequality and data-driven estimators.
result Algorithm reduces population loss with high probability.
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.