Adapts large transformer model for search query intent understanding.
problem Understanding and predicting user intents from search queries.
method Adapts BERT-like architecture for search queries, accounts for query noisiness and sparseness.
result Builds a shareable deep learning model for query intent identification.
New framework selects key features for better query performance prediction.
problem Predict query performance without relevance judgments.
method Step-wise forward and backward feature selection approach.
result Model with selected features performs as well as complex models and better than non-selective models.
Although interactive learning puts the user into the loop, the learner remains mostly a black box for the user. Understanding the reasons behind queries and predictions is important when assessing how the learner works and, in turn, trust. Consequently, we propose the novel framework of explanatory interactive learning…
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.
Quriosity analyzes curiosity-driven questions from diverse sources.
problem Understanding and analyzing human curiosity-driven questions.
method Collection of 13.5K questions from various sources, development of an iterative prompt improvement framework.
result 42% of questions are causal, revealing unique linguistic properties.
CUBE explains models by balanced experiments and contrasts.
problem Post-hoc explanation of trained predictive models.
method Design-based framework using balanced low-high probes.
result Reveals dominant learned effect structure and clarifies query efficiency.
The paper bridges theory and practice in query-driven selectivity learning.
problem Insufficient theoretical understanding of query-driven selectivity learning.
method Demonstrates learnability of selectivity predictors and establishes favorable OOD generalization error bounds.
result Theoretical advances improve OOD generalization of query-driven selectivity models.
Improves text-to-SQL models by selecting the best SQL query from beam output.
problem Simplifying database query writing for natural language questions.
method Discriminative re-ranker using BERT fine-tuned classifier.
result Achieved top 4 score on Spider leaderboard.
Paper reviews deep structural causal models for answering counterfactual queries.
problem Answering counterfactual queries using observational data with known causal structures.
method Deep generative models integrated with structural causal models.
result Provides insights into the capabilities and limitations of DSCMs.
The paper explores how to learn from incomplete online social networks.
problem Learning from partially observed networks via node querying.
method Developed algorithms NOL* for sequential node querying to maximize network observability.
result It is possible to sequentially learn which nodes to query for maximal network observability.
Search-oriented conversational systems rely on information needs expressed in natural language (NL). We focus here on the understanding of NL expressions for building keyword-based queries. We propose a reinforcement-learning-driven translation model framework able to 1) learn the translation from NL expressions to que…
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.
Membership Inference Attack (MIA) determines the presence of a record in a machine learning model's training data by querying the model. Prior work has shown that the attack is feasible when the model is overfitted to its training data or when the adversary controls the training algorithm. However, when the model is no…
This work proposes a collaborative multi-head attention layer to reduce model size without sacrificing accuracy.
problem Over-parameterization in transformer models trained with large datasets.
method Proposes a collaborative multi-head attention layer that shares key/query projections.
result Reduction in model size by 4 for same accuracy and speed.
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.
Information extraction and user intention identification are central topics in modern query understanding and recommendation systems. In this paper, we propose DeepProbe, a generic information-directed interaction framework which is built around an attention-based sequence to sequence (seq2seq) recurrent neural network…
A new framework uses directed information to efficiently select context chunks.
problem Efficiently selecting relevant context chunks for query understanding.
method Directed Information γ γ γ -covering framework, formulated as a γ γ γ -cover problem, with a greedy algorithm for context selection. result The γ γ γ -covering algorithm provides clear advantages in hard-decision regimes like context compression and single-slot prompt selection. LLM4Causal democratizes causal reasoning via fine-tuned LLMs.
problem Limited capability of LLMs in causal inference and interpretation.
method Fine-tuning an open-source LLM for causal tasks, proposing datasets for instruction tuning.
result LLM4Causal delivers end-to-end solutions for causal problems and interprets results easily.
New method uses low logit rank to simplify complex language models.
problem Understanding and learning from modern language models.
method Exploiting the low logit rank structure of language models for efficient learning.
result An efficient algorithm for learning low logit rank models from queries.
Studying a softmax-attention model, we show that the learned query converges to the latent signal subspace spanned by the informative direction.
problem Understanding the theoretical principles of attention mechanisms in large-scale token collections.
method Deriving a population objective and analyzing the limiting ordinary differential equation of the learning dynamics.
result The learned query asymptotically recovers the latent signal up to the intrinsic sign ambiguity.
Sum-Product Networks (SPNs) are recently introduced deep tractable probabilistic models by which several kinds of inference queries can be answered exactly and in a tractable time. Up to now, they have been largely used as black box density estimators, assessed only by comparing their likelihood scores only. In this pa…
Paper reconstructs training data from a single gradient query.
problem Privacy threats in federated learning due to model gradients.
method Provable attack using tensor decomposition.
result Training samples can be fully reconstructed from a single gradient query.
Study shows limitations and possibilities of learning quantum circuit output distributions.
problem Learnability of output distributions of local quantum circuits.
method Investigated within two oracle models: statistical query model and direct sample access model.
result Output distributions of super-logarithmic depth Clifford circuits are not efficiently learnable in the statistical query model.
This paper uses LLMs for causal discovery with active learning and dynamic scoring to improve efficiency and fairness.
problem High computational demands and complexities of large-scale data in causal discovery.
method Metadata-based approach, BFS strategy, Active Learning, Dynamic Scoring Mechanism, LLM confidence scores.
result Significantly reduced number of queries and improved efficiency in causal graph construction.
Quantum algorithms improve perceptron learning efficiency.
problem Improving quantum algorithms for perceptron learning.
method Revisiting and correcting a flawed quantum version space perceptron algorithm, proposing quantum-enhanced cutting-plane algorithms.
result Improved complexity bounds for quantum perceptron learning.
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 ( ε κ ) O(\sqrt{εκ}) O ( ε κ ) for ε κ ≲ 1 εκ\lesssim 1 ε κ ≲ 1 , improving over prior works. New framework limits SGD for multi-index models, addressing SQ framework shortcomings.
problem Limitations of SGD for multi-index models beyond SQ framework.
method Developed a new non-SQ framework to study SGD limitations for single-index and multi-index models.
result Applies to broad settings and architectures, including neural networks.
Paper solves k-sparse parity problem with sign SGD, matching SQ lower bound.
problem Solving k-sparse parity problems efficiently.
method Sign stochastic gradient descent on neural networks.
result Matches Statistical Query lower bound for solving k-sparse parity problems.
Machine learning is being increasingly used by individuals, research institutions, and corporations. This has resulted in the surge of Machine Learning-as-a-Service (MLaaS) - cloud services that provide (a) tools and resources to learn the model, and (b) a user-friendly query interface to access the model. However, suc…
Traditional statistical analysis requires that the analysis process and data are independent. By contrast, the new field of adaptive data analysis hopes to understand and provide algorithms and accuracy guarantees for research as it is commonly performed in practice, as an iterative process of interacting repeatedly wi…
Study reduces human labeling in LLM-based classification systems.
problem Minimizing human intervention in training LLM-based classification systems.
method Active learning framework with Conservative Hull-based Classifier (CHC), Center-based Classifier (CC), and Generalized Hull-based Classifier (GHC).
result CHC achieves O ( log d T ) \mathcal{O}(\log^d T) O ( log d T ) regret and is minimax optimal for d = 1 d=1 d = 1 . GHC bridges the gap between different regimes. Zero-shot understanding of accidents from surveillance videos using vision-language models
problem Accident understanding from surveillance videos
method Three-stage pipeline with vision-language similarity, metadata-driven multi-prompt reasoning, and entropy-gated pairwise adjudicator
result Substantial improvement in harmonic-mean score over baseline
Active learning has long been a topic of study in machine learning. However, as increasingly complex and opaque models have become standard practice, the process of active learning, too, has become more opaque. There has been little investigation into interpreting what specific trends and patterns an active learning st…
GraphQ system uses GNNs to search for subgraph patterns in graphs.
problem Efficiently identifying and matching subgraph patterns in graph data.
method Graph neural networks (GNNs) for encoding graph data and NeuroAlign for node alignment.
result NeuroAlign improves node-alignment accuracy by 19-29% compared to baseline GNNs.
Solves TOD systems' query annotation problem without explicit annotations.
problem Training TOD systems without explicit KB query annotation.
method Reinforcement learning (RL) and pipelined approach for query prediction and system training.
result Improved RL agent with modifications for TOD tasks.
The paper tackles sequential mode estimation with oracle queries.
problem Adaptively PAC-learning a probability distribution's mode.
method Two query models: index queries and pair queries. Sequential algorithms for mode estimation.
result Lower bounds on optimal query complexity for both models.
Algorithm learns arbitrary ReLU neurons under Gaussian inputs.
problem Learn an arbitrary ReLU activation over Gaussian marginals.
method Statistical Query (SQ) algorithm that outputs a ReLU activation achieving O ( O P T ) + ε O(\mathrm{OPT}) + \varepsilon O ( OPT ) + ε loss. result First constant factor approximation for arbitrary bias in polynomial time.
This paper investigates differentially private analysis of distance-based outliers. The problem of outlier detection is to find a small number of instances that are apparently distant from the remaining instances. On the other hand, the objective of differential privacy is to conceal presence (or absence) of any partic…
Study exact community recovery in noisy SBM with limited queries.
problem Community recovery in noisy stochastic block models with limited queries.
method Balanced uniform querying, two-stage adaptive strategy, sublinear queries, subsampled graph.
result Adaptive querying can improve exact recovery limits in noisy SBM.
Efficiently classifies binary labels with XOR queries, even under noisy conditions.
problem Binary classification with unknown labels using XOR queries.
method Effective query type and an efficient inference algorithm for noisy conditions.
result Achieves information-theoretic limit on optimal number of queries.
Paper studies model stealing for low-rank language models.
problem Model stealing threatens proprietary models' security and data privacy.
method Theoretical study of model stealing for Hidden Markov Models (HMMs) and low-rank language models using the conditional query model.
result Efficient algorithm for learning any low-rank distribution in the conditional query model.
Proposes a new query autocompletion method that maximizes retrieval performance.
problem Users often select suboptimal queries due to unknown best retrieval performance.
method Formulates query autocompletion as ranking item rankings, uses counterfactual learning.
result Empirical results show improved query suggestions for better retrieval performance.
Aligns attention distributions for improved accuracy and robustness.
problem Improving the accuracy and robustness of neural networks using attention mechanisms.
method Alignment attention that encourages key and query distributions to match within each head.
result Alignment attention leads to better accuracy, uncertainty estimation, and robustness across various tasks.
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.
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.
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.
The paper aims to mathematically define and learn abstractions from data.
problem Defining and learning abstractions from data.
method Characterize abstractions as summaries for answering queries, define leakiness as a loss function, and generalize classical statistics.
result A mathematical theory of abstraction can be learned from data.
Query2box embeds complex queries as boxes to handle logical operations in large KGs.
problem Handling complex logical queries on large-scale incomplete knowledge graphs.
method Embed KG entities and queries into a vector space as boxes, handling conjunctions as intersections and disjunctions through Disjunctive Normal Form.
result Query2box achieves up to 25% relative improvement over state-of-the-art methods.