Host: Aryeh Kontorovich​

An alternative theoretical approach to understanding generalization uses algorithmic stability, the extent to which a typical change in the input dataset affects the quality of the output model, to bound the generalization gap. Unlike complexity-based arguments which rely on the properties of the model class, stability-based arguments can rely on the specific learning algorithm and the underlying distribution of the data, which allows for a more nuanced analysis.

In this talk, we demonstrate that the algorithmic stability (and by extension, the generalization gap) equals the covariance between a model's loss with respect to the data and a Bayes Factor term reflecting the sample-specific information encoded by the learned model. This observation yields new, straightforward proofs of various information-based techniques for ensuring generalization.

Leveraging this understanding, we provide new generalization guarantees within the adaptive data analysis framework, improving on previous methods that invoke differential privacy (which can be interpreted as a stability notion tailored to worst-case sensitivity). This perspective allows us to shrink the required sample size to be less worst-case-dependent and to depend instead on a standard deviation term. More broadly, our results offer a frame through which to revisit the literature on generalization and to advance our understanding of what it is and how it can be achieved.

 Based on joint work with Katrina Ligett.

 Bio: Moshe is a Ph.D. candidate in the computer science department of the Hebrew University in Jerusalem, where he also received his B.Sc. in Physics, Math, and computer science, and his M.Sc. in Computer science, and is advised by Katrina Ligett. His research fields are differential privacy and adaptive data analysis and their relation to machine learning.

For his research, Moshe received the Apple Scholars in AI/ML PhD fellowship.

Bio: Inbar Seroussi is a postdoctoral fellow in the Applied Mathematics department at Tel Aviv University and McGill University. Before that, she was a postdoctoral fellow in the Mathematics department at the Weizmann Institute of Science, hosted by Prof. Ofer Zeitouni. She completed her Ph.D. in the Applied Mathematics department at Tel-Aviv University under the supervision of Prof. Nir Sochen. During her Ph.D., she was a long-term intern at Microsoft Research (MSR). Her research interest is at the interface between machine learning, statistical physics, and high dimensional probability.​

There is no universal definition of a fair algorithm that applies in all situations. Instead, there are many different definitions, often contradictory, and the choice of the right definition for each setting is a complex policy question. In this talk I am going to expand on the importance of fairness definitions and talk about an ad auction setting for job ads, where there is more than a single fairness definition. I am going to show how changing the definition can have advantages in reaching the desired outcome.

Regarding the question of how to achieve fairness, I am going to talk about omnipredictors with fairness constraints. An omnipredictor is a predictor that can be efficiently post-processed to minimize many different loss functions. I am going to discuss my work that extends the notion of an omnipredictor to optimization problems with constraints. If the constraints or the loss are changed, then only the efficient post-processing needs to be changed. Since fairness constraints are a result of a policy, it is rather likely that they might change over time. This works allows handling changing fairness constraints efficiently.

Additionally, I'll touch on how algorithmic fairness principles apply beyond their usual scope, in complexity theory. I'll also briefly discuss a work on quantum error correction. Concluding the talk, I'll share my research interests and future directions.​​

This talk will cover two of his recent research projects. The first project contributes to the efficient solution of “active Simultaneous Localization and Mapping (SLAM)," the fundamental problem behind long-duration mobile-robot navigation, which involves decision making under uncertainty in high-dimensional state spaces. As this work suggests, such problems can be automatically simplified, using predictive modification or sparsification of the robot's “belief" (uncertain estimate of the world state). This approach is supported by a theoretical framework allowing us to derive formal guarantees for the potential optimality loss. The second project supports long-lived autonomous robots by providing a theoretical and computational framework for planning experience reuse, allowing them to improve their cognitive abilities throughout their operation, without human intervention. This novel framework establishes techniques for online, automatic, lifelong encoding of individual experiences as generalizable “abstract skills," which can later be adapted for new contexts in real-time. This approach was demonstrated for robot manipulators performing object assembly, formulated as “task and motion planning."

 Bio: Khen Elimelech is a postdoctoral researcher and an instructor in the Department of Computer Science at Rice University, where he works with Professors Lydia Kavraki and Moshe Vardi. He also serves as the President of the Rice University Postdoctoral Association (RPA). Before joining Rice, he earned a B.Sc. in Applied Mathematics from Bar-Ilan University, and a Ph.D. from the Robotics and Autonomous Systems Program at the Technion–Israel Institute of Technology, under the supervision of Professor Vadim Indelman. For his Ph.D. thesis he won the national “Outstanding Ph.D. Research Award," on behalf of the Israeli Smart Transportation Research Center (ISTRC). For his postdoctoral work, he was honored as a finalist for the “Outstanding Postdoctoral Research Award," on behalf of Rice's School of Engineering. During his studies he was also recognized amongst the prestigious cohort of "Robotics: Science and Systems (R:SS) Pioneers" and amongst the “Top A.I. Student Ambassadors" by Intel. His research focuses on developing algorithms and theory allowing autonomous robots to robustly and efficiently perform cognitive tasks, such as planning, decision making, generalizing from experiences, and overcoming uncertainty.​

In my talk, I will discuss four critical challenges in real-life deep learning.
Firstly, I will discuss a method for reducing the bandwidth of read/write memory interactions during model deployment while taking into account communication complexity constraints. Prominent applications include large-language models, transformer-based foundation models, and large-graph architectures.  
Secondly,  I will introduce innovative approaches that enable learning with noisy and limited annotations. The first approach facilitates self-supervised pre-training to detect noisy samples better. The second approach takes advantage of a small calibration set to train a teacher model in a bi-level optimization framework implicitly. In addition, I will describe how to use a small number of annotated labels while efficiently merging between modalities to handle deep learning's necessity for clean and large amounts of annotated data.

Thirdly,  I will describe adversarial attacks that can efficiently mislead any navigation algorithm. These attacks are a significant safety concern that disables deep learning models from being deployed in real-world platforms, such as autonomous vehicles.
Lastly, I will introduce the geometric deep learning paradigm and focus on learning graph data in the context of various real-world problems. I will delve into the importance of the adversarial robustness of these models and relate to their expressivity.
I will also discuss future directions on combining the presented approaches to design novel deep learning models that will efficiently merge between different modalities under relaxed assumptions on the quality and amount of annotated data, safe for use in real-world platforms, and meet the specifications of modern AI accelerators.

Bio: Chaim Baskin is a Senior Research Associate at the VISTA laboratory within the Center for Intelligent Systems in the Computer Science Department and a Visiting Assistant Professor in the Faculty of Data and Decision Science at Technion. In addition, Chaim holds a Visiting Scholar position at Czech Technical University in Prague. Chaim's research focuses on representation learning, geometric deep learning, and optimization of neural networks for efficiency. He obtained his Ph.D. from the Computer Science Department at Technion in 2021. Chaim held a post-doctoral position at the same department from 2021 to 2022. Moreover, he is a member of Technion's TechAI and TASP research hubs.​

In this talk I'll discuss several recent theoretical results aiming at understanding these issues. In particular, we will discuss the merits and limitations of nonsmooth nonconvex optimization, as well as statistical generalization of nonsmooth models. Finally, we will discuss an issue overlooked by classical learning theory, namely why continuing the training process of NNs even after they fit the training data affects their generalization to unseen data.

Based on joint works with Steve Hanneke, Michael I. Jordan, Aryeh Kontorovich, Tianyi Lin, Ohad Shamir, Gilad Yehudai & Manolis Zampetakis. 

Bio: Guy Kornowski is a PhD student at the Weizmann Institute of Science, advised by Prof. Ohad Shamir. His research focuses on optimization and machine learning theory. He was granted an Azrieli fellowship.​

Our present work seeks to establish dimension-free (i.e., without an explicit dependence on d) estimates on M, including those that hold for d=∞. As such bounds must necessarily depend on μ, we refer to this regime as Local Glivenko-Cantelli, and are aware of very few previous bounds of this type — which are quite sub-optimal. Already the special case of product measures μ is quite non-trivial. We give necessary and sufficient conditions on μ for 𝔼[M]→0, and discover a novel sub-Gamma-type maximal inequality for shifted Bernoullis. 

 A number of challenging open problems are posed for future research. Joint work with Doron Cohen. 

https://arxiv.org/abs/2209.04054

Bio: Aryeh Kontorovich received his undergraduate degree in mathematics with a certificate in applied mathematics from Princeton University in 2001. His M.Sc. and Ph.D. are from Carnegie Mellon University, where he graduated in 2007. After a postdoctoral fellowship at the Weizmann Institute of Science, he joined the Computer Science department at Ben-Gurion University of the Negev in 2009, where he is currently a full professor. His research interests are mainly in machine learning, with a focus on probability, statistics, Markov chains, and metric spaces.He served as the director of the Ben-Gurion University Data Science Research Center during 2021-2022.

This talk presents a complete history of the Cardinality Estimation problem from Flajolet and Martin's seminal 1983 paper to the present, and includes an account of how the research community became fractured, delaying many natural developments by decades.  I will present our recent efforts to achieve information-theoretically optimal cardinality sketches, which draws on two notions of "information" developed in the 20th century: Fisher information (governing optimal point estimation) and Shannon entropy (governing optimal space/communication).

Joint work with Dingyu Wang:
(STOC 2021) https://arxiv.org/abs/2007.08051
(ICALP 2021) https://arxiv.org/abs/2008.08739
(PODS 2023) https://arxiv.org/abs/2208.10578

Short Bio: Seth Pettie is a Professor of Computer Science and Engineering at the University of Michigan.  He received his Ph.D. from UT-Austin in 2003, and was an Alexander von Humboldt Fellow at the Max Planck Institute for Computer Science from 2003-2006.  He has held Visiting Professor positions at Aarhus University (2013-14) and Bar-Ilan University (2023).

Bio: Moshe Babaioff is a Senior Principal Researcher at Microsoft Research, located in Israel. His research focuses on establishing rigorous theoretical foundations of solutions to real-world problems in the intersection of Economics and Computation (EC), using tools and approaches from Computer Science, Game Theory, and Microeconomic Theory. Moshe has served on multiple leadership positions at the EC community, including serving as Program co-Chair of ACM-EC 2017, as General Chair of ACM-EC 2014, and as co-chair of the Economics, Monetization, and Online Markets Track of The Web Conference (2023).

Moshe has been at Microsoft Research (MSR) for 15 years, first at MSR Silicon Valley lab (2007-2014) and then at MSR in Israel (since 2014). Before joining MSR he was a postdoctoral scholar at the University of California, Berkeley. He received his PhD in Computer Science from the Hebrew University in Jerusalem.

To begin, I describe how NLP researchers currently conduct experiments and measure model performance, highlighting some important limitations. I will present our work, in which we propose statistical analyses for comparing models that allow researchers to make credible and statistically valid claims in many experimental settings in NLP, such as experimenting with deep neural network models or reporting model performance across multiple languages.

Then, I will discuss challenges related to evaluating text-generation tasks, such as machine translation or automatic summarization. Evaluation of text-generation models is not straightforward because different texts can convey the same meaning. Therefore, comparing a model's output with a human-written reference may not reflect the true quality of the output. Researchers have designed metrics to automatically evaluate text-generation systems. However, none of them measures all of the aspects we wish to evaluate. Therefore, I will propose methods for estimating the quality of these evaluation metrics and introduce limitations for a certain type of evaluation technique known as reference-free. Finally, I will discuss future research directions and challenges in estimating the true performance of NLP models.

This talk is based on papers published in TACL (2017, 2021), ACL (2018, 2019), NAACL 2022, EMNLP 2022, and a book published by Morgan and Claypool Publishers in 2020.   ​

Bio: Rotem Dror is a postdoctoral researcher at the University of Pennsylvania Cognitive Computation Group, mentored by Prof. Dan Roth. She received her Ph.D. from the Technion - Israel Institute of Technology, where she was advised by Prof. Roi Reichart. With a focus on Natural Language Processing applications, her research involves developing statistically sound methodologies for empirical investigation and evaluation.​

By: Amos Korman, The French National Centre for Scientific Research (CNRS)

Host: Natan Rubin

Bio: Amos Korman received his Ph.D. in computer science at the Weizmann Institute of Science in May 2006, under the guidance of David Peleg. His Ph.D. thesis won Dean's prize for Ph.D. students. He then continued for two years of postdoc at the Technion and has been a researcher at CNRS, France, since Nov. 2007. In 2015 Amos received his Habilitation and in 2017 he was promoted to the rank "Directeur de Recherche". Until 2014 Amos worked primarily in the areas of distributed computing and graph algorithms. Around that time, he made a shift in his research focus, aiming to study biological phenomena through an algorithmic perspective. To support this pioneering initiative Amos received an ERC Consolidator Grant that lasted during the years 2015 - 2021. In 2020 Amos received the SIROCCO Prize for Innovation in Distributed Computing. As mentioned in the laudatio, the award was given for "pioneering contributions to distributed computing methods for system biology''.

A fundamental problem in robotics is to localize a robot in the real-world using only a monocular 2D RGB camera. Here, localization means 6 degrees of freedom: x,y,z-axes and rotations around them. Our group suggested the first solution with provable guarantees that can be applied in real-time on a very weak and lightweight micro-computer (RPI0, <5 grams, <$6). 

The motivation was to provide the first autonomous nano-drone of weight <100 grams, but we also used it for smart carts, and flying ads in the supermarket of Rami-Levi (near the lab). The main theoretical challenge was to provide the first provable approximation for the Perspective-n-Point problem: Compute a rotation and translation of a set of n points (in the 3d world) that minimize their sum of distances to n paired lines (2D pixels with missing depth). This is by proving that there is always a small subset of pairs (called core-set) that yields such an approximation and can be computed in O(n) time.

Based on papers with my awesome students:

- International Conference on Intelligence Robots and Systems (IROS'22), with Ibrahim Jubran, Fares Fares, Yuval        Alfassi, and Firas Ayoub.
- International Conference on Computer Vision (ICCV'21), with Ibrahim Jubran and Alaa Maalouf.

Bio: https://www.rbd-labs.com

 Bio: Michael Schapira is professor of Computer Science at Hebrew University. His research focuses on the design and analysis of (Inter)network architectures and protocols and, in particular, on the interface of networking and machine learning. Prior to joining Hebrew U, he worked at Google NYC's Infrastructure Networking Group and was a postdoctoral researcher at UC Berkeley, Yale University, and Princeton University. He is a recipient of the Allon Fellowship, the Wolf Foundation's Krill Prize, an ERC Starting Grant, faculty awards from Microsoft, Google, and Facebook, IETF/IRTF Applied Networking Research Prizes, and the IEEE Communications Society William R. Bennett Prize.

​Proactive and Online Distributed Load Balancing

By: Manish Kumar
Host: Shlomi Dolev

​A study of privacy and compression in learning theory.

By: Meni Sadigurschi

(Host: Aryeh Kontrovich)

​Federated Learning: Collaborative Learning on Private Data

By: Friedman Award - Amit Portnoy

(Host: Danny Hendler)

We introduce federated learning, discuss the communication challenges it poses, and present EDEN—a robust lossy compression technique tailored for its specific communication patterns and constraints. We discuss EDEN's appealing theoretical guarantees and present empirical results that demonstrate that it consistently improves over the state-of-the-art. EDEN will be presented at ICML '22. It is a generalization of our previous compression technique named DRIVE, presented at NeurIPS '21.

This talk is for a general CS audience.

Amit Portnoy is a Ph.D. student in the CS department, advised by Prof.

Danny Hendler. This is joint work with Ran Ben Basat, Yaniv Ben-Itzhak, Gal Mendelson, Michael Mitzenmacher, and Shay Vargaftik.

​Caching systems commonly advertise the cached content, thus allowing users to select which cache to query for the desired datum. The data structure used to advertise the cached content is called indicator. Due to bandwidth and energy constraints, a practical indicator is typically not a fresh, accurate list of all the items currently stored in the cache. Instead, the indicator is a stale approximation of the list of the currently cached items. As a result, indicators experience false indications. These false indications significantly increase costs, and may even result in a scenario where using indicators does more harm than good.

Our work introduces the cache selection problem, namely, the problem of selecting which cache to access in the face of such false indications. We formally model this problem as a cost minimization problem and introduce practical algorithms with guaranteed approximation ratios. We further perform an extensive simulation study with multiple real system traces. We show that our algorithms incur a significantly lower access cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).

Itamar Cohen received his B.Sc. degree in computer engineering and M.Sc. in electrical engineering from the Technion – I.I.T, and Ph.D. from the Ben-Gurion University of the Negev. He worked as a Chip Designer with EZchip Technologies, as a Test Engineer at Marvell, and as a Research Assistant at REMON—Israel 4G Mobile Consortium. He is currently a Post-Doctoral Fellow with the Politecnico di Torino, Italy. His research interests include network algorithms and resource allocation problems, and specifically issues related to scheduling, cooperative caching, and decision making under uncertainty.

Bio: Talya Eden is a postdoctoral fellow jointly affiliated with MIT and Boston University. She works on sublinear-time graph algorithms and randomized algorithms for huge data sets. Her work focuses on theoretical and applied graph parameter estimation in sublinear-time, as well as graph algorithms in other related areas, such as the streaming model, the massively parallel computation model, and learning-augmented algorithms.

 Talya completed her PhD at the School of Electrical Engineering at Tel Aviv University under the supervision of Prof. Dana Ron, and then continued on to a postdoctoral fellowship with the Foundations of Data Science Institute at MIT.  Talya has won several awards for her work, including the EATCS Distinguished Dissertation Award in Theoretical Computer Science, a Rothschild Postdoctoral Fellowship, a Schmidt Postdoctoral Award, a Ben Gurion University postdoctoral fellowship, a Weinstein Graduate Studies Prize, and the Azrieli Fellows Scholarship.

>> Homepage

>> Link ​to Lecture​​​

>> Link to Lecture​

In machine learning settings where the dataset consists of signals defined on many different graphs, the trained GNN should generalize to graphs outside the training set. A GNN is called transferable if, whenever two graphs represent the same underlying phenomenon, the GNN has similar repercussions on both graphs. Transferability ensures that GNNs generalize if the graphs in the test set represent the same phenomena as the graphs in the training set. We will discuss the different approaches to mathematically model the notions of transferability, and derive corresponding transferability error bounds, proving that GNNs have good generalization capabilities.

Links to related papers:
>> https://arxiv.org/pdf/1907.12972.pdf
>> https://arxiv.org/pdf/1705.07664.pdf

Bio:
Ron Levie received the Ph.D. degree in applied mathematics in 2018, from Tel Aviv University, Israel. During 2018-2020, he was a postdoctoral researcher with the Research Group Applied Functional Analysis, Institute of Mathematics, TU Berlin, Germany. Since 2021 he is a researcher in the Bavarian AI Chair for Mathematical Foundations of Artificial Intelligence, Department of Mathematics, LMU Munich, Germany. Since 2021, he is also a consultant at the Huawei project Radio-Map Assisted Pathloss Prediction, at the Communications and Information Theory Chair, TU Berlin. He won excellence awards for his MSc and PhD studies, and a Postdoc Minerva Fellowship. He is a guest editor at Sampling Theory, Signal Processing, and Data Analysis (SaSiDa), and was a conference chair of the Online International Conference on Computational Harmonic Analysis (Online-ICCHA 2021).
His current research interests are in the theory of deep learning, geometric deep learning, interpretability of deep learning, deep learning in wireless communication, harmonic analysis, signal processing, wavelet theory, uncertainty principles, continuous frames, and randomized methods.
>> Homepage​

The renaissance of machine learning (ML) and deep learning (DL) over the last decade is accompanied by an unscalable computational cost, limiting its advancement and weighing on the field in practice. In this talk, we take a systematic approach to address the algorithmic and methodological limitations at the root of these costs. We first demonstrate that DL training and pruning are predictable and governed by scaling laws -- for state of the art models and tasks, spanning image classification and language modeling, as well as for state of the art model compression via iterative pruning. Predictability, via the establishment of these scaling laws, provides the path for the principled design and trade-off reasoning, currently largely lacking in the field. We then continue to analyze the sources of the scaling laws, offering an approximation-theoretic view and showing through the exploration of a noiseless realizable case that DL is in fact dominated by error sources very far from the lower error limit. We conclude by building on the gained theoretical understanding of the scaling laws' origins. We present a conjectural path to eliminate one of the current dominant error sources -- through a data bandwidth limiting hypothesis and the introduction of Nyquist learners -- which can, in principle, reach the generalization error lower limit (e.g. 0 in the noiseless case), at finite dataset size.​