Finding classifiers robust to adversarial examples is critical for their safe deployment. Determining the robustness of the best possible classifier under a given threat model for a fixed data distribution and comparing it to that achieved by state-of-the-art training methods is thus an important diagnostic tool. In this paper, we find achievable information-theoretic lower bounds on robust loss in the presence of a test-time attacker for *multi-class classifiers on any discrete dataset*. We provide a general framework for finding the optimal $0-1$ loss that revolves around the construction of a conflict hypergraph from the data and adversarial constraints. The prohibitive cost of this formulation in practice leads us to formulate other variants of the attacker-classifier game that more efficiently determine the range of the optimal loss. Our valuation shows, for the first time, an analysis of the gap to optimal robustness for classifiers in the multi-class setting on benchmark datasets.

Understanding the fundamental limits of robust supervised learning has emerged as a problem of immense interest, from both practical and theoretical standpoints. In particular, it is critical to determine classifier-agnostic bounds on the training loss to establish when learning is possible. In this paper, we determine optimal lower bounds on the cross-entropy loss in the presence of test-time adversaries, along with the corresponding optimal classification outputs. Our formulation of the bound as a solution to an optimization problem is general enough to encompass any loss function depending on soft classifier outputs. We also propose and provide a proof of correctness for a bespoke algorithm to compute this lower bound efficiently, allowing us to determine lower bounds for multiple practical datasets of interest. We use our lower bounds as a diagnostic tool to determine the effectiveness of current robust training methods and find a gap from optimality at larger budgets. Finally, we investigate the possibility of using of optimal classification outputs as soft labels to empirically improve robust training.

We study the conditions that allow for the alignment of correlated databases with multivariate Gaussian features. We present some analysis tools that allow us to go beyond the achievability result for exact alignment and derive the condition for nearly-exact alignment. Our main theorem gives an expression for the order of magnitude of the error in alignment as a function of mutual information between features.

We consider the problem of aligning a pair of databases with jointly Gaussian features. We consider two algorithms, complete database alignment via MAP estimation among all possible database alignments, and partial alignment via a thresholding approach of log likelihood ratios. We derive conditions on mutual information between feature pairs, identifying the regimes where the algorithms are guaranteed to perform reliably and those where they cannot be expected to succeed.

While progress has been made in understanding the robustness of machine learning classifiers to test-time adversaries (evasion attacks), fundamental questions remain unresolved. In this paper, we use optimal transport to characterize the maximum achievable accuracy in an adversarial classification scenario. In this setting, an adversary receives a random labeled example from one of two classes, perturbs the example subject to a neighborhood constraint, and presents the modified example to the classifier. We define an appropriate cost function such that the minimum transportation cost between the distributions of the two classes determines the \emph{minimum $0-1$ loss for any classifier}. When the classifier comes from a restricted hypothesis class, the optimal transportation cost provides a lower bound. We apply our framework to the case of Gaussian data with norm-bounded adversaries and explicitly show matching bounds for the classification and transport problems and the optimality of linear classifiers. We also characterize the sample complexity of learning in this setting, deriving and extending previously known results as a special case. Finally, we use our framework to study the gap between the optimal classification performance possible and that currently achieved by state-of-the-art robustly trained neural networks for datasets of interest, namely, MNIST, Fashion MNIST and CIFAR-10.

We consider the problem of aligning a pair of databases with correlated entries. We introduce a new measure of correlation in a joint distribution that we call cycle mutual information. This measure has operational significance: it determines whether exact recovery of the correspondence between database entries is possible for any algorithm. Additionally, there is an efficient algorithm for database alignment that achieves this information theoretic threshold.

The existence of evasion attacks during the test phase of machine learning algorithms represents a significant challenge to both their deployment and understanding. These attacks can be carried out by adding imperceptible perturbations to inputs to generate adversarial examples and finding effective defenses and detectors has proven to be difficult. In this paper, we step away from the attack-defense arms race and seek to understand the limits of what can be learned in the presence of an evasion adversary. In particular, we extend the Probably Approximately Correct (PAC)-learning framework to account for the presence of an adversary. We first define corrupted hypothesis classes which arise from standard binary hypothesis classes in the presence of an evasion adversary and derive the Vapnik-Chervonenkis (VC)-dimension for these, denoted as the adversarial VC-dimension. We then show that sample complexity upper bounds from the Fundamental Theorem of Statistical learning can be extended to the case of evasion adversaries, where the sample complexity is controlled by the adversarial VC-dimension. We then explicitly derive the adversarial VC-dimension for halfspace classifiers in the presence of a sample-wise norm-constrained adversary of the type commonly studied for evasion attacks and show that it is the same as the standard VC-dimension, closing an open question. Finally, we prove that the adversarial VC-dimension can be either larger or smaller than the standard VC-dimension depending on the hypothesis class and adversary, making it an interesting object of study in its own right.

The capacity of a graph is defined as the rate of exponential growth of independent sets in the strong powers of the graph. In the strong power an edge connects two sequences if at each position their letters are equal or adjacent. We consider a variation of the problem where edges in the power graphs are removed between sequences which differ in more than a fraction δ of coordinates. The proposed generalization can be interpreted as the problem of determining the highest rate of zero undetected-error communication over a link with adversarial noise, where only a fraction δ of symbols can be perturbed and only some substitutions are allowed. We derive lower bounds on achievable rates by combining graph homomorphisms with a graph-theoretic generalization of the Gilbert-Varshamov bound. We then give an upper bound, based on Delsarte's linear programming approach, which combines Lovász' theta function with the construction used by McEliece et al. for bounding the minimum distance of codes in Hamming spaces.

In a symmetric-key cryptography system, it is often required to transmit a nonuniform message from a very large set. In this case, a computationally unbounded adversary can take advantage of the non-uniformity of the posterior to recover the message. Recently an encryption scheme called Honey Encryption has been proposed to increase the information-theoretic security of the system, i.e., guaranteed level of security regardless of the computational power of the adversary. In this paper, we present a technique called message partitioning which can be used to accomplish the same goal. We analyze the overall security of the combination of this technique with Honey Encryption, which uses a Distribution Transforming Encoder (DTE) block. We propose a new DTE which has an acceptable performance under limited amount of available auxiliary randomness. Achievable bounds are presented for both cases, which under certain conditions, are close to the lower bounds on the level of the success of the adversary.

We consider the problem of perfectly recovering the vertex correspondence between two correlated Erdos-Renyi (ER) graphs. For a pair of correlated graphs on the same vertex set, the correspondence between the vertices can be obscured by randomly permuting the vertex labels of one of the graphs. In some cases, the structural information in the graphs allow this correspondence to be recovered. We investigate the information-theoretic threshold for exact recovery, i.e. the conditions under which the entire vertex correspondence can be correctly recovered given unbounded computational resources. Pedarsani and Grossglauser provided an achievability result of this type. Their result establishes the scaling dependence of the threshold on the number of vertices. We improve on their achievability bound. We also provide a converse bound, establishing conditions under which exact recovery is impossible. Together, these establish the scaling dependence of the threshold on the level of correlation between the two graphs. The converse and achievability bounds differ by a factor of two for sparse, significantly correlated graphs.

Many of the classic problems of the coding theory are highly symmetric, which makes it easy to derive the sphere-packing upper bounds on the size of codes. We discuss the generalizations of the sphere-packing bounds to the arbitrary error models. These generalizations become especially important when the sizes of the error spheres are nonuniform. The best possible sphere-packing bounds are the solutions to the linear programs. We derive a series of bounds from the approximations to the packing and covering problems and study the relationships and the trade-offs between them. We show the method to obtain the upper bounds by optimizing across a family of channels that admit the same codes. We present a generalization of the local degree bound of Kulkarni and Kiyavash, and use it to improve the best-known upper bounds on the sizes of the single deletion correcting codes and the single grain error correcting codes.

We investigate deletion correcting codes and restricted composition codes in particular. Restricted composition codes generalize codes on permutations and multipermutations. We use graph theoretic methods to characterize codes, establish bounds on code size, and describe constructions. The substring partial order has a well-known property. For any string, the number of superstrings of a particular length depends only on the length of the original string. We generalize this property to take compositions into account. For any string, the number of superstrings of a particular composition depends only on the composition of the original string. We present a bijective proof of this fact. We apply this result to obtain a lower bound on the size of restricted composition codes. We obtain an upper bound by analyzing deletion errors when the composition of deleted symbols is restricted to a particular worst case composition. We construct binary restricted composition single-deletion correcting codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of restricted composition codes as long as the set of compositions used themselves form a code. The nonbinary single-deletion correcting codes constructed by Tenengolts are a special case of our method.

A combinatorial channel specifies a set of possible channel outputs for each channel input. A ranked partially ordered set, or ranked poset, gives us a notion of up errors and down errors. This allows us to define a variety of combinatorial channels. There is a family of channels that have the rank-n elements of the poset as the input, and introduce s total errors, each performing a different mixture of up errors and down errors. If a ranked poset has the “parallelogram property,” the family of channels all have the same confusion graph and thus the same codes. Furthermore, there is a natural metric on each rank of the poset. In the common confusion graph of the channel, vertices are adjacent if and only if their distance in this metric is at most 2s. Although all of the channels in the family have the same set of codes, each channel corresponds to a different integer linear program that characterizes the set of codes. Because each integer linear program has a different fractional relaxation, each leads to a different sphere-packing upper bound for the codes. We take advantage of this phenomenon by optimizing across the family of channels to obtain the best bound. This formulation includes many of classical error models, including erasures and substitutions in q-ary vectors, Hamming errors in constant weight binary codes, insertions and deletions in q-ary strings, the error model of subspace codes, the natural error model for compositions, and various errors models for permutations.

A code for a combinatorial channel is a feasible point in an integer linear program derived from that channel. Sphere-packing upper bounds are closely related to the fractional relaxation of this program. When bounding highly symmetric channels, this formulation can often be avoided, but it is essential in less symmetric cases. We present a few low-complexity upper bounds on the value of the relaxed linear program. We also discuss a more general bound derived from the codeword constraint graph for the channel. This bound is not necessarily computationally tractable. When there is a family of channels with the same constraint graph, tractable bounds can be applied to each channel and the best bound will apply to the whole family.

We consider deletion correcting codes over a q-ary alphabet. It is well known that any code capable of correcting s deletions can also correct any combination of s total insertions and deletions. To obtain asymptotic upper bounds on code size, we apply a packing argument to channels that perform different mixtures of insertions and deletions. Even though the set of codes is identical for all of these channels, the bounds that we obtain vary. Prior to this paper, only the bounds corresponding to the all-insertion case and the all-deletion case were known. We recover these as special cases. The bound from the all-deletion case, due to Levenshtein, has been the best known for more than 45 years. Our generalized bound is better than Levenshtein's bound whenever the number of deletions to be corrected is larger than the alphabet size.

We consider deletion correcting codes over a q-ary alphabet. It is well known that any code capable of correcting s deletions can also correct any combination of s total insertions and deletions. To obtain asymptotic upper bounds on code size, we apply a packing argument to channels that perform different mixtures of insertions and deletions. Even though the set of codes is identical for all of these channels, the bounds that we obtain vary. Prior to this work, only the bounds corresponding to the all insertion case and the all deletion case were known. We recover these as special cases. The bound from the all deletion case, due to Levenshtein, has been the best known for more than forty five years. Our generalized bound is better than Levenshtein's bound whenever the number of deletions to be corrected is larger than the alphabet size.

We take a graph theoretic view of deletion correcting codes. The problem of finding an n-bit s-deletion correcting code is equivalent to finding an independent set in a particular graph. We discuss the relationship between codes and colorings and demonstrate that the VT codes are optimal in a coloring sense. We describe a method of partitioning the set of bit strings by Hamming weight and finding codes within each partition. In the single deletion case, we find an optimal coloring of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We also prove a lower bound on size of codes constructed using these partitions for any number of deletions.