The paper tackles learning smooth distance functions using query-based methods.
problem Learning smooth distance functions under query constraints.
method Global and local approaches using Mahalanobis distance functions.
result Quadratic query complexity for both additive and multiplicative approximations.
Learn low-degree functions with few random queries.
problem Learning low-degree functions from limited random queries.
method Learn bounded functions f : { − 1 , 1 } n o [ − 1 , 1 ] f:\{-1,1\}^n o[-1,1] f : { − 1 , 1 } n o [ − 1 , 1 ] of degree at most d d d with L 2 L_2 L 2 -accuracy ε \varepsilon ε and confidence 1 − δ 1-δ 1 − δ from log ( f r a c n δ ) ε − d − 1 C d 3 / 2 log d \log( frac{n}δ)\,\varepsilon^{-d-1} C^{d^{3/2}\sqrt{\log d}} log ( f r a c n δ ) ε − d − 1 C d 3/2 l o g d random queries. result Learn low-degree functions efficiently with logarithmic number of random queries.
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.
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…
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.
AdaWISH improves efficiency of discrete integration queries.
problem Efficiently solving discrete integration in high-dimensional spaces.
method Adaptive quantile queries to reduce query count.
result AdaWISH achieves the same approximation guarantee with fewer queries.
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.
CwA optimizes search performance by jointly learning a balanced database partition and a neural probing function.
problem Suboptimal search performance due to mismatched database and query distributions.
method CwA jointly learns a balanced database partition and a neural probing function to optimize search performance directly for the query distribution.
result CwA achieves up to 4.7x throughput over state-of-the-art methods at equal recall.
Designers of AI agents often iterate on the reward function in a trial-and-error process until they get the desired behavior, but this only guarantees good behavior in the training environment. We propose structuring this process as a series of queries asking the user to compare between different reward functions. Thus…
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.
Query access significantly speeds up learning Multi-Index Models under Gaussian distribution.
problem Agnostically learning Multi-Index Models (MIMs) under Gaussian distribution.
method Query access for MIMs with complexity O ( k ) p o l y ( 1 / ε ) p o l y ( d ) O(k)^{\mathrm{poly}(1/ε)} \; \mathrm{poly}(d) O ( k ) poly ( 1/ ε ) poly ( d ) under standard regularity assumptions. result Query access gives significant runtime improvements over random examples for agnostically learning MIMs.
New bounds show complex neural networks need many queries to learn.
problem Learning non-polynomial activation functions with Gaussian marginals.
method Gradient boosting procedure to amplify lower bounds on SQ dimension of neural networks.
result Statistical-query lower bounds for ReLU regression with 2 n c ε 2^{n^c} ε 2 n c ε queries. Efficiently learns reward functions with fewer queries and shorter computation times.
problem Expensive data generation and labeling in robot learning.
method Batch active preference-based learning methods using determinantal point processes (DPP) and heuristic alternatives.
result Our batch active learning algorithm requires only a few queries and computes them in a short amount of time.
A new inference network learns undirected models from data.
problem Learning undirected models with hidden variables is hard.
method Train a single stochastic inference network from data, using a cost function over queries.
result The network can perform inference tasks like an undirected model without partition function.
We use Bayesian optimization to create efficient adversarial attacks with limited queries.
problem Creating adversarial examples with limited query access.
method Bayesian optimization for query-efficient adversarial attacks.
result Our method reduces query count by up to 80% compared to state-of-the-art 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.
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…
We provide a new theoretical analysis framework to investigate online gradient descent in the dynamic environment. Comparing with the previous work, the new framework recovers the state-of-the-art dynamic regret, but does not require extra gradient queries for every iteration. Specifically, when functions are α α α stron…
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.
TensorPlan algorithm finds δ-optimal policies with poly ( H , d ) (H,d) ( H , d ) queries under linearly realizable state-value function.
problem Efficient planning in MDPs with linearly realizable state-value function.
method TensorPlan algorithm using poly ( ( d H / δ ) A ) ((dH/δ)^A) (( d H / δ ) A ) simulator queries. result First algorithm with polynomial query complexity using only linear-realizability of a single competing value function.
New framework for efficient query-based imitation learning.
problem Aligning agent policy with human expert behavior without prior knowledge.
method Adversarial reward query with successor representation.
result Significantly outperforms uncertainty-based methods in query efficiency.
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 ε.
Projective preferential Bayesian optimization learns user preferences in high dimensions.
problem Finding extrema of a black-box function in high-dimensional spaces.
method Projective preferential queries for feedback in human-interaction.
result Framework finds global minimum of high-dimensional black-box function.
This paper improves coreset size via smoothed analysis.
problem Efficiently computing small subsets that approximate query errors.
method Smoothed analysis for approximate average error over queries.
result Deterministic and randomized algorithms for smaller coresets.
Differential privacy mechanism design has traditionally been tailored for a scalar-valued query function. Although many mechanisms such as the Laplace and Gaussian mechanisms can be extended to a matrix-valued query function by adding i.i.d. noise to each element of the matrix, this method is often suboptimal as it for…
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, v ∗ v^* v ∗ , by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes…
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.
Algorithm optimizes non-convex functions using dueling comparisons.
problem Optimizing non-convex functions with limited function evaluations.
method COMP-GP-UCB algorithm, leveraging dueling-choice bandits.
result Theoretical guarantee of O ( Φ T ) O(\fracΦ{\sqrt{T}}) O ( T Φ ) on simple regret. Optimal DP mechanisms for vector queries are found to be staircase distributions.
problem Designing optimal additive mechanisms for vector-valued queries under differential privacy.
method Reduction to radially symmetric distributions and convex rearrangement theory.
result Staircase mechanisms are optimal for any norm and cost function.
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.
Sign-OPT uses fewer queries to generate adversarial examples.
problem Efficiently generating adversarial examples with limited model queries.
method Adopting zeroth order optimization with sign of gradient estimation.
result Sign-OPT requires 5X to 10X fewer queries than state-of-the-art approaches.
P-BO reduces black-box adversarial attacks by 10x with Bayesian optimization and function prior.
problem Efficiently generating adversarial examples against black-box models.
method Prior-guided Bayesian Optimization (P-BO) with a function prior initialized from a surrogate model.
result Significantly reduces the number of queries needed for adversarial attacks.
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.
This work tackles model-based RL by optimizing state-action queries to learn policies with minimal data.
problem Expensive state transitions in practical RL problems limit the use of standard RL algorithms.
method Bayesian optimal experimental design to guide selection of state-action queries.
result Data-efficient RL approach that learns optimal policies with up to 1,000x less data.
New research shows exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions.
problem Determining the minimum number of queries needed for sound planners in MDPs with linear function approximation.
method Analyzing fixed-horizon and discounted MDPs with a generative model, showing lower bounds on the number of queries required.
result Sound planners need at least exponential number of queries in both fixed-horizon and discounted settings.
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…
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. 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…
Bayesian optimization is a sample-efficient method for finding a global optimum of an expensive-to-evaluate black-box function. A global solution is found by accumulating a pair of query point and its function value, repeating these two procedures: (i) modeling a surrogate function; (ii) maximizing an acquisition funct…
BILBO optimizes bilevel problems without repeated lower-level optimizations.
problem Challenges in bilevel optimization, especially in noisy, constrained, and derivative-free settings.
method BILevel Bayesian Optimization (BILBO) that optimizes both levels simultaneously, using confidence-bounds and function query selection.
result Theoretical and empirical evidence of BILBO's effectiveness on various problems.
LITE models improve query-document relevance with learnable late interactions.
problem Improving query-document relevance with lower latency and storage.
method Proposes learnable late-interaction models (LITE) that use factorized query and document embeddings followed by a learnable scorer.
result Empirically, LITE outperforms previous late-interaction models in re-ranking tasks.
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.
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.
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.
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 L L L in the minimax formulation, multiplicative in L L L in the Bayesian formulation. The paper establishes lower bounds for learning polynomial functions on hypercube.
problem Establishing lower bounds for learning polynomial functions on the discrete hypercube.
method Using packing numbers and Fourier analysis, the paper proves lower bounds on the number of queries needed for learning.
result Proves sharp lower bounds on the number of queries required for learning polynomial functions.
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.
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 Ω ( log ( 1 K ε ) ) Ω(\log(\frac{1}{Kε})) Ω ( log ( K ε 1 )) for any ε ≤ 1 / ( c K 4 ) ε\leq 1 / (cK^4) ε ≤ 1/ ( c K 4 ) , where c c c is a constant.