Pith. sign in

REVIEW 2 major objections 5 minor 71 references

Reweighting Improves Conditional Risk Bounds

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Weighted ERM provably improves conditional risk bounds on large-margin and low-variance regions by a factor gamma/c.

desk verdict The conditional-risk bound and O(1/n) variance-learning rate are real contributions, but the classification weight-estimation theorem targets the wrong conditional mean, so Corollary 1 does not follow as written. read the letter →

arxiv 2501.02353 v1 pith:VKZUNDES submitted 2025-01-04 cs.LG stat.ML

Yikai Zhang , Jiahe Lin , Fengpei Li , Songzhu Zheng , Anant Raj , Anderson Schneider , Yuriy Nevmyvaka This is my paper · ORCID
classification cs.LGstat.ML MSC 68T0562G0862G05
keywords weightedempiricalriskminimizationconditionalexcessBernsteinconditionmarginheteroscedasticregressionselectiveclassificationlocalRademachercomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that empirical risk minimization can be improved on selected sub-regions by multiplying each loss term by a data-dependent weight: the classification margin in classification, and the inverse conditional variance in regression. Under a "balanceable" Bernstein condition, weighted ERM replaces the usual conservative constant $B=1/\gamma$ by $B=1$, yielding conditional excess-risk bounds of order $\varepsilon/(c\,P(\omega^*(x)>c))$ instead of $\varepsilon/(\gamma\,P(\omega^*(x)>c))$. These sub-regions are the large-margin sets and the low-variance sets, and the improvement is a factor $\gamma/c$. The paper also derives an $O(1/n)$ rate for learning the variance function, improving an earlier $O(1/\sqrt n)$ guarantee, and gives a lower-bound construction showing the conditional bound is tight.

What carries the argument

The balanceable Bernstein condition (Assumption 1 of the paper): $$\mathrm{Var}[\omega(x)(\ell(f;z)-\ell(f^*;z))] \le \mathbb{E}[\omega(x)(\ell(f;z)-\ell(f^*;z))].$$ The weight is designed so that the variance-to-mean ratio is $1$, eliminating the conservative $B=1/\gamma$ factor used in standard Bernstein-type analyses. The proofs re-run the local Rademacher complexity machinery of [6] under an $\varepsilon$-additive version of this condition, so that a plug-in estimate $\hat\omega$ can be used in place of $\omega^*$.

What would settle it

For the classification pipeline, fit $\hat\eta$ by squared loss on $\pm 1$ labels under the DGP of Section 5.2 and compute the population minimizer: if it equals $2\eta^*-1$, then $|\hat\eta-1/2|$ does not converge to $\omega^*$, and $\mathbb{E}[(\hat\eta-\eta^*)^2]$ will not shrink to zero as $n$ grows. For the main reweighting bound, compare weighted and unweighted ERM conditional excess risk on $\{\omega^*>c\}$ at fixed sample size: the theory predicts a $\gamma/c$ improvement that should be visible in the risk gap.

Watch

Extended reading notes

Core claim

The central claim is that, for losses satisfying a balanceable Bernstein condition, the weighted ERM estimator that minimizes $\sum_i \omega(x_i)\ell(f;z_i)$ achieves conditional excess risk $$\mathbb{E}_z[\ell(\hat f;z)-\ell(f^*;z)\mid \omega^*(x)>c] \le \frac{\varepsilon}{c\,P(\omega^*(x)>c)}$$ with high probability, improving on the standard ERM bound by the factor $\gamma/c$. The weight $\omega^*$ is the margin $2P(y=f^*(x)\mid x)-1$ in classification and $1/\sigma^{2*}(x)$ in regression. The improvement comes from balancing the Bernstein inequality as $\mathrm{Var}[\omega^* h] \le \mathbb{E}[\omega^* h]$, which removes the $1/\gamma$ multiplier from the variance-to-mean bound. In classification the paper proves the conditional bound is minimax-optimal via a matching lower bound; in regression it proves the variance function can be estimated at rate $O(1/n)$.

Load-bearing premise

The end-to-end result assumes a weight estimate $\hat\omega$ with $\mathbb{E}[(\hat\omega-\omega^*)^2]\le\varepsilon$ can be obtained at sample size $O(d\log(1/\varepsilon)/\varepsilon)$; for classification, the paper constructs $\hat\omega=|\hat\eta-1/2|$ where $\hat\eta$ minimizes squared loss on $\pm 1$ labels, and that estimator actually converges to $|2\eta^*-3/2|$, not to the margin $\omega^*=2|\eta^*-1/2|$, so the stated derivation of the classification weight estimate is the load-bearing step that needs repair.

Editorial extensions

If this is right

  • In classification, with $\tilde\Theta(1/\varepsilon)$ samples, the weighted ERM bound on the large-margin region $\{\omega^*(x)>c\}$ is $\varepsilon/(c\,P(\omega^*(x)>c))$ versus $\varepsilon/(\gamma\,P(\omega^*(x)>c))$ for ERM; whenever $c>\gamma$ this is a strict improvement.
  • Under the low-margin diminishing condition $P(\omega^*(x)\le c)\,c^2\le\varepsilon$, the unconditional excess risk bound becomes $\varepsilon/c$, a $\gamma/c$ improvement over standard ERM.
  • In heteroscedastic regression, weighted ERM attains $\mathbb{E}_x[(1/\sigma^{2*}(x))(\hat f(x)-f^*(x))^2]\le\varepsilon$ with $\tilde\Theta(1/(\gamma\varepsilon))$ samples, whereas ERM needs $\tilde\Theta(1/(\gamma^2\varepsilon))$ samples; the gain is again a factor $1/\gamma$.
  • The variance function $\sigma^{2*}(x)$ can be learned at rate $O(1/n)$ through negative log-likelihood estimation, improving over the earlier $O(1/\sqrt n)$ bound and making the variance-estimation step no harder than learning the mean function.
  • The lower-bound construction shows that the conditional excess-risk bound for weighted ERM on $\{\omega^*(x)>c\}$ is tight among all estimators, so the improvement over ERM is not an artifact of a loose analysis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The balanceable-condition template suggests a soft-abstention view: instead of hard-excluding low-margin points, continuous down-weighting by the margin could yield similar selective gains while keeping some coverage; the paper draws this analogy but does not analyze the coverage-versus-risk trade-off in detail.
  • The claimed $O(1/n)$ variance-learning rate should extend to other NLL-based heteroscedastic models satisfying the same bounded-residual condition; a natural stress test is to add misspecification and check whether the rate degrades to $O(1/\sqrt n)$.
  • A corrected margin estimator for the classification pipeline would regress on $(y+1)/2\in\{0,1\}$, whose population minimizer is exactly $\eta^*(x)$, or would directly form $|2\hat\eta(x)-1|$ from a calibrated probability estimate; using such an estimator would make the end-to-end classification result follow from the paper's own equations.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies weighted empirical risk minimization in which each sample's loss is multiplied by a data-dependent weight, and it proves conditional excess-risk bounds on sub-regions where the weight is large. In binary classification the weight is the margin function and the sub-region is the large-margin set; in heteroscedastic regression the weight is the inverse conditional variance and the sub-region is the low-variance set. The main theoretical results are oracle-weight bounds (Theorems 4.1 and 4.5), weight-estimation results (Theorems 4.3 and 4.6), a general balanceable-Bernstein-condition result (Theorem 4.7), a lower bound for classification (Theorem 4.4), and an ERM-versus-weighted-ERM construction (Theorem 4.2). The paper reports an improved constant by a factor of order gamma/c in the selected regions and an O(1/n) rate for learning the variance function, together with synthetic experiments.

Significance. If the results were fully valid, the paper would make a useful contribution: the local Rademacher analysis under an epsilon-additive Bernstein condition is a reasonable technical tool, the oracle-weight inequalities in (6) and (13) are clean algebraic verifications, and an O(1/n) sample complexity for estimating the inverse variance function would improve on the earlier O(1/sqrt(n)) result in [65]. The conditional-risk improvement in high-margin and low-variance regions is a genuinely interesting refinement of standard ERM bounds. However, the advertised end-to-end classification guarantee currently rests on a weight-estimation theorem that does not estimate the object it claims to estimate under the paper's own +/-1 label model. This makes the classification application, which is central to the abstract and Table 1, not established as written, while the oracle-weight and regression-side analyses remain credible.

major comments (2)
  1. [Section 4.1, Theorem 4.3, Corollary 1, Appendix A.5] Theorem 4.3 estimates the wrong conditional mean. Under DGP (5), y takes values in {-1,1} with P(y=1|x)=eta*(x), so E[y|x]=2eta*(x)-1, not eta*(x). The squared-loss population minimizer over eta in [0,1] is therefore the projection of 2eta*(x)-1 onto [0,1], not eta*(x). The proof in Appendix A.5 asserts 'as eta*(x) := E[y]', which is false for this label model. Consequently the claimed bound Ex[(b_eta-eta*)^2] <= epsilon is not valid, and b_omega=|b_eta-1/2| does not approximate the margin. For a constant eta*=0.8, b_eta converges to 0.6, so b_omega converges to 0.1, whereas the margin omega*=2|eta*-1/2| is 0.6. Corollary 1, which combines Theorem 4.1 with Theorem 4.3, therefore does not follow from the paper's own equations, and the classification entries in the abstract and Table 1 are not supported.
  2. [Section 4.1 and Table 1; Appendix A.1] The definition of the margin function is internally inconsistent by a factor of two. Under the +/-1 label model in (5), the correct margin is omega*(x)=2P(y=f*(x)|x)-1=2|eta*(x)-1/2|=|2eta*(x)-1|, and this is what the derivation in Appendix A.1 actually yields. However, the text after (5) and in Theorem 4.3 defines omega*=|eta*-1/2|, and Theorem 4.3 constructs b_omega=|b_eta-1/2|. The two conventions are not equivalent. Even if the label-encoding issue in Theorem 4.3 were repaired by using {0,1} labels, the proposed b_omega=|b_eta-1/2| would converge to |eta*-1/2|, which is half of the margin stated in Table 1. The paper needs a single consistent definition of omega* and a weight estimator that targets that definition.
minor comments (5)
  1. [Appendix A.5] The proof of Theorem 4.3 also asserts Var[Delta R,eta] <= 2E[Delta R,eta] without a displayed calculation. Under the +/-1 label model, |y-eta(x)| can be as large as 2, and the variance-to-mean ratio is not bounded by 2 in the way claimed; this is part of the same label-encoding problem and should be corrected explicitly.
  2. [Theorem 4.4 proof, Appendix A.6] In the displayed decomposition of the excess risk, the first term should be multiplied by P[x in X1], not P[x in X2]; as printed, the decomposition is arithmetically wrong even before the subsequent lower-bound argument.
  3. [Section 5.2] The classification experiments estimate the margin using cross-entropy, whereas Theorem 4.3 is stated for squared-loss minimization. The experiments therefore do not directly validate the theoretical weight-estimation result, and the mismatch should be acknowledged or the theory extended to the cross-entropy procedure.
  4. [Theorem 4.6 and Appendix A.9] The final step of the proof of Theorem 4.6, converting the excess negative-log-likelihood bound into the claimed L2 bound on (1/b_sigma^2 - 1/sigma*^2), is only sketched with the phrase 'one can leverage' an inequality. Since the sample-complexity statement is advertised as an O(1/n) improvement over [65], the conversion should be written out with all constants, including the dependence on c3, gamma, and the bound on xi.
  5. [Notation in Theorem 4.6] The displayed sample complexity contains the artifact 'T1T 3 2', which appears to mean T1 T2^3, and the statement mixes eF, eG with the stated dP(F), dP(G) without defining the resulting constants. This should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the weighted-ERM bounds are derived from an external local-Rademacher analysis with direct variance algebra, and the self-cited prior work is used as a benchmark, not as a load-bearing premise.

full rationale

The main bounds (Theorems 4.1, 4.5, 4.7) are obtained by verifying a balanceable Bernstein condition through direct algebraic inequalities (e.g., eqs. (6), (13), Appendix A.1, A.3) and then applying the external local Rademacher machinery of Bartlett, Bousquet, and Mendelson [6]. The weight function is assumed close to the oracle in squared error, and no fitted constant is later renamed as a prediction. The weight-estimation theorems (4.3 and 4.6) are standard squared-loss/NLL regression problems solved against the same DGP; their conclusions are not assumed by the risk-bound theorems being combined. The citations to the authors' own work are not load-bearing: [65] is a benchmark for the claimed O(1/n) variance-learning rate, and [66] is cited alongside [29] for a standard Chernoff-type lemma whose proof is included. One non-circular correctness caveat should be noted: in Appendix A.5, the proof uses 'as η*(x) ≜ E[y]', which is inconsistent with the paper's DGP (5) where y|x ∈ {-1,1} and E[y|x] = 2η*(x) - 1; this makes Corollary 1's classification end-to-end guarantee unsupported as written, but this is an internal target mismatch rather than a circular reduction of the result to its inputs.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No fitted constants are tuned to data in the proofs; the threshold c is a user-chosen evaluation level. The key structural input is Assumption 1, verified algebraically for the two concrete settings. The paper assumes well-specified classes and, for the variance-learning theorem, a bounded normalized residual condition. No new physical or mathematical entities are introduced; the balanceable Bernstein condition is a modeling condition rather than an invented entity.

free parameters (1)
  • region threshold c = user-specified, e.g., 0.1
    The conditional region {omega*(x)>c} and the low-margin diminishing condition P(omega*(x)<=c)c^2<=epsilon depend on this hand-chosen threshold. It is not fitted to data and any c>0 is allowed, but the improvement factor gamma/c varies with it.
assumptions (4)
  • domain assumption Assumption 1: bounded, Lipschitz loss; semi-random noise label; balanceable Bernstein condition Var[omega(x)h(x)] <= E[omega(x)h(x)] for the true weight omega*
    Introduced in Section 4.3 and verified algebraically for 0-1 classification loss and squared regression loss. It is the core structural assumption of the paper.
  • domain assumption Well-specified setting: f* in F, eta* in G, sigma^2* in G (or in eF x eG), so the target lies in the hypothesis class
    Stated in Sections 4.1 and 4.2; the paper explicitly limits itself to well-specified settings in Section 6.
  • standard math Local Rademacher complexity and Bernstein machinery of Bartlett et al. [6] and Massart & Nedelec [39], including the sub-root fixed-point solution
    Used throughout the proofs as external benchmark results for fast-rate ERM analysis.
  • ad hoc to paper Bounded normalized residual condition (y-f(x))^2/sigma^2(x) <= 4c2^2 imposed in Theorem 4.6 to make the NLL loss uniformly bounded
    Imposed to ensure the negative log-likelihood loss is uniformly bounded so the local Rademacher analysis applies; this restricts the hypothesis classes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reweighting Improves Conditional Risk Bounds." pith.science (2026). https://pith.science/paper/VKZUNDES

@misc{pith2026250102353,
  author       = {Pith},
  title        = {Pith review of: Reweighting Improves Conditional Risk Bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VKZUNDES}},
  note         = {Machine review of arXiv:2501.02353}
}
read the original abstract

In this work, we study the weighted empirical risk minimization (weighted ERM) schema, in which an additional data-dependent weight function is incorporated when the empirical risk function is being minimized. We show that under a general ``balanceable" Bernstein condition, one can design a weighted ERM estimator to achieve superior performance in certain sub-regions over the one obtained from standard ERM, and the superiority manifests itself through a data-dependent constant term in the error bound. These sub-regions correspond to large-margin ones in classification settings and low-variance ones in heteroscedastic regression settings, respectively. Our findings are supported by evidence from synthetic data experiments.

Figures

Figures reproduced from arXiv: 2501.02353 by the authors.

Figure 1
Figure 1. Regression setting: underlying true data, estimates from ERM and weighted ERM, and the selective risk [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Classification setting: underlying true data, estimates from ERM and weighted ERM and the selective risk [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 66 canonical work pages

  1. [65]

    Risk bounds on aleatoric uncertainty recovery

    Zhang, Y., Lin, J., Li, F., Adler, Y., Rasul, K., Schneider, A., and Nevmyvaka, Y. Risk bounds on aleatoric uncertainty recovery . InInternational Conference on Artificial Intelligence and Statistics, pp. 6015–6036. PMLR, 2023

    work page 2023

  2. [1]

    Empirical risk minimization under random censorship

    Ausset, G., Cl´emenc ¸on, S., and Portier, F. Empirical risk minimization under random censorship. Journal of Machine Learning Research, 2022

    work page 2022

  3. [2]

    H-consistency bounds for surrogate loss minimizers

    Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, pp. 1117–1174. PMLR, 2022

    work page 2022

  4. [3]

    Self-concordant analysis for logistic regression

    Bach, F. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384–414, 2010

    work page 2010

  5. [4]

    Bartlett, P. L. and Mendelson, S. Empirical minimization. Probability theory and related fields, 135(3): 311–334, 2006

    work page 2006

  6. [5]

    Bartlett, P. L. and Wegkamp, M. H. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9(8), 2008

    work page 2008

  7. [6]

    L., Bousquet, O., and Mendelson, S

    Bartlett, P. L., Bousquet, O., and Mendelson, S. Local rademacher complexities. The Annals of Statistics, 33(4):1497–1537, 2005

    work page 2005

  8. [7]

    Theory of classification: A survey of some recent advances

    Boucheron, S., Bousquet, O., and Lugosi, G. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323–375, 2005

    work page 2005

Show all 71 references
  1. [8]

    and Zhivotovskiy, N

    Bousquet, O. and Zhivotovskiy, N. Fast classification rates without standard margin assumptions. Information and Inference: A Journal of the IMA, 10(4):1389–1421, 2021

    2021

  2. [9]

    Introduction to statistical learning theory

    Bousquet, O., Boucheron, S., and Lugosi, G. Introduction to statistical learning theory . InSummer school on machine learning, pp. 169–207. Springer, 2003

    2003

  3. [10]

    C., Talbot, N

    Cawley , G. C., Talbot, N. L., Foxall, R. J., Dorling, S. R., and Mandic, D. P. Heteroscedastic kernel ridge regression. Neurocomputing, 57:105–124, 2004

    2004

  4. [11]

    On optimum recognition error and reject tradeoff

    Chow, C. On optimum recognition error and reject tradeoff. IEEE Transactions on information theory, 16 (1):41–46, 1970

    1970

  5. [12]

    Sample selection bias correction theory

    Cortes, C., Mohri, M., Riley, M., and Rostamizadeh, A. Sample selection bias correction theory. In Algorithmic Learning Theory: 19th International Conference, ALT 2008, Budapest, Hungary, October 13-16,

    2008

  6. [13]

    Learning bounds for importance weighting

    Cortes, C., Mansour, Y., and Mohri, M. Learning bounds for importance weighting. Advances in neural information processing systems, 23, 2010

    2010

  7. [14]

    Learning with rejection

    Cortes, C., DeSalvo, G., and Mohri, M. Learning with rejection. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pp. 67–82. Springer, 2016

    2016

  8. [15]

    J., Chen, J., and Li, H

    Daye, Z. J., Chen, J., and Li, H. High-dimensional heteroscedastic regression with an application to eqtl data analysis. Biometrics, 68(1):316–326, 2012

    2012

  9. [16]

    Distribution-independent pac learning of halfspaces with massart noise

    Diakonikolas, I., Gouleakis, T., and Tzamos, C. Distribution-independent pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019

    2019

  10. [17]

    H., and Tzamos, C

    Diakonikolas, I., Park, J. H., and Tzamos, C. Relu regression with massart noise. Advances in Neural Information Processing Systems, 34:25891–25903, 2021

    2021

  11. [18]

    Dudley , R. M. Uniform central limit theorems, volume 142. Cambridge university press, 2014

    2014

  12. [19]

    El-Yaniv, R. et al. On the foundations of noise-free selective classification. JMLR, 11(5), 2010

    2010

  13. [20]

    Optimal strategies for reject option classifiers

    Franc, V., Prusa, D., and Voracek, V. Optimal strategies for reject option classifiers. Journal of Machine Learning Research, 24(11):1–49, 2023

    2023

  14. [21]

    Maximum likelihood estimation is all you need for well-specified covariate shift

    Ge, J., Tang, S., Fan, J., Ma, C., and Jin, C. Maximum likelihood estimation is all you need for well-specified covariate shift. arXiv preprint arXiv:2311.15961, 2023

    2023 arXiv

  15. [22]

    and Dougherty , E

    Hanczar, B. and Dougherty , E. R. Classification with reject option in gene expression data.Bioinformatics, 24(17):1889–1895, 2008

    2008

  16. [23]

    Theoretical foundations of active learning

    Hanneke, S. Theoretical foundations of active learning. Carnegie Mellon University , 2009

    2009

  17. [24]

    Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik- Chervonenkis dimension

    Haussler, D. Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik- Chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217–232, 1995

    1995

  18. [25]

    and Wegkamp, M

    Herbei, R. and Wegkamp, M. H. Classification with reject option. The Canadian Journal of Statistics/La Revue Canadienne de Statistique, pp. 709–721, 2006. 16

    2006

  19. [26]

    and Li, L

    Jiang, N. and Li, L. Doubly robust off-policy value evaluation for reinforcement learning. InInternational Conference on Machine Learning, pp. 652–661. PMLR, 2016

    2016

  20. [27]

    Exponential tail local rademacher complexity risk bounds without the bernstein condition

    Kanade, V., Rebeschini, P., and Vaskevicius, T. Exponential tail local rademacher complexity risk bounds without the bernstein condition. arXiv preprint arXiv:2202.11461, 2022

    2022 arXiv

  21. [28]

    and Gal, Y

    Kendall, A. and Gal, Y. What uncertainties do we need in bayesian deep learning for computer vision? Advances in neural information processing systems, 30, 2017

    2017

  22. [29]

    and Young, N

    Klein, P. and Young, N. E. On the number of iterations for dantzig–wolfe optimization and packing- covering approximation algorithms. SIAM Journal on Computing, 44(4):1154–1172, 2015

    2015

  23. [30]

    and Zhivotovskiy, N

    Klochkov, Y. and Zhivotovskiy, N. Stability and deviation optimal risk bounds with convergence rate o(1/n). Advances in Neural Information Processing Systems, 34:5065–5076, 2021

    2021

  24. [31]

    and Langer, S

    Kohler, M. and Langer, S. On the rate of convergence of fully connected deep neural network regression estimates. The Annals of Statistics, 49(4):2231–2249, 2021

    2021

  25. [32]

    and Panchenko, D

    Koltchinskii, V. and Panchenko, D. Rademacher processes and bounding the risk of function learning. In High dimensional probability II, pp. 443–457. Springer, 2000

    2000

  26. [33]

    and Levy, K

    Koren, T. and Levy, K. Fast rates for exp-concave empirical risk minimization. Advances in Neural Information Processing Systems, 28, 2015

    2015

  27. [34]

    Simple and scalable predictive uncertainty estimation using deep ensembles

    Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, 30, 2017

    2017

  28. [35]

    S., Bartlett, P

    Lee, W. S., Bartlett, P. L., and Williamson, R. C. The importance of convexity in learning with squared loss. In Proceedings of the Ninth Annual Conference on Computational Learning Theory , pp. 140–146, 1996

    1996

  29. [36]

    Learning with square loss: Localization through offset rademacher complexity

    Liang, T., Rakhlin, A., and Sridharan, K. Learning with square loss: Localization through offset rademacher complexity . InConference on Learning Theory, pp. 1260–1285. PMLR, 2015

    2015

  30. [37]

    and Tsybakov, A

    Mammen, E. and Tsybakov, A. B. Smooth discrimination analysis. The Annals of Statistics , 27(6): 1808–1829, 1999

    1999

  31. [38]

    h-consistency bounds: Characterization and extensions

    Mao, A., Mohri, M., and Zhong, Y. h-consistency bounds: Characterization and extensions. In Thirty- seventh Conference on Neural Information Processing Systems, 2023

    2023

  32. [39]

    and N´ed´elec, ´E

    Massart, P. and N´ed´elec, ´E. Risk bounds for statistical learning.The Annals of Statistics, 34(5):2326–2366, 2006

    2006

  33. [40]

    Improving the sample complexity using global data

    Mendelson, S. Improving the sample complexity using global data. IEEE transactions on Information Theory, 48(7):1977–1991, 2002

    1977

  34. [41]

    Rademacher averages and phase transitions in glivenko-cantelli classes

    Mendelson, S. Rademacher averages and phase transitions in glivenko-cantelli classes. IEEE transactions on Information Theory, 48(1):251–263, 2002

    2002

  35. [42]

    Learning without concentration for general loss functions

    Mendelson, S. Learning without concentration for general loss functions. Probability Theory and Related Fields, 171(1-2):459–502, 2018

    2018

  36. [43]

    Variance-aware off-policy evaluation with linear function approximation

    Min, Y., Wang, T., Zhou, D., and Gu, Q. Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34:7598–7610, 2021

    2021

  37. [44]

    and Sontag, D

    Mozannar, H. and Sontag, D. Consistent estimators for learning to defer to an expert. In International Conference on Machine Learning, pp. 7076–7087. PMLR, 2020

    2020

  38. [45]

    and Duchi, J

    Namkoong, H. and Duchi, J. C. Variance-based regularization with convex objectives. Advances in neural information processing systems, 30, 2017

    2017

  39. [46]

    D., Ma, M., and Tzamos, C

    Pia, A. D., Ma, M., and Tzamos, C. Clustering with queries under semi-random noise. In Loh, P.- L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pp. 5278–5313. PMLR, 02–05 Jul 2022....

    2022

  40. [47]

    and El-Yaniv, R

    Pidan, D. and El-Yaniv, R. Selective prediction of financial trends with hidden markov models. Advances in Neural Information Processing Systems, 24, 2011

    2011

  41. [48]

    Empirical processes

    Pollard, D. Empirical processes. volume 2, pp. 43–50. Institute of Mathematical Statistics, 1990

    1990

  42. [49]

    and Zhivotovskiy, N

    Puchkin, N. and Zhivotovskiy, N. Exponential savings in agnostic active learning through abstention. IEEE Transactions on Information Theory, 68(7):4651–4665, 2022. doi: 10.1109/TIT.2022.3156592. 17

    2022

  43. [50]

    On the pitfalls of heteroscedastic uncertainty estimation with probabilistic neural networks

    Seitzer, M., Tavakoli, A., Antic, D., and Martius, G. On the pitfalls of heteroscedastic uncertainty estimation with probabilistic neural networks. In International Conference on Learning Representations,

  44. [51]

    K., Das, S., Panda, R., Sattigeri, P., and Wornell, G

    Shah, A., Bu, Y., Lee, J. K., Das, S., Panda, R., Sattigeri, P., and Wornell, G. W. Selective regression under fairness criteria. In International Conference on Machine Learning, pp. 19598–19615. PMLR, 2022

    2022

  45. [52]

    Reliable training and estimation of variance networks

    Skafte, N., Jørgensen, M., and Hauberg, S. Reliable training and estimation of variance networks. Advances in Neural Information Processing Systems, 32, 2019

    2019

  46. [53]

    Sharper bounds for gaussian and empirical processes

    Talagrand, M. Sharper bounds for gaussian and empirical processes. The Annals of Probability , pp. 28–76, 1994

    1994

  47. [54]

    Tsybakov, A. B. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1): 135–166, 2004

    2004

  48. [55]

    Tsybakov, A. B. Optimal rates of aggregation. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 303–313. Springer, 2003

    2003

  49. [56]

    Valiant, L. G. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984

    1984

  50. [57]

    W., Wellner, J

    Van Der Vaart, A. W., Wellner, J. A., van der Vaart, A. W., and Wellner, J. A.Weak convergence. Springer, 1996

    1996

  51. [58]

    and Chervonenkis, A

    Vapnik, V. and Chervonenkis, A. Theory of pattern recognition, 1974

    1974

  52. [59]

    and Chervonenkis, A

    Vapnik, V. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971

    1971

  53. [60]

    Learning and generalisation: with applications to neural networks

    Vidyasagar, M. Learning and generalisation: with applications to neural networks. Springer Science & Business Media, 2013

    2013

  54. [61]

    Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling

    Xie, T., Ma, Y., and Wang, Y.-X. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019

    2019

  55. [62]

    and Zeevi, A

    Xu, Y. and Zeevi, A. Towards optimal problem dependent generalization error bounds in statistical learning theory .arXiv preprint arXiv:2011.06186, 2020

    2011 arXiv

  56. [63]

    and Wegkamp, M

    Yuan, M. and Wegkamp, M. Classification methods with reject option based on convex risk minimization. Journal of Machine Learning Research, 11(1), 2010

    2010

  57. [64]

    Z., and Ravikumar, P

    Zhai, R., Dan, C., Kolter, J. Z., and Ravikumar, P. K. Understanding why generalized reweighting does not improve over erm. In The Eleventh International Conference on Learning Representations, 2023

    2023

  58. [66]

    Learning to abstain from uninformative data

    Zhang, Y., Zheng, S., Dalirrooyfard, M., Wu, P., Schneider, A., Raj, A., Nevmyvaka, Y., and Chen, C. Learning to abstain from uninformative data. arXiv preprint arXiv:2309.14240, 2023

    2023 arXiv

  59. [67]

    and Hanneke, S

    Zhivotovskiy, N. and Hanneke, S. Localization of vc classes: Beyond local rademacher complexities. Theoretical Computer Science, 742:27–49, 2018. 18 A Proofs and Discussions In this section, we include proofs for the results established in Section 4 and the corresponding discu...

    2018

  60. [70]

    Therefore, n2+(⌊τ n3⌋)X i=n2+1 1 {y(i) = f ∗(x(i))} + n2X i=1 1 {y(i) = f ∗(x(i))} ≤ (1 − γ 2 ) n3 2 + γn3 4 ≤ n3 2 ≤ (n2+⌊τ n3⌋)X i=n2+1 1 {y(i) ̸= f ∗(x(i))}

    =⇒ (n2+⌊τ n3⌋)X i=n2+1 1 {y(i) = f ∗(x(i))} ≤(1 − γ 2 ) n3 2 . Therefore, n2+(⌊τ n3⌋)X i=n2+1 1 {y(i) = f ∗(x(i))} + n2X i=1 1 {y(i) = f ∗(x(i))} ≤ (1 − γ 2 ) n3 2 + γn3 4 ≤ n3 2 ≤ (n2+⌊τ n3⌋)X i=n2+1 1 {y(i) ̸= f ∗(x(i))}. (29) It can be easily verified that inequality (29) i...

  61. [71]

    Bounding Term II: Since for all f ∈ eF , σ2 ∈ eG, (y−f (x))2 σ2(x) ≤ 4c2 2, we further have q ξσ2∗(x) σ2(x) ≤ 2c2 + 2/c3

    Term I could be bounded as: 2Ex,ξ (ξ2 − 1)2 σ2∗(x) σ2(x) − 1 2 ≤ 4c2 2 + 4 c2 3 Ex,ξ − 1 + σ2∗(x) σ2(x) − log σ2∗(x) σ2(x) . Bounding Term II: Since for all f ∈ eF , σ2 ∈ eG, (y−f (x))2 σ2(x) ≤ 4c2 2, we further have q ξσ2∗(x) σ2(x) ≤ 2c2 + 2/c3. Consequently , we have 2Ex,ξ ξ...

  62. [2008]

    Proceedings 19, pp. 38–53. Springer, 2008

    2008

  63. [2022]

    URL https://openreview.net/forum?id=aPOpXlnV1T

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.