{"id":"2f7186fa-e4c2-436d-a70d-eeba7f474195","arxiv_id":"2505.17365","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For online l1-multicalibration, the paper achieves eO(T^{-1/3}) for finite group families and eO(T^{-1/4}) with an offline oracle, improving prior oracle-efficient rates.","lead":"This paper gives faster algorithms for online multicalibration, a fairness-like guarantee that predictions are unbiased across every group in a family. It achieves an improved convergence rate using a new reduction to an online optimization problem, and an oracle-efficient variant requiring only one offline optimization call per round.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The small-separator construction in Lemma 5.2 can fail admissibility for H containing a function that is identically zero on the separator but nonzero elsewhere; the proof's 'remove h WLOG' is invalid outside the transductive setting, so Theorem 1.4's sufficiently-separated branch is not fully…","rationale":"The paper's main contributions survive scrutiny in large part. The OLPO reduction (Theorem 3.1), the finite-class bound via Lin-OLPO (Lemma 4.1, Lemma 4.2), and the covering-based extension (Lemma 4.3, Theorem 1.2) appear internally consistent under their stated assumptions. The halfspace-oracle argument in Appendix A.2 also checks out. The part I find least secure is the oracle-efficient construction in Section 5.2. The FTPL analysis of Theorem 5.1 is standard, but its stability term depends essentially on δ-admissibility, specifically on distinct rows of Γ. Lemma 5.2's admissibility proof has a genuine gap for functions that vanish identically on the separator but are nonzero on off-separator contexts: the sentence 'otherwise we can simply remove h' is valid in the transductive setting, where X is the entire context set, but not in the small-separator setting, where the adversary may play contexts outside X and the removed group can dominate the multicalibration error. This is not a stylistic issue; without distinct rows, the argument that Γ equality implies action equality fails, and the probability bound (20) no longer controls the stability term T2. The result is likely repairable by strengthening the small-separator assumption to separate the full action set H×{±1}^M (equivalently, require every h to be nonzero somewhere in S), or by handling such functions separately, but that strengthening is absent from the statement of Theorem 1.4. I therefore recommend CONDITIONAL rather than REJECT or UNCHANGED: the main ideas are sound, but the sufficiently-separated branch of the central theorem needs an additional condition or a repaired argument.","tokens_in":27339,"tokens_out":25966,"duration_ms":309353,"concrete_test":"Take H={h0,h1}, contexts {1,2}, separator S={1}, with h0(1)=0, h0(2)=1, h1(1)=1, h1(2)=0, and M=2. This satisfies the paper's small-separator definition. Write down Γ from Lemma 5.2: the rows for (h0,θ) are identically zero for all four θ∈{±1}^2, violating Definition 5.2's distinct-row condition. Then run Algorithm 3 against an adversary that alternates rewards for h0 so the best θ alternates (e.g., f_t = e1 on odd rounds and e2 on even rounds, with h0(x_t)=1). With zero perturbation, h0 is governed by unperturbed Follow-the-Leader, so check numerically or analytically whether the regret bound O(DM√T) from Theorem 5.1 holds or whether the stability term T2 becomes linear in T. If it becomes linear, Theorem 1.4's small-separator part requires the stronger condition that every h∈H is nonzero somewhere on the separator (i.e., S separates the full action set H×{±1}^M, as in Dudík et al.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 5.2 constructs Γ_{(h,θ),(j,i)} = h(x_j)θ_i and claims 1-admissibility. The proof for h=h′, θ≠θ′ invokes an index j with h(x_j)≠0 and says 'otherwise we can simply remove h from the hypothesis class without loss of generality.' In the transductive setting X is the full context set, so h≡0 on X is the zero group and removing it does not change K(π_T,H). In the small-separator setting X is only a separator and contexts outside X are allowed. A group h0 with h0=0 on X but h0=1 at some off-separator context is not removable: it can have nonzero ℓ1-multicalibration error and can even be the maximizer in K(π_T,H). For such h0 all rows Γ_{(h0,θ)} are zero, so the distinct-row condition of Definition 5.2 fails. The stability proof in Theorem 5.1 (Lemma B.2) explicitly uses 'rows of Γ are distinct' to conclude Γ_{(h_t,θ_t)}=Γ_{(h_{t+1},θ_{t+1})} implies (h_t,θ_t)=(h_{t+1},θ_{t+1}); when that fails, the T2 stability bound and hence the O(N√T/δ) regret bound do not follow. Thus the sufficiently-separated branch of Theorem 1.4 is not proved for such H; the stated separator condition is weaker than the action-separating condition actually needed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online ℓ1-multicalibration over T rounds. It proposes a reduction (Theorem 3.1) from online multicalibration to an online linear-product optimization problem (OLPO), using a halfspace oracle to convert OLPO actions into prediction distributions. For finite hypothesis classes it designs a no-regret algorithm for a linearized version of OLPO and obtains E[K(π_T,H)] ≤ O(B T^{-1/3} sqrt(log(6T|H|))); an extension via β-covers handles infinite classes (Theorem 1.2). For oracle efficiency, the paper designs a generalized Follow-the-Perturbed-Leader algorithm for OLPO and, under transductive or small-separator contexts with binary-valued H, constructs a perturbation matrix claimed to be 1-admissible and implementable, yielding E[K(π_T,H)] ≤ O(B D T^{-1/4} sqrt(log(T|H|))) with a single offline-oracle call per round.","tokens_in":27629,"tokens_out":16063,"duration_ms":136021,"significance":"The OLPO reduction is a clean and potentially reusable lens: it avoids the indirect ℓ2/ℓ∞ transfer used in prior work and yields the best-known T^{-1/3} rate for finite classes, with a modular oracle-efficient extension. The halfspace-oracle construction is proved rather than assumed, the covering argument for infinite classes is carefully stated, and the paper explicitly compares with Noarov et al. (2025). If the oracle-efficient branch is repaired, the T^{-1/4} oracle-efficient result would improve over the T^{-1/8} bound of Garg et al. (2024) and would replace an online regression oracle with a weaker offline oracle. The two gaps identified below are local to the oracle-efficient branch, but they are load-bearing for Theorem 1.4 as stated.","major_comments":[{"comment":"The proof of 1-admissibility in Lemma 5.2 is incomplete in the small-separator setting. For the case h=h′ and θ≠θ′, the proof requires an index j with h(x_j)≠0 and says 'otherwise we can simply remove h from the hypothesis class without loss of generality.' This is valid in the transductive setting, where X is the full context set and h≡0 on X is the zero function, but it is not valid in the small-separator setting, where X is only a separator and contexts outside X are allowed. A binary group h0 with h0(x)=0 for all x∈X but h0(x)=1 for some context outside X can have nonzero ℓ1-multicalibration error and can even be the maximizer of K(π_T,H); for this h0 every row Γ_{(h0,θ)} is the zero vector, so the distinct-row requirement in Definition 5.2 fails. Lemma B.2 then cannot infer (h_t,θ_t)=(h_{t+1},θ_{t+1}) from equality of the corresponding Γ rows, so the stability bound and hence the regret bound of Theorem 5.1 do not follow for such H. The sufficiently-separated branch of Theorem 1.4 therefore requires an additional assumption (e.g., that X separates every h∈H from the zero function), or a different perturbation construction.","section":"§5.2, Lemma 5.2; Theorem 1.4"},{"comment":"There is an inconsistency in the range of Γ used in the regret proof. Theorem 5.1 and Definition 5.2 allow Γ∈[-B,B]^{(|H|×2M)×N}, but the final steps of the proof in Appendix B.1 use Γ∈[0,1] and α⪰0 to bound E[α·Γ(h_1,θ_1)]≤N√T and to drop the term −α·Γ(h,θ*). The matrix constructed in Lemma 5.2 has entries in {-1,0,1}, so those steps are not justified as written. This is fixable by working with a nonnegative Γ (e.g., by splitting columns according to sign) or by carrying absolute-value bounds, but the current proof does not establish (16) for the stated Γ.","section":"§5.1, Theorem 5.1 and Appendix B.1"}],"minor_comments":[{"comment":"The statement of Lemma 4.1 uses H^B and \tilde B_{1,∞} in the regret expression, while the proof treats a finite enumeration h^(1),...,h^(|H|); the notation should be aligned with the finite hypothesis class setting.","section":"§4.1, Lemma 4.1"},{"comment":"The exponent in the text 'β:=T^{-1/(2+d/2)}' and the resulting additive term appear garbled; the displayed formula should be corrected so that the second term is T^{-1/(2+d/2)} rather than the ambiguous 'T^{-1/2+d/2}'.","section":"§4.2, Application 2"},{"comment":"The sentence 'setting the allowable error in the optimization oracle to ϵ=1/M=1/T^{1/4}' conflicts with Theorem 5.1, whose proof sets ϵ=1/√T; please clarify whether ϵ is the oracle accuracy or the discretization parameter and show explicitly how the chosen ϵ enters the regret bound.","section":"§5.2, final paragraph"}],"recommendation":"major_revision","confidential_remarks":"The small-separator gap in Lemma 5.2 is real and affects Theorem 1.4 as stated, but it is a local fix (strengthen the separator condition or design a different perturbation construction) rather than a refutation of the overall approach. The T^{-1/3} results and the transductive branch appear sound. The Γ-range inconsistency in Theorem 5.1 is also fixable. I recommend major revision with a request to repair the oracle-efficient analysis and to state the exact extra assumption needed for the sufficiently-separated branch."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuinely useful paper. The OLPO reduction is clean, the finite-class eO(T^{-1/3}) rate is correct, and the oracle-efficient eO(T^{-1/4}) result is a real improvement over Garg et al. under the transductive assumption. But the advertised 'sufficiently separated' setting has a gap in Lemma 5.2 that the authors need to close.\n\nWhat's new: a direct l1 approach to online multicalibration, a reduction to online linear-product optimization, a linearization for finite H, and a GFTPL-based algorithm that makes a single call per round to an offline oracle and achieves T^{-1/4}. The proofs of Theorem 3.1 and the finite-class results are sound; the martingale bound and halfspace oracle construction check out. The authors also honestly acknowledge that the finite-class T^{-1/3} rate is obtainable from Noarov et al. and give a fair comparison.\n\nThe soft spot is in Lemma 5.2. The claimed 1-admissibility of Gamma_{(h,theta),(j,i)} = h(x_j) theta_i relies on the assertion that if h(x_j)=0 for all j in the separator, we can 'remove h WLOG.' That is valid in the transductive setting, where X is the full context set and such an h contributes nothing. It is not valid in the small-separator setting: a binary h that is zero on the separator but one on some off-separator context can have nonzero l1-multicalibration error and can be the maximizer in K(pi_T,H). For that h, every row Gamma_{(h,theta)} is the zero vector, so the distinct-row condition of delta-admissibility fails. The stability lemma (B.2) explicitly uses distinct rows to infer action equality from Gamma equality; without that, the T2 bound and the O(N sqrt(T)/delta) regret do not follow. So Theorem 1.4's sufficiently-separated branch, as stated, is not proved. This is a real but localized gap: the transductive branch and the black-box Theorem 5.1 (which assumes an admissible and implementable Gamma) are fine. The fix is likely to strengthen the separator condition (e.g., require every h in H to be nonzero somewhere on X) or to alter the Gamma construction so rows are distinct even for hypotheses vanishing on the separator.\n\nMinor issues: there's a small typo in the Gamma range in the proof of Theorem 5.1, but it does not affect the transductive result. The paper has no empirical claims and the math is checkable.\n\nWho it's for: anyone working on online calibration, multicalibration, omniprediction, or oracle-efficient online learning. It deserves a serious referee. I would recommend acceptance if the separator gap is acknowledged and fixed, or if the theorem is restated to cover only the transductive setting, which is the part that is fully proved.","headline":"Solid reduction-based paper with a real result under transductive contexts; the sufficiently-separated branch has a genuine gap in the admissibility proof.","tokens_in":28267,"tokens_out":4332,"would_cite":true,"duration_ms":34089,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Online $\\ell_1$-multicalibration reduces to an online product-reward game, yielding improved $\\widetilde{\\mathcal{O}}(T^{-1/3})$ rates for finite group families and oracle-efficient $\\widetilde{\\mathcal{O}}(T^{-1/4})$ rates with one…","keywords":["online multicalibration","ℓ1-multicalibration","oracle efficiency","online learning","calibration","Follow-the-Perturbed-Leader","no-regret learning","multigroup fairness"],"falsifier":"Run the oracle-efficient algorithm on a transductive instance with, say, $D=10$ binary groups, $M=8$ forecast bins and $T=10^5$, and check whether the observed $\\ell_1$-multicalibration error tracks $\\widetilde{\\mathcal{O}}(T^{-1/4})$; if it instead tracks the earlier $T^{-1/8}$ rate, the claimed oracle-efficient improvement would be contradicted.","tokens_in":27079,"feed_emoji":"⚖️","tokens_out":16778,"duration_ms":120069,"temperature":0.7,"pith_summary":"The paper establishes that online $\\ell_1$-multicalibration---keeping forecasts unbiased within every group of a large family, not just overall---can be solved directly in the $\\ell_1$ norm, rather than by converting weaker $\\ell_2$ or $\\ell_\\infty$ guarantees. Its central reduction turns the problem into an online game with product-based rewards that the paper calls $\\mathtt{OLPO}$, and from that reduction follow two algorithms: an $\\widetilde{\\mathcal{O}}(T^{-1/3})$ bound for finite group families (and, by covering, for many infinite families), nearly matching the best known rate for plain online calibration, and an $\\widetilde{\\mathcal{O}}(T^{-1/4})$ oracle-efficient bound that needs only one call per round to an offline optimization oracle under transductive or sufficiently separated contexts with binary-valued groups. The oracle-efficient bound improves the previous $\\widetilde{\\mathcal{O}}(T^{-1/8})$ rate for oracle-efficient online multicalibration and replaces an online regression oracle with a simpler offline one. The authors note that a similar finite-class rate could be obtained from a concurrent high-dimensional sequential prediction result; the paper's direct reduction is what also yields the oracle-efficient extension. If correct, the work brings multicalibration for large group families closer to being as cheap as plain calibration, with direct consequences for online omniprediction.","feed_headline":"Multicalibration drops to T^{-1/3}, oracle-efficient T^{-1/4}","feed_subtitle":"A direct reduction to product-reward optimization avoids the ℓ2/ℓ∞ detour and needs one offline call per round.","key_machinery":"The load-bearing object is the reduction to $\\mathtt{OLPO}$, an online game in which each round the learner chooses a group $h$ and a sign vector $\\theta$, the adversary reveals a context and a reward vector $f$, and the learner collects $\\langle \\theta, h(x)\\cdot f\\rangle$. The linearized version $\\mathrm{Lin}$-$\\mathtt{OLPO}$ rewrites this product reward as a linear reward in a higher-dimensional mixed-norm ball, letting the paper combine per-group online gradient descent with multiplicative weights. For oracle efficiency, the key machinery is the generalized Follow-the-Perturbed-Leader template with a perturbation translation matrix $\\Gamma$; the matrix must be $\\delta$-admissible (rows distinct, column entries separated) and implementable (its perturbations expressible as a small number of oracle queries). Lemma 5.2 builds such a $\\Gamma$ from entries $h(x_j)\\theta_i$, which is why the binary and transductive/small-separator assumptions enter, and Theorem 5.1 converts this into a regret bound of $O(B^2 N\\sqrt{T}/\\delta)$, which becomes $\\widetilde{\\mathcal{O}}(D T^{-1/4})$ after the reduction.","core_discovery":"The paper's central claim is that online $\\ell_1$-multicalibration reduces to $\\mathtt{OLPO}$ with essentially no loss: any no-regret algorithm for $\\mathtt{OLPO}$ yields a multicalibration algorithm whose error is bounded by the regret divided by $T$, plus discretization and fluctuation terms (Theorem 3.1). For the improved rate, the paper linearizes $\\mathtt{OLPO}$ into $\\mathrm{Lin}$-$\\mathtt{OLPO}$ by embedding all hypotheses into a higher-dimensional action space constrained by a mixed norm, then combines online gradient descent per hypothesis with multiplicative weights over hypotheses to obtain a regret of order $\\widetilde{\\mathcal{O}}(\\sqrt{T|H|})$, giving $E[K(\\pi_T,H)]=\\widetilde{\\mathcal{O}}(B T^{-1/3})$ for finite $H$. For large or infinite $H$, the paper instead feeds $\\mathtt{OLPO}$ to a generalized Follow-the-Perturbed-Leader algorithm whose perturbation matrix is $\\delta$-admissible and implementable; under transductive or small-separator contexts and binary-valued $H$, this uses a single offline oracle call per round and yields $E[K(\\pi_T,H)]=\\widetilde{\\mathcal{O}}(B D T^{-1/4})$. Infinite families are handled by a $1$-Lipschitz property of the $\\ell_1$-multicalibration error with respect to $H$, so a $\\beta$-cover reduces them to the finite case at additive cost $\\beta$.","pith_inferences":["A consequence the authors leave implicit: the $\\widetilde{\\mathcal{O}}(T^{-1/3})$ rate for finite families is unlikely to be improved without also improving plain online calibration, since multicalibration with a single trivial group is just calibration.","The gap between $\\widetilde{\\mathcal{O}}(T^{-1/3})$ and $\\widetilde{\\mathcal{O}}(T^{-1/4})$ in the oracle-efficient setting comes from the linear dependence on the discretization size $M$ in the generalized Follow-the-Perturbed-Leader regret; if that dependence were reduced to $\\sqrt{M}$, the same framework would plausibly yield the faster rate oracle-efficiently.","The $1$-Lipschitz covering argument is a generic recipe: any group family with known covering numbers would inherit these multicalibration rates once a cover is supplied."],"forward_implications":["Finite group families get $\\widetilde{\\mathcal{O}}(B T^{-1/3})$ $\\ell_1$-multicalibration error, improving on the previous $\\widetilde{\\mathcal{O}}(T^{-1/4})$ bound that came by transferring $\\ell_\\infty$ guarantees.","Oracle-efficient online multicalibration improves from $\\widetilde{\\mathcal{O}}(T^{-1/8})$ to $\\widetilde{\\mathcal{O}}(T^{-1/4})$ while using one offline oracle call per round instead of an online regression oracle.","Infinite families with finite $\\beta$-covers inherit the $T^{-1/3}$ rate up to additive $\\beta$; bounded linear functions on $[0,1]^d$ get error $\\widetilde{\\mathcal{O}}(B d^{1/2} T^{-1/3})$ with runtime $O((B\\sqrt{T})^d)$.","Because $\\ell_1$-multicalibration implies online omniprediction, these rates transfer to omniprediction guarantees for Lipschitz convex losses.","The authors state that the oracle-efficiency analysis should extend to smoothed or $K$-hint data, weakening the transductive/small-separator assumptions."],"supporting_citations":[{"why":"Establishes the $O(T^{-1/3})$ benchmark for online calibration that the paper's finite-class guarantee nearly matches.","marker":"(Foster and Vohra, 1998)"},{"why":"Supplies the no-regret/Blackwell reduction and the halfspace oracle used to convert OLPO actions into forecast distributions.","marker":"(Abernethy et al., 2011)"},{"why":"Provides the generalized Follow-the-Perturbed-Leader framework, including $\\delta$-admissibility, implementability, and the stability and approximation lemmas behind Theorem 5.1.","marker":"(Dudík et al., 2020)"},{"why":"Prior oracle-efficient online multicalibration and omniprediction result with $\\widetilde{\\mathcal{O}}(T^{-1/8})$ rate using an online regression oracle; the paper's Theorem 1.4 improves on it.","marker":"(Garg et al., 2024)"},{"why":"Prior online $\\ell_\\infty$-multicalibration rates whose transferred $\\ell_1$ bound of $\\widetilde{\\mathcal{O}}(T^{-1/4})$ is improved by Theorem 1.1.","marker":"(Gupta et al., 2022)"},{"why":"Introduces multicalibration in the batch setting, defining the fairness objective that the online algorithms inherit.","marker":"(Hébert-Johnson et al., 2018)"},{"why":"Source of the transductive and small-separator context assumptions used to make the oracle implementable.","marker":"(Syrgkanis et al., 2016)"},{"why":"Recent improvement for sequential calibration; defines the best-known plain-calibration rate that Theorem 1.1 nearly matches.","marker":"(Dagan et al., 2025)"}],"fun_headline_variants":["Online ℓ1-multicalibration gets direct T^{-1/3} rate","Oracle-efficient ℓ1-multicalibration achieves T^{-1/4}","Skip ℓ2/ℓ∞ detour: online ℓ1-multicalibration hits T^{-1/3}","Direct reduction to product rewards sharpens multicalibration","Improved ℓ1-multicalibration: T^{-1/3} and oracle-efficient T^{-1/4}"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The advertised oracle-efficient rate rests on binary group functions and on contexts that are either known in advance or separable by a small set, because the perturbation matrix can then be encoded by finitely many context evaluations; if either condition fails, the proof does not deliver the bound.","fun_headline_variants_meta":{"raw":{"variants":["Online ℓ1-multicalibration gets direct T^{-1/3} rate","Oracle-efficient ℓ1-multicalibration achieves T^{-1/4}","Skip ℓ2/ℓ∞ detour: online ℓ1-multicalibration hits T^{-1/3}","Direct reduction to product rewards sharpens multicalibration","Improved ℓ1-multicalibration: T^{-1/3} and oracle-efficient T^{-1/4}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00096,"raw_usage":{"total_tokens":4242,"prompt_tokens":1249,"completion_tokens":2993,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":865,"completion_tokens_details":{"reasoning_tokens":2876}},"tokens_in":865,"tokens_out":2993,"duration_ms":17833,"temperature":1.0,"reasoning_tokens":2876,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:48:34.168922+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the oracle-efficient algorithm on a transductive instance with, say, $D=10$ binary groups, $M=8$ forecast bins and $T=10^5$, and check whether the observed $\\ell_1$-multicalibration error tracks $\\widetilde{\\mathcal{O}}(T^{-1/4})$; if it instead tracks the earlier $T^{-1/8}$ rate, the claimed oracle-efficient improvement would be contradicted.","supporting_citations":[{"cited_title":"Asymptotic calibration","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(T^{-1/3})$ benchmark for online calibration that the paper's finite-class guarantee nearly matches."},{"cited_title":"Blackwell approachability and no-regret learning are equivalent","cited_arxiv_id":null,"evidence_quote":"Supplies the no-regret/Blackwell reduction and the halfspace oracle used to convert OLPO actions into forecast distributions."},{"cited_title":"Oracle efficient online multicalibration and omniprediction","cited_arxiv_id":null,"evidence_quote":"Prior oracle-efficient online multicalibration and omniprediction result with $\\widetilde{\\mathcal{O}}(T^{-1/8})$ rate using an online regression oracle; the paper's Theorem 1.4 improves on it."},{"cited_title":"Pai, and Aaron Roth","cited_arxiv_id":null,"evidence_quote":"Prior online $\\ell_\\infty$-multicalibration rates whose transferred $\\ell_1$ bound of $\\widetilde{\\mathcal{O}}(T^{-1/4})$ is improved by Theorem 1.1."},{"cited_title":"Breaking the T ^ 2/3 barrier for sequential calibration","cited_arxiv_id":null,"evidence_quote":"Recent improvement for sequential calibration; defines the best-known plain-calibration rate that Theorem 1.1 nearly matches."}],"review_version":1}