Paper establishes lower bounds and optimal algorithms for deployment-efficient RL.
problem Deployment efficiency in reinforcement learning.
method Optimization with constraints, lower bounds, algorithms.
result Established optimal algorithms for deployment-efficient RL.
Proposes an efficient lower bound for Gromov-Wasserstein discrepancy.
problem Comparing structured data from different metric-measure spaces.
method Orthogonal Gromov-Wasserstein (OGW) discrepancy with efficient closed-form lower bound.
result Efficient and tight lower bounds for Gromov-Wasserstein discrepancy.
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…
New bounds on efficiency for conformalized regression methods.
problem Efficiency of conformal prediction in regression models.
method Non-asymptotic bounds on prediction set length for conformalized quantile and median regression.
result Identifies phase transitions in convergence rates across different regimes of miscoverage level.
We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a Bayesian and a frequentist regret bound respectively, both of which reduce to the near-optimal bound …
The paper finds a fundamental trade-off between confidence and efficiency in transductive conformal prediction.
problem The challenge is to balance confidence and efficiency in predicting multiple data points.
method The authors derive a strict finite-sample bound and introduce a practical algorithm to approach this bound.
result Any non-trivial confidence level leads to exponential growth in prediction set size, with a linear scaling in the number of samples.
Efficiently verifies neural networks by handling neuron splits, improving speed and accuracy.
problem Handling neuron split constraints in incomplete neural network verification.
method β-CROWN, which optimizes parameters β to encode neuron splits and uses them in bound propagation.
result β-CROWN significantly speeds up verification while maintaining high accuracy.
Paper proposes an efficient method for bounding box annotation in object detection.
problem Manual annotation of bounding boxes is tedious and resource-intensive.
method Iterative training of object detector on small batches of labeled images, with human annotator correcting errors.
result Significant reduction in human annotation effort, up to 75%.
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-hint transductive learning. result Oracle-efficient regret bounds for learning real-valued and binary-valued functions.
New bounds on KPCA efficiency reveal conditions for fast convergence.
problem Lack of theoretical understanding of KPCA efficiency.
method Lower and upper bounds on KPCA efficiency involving empirical eigenvalues and new variance quantities.
result Fast convergence rates achievable for certain kernels, highlighting dataset properties.
We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. The hardness of recommending Copeland winners, the arms that beat the greatest number of other arms, is characterized by deriving an asymptotic regr…
New bounds on IDS for RL show how to balance computation and learning efficiency.
problem Understanding and optimizing information-directed sampling (IDS) for reinforcement learning.
method Developed novel information-theoretic tools to bound information ratio and cumulative information gain.
result Derived prior-free Bayesian regret bounds for IDS in tabular finite-horizon MDPs and improved computational efficiency.
Paper tackles efficient evaluation of natural stochastic policies in offline RL.
problem Efficiency issues in evaluating natural stochastic policies due to unknown evaluation policy.
method Derive efficiency bounds for tilting and modified treatment policies, propose nonparametric estimators.
result Proposed estimators attain efficiency bounds under lax conditions and enjoy partial double robustness.
PopArt efficiently solves sparse linear bandits with tighter recovery guarantees.
problem Sparse linear bandits where rewards depend on a few covariates.
method PopArt: a simple, computationally efficient sparse linear estimation method.
result Improved regret bounds compared to state-of-the-art algorithms.
Training neural networks with verifiable robustness guarantees is challenging. Several existing approaches utilize linear relaxation based neural network output bounds under perturbation, but they can slow down training by a factor of hundreds depending on the underlying network architectures. Meanwhile, interval bound…
Efficient tensor decomposition for count data models achieves near-optimal multiway analysis.
problem Efficient tensor decomposition for count data models.
method Rank-constrained maximum-likelihood estimator for tensor decomposition.
result Achieves multiway analysis with variance matching Cramér-Rao Lower Bound up to constants and logarithmic factors.
New method certifies global robustness of neural networks efficiently.
problem Adversarial examples threaten certifiably robust neural networks.
method Formalized global robustness, adapted widely-used architectures with efficient global Lipschitz bounds.
result Certifiable robust models achieve state-of-the-art verifiable accuracy with negligible costs.
Efficiently learns polytrees with known skeleton in polynomial time and sample complexity.
problem Learning polytrees with known skeleton structure.
method Proposes an efficient algorithm for learning d-polytrees in polynomial time and sample complexity when the skeleton is known. result Establishes finite-sample guarantees for efficient learning of d-polytrees. Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O(d/ε+d/(max{p,ε})2), SQ lower bound is Ω(d1/2/(max{p,ε})2). Flow matching KL divergence bound derived for smooth distributions.
problem Estimating smooth distributions efficiently.
method Deterministic upper bound on KL divergence derived from flow-matching loss.
result Flow matching achieves nearly minimax-optimal efficiency under TV distance.
New proof shows efficient ReLU networks for piecewise linear functions.
problem Existence of efficient ReLU neural networks for piecewise linear functions.
method Degree 1 triangulations of the relative homology class bounded by polyhedra.
result Existence of efficient ReLU neural networks for functions with compact support.
Efficient triangulations help in understanding 3-manifold boundaries.
problem Understanding boundary slopes in 3-manifolds.
method Introducing and studying boundary-efficient triangulations and inflating ideal triangulations.
result There are only finitely many boundary slopes for incompressible and \(\partial\)-incompressible surfaces in compact 3-manifolds.
This study optimizes covariate density and propensity score for efficient ATE estimation.
problem Efficiently estimating average treatment effects (ATEs) with minimal variance.
method Adaptive experiment optimizing both covariate density and propensity score.
result Proposed method minimizes the semiparametric efficiency bound for ATE estimation.
In deep neural networks, the spectral norm of the Jacobian of a layer bounds the factor by which the norm of a signal changes during forward/backward propagation. Spectral norm regularizations have been shown to improve generalization, robustness and optimization of deep learning methods. Existing methods to compute th…
Measuring Mutual Information (MI) between high-dimensional, continuous, random variables from observed samples has wide theoretical and practical applications. Recent work, MINE (Belghazi et al. 2018), focused on estimating tight variational lower bounds of MI using neural networks, but assumed unlimited supply of samp…
We study the problem of efficient online multiclass linear classification with bandit feedback, where all examples belong to one of K classes and lie in the d-dimensional Euclidean space. Previous works have left open the challenge of designing efficient algorithms with finite mistake bounds when the data is linear…
Sparse feature selection improves batch RL efficiency.
problem High-dimensional batch RL with many features.
method Sparse linear function approximation, Lasso, group Lasso, fitted Q-evaluation, fitted Q-iteration.
result Sparse feature selection makes batch RL more sample efficient.
Efficiently estimates sparse linear regression with heavy-tailed and outlier-contaminated data.
problem Estimating sparse linear regression coefficients with heavy-tailed and outlier-contaminated data.
method Efficient computation of estimators with sharp error bounds.
result Sharp error bounds for efficient estimators.
We study active learning of homogeneous s-sparse halfspaces in Rd under the setting where the unlabeled data distribution is isotropic log-concave and each label is flipped with probability at most η for a parameter η∈[0,21), known as the bounded noise. Even in the presence of mild la…
In this paper, we consider the problem of prediction with expert advice in dynamic environments. We choose tracking regret as the performance metric and develop two adaptive and efficient algorithms with data-dependent tracking regret bounds. The first algorithm achieves a second-order tracking regret bound, which impr…
Study on conditions for achieving optimal robustness in statistical estimators.
problem Achieving the optimal robustness of estimators in statistical models.
method Developed a Wasserstein analogue of the Cramer-Rao inequality and investigated conditions for achieving the Wasserstein-Cramer-Rao lower bound.
result Conditions for the existence of asymptotically efficient estimators in one-parameter models and location-scale families.
New coverage conditions improve sample efficiency in online reinforcement learning.
problem Improving sample efficiency in online reinforcement learning with function approximation.
method Identifying and studying new coverage conditions for online reinforcement learning.
result Improved regret bounds achieved with new coverage conditions.
Paper finds efficient OPE estimator for multiple logging policies with minimum variance.
problem Finding optimal importance sampling weights for multiple logging policies with varying variances.
method Established efficiency bound under stratified sampling and proposed an estimator achieving this bound.
result Proposed estimator achieves minimum variance for any instance.
This paper develops efficient bounds on the Wasserstein metric for discrete measures.
problem Computing the exact Wasserstein metric is computationally expensive.
method Formulates and solves a Kantorovich problem on a coarse grid using quantized measures and cost matrices, followed by upscaling and correction.
result Achieves a 10x-100x speedup while maintaining low approximation error.
New algorithm reduces online learning error for unknown feature distributions.
problem Oracle-efficient hybrid online learning with unknown feature and label distributions.
method Computational efficient online predictor using ERM oracle for finite-VC and fat-shattering classes.
result Oracle-efficient sublinear regret bounds for hybrid online learning with unknown feature generation.
Langevin MCMC samples efficiently from Riemannian manifolds with geometric Euler-Murayama analysis.
problem Efficient sampling from Gibbs distributions on Riemannian manifolds.
method Geometric Langevin MCMC, discretization error bound, contraction guarantee for Langevin Diffusion.
result Langevin MCMC iterates converge to the target distribution after a number of steps proportional to the inverse square of the desired accuracy.
New algorithm achieves small-loss bounds in online learning with improved rates.
problem Achieving strong stability in online learning algorithms.
method Introduces ρ-separation to enforce strong stability, unifying previous approaches. result Oracle-efficient algorithm achieves small-loss bounds with improved rates.
New algorithm for online omniprediction with strong guarantees for continuous hypothesis classes.
problem Online adversarial learning with continuous hypothesis classes.
method Developed an oracle-efficient online multicalibration algorithm for infinite benchmark classes.
result First efficient online omnipredictor with strong guarantees for Lipschitz convex loss functions.
Improved algorithm for contextual bandits with reduced regret.
problem Adversarial contextual bandits with i.i.d. contexts.
method Oracle-efficient relaxation with O(T32(Klog(∣Π∣))31) regret bound. result First to improve regret bound and match original bound for stochastic case.
GPE algorithm optimizes nonparametric contextual bandits with efficient regret bounds.
problem Optimizing nonparametric contextual bandits with efficient regret bounds.
method Inspired by Policy Elimination, GPE uses oracle-efficient techniques for nonparametric classes with infinite VC-dimension.
result GPE is regret-optimal for policy classes with integrable entropy, and for larger entropy, it provides an ε-greedy algorithm with matching regret bounds. Prediction-powered causal inference achieves smaller asymptotic variance than traditional methods.
problem Estimating causal and structural parameters in a semi-supervised setting.
method Combining efficient influence function with debiased machine learning and semi-supervised Riesz regression.
result Asymptotic variances of estimators match the derived efficiency bound.
This paper focuses on projection-free methods for solving smooth Online Convex Optimization (OCO) problems. Existing projection-free methods either achieve suboptimal regret bounds or have high per-iteration computational costs. To fill this gap, two efficient projection-free online methods called ORGFW and MORGFW are …
Kernel-based online learning has often shown state-of-the-art performance for many online learning tasks. It, however, suffers from a major shortcoming, that is, the unbounded number of support vectors, making it non-scalable and unsuitable for applications with large-scale datasets. In this work, we study the problem …
In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite prog…
Efficient exploration is one of the key challenges for reinforcement learning (RL) algorithms. Most traditional sample efficiency bounds require strategic exploration. Recently many deep RL algorithms with simple heuristic exploration strategies that have few formal guarantees, achieve surprising success in many domain…
Efficient local Lipschitz bounds improve neural network robustness.
problem Certifying robustness of neural networks is challenging and often leads to over-regularization.
method Proposes an efficient trainable local Lipschitz upper bound by considering activation functions and weight matrices.
result Consistently outperforms state-of-the-art methods in clean and certified accuracy on various datasets.
New algorithm optimizes Hölder continuous functions efficiently.
problem Optimizing Hölder continuous multivariate functions.
method Uses a query creation rule for global optimization, avoiding proxy functions.
result Achieves an average regret bound of $O(T^{- racα{n}})$ for Hölder exponent α. Novel neural architecture improves Bayesian experimental design efficiency.
problem Intractable evaluation of expected information gain (EIG) in Bayesian optimal experimental design.
method Develops a neural architecture that optimizes a single variational model for estimating EIG across many designs, using a lower bound for computational efficiency.
result Significantly improves accuracy in Bayesian experimental design with better sample efficiency.