Backend
High-dimensional online calibration from harmonic weights
arXiv stat.ML0 views
arXiv:2610.07740v1 Announce Type: new Abstract: We study the online calibration of multidimensional forecasts over an arbitrary convex set $Y\subseteq\mathbb{R}^d$ relative to an arbitrary error norm $\|\cdot\|_{L}$. For forecasting $d$ binary outcomes simultaneously ($Y=[0,1]^d$), we give the first algorithm that achieves $\varepsilon$-calibration in a number of rounds that is polynomial in $d$ for every fixed accuracy. It requires $d^{O(1/\varepsilon)}$ rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting ($Y=\Delta_d$), we obtain the same $d^{O(1/\varepsilon)}$ rate, improving the $d^{\widetilde{O}(1/\varepsilon^2)}$ bounds of Peng and Fishelson et al. Our algorithm is simple: on each round, it outputs a harmonically weighted distribution over harmonically smoothed past outcomes. The same algorithm works for every forecast set and norm. More generally, it achieves $\varepsilon$-calibration after $\exp(O(\gamma(Y,L)/\varepsilon))$ rounds, where $\gamma(Y,L)$ is a geometric parameter defined by a matrix discrepancy problem. The harmonic weights are motivated by the fact that the discrete Hilbert transform matrix achieves the optimal discrepancy up to a universal constant, simultaneously for every $L$. This optimality result may be of independent interest.
Source:https://arxiv.org/abs/2610.07740PreviousNash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability RegretNextTrustworthy Method Comparison with AI Judges: Estimation and Design under Order, Batch, and Aggregation Effects
Related posts
Convert YAML to JSON in the Browser (and JSON to YAML) Without Uploading the File
0dev.to
Vercel agent-desktop: computer use for coding agents through the accessibility tree
0dev.to
WARN Act and Job Search — How to Use the 60-Day Notice Period to Find Your Next Job
0dev.to
Node.js SMS Verification Code: Generating and Sending One-Time Passwords via API Integration
0dev.to
Introducing Takeout Mender – A Free Tool to Recover Metadata from Google Takeout
0dev.to
DeepSeek's Open-Source "Super-Agent" Codes Without Being Asked
0dev.to GitHub