Amir Yehudayoff

STOC Conference 2024 Conference Paper

Local Borsuk-Ulam, Stability, and Replicability

• Zachary Chase 0001
• Bogdan Chornomaz
• Shay Moran
• Amir Yehudayoff

We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of our methods in combinatorics and topology. We show that, besides trivial cases, both list-replicable and globally stable learning are impossible in the agnostic PAC setting. This is in contrast with the realizable case where it is known that any class with a finite Littlestone dimension can be learned by such algorithms. In the realizable PAC setting, we sharpen previous impossibility results and broaden their scope. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes. This provides an exponential improvement over previous works and implies an exponential separation from the Littlestone dimension. We further introduce lower bounds for weak learners, i.e., learners that are only marginally better than random guessing. Lower bounds from previous works apply only to stronger learners. To offer a broader and more comprehensive view of our topological approach, we prove a local variant of the Borsuk-Ulam theorem in topology and a result in combinatorics concerning Kneser colorings. In combinatorics, we prove that if c is a coloring of all non-empty subsets of [ n ] such that disjoint sets have different colors, then there is a chain of subsets that receives at least 1+ ⌊ n /2⌋ colors (this bound is sharp). In topology, we prove e.g. that for any open antipodal-free cover of the d -dimensional sphere, there is a point ‍ x that belongs to at least t =⌈ d +3/2⌉ sets.

FOCS Conference 2023 Conference Paper

Stability and Replicability in Learning

• Zachary Chase 0001
• Shay Moran
• Amir Yehudayoff

Replicability is essential in science as it allows us to validate and verify research findings. Impagliazzo, Lei, Pitassi and Sorrell ('22) recently initiated the study of replicability in machine learning. A learning algorithm is replicable if it typically produces the same output when applied on two i. i. d. inputs using the same internal randomness. We study a variant of replicability that does not involve fixing the randomness. An algorithm satisfies this form of replicability if it typically produces the same output when applied on two i. i. d. inputs (without fixing the internal randomness). This variant is called global stability and was introduced by Bun, Livni and Moran ('20) in the context of differential privacy. Impagliazzo et al. showed how to boost any replicable algorithm so that it produces the same output with probability arbitrarily close to 1. In contrast, we demonstrate that for numerous learning tasks, global stability can only be accomplished weakly, where the same output is produced only with probability bounded away from 1. To overcome this limitation, we introduce the concept of list replicability, which is equivalent to global stability. Moreover, we prove that list replicability can be boosted so that it is achieved with probability arbitrarily close to 1. We also describe basic relations between standard learningtheoretic complexity measures and list replicable numbers. Our results, in addition, imply that besides trivial cases, replicable algorithms (in the sense of Impagliazzo et al.) must be randomized. The proof of the impossibility result is based on a topological fixed-point theorem. For every algorithm, we are able to locate a "hard input distribution by applying the Poincaré-Miranda theorem in a related topological setting. The equivalence between global stability and list replicability is algorithmic.

FOCS Conference 2022 Conference Paper

A Characterization of Multiclass Learnability

• Nataly Brukhim
• Daniel Carmon
• Irit Dinur
• Shay Moran
• Amir Yehudayoff

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz, (2014). The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. He furthered showed that it is the only barrier, provided that the number of labels is bounded. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. This work provides a negative answer: we construct a non-learnable class with Natarajan dimension 1. For the construction, we identify a fundamental connection between concept classes and topology (i. e. , colorful simplicial complexes). We crucially rely on a deep and involved construction of hyperbolic pseudo-manifolds by Januszkiewicz and Światkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no obvious barriers exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics.

STOC Conference 2021 Conference Paper

A theory of universal learning

• Olivier Bousquet
• Steve Hanneke
• Shay Moran
• Ramon van Handel
• Amir Yehudayoff

How quickly can a given class of concepts be learned from examples? It is common to measure the performance of a supervised machine learning algorithm by plotting its “learning curve”, that is, the decay of the error rate as a function of the number of training examples. However, the classical theoretical framework for understanding learnability, the PAC model of Vapnik-Chervonenkis and Valiant, does not explain the behavior of learning curves: the distribution-free PAC model of learning can only bound the upper envelope of the learning curves over all possible data distributions. This does not match the practice of machine learning, where the data source is typically fixed in any given scenario, while the learner may choose the number of training examples on the basis of factors such as computational resources and desired accuracy. In this paper, we study an alternative learning model that better captures such practical aspects of machine learning, but still gives rise to a complete theory of the learnable in the spirit of the PAC model. More precisely, we consider the problem of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring uniformity over the distribution. The main result of this paper is a remarkable trichotomy: there are only three possible rates of universal learning. More precisely, we show that the learning curves of any given concept class decay either at an exponential, linear, or arbitrarily slow rates. Moreover, each of these cases is completely characterized by appropriate combinatorial parameters, and we exhibit optimal learning algorithms that achieve the best possible rate in each case. For concreteness, we consider in this paper only the realizable case, though analogous results are expected to extend to more general learning scenarios.

STOC Conference 2021 Invited Paper

Learnability can be independent of set theory (invited paper)

• Shai Ben-David
• Pavel Hrubes
• Shay Moran
• Amir Shpilka
• Amir Yehudayoff

TCS Journal 2020 Journal Article

On the covariance-Hessian relation in evolution strategies

• Ofer M. Shir
• Amir Yehudayoff

We consider Evolution Strategies (ESs) operating only with isotropic Gaussian mutations on positive quadratic objective functions, and investigate the covariance matrix when constructed out of selected individuals by truncation. We prove that the covariance matrix over ( 1, λ ) -selected decision vectors becomes proportional to the inverse of the landscape Hessian as the population-size λ increases. This confirms a classical hypothesis that statistical learning of the landscape is an inherent characteristic of standard ESs, and that this distinguishing capability stems only from the usage of isotropic Gaussian mutations and rank-based selection. Even though the model under consideration does not precisely conform with practically encountered scenarios, it plays a role of a theoretical foundation for learning capabilities within ESs. We also provide broad numerical validation for the proven results, and present empirical evidence for its generalization to ( μ, λ ) -selection.

IJCAI Conference 2019 Conference Paper

On Division Versus Saturation in Pseudo-Boolean Solving

• Stephan Gocht
• Jakob Nordström
• Amir Yehudayoff

The conflict-driven clause learning (CDCL) paradigm has revolutionized SAT solving over the last two decades. Extending this approach to pseudo-Boolean (PB) solvers doing 0-1 linear programming holds the promise of further exponential improvements in theory, but intriguingly such gains have not materialized in practice. Also intriguingly, most PB extensions of CDCL use not the division rule in cutting planes as defined in [Cook et al. , '87] but instead the so-called saturation rule. To the best of our knowledge, there has been no study comparing the strengths of division and saturation in the context of conflict-driven PB learning, when all linear combinations of inequalities are required to cancel variables. We show that PB solvers with division instead of saturation can be exponentially stronger. In the other direction, we prove that simulating a single saturation step can require an exponential number of divisions. We also perform some experiments to see whether these phenomena can be observed in actual solvers. Our conclusion is that a careful combination of division and saturation seems to be crucial to harness more of the power of cutting planes.

STOC Conference 2019 Conference Paper

Separating monotone VP and VNP

• Amir Yehudayoff

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

NeurIPS Conference 2017 Conference Paper

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues

• Noga Alon
• Moshe Babaioff
• Yannai A. Gonczarowski
• Yishay Mansour
• Shay Moran
• Amir Yehudayoff

In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the k'th moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.

NeurIPS Conference 2016 Conference Paper

Supervised learning through the lens of compression

• Ofir David
• Shay Moran
• Amir Yehudayoff

This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. We first extend the investigation to multiclass categorization: we prove that in this case learnability is equivalent to compression of logarithmic sample size and that the uniform convergence property implies compression of constant size. We use the compressibility-learnability equivalence to show that (i) for multiclass categorization, PAC and agnostic PAC learnability are equivalent, and (ii) to derive a compactness theorem for learnability. We then consider supervised learning under general loss functions: we show that in this case, in order to maintain the compressibility-learnability equivalence, it is necessary to consider an approximate variant of compression. We use it to show that PAC and agnostic PAC are not equivalent, even when the loss function has only three values.

FOCS Conference 2015 Conference Paper

Compressing and Teaching for Low VC-Dimension

• Shay Moran
• Amir Shpilka
• Avi Wigderson
• Amir Yehudayoff

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. Namely, the quality of sample compression schemes and of teaching sets for classes of low VC-dimension. Let C be a binary concept class of size m and VC-dimension d. Prior to this work, the best known upper bounds for both parameters were log(m), while the best lower bounds are linear in d. We present significantly better upper bounds on both as follows. We construct sample compression schemes of size exp(d) for C. This resolves a question of Littlest one and Warmuth (1986). Roughly speaking, we show that given an arbitrary set of labeled examples from an unknown concept in C, one can retain only a subset of exp(d) of them, in a way that allows to recover the labels of all other examples in the set, using additional exp(d) information bits. We further show that there always exists a concept c in C with a teaching set (i. e. A list of c-labeled examples uniquely identifying c in C) of size exp(d) log log(m). This problem was studied by Kuhlmann (1999). Our construction also implies that the recursive teaching (RT) dimension of C is at most exp(d) log log(m) as well. The RT-dimension was suggested by Zilles et al. And Doliwa et al. (2010). The same notion (under the name partial-ID width) was independently studied by Wigderson and Yehuday off (2013). An upper bound on this parameter that depends only on d is known just for the very simple case d=1, and is open even for d=2. We also make small progress towards this seemingly modest goal.

FOCS Conference 2013 Conference Paper

Direct Products in Communication Complexity

• Mark Braverman
• Anup Rao 0001
• Omri Weinstein
• Amir Yehudayoff

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f, C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μ n be the product distribution on n inputs and f n denote the function that computes n copies of f on these inputs. We prove that if T log 3/2 T ≪ (C - 1)√n and suc(μ, f, C) n, f n, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log 2 T ≪ Cn, we must have suc(μ n, f n, T) ≤ exp(-Ω(n)).

STOC Conference 2012 Conference Paper

Monotone expansion

• Jean Bourgain
• Amir Yehudayoff

This work presents an explicit construction of a family of monotone expanders, which are bi-partite expander graphs whose edge-set is defined by (partial) monotone functions. The family is essentially defined by the Mobius action of SL 2 (R), the group of 2 x 2 matrices with determinant one, on the interval [0,1]. No other proof-of-existence for monotone expanders is known, not even using the probabilistic method. The proof extends recent results on finite/compact groups to the non-compact scenario. Specifically, we show a product-growth theorem for SL 2 (R); roughly, that for every A ⊂ SL 2 (R) with certain properties, the size of AAA is much larger than that of A. We mention two applications of this construction: Dvir and Shpilka showed that it yields a construction of explicit dimension expanders, which are a generalization of standard expander graphs. Dvir and Wigderson proved that it yields the existence of explicit pushdown expanders, which are graphs that arise in Turing machine simulations.

FOCS Conference 2012 Conference Paper

Population Recovery and Partial Identification

• Avi Wigderson
• Amir Yehudayoff

We study several problems in which an unknown distribution over an unknown population of vectors needs to be recovered from partial or noisy samples, each of which nearly completely erases or obliterates the original vector. For example, consider a distribution p over a population V ⊆ {0, 1} n. A noisy sample v' is obtained by choosing v according to p and flipping each coordinate of v with probability say 0. 49 independently. The problem is to recover V, p as efficiently as possible from noisy samples. Such problems naturally arise in a variety of contexts in learning, clustering, statistics, computational biology, data mining and database privacy, where loss and error may be introduced by nature, inaccurate measurements, or on purpose. We give fairly efficient algorithms to recover the data under fairly general assumptions. Underlying our algorithms is a new structure we call a partial identification (PID) graph for an arbitrary finite set of vectors over any alphabet. This graph captures the extent to which certain subsets of coordinates in each vector distinguish it from other vectors. PID graphs yield strategies for dimension reductions and re-assembly of statistical information. The quality of our algorithms (sequential and parallel runtime, as well as numerical stability) critically depends on three parameters of PID graphs: width, depth and cost. The combinatorial heart of this work is showing that every set of vectors posses a PID graph in which all three parameters are small (we prove some limitations on their trade-offs as well). We further give an efficient algorithm to find such near-optimal PID graphs for any set of vectors. Our efficient PID graphs imply general algorithms for these recovery problems, even when loss or noise are just below the information-theoretic limit! In the learning/clustering context this gives a new algorithm for learning mixtures of binomial distributions (with known marginals) whose running time depends only quasi-polynomially on the number of clusters. We discuss implications to privacy and coding as well.

STOC Conference 2012 Conference Paper

Separating multilinear branching programs and formulas

• Zeev Dvir
• Guillaume Malod
• Sylvain Perifel
• Amir Yehudayoff

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n -variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size n Ω(log n) .

STOC Conference 2011 Conference Paper

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes

• Boaz Barak
• Zeev Dvir
• Amir Yehudayoff
• Avi Wigderson

STOC Conference 2010 Conference Paper

Non-commutative circuits and the sum-of-squares problem

• Pavel Hrubes
• Avi Wigderson
• Amir Yehudayoff

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree four polynomials, the classical sum-of-squares problem: find the smallest n such that there exists an identity (x 1 2 +x 2 2 +•• + x k 2 )• (y 1 ^2+y 2 2 +•• + y k 2 )= f 1 2 +f 2 2 + ... +f n 2 , where each f i = f i (X,Y) is bilinear in X={x 1 ,... ,x k } and Y={y 1 ,..., y k }. Over the complex numbers, we show that a sufficiently strong super-linear lower bound on n in, namely, n ≥ k 1+ε with ε >0, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

FOCS Conference 2010 Conference Paper

Pseudorandom Generators for Regular Branching Programs

• Mark Braverman
• Anup Rao 0001
• Ran Raz
• Amir Yehudayoff

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ϵ)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ϵ. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ϵ/γ 2.

STOC Conference 2008 Conference Paper

Hardness-randomness tradeoffs for bounded depth arithmetic circuits

• Zeev Dvir
• Amir Shpilka
• Amir Yehudayoff

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x 1 ,...,x m ) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d-8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). In particular, if we are guaranteed that the circuit computes a multilinear polynomial then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan-Wigderson generator of Impagliazzo and Kabanets together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form P(x 1 ,...,x n ,y) ≡ 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x 1 ,...,x n ) satisfies P(x 1 ,...,x n ,f(x 1 ,...,x n ))≡ 0 then f has a circuit of depth d+3 and size O(s • r + m r ), where m is the degree of f and r is the highest degree of the variable y appearing in P. In the other direction we observe that the methods of Impagliazzo and Kabanets imply that if we can derandomize polynomial identity testing for bounded depth circuits then NEXP does not have bounded depth arithmetic circuits. That is, either NEXP ⊄ P/poly or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

FOCS Conference 2008 Conference Paper

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

• Ran Raz
• Amir Yehudayoff

We study a new method for proving lower bounds for subclasses of arithmetic circuits. Roughly speaking, the lower bound is proved by bounding the correlation between the coefficients' vector of a polynomial and the coefficients' vector of any product of two polynomials with disjoint sets of variables. We prove lower bounds for several old and new subclasses of circuits.

FOCS Conference 2007 Conference Paper

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

• Ran Raz
• Amir Shpilka
• Amir Yehudayoff

We construct an explicit polynomial f(x 1, .. ., x n ), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n 4/3 log 2 n} The lower bound holds over any field.