Deep neural models have achieved state-of-the-art performance on a wide range of problems in computer science, especially in computer vision. However, deep neural networks often require large datasets of labeled samples to generalize effectively. An important area of active research is semi-supervised learning, which attempts to instead utilize large quantities of (easily acquired) unlabeled samples. One family of methods in this space is pseudo-labeling, a class of algorithms that use model outputs to assign labels to unlabeled samples which are then used as labeled samples during training. Such assigned labels, called pseudo-labels, are most commonly associated with the field of semi-supervised learning. In this work, we explore a broader interpretation of pseudo-labels within both self-supervised and unsupervised methods. After a thorough treatment of pseudo-labeling in these areas, we draw the connection between them and identify commonalities between fields, as well as new directions where advancements in one area would likely benefit others, such as curriculum learning and self-supervised regularization.

In many critical computer vision scenarios unlabeled data is plentiful, but labels are scarce and difficult to obtain. As a result, semi-supervised learning which leverages unlabeled data to boost the performance of supervised classifiers have received significant attention in recent literature. One representative class of semi-supervised algorithms are co-training algorithms. Co-training algorithms leverage two different models which have access to different independent and sufficient representations or “views” of the data to jointly make better predictions. Each of these models creates pseudo-labels on unlabeled points which are used to improve the other model. We show that in the common case where independent views are not available, we can construct such views inexpensively using pre-trained models. Co-training on the constructed views yields a performance improvement over any of the individual views we construct and performance comparable with recent approaches in semi-supervised learning. We present Meta Co-Training, a novel semi-supervised learning algorithm, which has two advantages over co-training: (i) learning is more robust when there is large discrepancy between the information content of the different views, and (ii) does not require re-training from scratch on each iteration. Our method achieves new state-of-the-art performance on ImageNet-10% achieving a ∼4.7% reduction in error rate over prior work. Our method also outperforms prior semi-supervised work on several other fine-grained image classification datasets.

We study the robustness of ridge regression, lasso regression, and of a neural network, when the training set has been randomly corrupted and in response to this corruption the training-size is reduced in order to remove the corrupted data. While the neural network appears to be the most robust method among these three, nevertheless lasso regression appears to be the method of choice since it suffers less loss both when the full information is available to the learner, as well as when a significant amount of the original training set has been rendered useless because of random data corruption.

We are interested in learning rules under class imbalance. In this direction we extend the traditional model of probably approximately correct (PAC) learning to also include explicitly among its goals high recall and high precision at the end of the learning process. We establish relationships for the recall and the precision of a learned hypothesis as a function of its risk and the rate of the minority class. We then show that we can PAC learn a concept class with high recall and high precision by allowing a polynomial increase in the time and space complexity of traditional PAC learning algorithms that generate hypotheses with low risk. In sequence, by introducing a pre-processing phase on such algorithms, with a constant-size overhead on the overall sample complexity, we are able, with high probability, to compute a lower bound of the true unknown rate p of the minority class, in the interval [p/8, p). Thus, we extend our positive results on PAC learning with high recall and high precision by also waiving the requirement that such a lower bound on the rate of the minority class is given to the learners by some oracle ahead of time. We conclude our work by exploring two popular PAC learning algorithms for monotone conjunctions.

A Bernoulli(p)n distribution Bn,p over {0, 1}n is a product distribution where each variable is satisfied with the same constant probability p. Diochnos (2016) showed that Valiant's swapping algorithm for monotone conjunctions converges efficiently under Bn,p distributions over {0, 1}n for any 0 < p < 1. We continue the study of monotone conjunctions in Valiant's framework of evolvability. In particular, we prove that given a Bn,p distribution characterized by some p ∈ (0, 1/3] ∪ {1/2}, then an evolutionary mechanism that relies on the basic mutation mechanism of a (1+1) evolutionary algorithm converges efficiently, with high probability, to an ε-optimal hypothesis. Furthermore, for 0 < α ≤ 3/13, a slight modification of the algorithm, with a uniform setup this time, evolves with high probability an ε-optimal hypothesis, for every Bn,p distribution such that p ∈ [α, 1/3 - 4α/9] ∪ {1/3} ∪ {1/2}.

Word embeddings have developed into a major NLP tool with broad applicability. Understanding the semantic content of word embeddings remains an important challenge for additional applications. One aspect of this issue is to explore the interpretability of word embeddings. Sparse word embeddings have been proposed as models with improved interpretability. Continuing this line of research, we investigate the extent to which human interpretable semantic concepts emerge along the bases of sparse word representations. In order to have a broad framework for evaluation, we consider three general approaches for constructing sparse word representations, which are then evaluated in multiple ways. We propose a novel methodology to evaluate the semantic content of word embeddings using a commonsense knowledge base, applied here to the sparse case. This methodology is illustrated by two techniques using the ConceptNet knowledge base. The first approach assigns a commonsense concept label to the individual dimensions of the embedding space. The second approach uses a metric, derived by spreading activation, to quantify the coherence of coordinates along the individual axes. We also provide results on the relationship between the two approaches. The results show, for example, that in the individual dimensions of sparse word embeddings, words having high coefficients are more semantically related in terms of path lengths in the knowledge base than the ones having zero coefficients.

In this work, we study probably approximately correct (PAC) learning under general perturbation-based adversarial attacks. In the most basic setting, referred to as an evasion attack, the adversary's goal is to misclassify an honestly sampled point x by adversarially perturbing it into x̃, i.e., h(x̃) = ≠ c(x̃), where c is the ground truth concept and h is the learned hypothesis. The only limitation on the adversary is that x̃ is not “too far” from x, controlled by a metric measure. We first prove that for many theoretically natural input spaces of high dimension n (e.g., isotropic Gaussian in dimension n under ℓ2perturbations), if the adversary is allowed to apply up to a sublinear amount of perturbations in the expected norm, PAC learning requires sample complexity that is exponential in the data dimension n. We then formalize hybrid attacks in which the evasion attack is preceded by a poisoning attack in which a poisoning phase is followed by specific evasion attacks. Special forms of hybrid attacks include so-called “backdoor attacks” but here we focus on the general setting in which adversary's evasion attack is only controlled by a pre-specified amount of perturbation based on data dimension and aim to misclassifying the perturbed instances. We show that PAC learning is sometimes impossible under such hybrid attacks, while it is possible without the attack (e.g., due to the bounded VC dimension).

Many modern machine learning classifiers are shown to be vulnerable to adversarial perturbations of the instances. Despite a massive amount of work focusing on making classifiers robust, the task seems quite challenging. In this work, through a theoretical study, we investigate the adversarial risk and robustness of classifiers and draw a connection to the well-known phenomenon of “concentration of measure” in metric measure spaces. We show that if the metric probability space of the test instance is concentrated, any classifier with some initial constant error is inherently vulnerable to adversarial perturbations.One class of concentrated metric probability spaces are the so-called Lévy families that include many natural distributions. In this special case, our attacks only need to perturb the test instance by at most O(√n) to make it misclassified, where n is the data dimension. Using our general result about Lévy instance spaces, we first recover as special case some of the previously proved results about the existence of adversarial examples. However, many more Lévy families are known (e.g., product distribution under the Hamming distance) for which we immediately obtain new attacks that find adversarial examples of distance O(√n).Finally, we show that concentration of measure for product spaces implies the existence of forms of “poisoning” attacks in which the adversary tampers with the training data with the goal of degrading the classifier. In particular, we show that for any learning algorithm that uses m training examples, there is an adversary who can increase the probability of any “bad property” (e.g., failing on a particular test instance) that initially happens with non-negligible probability to ≈ 1 by substituting only Õe(√m) of the examples with other (still correctly labeled) examples.

Recently, Mahloujifar and Mahmoody (TCC’17) studied attacks against learning algorithms using a special case of Valiant’s malicious noise, called $p$-tampering, in which the adversary gets to change any training example with independent probability $p$ but is limited to only choose ‘adversarial’ examples with correct labels. They obtained $p$-tampering attacks that increase the error probability in the so called ‘targeted’ poisoning model in which the adversary’s goal is to increase the loss of the trained hypothesis over a particular test example. At the heart of their attack was an efficient algorithm to bias the average output of any bounded real-valued function through $p$-tampering. In this work, we present new biasing attacks for biasing the average output of bounded real-valued functions. Our new biasing attacks achieve in \emph{polynomial-time} the the best bias achieved by MM16 through an \emph{exponential} time $p$-tampering attack. Our improved biasing attacks, directly imply improved $p$-tampering attacks against learners in the targeted poisoning model. As a bonus, our attacks come with considerably simpler analysis compared to previous attacks. We also study the possibility of PAC learning under $p$-tampering attacks in the \emph{non-targeted} (aka indiscriminate) setting where the adversary’s goal is to increase the risk of the generated hypothesis (for a random test example). We show that PAC learning is \emph{possible} under $p$-tampering poisoning attacks essentially whenever it is possible in the realizable setting without the attacks. We further show that PAC learning under ‘no-mistake’ adversarial noise is \emph{not} possible, if the adversary could choose the (still limited to only $p$ fraction of) tampered examples that she substitutes with adversarially chosen ones. Our formal model for such ‘bounded-budget’ tampering attackers is inspired by the notions of (strong) adaptive corruption in secure multi-party computation.

We study adversarial perturbations when the instances are uniformly distributed over {0,1}^n. We study both "inherent" bounds that apply to any problem and any classifier for such a problem as well as bounds that apply to specific problems and specific hypothesis classes. As the current literature contains multiple definitions of adversarial risk and robustness, we start by giving a taxonomy for these definitions based on their direct goals; we identify one of them as the one guaranteeing misclassification by pushing the instances to the error region. We then study some classic algorithms for learning monotone conjunctions and compare their adversarial risk and robustness under different definitions by attacking the hypotheses using instances drawn from the uniform distribution. We observe that sometimes these definitions lead to significantly different bounds. Thus, this study advocates for the use of the error-region definition, even though other definitions, in other contexts with context-dependent assumptions, may coincide with the error-region definition. Using the error-region definition of adversarial perturbations, we then study inherent bounds on risk and robustness of any classifier for any classification problem whose instances are uniformly distributed over {0,1}^n. Using the isoperimetric inequality for the Boolean hypercube, we show that for initial error 0.01, there always exists an adversarial perturbation that changes O(√n) bits of the instances to increase the risk to 0.5, making classifier's decisions meaningless. Furthermore, by also using the central limit theorem we show that when n→∞, at most c√n bits of perturbations, for a universal constant c<1.17, suffice for increasing the risk to 0.5, and the same c√n bits of perturbations on average suffice to increase the risk to 1, hence bounding the robustness by c√n.

We consider exact real solving of well-constrained, bivariate systems of relatively prime polynomials. The main problem is to compute all common real roots in isolating interval representation, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of ÕB(N14) for the purely projection-based method, and ÕB(N12) for two subresultants-based methods: these ignore polylogarithmic factors, and N bounds the degree and the bitsize of the polynomials. The previous record bound was ÕB(N14).