Sign Betting for Misspecified Regression: Variance Adaptivity and Optimal Approximation

Yinan Li; Han Han; Kwang-Sung Jun

cs.LGOct 14, 2026

Sign Betting for Misspecified Regression: Variance Adaptivity and Optimal Approximation

Authors: Yinan Li, Han Han, Kwang-Sung Jun

Organizations: Department of Computer Science, University of Arizona · GSAI/CSE, POSTECH

Abstract

We study bounded regression under model misspecification, evaluating a function $f$ by its $L_1(P_X)$ distance to the conditional mean $η(x)=\mathbb{E}[Y\mid X=x]$ , rather than the standard $L_2(P_X)$ . This $L_1$ metric is natural for downstream decision problems such as bandits and reinforcement learning. We analyze the min--max estimator of Baraud & Maillard (2025), which we call sign-betting regression. Our main results show that sign-betting regression achieves high-probability $L_1$ oracle inequalities under misspecification. Under realizability, our bound adapts to the average conditional variance and recovers the variance-adaptive rate of Li et al. (2026). We further characterize the optimal universal approximation factor for proper learning by showing that sign betting achieves factor 3, while no proper learner can satisfy a distribution-free, high-probability $L_1$ oracle inequality with a universal approximation factor strictly below 3. We extend the upper-bound analysis beyond finite classes and complement the theory with experiments in synthetic and real-world model-selection tasks.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

$n/d$	Log loss	Squared loss	Sign betting loss
2	$\mathbf{0.05320\pm 0.00082}$	$\mathbf{0.05320\pm 0.00082}$	$\mathbf{0.05320\pm 0.00082}$
4	$0.06629\pm 0.00086$	$0.06629\pm 0.00086$	$\mathbf{0.04490\pm 0.00067}$
8	$0.07960\pm 0.00068$	$0.06068\pm 0.00087$	$\mathbf{0.04605\pm 0.00070}$
16	$0.08142\pm 0.00063$	$0.06937\pm 0.00084$	$\mathbf{0.03945\pm 0.00047}$
32	$0.08411\pm 0.00054$	$0.07850\pm 0.00071$	$\mathbf{0.03714\pm 0.00034}$
64	$0.08879\pm 0.00026$	$0.08428\pm 0.00053$	$\mathbf{0.03538\pm 0.00015}$

Appendix

Table 1: Comparison of average mean absolute error (MAE) under log loss, squared loss, and sign betting loss across varying

n/d

. Reported values are the mean MAE over repeated trials, with

\pm

denoting the standard error. Best results are shown in bold . Sign betting loss achieves the lowest MAE for all tested values of

n/d

, tying with the other methods at

n/d=2

Figure 1: Comparison of average mean absolute error (MAE) obtained under log loss, squared loss, and sign betting loss in the synthetic experiment across varying

n/d

and noise levels

\rho\in\{0,0.02,0.04\}

. Error bars denote the standard error.

Figure 2: Comparison of average test MAE obtained under log loss, squared loss, and sign betting loss in the real-world and LLM experiments across varying validation sizes

n

. Error bars denote the standard error, and dashed horizontal lines indicate the MAE of the best model in each function class.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 579 papers

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
Aug 19, 2026Spencer Compton, Tselil SchrammMinimax Estimation Heteroscedastic Regression
Stanford University
Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem
Mar 10, 2026Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury +2Multi-Armed Bandits Algorithmic Stability
Department of Statistics, Rutgers University · Indian Statistical Institute, Kolkata
Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret
Apr 22, 2026Shubhada Agrawal, Aaditya RamdasRegret Minimization
Indian Institute of Science · Carnegie Mellon University

Aug 19, 2026J/K move · Enter open · S save

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

Spencer Compton, Tselil Schramm

Stanford University

Minimax Estimation Heteroscedastic Regression Linear Regression

Open paper AskPDF arXiv

We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive

n

pairs

(X_i,Y_i)

with labels

Y_i=X_i^\topβ+\varepsilon_i

, where

\varepsilon_i\sim N(0,σ_i^2)

and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples

m

for which

σ_i^2\le1

(larger

m

is easier). We obtain a polynomial-time estimator with rate

\tilde{O}((nd^3/m^4)^{1/6})

when

m\gg d^{3/4}n^{1/4}

, as well as nearly-matching lower bounds. For

d=O(1)

, our estimator achieves error

o(1)

when

m\gg n^{1/4}

, whereas

L_1

regression and other traditional approaches require

m\gg n^{1/2}

. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution

p

, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows

p

. We introduce a (computationally inefficient) adaptive estimator that, so long as

p

is a mixture of

k

symmetric log-concave densities, achieves error comparable with the optimal estimator that knows

p

and has

\tildeΘ(n/k)

samples. For

k=1

, we show that

L_q

regression (with data-dependent

q

) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where

X_i\sim N(0,I_d)

m

unknown samples are noiseless, and the rest have error

\varepsilon_i\sim N(0,1)

. We conjecture that recovering

β

up to error

\ll\sqrt{d/n}

(or exactly) may have an information-computation gap between

m=d+1

and

m\sim d^{3/4}n^{1/4}

, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.

Abstract

Statistical Learning Theory

Explore similar work

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem

Cover meets Robbins while Betting on Bounded Data: ln⁡n\ln nlnn Regret and Almost Sure ln⁡ln⁡n\ln\ln nlnlnn Regret

Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret