Paper tackles adaptive deletion of data points from trained models.
problem Adaptive deletion of data points from trained models.
method Reduction from adaptive to non-adaptive deletion guarantees using differential privacy and max information.
result Strong provable deletion guarantees for adaptive deletion sequences.
New guarantees for adaptive combinatorial maximization with various objectives.
problem Maximizing under cardinality constraints and minimum cost coverage in adaptive settings.
method Bayesian approach with comprehensive approximation guarantees for various utility functions.
result Maximal gain ratio is a new parameter that provides stronger approximation guarantees than greedy policies.
Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.
problem Improving Follow-the-Perturbed-Leader's BOBW guarantees in bandit problems.
method Introducing surrogate probability functions to compute adaptive learning rates without exact probabilities.
result BOBW guarantees for FTPL with Pareto perturbations for any α > 1 α>1 α > 1 . Adaptive designs achieve strong Neyman regret guarantees for ATE estimation.
problem Estimating unbiased average treatment effect in sequential experiments.
method Proposed adaptive designs with O ~ ( log T ) \widetilde{O}(\log T) O ( log T ) Neyman regret under boundedness assumptions and O ~ ( T ) \widetilde{O}(\sqrt{T}) O ( T ) multigroup Neyman regret in covariate-based settings. result Adaptive designs outperform non-adaptive designs in terms of Neyman regret, especially in covariate-based settings.
Paper adapts ACI for online multi-step time-series forecasting with coverage guarantees.
problem Achieving reliable error bounds in online multi-step time-series forecasting.
method Adaptive conformal inference (ACI) adapted for multi-step forecasting with dynamic significance levels.
result Proposes a multi-step ACI algorithm with finite-sample coverage guarantees for non-exchangeable data.
Paper presents adaptive minimax risk classifiers for multidimensional concept drift.
problem Multidimensional concept drift in supervised classification.
method Adaptive minimax risk classifiers (AMRCs) tracking multivariate and high-order distribution changes.
result AMRCs provide computable tight performance guarantees and improve classification.
New guarantees for ERM with adaptively collected data.
problem Failure of ERM guarantees with adaptively collected data.
method Importance sampling weighted ERM algorithm with maximal inequality.
result First generalization guarantees and fast convergence rates for adaptively collected data.
Unified analysis for nonlinear parametric models in Bayesian optimization.
problem Limited theoretical guarantees for nonlinear parametric models in Bayesian optimization.
method Kernel-based framework for analyzing regularized nonlinear parametric models trained on adaptively collected data.
result Unified convergence guarantees for nonlinear acquisition and surrogate models.
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of p…
Two private algorithms improve domain adaptation with privacy guarantees.
problem Improving predictions for a private target domain using public data.
method Two ( ε , δ ) (ε, δ) ( ε , δ ) -differentially private algorithms for supervised domain adaptation. result Private algorithms maintain performance close to non-private versions.
Guarantees for third-person imitation learning from offline data.
problem Improving generalizability in imitation learning.
method Problem-dependent statistical learning guarantees for third-person imitation from offline observation.
result Strong performance guarantees for transferred policies in the offline setting.
Adaptive methods learn from multiple datasets, leveraging similarities and robust to outliers.
problem Simultaneously analyze multiple datasets with possible similarities and differences.
method Adaptive multi-task learning methods that automatically utilize similarities and handle differences.
result Sharp statistical guarantees and robustness against outlier tasks demonstrated.
Adaptive Bayesian quadrature (ABQ) is a powerful approach to numerical integration that empirically compares favorably with Monte Carlo integration on problems of medium dimensionality (where non-adaptive quadrature is not competitive). Its key ingredient is an acquisition function that changes as a function of previou…
Adaptive sequential decision making is one of the central challenges in machine learning and artificial intelligence. In such problems, the goal is to design an interactive policy that plans for an action to take, from a finite set of n n n actions, given some partial observations. It has been shown that in many applicat…
New adaptive SGD algorithms for federated learning over physical channels.
problem Reducing communication cost in federated learning over physical channels.
method Proposed adaptive federated SGD algorithms considering channel noise and hardware constraints.
result Demonstrated convergence rates adaptive to stochastic gradient noise level.
Adapts data analysis for growing data, improving generalization guarantees.
problem Challenges of overfitting and statistical validity in adaptive workflows with growing data.
method Generalizes adaptive analysis on dynamic data, incorporating time-varying empirical accuracy bounds and mechanisms.
result First generalization bounds for adaptive analysis on dynamic data, matching prior works' improvement over data splitting.
Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we…
We show how to take any two parameter-free online learning algorithms with different regret guarantees and obtain a single algorithm whose regret is the minimum of the two base algorithms. Our method is embarrassingly simple: just add the iterates. This trick can generate efficient algorithms that adapt to many norms s…
Adaptive Quantum Conformal Prediction improves reliability of quantum machine learning predictions.
problem Quantum machine learning lacks robust uncertainty quantification methods.
method Adaptive Conformal Inference applied to quantum conformal prediction to maintain validity over time.
result AQCP achieves target coverage levels and is more stable than standard quantum conformal prediction.
Adapts Neyman-Pearson classification for both source and target distribution shifts.
problem Minimizing errors while controlling both Type-I and Type-II errors under distribution shifts.
method Derives an adaptive procedure that guarantees improved error rates and adapts to uninformative sources.
result Automatic adaptation to uninformative sources avoids negative transfer.
Adaptive data fusion boosts efficiency in multi-task optimization.
problem Multi-task non-smooth optimization in various fields.
method Adaptive data fusion approach leveraging commonalities among objectives.
result Significant improvements in sample efficiency with sharp statistical guarantees.
We present an approach towards convex optimization that relies on a novel scheme which converts online adaptive algorithms into offline methods. In the offline optimization setting, our derived methods are shown to obtain favourable adaptive guarantees which depend on the harmonic sum of the queried gradients. We furth…
We present a powerful general framework for designing data-dependent optimization algorithms, building upon and unifying recent techniques in adaptive regularization, optimistic gradient predictions, and problem-dependent randomization. We first present a series of new regret guarantees that hold at any time and under …
Datasets are often reused to perform multiple statistical analyses in an adaptive way, in which each analysis may depend on the outcomes of previous analyses on the same dataset. Standard statistical guarantees do not account for these dependencies and little is known about how to provably avoid overfitting and false d…
L-ARC improves model fairness by localizing risk guarantees.
problem Improving model fairness in tasks like image segmentation and wireless networks.
method Localized Adaptive Risk Control (L-ARC) updates a threshold function in RKHS to target localized statistical risk guarantees.
result L-ARC produces prediction sets with improved fairness across different data subpopulations.
Adaptive gradient methods like AdaGrad are widely used in optimizing neural networks. Yet, existing convergence guarantees for adaptive gradient methods require either convexity or smoothness, and, in the smooth setting, only guarantee convergence to a stationary point. We propose an adaptive gradient method and show t…
New technique for multiple-source adaptation without density estimation.
problem Multiple-source adaptation problem.
method Discriminative technique that uses conditional probabilities from unlabeled data.
result Our technique outperforms previous generative solutions and other domain adaptation baselines.
AdamCB optimizes neural network training by adaptively selecting samples.
problem Inefficient convergence due to unequal influence of different data samples.
method Integrates combinatorial bandit techniques into Adam to adaptively select samples.
result AdamCB achieves faster convergence and better performance than existing methods.
Adaptive PCR improves panel data analysis with uniform guarantees.
problem Adaptive data collection in panel data settings.
method Adapting PCR to online settings using martingale concentration.
result Time-uniform guarantees for adaptive PCR in panel data.
Paper proposes a privacy-preserving method to control false discoveries.
problem Protecting individual information in hypothesis tests while controlling false discoveries.
method Differentially private adaptive FDR control method with privacy guarantee.
result The method controls the FDR metric exactly at a user-specified level with privacy.
ARO overfits by making constraints dependent on uncertainty, leading to brittleness.
problem ARO's adaptive policies become brittle when realizations fall outside the uncertainty set.
method Assigning constraint-specific uncertainty set sizes with probabilistic guarantees.
result Regularization through specific uncertainty set sizes ensures stability and flexibility.
Efficient inference for adaptive data with directional stability condition.
problem Efficient inference on scalar targets after adaptive data collection.
method Introduces directional stability, a weaker condition than i.i.d. data, and shows asymptotic normality and efficiency of estimators.
result Estimators remain asymptotically normal and semiparametrically efficient under directional stability.
JAPAN uses flow-based models to create adaptive prediction areas with better coverage guarantees.
problem Inadequate prediction areas from existing conformal prediction methods, especially for multimodal distributions.
method JAPAN employs density-based conformity scores using flow-based models to construct context-adaptive prediction areas.
result JAPAN produces more accurate and context-adaptive prediction areas compared to existing methods.
AdaDetectGPT improves text authorship detection with statistical guarantees.
problem Determining if text is authored by a human or an LLM.
method Adaptive learning of a witness function from training data to enhance logits-based detectors.
result AdaDetectGPT nearly uniformly improves text authorship detection, with up to 37% improvement.
The study explores whether model selection guarantees apply to contextual bandits.
problem Applying model selection guarantees to contextual bandits.
method Investigates whether similar guarantees for model selection in statistical learning can be extended to contextual bandit learning.
result Initial findings suggest that model selection guarantees may not directly apply to contextual bandits.
The paper proposes a method for distribution-free prediction sets that adapt to unknown temporal changes.
problem Distribution-free prediction sets require reliable calibration data, which is often unavailable in real-world settings with temporal changes.
method The method selects an adaptive window to construct prediction sets, optimizing a bias-variance tradeoff.
result The method provides sharp coverage guarantees and is shown to be adaptive to temporal drift through numerical experiments.
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.
New SAE algorithm proves feature recovery for LLMs with theoretical guarantees.
problem Achieving interpretable features in large language models (LLMs).
method Proposed a statistical framework and bias adaptation technique for sparse autoencoders (SAEs).
result Proved correct recovery of all monosemantic features under specific data sampling.
New methods improve online matrix optimization with reduced computational cost.
problem Online matrix optimization with operator norm constraints.
method Gradient-based prediction scheme with smoothed potentials for nuclear norm.
result Adaptive matrix optimizers match Shampoo's regret up to a constant factor.
CPATTA uses conformal prediction for efficient test-time adaptation.
problem Low data selection efficiency in existing ATTA methods.
method Conformal Prediction, online weight-update algorithm, domain-shift detector, staged update scheme.
result CPATTA consistently outperforms state-of-the-art methods by 5% in accuracy.
Adaptive step-size improves optimization in complex geometries.
problem Optimizing functions with non-Euclidean geometries.
method Adaptive step-size strategy for optimization algorithms.
result Guaranteed convergence for Adaptive Conditional Gradient Descent.
New approach tackles resource constraints in bandit problems with weakly adaptive algorithms.
problem Maximizing rewards while adhering to general long-term constraints.
method Weakly adaptive primal and dual regret minimizers.
result Achieves sublinear constraints violations and competitive ratios in both stochastic and adversarial settings.
Adaptive coverage policies improve conformal prediction accuracy.
problem Fixed coverage levels in traditional conformal prediction lead to uninformative predictions.
method Optimizes adaptive coverage policy using a neural network trained on leave-one-out calibration.
result Adaptive coverage policies produce more informative and flexible prediction sets.
New methods adapt conformal prediction to unknown subpopulation shifts.
problem Failure of conformal prediction under unknown subpopulation shifts.
method Proposes new methods that adapt conformal prediction to unknown subpopulation shifts without explicit subpopulation labels.
result Ensures valid coverage guarantees without explicit knowledge of subpopulation structure.
Study shows reinforcement learning algorithm's performance depends on metric space's size.
problem Continuous state and action spaces with metrics.
method Refined analysis of Sinclair et al. (2019) algorithm.
result Regret scales with the zooming dimension, a new parameter capturing near optimal actions.
New algorithm offers costless model selection in contextual bandits.
problem Minimizing cumulative regret in stochastic contextual bandits.
method Gradually increasing class complexity and adapting to the simplest class with dominant estimation variance.
result Costless model selection is feasible under certain conditions, providing improved regret guarantees.
We propose algorithms for online principal component analysis (PCA) and variance minimization for adaptive settings. Previous literature has focused on upper bounding the static adversarial regret, whose comparator is the optimal fixed action in hindsight. However, static regret is not an appropriate metric when the un…
Adaptive batch sizes improve local gradient methods in distributed training.
problem Communication bottlenecks in distributed deep learning.
method Adaptive batch size strategies for local gradient methods.
result Adaptive batch sizes reduce minibatch gradient variance and improve training efficiency.