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.
Paper analyzes Greedy-GQ for reinforcement learning with Markovian noise.
This paper analyzes the sample complexity of two timescale reinforcement learning algorithms.
Sampling is a fundamental topic in graph signal processing, having found applications in estimation, clustering, and video compression. In contrast to traditional signal processing, the irregularity of the signal domain makes selecting a sampling set non-trivial and hard to analyze. Indeed, though conditions for graph …
This work improves RLHF performance guarantees using greedy sampling.
Improved Thompson Sampling for Bayesian Optimization.
New distributions allow greedy arm selection in sparse bandit problems.
LGES speeds up causal discovery while maintaining accuracy.
In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two no…
We study the problem of sampling a bandlimited graph signal in the presence of noise, where the objective is to select a node subset of prescribed cardinality that minimizes the signal reconstruction mean squared error (MSE). To that end, we formulate the task at hand as the minimization of MSE subject to binary constr…
Greedy training of recursive partitioning estimators faces a computational barrier when the true function doesn't satisfy a specific property.
AEGiS optimizes expensive function evaluations asynchronously.
We present a new method for conducting Monte Carlo inference in graphical models which combines explicit search with generalized importance sampling. The idea is to reduce the variance of importance sampling by searching for significant points in the target distribution. We prove that it is possible to introduce search…
Simpler ε-greedy with longer action durations improves exploration.
A major problem in data augmentation is to ensure that the generated new samples cover the search space. This is a challenging problem and requires exploration for data augmentation policies to ensure their effectiveness in covering the search space. In this paper, we propose Greedy AutoAugment as a highly efficient se…
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
New algorithm speeds up learning of graphical models.
Enhances PMD with lookahead to improve RL performance.
The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be sub-optimal in general. However, exploration-free greedy algorithms are desirable in practical setti…
In this paper, we address the problem of learning the structure of a pairwise graphical model from samples in a high-dimensional setting. Our first main result studies the sparsistency, or consistency in sparsity pattern recovery, properties of a forward-backward greedy algorithm as applied to general statistical model…
WiGS improves active learning for regression by dynamically selecting informative samples.
SIFT reduces training time by selecting samples with approximate losses.
Regression problems are pervasive in real-world applications. Generally a substantial amount of labeled samples are needed to build a regression model with good generalization ability. However, many times it is relatively easy to collect a large number of unlabeled samples, but time-consuming or expensive to label them…
Proposes a method to refine PDE-driven high-dimensional rare-event simulation.
Regularization-induced exploration improves contextual bandit performance.
The paper analyzes greedy algorithms for MMD minimization, showing their efficiency and approximation error.
We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requires to solve a large number of optimization problems, thus it is not scalable for large-size problems…
New technique tracks geometric properties to correct base algorithms' poor performance.
OOMP selects features online for sparse linear regression.
Recent successful deep reinforcement learning algorithms, such as Trust Region Policy Optimization (TRPO) or Proximal Policy Optimization (PPO), are fundamentally variations of conservative policy iteration (CPI). These algorithms iterate policy evaluation followed by a softened policy improvement step. As so, they are…
Novel hybrid method for Bayesian network structure learning reduces computational time without sacrificing accuracy.
We characterize the performance of sequential information guided sensing, Info-Greedy Sensing, when there is a mismatch between the true signal model and the assumed model, which may be a sample estimate. In particular, we consider a setup where the signal is low-rank Gaussian and the measurements are taken in the dire…
We study incentivized exploration for the multi-armed bandit (MAB) problem where the players receive compensation for exploring arms other than the greedy choice and may provide biased feedback on reward. We seek to understand the impact of this drifted reward feedback by analyzing the performance of three instantiatio…
Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and…
Study improves CTS's approximation regret for combinatorial bandits.
In Bayesian inference, the posterior distributions are difficult to obtain analytically for complex models such as neural networks. Variational inference usually uses a parametric distribution for approximation, from which we can easily draw samples. Recently discrete approximation by particles has attracted attention …
The paper develops a theory for speculative decoding acceptance criteria.
We propose a variable decomposition algorithm -greedy block coordinate descent (GBCD)- in order to make dense Gaussian process regression practical for large scale problems. GBCD breaks a large scale optimization into a series of small sub-problems. The challenge in variable decomposition algorithms is the identificati…
This paper develops a coreset method for GNNs that speeds up training on large graphs.
We discuss the relative merits of optimistic and randomized approaches to exploration in reinforcement learning. Optimistic approaches presented in the literature apply an optimistic boost to the value estimate at each state-action pair and select actions that are greedy with respect to the resulting optimistic value f…
Algorithm reduces support of discrete measures by integrating against functions.
Greedy algorithm achieves sublinear regret for various distributions.
Greedy algorithm optimizes consumption habits with power utility.
Optimizes state monitoring in Markovian systems with cost constraints.
This paper proposes a new algorithm for multiple sparse regression in high dimensions, where the task is to estimate the support and values of several (typically related) sparse vectors from a few noisy linear measurements. Our algorithm is a "forward-backward" greedy procedure that -- uniquely -- operates on two disti…
Compressed sensing (CS) shows that a signal having a sparse or compressible representation can be recovered from a small set of linear measurements. In classical CS theory, the sampling matrix and representation matrix are assumed to be known exactly in advance. However, uncertainties exist due to sampling distortion, …
Paper presents a deterministic method for diverse subset selection.
We propose a new yet natural algorithm for learning the graph structure of general discrete graphical models (a.k.a. Markov random fields) from samples. Our algorithm finds the neighborhood of a node by sequentially adding nodes that produce the largest reduction in empirical conditional entropy; it is greedy in the se…
This paper investigates the effectiveness of adversarial training in enhancing the robustness of Deep Q-Network (DQN) policies to state-space perturbations. We first present a formal analysis of adversarial training in DQN agents and its performance with respect to the proportion of adversarial perturbations to nominal…