LEAQI learns to query an expert less often for noisy guidance.
problem Active imitation learning with noisy guidance to reduce expert query complexity.
method Developed LEAQI, a difference classifier that predicts expert disagreement with noisy heuristic.
result Significantly fewer queries to the expert with comparable or better accuracy.
Fairly allocate items with noisy queries, reducing envy.
problem Fairly allocate indivisible goods with unknown valuations.
method Use Gaussian noisy queries to find an envy-free allocation.
result The optimal number of queries scales as \( \frac{m^{2.5}}{Δ^2} \) for large negative-envy.
Paper presents efficient algorithms for reconstructing noisy pooled data.
problem Reconstructing hidden states from noisy pooled data.
method Simple and efficient distributed algorithms for two noise models.
result Our algorithms reconstruct exact initial states with high probability.
Paper reveals free information from differential privacy mechanisms improving query accuracy.
problem Improving query accuracy with differential privacy mechanisms.
method Analysis of Noisy Max and Sparse Vector mechanisms.
result Noisy Max releases the noisy gap between the approximate maximizer and runner-up.
Interactive IL algorithm queries noisy expert for feedback, reducing sample size.
problem Imitation learning with noisy expert feedback requires many samples.
method Selective sampling algorithm with online regression oracle.
result Interactive IL algorithm reduces query complexity and improves performance.
In this paper, we initiate a rigorous theoretical study of clustering with noisy queries (or a faulty oracle). Given a set of n elements, our goal is to recover the true clustering by asking minimum number of pairwise queries to an oracle. Oracle can answer queries of the form : "do elements u and v belong to the…
Study exact community recovery in noisy SBM with limited queries.
problem Community recovery in noisy stochastic block models with limited queries.
method Balanced uniform querying, two-stage adaptive strategy, sublinear queries, subsampled graph.
result Adaptive querying can improve exact recovery limits in noisy SBM.
New algorithm finds k-centers from noisy distance estimates.
problem Finding k-centers in unknown metric spaces with noisy distance queries.
method Active algorithms using UCB, Thompson Sampling, and Track-and-Stop.
result Approximation ratio of two with high probability.
Efficiently clusters noisy data with minimal queries.
problem Clustering elements with noisy oracle feedback.
method Combination of sampling strategy and correlation clustering algorithm.
result First polynomial-time algorithms for NP-hard optimization problem.
Algorithm learns nearest neighbor graph from noisy distance queries.
problem Learning nearest neighbor graph from noisy distance samples.
method Active algorithm to find graph with high probability, analyzing query complexity.
result Empirically and theoretically efficient, needing only O(n log(n)Delta^-2) queries.
QActor optimizes learning from noisy labeled data streams by querying experts for clean labels.
problem Learning from noisy labeled data in continuous streams with limited oracle queries.
method Combines quality models for filtering and oracle queries for true labels, dynamically adjusting query limits.
result QActor nearly matches optimal accuracy with up to 6% additional ground truth data from experts.
Study learns linear utility functions from comparisons, showing learnability gaps between passive and active learning.
problem Learn linear utility functions from pairwise comparison queries.
method Analyzes passive and active learning settings, considering noise-free and noisy query responses.
result Efficient learnability of linear utilities in passive learning, but not for utility parameters without strong assumptions.
Algorithm identifies nearest mode in noisy data.
problem Identifying the point with the minimum k-th nearest neighbor distance in unknown multivariate probability density.
method Sequential learning algorithm using noisy oracle queries to adaptively decide which points to query.
result Upper bounds on query complexity show significant improvement over baselines.
The problem of active diagnosis arises in several applications such as disease diagnosis, and fault diagnosis in computer networks, where the goal is to rapidly identify the binary states of a set of objects (e.g., faulty or working) by sequentially selecting, and observing, (noisy) responses to binary valued queries. …
Bayesian optimisation tackles uncertain inputs in noisy function evaluations.
problem Optimizing functions with uncertain query locations and noisy outcomes.
method Proposes a UCB algorithm for BO with uncertain inputs, using Gaussian process models.
result Theoretical and experimental results show the proposed algorithm outperforms conventional methods.
We characterize learnability for stochastic noisy bandits, identifying optimal query complexities.
problem Learnability of stochastic noisy bandit models.
method Complete characterization through model class analysis and proof of optimal query complexities.
result Characterization of learnability for stochastic noisy bandit models.
Paper proposes a modified uncertainty sampling method to speed up preference learning from noisy humans.
problem Learning preferences from humans with limited queries and noisy responses.
method Modified uncertainty sampling using expected output value to speed up preference learning.
result The modified method outperforms the baseline uncertainty sampling in preference learning.
Personalizes query completion in digital commerce with image-based vectors.
problem High bounce rate and low recurring users in query completion.
method Injects dense vectors from product images into a noisy channel model.
result Image-based personalization improves query completion and user experience.
Efficiently classifies binary labels with XOR queries, even under noisy conditions.
problem Binary classification with unknown labels using XOR queries.
method Effective query type and an efficient inference algorithm for noisy conditions.
result Achieves information-theoretic limit on optimal number of queries.
Tree-search algorithm optimizes noisy black-box functions with multi-fidelity queries.
problem Optimizing noisy functions with expensive evaluations and low-cost approximations.
method Tree-like hierarchical partitions and multi-fidelity bandit tree-search algorithm.
result Simple regret bounds for the proposed algorithm.
The study examines how many samples are needed to minimize a noisy convex function with inaccurate gradient estimates.
problem Determining the number of samples needed to minimize a noisy convex function with inaccurate gradient estimates.
method Using Stochastic Convex Optimization as a case study, the study analyzes the relationship between the number of samples and the accuracy of gradient estimates.
result The study provides partial answers to the question, showing that a general analyst requires Ω(1/ε3) samples and that under certain assumptions, ildeΩ(1/ε2.5) samples are necessary for gradient descent to interact with the oracle. We study active learning where the labeler can not only return incorrect labels but also abstain from labeling. We consider different noise and abstention conditions of the labeler. We propose an algorithm which utilizes abstention responses, and analyze its statistical consistency and query complexity under fairly nat…
Paper tackles dense subgraph discovery with noisy feedback.
problem Discover dense subgraphs in edge-weighted graphs with noisy feedback.
method Proposes polynomial-time and scalable algorithms for dense subgraph discovery.
result Polynomial-time algorithm obtains nearly-optimal solution with high probability.
Paper shows semi-supervised clustering is equivalent to a type of source coding.
problem Multiclass labeling of unlabeled elements with noisy binary queries.
method Locally encodable source coding approach, using pairwise queries.
result Lower bounds on the number of queries required for correct labeling.
Lower bounds on queries needed for finding stationary points in non-convex optimization.
problem Finding ε-stationary points in non-convex stochastic optimization. method Proving lower bounds on the number of queries required by stochastic first-order methods.
result Lower bounds on the number of queries required to find ε-stationary points are tight and optimal. Paper tackles noisy comparison oracle for robust clustering algorithms.
problem Finding robust clustering algorithms under noisy comparison oracle.
method Develops algorithms for k-center clustering and agglomerative hierarchical clustering using noisy comparison oracle.
result Proves robust algorithms achieve good approximation guarantees with high probability.
Adapts large transformer model for search query intent understanding.
problem Understanding and predicting user intents from search queries.
method Adapts BERT-like architecture for search queries, accounts for query noisiness and sparseness.
result Builds a shareable deep learning model for query intent identification.
Estimates heavy hitters in data streams with queries, balancing accuracy and efficiency.
problem Identifying elements with high probability in i.i.d. samples.
method Sequential estimation algorithms for two query models: index and pair queries.
result Upper and lower bounds on query complexity for different distributions and noise models.
Study optimizes query strategy for private learning in eavesdropping scenarios.
problem Private sequential learning in the presence of eavesdropping.
method Developed new querying strategies and analytical techniques.
result Proved tight upper and lower bounds on optimal query complexity.
Study efficient graph optimization with noisy data.
problem Optimizing functions on graphs with noisy observations.
method Best-arm identification and simulated annealing variants.
result Near-optimal solutions found with small query numbers.
Generative model blends query input with latent states for structured improvisation.
problem Generating structured music from latent states of a neural network.
method Used a Variational Autoencoder (VAE) trained on a specific style corpus, and controlled blending with a noisy channel.
result Generated music with longer-term structure that blends query input with network style.
Suppose, we are given a set of n elements to be clustered into k (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "do two elements u and v belong to the same cluster?". The goal is to recover the optimum clustering by asking the minimum number of quer…
Paper tackles private optimization for non-smooth objectives efficiently.
problem Private stochastic convex optimization for non-smooth objectives.
method Noisy mirror descent algorithm.
result Achieves optimal rates in statistical complexity and number of queries.
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…
The probabilistic bisection algorithm (PBA) solves a class of stochastic root-finding problems in one dimension by successively updating a prior belief on the location of the root based on noisy responses to queries at chosen points. The responses indicate the direction of the root from the queried point, and are incor…
Motivation: Public and private repositories of experimental data are growing to sizes that require dedicated methods for finding relevant data. To improve on the state of the art of keyword searches from annotations, methods for content-based retrieval have been proposed. In the context of gene expression experiments, …
We consider the problem of global optimization of an unknown non-convex smooth function with zeroth-order feedback. In this setup, an algorithm is allowed to adaptively query the underlying function at different locations and receives noisy evaluations of function values at the queried points (i.e. the algorithm has ac…
This paper studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
problem Optimizing an unknown function with limited evaluations.
method Studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
result Minimax rates over Besov spaces are identical to those over the smallest Hölder space into which Besov spaces embed.
Proposes an active RBI framework using Rényi information measures for more informed decision-making.
problem Optimal latent variable estimates in real-time settings with streaming noisy observations.
method Unified inference and query selection steps through Rényi entropy and α-divergence; new objective called Momentum for exploration.
result Analytically demonstrates superior performance compared to conventional methods like mutual information.
Unified framework for simulation-based inference learns a single model for multiple tasks.
problem Simulation-based inference for multiple tasks with limited model retraining.
method Unified flow-matching generative model with query-aware masking distribution.
result Competitive performance on various inference tasks and real-world problems.
New oracle uses uncertainty for active classification with noisy feedback.
problem Improving query complexity in interactive binary classifier learning.
method Proposes a new pairwise comparison oracle that considers uncertainty and an adaptive labeling algorithm.
result Demonstrates improved performance and efficiency compared to existing methods.
Efficiently finds target objects using comparisons without features, scalable in both blind and non-blind settings.
problem Finding target objects using comparisons in latent feature spaces, blind or not.
method Bayesian comparison-based search algorithm for non-blind setting, combined with triplet embedding for blind setting.
result Query complexity on real-world datasets comparable to non-blind setting, demonstrating scalability.
Ricci-Filtration enhances retrieval-augmented generation rerankers for query-answer tasks by using discrete Ricci flow on graphs.
problem Improving retrieval-augmented generation rerankers for query-answer tasks.
method Discrete Ricci flow on graphs to evaluate structural importance of chunks.
result Ricci-Filtration outperforms baseline methods in accuracy, precision, recall, and F1 scores.
The paper studies estimating the normalizing constant using queries to a black-box function in RKHS.
problem Estimating the normalizing constant of a function in a reproducing kernel Hilbert space.
method Combines Bayesian quadrature and Bayesian optimization approaches, considering different levels of difficulty based on the parameter λ.
result The difficulty of estimating the normalizing constant varies between Bayesian quadrature and Bayesian optimization, even with noisy function evaluations.
This paper explores the adaptive (active) PAC (probably approximately correct) top-k ranking (i.e., top-k item selection) and total ranking problems from l-wise (l≥2) comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored …
We consider the problem of approximate K-means clustering with outliers and side information provided by same-cluster queries and possibly noisy answers. Our solution shows that, under some mild assumptions on the smallest cluster size, one can obtain an (1+ε)-approximation for the optimal potential with probabilit…
Traditional nearest points methods use all the samples in an image set to construct a single convex or affine hull model for classification. However, strong artificial features and noisy data may be generated from combinations of training samples when significant intra-class variations and/or noise occur in the image s…
Estimates user preferences from noisy paired comparisons.
problem Estimating user preferences from noisy paired comparisons.
method Greedy information maximization strategies.
result Superior preference estimation over state-of-the-art methods.