Pahan Dewasurendra

Interaction Is Unnecessary for Order-Optimal One-Bit Mean Estimation

Two Dimensions Govern Agnostic Multiclass Transductive Learning

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.

Sharp Root Anti-Concentration for Online Algorithm Configuration

Anytime Last Iterates in Fixed Dimension

Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants

The lifted-selector reduction has an inverse-polynomial radial gap, proved through a quantitative theorem for rational cyclic zonogons, and the results apply to Euclidean zonotope radius and positive-semidefinite binary quadratic maximization parameterized by rank.

Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration

A single, horizon-free algorithm that satisfies the optimal regret rate for every bounded proper loss and also adapt to every smooth proper loss, covering nondifferentiable losses and changes of the active simplex face.

Optimal-Dimension U-Calibration by Bayesian Bootstrap

It is shown that the classical Bayesian bootstrap closes this gap in U-calibration, which asks one online probability fore-caster to have low regret for every bounded proper loss, including losses unknown when the forecasts are made.