Preprints in learning theory, online learning, bandits, calibration and optimization

Each paper links to its abstract page, full text and source repository.

• A Sharp Adaptation Frontier for Heavy-Tailed Bandits with Unknown Moments
  Heavy-tailed bandit algorithms attain optimal regret when given a finite moment order and its bound. Without either parameter, optimal adaptation is impossible unless one restricts the reward distributions. What can be achieved under the moment condition alone has remained open. We give a sharp answer in the form of a Pareto frontier. Our algorithm takes only an exploration exponent $\rho\in(0,1)$. It combines deterministic forced exploration with a median-of-means empirical leader and uses neither the moment order, its bound, nor a tail-sign condition. If the unknown rewards have $(1+\epsilon)$th absolute moments bounded by $u$, its worst-case regret is, up to explicit arm factors and an arbitrarily slow factor, $u^{1/(1+\epsilon)} T^{1-\rho\epsilon/(1+\epsilon)},$ while its regret on every fixed instance is $O(T^\rho)$. A matching lower bound shows that improving either polynomial exponent worsens the other. Most notably, every fixed $\rho\leq2/3$ attains this frontier simultaneously for all $\epsilon\in(0,1]$. Thus at any point on this common segment, unknown tail order has no further polynomial price beyond unknown scale. This answers the assumption-free rate question posed at COLT 2025 on the maximal common segment and gives the first matching algorithm for the unknown-scale lower tradeoff.
  abstract · PDF · code · DOI
  heavy-tailed bandits, adaptation, moment assumptions, regret, median-of-means, multi-armed bandits
• Anytime Last Iterates in Fixed Dimension
  The standard horizon-free subgradient schedules, $\eta_t\asymp t^{-1/2}$ for convex objectives and $\eta_t\asymp t^{-1}$ under strong convexity, have last-iterate guarantees worse than the optimal rates by a logarithmic factor. Known matching examples use dimension growing with the horizon. We prove that this loss disappears in every fixed dimension for deterministic projected subgradient descent. The key is a pathwise conversion theorem for arbitrary positive and adaptive steps. On any suffix, the terminal objective can exceed the best suffix value by at most twice the suffix trajectory rank times the Lipschitz constant times the largest realized step length. The proof combines last exits from consecutive objective levels with a rank bound for obtuse vectors in a common open halfspace. Combining this conversion with suffix regret yields $O(dDL/\sqrt n)$ for $\eta_t=D/(L\sqrt t)$ on a domain of diameter $D$, and $O(dL^2/(\mu n))$ for both standard strongly convex schedules. Thus their horizon dependence is minimax optimal for every fixed dimension. The result complements recent dimension-free anytime impossibility and sharp horizon-tuned constant-step theory. It also gives data-dependent bounds in terms of trajectory rank and realized, rather than worst-case, step lengths.
  abstract · PDF · code
  last-iterate convergence, anytime guarantees, subgradient method, convex optimization, step-size schedules, suffix bounds
• Closing the Harmonic Gap: Exact Identity Testing for Zipfian Distributions
  Instance-optimal identity testing asks how many samples are needed to test an unknown discrete distribution against a specific known null. Existing characterizations truncate a constant multiple of the testing radius. This is usually harmless, but it creates a polynomial gap for the harmonic null $q_i\propto1/i$, the canonical obstruction highlighted in a 2024 COLT open problem. We give a constant-factor characterization for the full Zipfian class $q_i\asymp1/(Li)$. Let $m_q(\varepsilon)$ be the last index whose strict suffix has null mass at least $\varepsilon$. Throughout the nondegenerate range, $N^\star(q,\varepsilon) =\Theta \left(L\sqrt{m_q(\varepsilon)} \max\{1,(\varepsilon L)^{-2}\}\right),$ where constants depend only on the fixed Zipf envelope. For the exact harmonic law, $L=H_k$ and $m_q(\varepsilon)=\Theta(k\exp(-\varepsilon H_k))$, so $N^\star(q,\varepsilon) =\Theta \left(H_k\sqrt{k e^{-\varepsilon H_k}} \max\{1,(\varepsilon H_k)^{-2}\}\right).$ Thus, for every fixed $\varepsilon\in(0,1/3]$, the answer is $\Theta((\log k)k^{(1-\varepsilon)/2})$. The upper bound combines a coarsened instance-optimal test with one unweighted tail-collision statistic. Its key step is a water-filling inequality: if almost all of a Zipfian tail is deleted, its squared discrepancy cannot fall below the tail's collision mass. The lower bound introduces a graded-thinning prior. Tail coordinate $i$ is retained with probability proportional to $i^{-1/3}$ and inflated when retained. This profile makes the alternatives $\varepsilon$-far while keeping the mixture second moment bounded up to the matching sample size. Beyond settling the harmonic example robustly, the result isolates graded thinning as the mechanism missed by constant-radius truncations.
  abstract · PDF · code
  identity testing, distribution testing, Zipfian distributions, property testing, sample complexity, power laws
• Coded Manifolds Preserve Neural Hardness at Critical Reach
  Does sufficiently low curvature make neural networks easy to learn under the manifold hypothesis? Recent work nearly identified a sharp geometric boundary. It proved exponential hardness on manifolds of reach $O(n^\alpha)$ for every $\alpha<1/2$, while reach $\omega(\sqrt n)$ forces polynomial intrinsic volume and permits interpolation. The critical regime $\Theta(\sqrt n)$ was left open. We close this boundary on the hard side. For every large ambient dimension $n$, we construct a connected closed $C^\infty$ curve in $[0,1]^n$ with reach $\Theta(\sqrt n)$ and a full-support, polynomial-time samplable distribution whose density is within constant factors of arclength. Learning linear-width one-hidden-layer ReLU networks on this distribution from noise-free labels requires $\tau^2\exp(\Omega(n))$ full statistical queries of tolerance $\tau$. Under polynomial-modulus Learning with Rounding, no polynomial-time learner exists even with arbitrary output hypotheses. The construction replaces coordinate repetition by coding. We traverse a reflected Gray code of $\mathbb F_2^m$, embed its messages with an explicit systematic small-bias code, and smoothly round the resulting polygon. Character orthogonality gives a restricted isometry for every sparse signed measure needed by a chord and tangent. Federer's tangent formula then amplifies constant abstract reach to $\Omega(\sqrt n)$. The systematic coordinates preserve a linear Boolean prefix on all but an exponentially small fraction of local pieces, which yields an almost pairwise-independent family of continuous parity networks. This shows that the $\sqrt n$ threshold is a genuine critical point rather than a limitation of the previous construction.
  abstract · PDF · code
  manifold hypothesis, hardness of learning, reach, data manifolds, neural networks, computational lower bounds
• Confidence and Budgets under Honest Data Insertions
  A monotone adversary observes an i.i.d. labeled sample and appends correctly labeled examples. Recent work determined the worst-budget expected error but left the prescribed-budget and high-confidence laws open. We prove two sharp advances. First, for VC dimension $d\geq2$, $n$ clean examples, and exact known budget $m$, the worst-class minimax expected error is at least $c\min \left\{1,\frac dn\left[1+\log \left(1+\frac{\min\{m,n\}}d\right)\right]\right\}.$ Thus exactly $m=n$ honest insertions already realize the full $\Theta(1\wedge(d/n)\log(e+n/d))$ worst-budget penalty. The previous all-learner construction used a much larger budget and gave no interpolation in $m$. The proof introduces reciprocal completion: after a rare disagreement is selected from the clean sample, the adversary draws the missing side from its conditional clean law. The two target orientations then induce exactly the same final multiset while every inserted label remains correct. Second, we determine the worst-budget PAC sample complexity. At $d=1$ it is $\Theta(\varepsilon^{-1}\log(1/\delta))$, with no insertion penalty at any confidence. At every $d\geq2$ it is $\Theta \left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right).$ The dimension-one upper bound follows from a new nested-disagreement argument that gives the exact tail $\mathbb P\{\operatorname{err}>\varepsilon\}\leq(1-\varepsilon)^n$. These results close the high-confidence question and locate a quantitative finite-budget obstruction.
  abstract · PDF · code · DOI
  data insertion, monotone adversary, confidence bounds, sample budgets, robust learning, sample complexity
• Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants
  Input-convex neural networks permit globally tractable minimization over their inputs, so one might expect their global regularity to be tractable in low input dimension. We prove exact and accuracy-sensitive barriers to this expectation. Given a bias-free one-hidden-layer ReLU network $f(x)=\sum_{r=1}^n \operatorname{ReLU}(a_r^\top x)$ with unit positive output weights, deciding whether its global Euclidean Lipschitz constant is at least a rational threshold is NP-complete and W[1]-hard when parameterized by the input dimension $d$. The same holds on the unit ball and with integral first-layer weights having at most nine nonzeros. More sharply, no deterministic multiplicative approximation scheme runs in $g(d)\operatorname{poly}(\mathcal B,1/\varepsilon)$ time unless FPT equals W[1]. Under the Exponential Time Hypothesis, no such algorithm runs in $g(d)(\mathcal B+1/\varepsilon)^{o(d/\log d)}$ time. Thus accuracy cannot have a polynomial dependence separated from dimension. The exact result resolves the Euclidean case of an open problem posed at COLT 2025 and left open by the ICLR 2026 parameterized hardness theory for general two-layer networks. The approximation barrier is specific to generator-presented zonotopes, complementing known $(1/\varepsilon)^{O(d)}$-time schemes and an analogous barrier for halfspace-presented polytopes. Our lifted-selector reduction has an inverse-polynomial radial gap, proved through a quantitative theorem for rational cyclic zonogons. Equivalently, the results apply to Euclidean zonotope radius and positive-semidefinite binary quadratic maximization parameterized by rank. Convexity makes minimization easy, but it does not make global sensitivity fixed-parameter tractable or permit a dimension-separated fully polynomial accuracy guarantee.
  abstract · PDF · code
  Lipschitz constant estimation, neural network certification, parameterized complexity, hardness of approximation, input-convex neural networks, W[1]-hardness
• Curvature Coupling Makes Langevin Bias Condition-Number Sharp
  The unadjusted Langevin algorithm (ULA) has stationary Wasserstein bias at most $6h\sqrt{\kappa\beta d}$ for a potential with strong convexity $\alpha$, smoothness $\beta$, and condition number $\kappa=\beta/\alpha$. Gaussian examples show that the step-size and dimension dependences are necessary, but their first-order bias is only $\sqrt{\operatorname{tr}H}/4$. They do not explain whether the remaining condition-number factor is real. We prove that it is. For every $d\geq4$ and $\kappa\geq8$, we construct an explicit $C^\infty$ potential whose best Hessian bounds are exactly $\alpha$ and $\beta$ and whose stationary bias satisfies $\liminf_{h\downarrow0}\frac{W_2(\widehat\pi_h,\pi)}h \geq c\sqrt{\kappa\beta d}.$ The mechanism is a bounded curvature coupling between one soft and one stiff coordinate. It converts an $O(h)$ perturbation of stiff-coordinate curvature into an $O(h\sqrt\kappa)$ soft-coordinate mean shift. Independent copies give the dimension factor. Thus the worst-case first-order bias is $\Theta(\sqrt{\kappa\beta d})$ under only strong convexity and gradient smoothness. The same family gives a high-accuracy iteration lower bound. For one fixed, bounded scale-free initialization, every constant-step ULA sequence attaining error $\epsilon\downarrow0$ requires $\Omega(\kappa\sqrt d \epsilon^{-1}\log(1/\epsilon))$ iterations. This matches the corresponding upper guarantee, including its initialization logarithm.
  abstract · PDF · code · DOI
  Langevin algorithm, log-concave sampling, asymptotic bias, condition number, discretization error, strong convexity
• Dice Is Quadratic, Jaccard Is Exponential: Convex Calibration of Set Similarities
  Dice and Jaccard are monotone transforms on each prediction–outcome pair, yet their statistically calibrated convex surrogates have radically different dimension. For $s$-label instance-wise prediction, recent work places the convex calibration dimension of Dice/F1 at order $s^2$. We prove that Jaccard loss instead satisfies $2^{s-1}\ \leq\ \operatorname{CCdim}(L^{\rm Jac})\ \leq\ 2^s-1.$ Thus every distribution-free convex calibrated surrogate for example-based intersection over union needs exponentially many prediction coordinates. The score and loss matrices both have exact rank $2^s$, and the loss has affine dimension $2^s-1$. The lower bound is not a rank argument. We construct a full-support outcome law for which exactly $2^{s-1}+1$ reports are Bayes optimal: the empty report and all reports containing one distinguished label. Its boundary form combines an empty-outcome atom with factorial mass proportional to $1/(|A|-1)!$ on sets containing that label. A factorial cancellation makes all active reports tie, while strict positive definiteness of the Jaccard kernel makes their loss columns affinely independent. The feasible-subspace theorem then gives the lower bound. We also give a self-contained strict-definiteness proof by minwise hashing and Möbius inversion, an explicit calibrated upper surrogate, and a regret transfer. The result explains why low-dimensional convex IoU extensions cannot be exactly calibrated without additional assumptions.
  abstract · PDF · code
  convex calibration dimension, Jaccard index, Dice coefficient, surrogate losses, multi-label prediction, set similarity
• Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration
  Can one forecaster attain the optimal regret rate for every bounded proper loss and also adapt to every smooth proper loss? Recent work answered this up to a dimension gap. Its self-concordant perturbation gives roughly $K^{5/4}\sqrt T$ worst-case regret and incurs an additional $\beta\sqrt K\log K$ for $\beta$-smooth losses. We close both gaps with a one-line forecaster. After observing class counts $c_{t-1}$, draw the next prediction from $\operatorname{Dir}(c_{t-1})$, on the face of classes seen so far. This is a fresh Bayesian bootstrap of the outcomes. The analysis rests on an exact identity: averaging any bounded proper loss under $\operatorname{Dir}(\alpha)$ equals a discrete derivative of its Dirichlet-averaged Bayes risk. The identity makes the be-the-perturbed-leader term telescope to a nonpositive Jensen gap. A one-count likelihood ratio then bounds stability by the inverse square root of that class's count. The resulting single, horizon-free algorithm satisfies $\sup_{\ell}\mathbb E\operatorname{Reg}_\ell \leq4\sqrt{S_TT}\leq4\sqrt{KT}, \mathbb E\operatorname{Reg}_\ell \leq\tfrac52\beta(1+\log T) for every \beta-smooth proper \ell.$ Here $S_T$ is the number of observed classes. Known lower bounds show that both rates are optimal in their nontrivial regimes. The proof covers nondifferentiable losses and changes of the active simplex face.
  abstract · PDF · code · arXiv · DOI
  U-calibration, multiclass forecasting, proper losses, follow-the-leader, Dirichlet distribution, smooth losses
• Extrapolation Is an Assumption: Sharp Limits for Pass@k Forecasting
  Repeated sampling can reveal capabilities and risks that are invisible in one language-model attempt, motivating forecasts of pass@$k$ from much smaller response banks. We ask what such data support without a parametric law for task difficulty. With $b$ attempts per task, the count distribution identifies exactly the first $b$ moments of the latent success-probability distribution. We prove that the worst-case diameter of pass@$k$'s identified set is exactly twice the best degree-$b$ uniform approximation error for $x^k$. A theorem of Newman and Rivlin then yields explicit binomial-tail bounds and a sharp extrapolation transition at $k\asymp b^2$. We extend the limit to finite task sets through a Hellinger modulus and to adaptive policies with a per-task cap. We also give two finite-sample confidence intervals: a global polynomial interval that attains the limiting worst-case diameter and a data-adaptive projection interval. At 128 tasks and 78 attempts per task, any honest 95% interval for population pass has expected-length lower bounds $0.276$ and $0.686$ for pass@1000 and pass@10000. In synthetic audits, narrow taskwise Beta intervals have zero coverage under seven nonparametric alternatives. Across 22 public response banks, model-free intervals include every 10,000-response reference but are necessarily wide at distant horizons. Pass@$k$ extrapolation can be useful, but its uncertainty must disclose the structural assumptions that make it possible.
  abstract · PDF · code · DOI
  pass@k, repeated sampling, language model evaluation, extrapolation, binomial tails, forecasting
• Fast Swap-Agnostic Regression
  Swap-agnostic learning compares a forecaster with a different hypothesis on each level set of its predictions. A recent finite-class second-order approachability algorithm attains the sharp $\widetilde O(T^{1/3})$ time exponent. Extending it to infinite classes and optimizing its offset with an oracle were left open. We give a black-box reduction to online square-loss regression. The algorithm maintains one regressor per prediction bucket, locates an adjacent sign crossing with logarithmically many oracle queries, and updates only the sampled bucket. A square-loss identity preserves the comparator's negative quadratic activity. This yields, for any base regret $R$, $\operatorname{SwapReg}_T=O \left(NR(T/N)+T/N^2\right)$ up to loss and confidence factors. Logarithmic-regret regression therefore retains the $T^{1/3}$ exponent for infinite classes. For half-Brier loss and bounded $d$-parameter linear predictors, constrained Online Newton Step gives $\widetilde O(T^{1/3}d^{2/3})$ contextual swap regret. A direct sum of recalibration instances gives a matching $\Omega(T^{1/3}d^{2/3})$ lower bound for a fixed class of pseudodimension $d$. Kernel ridge regression further gives a spectrum-adaptive log-determinant bound for bounded RKHS predictors. For every sequential-entropy exponent $p>0$, fixed convex classes prove that both nonparametric rates are minimax optimal up to logarithmic factors. We also obtain fast canonical-link models and an oracle-efficient offline conversion with excess $\widetilde O((d/m)^{2/3})$.
  abstract · PDF · code · DOI
  swap regret, agnostic learning, regression, omniprediction, proper losses, calibration
• Interaction Is Unnecessary for Order-Optimal One-Bit Mean Estimation
  We resolve the open question of whether interaction is necessary for order-optimal one-bit mean estimation under a finite central moment. Let $\mu\in[-\lambda,\lambda]$ and $\mathbb E|X-\mu|^k\leq\sigma^k$ for fixed $k>1$. We construct a fully nonadaptive protocol whose query list is fixed before any bit is observed and whose sample complexity matches the adaptive one-bit minimax rate in every moment regime. The refinement cost is $(\sigma/\epsilon)^{k/(k-1)}\log(1/\delta)$ for $1<k<2$, $(\sigma/\epsilon)^2\log(\sigma/\epsilon)\log(1/\delta)$ for $k=2$, and $(\sigma/\epsilon)^2\log(1/\delta)$ for $k>2$, plus the optimal $\log(\lambda/\sigma)$ localization cost. The protocol first runs an existing nonadaptive codebook localizer. It then uses only decoding, not new queries, to choose a padded path through a prequeried dictionary of shifted modulo maps. Adjacent modulo remainders have finite-valued differences that are locally constant near the mean. Their variance is therefore charged only to samples that cross a scale-dependent boundary. A dyadic tail identity pays for all scales with one central-moment budget. This removes both the location dependence and the tail aliasing that obstruct global one-shot refinement.
  abstract · PDF · code · DOI
  one-bit quantization, distributed mean estimation, communication constraints, interactivity, minimax estimation, information constraints
• Multiscale Reward Hedging from Correct Demonstrations
  Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward. Existing reward-hedging guarantees consequently assume a finite reward class. We give the first horizon-free guarantee for continuous classes. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy. This yields the simultaneous tail bound $|\{t:\ell_t>2^{-j}\}|\leq \log_2\mathcal N(\mathcal G,2^{-j-1})+j,$ where $\mathcal G$ is the class of optimality-gap functions. Integrating the tails gives cumulative hidden gap bounded by a metric-entropy integral, independently of the number of rounds. Polynomial entropy $(A/\epsilon)^d$ gives $O(d\log A)$ total gap and a fast $O(d/m)$ statistical rate. For bounded linear contextual recommendation, the result is $O(d)$ regret for arbitrary compact menus. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction. Although the general vote can be expensive, it is exactly polynomial-time for one-dimensional Lipschitz parameter curves. Fixed-radius rank-two recommendation takes $O(KT^2)$ time for menus of size $K$. We also prove an $\Omega(d)$ lower bound, low-rank and bounded ReLU-network corollaries, and a robust theorem that adds only the demonstrator's cumulative suboptimality. A reproducible adaptive stress test illustrates the predicted scale adaptation. After factorization, an exact MovieLens audit runs in 1.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated-rating policy and a proper online baseline. The learner uses only action demonstrations and never observes a reward or a loss.
  abstract · PDF · code · arXiv · DOI
  imitation learning, learning from demonstrations, reward ambiguity, multiscale hedging, inverse reinforcement learning, optimality tests
• Near-Optimal Stochastic Autoregression from Full Traces
  How many full trajectories are needed to learn an autoregressive generator whose parameters are shared across time? For unrestricted $d$-dimensional logistic generators, the best known chain-of-thought bound is roughly $d^2\log M/\epsilon$ trajectories at horizon $M$. Whether the natural $d$-dimensional rate is possible was left open. We answer this question affirmatively, up to logarithmic factors. A proper information-theoretic learner achieves trajectory Hellinger risk and final-token squared error at most $\epsilon$ from $O \left(\frac{d\log(Md)\log(1/\epsilon)+\log(1/\delta)}{\epsilon}\right)$ full trajectories, with no norm, margin, mixing, or prompt-distribution assumption. A matching $\Omega((d+\log(1/\delta))/\epsilon)$ lower bound holds already at one step. The proof identifies an observed-path dimension that is much smaller than the complexity of the marginalized final-token map. After exponentiating the logistic weights, the likelihood of one revealed path is a rational function of $d$ positive parameters with degree at most $Md$. A sign-pattern argument gives VC-subgraph dimension $O(d\log(Md))$. A conditional rho-estimator then converts this dimension into a proper Hellinger oracle inequality while canceling the unknown prompt marginal. The argument extends to misspecification, every bounded trajectory statistic, unrestricted multiclass softmax generators, and model selection over unknown memory orders. It also yields a general theorem for shared-parameter autoregressive models with rational local probabilities.
  abstract · PDF · code · DOI
  autoregressive models, chain-of-thought supervision, sample complexity, logistic models, sequence learning, trajectory learning
• No Perfectly Truthful Sequential Calibration Measure
  A calibration measure should assign sublinear error to correct probabilistic forecasts, linear error to a fixed incorrect forecast, and give a forecaster no incentive to misreport its beliefs. Whether these three requirements can coexist under perfect truthfulness has remained open for sequential prediction. We prove that they cannot. Our main structural result shows that every bounded perfectly truthful measure computed from the outcomes and the forecasts observed along the realized path has a tree-additive Bayes risk. This representation requires no continuity, differentiability, strict truthfulness, or downstream decision guarantee. Although the measure itself may be nonsmooth, one fixed report probability avoids all nondifferentiability points across every horizon. At that report, the measure is forced to be a sum of nonnegative one-step proper losses. Concavity then implies that, under fair independent outcomes, this fixed incorrect report has expected error at most twice the truthful error. Completeness makes the latter sublinear, contradicting soundness. This resolves the perfect-truthfulness question posed by Haghtalab et al. and separates sequential evaluation from recent positive results for batch calibration. The boundary is sharp: if the evaluator can inspect the full forecast tree rather than one realized path, a simple squared-count score satisfies perfect truthfulness, completeness, and product soundness simultaneously.
  abstract · PDF · code
  calibration measures, truthfulness, sequential prediction, proper scoring rules, impossibility results, forecasting incentives
• Optimal-Dimension U-Calibration by Bayesian Bootstrap
  U-calibration asks one online probability forecaster to have low regret for every bounded proper loss, including losses unknown when the forecasts are made. For nontrivial $K\geq2$, the optimal worst-case rate is $\Theta( \sqrt{\min\{K,T\}T})$, while the smooth-loss class has minimax time rate $\Theta(\log T)$. A recent simultaneous algorithm attains both time rates but leaves a polynomial gap in $K$. We show that the classical Bayesian bootstrap closes this gap. At round $t$, independently assign exponential weights to the past outcomes and predict their normalized weighted histogram. Equivalently, if $c_{t-1}$ is the vector of past outcome counts, sample $P_t\sim\operatorname{Dirichlet}(c_{t-1})$ on the observed face of the simplex. For every outcome sequence with terminal counts $n_1,\ldots,n_K$, observed support size $m$, and every proper loss in $[-1,1]$, the expected regret is at most $6\sum_{i=1}^K\sqrt{n_i}\leq6\sqrt{mT}\leq6\sqrt{\min\{K,T\}T}.$ For every $\beta$-smooth loss, the same forecasts have regret at most the regret of empirical follow-the-leader plus $(\beta/2)\log T$, and therefore $O(\beta\log T)$ for bounded smooth proper losses. The proof uses three elementary facts: a one-count Dirichlet update has total variation $O(1/\sqrt{c_i})$, size-biasing an exponential weight adds an independent exponential weight, and weighted be-the-leader holds simultaneously for all proper losses. A class-aggregation reduction gives the matching dimension-capped lower bound. The algorithm is loss-agnostic, horizon-free, proper, and minimax-optimal for the worst bounded loss while retaining the minimax-optimal smooth-class time rate.
  abstract · PDF · code
  U-calibration, online forecasting, proper losses, Bayesian bootstrap, Dirichlet distribution, minimax regret
• Pooled Exploration Closes the Distributed Linear-Bandit Gap
  Distributed adversarial linear bandits have two sources of difficulty. A network needs time to mix information, while bandit feedback needs enough collective exploration to identify a $d$-dimensional loss. The best known finite-action guarantee multiplies both costs by $d$. Its lower bound only multiplies the bandit cost by $d$, leaving a factor $\sqrt d$ gap in the communication term. We close this gap. The key is that exploration should stabilize the pooled block estimate, not every local estimate separately. An exponential-potential argument with conditional Bernstein control allows a spanner exploration rate of order $\eta d/N$ across $N$ agents. The previous pointwise analysis requires order $\eta Bd$, where $B$ is the communication block length. A separate leverage lemma shows that the tiny uniform floor already present in the algorithm keeps every communicated spanner coordinate polynomially bounded, so reducing exploration does not weaken gossip. For $K$ actions spanning dimension $r\le d$, spectral gap $\rho$, and horizon $T$, our algorithm communicates $O(r)$ scalars per agent and round and has per-agent regret $\widetilde O \left( \sqrt{\bigl(\rho^{-1/2}+r/N\bigr)T\log K} \right).$ This matches the known lower bound up to logarithmic factors and resolves the finite-action linear-bandit gap. The proof also gives a general mini-batch EXP2 theorem showing that independent agents pool both variance and the exploration needed for exponential stability.
  abstract · PDF · code · DOI
  linear bandits, distributed learning, exploration, regret, collaborative bandits, communication
• Pure Relative Structured Matrix Learning with Square-Root Matvecs
  Let $\mathcal L\subseteq\mathbb R^{n\times m}$ be any known $q$-dimensional linear matrix family, and let an unknown $A$ be accessible only through products $Ax$ and $A^\top y$. A recent result obtains a nearly optimal approximation from $\mathcal L$ in about $\sqrt q$ queries, but incurs factor three and additive error proportional to $\|A\|_F$. Whether sublinear query complexity can give pure $(1+\epsilon)$ relative error was left open. We resolve this problem with a polynomial-time, nonadaptive algorithm. For a Frobenius-orthonormal basis $B_1,\ldots,B_q$, form the basis-invariant partial trace $S_L=\sum_iB_iB_i^\top$. The algorithm queries the leading eigenspace of $S_L$ exactly from the left, then fits the remaining directions from a Gaussian right sketch. If $\lambda_j$ are the eigenvalues of $S_L$, its constant-success query complexity is $\min_s\left\{s+C\left[ \max\{1,\lambda_{s+1}\}\log^2(2q) +\lambda_{s+1}/\epsilon \right]\right\}.$ The transposed profile is also available. Since $\lambda_{s+1}\le q/(s+1)$, every family admits pure relative error with $\widetilde O(\sqrt{q/\epsilon})$ queries, independent of ambient dimensions and $\|A\|_F/OPT$. The key proof is a partial-trace covariance lemma for a Gaussian matrix-valued design. Exact high-leverage queries make its expected Hessian the identity, while the centered regression offset has variance only $O(\lambda_{s+1}OPT^2/k)$. A median construction amplifies success without estimating residual norms. Finally, a symmetric Wishart lower bound for fixed-sparsity approximation yields $\Omega(\sqrt{q/\epsilon})$ adaptive two-sided queries when $q\epsilon$ is bounded below. Thus the universal rate is optimal up to logarithmic factors in this joint regime. We also show that the transformed profile gives pure relative reducible prediction risk under known input and output covariances. For structured positive-definite precisions, it further controls Gaussian KL error and preconditioned condition number.
  abstract · PDF · code · DOI
  matrix-vector queries, relative error approximation, structured matrices, query complexity, randomized linear algebra, spectral estimation
• Select, Do Not Vote: Optimal List PAC Learning and Exact Transduction
  List learning permits a classifier to return $\ell$ labels and counts a prediction as correct when the target appears anywhere in the list. Its realizable sample complexity is characterized qualitatively by the $\ell$-DS dimension $d$, but every known quantitative bound carries list-size dependence beyond $d$. We remove it. For every class of finite $\ell$-DS dimension $d$, a randomized learner uses $O \left(\frac{d+\log(1/\delta)}{\varepsilon}\right)$ samples. The algorithm does not aggregate lists. It samples a logarithmic number of prefix one-inclusion predictors and uses a fresh validation block to select one. This turns a high-probability average-risk inequality into a single list predictor without the $\ell+1$ loss of Top-$\ell$ voting. The rate is minimax sharp, uniformly in $\ell$. The lower bound uses functions with at most $d$ nondefault coordinates over $2\ell+1$ labels. We also solve fixed-design list transduction exactly. If $\mu_\ell$ is maximum excess hyperedge density, optimal randomized risk is $\mu_\ell/m$, while optimal deterministic risk is $\lceil\mu_\ell\rceil/m$. A one-coordinate class separates them by the sharp factor $\ell+1$. This is the list-valued extension of the Hall-complexity characterization for ordinary multiclass transduction. The same excess calculation strengthens the known i.i.d. transductive lower bound by $\ell+1$. List length can still reduce $d$, sometimes dramatically, but it creates no additional polynomial price once $d$ is fixed.
  abstract · PDF · code · DOI
  list learning, PAC learning, DS dimension, transductive learning, one-inclusion graph, sample complexity
• Self-Bounding Regret Matching+ in Potential Games and Product-Simplex Optimization
  Regret matching+ (RM+) is parameter free, scale invariant, and central to large game solving, but its only general individual-regret guarantee grows as $\sqrt{T}$. A recent ICLR result used this envelope to prove that RM+ reaches an $\epsilon$-stationary point of a smooth objective over a product of simplices in $O(\epsilon^{-4})$ iterations, or $O(\epsilon^{-8})$ from the standard zero initialization. We give an exact one-step conservation law for RM+. It states that forward utility gain pays for both squared state motion and growth of the regret-state norm. Norm growth is at most $\sqrt{m-1}$ times forward gain for $m$ actions, and the coefficient is sharp. This yields four results for unmodified RM+. Its regret on any utility path is controlled by centered temporal variation. Its regret is uniformly bounded under alternating play in every finite exact potential game, resolving an open question and making squared activation gaps summable. Both certified lazy and ordinary cyclic play attain an $\epsilon^{-2}$ exponent. On any smooth, possibly nonconcave simplex objective, RM+ finds an $\epsilon$-KKT point in $O(\epsilon^{-2})$ iterations. Most broadly, for a smooth objective over an arbitrary product of simplices, cyclic block RM+ attains the same $O(\epsilon^{-2})$ exponent from arbitrary initialization, with an explicit trajectory-dependent constant. The proof controls the finite objective loss caused by low-state blocks and then self-bounds every block state and the total squared path length. Complete proofs cover zero states, sharpness, common-profile stationarity, and robust gain dominance. Oracle-normalized diagnostics compare RM+ with predictive and smooth extra-gradient variants on graphical potential games and dense nonconvex objectives.
  abstract · PDF · code
  regret matching, potential games, no-regret learning, equilibrium computation, product simplex, convergence rates
• Sharp Pair Selection for Mean Regression
  Suppose a learner may train the empirical mean on two optimally selected examples, with repetition, and is evaluated by squared loss on the full dataset. How much worse can this be than the full mean? This is the first open column in a recent data-selection problem. We determine the exact answer in every dimension: $F(d,2)=1+\max\left\{\frac13,\frac{d-1}{2d}\right\}.$ Thus the sharp factor is $4/3$ for $d\leq3$ and $(3d-1)/(2d)$ for $d\geq4$. The two branches reveal distinct obstructions. A rare point on a line forces the dimension-free term, while a uniform regular simplex forces the dimension term. The proof gives a stronger convex-geometric theorem for distributions on at most $m$ atoms. Its key step is an explicit antithetic distribution over pairs. If one atom has mass at least $1/4$, a star coupling has exactly one third of the original second moment. Otherwise, a complete-graph coupling has a closed-form second moment, and a single Jensen inequality proves that uniform weights are worst. A variance-minimizing Carathéodory reduction then transfers the result to arbitrary finite datasets. This resolves all cases with selection budget two, supplies a short proof of the previously isolated planar case, and separates variance-normalized data selection from radius-normalized approximate Carathéodory bounds.
  abstract · PDF · supplement · code · DOI
  data selection, mean regression, squared loss, approximate Caratheodory, convex geometry, sharp constants
• Sharp Root Anti-Concentration for Online Algorithm Configuration
  Online algorithm configuration needs a local guarantee that a random transition boundary does not cross a short parameter interval. Existing polynomial bounds assume a bounded joint coefficient density and are quadratic in the degree. Recent work asks for natural necessary and sufficient coefficient conditions, polynomial guarantees under independent bounded marginals, and a normalization for Pfaffian boundaries. We address these questions through coefficient flux. For an affine boundary $a(t)+\langle X,u(t)\rangle=0$ with $\|u(t)\|_2=1$, we identify two Radon quantities, a slice density and a tangential first moment. Their maximum is exactly the best root-hitting constant uniform over all normalized affine boundaries. If the coefficient law is dominated by an isotropic log-concave law, both quantities are universally bounded. This gives a dimension-free bound controlled only by the total variation of $a$ and the spherical length of $u$. For monic degree-$d$ polynomials, the resulting joint-density bound is linear rather than quadratic in $d$. For independent coefficients with marginal densities at most $\kappa$ and support radius $R$, a Rogozin–Ball argument gives $O(\kappa R d^{3/2})$, and we construct product laws attaining this rate. Consequently, online losses with random monic transitions have sharp dispersion coefficient $\Theta(\kappa R d^{3/2})$ and $\widetilde O(\sqrt T)$ regret. Marginal density without independence can force a deterministic root. Finally, the normalized feature curve $F/\|F\|_2$ supplies a sufficient Pfaffian normalization and yields general dispersion and regret bounds. For exponential-kernel graph learning, the previously hidden conditioning is exactly controlled by the exponent range.
  abstract · PDF · code · DOI
  anti-concentration, data-driven algorithm configuration, online learning, log-concave distributions, dispersion, piecewise structure
• The Confidence Cost of Pairwise Distribution Learning
  Pairwise conditional access to an unknown distribution returns a draw from the distribution restricted to any requested pair. At constant confidence, this weak oracle is as sample-efficient for labeled total-variation learning as ordinary sampling, up to constants. We show that this equivalence fails at high confidence. For a distribution on $n$ labels, accuracy $\varepsilon$, and failure probability $\delta$, we prove the exact minimax query complexity $\Theta \left(\frac{n\log(1/\delta)}{\varepsilon^2}\right).$ The corresponding ordinary-sampling complexity is $\Theta((n+\log(1/\delta))/\varepsilon^2)$. Thus confidence amplification costs up to a factor $n$ under pairwise access. The upper bound reuses one trajectory of a pairwise-winner Markov chain whose stationary law is the target. Although its worst-case relaxation time is linear in $n$, we prove that its empirical distribution has the i.i.d.-scale stationary risk $O(\sqrt{n/T})$. The proof compares its conductances with a minimum-mass graph. After sorting the target probabilities, this graph has an explicit Helmert eigensystem, and a capped-mass Green-function bound telescopes without any minimum-mass or dynamic-range assumption. A geometric median of independent trajectories gives the high-confidence result. The lower bound uses a heavy label and uniform light labels. Every adaptive pair query then carries only $O(\varepsilon^2/n)$ KL information, which makes the multiplicative confidence cost unavoidable.
  abstract · PDF · code · DOI
  pairwise comparisons, distribution learning, high-probability bounds, confidence, sample complexity, preference learning
• The Exponential KL Boundary in Robust PAC Learning
  Distributionally robust PAC learning under Cressie–Read balls has polynomial sample complexity for every fixed order above one. The Kullback–Leibler endpoint was left open because it amplifies rare events on a different scale. We determine that endpoint. Let $\rho>0$ be fixed. For binary classification with zero-one loss, both realizable and agnostic KL-robust learning have sample complexity $\Theta_{\rho} \left( \frac{e^{\rho/\epsilon}}{\epsilon} \bigl(d+\log(1/\delta)\bigr)\right)$ samples, where $d$ is the VC dimension. The realizable statement is sharp without logarithmic factors. It follows from an exact reduction to ordinary PAC learning at the nominal accuracy $A_{\rho}(\epsilon)\sim e^{-1}\epsilon e^{-\rho/\epsilon}$. The agnostic result requires a different argument. Relative-VC control of ERM loses a factor of order $1/\epsilon$ at this singular endpoint. We combine a recent small-error improper learner with ERM. A new inverse-geometry dichotomy shows that multiplicative comparator slack is harmless exactly where the ERM logarithm is costly, and conversely. Validation between the two candidates gives the same sharp rate as in the realizable case. We also resolve the singular transition from Cressie–Read to KL. If the order is $k=1+\lambda\epsilon/\rho$, then the inverse nominal scale has exponent $(\rho/\epsilon)\log(1+\lambda)/\lambda$. This boundary layer interpolates continuously between KL and every near-KL polynomial regime, and shows that the limits $k\downarrow1$ and $\epsilon\downarrow0$ do not commute.
  abstract · PDF · code · DOI
  distributionally robust learning, Kullback-Leibler divergence, PAC learning, Cressie-Read divergences, sample complexity, robustness
• The List Spectrum of Product Classes
  How many predictions per example are necessary to learn several classification tasks simultaneously? For a class $\mathcal H$, let $K(\mathcal H)$ be the least list size that makes realizable PAC learning possible. Hanneke, Moran, and Waknine asked for $K(\mathcal H_1\otimes\mathcal H_2)$, leaving a gap between $(K(\mathcal H_1)-1)(K(\mathcal H_2)-1)$ and $K(\mathcal H_1)K(\mathcal H_2)$. We close the gap and determine a stronger risk spectrum. For nonempty classes with finite $k_j=K(\mathcal H_j)$, set $M=\prod_j k_j$. If a learner may output $L$ tuple labels, then its optimal worst-case expected realizable error converges to $\left(1-\frac{L}{M}\right)_+.$ Consequently, $K(\bigotimes_j\mathcal H_j)=\prod_jK(\mathcal H_j)$. The result is quantitative at every sample size. Its lower bound is a strong direct-product inequality in terms of the factor learning curves. The proof turns infinite list-DS pseudo-cubes into explicit finite Bayes experiments. On an unseen coordinate, the posterior contains $k_j$ competing labels. A difference of adjacent Bayes list risks lower bounds the $k_j$-th posterior mass. Under independent products, these masses multiply, while a list of size $L$ omits at least $M-L$ cells of the top-posterior grid. This posterior order-statistic argument also shows that optimal weak multiclass accuracies multiply. We complement the list theorem with an exact fixed-marginal tensorization under standard minimax regularity and dimension-dependent rates for uniform and agnostic product learning.
  abstract · PDF · code
  list learning, direct products, product classes, DS dimension, multiclass learning, risk spectrum
• The Missing Horizon in Random Reshuffling
  Random reshuffling now has an upper bound that dominates stochastic gradient descent at every constant step $\eta\leq1/(6L)$ and every finite horizon. Its matching lower bound was left open. We solve this problem for the exact all-inner average used by the upper bound. The answer is not the published horizon-independent stochastic envelope. If $\alpha=\eta nL\leq1$, the fixed-step minimax stochastic error is $\Theta \left(\eta^2nL\sigma_\star^2 \left[K^{-1}+\min\{(\alpha K)^2,1\}\right]\right).$ It decreases, increases, and then plateaus across three horizon regimes. Its minimum occurs at $K\asymp\alpha^{-2/3}$, before the usual mixing scale $\alpha^{-1}$. For $\alpha\geq1$, the law is $\Theta(\eta\sigma_\star^2)$. The upper bound follows from an exact finite-population bridge identity and a dimension-free control of all state memory as a Lipschitz remainder. The lower bound combines a centered common-Hessian bridge with a rectifying piecewise quadratic in two dimensions. An exact telescoping identity explains why common-Hessian quadratics alone miss the eventual floor. Together with the deterministic term, this gives a complete minimax characterization for all horizons and this full step range. Optimizing the step recovers the best known tuned rate up to the unavoidable initial-error cap, while the fixed-step theorem reveals a nonmonotone transient hidden by that rate.
  abstract · PDF · code · DOI
  random reshuffling, finite-horizon analysis, without-replacement SGD, minimax rates, step size, convex optimization
• The Price of Obliviousness in Noisy Linear Reconstruction
  An unknown point $x^\star\in\mathbb{R}^d$ is queried through unit linear functionals, each answered with adversarial additive error at most $\delta$. Recent work determined the adaptive minimax error. Its excess above the infinite-query Jung limit $J_d\delta=\sqrt{2d/(d+1)} \delta$ vanishes doubly exponentially in the number of queries, and it left the nonadaptive game open. We characterize that game. For every fixed $d\geq2$, its minimax excess is $\Theta_d(\delta T^{-2/(d-1)})$. Thus adaptivity changes the convergence law from polynomial to doubly exponential. We also resolve the previously open exponential-budget regime in high dimension. If $\log T/d\to\alpha\in(0,\infty)$, then the nonadaptive minimax error satisfies $\frac{\operatorname{OPT}^{na}_d(T,\delta)}{\delta} \longrightarrow \sqrt{\frac{2}{1-e^{-2\alpha}}}.$ The upper bounds combine spherical coverings with Jung's theorem. The lower bounds use a common transcript that hides every vertex of a suitably rotated and expanded regular simplex. This construction is what makes classical spherical-cap geometry sharp for point reconstruction. Finally, a batched strategy shows that each additional adaptive batch can double the polynomial exponent, interpolating between the two convergence laws.
  abstract · PDF · code
  nonadaptive queries, adversarial noise, linear queries, adaptivity gap, Jung's theorem, query complexity
• The Quadratic Cost of Replicable Distribution Estimation
  Estimating a distribution on $k$ symbols to expected total-variation error $\alpha$ needs $\Theta(k/\alpha^2)$ samples. Under algorithmic replicability, the best known upper bound is $O(k^2\log(1/\rho)/(\alpha^2\rho^2))$. Whether the quadratic alphabet dependence is necessary was left open by Bun et al. We prove that it is. Every $\rho$-replicable estimator with expected error at most $\alpha$ requires $\Omega \left(\frac{k^2}{\alpha^2\rho^2}\right)$ samples, for all sufficiently small universal $\alpha$ and $\rho$. The lower bound holds for arbitrary randomized estimators and matches every polynomial dependence in the known upper bound. Our proof introduces an average-distortion partition principle. Fixing the public randomness turns a replicable estimator into canonical output cells. Expected accuracy does not bound every cell, so bounded-diameter partition arguments do not apply. Instead, we show that cells with low average distortion cover constant measure, that each such cell has exponentially small measure, and that Gaussian-profile isoperimetry forces total boundary $\Omega(\sqrt{k})$. The hard instances form a smooth toroidal family of categorical distributions. Nearby parameters generate statistically indistinguishable samples at scale $\sqrt{k}/(\alpha\sqrt m)$. Thickening all canonical cells to this scale converts their boundary into nonreplicability, yielding the result by coarea.
  abstract · PDF · code
  replicability, distribution estimation, sample complexity lower bounds, total variation distance, reproducibility, algorithmic stability
• The Sharp Tail of Uniform Stability
  Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a $\gamma$-uniformly stable algorithm with loss in $[0,L]$ has generalization gap at most $O \left(\gamma\log(1/\delta) +L\sqrt{\frac{\log(1/\delta)}{n}}\right)$ with probability $1-\delta$. Whether an actual bounded-loss learning algorithm can realize the linear dependence on $\log(1/\delta)$ has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with $n$. The known learning lower bound holds only at constant probability. We close this gap. For every $n$, stability level $\gamma$, and loss bound $L$, we construct one deterministic $\gamma$-uniformly stable learning problem whose tail satisfies, simultaneously for $1\le p\le c n$, $\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,\gamma p+L\sqrt{p/n}\right\} \right)\ge e^{-p}.$ The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order $\gamma p$ without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.
  abstract · PDF · code
  uniform stability, generalization bounds, concentration, high-probability bounds, algorithmic stability, lower bounds
• The Universal Price of Best-Arm Identification
  The static oracle for fixed-budget best-arm identification knows the arm means and selects the allocation with the best error exponent. No adaptive algorithm can match this oracle on every instance when there are at least three arms. How large must the worst-case loss be? For unit-variance Gaussian arms, we determine this price to within an additive constant below $0.2$ for every number $K$ of arms. If $P_K$ is the smallest possible worst-case ratio between the oracle and algorithmic error exponents, then $C_K\leq P_K\leq U_K, 0<U_K-C_K<0.2,$ where both endpoints are explicit sequences and equal $\log K+O(1)$. Thus the exact leading constant in the price of universality is one. The lower bound strengthens a recent impossibility result using a translated equal-gap hard family. The upper bound is constructive. We optimize the batch lengths of a successive-elimination design and prove that its exponent is at least $\Gamma_{so}^\star/U_K$ on every instance. The schedule is exactly minimax within the full class of fixed-weight, one-at-a-time batched elimination designs. The key is a sharp information inequality relating the static oracle to the large-deviation cost of incorrectly eliminating the best arm. Equal-gap active sets are the unique extremizers. The optimized design strictly improves the classical Successive Rejects worst-case ratio for every $K\geq3$.
  abstract · PDF · code · DOI
  best-arm identification, fixed-budget, pure exploration, multi-armed bandits, successive rejects, minimax
• Two Dimensions Govern Agnostic Multiclass Transduction
  In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels. For binary classes, agnostic transductive and PAC learning have the same minimax rate. Whether this extends to multiclass learning was open, especially for unbounded label spaces where uniform convergence can fail. We resolve the question up to logarithmic factors. For every multiclass class $\mathcal H$ with DS dimension $d_{DS}$ and Natarajan dimension $d_{\mathrm N}$, the optimal agnostic transductive excess error satisfies $\widetilde\Theta\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right).$ The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable $d_{DS}/n$ obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic $\sqrt{d_{\mathrm N}/n}$ obstruction. The upper bound uses a random-reservation principle. The learner deliberately ignores a constant fraction of the visible labels, which makes the true test point uniform in a large unseen block. We combine realizable compression, a label-space reduction, and inside-menu agnostic compression across this finite-population split. A new without-replacement multiplicative-weights lemma preserves the fast $d_{DS}/n$ term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.
  abstract · PDF · code · DOI
  transductive learning, multiclass classification, DS dimension, Natarajan dimension, agnostic learning, sample complexity

Full source for every paper, including LaTeX and verification scripts, is at github.com/andotheror.