Improved fast rates for decision making with forward-KL regularization in contextual bandits.
problem Improving fast rates for decision making with forward-KL regularization in contextual bandits.
method Streamlined analysis of forward-KL-regularized offline CBs, exploiting the pessimism principle and convex-analytical pipeline.
result First ildeO(ε−1) upper bounds in tabular and general function approximation settings. Paper analyzes kNN estimator for KL divergence, proving its optimality.
problem Estimating KL divergence from identical samples.
method kNN estimator based on nearest neighbor distances.
result kNN method is asymptotically rate optimal for KL divergence estimation.
Cubic-regularized Newton's method (CR) is a popular algorithm that guarantees to produce a second-order stationary solution for solving nonconvex optimization problems. However, existing understandings of the convergence rate of CR are conditioned on special types of geometrical properties of the objective function. In…
SONATA algorithm converges to solutions of nonconvex smooth functions with KL property.
problem Decentralized optimization over networks with nonconvex smooth functions and convex constraints.
method Decentralized gradient-tracking algorithm SONATA under the KL property.
result SONATA converges to stationary solutions at R-linear rate for θ∈(0,1/2], sublinear rate for θ∈(1/2,1), and R-linear rate for θ=0. The paper finds the optimal wealth growth rate in betting games.
problem Optimizing wealth growth in Kelly betting games against arbitrary hypotheses.
method Analyzes the growth rate using KL divergence and proves it equals a specific limit.
result The optimal wealth growth rate is characterized and proven to be achievable.
In this paper, we study the Kurdyka-Łojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In …
New algorithm for private non-convex optimization with optimal rates.
problem Private optimization of non-convex functions under KL condition.
method Variance-reduced gradient descent and proximal point method.
result Achieves nearly optimal rates for excess empirical risk.
This paper tightens the law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
problem Developing nonasymptotic concentration bounds for empirical KL_inf with optimal constants and rates.
method Presenting a tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
result A tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
Decentralized Bayesian learning reduces KL-divergence exponentially.
problem Efficiently learning posterior distributions in a decentralized setting.
method Decentralized Langevin dynamics in a non-convex setting.
result The algorithm converges to the target posterior distribution with exponential decrease in KL-divergence and polynomial decrease in error contributions.
A new geometric concept, the dead direction, bridges singular learning theory and information geometry.
problem The gap between singular learning theory and information geometry.
method Introducing the dead direction, a unit vector along degenerating Fisher metric, and showing its KL order can be recovered.
result The KL order of the dead direction can be recovered as the decay rate of the directional Fisher curvature, providing a handle on singular geometry.
The paper studies convergence rates of Tsallis entropic regularization in optimal transport.
problem Optimal transport with regularization.
method Γ-convergence and quantization/shadow arguments.
result Derives convergence rate of Tsallis entropic regularization.
Paper characterizes optimal language model alignment methods.
problem Aligning language models to maximize reward while keeping them close to the original model.
method KL-constrained reinforcement learning and best-of-N methods.
result Optimal KL-constrained RL solution has a large deviation principle rate function.
This study provides an explicit expansion of KL divergence's gradient flow in Fisher-Rao geometry.
problem Sampling techniques struggle to traverse between modes in non-convex potential functions.
method Explicit expansion of KL divergence's gradient flow in Fisher-Rao geometry.
result The convergence rate to π is independent of the potential function.
Kurdyka-Lojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of 21 for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. I…
EM algorithm converges in KL divergence for exponential families via mirror descent.
problem Lack of understanding of EM's non-asymptotic convergence properties.
method Viewing EM as a mirror descent algorithm, showing convergence rates in KL divergence.
result KL divergence rates for EM in exponential families, invariant to parametrization.
Paper derives convergence rates for NPMLE in Hellinger distance using deep neural networks.
problem Difficulty in proving convergence of excess risk in nonparametric logistic regression.
method Unified approach for analyzing NPMLE, deriving convergence rates in Hellinger distance.
result Derives nearly optimal convergence rates for NPMLE with deep neural networks.
Flow matching KL divergence bound derived for smooth distributions.
problem Estimating smooth distributions efficiently.
method Deterministic upper bound on KL divergence derived from flow-matching loss.
result Flow matching achieves nearly minimax-optimal efficiency under TV distance.
Variational autoencoders optimize an objective that combines a reconstruction loss (the distortion) and a KL term (the rate). The rate is an upper bound on the mutual information, which is often interpreted as a regularizer that controls the degree of compression. We here examine whether inclusion of the rate also acts…
We analyze the Kozachenko--Leonenko (KL) nearest neighbor estimator for the differential entropy. We obtain the first uniform upper bound on its performance over Hölder balls on a torus without assuming any conditions on how close the density could be from zero. Accompanying a new minimax lower bound over the Hölder ba…
Paper improves MIRACLE for faster, more robust neural network compression.
problem Efficiently compressing neural networks while maintaining performance.
method Introduces Mean-KL parameterization to constrain compression cost.
result Mean-KL parameterization leads to twice as fast convergence and more robust compression.
EGMU optimizes portfolios using KL divergence, ensuring positive solutions.
problem Constructing multi-factor target-exposure portfolios efficiently and accurately.
method Convex optimization framework minimizing KL divergence, with explicit solvers.
result Established feasibility and uniqueness of strictly positive solutions under convex-hull conditions.
Improves reliability of BBVI optimization methods.
problem Reliability issues and expertise required for BBVI optimization.
method RABVI framework with automated learning rate adjustment and KL divergence estimation.
result RABVI detects inaccurate variational approximations and optimizes reliability.
New method reduces multi-armed bandit regret to near-optimal levels.
problem Improving regret bounds for KL-regularized multi-armed bandits.
method Sharp analysis of KL-UCB with peeling argument.
result First high-probability regret bound with linear dependence on K.
Langevin diffusion is a commonly used tool for sampling from a given distribution. In this work, we establish that when the target density p∗ is such that logp∗ is L smooth and m strongly convex, discrete Langevin diffusion produces a distribution p with KL(p∣∣p∗)≤ε in O~(εd) steps,…
New method solves complex constrained optimization problems.
problem Constrained nonconvex-nonconcave minimax optimization problems.
method Inexact proximal gradient method using sequential convex programming.
result Established complexity guarantees for approximate stationary points.
The paper connects tempering and entropic mirror descent for sampling.
problem Sampling from a target distribution with known unnormalized density.
method Establishes the connection between tempering SMC and entropic mirror descent, deriving convergence rates and geometric insights.
result Tempering SMC iterates correspond to entropic mirror descent on the reverse KL divergence, providing new optimization perspectives.
Study shows fast rates for inverse reinforcement learning with linear rewards.
problem Entropy-regularized min-max inverse reinforcement learning in finite-horizon MDPs.
method Structural and statistical analysis of Min-Max-IRL with pseudo-self-concordance.
result Both trajectory-level KL divergence and parameter error decay at O(n−1). 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.
Paper analyzes convergence rates of SGD for non-convex functions under various assumptions.
problem Analyzing convergence rates of SGD for non-convex functions.
method Studied convergence properties of Stochastic Gradient Descent (SGD) for invex functions under weaker and stronger hypotheses.
result Derives estimates on the rate of convergence of $J(oldsymbolθ_t)$ to its limit for functions satisfying the Polyak-Lojasiewicz (PL) condition.
Paper develops a method to compare generative models using KL divergence.
problem Lack of principled uncertainty quantification for generative models.
method Employ Kullback-Leibler divergence to measure generative model distance.
result Effective coverage rates and higher power compared to kernel-based methods.
CR-AIS improves AIS efficiency by constant rate annealing.
problem Efficiently sample from intractable distributions.
method Constant rate annealing schedule for AIS.
result CR-AIS outperforms existing Adaptive AIS methods.
Unified analysis of KL divergence using shifted composition for sampling.
problem Sampling from target distributions with KL divergence guarantees.
method Shifted composition rule applied to KL divergence, combining local error analysis and Girsanov's theorem.
result Unified KL guarantees for strongly log-concave, weakly log-concave, and log-Sobolev distributions.
New method tightens federated probe-logit distillation rates under varying bandwidths.
problem Estimating conditional distributions in federated learning with heterogeneous bandwidth constraints.
method Developed a new federated probe-logit distillation (FPLD) method with optimal allocation for varying bandwidths.
result Achieved matching lower and upper bounds for the minimax rate under heterogeneous bandwidths.
Paper improves PAC-Bayes bounds using a better-than-KL divergence.
problem Estimating the generalization error of stochastic algorithms.
method Developed new PAC-Bayes bounds with a novel divergence.
result Achieved strictly tighter bounds than the KL divergence.
Robust VB framework handles contamination using min-max median aggregation.
problem Handling contamination and outliers in datasets.
method Partition data into subsets, formulate robust optimization problem, use min-max median KL divergence.
result Min-max median formulation improves robustness and statistical rates.
Paper analyzes SVGD algorithm for non-asymptotic convergence.
problem Optimizing a set of particles to approximate a target probability distribution.
method Finite time analysis of SVGD algorithm, providing descent lemma and convergence rates.
result SVGD algorithm decreases the objective at each iteration and converges to the target distribution.
Our work improves Langevin dynamics convergence on manifolds.
problem Sampling from distributions defined on manifolds.
method Generalized Langevin dynamics to manifolds, proving KL decrease rate.
result KL divergence decreases geometrically on manifolds with log-Sobolev inequality.
KSG mutual information estimator, which is based on the distances of each sample to its k-th nearest neighbor, is widely used to estimate mutual information between two continuous random variables. Existing work has analyzed the convergence rate of this estimator for random variables whose densities are bounded away fr…
Estimating entropy and mutual information consistently is important for many machine learning applications. The Kozachenko-Leonenko (KL) estimator (Kozachenko & Leonenko, 1987) is a widely used nonparametric estimator for the entropy of multivariate continuous random variables, as well as the basis of the mutual inform…
Study shows how neural networks generalize with minimal training data.
problem Understanding how neural networks generalize with limited data.
method Mean-field analysis of KL-regularized empirical risk minimization.
result Generalization error rate is O(1/n) for large n. New bounds for Neyman-Pearson region using f-divergences.
problem Bounding the Neyman-Pearson region for hypothesis testing.
method Establishing novel lower and upper bounds using f-divergences. result Best possible lower bound for the Neyman-Pearson boundary using hockey-stick f-divergences. This paper is about index policies for minimizing (frequentist) regret in a stochastic multi-armed bandit model, inspired by a Bayesian view on the problem. Our main contribution is to prove that the Bayes-UCB algorithm, which relies on quantiles of posterior distributions, is asymptotically optimal when the reward dis…
We investigate the problem of estimating the causal effect of a treatment on individual subjects from observational data, this is a central problem in various application domains, including healthcare, social sciences, and online advertising. Within the Neyman Rubin potential outcomes model, we use the Kullback Leibler…
Paper analyzes inclusive KL inference using Wasserstein gradient flows.
problem Analyzing inclusive KL inference with mathematical tools.
method Gradient flows derived from PDE analysis.
result Unified view of existing sampling algorithms as inclusive-KL inference.
Study improves sample complexity for distinguishing continuous distributions and causal relationships.
problem Distinguishing continuous distributions and causal relationships in the presence of unobserved confounding.
method Proposed an estimator of KL divergence based on von Mises expansion for closeness testing.
result Established sample complexity guarantees for causal discovery in non-linear models with continuous variables and unobserved confounding.
TSC uses HMC and adaptive transport maps to optimize forward KL for variational inference.
problem Variational inference underestimates uncertainty when minimizing reverse KL.
method TSC uses Hamiltonian Monte Carlo and adaptive transport maps to optimize KL(p||q).
result TSC achieves competitive performance in training variational autoencoders on large-scale data.
VISA improves inference efficiency for complex models.
problem Efficient approximate inference in computationally intensive models.
method Sequential sample-average approximations within a trust region.
result VISA achieves comparable accuracy with computational savings.
Adaptive sampling for multimodal distributions converges faster than classical methods.
problem Sampling from multimodal distributions efficiently.
method Adaptive linear dynamics with adaptive diffusion coefficients and vector fields, interpreted as weighted Wasserstein gradient flows.
result Derivative-free dynamics can achieve significantly faster convergence for nonconvex potentials.