Statistical Computation · Cross-listed from cs.DS
On two proofs of $d^2$ mixing of weighted Dikin walks
Yuansi Chen and Yunbum Kook
We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, $\bar{\nu}$-
symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis–Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to the Lee–Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling from truncated PSD cones. Our second result establishes stronger $\chi^2$-divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably scaled Lee–Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $\chi^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.
Read the full abstract ▾
Machine Learning (Statistics)
Learning between the peaks: sharp asymptotics for kernel ridge regression under power-law anisotropy
Lorenzo Rizzi, Arie Wortsman Zurich and Bruno Loureiro
We study kernel ridge regression under anisotropic Gaussian data, where the input covariance decays as a power law with exponent $\alpha\geq 0$ for
polynomial inner-product kernels. We derive asymptotically sharp expressions for the kernel spectrum and the generalization error in the
polynomial high-dimensional regime $n=\Theta(d^\kappa)$, revealing how anisotropy reshapes the learning curves. For weak anisotropy ($0<\alpha<1$), the problem remains effectively high-dimensional and retains some features of the isotropic case, while departing from it in others: the variance still peaks at integer sample complexities $\kappa\in\mathbb{N}$, but these peaks are progressively damped as $\alpha$ grows; meanwhile, for targets strongly aligned with the data's principal directions, the bias drops at fractional sample complexities, decoupling the bias transitions from the interpolation peaks. For strong anisotropy ($\alpha > 1$), the effective dimension of the problem is constant, and the variance stops depending on sample size altogether, plateauing under ridgeless interpolation or vanishing at an explicit rate under fixed ridge penalty. The bias undergoes a sharp transition governed by the target's decay rate: below a threshold, learning is abrupt rather than gradual; above it, the bias decays as a power law that recovers the classical source and capacity rates. We finally specialize these results to single-index targets, showing how the
alignment of the index with the data's principal directions determines the effect of anisotropy on learning. Together, our results clarify how the input geometry shapes the kernel features and fundamentally impacts its generalization properties.
Read the full abstract ▾
Statistics Theory
A ridgeline correspondence criterion: the number of modes of a Gaussian mixture is finite
Carlos Améndola and Jose Israel Rodriguez
We prove that every finite multivariate Gaussian mixture density has only finitely many modes. Our approach combines an algebraic formulation of the ridgeline theory of Ray and Lindsay (2005) with a transcendence-degree argument based on Ax's functional-transcendence
theorem to bound the cardinality of the set of critical points. Our techniques extend recent work by Wang (2026), who used Ax's
theorem together with real-analytic curve selection to prove finiteness of the critical set of homoscedastic Gaussian mixtures. We introduce the ridgeline correspondence and use it to obtain a finiteness result that applies to arbitrary heteroscedastic Gaussian mixtures. Our framework also establishes finiteness of the number of modes for additional classes of
polynomial-exponential mixtures and generalized Gaussian mixtures.
Read the full abstract ▾
Statistics Theory · Cross-listed from cs.IT
A Complete Characterization of Tensorizable $f$-divergences
Rodrigo Cruz, Flavio P. Calmon and Qian Yu
Csiszar's formulation of the $f$-divergence introduced a vast family of functionals for quantifying dissimilarity between probability distributions. However, many applications in statistics and information theory rely only on a few $f$-divergences, such as the Kullback-Leibler divergence, the $\chi^2$-divergence, and the squared Hellinger distance. These divergences are especially useful because they admit simple compositional formulas under product measures, a property sometimes referred to as tensorization. In this work, we refine a formalism of tensorization previously introduced in the literature. Then, we show that any possible tensorization formula has a multi-affine form characterized by a single parameter, and identify all tensorizable $f$-divergences under our adopted notion of tensorization.
Read the full abstract ▾
Statistics Theory
Generalized Splines and Gaussian Processes
Michael Unser
For finite-dimensional linear inverse problems where the variables are Gaussian, it is well-known that the minimum-mean-square error
estimator takes the form of a regularized least-squares data fit. In this chapter, we show that this equivalence extends to a much broader infinite-dimensional setting where generalized splines take the role of linear regressors and generalized Gaussian processes on a nuclear space $S$ are the counterpart of Gaussian random vectors. The scope of this extension is of the same nature as the switch from the classic notion of function to that of a distribution, also known as a "generalized function." Our formalism involves a whitening/regularization operator $L: S\to S'$ whose continuous extension induces a native
Hilbert space $H\subset S'$ that plays a central role in our characterization. The presentation is self-contained for the most part and remarkably general and powerful. It allows for the recovery of all known instances of such equivalences; in particular, the methods involving innovations and reproducing-kernel
Hilbert spaces developed by Kailath and his students, and the mathematical correspondence between fractional splines and Mandelbrot's fractional Brownian motion (fractals), with the former being the optimal
estimators of the latter. It also covers general
Bayesian methods for the resolution of infinite-dimensional inverse problems.
Read the full abstract ▾
Statistical Methodology
Refining Relational Event Models: Bayesian Penalization and Variable Selection in REMs
Jonathan Koop, Sara van Erp and Mahdi Shafiee Kamalabad
Relational Event Models (REMs) provide valuable insights into the dynamics of longitudinal social networks. Yet, the vast availability of potential predictors for a dyad's event rate poses the risk of selecting irrelevant variables and specifying an overfitted model that does not generalize to new data. Despite the recent popularity of
Bayesian regularization methods to address this, there has not been a systematic evaluation of the performance of Exact
Bayesian Regularization (EBR) and Approximate
Bayesian Regularization (ABR) against standard Maximum Likelihood (ML) procedures commonly used for REMs. To address this, we conduct a simulation study in which directed Relational Event History (REH) data is generated with endogenous and exogenous effects of varying strength and compare the performance of (a) unregularized ML estimation, (b) ABR through normal approximations of the likelihood with Ridge and Horseshoe priors, and (c) EBR with Horseshoe priors. We find that threshold-based criteria applied to ABR and EBR with Horseshoe priors outperform univariate selection using p-values from ML estimation in variable selection accuracy. Regarding predictive performance, ABR with Ridge priors and EBR with Horseshoe priors outperform ML REMs, particularly for small sample sizes. Given only small gains with large computational burdens when using EBR, we therefore advise researchers to use ABR with a suitable prior.
Read the full abstract ▾
Machine Learning (Statistics)
Localizing Global Discrepancies: Marginal Contributions and Contextual Anomaly Detection
Tommaso dorigo
Global goodness-of-fit and discrepancy statistics can establish that a sample departs from a reference distribution without identifying which observations drive the departure. We develop a framework for this localization problem by assigning to each observation its conditional or marginal contribution across random statistical contexts. This connects resampling diagnostics and data valuation to projection theory and event-level anomaly detection. For symmetric statistics, fixed-size replacement is exactly equivalent to centered conditional localization. For U-statistics, the addition score equals the first Hoeffding/Hájek contribution; for smooth distributional functionals it is related at leading order to the influence function; and for unbiased known-background MMD it reduces exactly to the MMD witness. This viewpoint also yields more efficient
estimators. Matched-context subtraction removes fluctuations unrelated to the observation, while for pairwise MMD the event-containing terms give a simple localizer. On the LHC Olympics anomaly-detection
benchmark, the pair
estimator converges to the direct empirical MMD witness with the predicted 1/(Rm^2) scaling, where m is batch size and R the number of batches. At m=1000 and R=5x106 it reaches correlation 0.9993 with essentially identical AUC. We also ask when context contains information beyond an event's own features. In a shared-latent toy model, the full single-event signal and background distributions are identical by construction, forcing isolated-event AUC=0.5. Discriminating information survives only in cross-event dependence induced by the shared latent parameter; the ensemble recovers this information, whereas an independent-latent control does not. This separates two roles of context: efficient localization of a global discrepancy and genuinely additional class information when the alternative contains shared structure.
Read the full abstract ▾
Statistics Applications · Cross-listed from cs.CR
Optimal Adversarial Testing: Extracting Honest Test Results from Dishonest Test Takers
Owen Cox, April Xu and Weiyu Xu
In applications, it is often required to test objects or people to determine their qualities in terms of certain metrics. However, besides being naturally noisy, the test results can be corrupted by
adversarial behaviors of objects or people being tested (test takers). For example, dishonest test takers can cheat in the exams to distort the test results. With the development of AI technologies, such distortions driven by cheating using AI technologies are becoming more commonplace and severe. In this paper, we propose optimal testing strategies which can still recover needed test results even if there are cheaters polluting the results. The proposed testing strategies will optimally re-test selected group of test takers using different testing security measures. We determine the optimal testing strategies using a dynamic programming method.
Read the full abstract ▾
Statistical Methodology
Response Propensity Estimation and Cross-Fitting
Alessandro La Rocca
This paper investigates whether five fold cross fitting improves nonresponse adjustment in survey estimation when flexible machine learning methods are used to estimate response propensities. We conduct a finite population Monte Carlo simulation with 90 experimental configurations and 2,000 replications per configuration, varying sample size, response rate, and the structure of the response mechanism. Logistic regression is used as a conventional parametric
benchmark, while Random Forest and Gradient Boosting Machine are considered as flexible nonparametric models.
Read the full abstract ▾
Machine Learning (Statistics)
I-FLOP: Fast Learning of Order and Parents from Interventional Data
Liuting Chen and Alex Markham
We extend the FLOP (fast learning of order and parents)
algorithm recently proposed by Wienöbst et al. (2026) from observational to interventional data. In particular, we use the interventional BIC score of Hauser and Bühlmann (2012), adapting it to be used with the iterative Cholesky-based score updates that are partly responsible for FLOP's speed. We show that, in the sample limit, I-FLOP recovers a DAG in the same interventional Markov equivalence class as the data-generating DAG. We compare I-FLOP to existing causal structure learning
algorithms on real and simulated interventional data, where it performs favorably in terms of both performance and run time.
Read the full abstract ▾
Statistical Methodology
Exact two-sided p-values in natural exponential families: coincidence, non-uniqueness, and sample-size stability
Shaul K. Bar-Lev and Linard Hoessly
We study the non-uniqueness of exact two-sided $p$-values in continuous one-parameter natural exponential families (NEFs). For directed one-sided problems, the tail $p$-value agrees with the $p$-values using UMP, UMPU, and likelihood-ratio (LR) tests. For a two-sided simple null, we distinguish four constructions: equal-tail, density-ordered, UMPU, and LR $p$-values. At a fixed null parameter, UMPU and equal-tail $p$-values coincide if and only if the null law is symmetric about its mean; under a regular two-branch density-level condition, the same fixed-null
symmetry characterization holds for UMPU versus density ordering and equal-tail versus density ordering. Requiring any of these coincidences throughout the NEF characterizes the Gaussian family. We combine these results with the
theorem of Bar-Lev, Bshouty and Letac that UMPU and LR $p$-values coincide throughout a continuous NEF precisely for the normal, gamma and inverse-Gaussian families. We also investigate the two LR pairings not covered by those results. If equal-tail and LR $p$-values coincide throughout a NEF satisfying our standing regularity assumptions, then $(V^{2/3})^{\prime \prime \prime }=0$ on the mean domain. The same coincidence also forces an explicit density-at-the-mean identity. For an i.i.d.\ sample with canonical sufficient statistic $T_n=\sum_{i=1}^nX_i$, persistence of equal-tail-LR coincidence throughout the family along an unbounded sequence of sample sizes forces Gaussianity. A corresponding density-LR statement is given conditionally on an explicitly stated differentiated local Edgeworth expansion. Finally, inverse-Gaussian and
hyperbolic-secant examples quantify numerical $p$-value differences, disagreement of rejection decisions, and differences in power.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Performative Privacy: When Differential Privacy Maximizes Utility
Uddalak Mukherjee, Edwige Cyffers and Yann Chevaleyre
Privacy-preserving learning is often motivated by the idea that protecting users' data can preserve trust and thus participation, improving utility in the long term. However, this claim has not been formalized so far. In parallel, performative learning provides a framework for studying learning systems whose deployment affects the data they later observe. In this work, we bring these two perspectives together and introduce performative
privacy, where data leakage reduces future participation. We study a simple model where
agents repeatedly contribute data for mean estimation but may leave the system when their data is leaked.
Privacy is implemented through differentially private mechanisms, creating a trade-off between estimation noise and future participation. We show, through a theoretical study of the dynamics and numerical experiments, that a finite
privacy budget can outperform non-private estimation in the long term when the feedback loop between leakage and participation is sufficiently strong. This provides first evidence that differential
privacy can be optimal not only as a protection mechanism, but also from the perspective of long-term utility.
Read the full abstract ▾
Machine Learning (Statistics)
Conformal Risk-Averse Decision Making with Optimized Certainty Equivalent Risk Control
Amirmohammad Farzaneh and Osvaldo Simeone
We study risk-averse decision making, in which an
agent selects actions while being uncertain about the true system state. The risk is measured via optimized certainty equivalent (OCE) metrics, which generalize popular criteria such as mean-variance risk and conditional value-at-risk (CVaR). We characterize the optimal policy under known distributions, and show that it reduces to a prediction set-based solution for the CVaR. This provides an operational interpretation of conformal prediction-type prediction sets. For unknown distributions, we develop a data-driven calibration strategy, based on a synthetic model for the likelihood and held-out calibration data, yielding high-probability control of the OCE risk. The approach is evaluated on two wireless beamforming settings.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Generalized Gibbs Ensemble Weighting for Forecast Combination
Prasen R. Nuthanakaluva and Nava K. Gaddam
Forecast combination is a reliable way to improve predictive performance when several forecasting models are available. Simple aggregation rules such as the mean, median, trimmed mean, inverse-loss weighting, and exponential weighting are often strong baselines, but their relative performance can vary across
datasets, forecast horizons, deployment settings, and levels of disagreement among base forecasters. We develop Generalized Gibbs Ensemble Weighting (GGEW), a probabilistic framework that treats forecasting models as experts and assigns ensemble weights using a Gibbs-style exponential transformation of normalized predictive loss. The framework extends this basic weighting rule through numerical stabilization, diversity-aware score corrections, and online hyperparameter adaptation. GGEW produces a family of related methods, including Stable Gibbs weighting, Directional Gibbs-NCL, and Symmetric Gibbs-NCL. These variants share one core
algorithm and differ only in the score used inside the exponential weighting rule. For sequential deployment, we adopt a UCB-style bandit mechanism, called online Local-UCB, to adapt the learning rate, diversity strength, and Gibbs variant without evaluating the full hyperparameter grid at every prediction step. We evaluate GGEW on official M4 competition forecast submissions and external rolling-origin deployment experiments using Monash Traffic Hourly, Electricity Hourly, and Solar Weekly
datasets. Results suggest that Gibbs-style adaptive weighting is a useful and competitive tool across several
benchmark settings, although its relative performance varies across
datasets, forecast horizons, deployment protocols, and forecast disagreement groups. The contribution is not a universal dominance claim, but a framework and empirical study motivating further investigation of when adaptive Gibbs-style forecast combination is useful.
Read the full abstract ▾
Statistical Methodology
SCAN: Sequentially Detecting Change-points via Adaptive Nonparametric Inference
Ashoka Prabashwara, Patricia Menéndez, Liam Hodgkinson et al. (+1 more)
Modern time series are often long, serially dependent, and non-stationary. Existing change-point methods either target specific changes or become computationally intensive when using nonparametric costs on long series. Many also require thresholds to be carefully calibrated under serial dependence. We introduce SCAN, an offline method for detecting multiple distributional change-points in long, serially dependent univariate time series. SCAN compares adjacent windows using an integral probability metric, calibrates local discrepancies with a dependence-aware bootstrap, and refines candidate locations using a scaled 1-Wasserstein criterion, enabling detection of changes in mean, variance, and broader distributional structure within a unified framework. An ensemble over multiple window sizes reduces sensitivity to window size and threshold specification. We establish consistency of the estimated number and locations of change-points under exponential alpha-mixing dependence, and show that the localization statistic reduces to a CUSUM-type statistic under pure mean shifts. In simulations with up to one million observations, SCAN generally achieves higher covering and F1-scores than competing methods across mean and joint mean-variance shifts, particularly under serial dependence. On real data, SCAN identifies labeled activity transitions in sensor data and interpretable structural changes in hourly Bitcoin prices. Implementations are available in the Python package scan-cpd and R package scanr.
Read the full abstract ▾
All authors Ashoka Prabashwara, Patricia Menéndez, Liam Hodgkinson, Stuart Lee
Statistical Computation · Cross-listed from econ.EM
A Design Concept of Forecasting Software for Normalized Vector Autoregressions with Fat Tails and Stochastic Volatility
Fei Shang, Xiaolei Wang and Tomasz Woźniak
We present a suite of R packages for macroeconomic forecasting that leverages advanced
Bayesian, structural, multivariate, dynamic, hierarchical, non-linear, and non-Gaussian models. The suite enables both structural and predictive analyses, and is adapted to time series data across various types, dimensions, and sampling frequencies. Each additional feature increases computational complexity. To address this challenge, our software design incorporates a carefully curated selection of models, efficient
algorithms implemented in C++, advanced econometric and numerical methods, robust handling of complex input and output objects, and standardised workflows. This approach combines the computational efficiency of C++ with the convenience of working with data in R. We demonstrate that our packages facilitate original research contributions in forecasting, as illustrated by our example in which vector autoregressions with non-centred
stochastic volatility enhance density and point predictions relative to models with centred
stochastic volatility.
Read the full abstract ▾
Statistical Methodology
Parameter estimation in Conditional Sequential Monte Carlo algorithms through Particle Learning
Alfonso Diz-Lois Palomares and Geir Storvik
In this work, we explore particle learning strategies for the joint estimation of static parameters and latent states within conditional sequential Monte Carlo (CSMC)
algorithms. Building on this idea, we propose the p(parameter)-CSMC
algorithm, which incorporates both parameter learning and ancestor sampling, leading to much better mixing properties compared to (particle) Gibbs sampling in settings where strong internal correlations may challenge effective exploration. We also include two applications in the context of a branching process model: one using synthetic data, where we estimate the infectivity profile while assuming the reproductive number to be known, and another using real data, where we address the joint inference of the reproductive number and the infectivity profile based on daily hospital incidence from the arrival of the SARS-CoV-2 lineage B.1.1.7 (Alpha) in Norway in February 2021. We show that, in these settings, performance is dramatically enhanced, with substantially faster mixing and markedly reduced autocorrelation compared with standard particle Gibbs.
Read the full abstract ▾
Statistics Theory · Cross-listed from cs.LG
Exact Risk Ratios for Weighted Data Selection in Linear Regression
Guangjian Zhang
How much data must a fixed learner retain? Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed this question for linear regression with the minimum-norm empirical risk minimizer. A selector sees a finite
dataset $D\subseteq R^d\times R$, keeps at most $n$ examples with nonnegative weights, and $F_w(d,n)$ is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is $\infty$ for $n<d$, $d+1$ at $n=d$ and $1$ for $n\ge2d$, and the regime $d<n<2d$ was left open. We settle several cases. For every $d$ we prove $F_w(d,2d-1)=1+1/d$, which confirms a claim stated without proof in the original note. We also prove $F_w(3,4)=5/3$, $F_w(4,5)=2$ and $F_w(4,6)=3/2$, the three smallest
cells not covered by that formula. For every intermediate budget $n=d+k$ we prove the lower bound $F_w(d,d+k)\ge1+\Gamma_{d,k}$, where $\Gamma_{d,k}$ is an explicit harmonic quantity over balanced partitions of $d$. This bound is the exact minimax value on the class of
datasets whose whitened systems split into orthogonal
circuit blocks. All proved values equal $1+\Gamma_{d,k}$, and we
conjecture that this holds throughout the open regime. Our upper bounds combine a rigidity
theorem for positive spanning configurations of loss gradients with normal forms of the small positive bases in $R^3$ and $R^4$. These forms are special cases of the classification of Cornaz, Kerleau and Royer; we also control all gradients outside the basis. A dimension-free extremal-basis argument converts sign-cone geometry into selections of $d+1$ points. Explicit counterexamples rule out several shorter routes. Every upper bound is constructive, with selection procedures
polynomial in the number of points for fixed dimension. Every numerical claim about a specific instance is an exact rational or algebraic identity, recomputed in exact arithmetic in the supplementary material.
Read the full abstract ▾
Statistics Theory · Cross-listed from cs.AI
Should I Use This Synthetic Dataset for Training? How to Test with Minimal Real Data
Zhenyu Tao, Wei Xu, Xiaohu You et al. (+2 more)
Digital twins (DTs) and learned world models are increasingly used to generate synthetic data that augment the scarce real
datasets available for training artificial intelligence (AI) models in engineering systems. Owing to the inevitable simulation-to-reality (sim-to-real) gap, however, augmentation may fail to improve the performance of the trained model on the real data distribution. This paper addresses the resulting decision problem: Given a real
dataset, a candidate synthetic
dataset, and a fixed learning
algorithm, decide whether training on the augmented
dataset improves the true, population-level performance, while consuming as few real test data points as possible. Two formulations are considered: a direct test on the mean loss difference between the two trained models, and a
symmetry-based test on the paired loss difference, which trades a stronger null assumption for faster evidence accumulation. For the latter, we introduce the {adaptive e-process sign-flip test} (aeSFT), a doubly adaptive procedure that adapts both the number of Monte Carlo sign-flip rounds, and hence the computational cost, and the amount of real test data consumed. aeSFT yields anytime-valid Type-I error control, with no need to pre-specify the test-set size. Experiments on a synthetic-data classification task, a DT-aided wireless packet-scheduling task, and a
radio-map prediction task show that aeSFT identifies useful synthetic data using substantially fewer real test samples than mean-based sequential testing, matches the power of fixed-sample sign-flip testing and the paired $t$-test, while keeping the false-positive rate below the target level.
Read the full abstract ▾
All authors Zhenyu Tao, Wei Xu, Xiaohu You, Petar Popovski, Osvaldo Simeone
Statistics Theory
Exploiting Exact Conditionals Improves Conditioning: Provably Fast Mixing Time Bounds By Sampling from the Marginal
Abhijit Chowdhary, Federica Milinanni, Julianne Chung et al. (+1 more)
The problem of sampling from a probability distribution arises in many applications such as posterior sampling in hierarchical
Bayesian inverse problems and Gaussian processes for machine learning. Markov chain Monte Carlo (MCMC)
algorithms are often used for sampling from a target probability distribution, but implementations can be computationally expensive, especially for large-scale problems. In certain applications, the target distribution naturally factorizes into a lower dimensional marginal distribution and a conditional distribution that allows exact sampling. We describe an MCMC
algorithm called MarCo that exploits such a structure and generates a Markov chain via Metropolis-Hastings sampling from the marginal distribution, followed by sampling from the exact conditional distribution. By design, MarCo constructs a Markov chain on the joint space that inherits the convergence behavior of the marginal MCMC
algorithm. This provides multiple theoretical and computational advantages. We prove that MarCo can achieve improved mixing time upper bounds compared to direct sampling from the joint distribution. Moreover, compared to one-block methods that also exploit marginal-conditional structure, we use the framework of Peskun-Tierney ordering to show that MarCo has a larger right spectral gap and smaller asymptotic variance, thus leading to superior convergence properties. Numerical results illustrate the performance benefits of MarCo and are provided for various problems, including a semi-blind image deblurring example.
Read the full abstract ▾
All authors Abhijit Chowdhary, Federica Milinanni, Julianne Chung, Elizabeth Newman
Statistics Theory · Cross-listed from math.FA
Improved $\ell_0$-Isoperimetry for Convex Bodies via Mass Transport
Manuel Fernandez V
We study $\ell_0$ isoperimetry for a convex body $K\subset \mathbb{R}^n$, $n\ge2$. For a Borel set $S\subset K$, let $\partial_0^K S$ be the set of points in $K \setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the $\ell_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q \subset \mathbb{R}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0<s \le 1/2$, \[ \frac{\text{vol}(\partial_0^K S)}{\text{vol}(S)} \ge \frac{cr}{nR} \min\left\{1,\frac{\log(e/s)}{n}\right\}, \] where $c > 0$ is an absolute constant. Consequently, the associated $\ell_0$-isoperimetric coefficient is at least $cr/(n^2R)$. Previous direct lower bounds were only known for $\ell_2$ and $\ell_\infty$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to $\ell_2$ and $\ell_\infty$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.
Read the full abstract ▾