Token systems support repeated service exchange without monetary transfers, but their viability depends on the stability of token balances. We study token systems with compatibility constraints among agents. A requester is randomly sampled in each period, and only a few randomly sampled agents are available to provide service. We establish a necessary and sufficient condition for stability and show that the minimum-token rule, which selects the available provider with the lowest token balance, achieves the optimal stability region. We then apply this stability criterion to a random token system generated from stochastic block models with uniformly sampled requesters. We tightly characterize the stability regime by identifying two obstructions to stability: insufficient service opportunities for a group of communities or for an individual agent.
Stationary tail computation for high-dimensional reflected Brownian motions (RBMs) remains computationally challenging. Building on NN4MGF's shared-coordinate basic-adjoint-relationship (BAR) framework, we develop Holomorphic Cauchy Networks (HCNs). Native complex-valued rational Cauchy subnetworks enforce holomorphicity on pole-free domains, removing sampled Cauchy-Riemann penalties and their input-derivative graphs. Exact origin anchoring and boundary-coordinate exclusion enforce structural identities, while anchored interactions represent dependent transforms. Under holomorphic-log assumptions, we establish simultaneous value and first-derivative approximation for the constrained architectures and a mixed-derivative lower bound for coordinate-only representations under nonzero cross-covariance. Closed-form real-axis derivatives and sequential backpropagation further control memory. On the same NVIDIA H100 NVL, the tested 30D HCN configuration uses approximately tenfold less peak allocated memory and has 9.7-fold lower mean update time than NN4MGF; extrapolation to the respective scheduled update counts gives a projected full-schedule update-time ratio of 58.2. With 64 million sampled base inputs per high-dimensional run, HCN reaches 50 dimensions on a laptop GPU with 6.367% mean relative error over thresholds 1 through 8. Degree-matched comparisons yield lower reported mean relative errors over the primary evaluation ranges, including 1.422% versus 6.684% on the 2D Harrison non-product benchmark. An exploratory 10D correlated example illustrates the interaction extension.
Classical Langevin Monte Carlo algorithms, such as the unadjusted Langevin algorithm (ULA), are based on discretization schemes of the overdamped Langevin dynamics and are widely used for sampling in machine learning because they scale to high dimensions and large datasets. However, they require differentiable log-densities, and are less efficient for sampling heavy-tailed distributions. Although various approaches have been proposed in the literature for sampling non-differentiable and heavy-tailed targets, all of them are developed in the overdamped setting only. We propose a novel momentum-based underdamped anchored Langevin dynamics (UALD), and underdamped anchored Langevin Monte Carlo (UALMC) algorithm based on a discretization scheme of UALD. Our paper is the first to provide a kinetic (momentum-based) Langevin algorithm for non-differentiable and heavy-tailed targets that is free of asymptotic bias. The method replaces the original potential with a smooth reference potential and modifies the underdamped Langevin dynamics via multiplicative scaling in the drift term. We establish non-asymptotic guarantees in the 2-Wasserstein distance to the target distribution and show that the resulting iteration complexity has better dependence on dimension and accuracy level compared to overdamped-based anchored Langevin algorithms. We provide numerical experiments to illustrate the theory and practical performance of our proposed approach.
Recently, rectified flow has emerged as a fundamental framework for large-scale image generation, powering state-of-the-art systems such as FLUX.1 and Stable Diffusion 3. Despite its remarkable empirical success, the computational and statistical guarantees of iterative rectified flow have remained largely unexplored. We address this problem by studying c-rectified flow, a cost-aware class of rectified flow that projects velocity fields onto a gradient class while preserving endpoint marginals. The ordinary rectified flow can fail to recover the optimal transport coupling: in a Gaussian case study, the iteration converges to the optimal coupling if and only if the source and target covariance matrices commute. More generally, for a Gaussian to log-concave coupling, the ordinary rectified flow can reach a fixed point after one step from independent initialization. In contrast, under suitable regularity and uniform-integrability assumptions, iterative c-rectified flow always converges to the optimal transport coupling. We further establish quantitative one-step contraction and exponential convergence guarantees under projection-stability assumptions for both quadratic and strongly convex displacement costs. Finally, under a Hölder ball assumption, we develop new minimax-optimal score estimation rates and show that, when combined with iterative c-rectified flow, they yield a rate-optimal estimator of the optimal transport for the dimension \(d \ge 3\) and a nearly parametric rate for \(d=1,2\).
Anastasis Kratsios, Tin Sum Cheng, Bum Jun Kim, Daniel Roy
Transformers often transfer across related tasks with little fine-tuning; we study this question in noisy nonparametric regression for continuous maps $f,g:[0,1]^d\to\mathbb{R}^D$, representing the source and shifted tasks, using a single-query, single-head transformer $\mathcal{T}(\cdot)=V\operatorname{Softmax}(-α(\cdot,K))$ with $\ell^{\infty}$-based alignment scores $α$. Rather than assume that gradient-based training reaches an empirical risk minimizer, we give a model-specific two-stage procedure \textbf{certifying} source-task recovery and out-of-distribution (OOD) adaptation. With high probability, the resulting attention head recovers $f$ to arbitrary accuracy $\varepsilon>0$ in every fixed $L^p([0,1]^d)$ norm, $1\le p<\infty$, from noisy observations. For Lipschitz targets, its rate is minimax-optimal up to logarithmic factors without assuming oracle access to an asymptotic ERM. If $D=1$ and $f$ is Pfaffian than the values matrix factors into $AC$ with $A$ scaling at-most linearly $\mathcal{O}(\varepsilon^{-1})$ in the reciprocal approximation error $\varepsilon>0$. Importantly, our training procedure encodes all our identified (potentially) shared geometric structure from $f$ only into the values matrix factor $C$ and the keys matrix $K$ allowing for rapid access, and all $f$-specific structure only into $A$. Our main result concerns the OOD phase; where we identify geometric structures, which if shared by the source $f$ and OOD $g$ task; then only only the values matrix factor $A$ needs to be fine-tuned to guarantee an $L^p$-recovery of $g$. Critically, fine-tuning only $A$ is a convex problem which involving an \textit{at-most linear} number of parameters $\mathcal{O}(\varepsilon^{-1})$; dramatically cutting down on the worst-case scaling of $\mathcal{O}(\varepsilon^{-\mathbf{d}})$ unavoidable in the source-training phase.
Fan Chang, Joseph Slote, Chun-Kai Tseng, Alexander Volberg, Haonan Zhang
Polynomial threshold functions (PTFs) are an important low-complexity class of Boolean functions, with strong connections to learning theory and approximation theory. Recent work on learning and testing PTFs has exploited structural and isoperimetric properties of the class, especially bounds on average sensitivity, one of the central themes in the study of PTFs since the Gotsman--Linial conjecture recently solved by OpenAI, \cite{GLsol}. In this work we study PTFs through the lens of the Boolean surface area (or Talagrand boundary) \[ \mathbf{BSA}[f]=\mathbb{E}|\nabla f|=\mathbb{E}\sqrt{s_{f}(x)}, \] a natural measure of vertex-boundary complexity on the discrete cube. Our main result is that every degree-$d$ PTF has polylogarithmic Boolean surface area: \[ \mathbf{BSA}[f]\le C_d(\log(en))^{C_d}. \] The proof is based on the PTF Restriction Lemma of Kabanets, Kane, and Lu \cite{KKL2017} and proceeds through a tail bound for the pointwise sensitivity. In particular, it controls all subcritical fractional moments of the sensitivity. We also record a random block partition principle for Boolean surface area and an alternative recursive argument following Kane's work \cite{DK} on average sensitivity, which independently yields the second bound \[ \mathbf{BSA}[f]\le \exp(C(d)\sqrt{\log n}). \] This bound was obtained in \cite{FSVZ} without clarifying the magnitude of $C(d)$, which we do below. For lower moments $\bE |\nabla f|^η \le C(d, η)$ there is no dependence on $n$ for $0<η<1$.
We formulate flow matching on probability measures over probability measures. Directly from the Wasserstein-on-Wasserstein (WoW) continuity equation, we show that admissible nested outer and inner couplings induce a valid metameasure flow and non-local velocity field. Validity requires neither optimal plans nor a smooth manifold. Practically, this opens up the design space of multisample flow matching: exact Wasserstein plans are distinguished by energy and straightness, while sliced and lazy linear plans yield scalable alternatives. Point-cloud experiments, including controlled Bures-Wasserstein and Euclidean minibatch baselines, demonstrate the resulting geometry-cost trade-off.
The running-time distribution of a randomized algorithm is computed under independent randomness, but independence is rarely what a source guarantees. We study sources $ν$ satisfying $ν[w]\le DP[w]^s$ for every finite prefix $w$ of the random tape, where $P$ is an independent reference law, $0<s\le1$, and $D\ge1$; individual choices may be predictable, even determined by the past. The worst-case probability of any closed tape event $E$ is exactly $\min\{1,DC_s(E)\}$, where $C_s(E)$ is the infimum cost of covering $E$ by prefixes of varying depth, a tree max-flow/min-cut identity that makes worst-case survival probabilities exact and optimizable over the algorithm's choices. Three applications follow. For $n$ tasks on one machine, each retried until the next random symbol lies in its success set, every schedule has the same makespan distribution under independent randomness, yet under our constraint two fixed orders miss a linear deadline with worst-case probabilities $1$ and $\exp[-Θ(n)]$; a static priority rule is optimal at every deadline. For the standard local walk on a $k$-CNF with an assignment that satisfies a majority of each clause, we determine the sharp source threshold $s_*$. Below $s_*$, on some instances a single admissible source forces nontermination however clauses are selected; at $s_*$, with fixed $D$, the expected number of flips is at most cubic in the initial Hamming distance, against linear under independence, with matching worst-case instances; and any fixed margin above $s_*$ restores linear dependence on the distance. Third, verified backtracking for noisy predecessor search remains correct under a sufficiently strong bound on the comparison errors. In every setting the algorithm may also restart, which supplies no fresh randomness; restarting restores exponential tails exactly when the nontermination event has a prefix cover of cost below one.
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. $\textbf{Expected loads.}$ We show that the expected value of the $r$th largest bin is governed by the $r$th largest value among $n$ independent Poisson random variables of mean $m/n$. Specializing to the canonical setting of $m=n$ and $r=1$, our bounds show that the expected maximum load when $n$ balls are hashed into $n$ bins by a random $\mathbb{F}_2$-linear map is no more than the corresponding expectation for a fully random map $\textit{plus}$ $\frac{3}2 + o(1)$. Specializing to $m\gg n\log n$, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. $\textbf{Concentration.}$ When $m\gg n\log (1/ρ)$ balls are tossed into $n$ bins randomly, we expect with $0.99$ probability that $\textit{every}$ density-$ρ$ subset of bins will contain a $(1\pm o(1) )ρ$-fraction of the balls. We show that this remains the case if the $m$ balls are tossed using a random linear map, and our bound matches the $o(1)$-factor produced by the fully random case. This gives a stronger version of the Leftover Hash Lemma for linear maps. An implication of this is that all bins have load $m/n \pm O(\sqrt{(m/n)\log n})$ with probability $0.99$. We obtain these results by showing that the average of a log-potential on the bin loads is upper bounded by the cumulant generating function of a Poisson random variable of mean $m/n$.
We study the problem of sampling from target distributions whose potentials are simultaneously non-smooth, subject to superlinear gradient growth, and non-convex. We introduce the Subgradient Tamed Unadjusted Langevin Algorithm (SG-TULA), a discretisation of the Langevin diffusion that operates directly on subgradients, without relying on computationally demanding smoothing procedures. To handle the superlinear regime, taming techniques are employed to produce a stable, explicit scheme. We derive non-asymptotic convergence bounds in Wasserstein-2 distance, with all constants tracked explicitly in terms of dimension and inverse temperature, improving upon the currently known rates for subgradient-based Langevin algorithms. We further provide excess risk estimates for the associated optimisation problem. We verify the assumptions, with explicit constants, for the regularized pretraining potential of a LLM in the GPT-2 lineage and the boosted coordinate-wise variant of SG-TULA pretrains the former competitively against finetuned AdamW and Muon, for which no comparable non-asymptotic guarantees are presently available.
Süleyman Kerimov, Pengyu Qian, Mingwei Yang, Sophie H. Yu
We study centralized two-way dynamic matching markets in which agents arrive stochastically over time and wait in queues associated with their types. We focus on static priority policies that assign each agent type a fixed ranking over its neighbors and make online matching decisions using only queue availability. We propose the General Priority ($\mathbf{GP}$) policy, which builds on the Tree Priority ($\mathbf{TP}$) policy introduced in [KAG25]. Under the general position gap condition, $\mathbf{GP}$ selects matches using a nondegenerate optimal basic solution of the fluid relaxation. It prioritizes children over parents within trees and consistently gives clockwise neighbors priority over counterclockwise neighbors on each cycle. We establish the optimal all-time regret scaling $O(ε^{-1})$ for $\mathbf{GP}$ on general two-way matching networks, where the general position gap $ε$ measures the fluid relaxation's distance from degeneracy. In particular, this resolves the conjecture by [KAG25] on the optimal $ε$-dependence for $\mathbf{TP}$.
We analyze stochastic mirror descent for minimizing a convex objective expressed as an expectation under the stationary distribution of a Markov chain, using noisy subgradient observations along a single sample path. Through Poisson's equation, we decompose the Markovian noise and control its contribution under regularity and moment conditions that allow the stochastic subgradients and the Poisson solution to be unbounded across the state space. We establish an $O(T^{-1/2})$ bound on the expected suboptimality gap of the weighted-average iterate for an appropriately chosen step size. The analysis does not require aperiodicity or convergence of the chain's marginal distributions to stationarity. For irreducible finite-state chains, we verify the required conditions on the Poisson solution and derive explicit bounds that quantify the effect of periodicity. For irreducible countable-state chains, we verify the required regularity and moment conditions under a geometric Lyapunov drift condition and suitable growth bounds on the stochastic subgradients.
Denoising diffusion models are a recent class of generative models exhibiting state-of-the-art performance in image and audio synthesis. Such models approximate the time-reversal of a forward noising process from a target distribution to a reference density, which is usually Gaussian. Despite their strong empirical results, the theoretical analysis of such models remains limited. In particular, all current approaches crucially assume that the target density admits a density w.r.t. the Lebesgue measure. This does not cover settings where the target distribution is supported on a lower-dimensional manifold or is given by some empirical distribution. In this paper, we bridge this gap by providing the first convergence results for diffusion models in this more general setting. In particular, we provide quantitative bounds on the Wasserstein distance of order one between the target data distribution and the generative distribution of the diffusion model.
Score-based generative models (SGMs) need to approximate the scores $\nabla \log p_t$ of the intermediate distributions as well as the final distribution $p_T$ of the forward process. The theoretical underpinnings of the effects of these approximations are still lacking. We find precise conditions under which SGMs are able to produce samples from an underlying (low-dimensional) data manifold $\mathcal{M}$. This assures us that SGMs are able to generate the "right kind of samples". For example, taking $\mathcal{M}$ to be the subset of images of faces, we find conditions under which the SGM robustly produces an image of a face, even though the relative frequencies of these images might not accurately represent the true data generating distribution. Moreover, this analysis is a first step towards understanding the generalization properties of SGMs: Taking $\mathcal{M}$ to be the set of all training samples, our results provide a precise description of when the SGM memorizes its training data.