Paper improves worst-case regret bounds for RLSVI in reinforcement learning.
problem Minimizing regret in reinforcement learning with randomized value functions.
method Introduces a clipping variant of Thompson Sampling for RLSVI.
result Achieves a i l d e O ( H 2 S A T ) ilde{\mathrm{O}}(H^2S\sqrt{AT}) i l d e O ( H 2 S A T ) worst-case regret bound. Develops a new worst-case bound on expected shortfall with bivariate expert information.
problem Bounding expected shortfall with limited distributional information.
method Modeling trade-off between conservatism and expert information using Kullback-Leibler divergence.
result Bound reduces to comonotonic upper bound as expert information becomes more certain.
In three-dimensional computational topology, the theory of normal surfaces is a tool of great theoretical and practical significance. Although this theory typically leads to exponential time algorithms, very little is known about how these algorithms perform in "typical" scenarios, or how far the best known theoretical…
New framework improves worst-case generalization bounds for stochastic optimization.
problem Challenges in providing generalization guarantees for stochastic optimization algorithms.
method Introduces random set stability and empirically relevant complexity measures to avoid intractable mutual information terms.
result Bounded worst-case generalization error in terms of random set stability and empirically relevant complexity measures.
We consider the problem of learning a dictionary matrix from a number of observed signals, which are assumed to be generated via a linear model with a common underlying dictionary. In particular, we derive lower bounds on the minimum achievable worst case mean squared error (MSE), regardless of computational complexity…
Exact tail probability bounds for bounded kurtosis.
problem Determining worst-case tail probabilities under kurtosis constraints.
method AI-guided search and certifying pipeline to compute bounds.
result A four-regime map of tail probabilities with explicit formulas.
We provide valid confidence intervals for adaptive data analysis.
problem Lack of valid confidence intervals for adaptive statistical queries.
method General framework for instance-specific confidence intervals.
result Orders of magnitude better guarantees than worst-case bounds.
We find the exact worst-case tail probability for bounded kurtosis.
problem Determining the worst-case tail probability under bounded kurtosis constraints.
method AI-guided search and certificate verification around the certifying pipeline.
result A four-regime map of tail probabilities with explicit formulas and dual certificates.
MaxMatch improves SSL with worst-case consistency for better generalization.
problem Efficiently supervised learning with unlabeled data.
method Worst-case consistency regularization for SSL, providing a bound and an algorithm.
result The proposed method converges to a stationary point and improves generalization.
New regularization techniques using mass transportation for better generalization.
problem Mitigating overfitting with scarce data.
method Distributionally robust optimization and worst-case expected loss.
result Generalization bounds and tractable learning problems.
Study optimizes identifying the best arm with fixed rounds and Gaussian outcomes.
problem Designing efficient experiments to identify the best arm with fixed rounds and Gaussian outcomes.
method Developed worst-case lower bounds and the GNA-EBA strategy for optimal identification.
result GNA-EBA strategy is asymptotically worst-case optimal.
Study uses randomized value functions to enhance exploration in reinforcement learning.
problem Improving exploration in reinforcement learning algorithms.
method Injecting random noise into value functions for efficient exploration.
result Provably efficient exploration achieved through worst-case regret bounds.
New TVD estimator adapts to piecewise constant functions, improving performance.
problem Improving TVD estimator performance for piecewise constant functions.
method Investigates adaptivity of TVD estimator to piecewise constant functions and proposes a data-driven tuning parameter.
result The ideally tuned TVD estimator performs better than in the worst case for piecewise constant functions.
We introduce a class of utility-based market makers that always accept orders at their risk-neutral prices. We derive necessary and sufficient conditions for such market makers to have bounded loss. We prove that hyperbolic absolute risk aversion utility market makers are equivalent to weighted pseudospherical scoring …
We present methods for online linear optimization that take advantage of benign (as opposed to worst-case) sequences. Specifically if the sequence encountered by the learner is described well by a known "predictable process", the algorithms presented enjoy tighter bounds as compared to the typical worst case bounds. Ad…
New algorithm reduces worst-case regret for heavy-tailed bandits.
problem Stochastic Multi-Armed Bandit problem with heavy-tailed rewards.
method Modified minimax policy MOSS with saturated empirical mean.
result Worst-case regret matching lower bound for heavy-tailed distributions.
Oracle-efficient algorithms for online learning with smoothed and hint-adversaries.
problem Online learning with beyond worst-case adversaries.
method Oracle-efficient algorithms for two settings: smoothed analysis and K K K -hint transductive learning. result Oracle-efficient regret bounds for learning real-valued and binary-valued functions.
We bridge statistical and worst-case approaches to experimental design for linear regression.
problem Designing efficient experiments for linear regression models with arbitrary responses.
method Propose a new experimental design framework for arbitrary response distributions, combining statistical and worst-case approaches.
result Develop efficient randomized design procedures achieving strong variance bounds for unbiased estimators using few responses.
We prove the first nontrivial worst-case lower bounds for two closely related problems. First, Ω ( n 3 / 2 ) Ω(n^{3/2}) Ω ( n 3/2 ) degree-1 reductions, series-parallel reductions, and Δ Δ Δ Y transformations are required in the worst case to reduce an n n n -vertex plane graph to a single vertex or edge. The lower bound is achieved by any planar g…
Paper aims to ensure reliable detection of out-of-distribution data with certifiable worst-case guarantees.
problem Deep neural networks are overconfident with OOD inputs, posing safety risks.
method Enforces low confidence and bounds in an l ∞ l_\infty l ∞ -ball around OOD points using interval bound propagation (IBP). result Certifiable worst-case guarantees for OOD detection are possible without significant loss in accuracy.
New insights into multi-armed bandits with budget constraints.
problem Multi-armed bandits with supply/budget constraints.
method Characterization of logarithmic regret rates, simple regret, and reduction to other bandit problems.
result Full characterization of logarithmic, instance-dependent regret rates for BwK.
Optimizes privacy-preserving optimization for heavy-tailed data.
problem Privacy-preserving optimization with heavy-tailed gradients.
method Pure ε-differential privacy framework for Lipschitz extensions.
result Minimax optimal excess-risk rate for pure ε-DP heavy-tailed SCO.
Improved algorithms for stochastic linear bandits using tighter confidence sequences.
problem Stochastic linear bandits with improved worst-case regret guarantees.
method Novel tail bound for adaptive martingale mixtures to construct tighter confidence sequences.
result Linear bandit algorithm achieves competitive worst-case regret.
Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a \textit{semi-ran…
Hardness proof for agnostically learning halfspaces from worst-case lattice problems.
problem Agnostically learning halfspaces in the presence of noise.
method Reduction to worst-case lattice problems (GapSVP, SIVP).
result No efficient algorithm can achieve misclassification error better than 1/2 - γ under given hardness assumptions.
Improved DP SO with large Lipschitz parameters, handling outliers and heavy-tailed data.
problem Differential privacy in stochastic optimization with large Lipschitz parameters.
method Assumes bounded k-th order moments, provides linear-time algorithms for smooth convex and non-smooth convex losses.
result Improved risk bounds scaling with k-th moment, not uniform Lipschitz parameter.
The paper tackles robust control for insurance contracts under uncertain transition rates.
problem Maximizing utility in insurance contracts with uncertain transition rates.
method Novel robust utility maximization problem under bounded cumulative transition rate uncertainty, using worst-case scenario analysis.
result Existence and uniqueness of worst-case and best-case reserves for insurance contracts.
The paper tackles adversarial robustness by maximizing worst-case mutual information.
problem Training robust machine learning models against adversarial inputs is challenging.
method Develops a notion of representation vulnerability and an unsupervised learning method to maximize worst-case mutual information.
result Proves a lower bound on minimum adversarial risk and supports robustness of representations.
New expressive losses improve adversarial robustness without sacrificing accuracy.
problem Training networks for robustness at the expense of accuracy.
method Formalizing expressivity, using convex combinations of adversarial attacks and IBP bounds.
result Trivial expressive losses yield state-of-the-art results in various settings.
Paper proves higher-order flow matching preserves optimality in generative modeling.
problem Theoretical guarantees for higher-order flow matching in generative modeling.
method Neural network approximations with controlled depth, width, and sparsity.
result Proves worst case optimality for second-order flow matching.
Transforming curves with crossings requires a number of moves proportional to n^(3/2).
problem Transforming curves with crossings into simple curves.
method Finite sequence of local transformations called homotopy moves.
result Transforming a curve with n crossings requires Θ(n^(3/2)) homotopy moves in the worst case.
The paper analyzes extreme risk measures with limited distributional information.
problem Investigating risk measures under partial knowledge of distribution moments and shape.
method Employing probability inequalities and modified Schwarz inequality to derive bounds on distortion risk measures.
result Unified framework for calculating best- and worst-case scenarios of distortion risk measures.
New analysis shows neural networks and low-degree polynomials perform well on sparse latent structure problems.
problem Understanding the performance of neural networks and polynomial approximators on real-world sparse latent structure problems.
method Analysis of neural networks and polynomial kernels of bounded degree on a simple, natural inference problem with sparse latent structure.
result Almost-tight bounds on the performance of neural networks and low-degree polynomials for the problem, showing qualitative differences from worst-case settings.
Proposes a new uncertain volatility model with worst-case scenario analysis.
problem Modeling and pricing options under uncertain volatility.
method Connection between G-HJB equations and 2BSDEs for option pricing.
result Derives a limit model for worst-case price scenario.
DRCS selects a subset of data to minimize worst-case test error under covariate shift.
problem Selecting a subset of data that performs well across different deployment scenarios when data distributions differ.
method DRCS derives an upper bound for the worst-case test error assuming covariate shift and selects instances to minimize this bound.
result DRCS achieves distributionally robust training instance selection.
Federated learning uses worst-case optimization to handle uncertain local data impacts.
problem Handling uncertainty in local data sets in federated learning.
method Reformulate FL problem using worst-case optimization theory, considering local data as uncertain functions bounded in a closed region.
result Comparison of FL performance with centralized learning and application of regularization factors.
Proposes uncertain volatility models with fluctuating stochastic bounds for improved accuracy.
problem Improving accuracy in modeling volatility with fluctuating bounds.
method Introduces stochastic bounds that fluctuate according to a stochastic volatility process, applying perturbation analysis to reduce complexity.
result The method provides a significant computational advantage and performs well even with moderately slow varying bounds.
This paper studies bounds for the Lipschitz constant of random neural networks.
problem Quantifying the worst-case robustness of neural networks against adversarial perturbations.
method Analyzes upper and lower bounds for the Lipschitz constant of random ReLU neural networks under specific initialization conditions.
result For deep networks, the upper bound is larger than the lower bound by a logarithmic factor in width.
We introduce a modular framework for market making. It combines cost-function based automated market makers with bandit algorithms. We obtain worst-case profits guarantee's relative to the best in hindsight within a class of natural "overround" cost functions . This combination allow us to have distribution-free guaran…
We propose an approach to the aggregation of risks which is based on estimation of simple quantities (such as covariances) associated to a vector of dependent random variables, and which avoids the use of parametric families of copulae. Our main result demonstrates that the method leads to bounds on the worst case Valu…
New policy optimizes risk and optimality in stochastic bandits.
problem Optimizing risk in stochastic bandits with heavy-tailed risk.
method Designing policies with worst-case optimality for expected regret and light-tailed risk distribution.
result Achieves worst-case optimality for expected regret and light-tailed risk distribution.
This paper improves active learning for Gaussian process regression to handle distributional uncertainty.
problem Active learning for Gaussian process regression does not guarantee accurate predictions for target distributions.
method Proposes two methods to reduce worst-case expected error for Gaussian process regression.
result Shows an upper bound of the worst-case expected squared error, suggesting finite data labels can achieve arbitrarily small error.
Optimal strategy identified for minimizing regret in fixed-budget best arm selection.
problem Minimizing expected simple regret in fixed-budget best arm selection.
method Two-Stage (TS)-Hirano-Imbens-Ridder (HIR) strategy using HIR estimator.
result TS-HIR strategy is asymptotically minimax optimal.
Improves policy optimization with polylog(T) regret bounds for stochastic losses.
problem Improves theoretical guarantees for policy optimization in stochastic settings.
method Leverages Tsallis and Shannon entropy regularizers for polylog(T) regret, and log-barrier regularizer for adversarial settings.
result Achieves a first-order polylog(T) regret bound for policy optimization in stochastic settings.
New approach for pricing evaluation improves on existing methods.
problem Improving off-policy evaluation for personalized pricing.
method Balanced policy evaluation framework with worst-case optimization.
result Empirical advantage over existing methods in pricing applications.
Improved bounds for function approximation in nonlinear sets.
problem Achieving high probability error with limited samples in nonlinear function approximation.
method Restricting model class to a neighbourhood of the best approximation and estimating sample complexity using tangent and normal spaces' complexities and curvature.
result Improved worst-case bounds for sample complexity in more general sets like tensor networks and neural networks.
New algorithm expands FTRL framework with improved worst-case regret bounds.
problem Online learning with improved worst-case regret bounds.
method Generalized implicit Follow-The-Regularized-Leader (FTRL) algorithm.
result Unified framework for designing updates improving worst-case regret bounds.
New analysis shows D-SGD can generalize well regardless of graph connectivity.
problem Improving generalization of D-SGD in decentralized settings.
method Algorithmic stability analysis and optimization-dependent generalization bounds.
result D-SGD can achieve generalization bounds similar to classical SGD, independent of graph connectivity.