Pith. sign in

REVIEW 5 cited by

Optimistic Rates for Learning with a Smooth Loss

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1009.3896 v2 pith:CBNUKUZO submitted 2010-09-20 cs.LG

Nathan Srebro , Karthik Sridharan , Ambuj Tewari This is my paper · ORCID
classification cs.LG
keywords hypothesisrisksqrtclasslearninglosssmoothachievable
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

We establish an excess risk bound of O(H R_n^2 + R_n \sqrt{H L*}) for empirical risk minimization with an H-smooth loss function and a hypothesis class with Rademacher complexity R_n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R_n = \sqrt{R/n}, this translates to a learning rate of O(RH/n) in the separable (L*=0) case and O(RH/n + \sqrt{L^* RH/n}) more generally. We also provide similar guarantees for online and stochastic convex optimization with a smooth non-negative objective.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimistic Rates for Multiclass PAC Learning

    cs.LG 2026-08 accept novelty 8.0 of 10 partial

    For multiclass PAC learning, the optimal excess risk at any fixed oracle error L* equals the square root of L* times the Natarajan dimension over n, plus the realizable DS-dimension rate, with matching upper and lower bounds.

  2. Online Learning and Unlearning

    cs.LG 2025-05 conditional novelty 7.0 of 10

    Two OGD-based algorithms provably make deleted points statistically invisible in future outputs while adding only modest regret overhead.

  3. On Least Squares Estimation under Heteroscedastic and Heavy-Tailed Errors

    math.ST 2019-09 conditional novelty 7.0 of 10

    Under finite moments and a local envelope growth condition, the least squares estimator in nonparametric regression can achieve minimax rates with heavy-tailed, covariate-dependent errors.

  4. Tight Generalization Bound for AdaBoost

    cs.LG 2026-07 accept novelty 6.0 of 10

    AdaBoost’s generalization error is Θ(d ln(nγ²/d)/(nγ²) + ln(1/δ)/n), via a new zero-margin-loss bound for voting classifiers.

  5. What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness

    cs.LG 2025-06 conditional novelty 4.0 of 10

    Under bounded second-order heterogeneity, local updates are shown to achieve faster convergence than mini-batch SGD in several convex and non-convex regimes, with matching lower bounds.

Pith tools