Title
| When
| Abstract
|
Proactive and Online Distributed Load Balancing By: Manish Kumar
Host: Shlomi Dolev | Sep 6, 2022
16:00-17:00
Bldg. 37, Room 202
>> Zoom Link | In this talk, I will present the main results of my Ph.D. research work.
● The load balancing problem is defined when there is an undirected network
(graph) of computers (nodes). Each one is assigned a non-negative working load
and would like to balance their loads. We study the classic load balancing
problem on dynamic general graphs, where the graph changes arbitrarily between
the computational rounds, remaining connected with no permanent cut.
We solve the load balancing problem in the most general setting (in relation to
the previous work) and best-known efficiency. Our solutions are anytime,
monotonic, and deterministic distributed algorithms based on a short local
deal-agreement communication of proposal/deal in the neighborhood of each node
and proposed synchronous, asynchronous, and self-stabilizing algorithms. [SSS
2020 and Theory of Computing Systems 2022]
● Another research direction focuses on the diverse solutions for optimization
problems, such as finding the multi-criteria k-shortest paths, prioritized
multi-criteria 2-disjoint shortest paths, and k disjoint all-criteria-shortest
paths. These algorithms help in balancing the load efficiently in the
communication network. [CSCML 2021 and submitted to SN Computer Science
Journal]
● Additionally, we have initiated a study on testing randomness using
randomness, which helps during prediction-based load balancing. [CSCML 2022 and
will be submitted to Cryptography and Communication Journal]
My advisor is Shlomi Dolev. During my Ph.D., I collaborated with Daniel Berend
and Yefim Dinitz. |
Scalable Bayesian Nonparametric Mixtures for
Computer Vision and Deep Learning By: Or Dinari (Host: Oren Freifeld) | Jul 5, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | In the unsupervised-learning task of clustering, Bayesian
Nonparametric (BNP) mixtures provide a principled approach for inferring the
model complexity (i.e., the number of clusters) together with the other
parameters. Inference in such models, however, is more difficult than in the
parametric case (namely, when the number of clusters is known). In particular,
existing BNP methods usually scale poorly. This is a key obstacle in using such
models in real-world problems in general and, more specially, in Computer
Vision, where both the number of samples and the dimensions are usually high.
In this talk, I will present a few of our recent works that aim to bridge this
practicality gap, via new models, new inference algorithms, and efficient
distributed implementations.
References:
1) [Or Dinari and Oren Freifeld, AISTATS 2022]: Sampling
in Dirichlet Process Mixture Models for Clustering Streaming Data.
2) [Or Dinari and Oren Freifeld, UAI 2022]: Revisiting
DP-Means: Fast Scalable Algorithms via Parallelism and Delayed Cluster
Creation.
3) [Or Dinari*, Angel Yu, Oren Freifeld, and John Fisher
III. HPML Workshop, 2019]: Distributed MCMC Inference in Dirichlet Process Mixture
Models Using Julia.
4) [Or Dinari*, Raz Zamir*, John Fisher III, and Oren
Freifeld, Currently Under Review]: CPU- and GPU-based Distributed Sampling in
Dirichlet Process Mixtures for Large-scale Analysis.
About the speaker:
Or Dinari is a PhD student in the Department of Computer
Science at Ben-Gurion University, working in the areas of computer vision and
machine learning under the supervision of Dr. Oren Freifeld. His current
research focus is on unsupervised/semi-supervised learning, clustering, Bayesian
nonparametrics, deep learning, and computer-vision applications. >> Meeting Recording
|
A study of privacy and
compression in learning theory. By: Meni Sadigurschi (Host: Aryeh Kontrovich) | Jun 28, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Motivated by the
increasing awareness and demand for user privacy, the line of work on private
learning aims to construct learning algorithms that provide privacy protections
for their training data. It is especially desirable to achieve differential
privacy, a privacy notion which has been widely adopted by the academic
community, government agencies, and big corporations like Google, Apple, and
Microsoft.
In our work we study the task of private learning from various directions. In
this talk I will focus on two of these directions. The first is the fundamental
problem of learning
Axis-Aligned-Rectangles with differential privacy, for which I will present a
novel algorithm with optimal sample complexity. In the second part of the talk
I will present our study on ptivacy preserving universally Bayes consistent
learning, a notion of learning which is arguably more realistic than the
classical PAC learning framework. |
Implicit bias in machine learning By: Ohad Shamir (Host: Aryeh Kontrovich) | Jun 21, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Most practical
algorithms for supervised machine learning boil down to optimizing the average
performance over a training dataset. However, it is increasingly recognized
that although the optimization objective is the same, the manner in which it is
optimized plays a decisive role in the properties of the resulting predictor.
For example, when training large neural networks, there are generally many
weight combinations that will perfectly fit the training data. However,
gradient-based training methods somehow tend to reach those which, on the one
hand, do not overfit, and on the other hand, are very brittle to adversarially
crafted examples. Why the dynamics of these methods lead to such "implicit
biases" is still far from being fully understood. In this talk, I'll
describe several recent theoretical results related to this question, in the
context of benign overfitting and adversarial examples.
Based on joint work with Gal Vardi and Gilad Yehudai.
|
Federated Learning: Collaborative Learning on
Private Data By: Friedman Award - Amit Portnoy (Host: Danny Hendler) | Jun 14, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | Federated learning is a distributed machine learning
paradigm where clients collaboratively train a model without sending their
local data samples. Federated learning opens new opportunities for data
partnerships at scale, with applications in healthcare, transportation, IoT,
and more.
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.
|
New Directions in
Derandomization: Non-Black-Box Techniques, Superfast Algorithms By: Roei Tell (Host: Yuval Pinter) | Jun 7, 2022
15:20
zoom talk
Bldg. 37, Room 201>>Zoom Link | This talk will present
two new directions in the study of derandomization, which are related to each
other.
The first direction is avoiding pseudorandom generators in favor of
*non-black-box techniques*, thereby replacing the classical
hardness-vs-randomness framework with a new framework. The non-black-box
techniques extract pseudorandomness for a probabilistic machine from the code
of that specific machine.
The second direction is trying to minimize the computational overhead when
eliminating randomness, hoping for *free lunch results* in derandomization.
This is possible both for probabilistic algorithms, and for interactive proof
systems.
We will mention results from the last two years by myself and by others, most
prominently from joint works of mine with Lijie Chen. |
Matching vertices of
correlated random graphs
By: Mark Rudelson
(Host: Aryeh Kontrovich) | May 24, 2022
12:00-13:00
Bldg. 37, Room 201>>Zoom Link | Consider two copies of the same graph with a large number of
vertices.
In each copy, we independently delete a few edges. Our aim is to match
exactly the vertices of the first and the second copy. This problem
originates in particular in social networks, where you know the
identities of users in one network and want to recover the identities
in another one. This problem is computationally hard in a
deterministic setting, so it is often considered for typical, i.e.,
random graphs. We will discuss a computationally efficient
probabilistic algorithm which allows an exact recovery with high
probability even if one deletes a small constant proportion of edges.
Joint work with Cheng Mao and Konstantin Tikhomirov.
|
Quantum Pseudorandomness
and Classical Complexity
By: William Kretschmer
(Host: Dr. Or Sattath) | May 24, 2022
10:00-11:00
Bldg. 37, Room 201 >>Zoom Link | Pseudorandom quantum
states (PRSs) are a recently-introduced primitive
that have found exciting new applications in quantum cryptography and
black hole physics. In this talk, I will explore some connections
between PRSs and structural complexity theory. I will present a
surprising and counterintuitive result: a quantum oracle relative to
which BQP = QMA but PRSs exist. On the other hand, I will show that
PRSs do not exist if BQP = PP, a result which holds relative to all
oracles. I will discuss some implications of these results, including
a new impossibility result for shadow tomography.
Based on https://arxiv.org/abs/2103.09320
Homepage: https://www.cs.utexas.edu/~kretsch/ >> Meeting Recording |
Access strategies for network caching
By: Itamar Cohen
(Host: Dr. Gil Einziger) | Apr. 12, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link | 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. |
Projection Methods, Superiorization and Applications
By: Aviv Gibali
(Host: Dr. Eran Treister)
| Mar. 31, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link
| Projection methods are iterative algorithms that use projections onto sets
while relying on the general principle that when a family of sets is present,
then projections onto the given individual sets are easier to perform than
projections onto other sets that are derived from the given individual sets.
Their robustness, low computational effort and their ability to handle
huge-size problems make them very useful for many convex and non-convex real-world problems
such as Image Reconstruction, Intensity-Modulated Radiation Therapy
(IMRT) Treatment Planning as well as Sudoku and 8 Queens Puzzle.
The Superiorization Methodology is a heuristic tool and its goal is to find certain good, or superior, solutions to feasibility and optimization problems. In many scenarios, solving the full problem can be rather demanding from the computational point of view, but solving part of it, say the feasibility part is, often, less demanding.
In recent years "superiorized" projection methods and other iterative methods have been developed and applied successfully to feasibility, single and multi-objective optimization.
In this talk I will provide an overview on the above concepts, present several theoretical and practical results and also potential direction for future research.
|
Generalization in Overparameterized Machine Learning
By: Yehuda Dar
(Host: Eran Treister)
| Mar. 23, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link
| Deep neural networks are highly overparameterized models, i.e., they are highly complex with typically many more parameters than the number of training data examples. Such overparameterized models are usually learned to perfectly fit their training data; yet, in sharp contrast to conventional machine learning guidelines, they still generalize extremely well to inputs outside of their training dataset. This practical generalization performance motivates numerous foundational questions that have not yet been addressed even for much simpler models like linear regression.
This talk presents new analyses of the fundamental factors that affect generalization in overparameterized machine learning. Our results characterize the so-called “double descent phenomenon," which extends the classical bias-variance tradeoff, in several overparameterized learning settings. First, we consider a transfer learning process between source and target linear regression problems that are related and overparameterized. Our theory characterizes the generalization performance and hence the cases where transfer learning is beneficial. Second, we consider linear subspace learning problems for dimensionality reduction and data generation. We define semi- and fully supervised extensions to the common unsupervised forms of these subspace learning problems and demonstrate that overparameterization in conjunction with supervision can improve generalization performance.
Bio:
Yehuda Dar is a postdoctoral research associate in the Electrical and Computer Engineering Department at Rice University, working on topics in the foundational understanding of modern machine learning. Before that, he was a postdoctoral fellow in the Computer Science Department of the Technion — Israel Institute of Technology where he also received his PhD in 2018. Yehuda earned his MSc in Electrical Engineering and a BSc in Computer Engineering, both also from the Technion. His main research interests are in the fields of machine learning, signal and image processing, optimization, and data compression.
>> Link to Lecture
|
Information geometry of Markov kernels
By: Shun Watanabe
(Host: Aryeh Kontorovich)
| Mar. 22, 2022
12:00-13:00
>> Zoom Link
| In this talk, we first review basic concepts on the information geometry,
such as the e-family , m-family, and the Pythagorean identity, in the context
of probability distribution. We will also discuss an application of information
geometry to the problem of statistical hypothesis testing. Then, we will
discuss how the concepts of information geometry are extended to Markov
kernels. Finally, we will present our recent result that the set of reversible
Markov kernels constitute both e-family and m-family of Markov kernels.
This talk is based on a joint work with Geoffrey Wolfer.
>> Link to Lecture
|
Seeing the Unseen - a Generalized Scheme for Missing Mass Estimation
By: Amichai Painsky
(Host: Aryeh Kontorovich)
| Mar. 21, 2022
12:00-13:00
Bldg. 37, Room 201
>> Zoom Link
| Consider a finite sample from an unknown distribution over a countable
alphabet. The missing mass refers to the probability of symbols that do not appear
in the sample. Estimating the missing mass is a basic problem in statistics,
machine learning and related fields, which dates back to the early work of
Laplace, and the more recent seminal contribution of Good and Turing. The
missing mass problem has many applications in a variety of domains. For
example, given the observed population of Covid mutations, what is the
probability that we encounter a new variant that has not been seen before? In
this work we introduce a generalized framework for missing mass estimation. Our
framework provides novel risk bounds and improves upon currently known
estimation schemes. Importantly, it is easy to apply and does not require
additional modeling assumptions. This makes it a favorable choice for many
practical setups. Furthermore, we show that by utilizing our scheme, we improve
the estimation accuracy of large alphabet probability distributions.
Bio:
Amichai Painsky is a Senior Lecturer (Assistant Professor) at Tel Aviv
University. Amichai received his B.Sc. in Electrical Engineering from Tel Aviv
University (2007), his Masters in Electrical Engineering from Princeton
University (2009) and his Ph.D. in Statistics from Tel Aviv University (2016).
Following his graduation, Amichai joined Massachusetts Institute of Technology
(MIT) as a postdoctoral fellow (2019). Amichai's research focuses on
statistical inference and learning, and their connection to information theory.
>> Link to Lecture
|
Rank Aggregation with Proportionate Fairness
By: Baruch Schieber
(Host: Michael Elkin)
| Mar. 15, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
| Given multiple individual rank orders over a set of candidates or items,
where the candidates belong to multiple (non-binary) protected groups, we study
the classical rank aggregation problem under proportionate or p-fairness (RAPF
in short), considering Kemeny distance.
We first study the problem of producing a closest p-fair ranking for an
individual ranked order (IPF in short) considering Kendall-Tau distance, and
present multiple solutions for IPF. We then present a deterministic algorithm
and a randomized algorithm to solve RAF that leverage the solutions of IPF as a
subroutine.
We make several algorithmic contributions: (i) we prove that when the group
protected attribute is binary, IPF could be solved exactly using a greedy
technique; (ii) when the group protected attribute is multi-valued, solving IPF
is non-trivial: we present two different solutions for it, one is exact under
the assumption that the number of attribute values is constant, and the other
admits a 2 approximation factor; (iii) we present the guiding principle of designing
the solution for RAPF with an approximation factor that is 2+ the approximation
factor of the IPF solution, resulting in 3 and 4 approximation algorithms.
We run extensive experiments using multiple real world and large scale
synthetic datasets and compare our proposed solutions against multiple
state-of-the-art related works to demonstrate the effectiveness and efficiency
of our studied problem and proposed solution.
This is joint work with Senjuti Basu Roy, Mouinul Md Islam, and Dong Wei.
>> Link to Lecture
|
Sequential and distributed clustering algorithms
By: Tom Hess
(Supervisor: Prof. Sivan Sabato)
| Mar. 1, 2022
12:00-13:00
>> Zoom Link
| This seminar is about sequential and distributed clustering.
First, I introduce and study the setting of no-substitution sequential k-median
clustering. In this setting, an i.i.d. sequenceof examples is observed. An example can be selected as a center only
immediately after it is observed, and it cannot be substituted later.
The goal is to select a set of centers with a good k-median cost on the
distribution generated the sequence.
I provide algorithms for this setting in a general bounded metric space and
show that these algorithms obtain a similar cost guarantee for the best offline
algorithm. In addition, I study the k-median clustering under the sequential
no-substitution setting, without any structural assumption on the metric space.
I give the first algorithm for this setting that obtains a constant
approximation factor on the optimal cost, an exponential improvement over
previous work. Moreover, the number of selected centers is only quasi-linear in
k.
Second, I provide a new k-means algorithm for the distributed setting, where
the data is distributed across many machines, and a coordinator communicates
with these machines to calculate the output clustering. This algorithm
guarantees a cost approximation factor and a number of communication rounds
that depend only on the computational capacity of the coordinator. Moreover,
the algorithm includes a built-in stopping mechanism, which allows it to use
fewer communication rounds whenever possible. I show both theoretically and
empirically that in many natural cases, indeed 1-4 rounds suffice.
>> Link to Lecture
|
Optimal Linear Numeric
Planning
By: Dr. Alexander
Shleyfman
(Host: Prof. Ronen Brafman)
| Feb. 1, 2022
12:00-13:00
>> Zoom Link
| Forward search, such as A*, equipped with an informative heuristic and a strong pruning technique, proved to be one of the most efficient methods to solve planning problems. Most of these heuristics and pruning techniques, however, are currently limited by an assumption that all variables involved have finite domains. While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy restrictions on them. In particular, most current planners do not support heuristics and pruning techniques that account for linear numeric effects. The contribution of our work is twofold.
First, we extend the symmetry breaking pruning methods such as DKS and Orbit Space Search, proposed by Domshlak et al. (2012, 2015) to support actions with linear conditions and effects. Our experiments further show that symmetry reduction can yield a substantial reduction in search effort even if the algorithm is equipped with a strong heuristics.
Second, we adapt the well-known classical planning heuristic LM-cut (Helmert and Domshlak, 2009) to account for both additive constant and linear effects, where for linear effect we show a way to efficiently exploit specific variable structures. Empirical comparison shows that the proposed LM-cut heuristic favorably competes with the currently available state-of-the-art heuristics and achieves significant improvement in coverage.
Bio:
Alex did his Master's and PhD degrees in the field of Artificial Intelligence at the Faculty of Industrial Engineering and Management at the Technion under the supervision of Prof. Carmel Domshlak. After that, he moved to Canada for a postdoctoral fellowship at the University of Toronto, where he was hosted by Prof. J. Christopher Beck, and worked on resource management for cloud services and numeric planning. Today, Alex is back in Israel. He is a postdoctoral fellow at the Technion, at the Cognitive Robotics lab, hosted by Prof. Erez Karpas.
>> Link to Lecture
|
On the Role of Data in Algorithm Design
By: Tal Wagner
(Host: Prof. Sivan Sabato)
| Jan. 11, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
| Recently, there has been a growing interest in harnessing the power of big datasets and modern machine learning for designing new scalable algorithms. This invites us to rethink the role of data in algorithm design: not just as the input to pre-designed algorithms, but also a factor that enters the algorithm design process itself, driving it in a strong and possibly automated manner. This talk will show how to leverage data and learning for better algorithm design in two fundamental areas: high-dimensional similarity search and efficient linear algebra.
In particular, I will show the following:
1. Using data-dependent compression, we obtain optimal compressed representations of high-dimensional Euclidean distances. This result marks the first improvement over classical data-oblivious compression schemes, which provably cannot match its performance.
2. Using neural networks, we show how to learn to construct better data structures for high-dimensional similarity search.
3. We then show how those techniques also give rise to fast algorithms for low rank approximation of matrices.
Our algorithms are both proven analytically and implemented and validated empirically, showing improvements over previous methods on standard benchmark datasets.
Bio:
Tal Wagner is a postdoctoral researcher in the Machine Learning Foundations group at Microsoft Research Redmond. His research interests are in designing algorithms for massive high-dimensional datasets and large-scale machine learning. He received his PhD from the EECS department at MIT in September 2020. Previously, he earned his MSc from the Weizmann Institute and BSc from the Technion. During his PhD, he spent time as a research intern in Microsoft, Amazon and VMware.
|
Information in Mechanism Design
By: Alon Eden
(Host: Dr. Sigal Oren)
| Jan. 4, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| The modern economy is becoming highly digital, demanding a combination of both economic and computational techniques. The abundance of data and the unique nature of digital markets highlight the special role of information in today's economic systems. In this talk, I will discuss two domains of interest. The first is auction design in the interdependent value (IDV) setting. In IDV settings, buyers hold partial information regarding the quality of the good being sold, but their actual values also depend on information that other buyers have about the good. The second is indirect mechanism design, in which the economic system can only observe partial information regarding the buyers' preferences, if any. In both domains, impossibilities are known for very basic settings. I will show how my research has pushed the boundary of what is possible via a computational approach. For IDV settings, I utilize techniques from approximation algorithms to obtain the first general positive results for combinatorial auctions. For indirect mechanisms, I initiate the use of reinforcement learning for the design of such mechanisms.
>> Link to Lecture
|
Learning with Less Data
and Labels for Language Acquisition and Understanding
By: Elior Sulem
(Host: Prof. Michael Elhadad)
| Jan. 2, 2022
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| Natural Language Processing has attracted a lot of interest in recent years and has seen large improvements with the use of contextualized neural language models. However, the progress is limited to specific tasks where large datasets are available and models are often brittle outside of these datasets. Also, current models are usually pretrained on extremely large unlabeled datasets, which limits our understanding of low-resource scenarios and makes their use unfeasible for many in the academia and industry. On the other hand, children learn with much less data, which makes the study of child language acquisition an appealing research direction to address these issues. In the first part of the talk, I will focus on pretraining on unlabeled data and show what can be learned with an input both quantitatively and qualitatively comparable to that of an average English-speaking 6 year old. In the second part of the talk I will focus on Natural Language Understanding and show how zero-shot and transfer learning strategies can be used to go beyond task-specific training. In particular, I will present a zero-shot approach to Event extraction, which is usually based on the annotation of large domain-specific corpora, using Textual Entailments (TE) and Question-Answering (QA) tasks. I will show the challenge of missing arguments in this context, presenting new models that identify unanswerable questions, leveraging different QA and TE tasks.
Bio:
Elior Sulem is a Postdoctoral Researcher at the Department of Computer and Information Science at the University of Pennsylvania, working with Prof. Dan Roth on computational semantics, event extraction and computational psycholinguistics. He completed his PhD. in the School of Computer Science and
Engineering at the Hebrew University of Jerusalem under the supervision of Prof. Ari Rappoport in 2019, working on the integration of semantic information into text simplification and machine translation. Before that, he graduated with a master's degree (magna cum laude) in Cognitive Science at the Hebrew University of Jerusalem, under the supervision of Prof. Ari Rappoport (Cognitive Sciences Department's prize for outstanding thesis). He previously completed a B.Sc. degree in Mathematics (extended program) and
Cognitive Sciences at the Hebrew University. He was a fellow of the Language, Logic and Cognition Center from 2012 to 2016. He received the Best Paper Award Runner Up at CoNLL 2021.
>> Homepage
Links to related papers:
https://aclanthology.org/2021.conll-1.49/
https://aclanthology.org/2021.findings-emnlp.385.pdf
|
Informed Data Science
By: Amir Gilad
(Host: Prof. Ehud Gudes)
| Dec. 28, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| Data science has become prevalent in various fields that affect day-to-day lives, such as healthcare, banking, and the job market. The process of developing data science applications usually consists of several automatic systems that manipulate and prepare the data in different manners. Examples of automatic data manipulations and preparations include generating synthetic data, exploring it, repairing the data, and labeling it for machine learning. These systems can be highly complex and even data scientists can find it difficult to understand and verify their output. Moreover, uninformed use of these systems can lead to errors that may affect the quality of the results of such applications. In the talk, I will highlight prominent challenges in the data science process and present three approaches for addressing them. In particular, I will present a solution that generates natural language explanations for query results, a tool for generating synthetic linked data, and a solution that explains complex queries using abstract database instances. Bio: Amir Gilad is a postdoctoral researcher in the Database group at Duke University. He received his Ph.D. in Computer Science from Tel Aviv university under the supervision of Prof. Daniel Deutch. His work focuses on developing tools and algorithms that assist users in understanding and gaining insights into data and the systems that manipulate it. His research relates to classic database tools such as data provenance, as well as natural language processing, causal inference, and privacy. Amir is the recipient of the VLDB best paper award, the SIGMOD research highlight award, and the Google Ph.D. fellowship for Structured Data and Database Management. |
Sublinear-time graph algorithms: motif counting and
uniform sampling
By: Talya Eden
(Host: Prof. Michael Elkin)
| Dec. 21, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| In this talk I will survey recent developments in approximate subgraph-counting and subgraph-sampling in sublinear-time. Counting and sampling small subgraphs (aka motifs) are two of the most basic primitives in graph analysis, and have been studied extensively, both in theory and in practice. In my talk, I will present the sublinear-time computational model, where access to the input graph is given only through queries, and will explain some of the concepts that underlie my results. I will then explain how we can get improved bounds for a very natural graph family: the family of bounded arboricity graphs. Finally, I'll present a recent application, where again we take advantage of the unique structure of social networks in order to get improved bounds for a very basic and well-studied problem.
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
|
Harnessing Scientific Literature for Boosting Discovery and Innovation
By: Tom Hope
(Host: Dr. Yuval Pinter)
| Dec. 14, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| With millions of scientific papers coming out every year, researchers are
forced to allocate their attention to increasingly narrow areas, creating
isolated “research bubbles” that limit knowledge discovery. This fragmentation
of science slows down progress and prevents the formation of cross-domain links
that catalyze breakthroughs. Toward addressing these large-scale challenges for
the future of science, my work develops new paradigms for searching,
recommending and discovering scholarly knowledge.
In this talk, I will present methods and systems for recommending research
inspirations and creating links across areas and ideas. My approach is based on
extracting novel structural representations of scholarly literature, and
leveraging them for "matchmaking" between problems and solutions and
between scientists. I will also present a new task we introduced for jointly
addressing diversity, ambiguity and hierarchy of language in scientific texts.
In this new setting, the goal is to learn to construct cross-document coreference
clusters along with a hierarchy defined over the clusters. As I will
demonstrate, being able to automatically induce this graph structure can help
unlock important applications in scientific discovery, but this remains a
highly difficult open problem.
Bio:
Tom Hope is a postdoctoral researcher at The Allen Institute for AI (AI2) and
The University of Washington, working with Daniel Weld on accelerating
scientific discovery and closely collaborating with Eric Horvitz, CSO at
Microsoft. Tom completed his PhD with Dafna Shahaf at the Hebrew University of
Jerusalem in January 2020. His work has received four best paper awards,
appeared in top venues (PNAS, KDD, EMNLP, NAACL, WSDM, CHI, AKBC, IEEE), and
received media attention from Nature and Science on his systems for COVID-19
researchers. In parallel to his PhD studies Tom created and led an applied AI
research team at Intel that published award-winning work. Tom was selected for
the 2021 Global Young Scientists Summit and 2019 Heidelberg Laureate Forum, and
was a member of the KDD 2020 Best Paper Selection Committee.
>> Link to Lecture
|
Large-scale multi-robot systems: From algorithmic
foundations to smart-mobility applications
By: Kiril Solovey
(Host: Prof. Ronen Brafman)
| Dec. 7, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| Multi-robot systems are already playing a crucial role in various domains such as manufacturing and warehouse automation. In the future, these systems will be incorporated into our daily lives through drone-delivery services and smart-mobility systems that comprise thousands of autonomous vehicles, to give a few examples. The anticipated benefits of multi-robot systems are numerous, ranging from increased safety and efficiency, to broader societal facets such as sustainability. However, to reap those rewards we must develop algorithms that can adapt rapidly to unexpected changes on a massive scale. Importantly, these algorithms must capture (i) dynamical and collision-avoidance constraints of individual robots, (ii) interactions between multiple robots, and (iii), more broadly, the interaction of those systems with their environment. These considerations give rise to extremely complex and high-dimensional optimization problems that need to be solved in real-time. In this talk, I will present progress on the design of systematic control and decision-making mechanisms to allow the safe, effective, and societally-equitable deployment of multi-robot systems. I will highlight results on fundamental capabilities for multi-robot systems (e.g., motion planning and task allocation), as well as applications in smart-mobility systems. I will also discuss challenges and opportunities for smart mobility in addressing societal issues, including traffic congestion and fairness.
BIO: Kiril Solovey is a roboticist specializing in multi-robot systems and their applications to smart mobility. He is currently a Postdoctoral Scholar in the Faculty of Computer Science at the Technion. Prior to that, he was a postdoc in the Department of Aeronautics and Astronautics, Stanford University. He obtained a PhD in Computer Science from Tel Aviv University, where he was advised by Dan Halperin.
Kiril's research focuses on the design of scalable algorithmic approaches for multi-robot systems. His work draws upon ideas across the disciplines of computer science, engineering, and transportation science, to develop methods with substantial guarantees on solution quality and robustness. He received multiple awards, including the Clore Scholars and Fulbright Postdoctoral Fellowships, best paper awards and nominations (at Robotics: Science and Systems, International Conference on Robotics and Automation, International Symposium on Multi-Robot and Multi-Agent System, and European Control Conference), and teaching awards.
>> Homepage
SELECTED PAPERS:
* Rahul Shome, Kiril Solovey, Andrew Dobson, Dan Halperin, Kostas E.
Bekris: dRRT*: Scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robots 44(3-4): 443-467 (2020)
* Kiril Solovey, Mauro Salazar, Marco Pavone: Scalable and Congestion-Aware Routing for Autonomous Mobility-On-Demand Via Frank-Wolfe Optimization. Robotics: Science and Systems 2019
* Devansh Jalota, Kiril Solovey, Karthik Gopalakrishnan, Stephen Zoepf, Hamsa Balakrishnan, Marco Pavone: When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes. EAAMO 2021: 9:1-9:11
>> Link to Lecture
|
Efficient Secure Multi-Party Computation: How Low
Can We Go?
By: Ariel Nof
(Host: Prof. Amos Beimel)
| Nov. 30, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| In the setting of secure multi-party computation, a set of parties with private inputs wish to compute a joint function of their inputs, without revealing anything but the output. This computation is carried-out in the presence of an adversary controlling a subset of the parties, who may try to learn private information or disrupt the computation. The problem of constructing efficient protocols for secure computation has gained significant interest in the last decade or so and progress has been extraordinarily fast, transforming the topic from a notion of theoretical interest only, into a technology that is even being commercialized by multiple companies. A useful metric for measuring efficiency of secure protocols is the ratio between the communication cost of the protocol, and that of the best known protocol with a “minimal" level of security, namely security against semi-honest (passive) adversaries, who act as prescribed by the protocol but try to learn additional information from messages they receive. In this talk, I will describe recent efforts to minimize this ratio and show, in the honest majority setting, new results that close (in the amortized sense) the communication gap between secure protocols against adversaries who act in any arbitrary manner, and protocols against semi-honest adversaries.
|
A Theoretical Analysis of Generalization in Graph Convolutional Neural
Networks
By: Ron Levie (LMU Munich)
(Host: Dr. Eran Treister)
| Nov. 23, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| In recent years, the need to accommodate non-Euclidean structures in data science has brought a boom in deep learning methods on graphs, leading to many practical applications with commercial impact. In this talk, we will review the mathematical foundations of the generalization capabilities of graph convolutional neural networks (GNNs). We will focus mainly on spectral GNNs, where convolution is defined as element-wise multiplication in the frequency domain of the graph. 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
|
Towards Revealing Visual
Relations Between Fixations: Modeling the Center Bias During Free-Viewing
By: Rotem Mairon
(Adviser: Prof. Ohad Ben Shahar)
| Nov. 16, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
(Hybrid)
| Understanding eye
movements is essential for comprehending visual selection and has numerous
applications in computational vision and human-computer interfaces.
Eye-movement research has revealed a variety of behavioral biases that guide
the eye regardless of visual content.
However, computational models of eye-movement behavior only partially account
for these biases. The most well-known of these biases is the center bias, which
refers to the tendency of observers to fixate on the stimulus's center. In this
study, we investigate two aspects of the center bias to help distinguish it
from visual content-driven behavior. One aspect concerns standard procedures
for collecting eye-movement data during free viewing. Specifically, the
requirement to fixate on the center of the display prior to the appearance of
the stimulus, as well as the presentation of the stimulus in the display's
center. Our findings support a fundamental shift in data collection and
analysis procedures, all in the name of obtaining data that reflects more
content-driven and less bias-related eye-movement behavior. The second aspect is how the
center bias manifests during viewing, as opposed to how it is reflected in the
spatial distribution of aggregated fixations, which is used in almost all
computational models of eye-movement behavior. To that end, this work proposes
an eye-movement data representation based on saccades rather than fixations.
This representation not only demonstrates the dynamic nature of the center bias
throughout viewing, but it also holistically demonstrates other eye-movement
phenomena that were previously investigated exclusively. Finally, we
demonstrate that the proposed representation allows for more accurate modeling
of eye-movement biases, which is critical for establishing a baseline for
computational models. Such a baseline paves the way for researchers to learn
how, if at all, visual content guides the human eye from one fixation to the next
while freely viewing natural images.
|
Mind Reading: Decoding Visual Experience from Brain Activity
By: Guy Gaziv (WIS)
(Host: Dr. Eran Treister)
| Nov. 9, 2021
12:00-13:00
Bldg. 37, Room 202
| Reconstructing and semantically classifying observed natural images from
novel (unknown) fMRI brain recordings is a milestone for developing
brain-machine interfaces and for the study of consciousness. Unfortunately,
acquiring sufficient “paired” training examples (images with their
corresponding fMRI recordings) to span the huge space of natural images and
their semantic classes is prohibitive, even in the largest image-fMRI datasets.
We present a self-supervised deep learning approach that overcomes this
barrier, giving rise to better generalizing fMRI-to-image decoders. This is
obtained by enriching the scarce paired training data with additional easily
accessible “unpaired” data from both domains (i.e., images without fMRI, and
fMRI without images). Our approach achieves state-of-the-art results in image
reconstruction from fMRI responses, as well as unprecedented large-scale
(1000-way) semantic classification of never-before-seen classes.
Bio:
Guy Gaziv is a postdoctoral fellow in the Michal Irani Computer Vision group at
The Weizmann Institute of Science. This spring he will be starting his postdoc at the DiCarlo Lab at MIT. His PhD research focused on the intersection between machine and human vision,
and specifically on decoding visual experience from brain activity. Guy earned his BSc in Electrical and Computer Engineering from The Hebrew
University of Jerusalem, and his MSc in Physics and PhD in Computer Science
from The Weizmann Institute of Science.
|
Research-oriented
gathering of students and faculty members
By: Various Faculty Members
(Host: Dr. Eran Treister) | Nov. 2, 2021
12:00-13:00
Bldg. 37, Room 202
| You are invited for a small research-oriented gathering of students and faculty members on Nov 2nd, at 12:00, room 202/37 (invitation attached). The gathering is mostly intended for new students who did not find an adviser yet, but everyone is welcome. There will be six faculty members presenting their research briefly, two of them are new in the department. These faculty members and others that will also attend the meeting are looking for students, and this is a good opportunity to talk to them. We will also encourage faculty members to be available for personal meetings with you.
So - if you haven't done so already, we encourage you to visit our department's research page and follow the links according to your field(s) of interest. Try to read about the research fields and visit the web-pages of the relevant faculty members. Once you find a faculty member that looks relevant - email him/her and try to schedule a meeting (optionally, but not necessarily on that day).
|
Scaling laws for deep learning
By: Jonathan Rosenfeld
(Host: Dr. Eran Treister)
| Oct. 26, 2021
12:30-13:30
>> Zoom Link
| Running faster will only get you so far -- it is generally advisable to
first understand where the roads lead, then get a car ...
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.
|
Expanding the hub and spoke model
By: Clara Shikhelman (Chaincode Labs)
(Host: Dr. Or Sattath)
| Oct. 19, 2021
12:00-13:00
Bldg. 37, Room 202
>> Zoom Link
| When two parties transact often using banks, Bitcoin, or any other financial device that entails fees, they might choose to turn to second-layer solutions. In these solutions, both parties lock a certain amount as escrow in a channel and transact freely with reduced fees. This gives rise to a network of channels in which any two nodes can transact with each other. A downside of these solutions, especially if they are decentralized, is the tendency of the network toward the hub and spoke model. Most nodes in this model, the “spokes", are connected to a single “hub", a high degree node that the spokes believe to be well connected. This graph topology is known to be prone to various attacks and privacy issues. In this work, we present a solution that benefits the spokes, by saving on costs, and the network, by giving it higher connectivity and good expansion properties. We use probabilistic and spectral techniques for the proofs. Short Bio: Clara Shikhelman holds a PhD in mathematics from Tel Aviv University. Following a year at Simons institute in Berkeley and CalTech, she is currently a PostDoc at Chaincode Labs.
|
