{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:47Z","timestamp":1781028347552,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800924","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2218-2229","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Private Learning of Littlestone Classes, Revisited"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9440-5671","authenticated-orcid":false,"given":"Xin","family":"Lyu","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"International Conference on Machine Learning. 32\u201340","author":"Agarwal Naman","year":"2017","unstructured":"Naman Agarwal and Karan Singh. 2017. The price of differential privacy for online learning. In International Conference on Machine Learning. 32\u201340."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3526074"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_4_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 674\u2013699","author":"Asi Hilal","year":"2023","unstructured":"Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. 2023. Private online prediction from experts: Separations and faster rates. In The Thirty Sixth Annual Conference on Learning Theory. 674\u2013699."},{"key":"e_1_3_2_1_5_1","volume-title":"Shiva Prasad Kasiviswanathan, and Kobbi Nissim","author":"Beimel Amos","year":"2014","unstructured":"Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. 2014. Bounds on the sample complexity for private learning and private data release. Machine learning, 94 (2014), 401\u2013437."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422450"},{"key":"e_1_3_2_1_7_1","volume-title":"Private Learning and Sanitization: Pure vs. Approximate Differential Privacy","author":"Beimel Amos","unstructured":"Amos Beimel, Kobbi Nissim, and Uri Stemmer. 2013. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and Jos\u00e9 D. P. Rolim (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 363\u2013378. isbn:978-3-642-40328-6"},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"Agnostic Online Learning","volume":"3","author":"Ben-David Shai","year":"2009","unstructured":"Shai Ben-David, D\u00e1vid P\u00e1l, and Shai Shalev-Shwartz. 2009. Agnostic Online Learning.. In COLT. 3, 1.","journal-title":"COLT."},{"key":"e_1_3_2_1_9_1","volume-title":"International Conference on Algorithmic Learning Theory. 362\u2013389","author":"Bun Mark","year":"2024","unstructured":"Mark Bun, Aloni Cohen, and Rathin Desai. 2024. Private PAC learning may be harder than online learning. In International Conference on Algorithmic Learning Theory. 362\u2013389."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585246"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00044"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Edith Cohen and Xin Lyu. 2023. The Target-Charging Technique for Privacy Analysis across Interactive Computations. In NeurIPS.","DOI":"10.52202\/075280-2715"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585148"},{"key":"e_1_3_2_1_15_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory. 1200\u20131222","author":"Cohen Edith","year":"2024","unstructured":"Edith Cohen, Xin Lyu, Jelani Nelson, Tam\u00e1s Sarl\u00f3s, and Uri Stemmer. 2024. Lower bounds for differential privacy under continual observation and online threshold queries. In The Thirty Seventh Annual Conference on Learning Theory. 1200\u20131222."},{"key":"e_1_3_2_1_16_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory. 1379\u20131398","author":"Dmitriev Daniil","year":"2024","unstructured":"Daniil Dmitriev, Krist\u00f3f Szab\u00f3, and Amartya Sanyal. 2024. On the growth of mistakes in differentially private online learning: A lower bound perspective. In The Thirty Seventh Annual Conference on Learning Theory. 1379\u20131398."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_1_19_1","volume-title":"Conference on Learning Theory. 1000\u20131019","author":"Feldman Vitaly","year":"2014","unstructured":"Vitaly Feldman and David Xiao. 2014. Sample complexity bounds on differentially private learning via communication complexity. In Conference on Learning Theory. 1000\u20131019."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00119"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451028"},{"key":"e_1_3_2_1_22_1","unstructured":"Badih Ghazi Ravi Kumar and Pasin Manurangsi. 2020. Differentially Private Clustering: Tight Approximation Ratios. In NeurIPS."},{"key":"e_1_3_2_1_23_1","first-page":"11462","article-title":"Littlestone classes are privately online learnable","volume":"34","author":"Golowich Noah","year":"2021","unstructured":"Noah Golowich and Roi Livni. 2021. Littlestone classes are privately online learnable. Advances in Neural Information Processing Systems, 34 (2021), 11462\u201311473.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_24_1","volume-title":"Conference on Learning Theory. 24\u20131.","author":"Jain Prateek","year":"2012","unstructured":"Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. 2012. Differentially private online learning. In Conference on Learning Theory. 24\u20131."},{"key":"e_1_3_2_1_25_1","volume-title":"Smith","author":"Jain Palak","year":"2023","unstructured":"Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. 2023. The Price of Differential Privacy under Continual Observation. In ICML (Proceedings of Machine Learning Research, Vol. 202). PMLR, 14654\u201314678."},{"key":"e_1_3_2_1_26_1","volume-title":"On the equivalence between online and private learnability beyond binary classification. Advances in neural information processing systems, 33","author":"Jung Young","year":"2020","unstructured":"Young Jung, Baekjin Kim, and Ambuj Tewari. 2020. On the equivalence between online and private learnability beyond binary classification. Advances in neural information processing systems, 33 (2020), 16701\u201316710."},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on learning theory. 2263\u20132285","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. 2020. Privately learning thresholds: Closing the exponential gap. In Conference on learning theory. 2263\u20132285."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-3381"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-2086"},{"key":"e_1_3_2_1_31_1","volume-title":"Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2","author":"Littlestone Nick","year":"1988","unstructured":"Nick Littlestone. 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2 (1988), 285\u2013318."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Xin Lyu. 2022. Composition Theorems for Interactive Differential Privacy. In NeurIPS.","DOI":"10.52202\/068431-0705"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-2390"},{"key":"e_1_3_2_1_35_1","volume-title":"Vadhan and Tianhao Wang","author":"Salil","year":"2021","unstructured":"Salil P. Vadhan and Tianhao Wang. 2021. Concurrent Composition of Differential Privacy. In TCC (2) (Lecture Notes in Computer Science, Vol. 13043). Springer, 582\u2013604."},{"key":"e_1_3_2_1_36_1","volume-title":"Vadhan and Wanrong Zhang","author":"Salil","year":"2023","unstructured":"Salil P. Vadhan and Wanrong Zhang. 2023. Concurrent Composition Theorems for Differential Privacy. In STOC. ACM, 507\u2013519."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:54:59Z","timestamp":1781027699000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":37,"alternative-id":["10.1145\/3798129.3800924","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800924","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}