The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample elements without replacement. We show how to implicitly apply this 'Gumbel-Top-' trick on a factorized distribution over sequences, allowing to draw exact samples without replacement using a Stochastic Beam Sea…
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Deterministic Top-$r$ Sampling”
Improved SRHT for linear SVM classification with higher accuracy.
problem Inefficient random projection methods for high-dimensional data.
method Importance sampling and deterministic top- sampling for effective low-dimensional embedding.
result Higher classification accuracy on real-life datasets.
In this paper, we propose a novel progressive parameter pruning method for Convolutional Neural Network acceleration, named Structured Probabilistic Pruning (SPP), which effectively prunes weights of convolutional layers in a probabilistic manner. Unlike existing deterministic pruning approaches, where unimportant weig…
New algorithm reduces sample complexity for Top Two method.
problem Fixed-confidence best arm identification for Top Two methods.
method UCB-based Top Two algorithm for non-asymptotic analysis.
result First non-asymptotic upper bound on expected sample complexity.
Efficiently selects top-m designs for various contexts using sequential sampling.
problem Optimizing selection of top-m designs across different contexts.
method Formulated as a stochastic dynamic programming problem, developed sequential sampling policy.
result Asymptotically optimal sampling ratios for efficient selection.
Top-H decoding improves text generation by balancing creativity and coherence.
problem Balancing creativity and coherence in text generation.
method Entropy-constrained minimum divergence problem, NP-hard ECMM problem, top-H decoding.
result Top-H decoding outperforms min-p sampling by up to 25.63% on creative writing benchmarks.
In the standard models for optimal multiple stopping problems it is assumed that between two exercises there is always a time period of deterministic length , the so called refraction period. This prevents the optimal exercise times from bunching up together on top of the optimal stopping time for the one-exercise c…
We resolve the open problem of optimal sample complexity for multicalibration and deterministic predictors.
problem Optimal sample complexity for multicalibration and deterministic predictors
method Minimax-optimal multicalibration algorithm and generalization to OI predictors
result Minimax-optimal multicalibration algorithm and deterministic predictors with optimal sample complexity
We explain theoretically a curious empirical phenomenon: "Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scores results in a good low-rank matrix surrogate". To obtain provable guarantees, previous work requires randomized sampling of the columns wi…
Top Two Algorithms Revisitedstat.ML
Improved theoretical guarantees for Top Two algorithms.
problem Theoretical support for best arm identification with bounded distributions.
method General analysis of Top Two methods, identifying desirable properties and replacing sampling step.
result Theoretical support for Top Two algorithms with bounded distributions.
TyXe enables flexible Bayesian neural networks in Pytorch.
problem Uncertainty estimation in neural networks.
method Separates architecture, prior, inference, and likelihood specification; modular choices for priors, guides, and inference techniques.
result Minimal modifications to existing code for Bayesian neural networks.
We convert deterministic flow models to stochastic samplers.
problem Deterministic flow models are sensitive to errors and cannot condition on intermediate states.
method Transform ODEs into SDEs with the same marginal distributions.
result Empirically outperforms deterministic samplers and controls generation diversity.
Optimized sampling scheme for compressed sensing combining randomness and determinism.
problem Improving compressed sensing performance with deterministic sampling.
method Optimized sampling scheme combining random and deterministic selection of rows.
result Measurable improvements in image compressed sensing for generative and sparse priors.
The paper proposes methods to identify and sample from mixtures of Mallows models for top-k rankings.
problem Identifying and sampling from mixtures of Mallows models for top-k rankings in a heterogeneous population.
method Efficient sampling algorithms and identifiability proofs for both components of the mixture.
result The identifiability and learnability of the Mallows components' parameters in the mixture.
Batch norm with entropic regularization turns deterministic autoencoders into generative modelscs.LG
Batch normalization with regularization turns deterministic autoencoders into generative models.
problem Creating generative models from deterministic autoencoders.
method Using batch normalization as a source of non-determinism and adding entropic regularization.
result Deterministic autoencoders can be transformed into generative models with similar performance to variational autoencoders.
This paper uses deep reinforcement learning to optimize stock portfolios considering transaction costs and risks.
problem Optimizing stock portfolios with transaction costs and risks.
method Formulated stock portfolio optimization as a reinforcement learning problem, applied DDPG, GDPG, and PPO algorithms, and used Wavelet Transform.
result DDPG and GDPG algorithms outperformed PPO in continuous action space.
Unified analysis for deterministic samplers in diffusion models.
problem Challenges in analyzing deterministic samplers for diffusion models.
method Unified convergence analysis framework.
result Achieved polynomial iteration complexity for DDIM-type samplers.
Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete matrix is finitely rank- completable if there are at …
Reinforcement learning algorithms such as the deep deterministic policy gradient algorithm (DDPG) has been widely used in continuous control tasks. However, the model-free DDPG algorithm suffers from high sample complexity. In this paper we consider the deterministic value gradients to improve the sample efficiency of …
DeepTopPush improves accuracy at the top for complex classification tasks.
problem Minimizing irrelevant samples above a threshold in binary classification.
method Proposes a new method for end-to-end training of deep networks to minimize loss at the top.
result Demonstrates excellent performance on visual recognition and real-world applications.
Top-two algorithm improved for best-k-arm selection.
problem Best-k-arm identification in multi-armed bandits.
method Information-directed selection based on dual variables.
result Top-two Thompson sampling with IDS is asymptotically optimal.
In this paper, we analyze the fundamental conditions for low-rank tensor completion given the separation or tensor-train (TT) rank, i.e., ranks of unfoldings. We exploit the algebraic structure of the TT decomposition to obtain the deterministic necessary and sufficient conditions on the locations of the samples to ens…
We study the top- ranking problem where the goal is to recover the set of top- ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populat…
This paper explores the preference-based top- rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top- ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model…
New guarantees for matrix completion from any deterministic sampling patterns.
problem Proving guarantees for low-rank matrix completion from non-random sampling schemes.
method Introduced a graph with observed entries as edges to analyze the performance of constrained nuclear norm minimization algorithm.
result The algorithm can successfully complete the matrix if the observation graph is well-connected and has similar node degrees.
Deterministic training improves generative autoencoder performance.
problem Stochastic training limits generative autoencoder performance.
method Invertible layers for deterministic training.
result AEFs outperform VAEs in log-likelihood and sample quality.
Optimal top-2 method improves best arm identification with reduced error.
problem Identifying the arm with the highest mean in a set of arms.
method A novel top-2 algorithm that pulls the empirical best arm with probability β and the challenger arm otherwise.
result The proposed algorithm matches the information theoretic lower bound on sample complexity as δ approaches 0.
A new algorithm for sampling from complex distributions.
problem Sampling from high-dimensional multivariate probability densities.
method Combines kernel herding and Gibbs sampling for deterministic sampling.
result Significantly lower computation time compared to kernel herding.
The task of multi-step ahead prediction in language models is challenging considering the discrepancy between training and testing. At test time, a language model is required to make predictions given past predictions as input, instead of the past targets that are provided during training. This difference, known as exp…
Paper bounds PAC RL sample complexity in deterministic MDPs.
problem Identify ε-optimal policy with high probability.
method Proposes nearly matching upper and lower bounds on sample complexity, introduces deterministic return gap, uses graph-theoretical concepts and maximum-coverage exploration.
result First nearly matching upper and lower bounds on sample complexity for PAC RL in deterministic MDPs.
A framework for binary classification on top samples.
problem Binary classification problems above/below a threshold.
method General framework for ranking problems, hypothesis testing.
result Theoretical and numerical analysis of methods.
The seemingly stochastic transient dynamics of neocortical circuits observed in vivo have been hypothesized to represent a signature of ongoing stochastic inference. In vitro neurons, on the other hand, exhibit a highly deterministic response to various types of stimulation. We show that an ensemble of deterministic le…
Optimizes ranking of top-k players from partial comparison data.
problem Identifying the top-k players from incomplete pairwise comparisons.
method Maximum Likelihood Estimator (MLE) and Spectral Method.
result MLE achieves optimal partial and exact recovery, while Spectral Method is sub-optimal.
UCB algorithm's arm-sampling behavior is revealed, leading to new insights and proofs.
problem Optimizing multi-armed bandit algorithms for worst-case scenarios.
method Analysis of UCB algorithm's arm-sampling behavior and process-level characterization.
result UCB's arm-sampling rates are asymptotically deterministic, regardless of problem complexity.
Shape adaptor learns flexible resizing factors for neural networks.
problem Fixed resizing layers limit network performance.
method Learnable reshaping factor for traditional resizing layers.
result Performance increases consistently across multiple datasets.
Extends linear classification framework to nonlinear SVM-based ranking problems.
problem Maximizing performance on relevant samples in ranking problems.
method Dualization, kernel addition, componentwise dual ascent method.
result General framework for nonlinear classifiers in ranking problems.
How Does Attention Help? Insights from Random Matrices on Signal Recovery from Sequence Modelsstat.ML
Study reveals how attention helps in signal recovery from sequence models using random matrix theory.
problem Signal recovery from sequence models with attention mechanisms.
method Analysis of sample covariance matrices constructed from pooled sequence representations with attention weights.
result Optimal attention weights maximize signal-to-noise ratio and improve signal recovery.
New error bounds for flow matching methods using deterministic sampling.
problem Improving the accuracy of flow matching methods for generating probability distributions.
method Derived error bounds for flow matching methods under deterministic sampling conditions.
result Presented error bounds for flow matching methods using loss and regularity conditions.
Develops a new method to recover large latent tree models efficiently.
problem Inference of large latent tree structures from terminal node observations.
method Spectral Top-Down Recovery (STDR) using Fiedler vector partitioning.
result Proves statistical consistency and sample complexity for accurate tree recovery.
Study extends bounds on sample covariance matrices with general dependence.
problem Quantitative bounds on sample covariance matrices with i.i.d. columns.
method Extends previous work on deterministic equivalent to rectangular random matrices with general dependence structure.
result Proves quantitative bounds involving dimensions and spectral parameter, including closer proximity to real positive semi-line.
The paper develops a theory for speculative decoding acceptance criteria.
problem Speculative decoding's acceptance criteria and their rejection regions.
method Characterization of rejection regions as lower level sets of the target distribution, derivation of exact and margin-based certificates.
result Relaxed and tree-based acceptance criteria substantially enlarge the region of certified acceptance.
Optimizes identifying top-k items from comparisons with minimal comparisons.
problem Finding the top-k items from pairwise comparisons with a fixed error rate.
method Developed an asymptotically optimal algorithm using primal-dual procedure and adaptive comparison allocation.
result Proves the algorithm is asymptotically optimal for top-k identification.
We present online boosting algorithms for multilabel ranking with top-k feedback, where the learner only receives information about the top k items from the ranking it provides. We propose a novel surrogate loss function and unbiased estimator, allowing weak learners to update themselves with limited information. Using…
Minimalistic unsupervised learning with sparse manifold transform achieves SOTA performance.
problem Achieving state-of-the-art unsupervised learning performance without complex engineering.
method Sparse manifold transform, leveraging sparse coding, manifold learning, and slow feature analysis.
result 99.3% KNN top-1 accuracy on MNIST, 81.1% on CIFAR-10, and 53.2% on CIFAR-100.
Recurrent models can produce infinite sequences, causing bias; new methods prevent this.
problem Inconsistency in decoding infinite-length sequences from recurrent language models.
method Defined and proved inconsistency of common decoding algorithms; proposed remedies.
result Proposed methods prevent inconsistency in practice.
Ever since the proof of asymptotic normality of maximum likelihood estimator by Cramer (1946), it has been understood that a basic technique of the Taylor series expansion suffices for asymptotics of -estimators with smooth/differentiable loss function. Although the Taylor series expansion is a purely deterministic …
Variational Autoencoders (VAEs) provide a theoretically-backed and popular framework for deep generative models. However, learning a VAE from data poses still unanswered theoretical questions and considerable practical challenges. In this work, we propose an alternative framework for generative modeling that is simpler…
Electrostatics method samples complex distributions deterministically.
problem Sampling and inference of complex, high-dimensional distributions.
method Electrostatics-based particle system with Newton mechanics principles.
result Method achieves comparable performance to other methods in benchmark tasks.