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.
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(kn+) to O(klnk+n+) by generating variables in descending order. result Significantly reduces computation time for generating k Gumbel-Max variables. 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.
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.
Estimates proportions of LLM-generated text in mixed documents.
problem Estimating the proportion of text generated by a pre-specified LLM in mixed documents.
method Developed estimators for two observation regimes: full observation and pivotal reduction, and established sample complexity bounds.
result Full observation estimators require fewer samples than pivotal reduction estimators.
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.
The paper develops a method for inferring second opinions from experts using counterfactual inference.
problem Designing efficient decision support systems for second opinions.
method Set invariant Gumbel-Max structural causal model for multiclass classification.
result The proposed model can infer second opinions more accurately than non-causal models.
Reparameterization of variational auto-encoders with continuous random variables is an effective method for reducing the variance of their gradient estimates. In the discrete case, one can perform reparametrization using the Gumbel-Max trick, but the resulting objective relies on an argmax operation and is non-dif…
Thompson sampling has impressive empirical performance for many multi-armed bandit problems. But current algorithms for Thompson sampling only work for the case of conjugate priors since these algorithms require to infer the posterior, which is often computationally intractable when the prior is not conjugate. In this …
We introduce an off-policy evaluation procedure for highlighting episodes where applying a reinforcement learned (RL) policy is likely to have produced a substantially different outcome than the observed policy. In particular, we introduce a class of structural causal models (SCMs) for generating counterfactual traject…
Many machine learning tasks require sampling a subset of items from a collection based on a parameterized distribution. The Gumbel-softmax trick can be used to sample a single item, and allows for low-variance reparameterized gradients with respect to the parameters of the underlying distribution. However, stochastic o…
The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample k elements without replacement. We show how to implicitly apply this 'Gumbel-Top-k' trick on a factorized distribution over sequences, allowing to draw exact samples without replacement using a Stochastic Beam Sea…
Log-linear models are arguably the most successful class of graphical models for large-scale applications because of their simplicity and tractability. Learning and inference with these models require calculating the partition function, which is a major bottleneck and intractable for large state spaces. Importance Samp…
Develops methods to answer counterfactual questions in temporal point processes.
problem Lack of counterfactual analysis in temporal point process models.
method Causal model of thinning based on Gumbel-Max structural causal model, superposition theorem, and sampling algorithm.
result Simulation of counterfactual realizations provides valuable insights for targeted interventions.
New framework improves text watermark detection under imperfect pseudorandomness.
problem Structured dependence in generated text from language models causes Type I error control issues.
method Hierarchical two-layer partition, minimal units, non-asymptotic efficiency measure, minimax hypothesis testing.
result Closed-form optimal rules for watermark detection under imperfect pseudorandomness.
Develops methods for finding counterfactual explanations in sequential decision making.
problem Finding counterfactual explanations for sequential decision making processes.
method Formal characterization of sequential actions and states using Markov decision processes and Gumbel-Max structural causal model. Introduces a polynomial time algorithm based on dynamic programming.
result Algorithm finds optimal counterfactual explanations for sequential decision making.
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.
New method detects watermarks in LLM-generated text with human edits.
problem Dilution of watermark signals by human edits on LLM-generated text.
method Truncated goodness-of-fit test (Tr-GoF) for robust detection.
result Tr-GoF achieves optimality in robust detection of Gumbel-max watermark.