2 papers
cs.LG2024
The Cost of Parallelizing Boosting
Xin Lyu, Hongxun Wu, Junzhao Yang
We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold: - First, we prov…
cs.LG2023
Tight Time-Space Lower Bounds for Constant-Pass Learning
Xin Lyu, Avishay Tal, Hongxun Wu +1
In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS'16, JACM'19]. A line of work tha…