Optimal Lower Bounds for Online Multicalibration

• URL: http://arxiv.org/abs/2601.05245v1
• Date: Thu, 08 Jan 2026 18:59:32 GMT
• Title: Optimal Lower Bounds for Online Multicalibration
• Abstract summary: We prove an $(T2/3)$ lower bound on expected multicalibration error using just three disjoint binary groups.<n>We then turn to lower bounds for the more difficult case of group functions that may depend on context but not on the learner's predictions.
• Score: 9.852468478532652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove tight lower bounds for online multicalibration, establishing an information-theoretic separation from marginal calibration. In the general setting where group functions can depend on both context and the learner's predictions, we prove an $Ω(T^{2/3})$ lower bound on expected multicalibration error using just three disjoint binary groups. This matches the upper bounds of Noarov et al. (2025) up to logarithmic factors and exceeds the $O(T^{2/3-\varepsilon})$ upper bound for marginal calibration (Dagan et al., 2025), thereby separating the two problems. We then turn to lower bounds for the more difficult case of group functions that may depend on context but not on the learner's predictions. In this case, we establish an $\widetildeΩ(T^{2/3})$ lower bound for online multicalibration via a $Θ(T)$-sized group family constructed using orthogonal function systems, again matching upper bounds up to logarithmic factors.

Related papers

• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  We study multicalibration for a sequence of $k$ properties in which each property is identifiable once the preceding properties are fixed.<n>Even with only polylogarithmically many binary groups, achieving multicalibration error $varepsilon$ requires $widetilde(varepsilon-(k+2))$ samples.
  arXiv  Detail & Related papers  (2026-08-04T23:38:54Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  We show that a lower bound holds for every admissible function and follows from a convex relaxation giving stronger bounds.<n>A theory verifies each agent one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point in the interval.
  arXiv  Detail & Related papers  (2026-06-30T06:10:25Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• The Sample Complexity of Multicalibration [9.852468478532652]
  We study the minimax sample complexity of multicalibration in the batch setting.<n>A learner observes $n$ i.i.d. samples from an unknown distribution and must output a predictor whose population multicalibration error, measured by Expected Error (ECE), is at most $varepsilon$ with respect to a given family of groups.<n>We establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted $L_p$ multicalibration metric for all $1 le p le 2$, with optimal $3/p$.
  arXiv  Detail & Related papers  (2026-04-23T17:59:01Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  We prove by a direct reduction from Hstad's theorem that no-time algorithm can exceed the randomassignment ratio $r/q$ by any constant.<n>This threshold coincides with the $ell/m to 0$ limit of the semicircle law governing decoded quantum interferometry.
  arXiv  Detail & Related papers  (2026-03-04T19:26:26Z)
• Efficient Swap Multicalibration of Elicitable Properties [41.64272548564929]
  [NR23] established a surprising connection between multicalibration for an arbitrary property $Gamma$ and property elicitation.<n>In this paper, we generalize multicalibration for an elicitable property $Gamma$ from group membership functions to arbitrary bounded hypothesis classes.
  arXiv  Detail & Related papers  (2025-11-07T01:14:39Z)
• Minimax learning rates for estimating binary classifiers under margin conditions [0.0]
  We study classification problems using binary estimators where the decision boundary is described by horizon functions.<n>We establish upper and lower bounds for the minimax learning rate over broad function classes with bounded Kolmogorov entropy in Lebesgue norms.
  arXiv  Detail & Related papers  (2025-05-15T18:05:10Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  We introduce a novel approach to estimating $m_1(mathbbR2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus.<n>Our experimental results, supported by theoretical justifications of proposed method, demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound.
  arXiv  Detail & Related papers  (2024-11-20T12:07:19Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Neural-network quantum state study of the long-range antiferromagnetic Ising chain [0.771303749110121]
  We investigate quantum phase transitions in the transverse field Ising chain with algebraically decaying long-range (LR) antiferromagnetic interactions. We find that the universal ratio of the SR limit does not hold for $alpha_mathrmLR 2$, implying a deviation in the criticality.
  arXiv  Detail & Related papers  (2023-08-18T17:58:36Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
  We consider the well-studied problem of learning intersections halfspaces under the Gaussian distribution in the challenging emphagnostic learning model. We prove two variants of our lower bound, each of which combines ingredients from Diakonikolas et al. (2021) with (an extension of) a different earlier approach for SQ lower bounds for the Boolean setting.
  arXiv  Detail & Related papers  (2022-02-10T15:34:10Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  We investigate the problem dependent regime in the Thresholding Bandit problem (TBP) The objective of the learner is to output, at the end of a sequential game, the set of arms whose means are above a given threshold. We provide upper and lower bounds for the probability of error in both the concave and monotone settings.
  arXiv  Detail & Related papers  (2021-06-18T15:01:01Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  We show that the optimal regret scales as $widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$, where $T$ is the number of time steps, $d_mathbfu$ is the dimension of the input space, and $d_mathbfx$ is the dimension of the system state. Our lower bounds rule out the possibility of a $mathrmpoly(logT)$-regret algorithm, which had been
  arXiv  Detail & Related papers  (2020-01-27T03:44:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.