With the help of an intricate geometric construction, we can prove that instance-wise cost functions quickly drive SVC to infinity.<\/h4>\n
In the previous article in this series<\/a>, we examined the concept of strategic VC dimension<\/em> (SVC) and its connection to the Fundamental Theorem of Strategic Learning<\/em>. We will make use of both of those in this article, alongside the ideas of achievable labelings<\/em> and strategic shattering coefficients<\/em> that we explored in the lead-up to\u00a0them.<\/p>\n Quantifying the Complexity and Learnability of Strategic Classification Problems<\/a><\/p>\n If you haven\u2019t read the <\/strong>first article in this series<\/strong><\/a> yet, I encourage you to start from there before moving on to the aforementioned article on\u00a0SVC:<\/strong><\/p>\n Extending PAC Learning to a Strategic Classification Setting<\/a><\/p>\n With the context from the other articles in this series in place, a basic grasp of set theory and geometry will be all you\u2019ll need to understand the theorem and its\u00a0proof.<\/strong><\/p>\n As we saw, SVC can be used as a tool to estimate the expressive power of a hypothesis class within a strategic classification context. Having carefully defined SVC as a generalization of the canonical VC dimension, we understand that the two have much in common. When, though, does SVC diverge from its canonical counterpart? Can we come up with a scenario in which the strategic aspect of a classification problem significantly increases its complexity? It turns out we can, with relative ease: linear classification.<\/strong><\/p>\n Linear classification involves determining whether a data point should be positively or negatively classified based on a linear function applied to its features. Geometrically, we can imagine a linear classifier inducing a linear decision boundary in d<\/em>-dimensional real space (\u211d\u1d48 <\/em>). Anything on one side of the boundary is positively classified, and anything on the other side is negatively classified. In one-dimensional space, the decision boundary is a threshold (as we saw in the previous article<\/a>). In two-dimensional space, it\u2019s a line dividing the plane. In general, it\u2019s a hyperplane<\/a>.<\/p>\n In canonical binary classification, the VC dimension of the hypothesis class comprising all linear classifiers in \u211d\u1d48 <\/em>is d + 1<\/em><\/strong>, which is finite.<\/strong> For example, for d<\/em> = 2 (linear classifiers in \u211d<\/strong>\u00b2), the VC dimension is 3. The Fundamental Theorem of Statistical Learning<\/a> dictates that canonical linear classification is therefore PAC learnable.\u207d\u00b9\u207e<\/strong><\/p>\n Intuitively, we might expect the same conclusion to hold for the strategic analog of the problem.<\/strong> After all, linear classifiers are some of the simplest classifiers there are, and reasoning about them can be rather natural.\u207d\u00b2\u207e<\/strong><\/p>\n However, that simplicity goes out the window as soon as we throw instance-wise<\/em> cost functions into the mix. As we will\u00a0prove:<\/strong><\/p>\n \nGiven a strategic linear classification problem S\u1d1b\u0280\u1d00\u1d04\u27e8<\/em>H, <\/em>R, <\/em>c\u27e9, <\/em>there exists an<\/em><\/strong> <\/em>instance-wise cost function<\/em><\/strong> <\/em>c(<\/em>z; <\/em>x)<\/em><\/strong> <\/em>= \u2113<\/em>\u2093(<\/em>z – x)<\/em><\/strong> <\/em>such that SVC(<\/em>H, <\/em>R, <\/em>c) =\u00a0<\/em>\u221e.<\/strong>\n<\/p><\/blockquote>\n In other words, using the Fundamental Theorem of Strategic Learning<\/em><\/a>, we find that linear classification in a strategic setting equipped with an instance-wise<\/em> cost function is not generally PAC learnable.<\/strong> Interestingly, it will not be PAC learnable even if we strip away as much complexity as we can. In this case, we will do so by focusing on strategic linear classification on the Cartesian plane ( X <\/em>\u2286 \u211d\u00b2) with the homogeneous preference class (R<\/em> = { 1\u00a0}).<\/strong><\/p>\n The more general conclusion will follow from the counterexample we will show under those simplifying conditions. <\/strong>If strategic linear classification is not PAC learnable in \u211d\u00b2, there is no way it could be PAC learnable in any higher dimension. Likewise, every other preference class we laid out in our setup is a strict generalization of the homogeneous preference class. If we could prove PAC learnability for any of those preference classes, we would also be able to do so for the simpler case where R<\/em> = { 1\u00a0}.<\/p>\n Based on the assumptions above, we begin by turning our attention to the special case S\u1d1b\u0280\u1d00\u1d04\u27e8H\u2097<\/em>, { 1 }, c<\/em>\u27e9, <\/strong>with H\u2097 <\/em>being the hypothesis class comprising all linear classifiers in \u211d\u00b2. We then initialize n<\/em> two-dimensional feature vectors at the origin: \u2200 i<\/em> \u2264 n\u00a0<\/em>. x\u1d62<\/em> = (0, 0). Since we\u2019re using the homogeneous preference class, we have that \u2200 i<\/em> \u2264 n\u00a0<\/em>. r\u1d62<\/em> = 1. The only difference between the data points will be in how our cost function behaves on each of them.<\/strong> This is where the crux of the proof lies, as we will soon\u00a0see.<\/p>\n Before we discuss the cost function at length, though, we need to geometrize <\/em>the <\/strong>possible labelings<\/strong><\/a> of our unlabeled data points.<\/strong> As we saw last time<\/a>, a set of n<\/em> unlabeled data points must have exactly 2\u207f<\/em> possible labelings.<\/strong> Representing a set of labelings (n<\/em>-tuples) geometrically in \u211d\u00b2 is relatively straightforward: we simply select an arbitrary point for each possible labeling. In particular, we will choose 2\u207f<\/em> such representative points<\/strong> on the unit circle<\/em>,<\/strong> each assigned to a possible labeling.<\/strong> While the particular coordinates of the representative points themselves are unimportant, we do <\/em>require that each such point be unique.<\/strong> We also require that no two points be origin-symmetric with respect to one\u00a0another.<\/p>\n We will denote this set of representative points by S<\/em>.<\/strong> Having selected our representative points, we use them to define the origin-symmetric set S\u2019,<\/em><\/strong> i.e., S\u2019<\/em> = { (-x<\/em>, –y<\/em>)\u00a0: (x<\/em>, y<\/em>) \u2208 S <\/em>}. Note that S<\/em> and S\u2019 <\/em>are disjoint (S<\/em> \u2229 S\u2019<\/em> = \u2205) as a consequence of how we selected the points in\u00a0S<\/em>.<\/p>\n For a particular x<\/em>\u1d62, we define S\u1d62 <\/em>as the subset of S that includes only the points that represent labelings in which x<\/em>\u1d62 is positively classified. <\/strong>Similarly, we derive the origin-symmetric S\u1d62\u2019 <\/em>\u2282 S\u2019<\/em> from S\u1d62<\/em>. In the example below, the points above the x<\/em>-axis are those representing labelings in which x<\/em>\u1d62 is positively classified, i.e., S\u1d62<\/em>. Those below the x<\/em>-axis comprise their origin-symmetric set S\u1d62\u2019<\/em> (with the numbering matching between symmetric pairs of points). Note that the selection of points above the x<\/em>-axis is completely arbitrary.<\/p>\n We proceed to construct a convex polygon G\u1d62<\/em>, with its vertices being the points in S\u1d62<\/em> \u222a S\u1d62\u2019<\/em>.<\/strong> The G\u1d62<\/em> for each unlabeled data point will be key in designing an instance-wise cost function c<\/em> with which we will always be able to achieve all possible labelings, thus showing that SVC(H\u2097<\/em>, { 1 }, c<\/em>) = \u221e. Towards this end, the convexity of G\u1d62 <\/em>will prove critical, as will its origin symmetry (stemming from our choice of S\u1d62\u2019\u00a0<\/em>).<\/p>\n For each of the n<\/em> origin-initialized, unlabeled data points we started with, we now have a convex, origin-symmetric polygon that represents the labelings in which it is positively classified. Each G\u1d62<\/em> can now be used to define the behavior of our instance-wise cost function c<\/em> on its corresponding x\u1d62<\/em>.<\/strong> We will use G\u1d62 <\/em>to define a seminorm\u207d\u00b3\u207e<\/strong>:<\/p>\n \u2225 <\/em>y \u2225<\/em>\u0262\u1d62 = inf { \u03b5 \u2208 <\/em>\u211d\u207a\u00a0: <\/em>y \u2208 \u03b5<\/em>G\u1d62\u00a0}<\/em><\/strong><\/p><\/blockquote>\n This definition implies that the distance between x\u1d62<\/em> and some point z<\/em> is less than 1 if and only if z <\/em>lies within G\u1d62.<\/em><\/strong>\u00a0I.e.:<\/p>\n \n\u2225 <\/em>z – x\u1d62 \u2225<\/em>\u0262\u1d62 < 1 \u21d4 <\/em>z \u2208\u00a0<\/em>G\u1d62<\/p><\/blockquote>\n For the rest of the proof, it is sufficient that we understand this connection between \u2225 \u22c5 \u2225\u0262\u1d62 <\/em>and a point being inside G\u1d62.<\/em><\/strong> <\/em>(See Footnote (3) for a discussion of why \u2225 \u22c5 \u2225\u0262\u1d62 <\/em>qualifies as a seminorm and for more details about its geometric interpretation.)<\/p>\n We thus define the instance-wise cost function\u00a0c<\/em>:<\/strong><\/p>\n c(<\/em>z; <\/em>x\u1d62) = \u2113<\/em>\u1d62(<\/em>z –\u00a0<\/em>x\u1d62)<\/em>\n<\/p><\/blockquote>\n Where:<\/strong><\/p>\n \n\u2113<\/em>\u1d62(<\/em>z – <\/em>x\u1d62) = \u2225 <\/em>z – <\/em>x\u1d62\u00a0\u2225<\/em>\u0262\u1d62<\/p><\/blockquote>\n That is, for each unlabeled data point x\u1d62<\/em>, c<\/em> behaves as \u2225 \u22c5 \u2225\u0262\u1d62 <\/em>would.<\/strong> Note that this behavior is different for each data point. This is because we constructed a unique G\u1d62 <\/em>for every x\u1d62<\/em>, and each \u2225 \u22c5<\/strong> \u2225\u0262\u1d62<\/em> is derived from its corresponding polygon\u00a0G\u1d62<\/em>.<\/p>\n With the instance-wise cost function c<\/em> in place, we may turn our attention to how our data points interact with linear classifiers.<\/strong> Recall that we have constrained our consideration to the homogeneous preference class, meaning that r<\/em> = 1 for all of our points. I.e., x\u1d62<\/em> stands to gain a reward of magnitude 1 for being positively classified. Given a linear classifier, each data point will thus be willing to incur any cost less than 1 to manipulate its feature vector to ensure it falls on the positive side of the decision boundary. <\/strong>This will guarantee it receives positive utility as a result of the manipulation.<\/p>\n c<\/em> is designed so that a data point with feature vector x\u1d62<\/em> has to pay \u2225 z<\/em> – x\u1d62<\/em> \u2225\u0262\u1d62<\/em> to change its feature vector to z<\/em>. As we saw, <\/strong>as long as z<\/em> lies inside G\u1d62<\/em>, this cost will be less than\u00a01.<\/p>\n Suppose we have a decision boundary that crosses G\u1d62 <\/em><\/strong>(intersects it at two points) with x\u1d62<\/em> falling on its negative half-plane.<\/em> As illustrated in Figure 3 below,<\/strong> this creates a sub-polygon such that for any z<\/em> within\u00a0it:<\/p>\nHow an Instance-Wise Cost Function Affects SVC: Stating the\u00a0Theorem<\/h4>\n
From Labelings to Points on the Unit Circle: Proof\u00a0Setup<\/h4>\n
![\"\"](\"https:\/\/i0.wp.com\/cdn-images-1.medium.com\/max\/776\/1%2A-AenB5mfrqb6jxd2y6XDEA.png?ssl=1\")
![\"\"](\"https:\/\/i0.wp.com\/cdn-images-1.medium.com\/max\/776\/1%2A5HfGStJrf3PXZAgA9U4jVA.png?ssl=1\")
Turning Polygons into Preferences: Constructing the Cost\u00a0Function<\/h4>\n
Data Point Best Response as a Result of the Cost\u00a0Function<\/h4>\n
\n