Paper proposes efficient algorithm for learning causal Bayesian networks using path queries.
problem Learning the exact structure of causal Bayesian networks from observational data.
method Polynomial time algorithm using interventional path queries to identify directed paths.
result Logarithmic sample complexity for learning transitive reduction of causal Bayesian networks.
New training method improves accuracy of path queries on knowledge graphs.
problem Path queries on knowledge graphs are disrupted by missing facts.
method Recursive application of vector space embeddings with a new training objective.
result Compositional training dramatically improves accuracy of path queries.
LSDAT reduces query efficiency for decision-based adversarial attacks.
problem Improving query efficiency for decision-based adversarial attacks.
method Low-rank and sparse decomposition (LSD) to craft perturbations.
result LSDAT achieves superior fooling rates with fewer queries.
Tree-Query uses LLMs to discover causal relationships in a transparent, interpretable manner.
problem Error propagation in classical causal discovery methods and opaque, confidence-free behavior of recent LLM-based causal oracles.
method Tree-Query is a tree-structured, multi-expert LLM framework that reduces causal discovery to queries about backdoor paths and dependencies.
result Tree-Query provides interpretable judgments with robustness-aware confidence scores and improves structural metrics over LLM baselines.
Proposes CGA model for logical queries over KGs.
problem Handling logical queries over incomplete KGs with unequal query path contributions.
method Multi-head graph attention with initial neighborhood aggregation for center node prediction.
result CGA model outperforms baselines on DB18, WikiGeo19, and Bio datasets.
BOSH improves decision-based attacks by optimizing solution paths.
problem Generating optimal adversarial examples for decision-based attacks.
method BOSH-attack uses Bayesian Optimization and Successive Halving to explore solution paths.
result BOSH converges to better solutions with fewer queries.
Paper analyzes regret bounds for unconstrained online optimization.
problem Minimizing regret in dynamic online learning for strongly convex and smooth functions.
method Preconditioned OGD, Online Optimistic Newton (OON), multiple gradient queries.
result Achieves O ( C 2 , T ∗ ) O(C^*_{2,T}) O ( C 2 , T ∗ ) regret bound with one gradient query per round. Develops a new causal model for path-dependent link prediction.
problem Existing causal models assume fixed node factors, but real-world links can depend on existing ones.
method Introduces causal lifting and structural pairwise embeddings for path-dependent link prediction.
result Validated on three scenarios, demonstrating improved accuracy for causal link prediction.
S2 is a graph-based active learning algorithm for binary label prediction with theoretical guarantees.
problem Binary label prediction on graphs with theoretical guarantees.
method S2 selects vertices to label based on shortest shortest paths between oppositely labeled vertices.
result S2 achieves near minimax optimal excess risk for nonparametric classification problems.
A new network learns to prioritize messages for efficient multi-robot path planning.
problem Efficient path planning and coordination for large-scale multi-robot systems.
method Message-Aware Graph Attention Network (MAGAT) incorporating attention mechanisms.
result MAGAT achieves performance close to a coupled centralized expert algorithm.
Proposes a neural network model for embedding knowledge bases and answering questions.
problem Handling uncertainty and conjunction in neural question answering.
method Gaussian attention model for neural memory access and scoring function.
result Demonstrates model's effectiveness on soccer player dataset for path and conjunctive queries.
Optimal experiments tighten causal effect bounds efficiently.
problem Selecting experiments to tighten causal effect bounds from observational data.
method Formalized as max-potency problem, NP-hard. Polynomial-programming framework with graphical pruning criteria.
result Pruning criteria reduce search space significantly, enabling efficient experiment selection.
Bayesian Algorithm Execution uses mutual information to infer properties of black-box functions efficiently.
problem Estimating computable properties of expensive black-box functions with limited evaluations.
method Sequentially choosing queries that maximize mutual information with respect to the algorithm's output.
result InfoBAX reduces query counts by up to 500 times compared to the original algorithm.
Transformer models outperform recurrent ones in modeling hierarchical data.
problem Modeling hierarchical structure in data.
method Introducing Multiresolution Transformer Networks leveraging self-attention.
result Multiresolution Transformer Networks significantly outperform state-of-the-art models on query suggestion datasets.
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.
The paper optimizes querying schemes for crowdsourced classification using XOR queries.
problem Optimizing querying schemes for crowdsourced classification.
method Modeling crowdsourced labeling/classification as source coding problem, leveraging connections to channel coding.
result Provides querying schemes with almost optimal number of queries, each involving a constant number of labels.
Improved query complexity for adaptive learning of decision trees.
problem Learning decision trees of depth at most d from membership queries.
method Randomized and deterministic polynomial time algorithms with improved query complexity.
result Queries reduced for both randomized and deterministic algorithms.
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.
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.
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.
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.
A new hypergraph-based active learning scheme reduces query complexity.
problem Efficiently querying and learning from complex hypergraph structures.
method Developed a novel hypergraph-based active learning scheme H S 2 HS^2 H S 2 that can handle both pointwise and pairwise queries. result Demonstrated that H S 2 HS^2 H S 2 requires significantly fewer queries than a previously used graph-based method S 2 S^2 S 2 . Study efficient black-box attacks on classifiers with limited queries.
problem Attacking machine learning classifiers with query constraints.
method Bayesian optimization to minimize query count.
result Number of queries can be reduced to about 1/10th of random strategy.
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.
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.
Study modular concept learning with different oracle interfaces.
problem Learning a concept that is a cross product of component concepts.
method Analyze different types of oracle interfaces and queries.
result Modular concept learning is easier with positive examples and membership queries.
Survey of statistical queries and their applications.
problem Understanding statistical queries and their applications.
method Exploration of statistical queries model, definitions, and connections to learnability.
result Connections to learnability and applications in optimization, evolvability, and differential privacy.
New bounds on query learning complexity for various concept classes.
problem Learning complexity in query learning models.
method Introducing new combinatorial quantities and proving lower and upper bounds.
result New and shorter proofs of efficient learnability for prominent examples.
Paper shows semi-supervised clustering is equivalent to a type of source coding.
problem Multiclass labeling of unlabeled elements with noisy binary queries.
method Locally encodable source coding approach, using pairwise queries.
result Lower bounds on the number of queries required for correct labeling.
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 / ε ) L\log(1/\varepsilon) L log ( 1/ ε ) for accurate estimation. A new query embedding method improves KB performance on complex queries.
problem QE systems disagree with deductive reasoning on some queries.
method A novel QE method more faithful to deductive reasoning.
result Better performance on complex queries to incomplete KBs.
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.
New algorithms reduce query and round complexity for learning graphs with edge-detecting queries.
problem Learning a general graph using edge-detecting queries with reduced complexity.
method Two new algorithms: one for unknown m m m (O(1) rounds, O ( m log n + m log 2 n ) O(m\log n+\sqrt{m}\log^2 n) O ( m log n + m log 2 n ) queries) and another for O ( m log n ) O(m\log n) O ( m log n ) queries (O(log* n) rounds). For known m m m , two Monte Carlo algorithms with O ( m 4 / 3 log n ) O(m^{4/3}\log n) O ( m 4/3 log n ) and O ( m log n ) O(m\log n) O ( m log n ) queries, and a 3 3 3 -round Monte Carlo algorithm with O ( m log n ) O(m\log n) O ( m log n ) queries. result Reduced query and round complexity for graph learning.
Fairly allocate items with noisy queries, reducing envy.
problem Fairly allocate indivisible goods with unknown valuations.
method Use Gaussian noisy queries to find an envy-free allocation.
result The optimal number of queries scales as \( \frac{m^{2.5}}{Δ^2} \) for large negative-envy.
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…
Sequence learning improves query expansion in information retrieval.
problem Improving query expansion in information retrieval systems.
method Used sequence to sequence algorithms to extract keywords from sentence embeddings and trained a neural network on open datasets.
result Sequence to sequence models can capture complex query expansion relations in word embeddings.
A new method uses LLMs to discover causal pathways that affect fairness in machine learning.
problem Discovering fairness-relevant causal pathways in the presence of noise and confounding.
method Hybrid LLM-guided causal discovery framework combining active learning and dynamic scoring.
result LLM-guided methods, including the proposed active, dynamically scored variant, outperform baselines in recovering fairness-relevant structure under noisy conditions.
Framework detects suspicious money laundering flows in large transaction graphs.
problem Detecting money laundering in large, complex transaction networks.
method Adapted framework for domain-specific constraints, including weighting method for edge significance.
result Framework outperforms state-of-the-art solutions in efficiency and effectiveness for large datasets.
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.
New algorithms for estimating linear queries with local differential privacy.
problem Estimating linear queries under local differential privacy constraints.
method Developed new offline and adaptive algorithms for linear queries estimation.
result Achieved optimal L 2 L_2 L 2 and L ∞ L_{\infty} L ∞ error bounds for linear queries estimation. Efficiently tests two distributions with few label queries.
problem Two-sample test with limited label information.
method Three-stage framework: classifier training, bimodal query, FR test.
result Significantly reduces Type II error compared to uniform querying.
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.
This work sets lower bounds on the number of score queries needed for diffusion sampling.
problem Establishing information-theoretic limits on the number of score evaluations required for diffusion sampling.
method Proving lower bounds on the number of adaptive score queries needed for sampling.
result Any sampling algorithm requires at least \(\widetilde{\Omega}(\sqrt{d})\) adaptive score queries for \(d\)-dimensional distributions.
Most content-based image retrieval systems consider either one single query, or multiple queries that include the same object or represent the same semantic information. In this paper we consider the content-based image retrieval problem for multiple query images corresponding to different image semantics. We propose a…