In this paper we study the adaptive learnability of decision trees of depth at most from membership queries. This has many applications in automated scientific discovery such as drugs development and software update problem. Feldman solves the problem in a randomized polynomial time algorithm that asks $\tilde O(2^…
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 “query algorithms”
In query learning, the goal is to identify an unknown object while minimizing the number of "yes" or "no" questions (queries) posed about that object. A well-studied algorithm for query learning is known as generalized binary search (GBS). We show that GBS is a greedy algorithm to optimize the expected number of querie…
Improved algorithm for selecting a hypothesis locally privately with fewer queries.
problem Locally private hypothesis selection with minimal privacy-preserving queries.
method Introduces a Scheffé graph to reduce query complexity for hypothesis selection.
result Algorithm performs queries, improving on previous methods.
New memory-query tradeoffs for convex optimization algorithms.
problem Optimizing memory usage for convex optimization algorithms.
method Analyzing randomized first-order algorithms for minimizing convex functions.
result Cutting plane methods are optimal in terms of memory and query complexity.
We consider the problem of learning a general graph using edge-detecting queries, where the number of vertices is given to the learner. The information theoretic lower bound gives for the number of queries, where is the number of edges. In case the number of edges is also given t…
We investigate the problem of active learning on a given tree whose nodes are assigned binary labels in an adversarial way. Inspired by recent results by Guillory and Bilmes, we characterize (up to constant factors) the optimal placement of queries so to minimize the mistakes made on the non-queried nodes. Our query se…
In query learning, the goal is to identify an unknown object while minimizing the number of "yes or no" questions (queries) posed about that object. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world, time-critical identification tasks such as emergency…
New algorithms learn MNL weights efficiently for any slate size.
problem Efficiently learn weights for MNL models given query access.
method Two algorithms: adaptive and non-adaptive, with specific query complexities.
result Optimal query complexities for both adaptive and non-adaptive cases.
New algorithm for clustering with faulty oracle achieves optimal queries and efficiency.
problem Clustering with a faulty oracle, especially for multiple clusters.
method Built on stochastic block model, provides nearly-optimal query complexity.
result Time-efficient algorithm with nearly-optimal query complexity for all constant k and any δ.
Most content-based image retrieval systems consider either one single query, or multiple queries that include the same object or represent the same semantic information. In this paper we consider the content-based image retrieval problem for multiple query images corresponding to different image semantics. We propose a…
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.
Adaptive compute allocation improves model performance by prioritizing harder queries.
problem Inefficiency in allocating test-time compute uniformly across all queries.
method Formulated as a bandit learning problem, proposed adaptive algorithms that estimate query difficulty and allocate compute accordingly.
result Achieved up to 15.29% relative performance improvement on various benchmarks.
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.
Algorithm improves query recommendations with immediate user feedback.
problem Lack of adaptability to immediate user feedback in query recommendation algorithms.
method Augmented transformer-based causal language models with multi-armed bandit framework.
result Substantial improvement in per-round regret compared to state-of-the-art models.
We consider the problem of adaptively PAC-learning a probability distribution 's mode by querying an oracle for information about a sequence of i.i.d. samples generated from . We consider two different query models: (a) each query is an index for which the oracle reveals…
New algorithm learns halfspaces with membership queries, achieving near optimal label complexity.
problem Learning halfspaces with membership queries.
method Proposed a new algorithm for learning halfspaces with membership queries, proving near optimal label complexity.
result Achieves near optimal label complexity for learning halfspaces.
Algorithm approximates target distribution using weight queries.
problem Approximating a distribution without sampling.
method Interactive algorithm using weight queries and UCB approach.
result Approximation bound on total variation distance.
We consider a query-based data acquisition problem for binary classification of unknown labels, which has diverse applications in communications, crowdsourcing, recommender systems and active learning. To ensure reliable recovery of unknown labels with as few number of queries as possible, we consider an effective quer…
Study on how many queries an adversary needs to make to match the best attack in white-box model.
problem Query complexity of adversarial attacks in machine learning models.
method Investigates the number of queries required for an adversary to match the best possible attack in the white-box model, using entropy of decision boundaries as a measure.
result Lower bound on the number of queries required for an adversary to match the best possible attack in the white-box model.
Noise addition prevents overfitting in adaptive data analysis.
problem Overfitting in repeated use of a data sample via adaptively chosen queries.
method Simple noise addition algorithms and differential privacy-based analysis.
result Noise-addition algorithms provide variance-dependent guarantees for unbounded queries.
Algorithm adapts to shifting domains with minimal label queries.
problem Adaptive learning in online machine learning systems with domain shifts.
method Adaptive algorithm balancing regret and label queries for hidden domains.
result Achieves lower regret compared to uniform and greedy queries.
New algorithms recover clusters with minimal queries, connecting margins to recoverability.
problem Active cluster recovery with oracle queries for minimal cost.
method Introducing margin-based clustering, designing algorithms for various spaces.
result Achieve queries for general pseudometric spaces and convex clusters.
We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of query learning in terms of various combinatorial quantities. Our approach is flexible and powerful enough to enough to give new and very short proofs of the efficient learnability…
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.
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.
Quantum algorithms for multi-armed bandits are explored with limited reward access.
problem Exploring quantum speed-ups in multi-armed bandit problems with limited reward information.
method Introduced new bandit models and showed query complexity equivalence with classical algorithms.
result No quadratic speed-up is possible for multi-armed bandits with limited reward access.
Survey of statistical queries and their applications.
problem Understanding statistical queries and their applications.
method Exploration of statistical queries model, definitions, and connections to learnability.
result Connections to learnability and applications in optimization, evolvability, and differential privacy.
Quadratic memory is essential for optimal convex optimization queries.
problem Optimal query complexity for convex optimization and feasibility problems.
method Lower bounds on query complexity for convex optimization and feasibility problems.
result Center-of-mass algorithms are Pareto-optimal for both convex optimization and feasibility problems.
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.
The paper tackles machine unlearning by designing efficient algorithms for adaptive query classes.
problem Designing efficient unlearning algorithms for machine learning models.
method Formalizes the problem and gives efficient unlearning algorithms for linear and prefix-sum query classes.
result Improved guarantees for stochastic convex optimization with reduced unlearning query complexity.
Overlapping clusters are common in models of many practical data-segmentation applications. Suppose we are given elements to be clustered into possibly overlapping clusters, and an oracle that can interactively answer queries of the form "do elements and belong to the same cluster?" The goal is to recov…
We study the problem of estimating a set of linear queries with respect to some unknown distribution over a domain based on a sensitive data set of individuals under the constraint of local differential privacy. This problem subsumes a wide range of estimation tasks, e.g., distrib…
Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
problem High-dimensional hypothesis testing and information-computation gaps.
method Analysis of statistical query framework and low-degree polynomials.
result Statistical query algorithms and low-degree polynomials are almost equivalent in power under mild conditions.
Budgeted deferral framework reduces expert query costs in machine learning.
problem High cost of querying all experts in deferral algorithms.
method Introduces budgeted deferral framework for selective expert querying.
result Empirical results show substantial reduction in training costs without sacrificing accuracy.
We study the most practical problem setup for evaluating adversarial robustness of a machine learning system with limited access: the hard-label black-box attack setting for generating adversarial examples, where limited model queries are allowed and only the decision is provided to a queried data input. Several algori…
Algorithm learns diverse rankings for search engines.
problem Designing algorithms for search engines to rank diverse items.
method LDR (Learning Diverse Rankings) algorithm, efficient learning based on users' feedback.
result Algorithm achieves optimal ranking performance with regret.
Study efficient auditing of ML fairness models.
problem Scalability of auditing ML models for fairness.
method Query-based auditing algorithms for estimating demographic parity.
result Optimal deterministic and practical randomized algorithms for fairness estimation.
Fuzzy clustering with similarity queries improves efficiency and accuracy.
problem Clustering uncertain or vague datasets.
method Semi-supervised active clustering framework with oracle similarity queries.
result Polynomial-time approximation algorithm for fuzzy clustering with few similarity queries.
Proposes efficient FOBO algorithms for global maxima of expensive functions.
problem Finding global maxima of expensive-to-evaluate functions.
method Uses gradient information from Gaussian process models to identify potential query points.
result Proposed algorithms outperform state-of-the-art FOBO algorithms.
We propose a new localized inference algorithm for answering marginalization queries in large graphical models with the correlation decay property. Given a query variable and a large graphical model, we define a much smaller model in a local region around the query variable in the target model so that the marginal dist…
This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued function through a sequence of strategically selected q…
Active Coveringcs.LG
Active learning method reduces label queries for positive examples.
problem Minimizing label queries for identifying all positive examples.
method Repurposed support estimator as offline algorithm, and a simple active learning method.
result Improved excess query cost of compared to offline methods.
We propose a framework for Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to interact with a domain expert, asking whether two given instances belong to the same cluster or not. We study the query and computational complexity of clustering in this framework. We consider a setting where…
Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcs.LG
Meta-algorithm for efficient reinforcement learning from human preferences.
problem Learning from human preference comparisons in Markov decision processes.
method Randomized exploration and experimental design for batch comparison queries.
result Meta-algorithm achieves both regret and last-iterate guarantees with minimal preference queries.
Efficient algorithms recover two sparse models from a mix of linear queries.
problem Recovering two sparse models from a mix of linear queries.
method Efficient algorithms for query complexity problem.
result Improved query complexity for model recovery.
Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional privacy cost). Noisy Max is used to return the approximate maximizer amon…
This paper tackles the computational complexity of finding approximate stationary points in non-convex optimization.
problem Finding approximate stationary points in non-convex optimization problems.
method PLS-completeness, zero-order algorithms, and gradient queries.
result The query complexity of finding approximate stationary points is Θ(1/ε) for d=2.
New tool for parallel and private stochastic convex optimization reduces query complexity.
problem Parallel and private stochastic convex optimization with reduced query complexity.
method Reweighted Stochastic Query (ReSQue) estimator combined with ball oracle acceleration.
result Achieves state-of-the-art complexities for SCO in parallel and private settings.