Paper optimizes sample selection for top-k arms in stochastic bandits.
problem Identifying the k arms with the largest means in stochastic bandits.
method Developed an elimination-based algorithm with sample complexity matching lower bounds.
result Algorithm strictly dominates state-of-the-art for Best-k-Arm problem.
A new algorithm for selecting top-k arms in extreme contextual bandits with improved efficiency.
problem Selecting top-k arms from a large set with contextual information and limited rewards.
method Proposes an algorithm for both non-extreme and extreme settings, using Inverse Gap Weighting and arm hierarchy models.
result Achieves improved regret guarantees for extreme settings with significant computational and statistical efficiency.
DART optimizes subset selection in non-linear bandit problems.
problem Optimizing subset selection in non-linear bandit problems with correlated rewards.
method DART algorithm for combinatorial bandits without individual arm feedback or linearity assumption.
result DART achieves a regret bound of i l d e O ( K K N T ) ilde{\mathcal{O}}(K\sqrt{KNT}) i l d e O ( K K N T ) . Polynomial-time algorithms for identifying the best super arm in full-bandit feedback.
problem Finding the best super arm in a set of single arms with full-bandit feedback.
method Proposed polynomial-time bandit algorithms and an approximation algorithm for the 0-1 quadratic maximization problem.
result Polynomial-time algorithms for top-k selection problems.
Top-two algorithm improved for best-k-arm selection.
problem Best-k-arm identification in multi-armed bandits.
method Information-directed selection based on dual variables.
result Top-two Thompson sampling with IDS is asymptotically optimal.
A new algorithm for top-k combinatorial bandits with full-bandit feedback.
problem Optimizing decisions among subsets of arms with only aggregate rewards observed.
method CSAR algorithm using Hadamard matrices for estimating individual arm rewards.
result Proved a tight lower bound on sample complexity for k = O ( 1 ) k=O(1) k = O ( 1 ) . Master-slave architecture tackles combinatorial multi-armed bandits with diversity constraints.
problem Solving top- K K K combinatorial multi-armed bandits with non-linear feedback and diversity constraints. method Master-slave architecture with six slave models, teacher learning, and policy co-training.
result Significantly outperforms existing algorithms in synthetic and real datasets.
A new algorithm THV-UCB reduces regret in multi-objective bandit problems.
problem Maintaining a small set of actions that jointly approximate the Pareto frontier in multi-objective slate selection.
method THV-UCB, an optimistic algorithm that selects arms based on optimistic estimates of their marginal hypervolume contributions.
result The algorithm achieves a gap-free regret bound of i l d e O ( d n k T ) ilde{O}(d\sqrt{nkT}) i l d e O ( d nk T ) and a gap-dependent bound of i l d e O ( n k 2.5 / Δ min ) ilde{O}(nk^{2.5}/Δ_{\min}) i l d e O ( n k 2.5 / Δ m i n ) . Paper introduces efficient top-k selection with differential privacy.
problem Efficiently selecting top-k elements with differential privacy.
method Oneshot Laplace mechanism, generalizing Report Noisy Max.
result Noise level of O(sqrt(k)/eps) for approximate differential privacy.
The paper tackles noisy multi-armed bandit problems with improved regret guarantees.
problem Tackling noisy evaluations in multi-armed bandit problems.
method Derives different algorithmic approaches and theoretical guarantees based on the type of observation functions.
result Improved regret guarantees for noisy linear functions of true rewards.
Introduces top- k k k regularization for better feature selection in machine learning.
problem Limited ability of existing feature selection methods to reconcile feature representativeness and inter-correlations.
method Top- k k k regularization, which induces a sub-architecture on the model's architecture to select informative features and model complex relationships. result Uniform approximation error bound for top- k k k regularization approximating high-dimensional sparse functions. Unified model for prediction and deferral selects top-k entities efficiently.
problem Efficiently selecting top-k entities for deferral in machine learning.
method One-stage Top- k k k Learning-to-Defer framework with a convex surrogate. result Unified model achieves superior accuracy-cost trade-offs.
New algorithms identify top K arms with high confidence.
problem Identifying K arms with the largest means from N stochastic bandit arms.
method Proposed new practical algorithms with nearly optimal sample complexity.
result Outperform state-of-the-art algorithms in practical applications.
A new technique called the Simulator analyzes adaptive sampling, improving on existing methods.
problem Analyzing the difficulty of distinguishing good from bad sampling strategies with limited data.
method A novel approach considering the difficulty of distinguishing strategies, matching strengths of Fano and change-of-measure techniques.
result First instance-based lower bounds for top-k problem, revealing new phenomena.
The paper optimizes identifying top k k k arms from a fraction of ρ ρ ρ arms in stochastic bandits.
problem Identifying k k k distinct arms among the top ρ ρ ρ fraction of arms in stochastic bandits with a PAC tolerance. method The paper considers two cases: known and unknown threshold of top arms' expected rewards. It proves lower bounds and proposes algorithms for each case, showing sample complexity optimality for two algorithms.
result Two algorithms are sample complexity optimal (up to constant factors) and the other two are optimal up to a log factor.
Paper introduces MPES for top-k ranking BO with preferential observations.
problem Handling top-k ranking and tie/indifference observations in Bayesian optimization.
method Designs a surrogate model and introduces MPES acquisition function.
result MPES outperforms existing acquisition functions in handling preferential observations.
New algorithms find all ε-good arms in stochastic bandits.
problem Finding all arms with means above a specified threshold in stochastic bandits.
method Two algorithms introduced to identify all ε-good arms.
result Demonstrated great empirical performance on large datasets.
New algorithm for choosing top-K options efficiently with linear space and non-linear feedback.
problem Choosing the best K out of N options at each time instant with efficient trade-off between exploration and exploitation.
method CMAB-SM algorithm, divide-and-conquer strategy, linear space, non-linear feedback.
result Achieves a sub-linear regret bound of $O(K^{ rac{1}{2}}N^{ rac{1}{3}}T^{ rac{2}{3}})$ .
Top-k sparsification reduces deep learning communication costs.
problem Reducing communication overhead in distributed deep learning.
method Extensive experiments and theoretical analysis of Top-k sparsification.
result A tighter bound for Top-k operator derived, improving scaling efficiency.
Proposes differentiable and sparse top-k operators for neural networks.
problem Discontinuity of top-k operator makes it unsuitable for end-to-end training with backpropagation.
method Formulates top-k as a linear program over permutahedron, introduces p-norm regularization, and uses isotonic optimization.
result Successfully applied to neural network pruning, fine-tuning, and routing.
New method identifies cluster representatives with minimal pulls.
problem Identifying cluster representatives in multi-armed bandits.
method Fixed confidence approach using confidence intervals.
result Sample complexity matches theoretical lower bound.
Unified framework for deferring queries to top-k experts, improving accuracy-cost trade-offs.
problem Limitation of existing L2D frameworks to single-expert deferral.
method Top- k k k Learning-to-Defer framework, including adaptive Top- k ( x ) k(x) k ( x ) variant. result Superior accuracy-cost trade-offs with multi-expert deferral.
Thompson Sampling tackles USS, a sequential selection problem without feedback.
problem Unsupervised Sequential Selection (USS) problem with fixed costs and ordered arms.
method Thompson Sampling algorithm for USS problem.
result Thompson Sampling achieves near optimal regret and better performance than existing algorithms.
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.
New insights into the top-K sparse softmax gating function for deep learning.
problem Understanding the theoretical effects of the top-K sparse softmax gating function on density and parameter estimations.
method Using a Gaussian mixture of experts, novel loss functions, and theoretical analysis.
result The convergence rates of density and parameter estimations are parametric under certain conditions, but slow under over-specified models.
RAMPART ranks top-k features more accurately than existing methods.
problem Accurate ranking of important features in machine learning.
method Adaptive sequential halving strategy combined with ensembling techniques.
result RAMPART achieves the correct top-k ranking with high probability.
Algorithm identifies best arm with biased proxy and selective ground truth audits.
problem Fixed-confidence best-arm identification with biased proxy and selective ground truth.
method Propensity-weighted estimator and adaptive auditing algorithm.
result Plug-in Neyman rule achieves near-oracle audit efficiency.
Proposes a max-utility arm selection strategy for reducing cumulative regret in sequential query recommendations.
problem Reduces cumulative regret in sequential query recommendations for closed loop interactive learning settings.
method Proposes a max-utility arm selection strategy based on the maximum utility of arms.
result Improves cumulative regret substantially compared to baseline algorithms and random selection.
Algorithm learns optimal arm selection in unsupervised sequential selection with contextual information.
problem Learning optimal arm selection in unsupervised sequential selection with contextual information.
method Proposes an algorithm for the contextual USS problem under the CWD property, demonstrating sub-linear regret.
result Demonstrates sub-linear regret for the proposed algorithm.
Paper tackles risk-aware portfolio selection using multi-armed bandit.
problem Sequential portfolio selection under uncertainty.
method Incorporates risk-awareness into multi-armed bandit, constructs portfolio through asset filtering and risk minimization.
result Achieves balance between risk and return.
Improved theoretical guarantees for Top Two algorithms.
problem Theoretical support for best arm identification with bounded distributions.
method General analysis of Top Two methods, identifying desirable properties and replacing sampling step.
result Theoretical support for Top Two algorithms with bounded distributions.
New methods provide stable ranking without assumptions on data distributions.
problem Stability issues in ranking problems with noisy data.
method Developed a stability framework and two ranking operators.
result Guaranteed stability without assumptions on data distributions.
Proposes learning ordered Top-k attacks for image classification.
problem Vulnerability of DNNs to adversarial attacks, especially white-box targeted attacks.
method Adversarial distillation framework to compute adversarial probability distributions and minimize KL divergence.
result Outperforms C&W method in Top-1 and Top-5 settings for image classification.
New algorithm identifies best arm in rested bandit setting.
problem Best arm identification in rested bandit with decreasing losses.
method Introduced a novel best arm identification problem and analyzed an arm elimination algorithm.
result Regret vanishes as time horizon increases, with convergence rate depending on expected loss function.
The paper analyzes top-k classification and proposes consistent loss functions.
problem Understanding consistency of top-k classification in challenging tasks.
method Theoretical analysis, defining top-k calibration, proposing new loss functions.
result Proposes a new consistent hinge loss and a top-k calibrated convex loss.
Paper analyzes trade-offs in top-k classification accuracies and proposes a new loss function.
problem CE loss does not always optimize top-k prediction, especially with complex data.
method Introduces a novel top-k transition loss to improve top-k accuracy.
result Our loss function improves top-k accuracy, especially for k > 10.
Improves YouTube's recommendation system by correcting biases in logged feedback.
problem Data biases in logged feedback from multiple behavior policies.
method Top-K off-policy correction applied to REINFORCE algorithm.
result Efficacy demonstrated through simulations and live experiments.
Class ambiguity is typical in image classification problems with a large number of classes. When classes are difficult to discriminate, it makes sense to allow k guesses and evaluate classifiers based on the top-k error instead of the standard zero-one loss. We propose top-k multiclass SVM as a direct method to optimiz…
A method for finding most influential sets reduces a complex problem to a sequence of simpler top- k k k problems.
problem Identifying most influential subsets in complex models.
method Reduces the problem to a sequence of top- k k k problems using Dinkelbach's method. result The method returns a globally optimal set for the univariate ratio objective, including partial linear models.
Algorithm selects k arms from context-dependent options using Plackett-Luce model.
problem Selecting k arms from context-dependent options with Plackett-Luce feedback.
method Proposes CPPL algorithm inspired by UCB, evaluated on synthetic and real data.
result Demonstrates effectiveness of CPPL algorithm in online algorithm selection.
Study best arm identification in restless Markov multi-armed bandits with state-dependent transitions.
problem Identify the best arm in a multi-armed bandit with time-varying states.
method Propose a sequential policy to select arms without knowing their exact TPMs.
result Upper and lower bounds on expected time to find the best arm match in a special case.
New method selects best exploration strategies in uncertain environments.
problem Selecting optimal strategies in unknown, multi-strategy environments.
method Formulates Multi-Armed Bandits problem with diversity of effects as reward signal.
result Method outperforms fixed mixtures of strategies in diverse, challenging conditions.
Algorithm reduces regret in restless multi-armed bandits by adaptively sequencing arm choices.
problem Minimizing regret in restless multi-armed bandits with unknown dynamics.
method Adaptive Sequencing Rules (ASR) algorithm that selects arms in a consecutive manner.
result Achieves logarithmic regret order with time and finite-sample bound.
New distributions allow greedy arm selection in sparse bandit problems.
problem Sparse contextual bandit problem with sparse parameters and feature distributions.
method Introduced new distribution classes and demonstrated that mixtures of these distributions are also greedy-applicable.
result Greedy algorithm applicable to a wider range of arm feature distributions, including those with origin-asymmetric support.
Proposes DEXP3.M for unknown delay in multi-arm bandit with multiple play.
problem Unknown delays in adversarial multi-armed bandit with multiple play.
method DEXP3.M algorithm addressing the challenge of associating feedback losses to arms.
result Regret bound is only slightly worse than single play setting.
FedSel uses local differential privacy to protect data privacy in federated SGD.
problem Privacy leakage from gradients in federated SGD.
method Two-stage framework with top-k dimension selection and gradient accumulation.
result FedSel reduces privacy leakage by privately selecting important dimensions.
The paper studies ranking algorithms from pairwise and listwise comparisons, deriving lower bounds and optimal algorithms.
problem Designing efficient ranking algorithms from pairwise and listwise comparisons.
method Deriving lower bounds and proposing optimal algorithms for top-k and total ranking problems.
result The proposed algorithms match the derived lower bounds and are optimal up to a logarithmic factor.
New algorithm for top-K ranking with linear time and competitive ratio of sqrt(n).
problem Identifying top K items from noisy pairwise comparisons.
method Linear time algorithm with competitive ratio of sqrt(n) under strong stochastic transitivity model.
result Tight competitive ratio of sqrt(n) for top-K ranking problem.