High-dimensional online calibration from harmonic weights

Maxwell Fishelson; Mehryar Mohri

Source-linked AI summary

High-dimensional online calibration from harmonic weights

Maxwell Fishelson, Mehryar Mohri

arXiv:2610.07740v1Oct 6, 2026stat.MLcs.LG

TL;DR

Online calibration of multidimensional forecasts has faced exponential dimension dependence or weaker accuracy dependence in prior guarantees. This paper uses one harmonically weighted algorithm for arbitrary convex forecast sets and error norms, achieving improved horizons in multi-event and multi-class settings and a general geometry-dependent guarantee.

Problem
Standard ε-net approaches require (1/ε)^{O(d)} points and yield calibration horizons exponential in dimension, limiting their use for forecasts with many events or classes.
Source: §1 · p. 2
Method
The algorithm stores harmonically weighted averages of past outcomes and outputs a harmonically weighted distribution over those forecasts.
Source: §1 · p. 3
Results
d^{O(1/ε)} rounds achieve multi-event calibration with polynomial dimension dependence for fixed accuracy, and multi-class forecasting matches this horizon while improving prior accuracy dependence.
Source: §1 · pp. 2–3
Takeaways & Limitations
The same harmonic algorithm works for every convex forecast set and error norm, with its general calibration guarantee governed by a matrix-discrepancy geometric coefficient.
Source: §1 · pp. 3–4
For some norm balls, the general geometric coefficient is Ω(d^{1/3}), so that guarantee cannot provide a polynomial-in-d horizon for every norm ball.
Source: §3.2 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the dimension dependence of online calibration for multidimensional forecasts, presenting one harmonic algorithm for arbitrary convex forecast sets and error norms. It improves calibration horizons in standard forecasting settings and gives a general geometry-dependent guarantee.

Motivation

Standard ε-net methods require (1/ε)^{O(d)} points and yield calibration horizons exponential in dimension, while recent methods trade improved dimension dependence for worse accuracy dependence.For multi-event forecasting, the cited TreeCal bound remains exponential in dimension.Source: §1 · p. 2

Calibration setting

The protocol lets the forecaster announce a finite distribution each round before the adversary selects an outcome, then evaluates calibration by forecast-group average outcomes.The average calibration error is required to be at most ε for every realized transcript.Source: §1 · p. 2

Scope

For sampled calibration, the appendix obtains the same headline rates in expectation..Source: §1 · p. 2

Results

d^{O(1/ε)} rounds achieve multi-event calibration for the first time with polynomial dimension dependence at fixed accuracy; multi-class forecasting matches this horizon.For multi-class forecasting, this improves the accuracy dependence of prior bounds; the paper also improves the Euclidean unit-ball horizon independently of dimension.Source: §1 · pp. 2–3

Algorithm

The algorithm stores harmonically weighted averages of past outcomes, then outputs a harmonically weighted distribution over those stored forecasts.Both operations use weights that decay inversely with age.Source: §1 · p. 3

General guarantee

The general guarantee is governed by a geometric coefficient defined through a matrix-discrepancy objective for the forecast set and error norm.The paper states a general guarantee for any norm unit ball and nonempty compact convex forecast set.Source: §1 · p. 4

Why harmonic weights

The shifted discrete Hilbert transform matrix minimizes the discrepancy objective up to an absolute constant factor over the considered matrix class.This holds simultaneously for every pair of test sets.Source: §1 · p. 4

Analysis

Finite Hilbert matrix moment bounds are the core tool used to establish sublinear calibration and polynomial dimension dependence for many classes of interest.The paper identifies these bounds as its core tool.Source: §1 · p. 4

2 A general matrix formulation

The section formulates a family of forecasting algorithms through matrices P and Q, then shows that harmonic weights are as effective as optimizing over the general family, up to an absolute constant factor.

2 A general matrix formulation

The algorithm uses lower-triangular row-stochastic P and strictly lower-triangular row-stochastic Q to form causal forecasts from past outcomes.Source: §2 · p. 5
Theorem 2.1 states that the matrix-parameterized algorithm's guarantee holds for every outcome sequence.Source: §2 · p. 6
The general algorithm assigns weights to stored forecasts using Q, treating duplicate forecast values as distinct for its upper-bound analysis.Source: §2 · p. 6
Harmonic weights achieve, up to an absolute constant factor, as good a calibration bound as optimizing weights in the general algorithm.Source: §2 · p. 7

3 Harmonic growth and geometric calibration rates

Harmonic weighting yields calibration horizons that are dimension-independent for the Euclidean ball and polynomial in dimension for multi-event and multi-class forecasting at fixed accuracy. The analysis connects these guarantees to finite Hilbert matrix moments and geometric bounds.

3 Harmonic growth and geometric calibration rates

The main algorithm sets H=cKT, using a row-column normalized shifted discrete Hilbert transform matrix, and requires neither L nor T as input.Source: §3 · pp. 7–8
At every fixed accuracy, the bounds give dimension-independent horizons for the Euclidean ball and polynomial-in-d horizons for multi-event and multi-class forecasting.Source: §3 · p. 8

3.1 Higher moments of the finite Hilbert matrix

The finite Hilbert matrix has a 2-norm bound of π/2, and the moment lemma establishes higher-moment bounds that also hold for KT.Source: §3.1 · pp. 9–10

3.2 Geometric bounds

The geometric analysis gives γ(Bd∞) = O(log d), but some norm balls have γ(L,L)=Ω(d^(1/3)), so the general guarantee need not yield polynomial-in-d horizons for every norm ball.Source: §3.2 · pp. 12–13

4 Universal Optimality of the Discrete Hilbert Transform Matrix

The shifted discrete Hilbert transform yields harmonic weights that are universally optimal up to a constant factor for the matrix objective. The proof combines a scalar lower bound with a pulse-based comparison for general test sets.

4 Universal Optimality of the Discrete Hilbert Transform Matrix

Harmonic weights minimize the matrix objective up to an absolute constant factor, simultaneously for every admissible pair of test sets.The constant is independent of the sets, their dimension, and the horizon.Source: §4 · p. 14

4.1 Scalar warm-up

The scalar warm-up shows that sign-compatible matrices of mass M have objective at least proportional to M/log T, while the Hilbert matrix spreads Θ(T log T) mass with O(T) per dyadic level.This matches the lower bound up to constants; embedding the scalar construction gives a dimension-independent baseline for general test sets.Source: §4.1 · pp. 15–16

4.2 Full proof of Theorem 4.2

The full proof turns maximizing vector lists into pulses and uses harmonic averaging to make expected pairings depend on the sign of the index difference, recovering the Hilbert objective.The pulse approximation errors are bounded by r/64 and 3r/64, respectively.Source: §4.2 · pp. 16–18

A Sampled forecasts by repetition

Sampling forecasts does not automatically preserve distributional calibration: the total number of forecast labels matters. A martingale bound controls the sampling cost when labels are predictably created and their number is deterministically bounded.

A Sampled forecasts by repetition

The adversary may observe the announced distribution and past samples, but must choose the current outcome without seeing the current sampled forecast.The guarantee for sampled forecasts is in expectation.Source: A Sampled forecasts by repetition · p. 21
A distribution with small support on each round can still have linear expected sampled error when it creates many singleton forecast buckets across rounds.The example uses T distinct points near 1/2 and independent fair binary outcomes; the expected number of singleton buckets is exponential in T.Source: A Sampled forecasts by repetition · p. 22

A.1 A vector martingale bound for predictable labels

With at most m distinct announced forecast points, each chosen before any sample can select it, the predictable-label lemma bounds the sampling discrepancy under the stated timing condition.The labels may be random and depend on past sampled forecasts.Source: §A.1 · p. 22

A.2 The repeated harmonic algorithm

The repeated harmonic algorithm runs the virtual algorithm in blocks, holding its distribution fixed within each block. Repetition gives an expected sampled-calibration guarantee at specified real horizons.

A.2 The repeated harmonic algorithm

The repeated algorithm holds each virtual forecast distribution fixed for S actual rounds, then uses the block’s average outcome in the virtual run.The virtual algorithm announces at most n distinct forecast points over n rounds.Source: §A.2 · p. 23
At real horizon T = nS, the repeated algorithm’s expected sampled calibration is bounded using the virtual calibration guarantee and a sampling-error term.The stated sufficient horizons use Ccal = 9γ(Y, L).Source: §A.2 · pp. 23–24
For 0 < ε ≤ 1, the corollary gives expected sampled-calibration horizons with asymptotic upper bounds exp(C/ε) for the Euclidean ball and (2d)^{C/ε} for the cube and simplex.C is an absolute constant; the bounds are sufficient horizons of the repeated algorithm.Source: §A.2 · pp. 24–25
These sampled guarantees are expectation statements, not implicit high-probability or anytime guarantees; the dimension-independent Euclidean embedding does not extend to every norm.The Euclidean dimension-independent bound is specific to the displayed embedding argument.Source: §A.2 · p. 25

B.1 Mass identities and normalization corrections

The appendix compares normalized and unnormalized Hilbert matrices, controls errors in recovering the Hilbert objective from pulses, and illustrates the pulse construction in a scalar example.

B.1 Mass identities and normalization corrections

The row-column normalization changes the objective by at most an absolute factor of three, and the comparison need not be exact minimization.For A = B = [-1, 1] and T = 2, the normalized choice has value 5/2 versus the minimum value 2.Source: §B.1 · p. 26

B.2 Recovering the Hilbert objective from pulses

Pulse pairings recover the Hilbert objective with total error at most r/16, combining errors of r/64 from periodization and 3r/64 from replacing pulses by their centers.The pulse centers align with the Hilbert denominators.Source: §B.2 · pp. 26–27

B.3 A visual example of the pulse construction

In the T = 2 scalar illustration, shifted pulses produce a correlation whose odd part is formed by taking (ψ(v) − ψ(−v))/2.The displayed period is [-4, 4], and the functions repeat every 8 units.Source: §B.3 · p. 28

C Fourier maps as an analogue of the SVD

The Fourier maps act like an SVD: they preserve the 2-norm, while their factorization isolates a scalar bound that limits every singular value of K. The appendix also gives geometric bounds that yield calibration guarantees.

C Fourier maps as an analogue of the SVD

The Fourier maps U and V are isometries, preserving the 2-norm like matrices with orthonormal columns.Their columns are orthonormal under the inner product over θ ∈ [0, π].Source: C Fourier maps as an analogue of the SVD · p. 29
The factorization isolates the scalar π/2, with the remaining maps having norm at most one, bounding every singular value of K.Source: C Fourier maps as an analogue of the SVD · p. 29

D Further geometric bounds

If Y ⊆ c + rL and cY ∈ Y, then γ(Y, L) ≤ 2rγ(L, L); the listed geometric upper bounds give calibration guarantees through Theorem 1.2.The appendix covers general ℓp norms, symmetric polytopes, and products of Euclidean balls, and gives a polynomial lower bound for γ for some norms.Source: D Further geometric bounds · p. 30

D.1 General ℓp norms

The appendix bounds the discrete Hilbert transform in ℓq norms and uses those estimates to derive geometric bounds for general ℓp norms. Choosing q as a function of p and d yields a calibration guarantee through Theorem 1.2.

For 1 < q < ∞, the discrete Hilbert transform satisfies ∥K^T x∥_q ≤ Cq*∥x∥_q, where q* = max{q, q/(q − 1)}.Source: §D.1 · p. 30
Applying the scalar estimate coordinatewise and comparing inputs and output columns yields the geometric bound for general ℓp norms.Source: §D.1 · p. 30
Choosing q near max{2, log d} gives q* ≤ C min{p*, log(2d)} and, by Theorem 1.2, a calibration guarantee.The choice is adjusted to p: q = min{p, q0} for p ≥ 2 and q = max{p, q0/(q0 − 1)} for 1 ≤ p ≤ 2, with q0 = max{2, log d}.Source: §D.1 · p. 30

D.2 Symmetric polytopes

For a norm whose unit ball is the symmetric polytope in Theorem D.2, the appendix bounds γ(L, L) by a logarithm of the number of defining functionals. This gives an ε-calibration guarantee for Y = L.

γ(L, L) ≤ C log(2m), and for Y = L, Algorithm 1 achieves ε-calibration when T ≥ (2m)^(C/ε).Source: §D.2 · p. 30
The proof represents the norm as ∥x∥_L = max_i |⟨u_i, x⟩| and applies the scalar estimate to the resulting functionals.Source: §D.2 · p. 31
Choosing q = max{2, log m} keeps m^(1/q) ≤ e and q = O(log(2m)), yielding the bound after taking the supremum over inputs and horizon.Source: §D.2 · p. 31

D.3 Products of Euclidean balls

For products of Euclidean balls, the appendix extends the scalar estimate to vector-valued sequences using Gaussian projections, then applies it in each block. Theorem 1.2 gives ε-calibration, with buckets that are complete joint forecasts.

The scalar estimate extends to finite-dimensional Euclidean-valued sequences by applying it to Gaussian projections and taking expectations.The proof cancels the positive scalar m_q after taking expectations.Source: §D.3 · p. 31
Applying the extended estimate in each block and choosing q = max{2, log k} yields the calibration guarantee through Theorem 1.2.Source: §D.3 · p. 31
The resulting buckets are complete joint forecasts, independently of the dimensions d_j.Source: §D.3 · p. 31

D.4 A polynomial lower bound for the geometric coefficient

D.4 constructs norm balls with a polynomial lower bound on the geometric coefficient, extending the result to every dimension. The bound concerns the guarantee parameter and does not itself lower-bound calibration error.

D.4 A polynomial lower bound for the geometric coefficient

Bourgain’s n-sine construction has size O(n^(2/3)) while its cosine sum reaches n at zero, and translates of the sine sums witness the matrix objective.The construction places these witnesses in a 2n-dimensional function space with a norm ball whose translated evaluations belong to its polar.Source: §D.4 · pp. 31–32
A norm ball yields a geometric-coefficient lower bound growing on the n^(1/3) scale.Theorem D.4 states the result for some norm ball in each dimension d ≥ 2.Source: §D.4 · pp. 31–32
Triangular weights average symmetric partial sums to their limit; the Fourier square-wave identity and zero center of mass lead to the stated inequality.The proof passes to the limit as T tends to infinity before obtaining the bound.Source: §D.4 · p. 32
For odd dimensions, adjoining an interval and extending vectors and functionals by a zero coordinate preserves the objective, yielding the bound in every dimension.The argument uses n ≥ d/3 for d ≥ 2 and adjusts the absolute constant.Source: §D.4 · p. 32
The result rules out a uniform polylogarithmic bound on γ(L,L), but does not by itself establish a lower bound on calibration error.It limits the guarantee in Theorem 1.2, not calibration error itself.Source: §D.4 · p. 32