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.
Learn low-degree functions with few random queries.
problem Learning low-degree functions from limited random queries.
method Learn bounded functions f:{−1,1}no[−1,1] of degree at most d with L2-accuracy ε and confidence 1−δ from log(fracnδ)ε−d−1Cd3/2logd random queries.
result Learn low-degree functions efficiently with logarithmic number of random queries.
Causal discovery from empirical data is a fundamental problem in many scientific domains. Observational data allows for identifiability only up to Markov equivalence class. In this paper we first propose a polynomial time algorithm for learning the exact correctly-oriented structure of the transitive reduction of any c…
Improved sampling from high-dimensional Gaussians using smoothed scores.
problem Sampling from high-dimensional Gaussian distributions with gradient information.
method Using smoothed scores, which are gradients of the logarithms of Gaussian-convolved densities, to overcome approximation barriers.
result Improved sampling efficiency with a complexity of \(O\left(\left(\logκ+\log(e\sqrt d/δ_{
m TV})
ight)\log(e\sqrt d/δ_{
m TV})
ight)\) smoothed-score queries.
We study the sample complexity of private synthetic data generation over an unbounded sized class of statistical queries, and show that any class that is privately proper PAC learnable admits a private synthetic data generator (perhaps non-efficient). Previous work on synthetic data generators focused on the case that …
We study the problem of estimating a set of d linear queries with respect to some unknown distribution p over a domain 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…
Paper analyzes risk bounds for in-context learning in multiclass classification.
problem Risk bounds for in-context learning in multiclass classification.
method Formalizes tasks as sequences of labeled examples and queries, estimates conditional class probabilities, establishes oracle inequality for KL divergence.
result ICL achieves minimax optimal rate for conditional probability estimation.
In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active…
Semi-supervised active clustering (SSAC) utilizes the knowledge of a domain expert to cluster data points by interactively making pairwise "same-cluster" queries. However, it is impractical to ask human oracles to answer every pairwise query. In this paper, we study the influence of allowing "not-sure" answers from a w…
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 ℓ1 distance. In…
The study quantifies the information needed for causal queries at different levels of Pearl's hierarchy.
problem How much additional information is needed for interventional and counterfactual queries compared to observational queries?
method Formalized via query-class description length, using Kolmogorov complexity of answer oracles induced by SCMs.
result Binary acyclic SCMs show a quadratic gap between observational and interventional descriptions, and a logarithmic gap between interventional and counterfactual descriptions.
Suppose, we are given a set of n elements to be clustered into k (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "do two elements u and v belong to the same cluster?". The goal is to recover the optimum clustering by asking the minimum number of quer…
We consider the problem of optimizing a high-dimensional convex function using stochastic zeroth-order queries. Under sparsity assumptions on the gradients or function values, we present two algorithms: a successive component/feature selection algorithm and a noisy mirror descent algorithm using Lasso gradient estimate…
Online minimization of an unknown convex function over the interval [0,1] is considered under first-order stochastic bandit feedback, which returns a random realization of the gradient of the function at each query point. Without knowing the distribution of the random gradients, a learning algorithm sequentially choo…
Datasets are often reused to perform multiple statistical analyses in an adaptive way, in which each analysis may depend on the outcomes of previous analyses on the same dataset. Standard statistical guarantees do not account for these dependencies and little is known about how to provably avoid overfitting and false d…
We study online active learning for classifying streaming instances within the framework of statistical learning theory. At each time, the learner either queries the label of the current instance or predicts the label based on past seen examples. The objective is to minimize the number of queries while constraining the…
We give algorithms for estimating the expectation of a given real-valued function φ:X→R on a sample drawn randomly from some unknown distribution D over domain X, namely Ex∼D[φ(x)]. Our algorithms work in two well-studied models of restricted access to data samples. The first o…
Many machine learning models can be attacked with adversarial examples, i.e. inputs close to correctly classified examples that are classified incorrectly. However, most research on adversarial attacks to date is limited to vectorial data, in particular image data. In this contribution, we extend the field by introduci…
We design and study a Contextual Memory Tree (CMT), a learning memory controller that inserts new memories into an experience store of unbounded size. It is designed to efficiently query for memories from that store, supporting logarithmic time insertion and retrieval operations. Hence CMT can be integrated into existi…
In the era of big data, learning from categorical features with very large vocabularies (e.g., 28 million for the Criteo click prediction dataset) has become a practical challenge for machine learning researchers and practitioners. We design a highly-scalable vocabulary compression algorithm that seeks to maximize the …
We consider the problem of strongly-convex online optimization in presence of adversarial delays; in a T-iteration online game, the feedback of the player's query at time t is arbitrarily delayed by an adversary for d_t rounds and delivered before the game ends, at iteration t+d_t-1. Specifically for \algo{online-gradi…
We consider a query-based data acquisition problem for binary classification of unknown labels, which has diverse applications in communications, crowdsourcing, recommender systems and active learning. To ensure reliable recovery of unknown labels with as few number of queries as possible, we consider an effective quer…
We consider the problem of adaptively PAC-learning a probability distribution P's mode by querying an oracle for information about a sequence of i.i.d. samples X1,X2,… generated from P. We consider two different query models: (a) each query is an index i for which the oracle reveals…
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.