We study the query complexity of a learner-private sequential learning problem, motivated by the privacy and security concerns due to eavesdropping that arise in practical applications such as pricing and Federated Learning. A learner tries to estimate an unknown scalar value, by sequentially querying an external datab…
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 “sequential queries”
We formulate a private learning model to study an intrinsic tradeoff between privacy and query complexity in sequential learning. Our model involves a learner who aims to determine a scalar value, , by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes…
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.
New insights on active sequential prediction for mean estimation.
problem Active sequential prediction-powered mean estimation problem.
method Combining uncertainty-based suggestion with a constant probability, analyzing non-asymptotic bounds, and using no-regret learning.
result The optimal query probability is close to the constraint when using no-regret learning.
Efficient methods for answering complex probabilistic queries in sequential data.
problem Complex probabilistic queries in sequential data.
method Broad class of novel approximation techniques for marginalization in sequential models.
result Efficient techniques for answering long-range probabilistic queries.
Study efficient sequential evaluation of large language models using historical data.
problem Sequentially evaluate a new large language model (LLM) on a fixed question set.
method Construct a confidence sequence (CS) and design active querying rules to shrink CS width.
result Simple uniform sampling can sometimes outperform adaptive querying rules.
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…
Study approximates unknown function levels with queries.
problem Approximating unknown function levels through sequential queries.
method Introduce Bisect and Approximate algorithms to reduce to local function approximation.
result Rate-optimal sample complexity guarantees for H{ö}lder functions.
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.
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.
Adaptive querying learns user psychometrics with AI personas.
problem Learning user psychometrics within query budgets.
method Persona-induced latent variable model with AI personas and large language model response distributions.
result Persona-based posteriors deliver accurate probabilistic predictions.
Optimizes functions on manifolds using Gaussian processes and graph models.
problem Optimizing functions on unknown manifolds with limited data.
method Graph Gaussian process surrogate model for sequential optimization.
result Established regret bounds for the proposed algorithm.
A new method for making interpretable predictions by sequentially asking questions, faster and more efficient.
problem Developing interpretable machine learning models for complex tasks.
method Variational Information Pursuit (V-IP) that bypasses the need for learning generative models.
result V-IP is 10-100x faster and finds shorter query chains compared to IP and reinforcement learning.
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.
C-IP improves LLMs' query selection for interactive tasks by estimating uncertainty robustly.
problem Minimizing the number of queries for interactive LLMs.
method Conformal Information Pursuit (C-IP) using conformal prediction sets.
result C-IP achieves better predictive performance and shorter query-answer chains.
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. …
Studies of networked phenomena, such as interactions in online social media, often rely on incomplete data, either because these phenomena are partially observed, or because the data is too large or expensive to acquire all at once. Analysis of incomplete data leads to skewed or misleading results. In this paper, we in…
Efficient exploration improves large language model performance with fewer queries.
problem Improving large language model performance with fewer human feedback queries.
method Sequentially generates queries, fits a reward model to feedback, uses double Thompson sampling with epistemic neural network uncertainty.
result Efficient exploration enables high performance with far fewer queries.
Adaptive truncation improves privacy in online Bayesian estimation.
problem Ensuring privacy in online Bayesian estimation of a static parameter.
method Sequential Monte Carlo, adaptive truncation, Thompson sampling.
result Adaptive truncation reduces privacy-preserving noise, enabling more accurate estimation.
New method reduces regret in budgeted learning problems.
problem Decision-making with limited reward queries.
method Confidence-Budget Matching (CBM) principle.
result CBM-based algorithms perform well in adversarial settings.
Two novel search strategies reduce complexity for target localization with size-dependent noise.
problem Target localization with varying measurement noise based on query region size.
method Proposes and strategies with low complexity and connected query geometry.
result Unified analysis shows asymptotically optimal in search time, near-optimal in rate.
Active search (AS) on graphs focuses on collecting certain labeled nodes (targets) given global knowledge of the network topology and its edge weights under a query budget. However, in most networks, nodes, topology and edge weights are all initially unknown. We introduce selective harvesting, a variant of AS where the…
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.
GO-CBED optimizes experiments for specific causal queries, improving efficiency.
problem Efficiently infer causal relationships with limited resources.
method Goal-oriented Bayesian framework that maximizes expected information gain on user-specified causal quantities.
result GO-CBED outperforms existing methods in various causal tasks, especially with limited budgets.
Prediction in a small-sized sample with a large number of covariates, the "small n, large p" problem, is challenging. This setting is encountered in multiple applications, such as precision medicine, where obtaining additional samples can be extremely costly or even impossible, and extensive research effort has recentl…
DP-SPRT improves privacy in sequential tests with near-optimal error rates.
problem Privacy constraints in sequential probability ratio tests.
method A wrapper for SPRT that uses a private mechanism to determine when to stop based on predefined intervals.
result DP-SPRT achieves near-optimal error rates and privacy guarantees.
We study the power of interactivity in local differential privacy. First, we focus on the difference between fully interactive and sequentially interactive protocols. Sequentially interactive protocols may query users adaptively in sequence, but they cannot return to previously queried users. The vast majority of exist…
This study examines how sequential correlations affect in-context learning in sequence models.
problem Understanding how in-context learning works with sequentially correlated data.
method Extended linear regression model to sequentially correlated data, tested on transformer architectures.
result Sequential correlations alter the effective context length and attention architecture effectiveness.
We consider the problem of prediction by a machine learning algorithm, called learner, within an adversarial learning setting. The learner's task is to correctly predict the class of data passed to it as a query. However, along with queries containing clean data, the learner could also receive malicious or adversarial …
Paper proposes a 1-bit mean estimation method with near-optimal sample complexity.
problem Distributed mean estimation with 1-bit communication constraints.
method Randomized and sequentially-chosen interval queries to estimate mean.
result Sample complexity bound matches minimax lower bound with logarithmic factors.
Solving sequential decision prediction problems, including those in imitation learning settings, requires mitigating the problem of covariate shift. The standard approach, DAgger, relies on capturing expert behaviour in all states that the agent reaches. In real-world settings, querying an expert is costly. We propose …
Paper introduces efficient methods for probabilistic querying of event sequences.
problem Hard queries about future events in continuous-time sequences.
method Importance sampling framework for addressing query types.
result Method is more efficient than naive simulation, often 1,000 times.
Marich: A Query-efficient Distributionally Equivalent Model Extraction Attack using Public Datacs.LG
Marich extracts high-fidelity models from public data with minimal queries.
problem Creating an accurate replica of a target ML model using few queries.
method Sequentially selects informative queries to maximize entropy and reduce model mismatch.
result Extracted models achieve 60-95% of target model's accuracy with 1,000-8,500 queries.
Paper develops an efficient mean estimator for 1-bit communication constraints.
problem Mean estimation under 1-bit communication constraints.
method Adaptive mean estimator based on randomized threshold queries.
result Order-optimal sample complexity in various tail regimes.
This paper proposes an active metric learning method for clustering with pairwise constraints.
problem Clustering with pairwise constraints and improving clustering performance.
method Active metric learning method that queries informative instance pairs and updates the learned metric sequentially.
result The proposed method enhances clustering performance and provides a tighter error bound.
Online minimization of an unknown convex function over the interval is considered under first-order stochastic bandit feedback, which returns a random realization of the gradient of the function at each query point. Without knowing the distribution of the random gradients, a learning algorithm sequentially choo…
Machine teaching addresses the problem of finding the best training data that can guide a learning algorithm to a target model with minimal effort. In conventional settings, a teacher provides data that are consistent with the true data distribution. However, for sequential learners which actively choose their queries,…
We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We show that the widely used bisection approach is Info-Greedy for a family of -sparse signals b…
We study the sample complexity of private synthetic data generation over an unbounded sized class of statistical queries, and show that any class that is privately proper PAC learnable admits a private synthetic data generator (perhaps non-efficient). Previous work on synthetic data generators focused on the case that …
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.
Standard acquisition functions are sufficient for asynchronous Bayesian optimization.
problem Redundant and repeated queries in asynchronous Bayesian optimization.
method Conceptual analysis and theoretical guarantees of standard acquisitions.
result Standard acquisition functions achieve theoretical guarantees equivalent to Thompson sampling in asynchronous settings.
Proposes an online model for LLM cascading with adaptive API selection.
problem Adaptive querying and selection of LLM APIs in a context-dependent environment.
method Develops a learning approach combining GMM estimation and UCB-style bounds.
result Achieves cumulative regret of over periods.
ABCI infers causal models and queries simultaneously using Bayesian active learning.
problem Inference of causal models and effects in a two-stage process is inefficient and unnatural.
method Active Bayesian Causal Inference (ABCI) using Gaussian processes for sequentially designing experiments.
result ABCI is more data-efficient and accurate in learning causal queries from fewer samples.
In many high-throughput experimental design settings, such as those common in biochemical engineering, batched queries are more cost effective than one-by-one sequential queries. Furthermore, it is often not possible to directly choose items to query. Instead, the experimenter specifies a set of constraints that genera…
No-regret optimization for time-varying functions using uncertainty injection.
problem Optimizing time-varying functions with no-regret in bandit feedback.
method W-SparQ-GP-UCB, incorporating uncertainty injection and additional queries.
result Achieves no-regret with a vanishing number of additional queries per iteration.
DMLE improves active learning by correcting MLE for sample dependencies.
problem Dependencies among samples in active learning affect model parameter estimation.
method Dependency-aware Maximum Likelihood Estimation (DMLE).
result DMLE achieves superior performance across multiple benchmark datasets.
This paper improves active learning by using robust divergences for committee disagreement.
problem Active learning with high measurement costs.
method Query by committee with Bregman divergence (including Kullback-Leibler divergence as a special case).
result The proposed method is more robust and performs as well as or better than conventional methods.
Neural Processes combine the strengths of neural networks and Gaussian processes to achieve both flexible learning and fast prediction in stochastic processes. However, a large class of problems comprises underlying temporal dependency structures in a sequence of stochastic processes that Neural Processes (NP) do not e…