In this chapter we describe reverse-engineering attacks (REAs) on classifiers and defenses against them. REAs involve querying (probing) a classifier to discover its decision rules. One primary application of REAs is to enable TTEs. Another is to reveal a private (e.g., proprietary) classifier’s decision-making. For example, an adversary may seek to discover the workings of a military automated target-recognition system. Early work demonstrates that, with a modest number of (random) queries, which do not rely on any knowledge of the nominal data distribution, one can learn a surrogate classifier on a given domain that closely mimics an unknown classifier. However, a critical weakness of this attack is that random querying makes the attack easily detectable – randomly selected query patterns will typically look nothing like legitimate examples. They are likely to be extreme outliers of all the classes. Each such query is thus individually highly suspicious, let alone thousands or millions of such queries (required for accurate reverse-engineering). However, more recent REAs, which are akin to active learning strategies, are stealthier. Here, we use the ADA method (developed in Chapter 4 for TTE detection) to detect REAs. This method is demonstrated to provide significant detection power against stealthy REAs.

This chapter considers a different, although closely related method. In this approach, we first bound the expectation of the supremum of an underlying empirical process using the so-called Rademacher complexity, and then use concentration inequalities to obtain high-probability bounds. This approach simplifies various derivations in generalization analysis.

This chapter derives covering number estimates of certain function classes, including some parametric and nonparametric function classes. They can be used to bound the complexity of various machine learning problems.

In practical applications, we often try many different model classes (such as SVM, neural networks, decision trees), and we want to select the best model to achieve the smallest test loss. This problem is referred to as model selection. This chapter studies techniques used to analyze model selection problems.

This chapter introduces the concept of covering numbers and uniform convergence, and using them to analyze the generalization of machine learning algorithms.

Introduction to the book material.

In the standard multiarmed bandit problem, one observes a fixed number of arms. To achieve optimal regret bounds, one estimates confidence intervals of the arms by counting. In the contextual bandit problem, one observes side information for each arm, which can be used as features for more accurate confidence interval estimation. This chapter studies contextual bandit problems with both linear and nonlinear models

For bandit problems, we consider the so-called partial information setting, where only the outcome of the action taken is observed. In this chapter, we will investigate some bandit algorithms that are commonly used.

This chapter studies the basic mathematical tools to estimate tail probabilities of sums of random variables by using exponential moment estimates.

In Chapter 14, we introduced the basic definitions of online learning, and analyzed a number of first-order algorithms. In this chapter, we consider more advanced online learning algorithms that inherently exploit second-order information.

The idea of reproducing kernel Hilbert space (RKHS), was popularized in machine learning through support vector machines (SVMs) in the 1990s. This chapter presents an overview of RKHS kernel methods and their theoretical analysis.

In practical applications, we typically solve the empirical risk minimization problem using optimization methods such as stochastic gradient descent (SGD). Such an algorithm searches a model parameter along a path that does not cover the entire model space. Therefore the empirical process analysis may not be optimal to analyze the performance of specific computational procedures. In recent years, another theoretical tool, which we may refer to as stability analysis, has been proposed to analyze such computational procedures.

In this chapter, we focus on additive models that can be regarded as the sum of base models. The goal of additive model is to find a combination of models such that the combined model is more accurate than the base models.