The Gumbel-max trick and its extensions simplify sampling from categorical distributions in machine learning.
problem Sampling from categorical distributions with unnormalized probabilities.
method Extensions of the Gumbel-max trick for various applications.
result Simplified and efficient methods for sampling and gradient estimation.
The Gumbel trick is a method to sample from a discrete probability distribution, or to estimate its normalizing partition function. The method relies on repeatedly applying a random perturbation to the distribution in a particular way, each time solving for the most likely configuration. We derive an entire family of r…
GumBolt extends Gumbel trick for Boltzmann priors in VAEs.
problem Non-differentiability of discrete units in Boltzmann machines prevents using the reparameterization trick.
method Proposes GumBolt, extending Gumbel trick to Boltzmann priors in VAEs.
result Significantly simpler than recent methods and outperforms them.
Unified framework for gradient estimation in combinatorial spaces.
problem Scaling relaxed gradient estimators to large combinatorial distributions.
method Introducing stochastic softmax tricks within the perturbation model framework.
result Stochastic softmax tricks improve model performance and discover more latent structure.
A new method samples sequences without replacement using Gumbel-Top-k trick.
problem Sampling sequences without replacement from large domains efficiently.
method Gumbel-Top-k trick applied to Stochastic Beam Search.
result Efficient sampling with linear model evaluations in k k k . A new algorithm FastGM speeds up generating Gumbel-Max variables.
problem Efficiently generating multiple Gumbel-Max variables from high-dimensional vectors.
method FastGM reduces time complexity from O ( k n + ) O(kn^+) O ( k n + ) to O ( k ln k + n + ) O(k \ln k + n^+) O ( k ln k + n + ) by generating variables in descending order. result Significantly reduces computation time for generating k k k Gumbel-Max variables. Paper proposes a new estimator for generic discrete distributions.
problem Estimating gradients for stochastic nodes in deep generative models.
method Generalized Gumbel-Softmax estimator using truncation, Gumbel-Softmax trick, and linear transformation.
result Efficacy and practical value demonstrated in synthetic examples and topic models.
Improves performance in various machine learning tasks by reparameterizing subset sampling.
problem Stochastic optimization involving subset sampling is not reparameterizable.
method Continuous relaxation of subset sampling to provide reparameterization gradients.
result Improves performance in instance-wise feature selection, deep stochastic k-nearest neighbors, and parametric t-SNE.
A new method reparameterizes Gaussian noise for better flexibility and performance.
problem Improving the Gumbel-Softmax for better flexibility and performance.
method Invertible Gaussian Reparameterization (IGR) using modified softmax and transformations.
result IGR outperforms Gumbel-Softmax in various experiments.
New method reduces variance in estimating PL model expectations.
problem High variance in Monte Carlo estimates of PL model expectations.
method Combining Gumbel top-k trick with quasi-Monte Carlo sampling.
result More sample-efficient estimators of PL model expectations.
Deep k-means learns clustering and features from unlabeled data.
problem Clustering and feature learning from unlabeled data.
method Gradient-estimator for non-differentiable k-means objective via Gumbel-Softmax reparameterisation.
result Concrete k-means model optimised for canonical k-means objective, end-to-end trainable.
Direct optimization of discrete variational auto-encoders using arg max.
problem Optimizing discrete latent variables in variational auto-encoders.
method Direct optimization through arg max without softmax relaxations.
result Empirical effectiveness of direct loss minimization in discrete latent variables.
Improved Gumbel watermark detection method.
problem Detecting Gumbel watermarking with high accuracy.
method A near-optimal model-agnostic detection mechanism.
result Demonstrates near-optimal performance under i.i.d. assumptions.
Efficient Thompson sampling for non-conjugate priors.
problem Thompson sampling's computational intractability with non-conjugate priors.
method Reformulate Thompson sampling as an optimization problem and use Gumbel-Max trick.
result Proposes an efficient algorithm for non-conjugate priors.
Improved Boltzmann exploration reduces regret in stochastic MAB problems.
problem Improving regret in stochastic multi-armed bandit problems.
method A modified Boltzmann exploration with a doubling trick.
result Achieves O ( K log 1 + α T ) O(K\log^{1+α} T) O ( K log 1 + α T ) regret, improving on previous results. This paper introduces Gumbel-Sinkhorn networks for learning latent matchings.
problem Learning in latent variable models with permutations is difficult due to combinatorial intractability.
method Approximates maximum-weight matching using the Sinkhorn operator, extending Gumbel-Softmax.
result Demonstrates effectiveness on sorting, jigsaw puzzles, and neural signal identification tasks.
Paper improves Gumbel-Softmax estimator variance reduction.
problem Challenges in gradient estimation for models with discrete latent variables.
method Rao-Blackwellization applied to straight-through Gumbel-Softmax estimator.
result Reduces mean squared error and variance of Gumbel-Softmax estimator.
Proposes a new method for estimating counterfactual treatment effects.
problem Uncertainty in identifying causal mechanisms from observational data.
method Introduces a parameterized family of causal mechanisms that generalize Gumbel-max, trained to minimize counterfactual effect variance.
result Trained mechanisms yield lower variance estimates of counterfactual treatment effects.
GSO framework optimizes COPs on graphs using Gumbel-softmax.
problem Finding optimal configurations or network structures in combinatorial optimization problems.
method Introducing Gumbel-softmax technique for direct optimization of objective functions.
result High-quality solutions obtained with less time compared to traditional methods.
Generative Adversarial Networks (GAN) have limitations when the goal is to generate sequences of discrete elements. The reason for this is that samples from a distribution on discrete objects such as the multinomial are not differentiable with respect to the distribution parameters. This problem can be avoided by using…
Categorical variables are a natural choice for representing discrete structure in the world. However, stochastic neural networks rarely use categorical latent variables due to the inability to backpropagate through samples. In this work, we present an efficient gradient estimator that replaces the non-differentiable sa…
The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem. In this work, we show how sampling from a continuous distribution can be converted into an optimization problem over continuous space. Central to the method is a stochastic process recently described in ma…
Investigates statistical properties of perturb-softmax and perturb-argmax distributions.
problem Underexplored statistical properties of Gumbel-Softmax and Gumbel-Argmax distributions.
method Investigates convexity and differentiability to determine completeness and minimality of these distributions.
result Identifies parameters that admit complete and minimal representation of probability distributions.
Differentiable NAS method optimizes network architecture and parameters efficiently.
problem Challenging to simultaneously guarantee effectiveness and efficiency in network architecture search.
method Differentiable architecture search with ensemble Gumbel-Softmax estimator.
result End-to-end mechanism for searching network architectures, discovering high-performance architectures efficiently.
Unified approach to DP problems using Gumbel distribution and variational Bayesian inference.
problem Solving classical optimal path problems in a probabilistic framework.
method Gumbel distribution and variational Bayesian inference for latent optimal paths.
result Unified approach transforms DP problems into directed acyclic graphs with Gibbs distribution.
Two new methods generate adversarial examples for discrete data.
problem Creating robust models against adversarial attacks on discrete data.
method Greedy Attack and Gumbel Attack methods.
result Character-based CNNs can be fooled by modifying only a few characters.
This article proposes a method to quantify the structure of a bipartite graph using a network entropy per link. The network entropy of a bipartite graph with random links is calculated both numerically and theoretically. As an application of the proposed method to analyze collective behavior, the affairs in which parti…
GDM models time series with smoother transitions and interpretable states.
problem Capturing smooth, variable-speed transitions and stochastic mixtures of states.
method Introduces a continuous relaxation of discrete states and a Gumbel noise model.
result Models real-world datasets more faithfully with smoother dynamics and interpretable states.
Study on estimating Gumbel--Max watermark proportions in edited documents.
problem Estimating the proportion of a document generated from a watermarked LLM.
method Comparison of full observation and pivotal reduction observation regimes; development of estimators and information-theoretic lower bounds.
result Full observation yields a substantially smaller sample complexity compared to pivotal reduction.
LLM-as-a-service prices vary arbitrarily due to tokenization multiplicity.
problem Arbitrary price variation in LLM-as-a-service due to multiple tokenizations of the same output.
method Introduce canonical generation to restrict LLMs to unique tokenizations and develop an efficient sampling algorithm.
result Our sampling algorithm for canonical generation solves tokenization multiplicity and maintains comparable performance and runtime to standard sampling.
Paper defines embolic volume and relates it to Betti number using the covering trick.
problem Relating embolic volume to topological invariants.
method Covering trick from systolic geometry applied to Berger's inequality.
result Relates embolic volume to the first Betti number.
Improved learning of probabilistic box embeddings by modeling parameters with Gumbel distributions.
problem Local identifiability issues in geometric embeddings.
method Modeling box parameters with min and max Gumbel distributions, calculating expected intersection volume.
result Improves the ability of probabilistic box embeddings to learn.
Improved CAEs reduce training time and enhance generalization.
problem Stability issues in Concrete Autoencoders (CAEs) for feature selection.
method Indirectly Parameterized Concrete Autoencoders (IP-CAEs) learn parameters of Gumbel-Softmax distributions.
result IP-CAEs achieve significant improvements in generalization and training time.
Study of skateboard flips as continuous curves in S O ( 3 ) SO(3) S O ( 3 ) group.
problem Characterize skateboard flip tricks as continuous motions.
method Model flips as curves in S O ( 3 ) SO(3) S O ( 3 ) , analyze lifts to S 3 S^3 S 3 , derive formulas. result There are only four distinct flip tricks up to continuous deformation.
A new method centers outliers in robust PCA without manual intervention.
problem Outliers in robust PCA require manual centering, complicating the analysis.
method Introduces a 'bias trick' to automatically center non-outliers.
result First optimal RPCA algorithm with automatic centering.
DDLK uses deep learning to find important features in models.
problem Discovering important features in black box models like deep neural networks.
method DDLK directly minimizes KL divergence to generate knockoffs that obey the swap property.
result DDLK outperforms baselines in discovering important features while controlling false discovery rate.
Nash's theorem proved with Günther's trick
problem Proving Nash's smooth embedding theorem
method Using Günther's trick
result Nash's theorem proved
Explains Conway's tangle trick and its mathematical origins.
problem Understanding the relationship between braids and elliptic curves.
method Discusses the tangle trick, its mathematical underpinnings, and historical context.
result Establishes the connection between braids and elliptic curves.
New framework maximizes perturbed samples for inverse classification with budget constraints.
problem Maximizing perturbed samples for desired classification outcomes under budget constraints.
method Gradient methods, stochastic processes, Lagrangian relaxations, Gumbel trick.
result Stochastic process-based algorithms outperform in different budget settings.
This paper improves MADDPG's performance in discrete grid-world scenarios.
problem MADDPG struggles with discrete action spaces in grid-world tasks.
method Integrates alternative Gumbel-Softmax estimators into MADDPG.
result One alternative estimator significantly improves performance in grid-world tasks.
Neural jump model improves option pricing accuracy.
problem Jump risk in option pricing.
method Neural jump stochastic differential equation model with Gumbel-Softmax gradient learning.
result Neural jump components significantly improve option pricing accuracy.
We prove all knots can be transformed into a trefoil using special diagrams.
problem Transforming any knot into a trefoil using magic tricks.
method Introducing knotholder diagrams to encode transformations.
result All knots can be transformed into a trefoil.
Geometric trick simplifies link homotopy and concordance.
problem Homotopy and concordance of links in homology spheres.
method Relative Whitney trick to remove double points.
result Links in homology spheres can be simplified to topologically slice links.
Tricks improve retail product image classification accuracy.
problem Retail Product Image Classification
method Various tricks including a new LCA layer, Instagram-pretrained Convnet, and Maximum Entropy loss.
result Increased accuracy of fine-tuned convnets by a large margin.
Deep learning improves community detection in graph datasets.
problem Community detection in graph datasets using deep learning.
method Proposes a deep learning approach using Gumbel Softmax for clustering graph nodes.
result The new approach significantly outperforms traditional clustering methods.
A new gradient estimator for categorical distributions reduces bias and variance.
problem Intractability of gradients for categorical distributions in discrete latent variable models.
method CatLog-Derivative trick and IndeCateR gradient estimator.
result IndeCateR reduces bias and variance of gradients for categorical distributions.
Establishes necessary and sufficient conditions for smooth triviality of Lie subalgebras and Lie ideals, and proves Moser's trick for foliations.
problem Smooth triviality of Lie subalgebras and Lie ideals
method Establishing necessary and sufficient conditions and proving Moser's trick for foliations
result Direct proof of Moser's trick for foliations
Doubling tricks help improve multi-armed bandit algorithms, but their effectiveness depends on the horizon length.
problem Improving the performance of multi-armed bandit algorithms using doubling tricks.
method Analyzed geometric and exponential doubling tricks for different horizon lengths.
result Geometric doubling tricks can conserve regret bounds in O ( T ) O(\sqrt{T}) O ( T ) , but not in O ( log T ) O(\log T) O ( log T ) . Exponential doubling tricks can conserve bounds in O ( log T ) O(\log T) O ( log T ) .