pipette
ENEnglish

High-dimensional online calibration from harmonic weights

Maxwell Fishelson, Mehryar Mohri

PreprintDice ser un gran avance

En palabras de los autores

We study the online calibration of multidimensional forecasts over an arbitrary convex set relative to an arbitrary error norm . For forecasting binary outcomes simultaneously (), we give the first algorithm that achieves -calibration in a number of rounds that is polynomial in for every fixed accuracy. It requires rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (), we obtain the same rate, improving the 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 -calibration after rounds, where 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 . This optimality result may be of independent interest.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.