Skip to content
conftrace_
2023 COLT COLT 2023

Open problem: log(n) factor in "Local Glivenko-Cantelli"

Abstract

Can the log(n) factor in the upper bound of Cohen and Kontorovich (COLT, 2023)be removed?

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization

Authors

Doron Cohen, Aryeh Kontorovich

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning Mathematics & Optimization > Statistics

Keywords

learning theory sample complexity uniform convergence vc theory concentration inequality empirical process theory glivenko-cantelli theorem
Download PDF

More from COLT 2023

All COLT 2023 papers →
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique
Fine-Grained Distribution-Dependent Learning Curves
Efficient median of means estimator
Open Problem: Learning sparse linear concepts by priming the features
Open Problem: The Sample Complexity of Multi-Distribution Learning for VC Classes
Open Problem: Polynomial linearly-convergent method for g-convex optimization?