About

Hello!

I am a postdoctoral researcher at the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL) in Chicago, where I am hosted by Lev Reyzin (University of Illinois Chicago), Avrim Blum, and Nati Srebro (Toyota Technological Institute at Chicago).

I earned my PhD from the Computer Science Department at Ben-Gurion University, where I had the privilege of being advised by Aryeh Kontorovich (Ben-Gurion University) and Yishay Mansour (Tel Aviv University and Google Research). Prior to that, I completed my Bachelor's degree in Mathematics and Computer Science at Tel Aviv University.

I’ll be joining the Computer Science Department at the Technion as a faculty member in 2027.
Feel free to reach out to chat about research and opportunities.

Research interests

My primary research interests lie in the foundations of machine learning theory and data-driven sequential decision-making, as well as their intersections with game theory, private data analysis, information theory, signal processing, theoretical computer science and cognitive science.

Recent news and activities

Aug 2026
I'll participate in the Foundations of Interpretability Workshop at UCLA.
Feb 2026
I gave a talk on the hardness of learning regular expressions at the FLaNN Seminar. This paper recently received an Elegance Paper Award at ALT 2026.
Nov 2025
Two papers accepted as spotlights to NeurIPS 2025.
Feb 2025
I'll participate in the Deep Learning Theory workshop at the Simons Institute in Berkeley (Feb 2025) and at the Simons Foundation in New York (Sep 2025).
Oct 2024
I’m helping with the organization of FOCS 2024 in Chicago, come to the learning session on October 30.
Nov 2024
I'll participate in the Rising Stars in Data Science workshop at UCSD.
Jul 2024
Our paper on "Information Complexity of Stochastic Convex Optimization" won a best paper award at ICML 2024.
Apr 2024
I'll start a postdoctoral position in fall 2024 at IDEAL Institute (NSF TRIPODS program), hosted by Lev Reyzin (UIC), Avrim Blum, and Nati Srebro (TTIC).
Aug 2023
I'll be at Vector Institute to work with Daniel Roy and Karolina Dziugaite as a research intern starting August 2023.

Publications

* Authors are listed in alphabetical order, except sometimes when a student author is listed first.

Preprints
Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
Arxiv
Capacity-Constrained Online Convex Optimization with Delayed Feedback
Alexander Ryabchenko, Idan Attias, Daniel M. Roy
Arxiv
A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
Alexander Ryabchenko, Idan Attias, Daniel M. Roy
Arxiv
Learning-Augmented Algorithms for Boolean Satisfiability
Idan Attias, Xing Gao, Lev Reyzin
Arxiv
Fixed Point Computation: Beating Brute Force with Smoothed Analysis
Idan Attias, Yuval Dagan, Constantinos Daskalakis, Rui Yao, Manolis Zampetakis
Arxiv
Publications (conferences and journals)
Positive Distribution Shift as a Framework for Understanding Tractable Learning
Marko Medvedev, Idan Attias, Elisabetta Cornacchia, Theodor Misiakiewicz, Gal Vardi, Nathan Srebro
43rd International Conference on Machine Learning (ICML 2026)
Arxiv • Twitter summary • Video (3:50-38:20)
On the Hardness of Learning Regular Expressions
Idan Attias, Lev Reyzin, Nathan Srebro, Gal Vardi
37th International Conference on Algorithmic Learning Theory (ALT 2026)
Elegant Paper Award
Arxiv • Twitter summary
Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025)
Spotlight
Arxiv
On Traceability in ℓp Stochastic Convex Optimization
Sasha Voitovych, Mahdi Haghifam, Idan Attias, Gintare Karolina Dziugaite, Roi Livni, Daniel M. Roy
39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025)
Spotlight
Arxiv
Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
38th Annual Conference on Learning Theory (COLT 2025)
Arxiv • Slides • Video (Alex, 44:30-55:30) • Video (40:30-54:00)
PAC Learning with Improvements
Idan Attias, Avrim Blum, Keziah Naggita, Donya Saless, Dravyansh Sharma, Matthew Walter
42nd International Conference on Machine Learning (ICML 2025)
Arxiv • Video (Avrim, 25:00-38:00)
Sample Compression Scheme Reductions
Idan Attias, Steve Hanneke, Arvind Ramaswami
36th International Conference on Algorithmic Learning Theory (ALT 2025)
Arxiv • Video (Arvind)
Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
Ziyi Liu, Idan Attias, Daniel M. Roy
38th Annual Conference on Neural Information Processing Systems (Neurips 2024)
Arxiv
Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, Daniel M. Roy
41st International Conference on Machine Learning (ICML 2024)
ICML 2024 Best Paper Award • Oral
Arxiv • Twitter summary • Slides • Video
Agnostic Sample Compression Schemes for Regression
Idan Attias, Steve Hanneke, Aryeh Kontorovich, Menachem Sadigurschi
41st International Conference on Machine Learning (ICML 2024)
Spotlight
Arxiv
Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginal
Ziyi Liu, Idan Attias, Daniel M. Roy
41st International Conference on Machine Learning (ICML 2024)
Arxiv • Slides • Video (0:00–40:00)
Universal Rates for Real-Valued Regression: Separations between Cut-Off and Absolute Loss
37th Annual Conference on Learning Theory (COLT 2024)
Fat-shattering dimension of k-fold Aggregations
Idan Attias, Aryeh Kontorovich
Journal of Machine Learning Research, Vol. 25 (JMLR 2024)
Arxiv
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas
37th Annual Conference on Neural Information Processing Systems (NeurIPS 2023)
Oral Presentation
Arxiv • Slides
Online Learning and Solving Infinite Games with an ERM Oracle
Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson
36th Annual Conference on Learning Theory (COLT 2023)
Arxiv • Slides
Adversarially Robust PAC Learnability of Real-Valued Functions
Idan Attias, Steve Hanneke
40th International Conference on Machine Learning (ICML 2023)
Arxiv
Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers
Eitan-Hai Mashiah, Idan Attias, Yishay Mansour
37th Conference on Artificial Intelligence (AAAI 2023)
Oral Presentation
Arxiv • Slides
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Idan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer
Algorithmica 2024 / 14th Innovations in Theoretical Computer Science (ITCS 2023)
Arxiv • Slides • Video (Moshe)
A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
Idan Attias, Steve Hanneke, Yishay Mansour
36th Annual Conference on Neural Information Processing Systems (NeurIPS 2022)
Arxiv • Slides
Domain Invariant Adversarial Learning
Transactions on Machine Learning Research (TMLR 2022)
Arxiv
Prediction with Corrupted Expert Advice
Idan Amir, Idan Attias, Tomer Koren, Roi Livni, Yishay Mansour
34th Annual Conference on Neural Information Processing Systems (NeurIPS 2020)
Spotlight
Arxiv • Slides
Improved Generalization Bounds for Adversarially Robust Learning
Idan Attias, Aryeh Kontorovich, Yishay Mansour
Journal of Machine Learning Research, Vol. 23 (JMLR 2022)
Preliminary version: 30th International Conference on Algorithmic Learning Theory (ALT 2019)
Arxiv

Teaching

Introduction to Machine Learning, Ben-Gurion University
Teaching Assistant: Fall 23
Computational Models, Ben-Gurion University
Teaching Assistant: Spring 20, Spring 21, Spring 22, Spring 23
[Regular languages and finite automata, Grammars and Context-Free Languages, Turing Machines and Computability, Introduction to complexity]
Design of Algorithms, Ben-Gurion University
Teaching Assistant: Fall 21, Fall 22
[Reductions, Greedy algorithms, Dynamic programming, Shortest path, Maximum flow, Randomized algorithms, Linear programming, Approximation algorithms]
Theory of Interactive Learning (graduate-level course), Ben-Gurion University
Grader: Spring 22
[PAC learning, VC theory, Active learning]
Introduction to Computer Science, Ben-Gurion University
Teaching Assistant: Fall 20
Discrete Math, Tel Aviv University
Grader: Fall 16

Contact

University of Illinois at Chicago — Science and Engineering Offices (MC 249), Room 618, Department of Mathematics, Statistics, and Computer Science
Toyota Technological Institute at Chicago — Room 406