Second-Order Bounds for $[0,1]$-Valued Regression via Betting Loss

Yinan Li, Sungjoon Yoon, Ethan Huang, Kwang-Sung Jun
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4674-4721, 2026.

Abstract

We consider the $[0,1]$-valued regression problem in the stochastic setting. In a related problem called cost-sensitive classification, Foster and Krishnamurthy (2021) have shown that the log loss minimizer achieves an improved generalization bound compared to that of the squared loss minimizer in the sense that the bound scales with the cost of the best classifier, which can be arbitrarily small depending on the problem instance. Such a result is often called a first-order bound. For $[0,1]$-valued regression, we first show that the log loss minimizer leads to a similar first-order bound. We then ask if there exists a loss function that achieves a variance-dependent bound, also known as a second-order bound, which is a strict improvement upon first-order bounds. We answer this question in the affirmative by proposing a novel loss function called betting loss. Our result is variance-adaptive in the sense that the bound is attained by an algorithm without any knowledge about the variance, which is in contrast to the existing works such as weighted least squares with known variances or those that model label variance or its distribution such as distributional reinforcement learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-li26a, title = {Second-Order Bounds for $[0,1]$-Valued Regression via Betting Loss}, author = {Li, Yinan and Yoon, Sungjoon and Huang, Ethan and Jun, Kwang-Sung}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4674--4721}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/li26a/li26a.pdf}, url = {https://proceedings.mlr.press/v336/li26a.html}, abstract = {We consider the $[0,1]$-valued regression problem in the stochastic setting. In a related problem called cost-sensitive classification, Foster and Krishnamurthy (2021) have shown that the log loss minimizer achieves an improved generalization bound compared to that of the squared loss minimizer in the sense that the bound scales with the cost of the best classifier, which can be arbitrarily small depending on the problem instance. Such a result is often called a first-order bound. For $[0,1]$-valued regression, we first show that the log loss minimizer leads to a similar first-order bound. We then ask if there exists a loss function that achieves a variance-dependent bound, also known as a second-order bound, which is a strict improvement upon first-order bounds. We answer this question in the affirmative by proposing a novel loss function called betting loss. Our result is variance-adaptive in the sense that the bound is attained by an algorithm without any knowledge about the variance, which is in contrast to the existing works such as weighted least squares with known variances or those that model label variance or its distribution such as distributional reinforcement learning.} }
Endnote
%0 Conference Paper %T Second-Order Bounds for $[0,1]$-Valued Regression via Betting Loss %A Yinan Li %A Sungjoon Yoon %A Ethan Huang %A Kwang-Sung Jun %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-li26a %I PMLR %P 4674--4721 %U https://proceedings.mlr.press/v336/li26a.html %V 336 %X We consider the $[0,1]$-valued regression problem in the stochastic setting. In a related problem called cost-sensitive classification, Foster and Krishnamurthy (2021) have shown that the log loss minimizer achieves an improved generalization bound compared to that of the squared loss minimizer in the sense that the bound scales with the cost of the best classifier, which can be arbitrarily small depending on the problem instance. Such a result is often called a first-order bound. For $[0,1]$-valued regression, we first show that the log loss minimizer leads to a similar first-order bound. We then ask if there exists a loss function that achieves a variance-dependent bound, also known as a second-order bound, which is a strict improvement upon first-order bounds. We answer this question in the affirmative by proposing a novel loss function called betting loss. Our result is variance-adaptive in the sense that the bound is attained by an algorithm without any knowledge about the variance, which is in contrast to the existing works such as weighted least squares with known variances or those that model label variance or its distribution such as distributional reinforcement learning.
APA
Li, Y., Yoon, S., Huang, E. & Jun, K.. (2026). Second-Order Bounds for $[0,1]$-Valued Regression via Betting Loss. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4674-4721 Available from https://proceedings.mlr.press/v336/li26a.html.

Related Material