New algorithm achieves instance-optimality in decision making.
problem Develop adaptive algorithms for interactive decision making.
method Introduce Allocation-Estimation Coefficient (AEC) and develop AE2 algorithm. result First non-asymptotic instance-optimal performance guarantees.
Develops new instance-optimality concepts in differential privacy.
problem Improving privacy guarantees in statistical estimation.
method Introduces local minimax risk and unbiased mechanisms, and develops inverse sensitivity mechanisms.
result Inverse sensitivity mechanisms are nearly instance optimal for a wide range of functions.
Algorithm extsc{Pedel} learns near-optimal policies efficiently on specific problems.
problem Learning near-optimal policies in linear MDPs with minimal samples.
method Online experiment design to focus exploration on relevant directions.
result Achieves instance-dependent complexity, outperforming minimax-optimal algorithms.
The research proposes a stopping rule for reinforcement learning algorithms based on instance-dependent confidence.
problem Dramatic variation in convergence rates of reinforcement learning algorithms due to problem structure.
method Develops instance-dependent confidence regions and a data-dependent stopping rule for MDP policy evaluation and optimal value estimation.
result Proposes a stopping rule that adapts to the instance-specific difficulty of the problem, allowing for early termination.
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
Study binary hypothesis testing with privacy and communication constraints.
problem Binary hypothesis testing under local differential privacy and communication constraints.
method Qualifies results as minimax or instance optimal, develops instance-optimal algorithms.
result Achieves minimum possible sample complexity under both privacy and communication constraints.
Private density estimation in Wasserstein distance for geographic populations.
problem Private estimation of population density distributions.
method Differentially private algorithms for Wasserstein distance, instance-optimal.
result Uniformly achievable instance-optimal rates in both 1D and 2D.
Private KL distribution estimation improved with instance-optimality.
problem Minimizing KL divergence between true and estimated distributions.
method Construct minimax optimal private estimators, then focus on instance-optimality.
result Achieved instance-optimality up to constant factors for KL estimation.
New algorithm optimally evaluates policies with linear approximations.
problem Policy evaluation with linear function approximation.
method Accelerated, variance-reduced fast temporal difference algorithm (VRFTD).
result VRFTD matches both deterministic and stochastic lower bounds.
Paper explores rate-preserving reductions between Blackwell approachability and no-regret learning.
problem Tackles rate-preserving reductions between Blackwell approachability and no-regret learning.
method Studies fine-grained reductions and optimal rates of convergence.
result Shows that rate-preserving reductions do not always hold, but provides conditions for when they do.
Paper establishes first instance-dependent lower bound for PAC reinforcement learning.
problem Identifying near-optimal policies in tabular MDPs with minimal samples.
method Proposes instance-dependent lower bound for sample complexity.
result Lower bound closely matches PEDEL algorithm's sample complexity.
New algorithm reduces contextual bandit identification to argmax calls.
problem Best-arm identification in stochastic contextual bandits.
method Instance-optimal PAC algorithm using argmax oracle calls.
result First instance-dependent PAC sample complexity for contextual bandits.
Paper proposes a universal probabilistic model for handling instance-dependent label noise.
problem Instance-dependent label noise in data quality challenges DNN training robustness.
method Categorizes instances into confusing and unconfusing, proposes a probabilistic model.
result Significant improvements in robustness over state-of-the-art methods on various datasets.
New algorithms for model selection in linear bandits adapt to instance complexity.
problem Adapting to the instance-dependent complexity of the true model in linear bandits.
method Design of algorithms in fixed confidence and fixed budget settings, leveraging experimental design and selection-validation procedures.
result Near instance optimal guarantees for model selection in linear bandits.
This paper introduces collective counterfactual explanations for groups of instances in classification models.
problem Understanding how classification models make decisions for groups of instances.
method Novel Mathematical Optimization models to find collective counterfactual explanations that minimize total perturbation cost.
result Detects critical features for entire dataset classification and handles outliers.
Optimal best-arm identification with known number of optimal arms.
problem Identifying the best arm in a multi-armed bandit with multiple optimal arms under fixed confidence.
method Deriving a new information-theoretic lower bound and proposing a modified stopping rule.
result Achieving asymptotic instance-optimality with a new lower bound and new stopping rule.
New method estimates optimal Q-values with better accuracy for specific problems.
problem Estimating optimal Q-values in reinforcement learning is difficult and varies by problem instance.
method Local minimax framework and variance-reduced Q-learning.
result Sharp lower bounds on estimation accuracy for Q-learning.
Method reweights instances and classes to improve robustness in noisy data.
problem Improving deep learning performance in the presence of label noise.
method Formulates constrained optimization problems to assign importance weights to instances and class labels.
result Significant performance gains observed in benchmark datasets with label noise.
No communication allows optimal instance-dependent regret guarantees in multi-player bandits.
problem Achieving optimal instance-dependent regret in multi-player multi-armed bandits without communication.
method Characterization of Pareto optimal trade-offs and development of an algorithm.
result Achieving optimal instance-dependent regret requires strict sub-optimality in other regimes.
New algorithm IAC recovers hidden communities in labeled SBM with optimal performance.
problem Recovering hidden communities in Labeled Stochastic Block Model with varying cluster sizes.
method IAC (Instance-Adaptive Clustering) algorithm, consisting of spectral clustering and iterative likelihood-based improvements.
result IAC achieves optimal performance matching instance-specific lower bounds in expectation and with high probability.
Improved stochastic optimization outperforms standard methods.
problem Optimizing smooth, strongly convex functions with noisy data.
method Variance reduction strategy called VISOR.
result VISOR achieves optimal sample complexity and oracle complexity.
Recently neural networks and multiple instance learning are both attractive topics in Artificial Intelligence related research fields. Deep neural networks have achieved great success in supervised learning problems, and multiple instance learning as a typical weakly-supervised learning method is effective for many app…
Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational …
New methods improve temporal difference learning for policy evaluation in Markov decision processes.
problem Improving temporal difference learning for policy evaluation in Markov decision processes.
method Introduced variance-reduced forms of stochastic approximation to achieve non-asymptotic, instance-dependent optimality.
result Temporal difference learning is strictly suboptimal, but variance-reduced forms achieve optimality up to logarithmic factors.
New algorithm identifies best arm in semiparametric bandits with near optimal efficiency.
problem Fixed-confidence Best Arm Identification in semiparametric bandits with unknown baseline shift.
method Phase-elimination algorithm based on orthogonalized regression design.
result Nearly optimal high-probability sample-complexity upper bound established.
Classifier evasion consists in finding for a given instance x the nearest instance x′ such that the classifier predictions of x and x′ are different. We present two novel algorithms for systematically computing evasions for tree ensembles such as boosted trees and random forests. Our first algorithm uses a Mixe…
Recently, network lasso has drawn many attentions due to its remarkable performance on simultaneous clustering and optimization. However, it usually suffers from the imperfect data (noise, missing values etc), and yields sub-optimal solutions. The reason is that it finds the similar instances according to their feature…
Semi-supervised learning is pervasive in real-world applications, where only a few labeled data are available and large amounts of instances remain unlabeled. Since AUC is an important model evaluation metric in classification, directly optimizing AUC in semi-supervised learning scenario has drawn much attention in the…
We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a r…
We study the active learning problem of top-k ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top-k items with high probability by adaptively querying sets for comparisons and observing the noisy output of the most preferred item from each comparison. To ac…
We consider PAC-learning a good item from k-subsetwise feedback information sampled from a Plackett-Luce probability model, with instance-dependent sample complexity performance. In the setting where subsets of a fixed size can be tested and top-ranked feedback is made available to the learner, we give an algorithm w…
Study optimal and instance-dependent guarantees for solving linear equations with Markovian data.
problem Approximately solving linear fixed point equations with Markovian data.
method Non-asymptotic bounds and instance-dependent characterizations for stochastic approximation.
result Instance-optimality of the averaged SA estimator and matching upper and lower bounds.
Efficiently solves inverse classification problems for logistic and softmax models.
problem Finding instances that change classifier predictions.
method Closed-form solution for logistic regression, iterative optimization for softmax.
result Fast, exact solutions for high-dimensional instances and many classes.
Machine learning reduces combinatorial optimization problem dimensions.
problem Reducing the complexity of large combinatorial optimization problems.
method Generalization of a machine learning model for problem reduction on TSP.
result Machine learning can predict which variables are not part of an optimal solution.
Graph cuts find global optima for Potts models in slight perturbations.
problem Finding optimal solutions in Potts models with graph cuts.
method α-expansion algorithm for MAP inference, with certification for perturbations.
result All local minima are global minima in slight perturbations, and solutions are close to original.
LGS-Net improves NCO performance on combinatorial optimization tasks.
problem NP-hard combinatorial optimization problems in logistics, manufacturing, and drug discovery.
method LGS-Net uses a latent space model that conditions on problem instances and introduces Latent Guided Sampling for efficient inference.
result Empirical results show state-of-the-art performance on benchmark routing tasks.
New algorithms improve contextual bandit performance by adapting to problem difficulty.
problem Improving contextual bandit performance on problems with varying difficulty.
method Introducing complexity measures and oracle-efficient algorithms.
result Achieves optimal instance-dependent regret bounds for rich policy classes.
Study optimizes solving fixed-point equations using subspace search.
problem Solving linear fixed point equations in Hilbert spaces.
method Linear stochastic approximation scheme with Polyak--Ruppert averaging.
result Established optimal approximation factor for temporal difference learning methods.
New algorithm reduces regret for kernelized bandits by adapting to specific problem instances.
problem Efficiently learning the optimizer of an unknown function in RKHS with noisy oracle.
method Instance-dependent regret analysis and a new minimax near-optimal algorithm.
result New algorithm achieves better performance on specific problem instances.
Study task-guided exploration in linear dynamical systems, improving sample complexity.
problem Efficiently learning about an environment to complete a specific task.
method Proposed a computationally efficient experiment-design based exploration algorithm.
result Optimally explores the environment, collecting precise information needed to complete the task.
Multi-instance data, in which each object (bag) contains a collection of instances, are widespread in machine learning, computer vision, bioinformatics, signal processing, and social sciences. We present a maximum entropy (ME) framework for learning from multi-instance data. In this approach each bag is represented as …
Paper bounds PAC RL sample complexity in deterministic MDPs.
problem Identify ε-optimal policy with high probability.
method Proposes nearly matching upper and lower bounds on sample complexity, introduces deterministic return gap, uses graph-theoretical concepts and maximum-coverage exploration.
result First nearly matching upper and lower bounds on sample complexity for PAC RL in deterministic MDPs.
A new method improves adversarial robustness by optimizing importance weights.
problem Adversarial training's non-uniform robustness across different data points.
method Doubly-robust instance reweighted adversarial training using distributionally robust optimization.
result Improves robustness against attacks on the weakest data points.
A deep RL approach generates counterfactual instances efficiently.
problem Efficient generation of counterfactual instances for large datasets and diverse models.
method Deep reinforcement learning to optimize counterfactual instances in a single forward pass.
result Model-agnostic and scalable counterfactual generation.
Approximate algorithms for structured prediction problems---such as LP relaxations and the popular alpha-expansion algorithm (Boykov et al. 2001)---typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of thi…
Paper improves deep learning for instance-level classification from label proportions.
problem Dealing with noisy pseudo-labeling and high-entropy class distributions in LLP.
method Introducing a two-stage training approach with constrained optimization and mixup strategy.
result Significant performance improvement in instance-level classification.
New algorithm tackles heavy-tailed rewards in RL with instance-dependent regret bounds.
problem Efficient algorithms for RL with heavy-tailed rewards in large state-action spaces.
method Design of \textsc{Heavy-OFUL} for heavy-tailed linear bandits and \textsc{Heavy-LSVI-UCB} for RL with linear function approximation.
result First instance-dependent regret bounds for heavy-tailed rewards in RL with linear function approximation.
Quantum computing exploits basic quantum phenomena such as state superposition and entanglement to perform computations. The Quantum Approximate Optimization Algorithm (QAOA) is arguably one of the leading quantum algorithms that can outperform classical state-of-the-art methods in the near term. QAOA is a hybrid quant…