# Yishay Mansour

Prof. Yishay Mansour got his PhD from MIT in 1990, following it he was
a postdoctoral fellow in Harvard and a Research Staff Member in IBM T.
J. Watson Research Center. Since 1992 he is at Tel-Aviv University,
where he is currently a Professor of Computer Science and has serves
as the first head of the Blavatnik School of Computer Science during
2000-2002. He was the founder and first director of the Israeli Center of Research
Excellence in Algorithms.
Prof. Mansour has published over 100 journal papers and over 200
proceeding papers in various areas of computer science with special
emphasis on machine learning, algorithmic game theory, communication
networks, and theoretical computer science and has supervised over a
dozen graduate students in those areas.
Prof. Mansour was named as an ACM fellow 2014, and he is currently an
associate editor in a number of distinguished journals and has been on
numerous conference program committees. He was both the program chair
of COLT (1998) and the STOC (2016) and served twice on the COLT
steering committee and is a member of the ALT steering committee.

### Research Areas

Authored Publications

Google Publications

Other Publications

Sort By

Adversarially Robust Streaming Algorithms via Differential Privacy

Journal of the ACM, vol. 69(6) (2022), pp. 1-14

Preview abstract
A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary. We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy. This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.
View details

Fair Wrapping for Black-box Predictions

Alexander Soen

Sanmi Koyejo

Nyalleng Moorosi

Ke Sun

Lexing Xie

NeurIPS (2022)

Preview abstract
We introduce a new family of techniques to post-process an accurate black box posterior and reduce its bias, born out of the recent analysis of improper loss functions whose optimisation can correct any \textit{twist} in prediction, unfairness being treated as one. Post-processing involves learning a function we define as an $\alpha$-tree for the correction, for which we provide two generic boosting compliant training algorithms. We show that our correction has appealing properties in terms of composition of corrections, generalization, interpretability and divergence to the black box. We exemplify the use of our technique for fairness compliance in three models: conditional value at risk, equality of opportunity and statistical parity and provide experiments on several readily available domains.
View details

Differentially-Private Bayes Consistency

Aryeh Kontorovich

Shay Moran

Menachem Sadigurschi

Archive, Archive, Archive

Preview abstract
We construct a universally Bayes consistent learning rule
which satisfies differential privacy (DP).
We first handle the setting of binary classification
and then extend our rule to the more
general setting of density estimation (with respect to the total variation metric).
The existence of a universally consistent DP learner
reveals a stark difference with the distribution-free PAC model.
Indeed, in the latter DP learning is extremely limited:
even one-dimensional linear classifiers
are not privately learnable in this stringent model.
Our result thus demonstrates that by allowing
the learning rate to depend on the target distribution,
one can circumvent the above-mentioned impossibility result
and in fact learn \emph{arbitrary} distributions by a single DP algorithm.
As an application, we prove that any VC class can be privately learned in a semi-supervised
setting with a near-optimal \emph{labelled} sample complexity of $\tilde O(d/\eps)$ labeled examples
(and with an unlabeled sample complexity that can depend on the target distribution).
View details

Near-optimal Regret Bounds for Stochastic Shortest Path

Aviv Rosenberg

International Conference on Machine Learning (ICML) 2020 (2020)

Preview abstract
Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost.
In the learning formulation of the problem, the agent is unaware of the environment dynamics (i.e., the transition function) and has to repeatedly play for a given number of episodes while learning the problem’s optimal solution.
Unlike other well-studied models in reinforcement learning (RL), the length of an episode is not predetermined (or bounded) and is influenced by the agent’s actions.
Recently, Tarbouriech et al. (2019) studied this problem in the context of regret minimization, and provided an algorithm whose regret bound is inversely proportional to the square root of the minimum instantaneous cost.
In this work we remove this dependence on the minimum cost—we give an algorithm that guarantees a regret bound of $O(B S \sqrt{A K})$ , where B is an upper bound on the expected cost of the optimal policy, S is the number of states, A is the number of actions and K is the total number of episodes.
We additionally show that any learning algorithm must have at least $\Omega(B \sqrt{S A K})$ regret in the worst case.
View details

Planning and Learning with Stochastic Action Sets

Martin Mladenov

Proceedings of the Twenty-seventh International Joint Conference on Artificial Intelligence (IJCAI-18), Stockholm (2018), pp. 4674-4682

Preview abstract
This is an extended version of the paper Planning and Learning with Stochastic Action Sets that appeared in the Proceedings of the Twenty-seventh International Joint Conference on Artificial Intelligence (IJCAI-18), pp.4674-4682, Stockholm (2018).
In many practical uses of reinforcement learning (RL) the set of actions available
at a given state is a random variable, with realizations governed by an exogenous
stochastic process. Somewhat surprisingly, the foundations for such sequential
decision processes have been unaddressed. In this work, we formalize and
investigate MDPs with stochastic action sets (SAS-MDPs) to provide these foundations.
We show that optimal policies and value functions in this model have a
structure that admits a compact representation. From an RL perspective, we show
that Q-learning with sampled action sets is sound. In model-based settings, we
consider two important special cases: when individual actions are available with
independent probabilities; and a sampling-based model for unknown distributions.
We develop poly-time value and policy iteration methods for both cases; and in the
first, we offer a poly-time linear programming solution.
View details

History-Independent Distributed Multi-agent Learning

Amos Fiat

Algorithmic Game Theory: 9th International Symposium, SAGT 2016, Proceedings, Springer, pp. 77-89

Preview abstract
How should we evaluate a rumor? We address this question in a setting where multiple agents seek an estimate of the probability, b, of some future binary event. A common uniform prior on b is assumed. A rumor about b meanders through the network, evolving over time. The rumor evolves, not because of ill will or noise, but because agents incorporate private signals about b before passing on the (modified) rumor. The loss to an agent is the (realized) square error of her opinion. Our setting introduces strategic behavior based on evidence regarding an exogenous event to current models of rumor/influence propagation in social networks. We study a simple Exponential Moving Average (EMA) for combining experience evidence and trusted advice (rumor), quantifying its resulting performance and comparing it to the optimal achievable using Bayes posterior having access to the agents private signals. We study the quality of p_T, the prediction of the last agent along a chain of T rumor-mongering agents. The prediction p_T can be viewed as an aggregate estimator of b that depends on the private signals of T agents.
View details

Robust Domain Adaptation

Annals of Mathematics and Artificial Intelligence, vol. 71 Issue 4 (2014), 365–380

Preview abstract
We derive a generalization bound for domain adaptation by using the properties of robust algorithms. Our new bound depends on λ-shift, a measure of prior knowledge regarding the similarity of source and target domain distributions. Based on the generalization bound, we design SVM variants for binary classification and regression domain adaptation algorithms.
View details

Ad Exchange – Proposal for a New Trading Agent Competition Game

Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets: AMEC and TADA (2013), pp. 133-145

Learning with Maximum-Entropy Distributions