We present a provably optimal differentially private algorithm for the stochastic multi-arm bandit problem, as opposed to the private analogue of the UCB-algorithm [Mishra and Thakurta, 2015; Tossou and Dimitrakakis, 2016] which doesn't meet the recently discovered lower-bound of [Shar…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Successive elimination”
The paper tackles best arm identification in contaminated bandits with optimal error guarantees and sample complexity.
problem Best arm identification in stochastic bandits with adversarial reward contamination.
method Proposes two algorithms: a gap-based algorithm and a successive elimination-based algorithm for sub-Gaussian bandits.
result Asymptotically optimal sample complexity for both algorithms.
Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Schemestat.ML
Study quantile multi-armed bandits for identifying the best arm with a specified quantile level.
problem Identifying the arm with the highest quantile in multi-armed bandits with private rewards.
method Proposed a (non-private) and differentially private successive elimination algorithms for best-arm identification.
result The proposed algorithms are essentially optimal for quantile bandit problems, with finite sample complexity even for distributions with infinite support-size.
Proposes a new semi-parametric framework for batched bandits with covariates.
problem Sequential decision-making with batched feedback and contextual information.
method Batched single-Index Dynamic binning and Successive arm elimination (BIDS) using single-index regression.
result Achieves minimax-optimal rates for nonparametric batched bandits.
Max-Min Grouped Banditsstat.ML
New bandit problem for finding best group of arms with worst mean reward.
problem Finding the best group of arms with the worst mean reward in overlapping groups.
method Two algorithms based on successive elimination and robust optimization.
result Upper bounds on the number of samples to find max-min optimal or near-optimal group.
We consider a multi-armed bandit problem in a setting where each arm produces a noisy reward realization which depends on an observable random covariate. As opposed to the traditional static multi-armed bandit problem, this setting allows for dynamically changing rewards that better describe applications where side inf…
New algorithm improves best arm identification in Bayesian settings.
problem Finding the arm with the highest mean in unknown distributions.
method Developed a variant of successive elimination algorithm.
result Achieved optimal performance in Bayesian setting with logarithmic gap.
A scheme robust to action erasures improves MAB performance.
problem Learning in multi-arm bandits with erasure channels.
method Proposes a scheme to work on top of any MAB algorithm.
result Worst-case regret is at most a factor of away from no-erasure case.
New algorithm finds high-reward combinatorial sets with fewest pulls.
problem Finding high-reward combinatorial sets with unknown individual arm rewards.
method Successive acceptance and elimination based on combinatorial structure.
result Algorithm requires minimal combinatorial oracle calls, making it practical for large problems.
New algorithm for non-stationary bandits with slow drifts.
problem Minimizing dynamic regret in non-stationary bandits with slowly varying rewards.
method Extends Successive Elimination to non-stationary bandits with a novel gap profile characterization.
result First instance-dependent regret upper bound for slowly varying non-stationary bandits.
In this short paper we investigate whether meta-learning techniques can be used to more effectively tune the hyperparameters of machine learning models using successive halving (SH). We propose a novel variant of the SH algorithm (MeSH), that uses meta-regressors to determine which candidate configurations should be el…
We study an original problem of pure exploration in a strategic bandit model motivated by Monte Carlo Tree Search. It consists in identifying the best action in a game, when the player may sample random outcomes of sequentially chosen pairs of actions. We propose two strategies for the fixed-confidence setting: Maximin…
Truncated SGD with heavy-tailed noise eliminates sharp local minima.
problem Avoiding sharp local minima in deep learning models.
method Truncated SGD with heavy-tailed gradient noise.
result Truncated SGD can eliminate sharp local minima entirely from its training trajectory.
Proposes a flexible tournament design combining knockout and round-robin.
problem Designing a tournament that eliminates participants linearly.
method Combines knockout and round-robin structures for flexible elimination.
result Flexible tournament design can eliminate participants linearly.
In many platforms, user arrivals exhibit a self-reinforcing behavior: future user arrivals are likely to have preferences similar to users who were satisfied in the past. In other words, arrivals exhibit positive externalities. We study multiarmed bandit (MAB) problems with positive externalities. We show that the self…
Improved elimination strategies for adaptive bandit identification reduce sample complexity and computational burden.
problem Inefficient elimination strategies in bandit identification.
method Adaptive elimination methods that update sampling rules frequently and reduce problem size.
result Adaptive elimination methods achieve better sample complexity and computational efficiency.
A new algorithm selects models for contextual bandits, reducing regret.
problem Model selection for stochastic contextual bandits under realizability assumption.
method Adaptive Contextual Bandit (ACB) algorithm, successive refinement phases.
result ACB algorithm achieves similar regret bound to known algorithms, with a model selection cost.
In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the re…
Defense against DL-based lithographic hotspot detectors backdooring attacks reduces success rate from 84% to ~0%
problem DL-based lithographic hotspot detectors are vulnerable to backdoor attacks that can misclassify hotspots.
method Training data augmentation to eliminate intentional biases introduced during training.
result Significant reduction in attack success rate (from 84% to ~0%) using the proposed defense.
Classification may not be reliable for several reasons: noise in the data, insufficient input information, overlapping distributions and sharp definition of classes. Faced with several possibilities neural network may in such cases still be useful if instead of a classification elimination of improbable classes is done…
Theoretical justification for asymmetric actor-critic algorithms in reinforcement learning.
problem Lack of precise theoretical justification for asymmetric actor-critic algorithms in reinforcement learning.
method Adapting a finite-time convergence analysis to the asymmetric actor-critic setting with linear function approximators.
result A finite-time bound reveals that the asymmetric critic eliminates aliasing errors in the agent state.
SPO optimizes LLMs by eliminating group-based baselines and variance issues.
problem Frequent degenerate groups and synchronization barriers in group-based policy optimization methods.
method Single-stream Policy Optimization (SPO) replaces per-group baselines with a persistent, KL-adaptive value tracker and global advantage normalization.
result SPO converges more smoothly and attains higher accuracy than GRPO, improving maj@32 by +3.4 pp across five math benchmarks.
New algorithm eliminates arms to minimize regret in complex bandit problems.
problem Minimizing regret in combinatorial bandit problems with explicit exploration.
method Introduces a novel arm elimination scheme that partitions arms into three categories and incorporates explicit exploration.
result Achieves near-optimal regret in combinatorial multi-armed and linear contextual bandit problems.
Probabilistic graphical models are a key tool in machine learning applications. Computing the partition function, i.e., normalizing constant, is a fundamental task of statistical inference but it is generally computationally intractable, leading to extensive study of approximation methods. Iterative variational methods…
Training recurrent neural networks (RNNs) on long sequence tasks is plagued with difficulties arising from the exponential explosion or vanishing of signals as they propagate forward or backward through the network. Many techniques have been proposed to ameliorate these issues, including various algorithmic and archite…
Learning how to act when there are many available actions in each state is a challenging task for Reinforcement Learning (RL) agents, especially when many of the actions are redundant or irrelevant. In such cases, it is sometimes easier to learn which actions not to take. In this work, we propose the Action-Elimination…
New algorithm eliminates sign function in PGD attacks, improving performance.
problem Improving robustness of neural networks against adversarial attacks.
method Proposes a new raw gradient descent (RGD) algorithm that eliminates the sign function in PGD attacks.
result The RGD algorithm outperforms PGD and other competitors in various settings.
We introduce Neural Choice by Elimination, a new framework that integrates deep neural networks into probabilistic sequential choice models for learning to rank. Given a set of items to chose from, the elimination strategy starts with the whole item set and iteratively eliminates the least worthy item in the remaining …
Aims to eliminate domain bias in authentication without domain labels.
problem Authentication models are biased due to domain differences.
method Discover latent domains and eliminate domain difference alternately, using a meta-learning framework.
result Eliminates domain difference in authentication without domain labels.
Algorithm reduces regret in multi-player bandits with unknown collision rewards.
problem Reducing regret in multi-player multi-armed bandits with unknown collision rewards.
method Proposes an algorithm that combines a modified successive elimination strategy with a communication protocol to estimate suboptimality gaps and coordinate among players.
result Achieves logarithmic regret for the problem when collision reward is unknown.
Smart watches can identify smoking gestures with high accuracy.
problem Identifying smoking gestures to prevent relapses.
method Used accelerometer sensors in smart watches and Artificial Neural Networks (ANNs).
result 85%-95% success rates in identifying smoking gestures.
We study the effect of the social stratification on the wealth distribution on a system of interacting economic agents that are constrained to interact only within their own economic class. The economical mobility of the agents is related to its success in exchange transactions. Different wealth distributions are obtai…
Stochastic regularization of neural networks (e.g. dropout) is a wide-spread technique in deep learning that allows for better generalization. Despite its success, continuous-time models, such as neural ordinary differential equation (ODE), usually rely on a completely deterministic feed-forward operation. This work pr…
We simplify Khovanov homology for torus braids using Gaussian elimination.
problem Computing Khovanov homology for torus braids is complex and computationally intensive.
method Applying Gaussian elimination to reduce the number of generators in the Khovanov chain complex.
result We provide a bound on the number of generators in the whittled complex at fixed homological degree.
This paper investigates Shampoo's heuristics and decouples preconditioner updates.
problem Improving Shampoo's heuristics for training neural networks.
method Decomposing preconditioner updates, correcting eigenvalues, and adapting eigenbasis computation frequency.
result Principled techniques to remove Shampoo's heuristics and improve training algorithms.
A wide class of machine learning algorithms can be reduced to variable elimination on factor graphs. While factor graphs provide a unifying notation for these algorithms, they do not provide a compact way to express repeated structure when compared to plate diagrams for directed graphical models. To exploit efficient t…
We develop an approach for feature elimination in statistical learning with kernel machines, based on recursive elimination of features.We present theoretical properties of this method and show that it is uniformly consistent in finding the correct feature space under certain generalized assumptions.We present four cas…
In this paper, we theoretically prove that adding one special neuron per output unit eliminates all suboptimal local minima of any deep neural network, for multi-class classification, binary classification, and regression with an arbitrary loss function, under practical assumptions. At every local minimum of any deep n…
Generative Adversarial Networks (GANs) are a powerful class of generative models. Despite their successes, the most appropriate choice of a GAN network architecture is still not well understood. GAN models for image synthesis have adopted a deep convolutional network architecture, which eliminates or minimizes the use …
Two new feature selection algorithms improve on RFE.
problem Optimal feature selection for faster and more accurate models.
method Fibonacci and k-Subsecting Recursive Feature Elimination.
result Faster feature selection with comparable predictive performance.
-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcs.LG
In this paper, we consider the problem of online learning of Markov decision processes (MDPs) with very large state spaces. Under the assumptions of realizable function approximation and low Bellman ranks, we develop an online learning algorithm that learns the optimal value function while at the same time achieving ve…
A novel algorithm reduces communication costs in federated best arm identification.
problem Identifying the best arm in a federated multi-armed bandit setup with minimal communication cost.
method Proposes a novel algorithm called FedElim that communicates only in exponential time steps.
result Demonstrates that communication is almost cost-free in FedElim, with a total cost at most 3 times the maximum under its variant.
Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Accesscs.LG
Improved sample complexity for diffusion models without needing empirical risk minimizers.
problem Theoretical limitations in sample complexity for diffusion models.
method Structured decomposition of score estimation error, eliminating dependence on neural network parameters.
result Achieved sample complexity bound of O(ε^(-4)) without empirical risk minimizer access.
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.
We study an adaptive source seeking problem, in which a mobile robot must identify the strongest emitter(s) of a signal in an environment with background emissions. Background signals may be highly heterogeneous and can mislead algorithms that are based on receding horizon control. We propose AdaSearch, a general algor…
An increasing number of sensors on mobile, Internet of things (IoT), and wearable devices generate time-series measurements of physical activities. Though access to the sensory data is critical to the success of many beneficial applications such as health monitoring or activity recognition, a wide range of potentially …
Reviews recent findings on neural network landscapes.
problem Non-convexity of loss functions causing bad landscapes.
method Rigorous geometric analysis and empirical exploration.
result Wide neural nets may have sub-optimal local minima.
We study a non-concave optimization problem in which a financial company maximizes the expected utility of the surplus under a risk-based regulatory constraint. For this problem, we consider four different prevalent risk constraints (Expected Shortfall, Expected Discounted Shortfall, Value-at-Risk, and Average Value-at…