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,742 papers · 148 categories
Trend · papers per month
48 results for “Optimal Query Complexity”
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.
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.
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.
LAZO reduces query complexity and variance in ZO methods.
problem High query complexity and variance in zeroth-order optimization.
method LAZO uses adaptive lazy queries to reduce variance and save queries.
result LAZO achieves lower regret and query complexity compared to existing methods.
A new method for private query release using Johnson-Lindenstrauss projection.
problem Private release of query answers with minimal privacy loss.
method Random projection of query answers to a lower dimension, followed by noise addition.
result Optimal worst-case sample complexity for answering a workload of k queries.
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.
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.
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 δ.
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.
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…
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.
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…
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.
New insights into query complexity for Nash equilibrium learning.
problem Characterizing the number of queries needed to learn approximate Nash equilibria in matrix games.
method Introduced a new technique to prove lower bounds on query complexity, improving previous techniques.
result Lower bounds of order for any , where is a constant.
Lower bounds on query complexity for reconstructing private learner's training data.
problem Query complexity of reconstructing private learner's training data.
method Minimax analysis, Rényi DP, Metric DP framework.
result First known lower bounds on adversary's query complexity for various DP learners.
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 method tackles geodesically convex optimization with polynomial convergence.
problem Designing an efficient algorithm for geodesically convex optimization.
method Ellipsoid-like algorithm with polynomial query and per-query complexity.
result Achieves polynomial convergence for geodesically convex functions.
Tensor PCA problem analyzed with statistical query lower bounds.
problem Estimating the expected value of a rank-1 tensor from Gaussian samples.
method Sharp analysis of optimal sample complexity in the Statistical Query model.
result SQ algorithms with polynomial query complexity fail in the conjectured hard phase and have sub-optimal sample complexity.
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.
The paper provides an almost optimal learning and testing algorithm for sparse polynomials.
problem Learning and testing sparse multivariate polynomials efficiently.
method The paper presents an algorithm with sublinear query complexity in and almost linear in for learning and testing -sparse polynomials.
result The algorithm achieves almost optimal query complexity, making it the first of its kind.
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.
This paper explores the non-convex composition optimization in the form including inner and outer finite-sum functions with a large number of component functions. This problem arises in some important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gr…
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…
The paper addresses learner privacy in convex optimization with feedback.
problem Privacy risks from eavesdropping adversaries observing learner's queries.
method Optimally obfuscating learner's queries to make their learned optimal value hard to estimate.
result Query complexity overhead is additive in in the minimax formulation, multiplicative in in the Bayesian formulation.
New algorithm reduces dimensionality in stochastic optimization.
problem Stochastic optimization in high-dimensional problems.
method Proposes a sparsity-inducing stochastic gradient-free (SI-SGF) algorithm.
result Proves dimension-free query complexity in convex and strongly convex cases.
Optimizes reward learning design for complex tasks using nonparametric methods.
problem Challenges in specifying reward functions for complex tasks.
method Models rewards and policies as nonparametric functions in RKHSs, derives risk bounds, and optimizes query design.
result Derives non-asymptotic excess risk bounds and finite sample statistical rates for reward learning.
Improved API to achieve optimal error bound and query complexity in local planning.
problem Efficient local planning in discounted MDPs with linear approximation.
method Confident Approximate Policy Iteration (CAPI) for stationary policies, applying to local access simulators.
result Achieves optimal accuracy and query complexity bounds, improving over API.
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.
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…
Paper proposes efficient RLHF methods for LLMs using active queries.
problem Efficiently aligning LLMs with human preferences using RLHF.
method Formalizes RLHF as a dueling bandit problem, introduces APPO and ADPO algorithms.
result ADPO achieves similar performance to state-of-the-art methods with fewer queries.
New sampling algorithm for non-log-concave distributions requires many queries.
problem Sampling from non-log-concave distributions with good accuracy.
method Lower bound on query complexity and algorithm for sampling.
result Tight query complexity characterization for sampling from non-log-concave distributions.
We lower bound the complexity of finding -stationary points (with gradient norm at most ) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (i…
Memory-constrained algorithms need superlinear memory for efficient convex optimization.
problem Efficiently minimizing convex functions with limited memory.
method Analyzing first-order algorithms with superlinear memory constraints.
result Superlinear memory is necessary for optimal performance in convex optimization.
Active sampling algorithm for linear regression with various norms and improved query complexity.
problem Efficiently querying a few entries of a target vector for near optimal minimizers of linear regression.
method Lewis weight sampling and active sampling algorithms for different norms.
result Optimal query complexity for , , and .
We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constra…
A new one-point feedback scheme improves ZO algorithms for black-box optimization.
problem Optimizing black-box functions without gradient information.
method Proposes a one-point feedback scheme to estimate gradients using residuals.
result Matches query complexity of two-point schemes for deterministic Lipschitz functions.
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.
Gradient descent is efficient for solving feasibility problems with minimal memory and queries.
problem Finding a point in a given set using a memory-constrained algorithm with a separation oracle.
method Oracle complexity lower bounds for gradient descent and other algorithms.
result Gradient descent is Pareto-optimal in the oracle complexity/memory tradeoff for feasibility problems.
We study the query complexity of Bayesian Private Learning: a learner wishes to locate a random target within an interval by submitting queries, in the presence of an adversary who observes all of her queries but not the responses. How many queries are necessary and sufficient in order for the learner to accurately est…
Optimizing an expensive-to-query function is a common task in science and engineering, where it is beneficial to keep the number of queries to a minimum. A popular strategy is Bayesian optimization (BO), which leverages probabilistic models for this task. Most BO today uses Gaussian processes (GPs), or a few other surr…
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.
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.
The paper develops algorithms to restore monotonicity in non-monotone functions.
problem Non-monotone solutions from heuristic algorithms need to be corrected.
method Develops algorithms to restore monotonicity with limited queries.
result Restores monotonicity while degrading the function value by at most ε.
BMBO-DARN optimizes expensive functions with varying fidelities.
problem Optimizing expensive, multi-fidelity functions efficiently.
method Batch Multi-fidelity Bayesian Optimization with Deep Auto-Regressive Networks.
result BMBO-DARN improves surrogate learning and optimization performance.
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.
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.
Paper develops online statistical inference methods for stochastic optimization using Kiefer-Wolfowitz algorithms.
problem Online statistical inference of model parameters in stochastic optimization problems.
method Kiefer-Wolfowitz algorithm with random search directions, asymptotic distribution analysis.
result Developed valid confidence intervals for online statistical inference.