Estimates log-concave densities in graphical models using tent functions.
problem Maximum likelihood estimation of log-concave densities in undirected graphs.
method MLE as product of tent functions corresponding to maximal cliques.
result MLE can be found via convex optimization.
Study minimax risk of score estimation for log-concave distributions.
problem Minimizing risk in score estimation for log-concave distributions.
method Developed subclasses of log-concave densities and constructed a locally adaptive, multiscale estimator.
result Established minimax rates for score estimation over specific subclasses of log-concave densities.
A new sampling method using log-concave Markov chains.
problem Sampling from unnormalized densities efficiently.
method Decomposes sampling into log-concave Markov chains with noisy measurements.
result Shows remarkable capacity to 'tunnel' between modes of a distribution.
The main results are two characterisations of log-concave densities in terms of the collection of lift zonoids corresponding to a peacock. These notions are recalled and connected to arbitrage-free asset pricing in financial mathematics.
New algorithm samples neural network posteriors efficiently.
problem Challenges of sampling multimodal Bayesian posteriors for neural networks.
method Greedy Bayes method using log-concave coupling of posterior and auxiliary random variable.
result Log-concave coupling facilitates efficient sampling of neuron weights.
This work studies the location estimation problem for a mixture of two rotation invariant log-concave densities. We demonstrate that Least Squares EM, a variant of the EM algorithm, converges to the true location parameter from a randomly initialized point. We establish the explicit convergence rates and sample complex…
Algorithm samples from composite log-concave distributions using gradient evaluations and restricted Gaussian oracles.
problem Sampling from composite log-concave distributions with limited gradient evaluations.
method Proximal gradient algorithm with RGO for g g g and strong/strongly convex conditions for f f f . result Achieves ε ε ε error in total variation distance in O ~ ( κ d log 4 ( 1 / ε ) ) \widetilde{\mathcal O}(κ\sqrt d \log^4(1/ε)) O ( κ d log 4 ( 1/ ε )) iterations. Sampling from various kinds of distributions is an issue of paramount importance in statistics since it is often the key ingredient for constructing estimators, test procedures or confidence intervals. In many situations, the exact sampling from a given distribution is impossible or computationally expensive and, there…
For sampling from a log-concave density, we study implicit integrators resulting from θ θ θ -method discretization of the overdamped Langevin diffusion stochastic differential equation. Theoretical and algorithmic properties of the resulting sampling methods for θ ∈ [ 0 , 1 ] θ\in [0,1] θ ∈ [ 0 , 1 ] and a range of step sizes are established. Ou…
Gibbs sampler contracts entropy under strong log-concavity, improving mixing time.
problem Improving the mixing time of Gibbs sampler under strong log-concavity.
method Analyzing Gibbs sampler contraction under strong log-concavity, providing sharp contraction rate.
result Gibbs sampler contracts entropy linearly with condition number and independent of dimension under strong log-concavity.
CAVI converges for log-concave measures via optimal transport.
problem Finding the closest product measure to a log-concave measure via CAVI.
method Adapting coordinate descent techniques from Euclidean space to optimal transport for log-concave densities.
result Proves convergence of CAVI for log-concave densities and provides rates of convergence under additional conditions.
We consider the problem of sampling from a strongly log-concave density in R d \mathbb{R}^d R d , and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by simulating a Markov chain obtained from the discretization of an appropriate Langevin dif…
A new sampling method, RC-LMC, reduces computational cost for high-dimensional log-concave distributions.
problem High computational cost of LMC in high dimensions.
method RC-LMC updates only one coordinate at a time, adding noise.
result RC-LMC is more efficient than LMC in high dimensions, especially for skewed distributions.
MALA mixes efficiently under smoothness and isoperimetry assumptions.
problem Sampling from target densities efficiently.
method Metropolis-Adjusted Langevin algorithm (MALA) with smoothness and isoperimetry assumptions.
result MALA mixes in $O\left(\frac{(LΥ)^{\frac12}}{ψ_μ^2} \log\left(\frac{1}ε
ight)
ight)$ iterations.
Random scan CAVI converges linearly under log-concave assumptions.
problem Analyzing the convergence rate of random scan Coordinate Ascent Variational Inference (CAVI) under log-concave conditions.
method Building on previous work, we analyze the random scan version of CAVI using optimal transport geometry.
result We obtain tight linear convergence rates for the random scan version of CAVI.
BBVI converges nearly dimensionally independent for log-concave targets.
problem Efficiently optimizing variational parameters in high-dimensional spaces.
method Proved convergence rate of BBVI with reparametrization gradient for log-concave targets.
result BBVI converges with nearly independent dimension dependence for log-concave targets.
We consider the problem of sampling from a strongly log-concave density in R d \mathbb{R}^d R d , and prove an information theoretic lower bound on the number of stochastic gradient queries of the log density needed. Several popular sampling algorithms (including many Markov chain Monte Carlo methods) operate by using stochas…
New algorithms improve convergence rates for non-log-concave sampling and log-partition estimation.
problem Efficiently sampling from non-log-concave distributions and estimating their log-partition function.
method Analysis of information-based complexity, study of polynomial-time sampling algorithms.
result Optimal rates for sampling and log-partition estimation sometimes exceed those for optimization.
MALA mixes optimally in κ√d steps for log-concave sampling.
problem Sampling from log-concave distributions efficiently.
method Metropolis-Adjusted Langevin Algorithm (MALA) with warm start.
result Optimal minimax mixing time of κ√d iterations for log-concave distributions.
New privacy mechanism reduces error in query results.
problem Achieving privacy while minimizing noise in query results.
method Extended sufficient and necessary condition for ( ε , δ ) (ε, δ) ( ε , δ ) -differential privacy for symmetric and log-concave noise densities. result Significantly lower mean squared errors than Laplace and Gaussian mechanisms.
Improved convergence for non-log-concave sampling.
problem Sampling from non-log-concave distributions.
method Novel conductance analysis of SGLD with auxiliary Markov Chain.
result SGLD achieves ε-sampling error with fewer evaluations.
Improves SGM convergence bounds in W2-distance without strict assumptions.
problem Convergence bounds for SGMs in W2-distance require stringent assumptions.
method Novel framework using the OU process and PDE analysis.
result Log-concavity evolves from weak to strong over time.
A new sampling method reduces computational cost for high-dimensional log-concave distributions.
problem High computational cost of ULMC in high dimensions.
method Random Coordinate ULMC (RC-ULMC) selects a single coordinate per iteration.
result RC-ULMC is cheaper than classical ULMC, especially in highly skewed and high-dimensional problems.
Study improves sampling from complex distributions using annealed Langevin Monte Carlo.
problem Sampling from non-log-concave and multimodal distributions.
method Annealed Langevin Monte Carlo algorithm with theoretical guarantees.
result Oracle complexity of O(dβ²A²/ε⁶) for achieving ε² accuracy in Kullback-Leibler divergence.
New algorithm speeds up sampling from log-concave distributions over polytopes.
problem Sampling from log-concave distributions constrained to polytopes efficiently.
method Improved Markov chain with efficient linear solvers and randomized estimators.
result Per-step complexity is nearly optimal, with reduced arithmetic operations.
Paper tackles sampling from non-log-concave distributions using denoising diffusion.
problem Sampling from non-log-concave distributions efficiently.
method DDMC framework, Zeroth-Order Diffusion Monte Carlo (ZOD-MC) algorithm.
result ZOD-MC achieves inverse polynomial dependence on sampling accuracy, efficient for low dimensions.
In the field of optimal transport theory, an optimal map is known to be a gradient map of a potential function satisfying cost-convexity. In this paper, the Jacobian determinant of a gradient map is shown to be log-concave with respect to a convex combination of the potential functions when the underlying manifold is t…
New algorithm reduces variance in stochastic gradient estimation.
problem Optimizing the variance of stochastic gradient algorithms for non-log-concave distributions.
method Developed a Multi-index Antithetic Stochastic Gradient Algorithm (MASGA) that is independent of the distribution's structure.
result MASGA achieves performance comparable to Monte Carlo estimators with unbiased samples.
Improved privacy and efficiency in online convex optimization.
problem Differentially private online convex optimization in high dimensions.
method Improves upon Agarwal et al. [2023] by reducing dimension factors and removing smoothness requirement.
result Best known rates for ( ε , δ ) (ε, δ) ( ε , δ ) -differentially private online convex optimization in the regime of ε not being very small. Novel stability bounds for OT maps improve density estimation.
problem Estimating optimal transport maps between probability distributions.
method Developed novel stability bounds for OT maps, reducing the problem to density estimation.
result Stability bounds allow for sharper guarantees without smoothness assumptions.
New sampling method guarantees approximate first-order stationary points for non-convex functions.
problem Sampling from non-log-concave densities with non-convex potential functions.
method Averaged Langevin Monte Carlo with complexity analysis.
result Langevin Monte Carlo outputs a sample with ε-relative Fisher information after O(L²d²/ε²) iterations.
Proves log-concavity of cluster algebra coefficients for type A n A_n A n .
problem Log-concavity of cluster algebra coefficients.
method Introduced atomic theta basis and proved log-concavity for type A n A_n A n . result Proved log-concavity of coefficients for cluster algebra variables of type A n A_n A n . Optimal convex loss function improves regression coefficient estimation.
problem Asymptotic variance improvement in linear regression estimation.
method Score matching extension for log-concave projection.
result Semiparametric estimator attains minimal asymptotic covariance.
Study improves sampling from non-log-concave distributions using Fisher information.
problem Sampling from non-log-concave distributions with high Fisher information guarantees.
method Proximal sampler with RGO implementation, leveraging log-concave sampling results.
result Improved complexity guarantee in relative Fisher information for non-log-concave sampling.
New weighted surface area measures for convex bodies with applications.
problem Generalizing surface area measures to weighted Borel measures.
method Formulating and analyzing weighted surface area measures, proving integral formula and Bézout-type inequality.
result New integral formula for mixed measure of three bodies, generalizing Bézout-type inequality.
As an important Markov Chain Monte Carlo (MCMC) method, stochastic gradient Langevin dynamics (SGLD) algorithm has achieved great success in Bayesian learning and posterior sampling. However, SGLD typically suffers from slow convergence rate due to its large variance caused by the stochastic gradient. In order to allev…
Improved regret bounds for adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Truncated continuous exponential weights algorithm over the probability simplex, analyzing with linear bandit setting without contexts.
result Second-order bound of i l d e O ( K d V T ) ilde O(K\sqrt{d V_T}) i l d e O ( K d V T ) and first-order bound of i l d e O ( K d L T ∗ ) ilde O(K\sqrt{d L_T^*}) i l d e O ( K d L T ∗ ) . Establishes log-concavity estimates for convex domains' first Dirichlet eigenfunctions.
problem Quantifying the Hessian of log-concave eigenfunctions on convex domains.
method Analyzes log-concavity properties of the first Dirichlet eigenfunction on convex domains.
result Obtains quantitative estimates for the Hessian of log u \log u log u . New sampling algorithm for non-log-concave distributions requires many queries.
problem Sampling from non-log-concave distributions with good accuracy.
method Lower bound on query complexity and algorithm for sampling.
result Tight query complexity characterization for sampling from non-log-concave distributions.
New Langevin algorithms improve sampling efficiency in high dimensions.
problem Sampling from log-concave and smooth distributions in high dimensions.
method Combining splitting and accurate integration methods for P P P -th order Langevin dynamics. result LMC algorithms converge faster with better dimension dependence as P P P increases. Poisson Midpoint Method improves Langevin Dynamics for diffusion models.
problem Slow convergence of LMC in diffusion models requiring many small steps.
method Poisson Midpoint Method approximates LMC with larger steps, proving quadratic speed up.
result Poisson Midpoint Method maintains quality of DDPM with fewer calls.
A new method lifts training of input-convex neural networks to avoid dead weights and plateaued loss.
problem Training input-convex neural networks with non-negative weights.
method Introduces a hypernetwork that emits non-negative weights from a summary of the input batch, adding stochasticity to soften the loss landscape.
result The lift method achieves lower test loss than projected gradient descent and direct softplus reparametrization.
Log-concavity of eigenfunctions on curved surfaces is proven, leading to fundamental gap estimates.
problem Proving log-concavity of eigenfunctions on curved surfaces.
method Analyzing the Laplacian eigenfunctions on positively curved surfaces.
result Strong log-concavity of the first eigenfunction on positively curved surfaces.
Langevin Monte Carlo (LMC) is an iterative algorithm used to generate samples from a distribution that is known only up to a normalizing constant. The nonasymptotic dependence of its mixing time on the dimension and target accuracy is understood mainly in the setting of smooth (gradient-Lipschitz) log-densities, a seri…
Improved sampling guarantees for weakly log-concave distributions.
problem Sampling from distributions that are not strongly log-concave.
method Proximal sampler with convergence guarantees under weaker assumptions.
result New state-of-the-art sampling guarantees for various target distributions.
New findings show transfer learning is possible even when density ratios are unbounded.
problem Transfer learning under unbounded density ratios.
method Low-degree polynomial estimators, general transfer inequality over R n \mathbb{R}^n R n . result Non-trivial transfer learning possible under mild assumptions, including log-concave measures.
Log-concavity proven for multinomial likelihoods under specific constraints.
problem Log-concavity of multinomial likelihoods under interval censoring constraints.
method Proved log-concavity by showing M-convex subsets of the discrete simplex.
result Likelihood function is completely log-concave.
The Links-Gould polynomial of alternating knots is shown to be log-concave and positive.
problem Verifying the positivity and log-concavity of the Links-Gould polynomial for alternating knots.
method Formulated a conjecture and verified it computationally for all 51.3 million knots with up to 19 crossings.
result All but 544 knots satisfy a stronger log-concavity condition.