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.

169,042 papers · 148 categories

Trend · papers per month

count % of corpus

48 results for “linear queries”

Recovery of Sparse Signals from a Mixture of Linear Samplesstat.ML

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.

sparse signals linear regression query complexity oracle queries compressed sensing

2020-06-29abs ↗pdf ↗

Learning Linear Utility Functions From Pairwise Comparison Queriescs.LG

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.

utility functions pairwise comparisons active learning passive learning noise-free queries

2024-05-04abs ↗pdf ↗

Recovery of sparse linear classifiers from mixture of responsesstat.ML

Study on recovering sparse linear classifiers from mixed binary responses.

problem Learning a mixture of sparse linear classifiers from binary responses.

method Query-based approach to identify all sparse vectors from a set.

result Upper bounds on the number of queries required for recovery.

sparse linear classifiers mixture models query complexity 1-bit compressed sensing heterogeneous data

2020-10-22abs ↗pdf ↗

From Adaptive Query Release to Machine Unlearningcs.LG

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.

machine learning unlearning adaptive queries stochastic convex optimization linear models

2023-07-20abs ↗pdf ↗

Statistical Query Lower Bounds for List-Decodable Linear Regressioncs.DS

Statistical Query lower bound shows difficulty in list-decodable linear regression.

problem List-decodable linear regression with adversarial corruption.

method Statistical Query (SQ) lower bound analysis.

result Lower bound of

d^{\mathrm{poly}(1/α)}

for list-decodable linear regression.

Statistical Query List-decodable Linear Regression Adversarial Corruption Lower Bound

2021-06-17abs ↗pdf ↗

Linear Queries Estimation with Local Differential Privacycs.LG

We study the problem of estimating a set of $d$ linear queries with respect to some unknown distribution $\mathbf{p}$ over a domain $\mathcal{J}=[J]$ based on a sensitive data set of $n$ individuals under the constraint of local differential privacy. This problem subsumes a wide range of estimation tasks, e.g., distrib…

2018-10-05abs ↗pdf ↗

Active Online Learning with Hidden Shifting Domainscs.LG

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.

online learning domain shifts adaptive algorithms label queries regret minimization

2020-06-25abs ↗pdf ↗

The Power of Comparisons for Actively Learning Linear Classifierscs.LG

Active learning with comparisons reduces label needs for linear classifiers.

problem Learning with limited labeled data in big data.

method Active learning with comparison queries, RPU learning model.

result Active learning with comparisons requires exponentially fewer samples for linear classifiers.

active learning linear classifiers comparison queries RPU learning label efficiency

2019-07-08abs ↗pdf ↗

Not All Attributes are Created Equal:

d_{\mathcal{X}}

-Private Mechanisms for Linear Queriesstat.ML

Differential privacy provides strong privacy guarantees simultaneously enabling useful insights from sensitive datasets. However, it provides the same level of protection for all elements (individuals and attributes) in the data. There are practical scenarios where some data attributes need more/less protection than ot…

2018-06-06abs ↗pdf ↗

A necessary and sufficient stability notion for adaptive generalizationcs.LG

New stability notion ensures generalization in adaptive settings for linear queries.

problem Ensuring generalization in adaptive settings for linear queries.

method Introducing a new stability notion based on observing outputs and quantifying their effect on posterior data sample elements.

result The new stability notion is both necessary and sufficient for generalization in adaptive settings.

stability generalization adaptive linear queries posterior

2019-06-03abs ↗pdf ↗

Active Inverse Reward Designcs.LG

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…

2018-09-09abs ↗pdf ↗

Statistical-Computational Trade-offs for Density Estimationcs.DS

Lower bounds show density estimation requires linear samples or query time.

problem Statistical-computational trade-offs in density estimation.

method Lower bound analysis on data structures.

result Lower bounds demonstrate statistical-computational trade-offs for density estimation.

density estimation statistical-computational trade-offs lower bounds data structures

2024-10-30abs ↗pdf ↗

Active Linear Regression for

\ell_p

Norms and Beyondcs.LG

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

p

norms.

result Optimal query complexity for

p \in (0,1)

1<p<2

, and

2<p<\infty

active sampling linear regression Levin weight query complexity optimal bounds

2021-11-09abs ↗pdf ↗

Query Complexity of Bayesian Private Learningcs.LG

Lower bounds on queries for Bayesian private learning.

problem Estimating a target within error ε while keeping it hidden from an adversary.

method Lower bound proof using Fano's inequality and proportional-sampling estimators.

result Query complexity is on the order of

L\log(1/\varepsilon)

for accurate estimation.

Bayesian learning private learning query complexity Fano's inequality proportional sampling

2019-11-15abs ↗pdf ↗

On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncs.LG

TensorPlan algorithm finds δ-optimal policies with poly $(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

((dH/δ)^A)

simulator queries.

result First algorithm with polynomial query complexity using only linear-realizability of a single competing value function.

MDP planning query efficiency linear realizability state-value function TensorPlan algorithm

2021-02-03abs ↗pdf ↗

Oracle-Efficient Combinatorial Semi-Banditsstat.ML

Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.

problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.

method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.

result Achieved

ilde{O}(\sqrt{T})

regret with

O(\log\log T)

oracle queries for worst-case linear rewards.

semi-bandits combinatorial oracle-efficient regret logarithmic

2025-10-24abs ↗pdf ↗

Fast k-Nearest Neighbour Search via Prioritized DCIcs.LG

Most exact methods for k-nearest neighbour search suffer from the curse of dimensionality; that is, their query times exhibit exponential dependence on either the ambient or the intrinsic dimensionality. Dynamic Continuous Indexing (DCI) offers a promising way of circumventing the curse and successfully reduces the dep…

2017-03-01abs ↗pdf ↗

Efficient Point-to-Subspace Query in

\ell^1

with Application to Robust Object Instance Recognitioncs.CV

Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space, and a query point (image), efficiently determine the nearest subspace to the query in $\ell^1$ distance. In…

2012-08-02abs ↗pdf ↗

Confidence-Budget Matching for Sequential Budgeted Learningcs.LG

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.

confidence intervals reward queries regret minimization sequential decision-making budgeted learning

2021-02-05abs ↗pdf ↗

Active Learning on Attributed Graphs via Graph Cognizant Logistic Regression and Preemptive Query Generationcs.LG

Improves node classification in graphs with active learning.

problem Difficult or expensive labeling in node classification tasks.

method Graph cognizant logistic regression and preemptive query generation.

result Significant improvement over state-of-the-art approaches.

active learning attributed graphs node classification graph cognizant logistic regression preemptive query generation

2020-07-09abs ↗pdf ↗

Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscs.LG

New algorithm tackles dynamic query routing to multiple embedding models.

problem Dynamic query routing to multiple embedding models under adversarial conditions.

method Formalized as adversarial contextual linear bandit with low-rank experts, proposed HPG algorithm.

result HPG algorithm achieves linearized policy regret of

ilde{\mathcal O}(s\sqrt{M T})

embedding models contextual bandits policy regret adversarial feedback low-rank structure

2026-06-12abs ↗pdf ↗

Point Location and Active Learning: Learning Halfspaces Almost Optimallycs.CG

New algorithm learns halfspaces almost optimally with fewer queries.

problem Learning halfspaces with minimal queries.

method Randomized linear decision tree of depth O(d log |X|).

result First nearly optimal solution for active learning of halfspaces.

active learning halfspaces linear decision tree point location membership queries

2020-04-23abs ↗pdf ↗

On the Robustness of Transformers against Context Hijacking for Linear Classificationcs.CL

Transformers can be hijacked by context, but deeper models are more robust.

problem Robustness of Transformers against context hijacking for linear classification.

method Developed a theoretical analysis on the robustness of linear transformers, considering model depth, training context lengths, and number of hijacking context tokens.

result Deeper transformers are more robust to context hijacking.

Transformer Robustness Context Hijacking Linear Classification Deep Learning

2025-02-21abs ↗pdf ↗

On efficient robust regression with subquadratic samplescs.DS

Improved efficient robust regression with near-linear time and subquadratic samples.

problem Robust linear regression with unknown covariance matrix under Gaussian covariates.

method Near-linear time algorithm using subquadratic samples, complemented by SQ and polynomial lower bounds.

result Achieves prediction error

O(\sqrt{εκ})

for

εκ\lesssim 1

, improving over prior works.

robust regression Gaussian covariates near-linear time subquadratic samples prediction error

2026-05-18abs ↗pdf ↗

Almost Optimal Proper Learning and Testing Polynomialscs.LG

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

1/ε

and almost linear in

s

for learning and testing

s

-sparse polynomials.

result The algorithm achieves almost optimal query complexity, making it the first of its kind.

sparse polynomials learning algorithm testing algorithm sublinear complexity polynomial-time

2022-02-07abs ↗pdf ↗

TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functionscs.LG

TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.

problem Finding an exponential lower bound for planning in MDPs with linearly realizable value functions.

method TensorPlan and a few action lower bound approach.

result An exponentially large lower bound is shown for planning in MDPs with linearly realizable value functions.

TensorPlan Planning MDPs Linearly Realizable Exponential Lower Bound

2021-10-05abs ↗pdf ↗

Attention improves concentration when learning node embeddingscs.LG

Attention improves edge prediction in e-commerce graphs.

problem Predicting edges in graphs from node attributes in e-commerce.

method Used attention mechanism in simple feedforward networks, derived analytically tractable model AttEST.

result Attention network outperforms LSTM architectures by over 20% on F-1 score.

graph prediction attention mechanism e-commerce query embeddings low-rank matrix

2020-06-11abs ↗pdf ↗

Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscs.LG

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.

Markov Decision Processes Linear Function Approximation Exponential Lower Bounds Sound Planners Query Complexity

2020-10-03abs ↗pdf ↗

Efficient Point-to-Subspace Query in

\ell^1

: Theory and Applications in Computer Visionstat.ML

Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space and a query point (image), efficiently determine the nearest subspace to the query in $\ell^1$ distance. We …

2012-11-05abs ↗pdf ↗

Bayes-Optimal Entropy Pursuit for Active Choice-Based Preference Learningstat.ML

We analyze the problem of learning a single user's preferences in an active learning setting, sequentially and adaptively querying the user over a finite time horizon. Learning is conducted via choice-based queries, where the user selects her preferred option among a small subset of offered alternatives. These queries …

2017-02-24abs ↗pdf ↗

Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Gamescs.GT

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(\frac{1}{Kε}))

for any

ε\leq 1 / (cK^4)

, where

c

is a constant.

Nash Equilibrium Query Complexity Matrix Games Approximation Lower Bounds

2023-04-25abs ↗pdf ↗

Confident Approximate Policy Iteration for Efficient Local Planning in

q^π

-realizable MDPscs.LG

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.

Approximate Policy Iteration Local Planning Linear Approximation Markov Decision Processes Optimal Error Bound

2022-10-27abs ↗pdf ↗

Performance Metric Elicitation from Pairwise Classifier Comparisonsstat.ML

Given a binary prediction problem, which performance metric should the classifier optimize? We address this question by formalizing the problem of Metric Elicitation. The goal of metric elicitation is to discover the performance metric of a practitioner, which reflects her innate rewards (costs) for correct (incorrect)…

2018-06-05abs ↗pdf ↗

Efficient Local Planning with Linear Function Approximationcs.LG

Efficient local planning with linear approximations for agents with limited simulator access.

problem Planning with limited simulator access in reinforcement learning.

method Confident Monte Carlo Least Square Policy Iteration (Confident MC-LSPI) and Politex (Confident MC-Politex) algorithms.

result The algorithms can learn the optimal policy with local simulator access, even for linear Q-functions.

reinforcement learning local planning linear function approximation simulator access policy iteration

2021-08-12abs ↗pdf ↗

Robust and differentially private stochastic linear banditscs.LG

Paper addresses privacy and robustness in stochastic linear bandits.

problem Stochastic linear bandits with differential privacy and adversarial robustness.

method Logarithmic batch queries, arm elimination algorithm, two privacy models.

result First algorithms providing differential privacy and adversarial robustness.

stochastic linear bandits differential privacy robustness local differential privacy adversarial robustness

2023-04-23abs ↗pdf ↗

Noise-tolerant, Reliable Active Classification with Comparison Queriescs.LG

New algorithms learn from comparisons to classify data robustly to noise.

problem Learning robust classifiers from noisy data efficiently.

method Introducing comparison queries to active learning, providing noise-tolerant classifiers.

result First time and query efficient algorithms for robust learning under bounded noise.

active learning comparison queries robust classification bounded noise Tsybakov condition

2020-01-15abs ↗pdf ↗

Private Regression via Data-Dependent Sufficient Statistic Perturbationcs.LG

Paper introduces data-dependent SSP for private linear and logistic regression.

problem Private linear and logistic regression with better performance.

method Data-dependent sufficient statistic perturbation (SSP) for linear and logistic regression.

result Data-dependent SSP outperforms state-of-the-art methods for linear and logistic regression.

differential privacy private regression sufficient statistics logistic regression synthetic data

2024-05-23abs ↗pdf ↗

Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noisecs.LG

Study shows SQ hardness for multiclass linear classification with random noise.

problem Complexity of multiclass linear classification with random noise.

method Proves super-polynomial SQ lower bounds for MLC with RCN.

result Super-polynomial SQ lower bounds for MLC with RCN.

Statistical Query Multiclass Linear Classification Random Classification Noise PAC model Complexity Theory

2025-02-17abs ↗pdf ↗

Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Timecs.LG

New algorithm maximizes non-monotone adaptive submodular functions in linear time.

problem Maximizing non-monotone adaptive submodular functions subject to a cardinality constraint.

method Developed a linear-time algorithm for non-monotone adaptive submodular maximization.

result Achieved a

1/e-ε

approximation ratio with

O(nε^{-2}\log ε^{-1})

value oracle queries.

submodularity maximization greedy algorithm linear time non-monotone

2020-08-11abs ↗pdf ↗

Learning Distributions from Multiple Data Providerscs.DS

Study on learning distributions from multiple data providers with restricted samples.

problem Learning an unknown distribution from conditional samples given a fixed family of queryable sets.

method Studied a stylized model of distribution learning from restricted conditional samples, focusing on the co-occurrence graph associated with the queryable sets.

result The optimal sample complexity of PAC learning ranges from nearly linear to quadratic, depending on the structure of the queryable sets.

distribution learning conditional samples co-occurrence graph PAC learning queryable sets

2026-07-27abs ↗pdf ↗

ReSQueing Parallel and Private Stochastic Convex Optimizationmath.OC

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.

Stochastic Convex Optimization Parallel Algorithms Private Computing Reweighted Stochastic Query Ball Oracle Acceleration

2023-01-01abs ↗pdf ↗

Approximate Causal Effect Identification under Weak Confoundingstat.ML

Proposes efficient bounds for causal effect estimation under weak confounding.

problem Estimating causal effects with weakly confounded variables.

method Develops an efficient linear program to derive upper and lower bounds on causal effect under small entropy of unobserved confounders.

result Bounds are consistent and tighter for weakly confounded variables.

causal inference confounding linear programming entropy bounds

2023-06-22abs ↗pdf ↗

Cluster with Auctions for Vector Searchcs.IR

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.

vector search nearest neighbor search cluster assignment auction algorithm neural probing function

2026-07-15abs ↗pdf ↗

Flattening a Hierarchical Clustering through Active Learningcs.LG

Active learning reconstructs hierarchical tree cuts from leaf similarity.

problem Reconstructing hierarchical tree cuts from pairwise leaf similarity.

method Pairwise similarity over tree leaves; active learning; regret and query complexity bounds.

result Theoretical guarantees on statistical error and practical linear-time implementations.

active learning hierarchical clustering pairwise similarity regret bounds query complexity

2019-06-22abs ↗pdf ↗

Online Active Regressioncs.LG

Online active regression algorithms minimize label queries for efficient data regression.

problem Efficiently predict data points with minimal label queries in an online setting.

method Proposed online algorithms for active regression under ℓ_p loss, achieving (1+ε)-approximation with minimal label queries.

result Achieves (1+ε)-approximation with only ε^(-1) d log(nκ) label queries, matching offline methods in performance.

online learning active regression label queries approximation algorithms ℓ_p loss

2022-07-13abs ↗pdf ↗

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcs.DS

Study shows efficient algorithms for noiseless linear regression require quadratic sample complexity in contamination rate.

problem Efficient algorithms for noiseless linear regression under Gaussian covariates with oblivious contamination.

method Formal evidence using Statistical Query complexity.

result Any efficient Statistical Query algorithm requires VSTAT complexity at least Ω(d^(1/2)/α^2).

linear regression noiseless oblivious contamination Statistical Query VSTAT complexity

2025-10-12abs ↗pdf ↗

Embedding Logical Queries on Knowledge Graphscs.SI

Learning low-dimensional embeddings of knowledge graphs is a powerful approach used to predict unobserved or missing edges between entities. However, an open challenge in this area is developing techniques that can go beyond simple edge prediction and handle more complex logical queries, which might involve multiple un…

2018-06-05abs ↗pdf ↗

SQ Lower Bounds for Learning Mixtures of Linear Classifierscs.LG

Lower bounds show learning mixtures of linear classifiers is nearly impossible.

problem Learning mixtures of linear classifiers under Gaussian covariates.

method Statistical Query (SQ) lower bounds and new spherical designs.

result Complexity of any SQ algorithm is $ n^{\mathrm{poly}(1/Δ) \log(r)} $, where Δ is the pairwise $\ell_2$-separation.

Statistical Query Learning Mixtures Linear Classifiers Gaussian Covariates Spherical Designs

2023-10-18abs ↗pdf ↗