Minimax Rate

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, up 25% on the four weeks before. 0.1% of all new papers.

Jul 6Week of Sep 21

Latest papers 38

Sep 30, 2026cs.LG

Finite-Horizon Fisher Memory in Two-Sided Power-Bounded Recurrent Systems

We analyse allocation, admission and post-write retention in finite-horizon linear-Gaussian noisy recurrent memories. At every horizon, the directional Fisher memory

M_n

satisfies

\operatorname{tr}M_n=N

: non-normality redistributes information but cannot raise its spherical average, while normal carriers satisfy

M_n=I

. For bi-power-bounded carriers, we derive uniform

1/n

lag bounds, identify the limit of

M_n

with the inverse of the classical Cesàro asymptotic limit of

W^\top

, and give finite-horizon error bounds. A time-varying coupling defines an end-to-end store operator. The writer-optimal direction need not be store-optimal. After writing ends, an invertible hold preserves the full stored Fisher matrix. Additive contamination bounded by

α

times the closure covariance retains at least

1/(1+α)

of that matrix; a covariance-aware decoder attains the corresponding accuracy. With recurrent carriers held fixed, training input masks and linear readouts approached the task-specific optimum in 160 runs, with median normalized Rayleigh efficiency above

0.998

. Binary accuracy matched the Gaussian prediction to mean absolute error below

0.002

over more than four orders of magnitude in

J

. In a separate pre-specified study of 320 runs, trained masks followed the designated input-time objective in both carrier types, in 16 of 16 draws. These studies used development-seen carriers and are pre-specified validations, not blind holdouts. The same fixed design reproduced the objective-specific result in 16 of 16 draws on carriers unused before run commitment. Exact isolation preserved information, while a decoder fixed at its training horizon fell to chance; inverse-adjoint transport restored its sampled decisions to numerical precision.

Jeonghoon Lee

Attractor Dynamics Inc.

Fisher Information Matrix Recurrent Model Recurrence Minimax Rate Retention

Sep 30, 2026stat.ML

Minimax Additive Regression under Unknown Dependent Designs

We study additive regression under a potentially non-product random design on

[0,1]^d

, allowing the dimension

d

to grow with the sample size

n

. We introduce coupled smoothness classes that separately control the regularity of the marginal densities and the density-weighted additive components. To handle dependence, we adapt a Riesz-basis construction for functional ANOVA models and establish compatibility bounds with constants independent of the dimension under uniform bounds on the joint density. We construct thresholded least-squares estimators and establish matching minimax upper and lower bounds for prediction with known or unknown marginal densities, under suitable dimension-growth conditions. When the marginal densities are at least as smooth as the weighted components, the unknown-density problem attains the known-density minimax rate. When the densities are less smooth, their regularity determines the minimax rate over the coupled class. Finally, we show that the centered additive components can be recovered at the same aggregate upper rate, without an additional order of error.

Baptiste Ferrere, Fabrice Gamboa, Jean-Michel Loubes

Université de Toulouse EDF R&D · Université de Toulouse ANITI

Minimax Rate Minimax Growth Random

Sep 30, 2026stat.ML

Minimax rates for learning spectral Barron functions by deep ReLU neural networks

We study how well deep neural networks approximate and learn spectral Barron functions. Recent studies have shown that these function classes can be efficiently approximated by shallow neural networks without suffering from the curse of dimensionality. We complement these results by providing new approximation bounds for deep networks with ReLU activation and establishing the minimax rates for learning these function classes. Specifically, we show that

d

-dimensional spectral Barron functions with smoothness index

s>0

can be approximated by deep ReLU neural networks with approximation rate

\widetilde{\mathcal{O}} (S^{-\frac{1}{2}-\frac{s}{d}})

, where

S

denotes the number of nonzero parameters in the network. Using this approximation result, we further show that deep ReLU neural networks can learn spectral Barron functions in a fast rate

n^{-\frac{d+2s}{2d+2s}}

with

n

training samples. Finally, we prove that this convergence rate is minimax optimal up to logarithmic factors.

Songqiu Ma, Yunfei Yang

School of Mathematics (Zhuhai), Sun Yat-sen University, Zhuhai, China. · School of Mathematics (Zhuhai) and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Zhuhai, China.

Rectified Linear Unit Networks Neural Network Approximation Minimax Rate

Sep 23, 2026math.ST

Robustness of Diffusion Models under Distribution Shift

Score-based diffusion models are increasingly considered in settings where the underlying data distribution may differ from the training distribution, yet existing theoretical guarantees largely focus on the no-shift setting. In this work, we study robust score estimation under Wasserstein perturbations of a reference distribution. For the Ornstein--Uhlenbeck diffusion, we show that robust estimation decomposes into two fundamental components: the statistical cost of learning the reference distribution and the intrinsic cost of distribution shift. The latter scales quadratically with the Wasserstein radius, and this dependence is minimax optimal. We construct an explicit finite-sample estimator achieving the resulting robust minimax rate without knowing the shift radius. When the reference distribution lies on an unknown low-dimensional subspace, the statistical term adapts to the intrinsic dimension while the shift cost remains unchanged. Finally, we show that the same decomposition governs positive-time reverse sampling and obtain matching minimax guarantees in KL divergence. Together, these results characterize how finite data, intrinsic dimension, and distribution shift affect the robustness of score-based diffusion models.

Wei Luo, Neil K. Chada, Shijie Zhang +1

Department of Mathematical Sciences, Tsinghua University · Department of Mathematics, City University of Hong Kong, Hong Kong SAR · Artificial Intelligence Research Institute, Shenzhen MSU-BIT University +1

Score-Based Diffusion Model Distribution Shifts Wasserstein Distance Diffusion Models Uncertainty Score Minimax Rate

Sep 22, 2026stat.ML

Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions

We study preference elicitation under the Bradley-Terry-Luce (BTL) model where the true partworth vector is unknown and has to be estimated as a parameter with elicited preference information. The set of selected pairwise queries is non-uniform, deterministic, and arbitrary over a collection of alternatives, provided that it satisfies a joint identifiability condition. We focus on understanding when the canonical maximum likelihood estimator (MLE) is finite and admits sharp error bounds without explicit compactness constraints on the feasible set or external regularizers. To this end, we derive minimax lower bounds under the standard bounded dynamic range condition, and find that the same Fisher-information geometry in the classic Cramér-Rao lower bounds underpins the finite-sample difficulty of the estimation problem. By combining a non-asymptotic expansion of the likelihood score equation with a fixed-point localization argument, we identify a design-dependent sample size threshold above which the unconstrained canonical MLE exists and is unique with high probability. The same expansion yields a decomposition of the estimation error into a linear stochastic term, an explicit second-order bias, and a higher-order remainder. A refined analysis gives sufficient sample size conditions under which the canonical MLE attains the minimax rates up to logarithmic and constant factors. These results provide a unified non-asymptotic theory for parametric utility elicitation and reveal when the inference is determined by response data alone rather than by external regularization. Preliminary numerical results are consistent with the theoretical findings.

Yicheng Li, Huifu Xu

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong.

Maximum Likelihood Finite-Sample Minimax Rate Preference Alignment Learning

Sep 16, 2026cs.RO

Asymptotically Optimal Multi-Robot Task and Motion Planning

Multi-robot task and motion planning (MR-TAMP) requires jointly reasoning about discrete task decisions and continuous collision-free motions of multiple interacting robots. Although asymptotically optimal algorithms have been developed for task and motion planning, extending these guarantees to the multi-robot setting introduces an important challenge: different task transitions may involve different subsets of robots and therefore impose constraints of different dimensions on the composite configuration space. Consequently, an asymptotically optimal planner must not only optimize motion within each task mode, but also ensure sufficient exploration of the different types of transitions connecting them. We characterize this transition structure and establish sufficient conditions for global asymptotic optimality in MR-TAMP, requiring persistent coverage of relevant transitions and asymptotically improving motion planning within connected feasible regions. Based on these conditions, we develop an efficient asymptotically optimal MR-TAMP algorithm that combines evolving individual-robot roadmaps with implicit tensor-product search, avoiding explicit construction of the composite roadmap. The planner further employs conditional transition sampling, lazy collision checking, and mode- and solution-level guidance to improve finite-time planning efficiency while retaining persistent exploration. The resulting framework provides asymptotic optimality guarantees for multi-robot manipulation while efficiently exploiting the structure of individual-robot motion planning.

Thi Thuy Ngan Duong, Cheuk Tung Shadow Yiu, Rahul Shome +1

Nanyang Technological University · The Australian National University

Multi-Robot Motion Planning Motion Planning Collision-Free Trajectories Planning Finite Time Analysis Transitions+1

Sep 14, 2026stat.ML

Learning under Target Shift: Optimal Density Ratio Estimation and Importance-Weighted Regression

We study density ratio estimation and importance-weighted regression under target shift with continuous outputs. Under target shift, the conditional distribution of the inputs given the outputs remains invariant across the training and test distributions, while the output marginal distribution may change. Although this problem has been extensively studied for discrete outputs, the continuous setting is substantially less understood: the importance weights are determined by an unknown density ratio function, for which existing estimation methods lack explicit finite-sample convergence rates. We propose a spectral regularization method in a reproducing kernel Hilbert space (RKHS) for estimating the continuous density ratio from labeled training samples and unlabeled test inputs. Under a source condition with regularity parameter

ι>0

, we establish high-probability finite-sample guarantees and show that the estimator achieves the capacity-independent minimax-optimal RKHS-norm rate

O(n_η^{-ι/(2ι+2)})

. We then incorporate the estimated density ratio into importance-weighted regression and characterize the propagation of density-ratio estimation error to the final predictor. When sufficiently many samples are available for density ratio estimation, the resulting regression estimator attains the minimax-optimal rates of standard kernel regression. These results establish a finite-sample theory for continuous density ratio estimation and importance-weighted learning under target shift.

Ren-Rui Liu, Zheng-Chu Guo

School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, China

Density Ratio Estimation Finite-Sample Minimax Rate

Sep 8, 2026stat.ML

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query

Q: \mathbb{R}\to\{0,1\}

chosen by a central learner. The distribution has mean in

[-λ,λ]

and

k

-th central moment at most

σ^k

, for a fixed

k>1

. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every

k>1

, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set

Q^{-1}(1)

is restricted to a union of at most

s

intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order

(λσ/(s\varepsilon^2))\log(1/δ)

, giving the full tradeoff between sample complexity and interval complexity to within

k

-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.

Ivan Lau, Jonathan Scarlett

National University of Singapore

Optimal Sample Complexity Minimax Rate Mean Optimal Trade-Off

Aug 13, 2026stat.ML

Sinkhorn Linearization and the Spectral Proxy: Unifying the Statistical and Algorithmic Theory of Feature-Parameterized Inverse Optimal Transport via a Single Spectral Sandwich

We develop the statistical and algorithmic theory of inverse optimal transport (IOT) under the feature-parameterized cost C_theta(i,j) = -theta^T phi(i,j). The core technical contribution is the Sinkhorn linearization -- the implicit-function sensitivity of the entropic OT plan to the cost -- together with its spectral proxy, a formula that is spectrally exact yet geometrically transparent. The restricted Hessian on the tangent space satisfies the spectral sandwich (pi_min/epsilon) I <= H_T^{-1} <= (pi_max/epsilon) I, yielding the single core bound sigma_min >= (pi_min/(a_max epsilon)) sqrt(lambda_min(Sigma)) that drives the entire theory. On this core we establish four theorems and one observation. T1 (identifiability): theta is globally injective on the quotient of the gauge kernel, with dimension bound F <= (K-1)^2. T2 (sparsistency): the l1-penalized estimator recovers the true support under irrepresentability and score concentration, with exponential failure probability. T3 (well-posedness): the feature-moment map M(theta) = Phi^T x_theta is strongly monotone, and the inverse is Lipschitz with constant L <= epsilon ||Phi^T S_a||_op / (pi_min lambda_min(Sigma)). T4 (convergence): local strong convexity with mu >= pi_min^2 lambda_min(Sigma) / epsilon^2 guarantees monotone gradient descent convergence. O5 (misspecification): the estimator converges to the OT-model projection of the truth; the Holder continuity of the projection map is assessed numerically, yielding setting-dependent empirical exponents alpha_eff in (0,1).

Han Dong, Jiaming Li, Yongqiang Gong +2

School of Medicine, Nankai University · College of Artificial Intelligence, Nankai University

Optimal Transport Approach Proximal Operators Minimax Rate Spectral

Aug 11, 2026cs.IT

Information Bottleneck under Perfect Privacy

In this work, we study the information bottleneck under perfect privacy, with particular emphasis on the active-rate regime, where the representation-rate constraint is binding and directly limits the achievable utility. The goal is to construct a representation that preserves utility-relevant information while remaining statistically independent of a sensitive variable. This exact independence requirement introduces an additional constraint beyond the classical rate-relevance tradeoff and must be explicitly incorporated into the optimization. To this end, we develop an alternating direction method of multipliers (ADMM)-based method tailored to the resulting problem structure. Under suitable regularity conditions, we establish global convergence of the generated sequence, characterize its convergence rate through the Kurdyka-Lojasiewicz exponent, and extend the analysis to inexact block updates.

Junle Zhong, Mohamad Assaad, Sreejith Sreekumar

Laboratoire des Signaux et Syst`emes (L2S), CNRS, CentraleSup´elec, Universit´e Paris-Saclay, 91190 Gif-sur-Yvette, France

Information Bottleneck Minimax Rate Kullback-Leibler Regularization Privacy Lyapunov Function Representation Quality+1

Aug 10, 2026cs.LG

Training-Free Universal Approximation by Prompting Random Transformers

How expressive is prompting a transformer? Answering this question is important for separating the roles of prompting, architecture, and pretraining in transformer models, and for determining whether task-specific behavior must be stored in model weights or can instead be induced at inference time through the prompt. We show, in an approximation-theoretic sense, that pretraining is optional: a single-layer softmax attention network with random, untrained weights can approximate any Hölder function on a compact manifold when steered by an appropriate soft prompt. Guided by the connection between softmax attention and kernel methods, we construct explicit soft prompts (a prompt per target function, independent of the query) as solutions to linear systems matching attention logits to Gaussian kernel exponents, under which the frozen transformer emulates the classical Nadaraya-Watson kernel estimator. The construction requires only a mild rank condition on the weights, which we show holds almost surely under Gaussian initialization. The prompted network inherits the theoretical guarantees of kernel regression, leading to universal approximation theorems with minimax-optimal rates that depend on the intrinsic dimension. We further quantify the cost of prompting, exposing a tradeoff between the norm of the constructed soft prompt tokens, prompt length, and hidden dimension. Numerical experiments corroborate the constructions and predicted rates.

Alexander Hsu, Rongjie Lai

Department of Mathematics, Purdue University

Transformer Architectures Approximation Prompt Engineering Training-Free Minimax Rate

Aug 3, 2026cs.LG

BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition

Active feature acquisition (AFA) asks which unobserved feature to measure next for each test instance under a budget. Greedy rules are easy to train but can overlook context features whose value is realized only through later acquisitions, while reinforcement-learning and generative approaches introduce difficult optimization or conditional-density estimation. We introduce \method, a deployable, supervised alternative that learns a separate candidate-conditioned risk-to-go function for every remaining budget. Starting from the one-step terminal classification risk, the functions are fitted backward with Bellman targets; inference greedily minimizes the learned terminal risk using only observed values, the mask, candidate identity, and remaining budget. A controlled non-myopic benchmark shows the expected mechanism: at budgets two and three, \method improves accuracy over its one-step ablation by

4.84\pm2.17

and

4.39\pm1.10

percentage points (mean

\pm

standard error over five seeds). On Fashion-MNIST with 20 candidate pixels, it improves accuracy at every nontrivial reported budget on average, including

10.20\pm0.74

points at four acquisitions; its mean paired gain across budgets

\{2,4,8,12,16\}

is

3.50\pm0.37

points. A three-seed MiniBooNE study is mixed at small budgets but positive at 8 and 16 acquisitions, identifying a current boundary rather than supporting a universal claim. These results establish a reproducible mechanism-level case for direct Bellman risk regression and delimit the experiments still needed for state-of-the-art comparison.

Jiaorong Feng, Qian Li, Ying Li

Curtin Business School, Curtin University, Perth, Western Australia, Australia · †Present affiliation: Independent Researcher. · School of Electrical Engineering, Computing and Mathematical Sciences, Curtin University, Perth, Western Australia, Australia

Pool-Based Active Learning Feature Engineering Minimax Rate

Jul 31, 2026stat.ML

Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs

We study expected improvement (EI) for minimizing a deterministic function

f

in the RKHS

\mathcal H_k

of a continuous positive-semidefinite kernel

k

on a nonempty compact set

\mathcal X\subset\mathbb R^d

. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance

σ^2k

,

σ>0

. A weak-EI policy queries a point whose EI is at least a fixed positive fraction of its maximum. We introduce a notion of sequential separation radius relating ranked selected-point innovation norms to Kolmogorov widths, drawing on greedy approximation. Standard power-function estimates from scattered-data approximation and a finite-budget regret argument yield the rates. After

N

post-initial queries, every weak-EI policy has simple regret

O(N^{-ν/d})

for isotropic Matérn kernels of smoothness

ν>0

and

O(\exp[-c_1\min\{N,N^{1/d}\log(eN)\}])

for the isotropic squared-exponential kernel, with

c_1>0

. For

d=1

, the sharper bound

O(\exp[-c_2N\log(eN)])

holds for exact EI, with

c_2>0

. These bounds are uniform over each fixed RKHS ball. If

\mathcal X

has nonempty interior and

B>0

, the exact EI policy is minimax-rate optimal over the RKHS ball of radius

B

for Matérn kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of

\mathcal X

.

Emmanuel Vazquez, Sébastien Petit

Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des Signaux et Systèmes, 91190 Gif-sur-Yvette, France · Laboratoire national de métrologie et d’essais (LNE), 1 rue Gaston Boissier, 75724 Paris Cedex 15, France

Reproducing Kernel Hilbert Spaces Minimax Rate Kernel Method Minimax Objective Functions Improvement

Jul 30, 2026stat.ML

The Noise Premium in Adversarial Training for Kernel Regression

Adversarial training can improve the robustness of predictive models to bounded perturbations, often at the cost of statistical efficiency. We study this trade-off in kernel regression over a reproducing kernel Hilbert space (RKHS). It is shown that, under squared loss, adversarial training in RKHS introduces a term involving the product of the function norm with the mean absolute value of the response noise, which we call the \textit{noise premium}. Our analysis shows that the noise premium makes the prediction error of adversarial training converge strictly more slowly than the nonparametric minimax benchmark even after balancing approximation and estimation errors. Moreover, for a fixed perturbation budget, once the budget exceeds a certain threshold, the solution to adversarial training collapses to the zero function. To mitigate these effects of the noise premium, we propose noise-debiased adversarial training. The resulting noise-debiased estimator can attain the minimax optimal rate up to a logarithmic factor for the prediction error, raises the collapse threshold, and admits an explicit bound on the increase in adversarial loss. Numerical experiments on synthetic and real data support the theoretical findings and validate the effectiveness of the proposed noise-debiased method.

Yiling Xie, Xiaoming Huo

Department of Decision Analytics and Operations, City University of Hong Kong · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology

Kernel Ridge Regression Adversarial Training Minimax Rate

Jul 25, 2026cs.LG

Training with (Swap) Regret Loss in a Single-Layer Self-Attention Model: A Case Study on the Probability Simplex

We revisit the regret loss framework introduced in Park et al. (2025), which uses decision-theoretic regret as a direct loss function for training models to make better decisions, through the lens of probability-simplex policies. Our first result shows that a single-layer self-attention model trained with regret loss admits a stationary point whose forward-pass exactly matches smoothed fictitious play with the appropriate stepsize that ensures no-regret behavior-i.e., for any given policy input, the model outputs the same update that smoothed fictitious play would produce. In parallel, we also newly introduce a swap-regret loss function, which extends the regret-loss framework beyond external regret and enables models to directly optimize for swap-deviation robustness. We further show that this swap-regret loss admits a stationary point whose forward pass implements the corresponding swap-regret update induced by classical Blum-Mansour no-pass implementation algorithm, with each head implementing an external-regret update via smoothed fictitious play. Together, these results show that regret-trained attention can realize differentiable mechanisms whose deployment induces equilibrium behavior in games: external-regret dynamics lead to coarse correlated equilibrium, while swap-regret dynamics lead to correlated equilibrium. Thus, regret-based objectives steer minimal attention architectures toward online-learning dynamics with game-theoretic guarantees, without supervised traces of those algorithms.

Chanwoo Park, Asuman Ozdaglar

1MIT EECS

Plan Regret Self-Play Minimax Rate Switch Probability

Jul 19, 2026cs.IT

Rate-Distortion-Perception Theory: Redefining the Fundamental Limits of Information Representation

Classical rate-distortion (RD) theory has long established the fundamental limits of lossy compression by quantifying the minimum number of bits required to represent a source under a prescribed distortion constraint. However, widely used distortion measures such as mean-squared error often fail to capture perceptual quality or semantic validity, which are increasingly central in modern learning-driven applications. Rate-distortion-perception (RDP) theory extends the RD framework by introducing perception as a third fundamental axis, quantified via distributional similarity between the source and reconstructed signals, leading to the rate-distortion-perception function (RDPF). This tutorial provides a structured overview of the coding principles underlying perception-aware lossy compression and surveys recent achievability results under different randomness assumptions. It then presents a unifying optimization viewpoint for computing the RDPF as defined by Blau and Michaeli, for both discrete and continuous sources under broad families of perceptual constraints, including f-divergences, alpha-divergences, and Wasserstein-based metrics. Special attention is given to computational tools such as alternating minimization schemes, Newton-based methods, and convex optimization formulations, as well as to analytically tractable cases such as Gaussian sources and the perfect-realism regime. Unlike recent broad surveys that emphasize generative architectures and AI-empowered communication systems, this tutorial focuses on the coding-theoretic and computational machinery needed to characterize, compute, and interpret the RDP limits. Finally, the tutorial outlines promising research directions at the intersection of information theory, neural compression, robust source coding, and perception-aware networked control systems.

Photios A. Stavrou, Giuseppe Serra, Marios Kountouris

Rate-Distortion Theory Source-Channel Coding Information-Theoretic Limits Distortion Minimax Rate Fundamental Limits+1

Jul 3, 2026cs.IT

Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?

Ivan Lau, Jonathan Scarlett

National University of Singapore

Minimax Rate Maximization Exponential Family Open Problems Interaction Data

Jul 2, 2026cs.LG

Safe Inference-Time Alignment via Lagrangian Reward Augmentation

Inference-time alignment steers a frozen language model during decoding using auxiliary reward signals, avoiding the cost of repeated weight updates. However, existing inference-time alignment methods typically optimize a single scalar score, so explicit safety constraints must either be ignored or encoded through manually tuned penalties. We propose Lagrangian Reward Augmentation (LARA), a general inference-time alignment framework under safety constraints. Starting from a KL-regularized constrained objective with a reward model and a cost model, LARA dualizes the constraint and reduces the optimization problem to a one-dimensional convex problem over a nonnegative dual variable. Estimated on a small calibration set, this dual variable defines an augmented reward that can be used as a drop-in scoring signal within existing inference-time alignment methods. For sequence-level sampling methods, such as Best-of-N reranking, the calibrated dual variable corresponds to the solution of the expected-cost constrained problem. For token-level reward-guided decoding methods, the same construction yields a principled dual-calibrated heuristic rather than an exact constrained-policy guarantee. We evaluate LARA on both sequence-level and token-level inference-time alignment methods, and find that LARA improves the helpfulness-harmlessness tradeoff, with Best-of-N achieving the best performance among inference-time methods, approaching finetuning-based direct alignment baselines.

Yaswanth Chittepu, Ativ Joshi, Sohini Chintala +1

University of Massachusetts Amherst · Independent Researcher

Reward Gradients Frozen Language Model Minimax Rate

Jul 2, 2026cs.LG

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least

T^{1/2 - 1/(2p)}

, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains

O((\log T)^2)

regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves

o(\sqrt{T})

regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

Jiawei Zhang

Stern School of Business New York University

\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret Queue Control Minimax Rate Slow Relaxation Modes

Jun 15, 2026eess.SP

A Perception vs. Distortion Perspective on Score-Based Generative Channel Estimation

Driven by their remarkable success in computer vision and inverse problem solving, score-based models are increasingly applied to wireless communications, where they show promise across a range of physical-layer tasks. However, despite this growing interest, the current literature often lacks a rigorous analysis of when score-matching offers a tangible advantage over traditional discriminative learning. This paper aims to address this gap through the use-case of channel estimation, a fundamental inverse problem in wireless systems. We present a theoretically grounded interpretation of score-based channel estimation through the lens of the perception-distortion tradeoff, identifying the conditions where score matching excels as well as its key limitations. In particular, by modeling downstream wireless tasks (e.g., capacity maximization) as functionals of the channel estimation process, we quantify the excess risk incurred by standard distortion-minimization approaches. Extensive numerical results show that under high predictive uncertainty, the large excess risk gap can be offset by score-based estimation, enabling near Bayesian-optimal precoding via the learned posterior, whereas in the low predictive uncertainty regime, discriminative distortion-minimization approaches are preferable due to lower complexity and more efficient use of model capacity.

Marco Skocaj, Lukas Eller, Mate Boban

All authors are with the Advanced Wireless Technology Laboratory, Huawei Heisenberg Research Centre, Munich, Germany.

Channel Estimation Beamforming Minimax Rate Wireless Communications Channel Distortion+2

Jun 9, 2026stat.ML

Annealed Entropic Allocation for Ranking and Selection

We propose annealed entropic allocation, an adaptive sampling policy based on an annealed, weighted soft-min formulation of static budget allocation. We replace the maximin large-deviation rate objective with a weighted log-sum-exp surrogate that blends challenger-specific pairwise scores through soft-min weights, avoiding hard switching when several challengers are nearly active. To capture tail behavior beyond the leading exponent, the surrogate incorporates saddlepoint prefactors from refined pairwise tail asymptotics. Because these corrections are subexponential, decreasing the annealing temperature with the budget preserves the same first-order target allocation. For the static problem, we prove uniform convergence to the hard minimum, concentration of soft-min weights on active challengers, and continuity of the induced target-allocation map under fixed weights. Experiments show that the proposed methods are consistently competitive: the no-saddlepoint ablation performs best in symmetric Gaussian and exponential slippage settings, while saddlepoint weighting can help in heterogeneous or asymmetric cases.

Xin Fei, Juergen Branke

Business School · The University of Edinburgh, Edinburgh, UK · Warwick Business School +1

Minimax Rate Token Budget Allocation Ranking

Jun 9, 2026cs.IT

Minimum Distortion Quantization with Specified Output Distribution

We derive the optimal quantizer of a real-valued random variable

W

with distribution

P_W

such that 1) the distribution of the quantization output

X

that can take

k

values follows any specified distribution

P_X

over

\{1,\ldots,k\}

, and 2) the minimum mean squared error (MMSE) of estimating

W

from

X

is minimized. It is shown that the optimal quantizer takes the form

X=σ\big(F_{σ^{-1}(X)}^{-1}(F_W(W))\big)

, where

σ

is the optimal permutation of

\{1,\ldots,k\}

among all permutations to minimize the MMSE, and

F

is the cumulative distribution function. When

P_W

is uniform over an interval or

P_X

is uniform over

\{1,\ldots,k\}

, the quantizer takes a simple form

X=F_{X}^{-1}(F_W(W))

. The concept of majorization plays a key role in the optimality proof. Specifying the output distribution is useful for designing quantizers with explicitly controlled output entropy, maximized mutual information between input and output, tailored output distribution to match channel input requirements for communication, and data anonymization.

Aolin Xu

Rate-Distortion Theory Quantizer Minimax Rate Distributions Mutual Information Optimality

Jun 5, 2026math.ST

A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space

We study the minimax rate of estimating a future value

μ_{t_n+h}

of a curve

t\mapstoμ_t

in the

2

-Wasserstein space

\mathcal{P}_2(\mathbb{R}^d)

from finitely many noisy snapshots of its past, under an adiabatic bound

\|\nabla_t^k v\|\le\varepsilon

on the

k

-th covariant derivative of the velocity field. Our central result is a unified temporal-spatial minimax lower bound: over regular, locally transport-rich subclasses, every estimator incurs

W_2

-risk with

M

-exponent

γ_d(k+1)/(k+1+γ_d)

,

γ_d=\min(1/d,1/2)

(

M

the total sample size). It follows from a temporal-to-spatial reduction: the smoothness budget defines a reachable

W_2

-ball into which a transport packing is embedded along the time axis, and the information of the entire snapshot experiment is controlled by a Fano argument -- the spatial packing is classical, but its smoothness-admissible temporal embedding and the full-window analysis are new. The bound interpolates a dimension-free extrapolation floor of order

\varepsilon h^{k+1}

-- the irreducible cost of an unobserved future, present even with the exact past -- and the spatial estimation curse

M^{-γ_d}

, recovering the static distribution-estimation rate as

k\to\infty

. We state the lower bound in a design-dependent form -- with a design-weighted effective sample size -- valid for arbitrary observation times, and obtain the closed-form exponent in the dense (equispaced) regime. The matching upper bound is established at

k=0

(rate

M^{-1/(d+1)}

,

d\ge3

) and, in a translation submodel, for all

k

; for

k\ge1

a covariant estimator attains the rate conditionally on two estimates (a comparison-geometry bias bound and an optimal-transport map-estimation rate), leaving the unconditional general-

k

upper bound as an open problem. Numerical experiments on synthetic curved and flat families corroborate the predicted exponents.

Munsik Kim

Wasserstein Distance Minimax Rate Exponential Family Distributions

Jun 4, 2026stat.ML

Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods

Understanding the generalization performance of over-parameterized neural networks has become a central topic in deep learning theory. While recent advances, particularly works under the Neural Tangent Kernel (NTK) regime, have shed light on the behavior of shallow architectures, the statistical generalization properties of deep neural networks (DNNs), especially in regression tasks, remain far less understood. In this paper, we make significant progress toward closing this gap by providing a comprehensive generalization analysis of DNNs trained using gradient-based methods. First, we establish, for the first time, a crucial connection between the learning dynamics of a DNN with smooth activation functions trained via gradient-based methods and those of kernel methods, showing that gradient-based methods on over-parameterized DNNs can fully inherit the favorable learning dynamics of their kernel counterparts. Building on this connection and the well-established optimality of kernel methods, we derive the first known minimax-optimal rates for the excess population risk of both gradient descent (GD) and stochastic gradient descent (SGD), under the assumption that network width scales polynomially with the sample size. Our results demonstrate that, with sufficient width, DNNs trained by GD or SGD can achieve generalization performance comparable to kernel-based methods.

Junyu Zhou, Puyu Wang, Yunwen Lei +2

Mathematical Institute for Machine Learning and Data Science, Catholic University of Eichstätt-Ingolstadt · Department of Computer Science, RPTU Kaiserslautern-Landau · Department of Mathematics, The University of Hong Kong +1

Overparameterization Neural Tangent Kernel Stochastic Gradient Descent Minimax Rate Neural Network

May 26, 2026cs.LG

Near-Optimal Regret in Adversarial Kernel Bandits

We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose an exponential-weights algorithm built on a regularized importance-weighted loss estimator, together with an explicit correction term that cancels the bias introduced by the regularization. Our main result bounds the regret by

\widetilde{O}\big(\sqrt{T\, d_*(λ)\,\log|{X}|}\big)

, where

d_*(λ)

is a widely-adopted notion of effective dimension that captures the complexity of the kernel. Up to logarithmic factors, this matches the known rate achieved in the related stochastic kernel bandit problem. A notable application is the Matérn

(ν,d)

kernel with smoothness parameter

ν

on

\mathbb{R}^d

, for which our bound specializes to

\widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big)

, improving over the best-known prior rate of Chatterji et al. [2019] while simultaneously removing the rank-one adversary assumption required by their analysis. Moreover, this rate is the same as the known optimal rate for stochastic kernel bandits, and also matches a lower bound from concurrent work up to a

\log T

factor.

Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1

National University of Singapore

\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Minimax Rate Kernel Hilbert Spaces Bandits Regret Loss Function

May 18, 2026stat.ML

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical work has shown promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of Data-driven Algorithm Design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of

\mathcal{O}(s^{1.5}/\sqrt{N})

for the learned multipliers, where

s

is the number of coupling constraints and

N

is the sample size. Second, we provide a minimax lower-bound of

Ω(s/\sqrt{N})

, proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate

Θ(s/\sqrt{N})

. Finally, we extend our framework to the learning-to-warm-start setting, proving that it achieves a fast, minimax-optimal rate of

Θ(s/N)

and establishing a theoretical advantage over direct multiplier prediction.

Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen

Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.

Mixed-Integer Programming Convex Relaxation Minimax Rate Stochastic Gradient Descent Data-Driven

May 17, 2026cs.LG

Calibeating for general proper losses: A Bregman divergence approach

This work introduces a general framework for calibeating based on regret minimization. As compared to Foster and Hart's seminal calibeating work which had specialized treatments of Brier score (squared loss) and log loss, we consider a large family of proper losses that includes

α

-Tsallis losses (for

α\in [1, 2]

) and Lipschitz losses. Our results for Tsallis losses also hold for an unscaled version of Tsallis loss that recovers log loss. Our analysis is oriented around the Bregman divergence view of a proper loss. Technically, our results for the family of Tsallis losses that we consider are U-calibration results, simultaneously obtaining logarithmic regret for all losses in this family while having a weaker dependence on the dimension compared to previous results. Of potential independent interest, we also show a new regret equality for the regret of Be The Regularized Leader. This regret equality holds for general proper losses and itself is based on two results related to online updating formulas for the generalized variance, the latter being a previously introduced generalization of variance based on Bregman divergences.

Maximilian Fichtl, Cristóbal Guzmán, Nishant A. Mehta

Independent researcher · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile · Department of Computer Science, University of Victoria

Bregman Divergences Convex Loss \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Minimax Rate Divergence

May 14, 2026stat.ML

Large Dimensional Kernel Ridge Regression: Extending to Product Kernels

Recent studies have reported

\textit{saturation effects}

and

\textit{multiple descent behavior}

in large dimensional kernel ridge regression (KRR). However, these findings are predominantly derived under restrictive settings, such as inner product kernels on sphere or strong eigenfunction assumptions like hypercontractivity. Whether such behaviors hold for other kernels remains an open question. In this paper, we establish a broad, new family of large dimensional kernels and derive the corresponding convergence rates of the generalization error. As a result, we recover key phenomena previously associated with inner product kernels on sphere, including:

i)

the

\textit{minimax optimality}

when the source condition

s\le 1

;

ii)

the

\textit{saturation effect}

when

s>1

;

iii)

a

\textit{periodic plateau phenomenon}

in the convergence rate and a

\textit {multiple-descent behavior}

with respect to the sample size

n

.

Yang Zhou, Yicheng Li, Yuqian Cheng +1

Department of Statistics and Data Science Tsinghua University Beijing, 100084, China · Department of Mathematical Science Tsinghua University Beijing, 100084, China

Kernel Ridge Regression Kernel Method Minimax Rate Convergence Descent Saturation

May 12, 2026stat.ML

Minimax Rates and Spectral Distillation for Tree Ensembles

Tree ensembles such as random forests (RFs) and gradient boosting machines (GBMs) are among the most widely used supervised learners, yet their theoretical properties remain incompletely understood. We adopt a spectral perspective on these algorithms, with two main contributions. First, we derive minimax-optimal convergence for RF regression, showing that, under mild regularity conditions on tree growth, the eigenvalue decay of the induced kernel operator governs the statistical rate. Second, we exploit this spectral viewpoint to develop compression schemes for tree ensembles. For RFs, leading eigenfunctions of the kernel operator capture the dominant predictive directions; for GBMs, leading singular vectors of the smoother matrix play an analogous role. Learning nonlinear maps for these spectral representations yields distilled models that are orders of magnitude smaller than the originals while maintaining competitive predictive performance. Our methods compare favorably to state of the art algorithms for forest pruning and rule extraction, with applications to resource constrained computing.

Binh Duc Vu, David S. Watson

King’s College London

Tree Ensembles Random Forest Minimax Rate Semi-Supervised Learning Convergence Dataset Distillation

May 8, 2026cs.LG

The Minimax Rate of Second-Order Calibration

We characterize the minimax rate of estimating the second-order calibration error for binary classification, which quantifies whether a higher-order predictor's epistemic-uncertainty estimate matches the conditional variance of the label probability on its level sets. Our key observation is that the sech perturbation kernel, previously used only to enforce smoothness of calibration functions, in fact makes them analytic in a strip of half-width

hπ/2

. Polynomial regression then estimates the calibration error at rate

\tilde{O}(1/\sqrt{n})

, with explicit constants, a qualitative improvement over the

O(n^{-1/4})

rate achievable by bucketing or kernel smoothing. A matching

Ω(1/\sqrt{n})

lower bound establishes minimax optimality up to logarithmic factors. As a corollary, we give the first finite-sample guarantee for second-order Platt scaling, yielding a post-hoc procedure that recalibrates both the mean prediction and the epistemic-variance estimate of any higher-order predictor. Along the way, we provide a bucket-free definition of second-order calibration and relate it quantitatively to the bucketed formulation of Ahdritz et al. [2025]. Our experiments confirm the predicted rate and the quality of the recalibrated uncertainties.

Kamil Ciosek, Banafsheh Rafiee, Sina Ghiassian +1

Spotify

Calibrated Uncertainty Minimax Rate Recalibration

May 7, 2026stat.ML

ConquerNet: Convolution-Smoothed Quantile ReLU Neural Networks with Minimax Guarantees

Quantile regression is a fundamental tool for distributional learning but poses significant optimization challenges for deep models due to the non-smoothness of the pinball loss. We propose ConquerNet, a class of \textbf{con}volution-smoothed \textbf{qu}antil\textbf{e} \textbf{R}eLU neural \textbf{net}works, which yield smooth objectives while preserving the underlying quantile structure. We establish general nonasymptotic risk bounds for ConquerNet under mild conditions, providing minimax guarantees over Besov function classes. In numerical studies, we demonstrate that the proposed approach outperforms standard quantile neural networks at multiple quantile levels, showing improved estimation accuracy and training efficiency across the board, with particularly pronounced advantages at high and low quantiles.

Tianpai Luo, Fangwei Wu, Weichi Wu

Department of Statistics and Data Science Tsinghua University Beijing, 100084, China

Multi-Quantile Regression Rectified Linear Unit Networks Minimax Rate Exponential Family Neural Network Smoothing+2

Apr 30, 2026cs.LG

Shuffling-Aware Optimization for Private Vector Mean Estimation

We study

d

-dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. While minimax-optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. We then establish a minimax lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. Finally, we construct an asymptotically minimax optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism.

Shun Takagi, Seng Pei Liew

LY Corporation, Tokyo, Japan

Random Rotations Decentralized Optimization Minimax Rate

May 28, 2025cs.LG

Fully Offline Reinforcement Learning

Offline RL (ORL) promises safe and sample-efficient deployment but existing methods rely on undocumented online interactions for hyperparameter tuning and lack reliable fully offline estimates of initial online performance. We introduce SOReL, a fully offline Bayesian model-based RL method that learns a posterior over dynamics, estimates policy value via predictive uncertainty, and enables complete offline hyperparameter selection. We further propose TOReL, which extends this tuning framework to arbitrary model-free and model-based ORL algorithms. We provide a regret analysis showing that Bayesian offline RL achieves the minimax-optimal parametric rate under standard regularity conditions. Together, our methods establish a practical and theoretically grounded framework for fully offline RL.

Mattie Fellows, Clarisse Wibault, Uljad Berdica +3

Foerster Lab for AI Research (FLAIR), Department of Engineering Science, University of Oxford · Machine Learning Research Group, Department of Engineering Science, University of Oxford

Model-Based Reinforcement Learning Offline Reinforcement Learning Minimax Rate

Apr 15, 2025math.OC

Wasserstein Distributionally Robust Regret Optimization

Distributionally robust optimization (DRO) is widely used for decision-making under uncertainty, but its adversarial focus on worst-case loss can lead to overly conservative policies. To mitigate this, we study ex-ante Distributionally Robust Regret Optimization (DRRO) with Wasserstein ambiguity sets, designed to balance robustness with upside potential. We develop a theory of Wasserstein DRRO (WDRRO) paralleling Wasserstein DRO. Under smoothness and regularity, WDRRO selects among ERM optima by a first-order gradient-discrepancy rule. If the ERM optimizer is unique, first-order sensitivity vanishes and a second-order expansion governs deviations. For convex quadratics ERM and DRRO coincide for any radius. We then study regimes where these assumptions fail: nondifferentiable max-affine losses, discrete references, and larger radii, where WDRRO can differ from ERM and WDRO. We show that computing WDRRO regret is NP-hard even without bilinear terms. Nevertheless, we develop exact algorithms, a tractable convex relaxation with guarantees, and experiments showing tightness and loss-dependent behavior.

Lukas-Benedikt Fiechtner, Jose Blanchet

Institute of Computational and Mathematical Engineering Stanford University · Institute of Computational and Mathematical Engineering Department of Management Science and Engineering Stanford University

Distributionally-Robust Optimization Robust Optimization Wasserstein Distance Convex Loss Minimax Rate Regret

Jan 18, 2025stat.ML

Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfer

The principal objective of this work is twofold within nonparametric regression settings: (1) to establish the minimax optimal convergence rates for fixed-bandwidth Gaussian kernel spectral algorithms when the true regression function resides in a Sobolev space, and (2) to apply Gaussian spectral algorithms for achieving robust and adaptive transfer learning under concept shift. While minimax optimality of misspecified spectral algorithms has been established, existing guarantees are typically restricted to the non-saturation regime. We demonstrate that the infinite smoothness of fixed-bandwidth Gaussian kernels provides universal robustness to model misspecification by showing that this kernel choice enables any spectral algorithm to attain minimax optimal rates, provided the regularization parameter decays exponentially. This result effectively decouples optimality from the algorithm's inherent qualification. Building on this, we then advocate Gaussian spectral algorithms as powerful components in a learning framework for robust and adaptive transfer. Specifically, we derive the adaptive convergence rate of the excess risk for this framework and show that the rates are optimal up to logarithmic factors. Our results also reveal the impact of the magnitude of the concept shift and the sample size on the generalization error.

Haotian Lin, Matthew Reimherr

Department of Statistics, The Pennsylvania State University.

Minimax Rate Kernel Ridge Regression Spectral Representation Method Kernel Method Transfer Learning Regularization

Jan 13, 2025stat.ML

Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications

Most statistical models for pairwise comparisons, including the Bradley-Terry (BT) and Thurstone models and many extensions, make a relatively strong assumption of stochastic transitivity. This assumption imposes the existence of an unobserved global ranking among all the players/teams/items and monotone constraints on the comparison probabilities implied by the global ranking. However, the stochastic transitivity assumption does not hold in many real-world scenarios of pairwise comparisons, especially games involving multiple skills or strategies. As a result, models relying on this assumption can have suboptimal predictive performance. In this paper, we propose a general family of statistical models for pairwise comparison data without a stochastic transitivity assumption, substantially extending the BT and Thurstone models. In this model, the pairwise probabilities are determined by a (approximately) low-dimensional skew-symmetric matrix. Likelihood-based estimation methods and computational algorithms are developed, which allow for sparse data with only a small proportion of observed pairs. Theoretical analysis shows that the proposed estimator achieves minimax-rate optimality, which adapts effectively to the sparsity level of the data. The spectral theory for skew-symmetric matrices plays a crucial role in the implementation and theoretical analysis. The proposed method's superiority against the BT model, along with its broad applicability across diverse scenarios, is further supported by simulations and real data analysis.

Sze Ming Lee, Yunxiao Chen

Department of Statistics · London School of Economics and Political Science · London WC2A 2AE, United Kingdom

Minimax Rate Ranking Theory

Oct 14, 2024stat.ML

Statistical Properties of Deep Neural Networks with Dependent Data

This paper develops theory for deep neural network (DNN) estimators under dependent data. To provide theory applicable to a variety of DNN-based estimators, I first establish nonasymptotic probability bounds on the theoretical and empirical

\mathcal{L}^{2}

-errors of nonparametric sieve estimators for a general class of estimation problems under possibly nonstationary

β

-mixing data taking values in unbounded sets. I then apply the theory to fully connected and convolutional DNN estimators without bounds or sparsity restrictions on the DNN weights. For both DNN classes, I derive general results when the function to be estimated is Hölder smooth and the data are nonstationary, subgaussian, and

β

-mixing with either exponential or polynomial decay. I then specialize these to nonparametric regression, logistic regression, and quantile regression settings. Under exponential

β

-mixing, the resulting estimators attain the nonparametric minimax rate of Stone (1982) up to logarithmic factors.

Chad Brown

Department of Economics, University of Colorado Boulder, 80309, USA.

Exponential Family Minimax Rate Neural Network High-Dimensional

Sep 13, 2024math.ST

Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent

We provide finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy (

\mathsf{KSD}

) and Wasserstein-2 metrics. Our key insight is that the time derivative of the relative entropy between the joint density of

N

particle locations and the

N

-fold product target measure, starting from a regular initial distribution, splits into a dominant negative part' proportional to $N$ times the expected $\mathsf{KSD}^2$ and a smaller positive part'. This observation leads to

\mathsf{KSD}

rates of order

1/\sqrt{N}

, in both continuous and discrete time, providing a near optimal (in the sense of matching the corresponding i.i.d. rates) double exponential improvement over the recent result by Shi and Mackey (2024). Under mild assumptions on the kernel and potential, these bounds also grow polynomially in the dimension

d

. By adding a bilinear component to the kernel, the above approach is used to further obtain Wasserstein-2 convergence in continuous time. For the case of `bilinear + Matérn' kernels, we derive Wasserstein-2 rates that exhibit a curse-of-dimensionality similar to the i.i.d. setting. We also obtain marginal convergence and long-time propagation of chaos results for the time-averaged particle laws.

Sayan Banerjee, Krishnakumar Balasubramanian, Promit Ghosal

Department of Statistics and Operations Research, University of North Carolina, Chapel Hill. · Department of Statistics, University of California, Davis. · Department of Statistics, University of Chicago.

Wasserstein Distance Convergence Gradient Descent Minimax Rate