[1910.07423] On the Global Optima of Kernelized Adversarial Representation Learning
Numerical experiments on multiple datasets indicated that the global optima solution of the “kernel” form of ARL is able to obtain a trade-off between utility and invariance that is comparable to that of local optima solutions of deep neural network based ARL

Abstract Adversarial representation learning is a promising paradigm for obtaining data representations that are invariant to certain sensitive attributes while retaining the information necessary for predicting target attributes. Existing approaches solve this problem through iterative adversarial minimax optimization and lack theoretical guarantees. In this paper, we first study the “linear” form of this problem i.e., the setting where all the players are linear functions. We show that the resulting optimization problem is both non-convex and non-differentiable. We obtain an exact closed-form expression for its global optima through spectral learning and provide performance guarantees in terms of analytical bounds on the achievable utility and invariance. We then extend this solution and analysis to non-linear functions through kernel representation. Numerical experiments on UCI, Extended Yale B and CIFAR-100 datasets indicate that, (a) practically, our solution is ideal for “imparting” provable invariance to any biased pre-trained data representation, and (b) empirically, the trade-off between utility and invariance provided by our solution is comparable to iterative minimax optimization of existing deep neural network based approaches. Code is available at https: //github.com/human-analysis/Kernel-ARL
‹

y_hat == Theta_y * z + b_y, s_hat == Theta_s * z + b_s

Figure 1: Adversarial Representation Learning consists of three entities, an encoder E that obtains a compact representation z of input data x, a predictor T that predicts a desired target attribute y and an adversary that seeks to extract a sensitive attribute s, both from the embedding z. (Introduction)Figure 2: Overview: Illustration of adversarial representation learning for imparting invariance to a fixed biased pretrained image representation x = F(x0 ; ΘF ). An encoder E, in the form of a kernel mapping, produces a new representation z. A target predictor and an adversary, in the form of linear regressors, operate on this new representation. We theoretically analyze this ARL setup to obtain a closed form solution for the globally optimal parameters of the encoder ΘE. Provable bounds on the achievable trade-off between the utility and fairness of the representation are also derived. (Introduction)Figure 3: Geometric Interpretation: An illustration of a three-dimensional input space x and one-dimensional target and adversary regressors. Therefore, both Cxs and Cxy are one-dimensional. We locate the y-axis in the same direction as Cxs. The feasible space for the solution GE = ΘT E imposed by the constraint Js(ΘE) ≥ α corresponds to the region outside the cone (specified by Cs and α) around Cxs. The non-convexity of the problem stems from the nonconvexity of this feasible set. The objective min Jy(ΘE) corresponds to minimizing the angle between the line Cxy and the plane G. When Cxy is outside the cone, the line Cxy itself or any plane that contains the line Cxy and does not intersect with the cone, is a valid solution. When Cxy is inside the cone, the solution is either a line or, as we illustrate, a tangent hyperplane to the cone that is closest to Cxy. The non-differentiability stems from the fact that the solution can either be a plane or a line. (The Linear Case)Figure 4: Samples from a mixture of four Gaussians. Each sample has two attributes, shape and color. (Mixture of Four Gaussians)Figure 5: Color (λ = 0) Figure 6: Color (λ = 0.5) Figure 7: Color (λ = 1) Figure 8: Color (λ = 0.5) Figure 9: Shape (λ = 0) Figure 10: Shape (λ = 0.5) Figure 11: Shape (λ = 1) Figure 12: Shape (λ = 0.5) Figure 13: Gaussian Mixture: The optimal dimensionality of embedding z is 1. Visualization of the embedding histogram w.r.t each attribute for different relative emphasis, λ, on the target (shape) and sensitive attributes (color). Top row is color and bottom row is shape. First three columns show results for a linear-encoder. At λ = 0 the weight on the adversary is 0, so color is still separable. As the value of λ increases, we observe that the colors are less and less separable. Last column shows results for a kernel-encoder. Visualization of the embedding histogram for λ = 0.5. We observe that the target attribute is quite separable while the sensitive attribute is entangled. (Mixture of Four Gaussians)Figure 14: Gaussian Mixture: Trade-off between target performance and leakage of sensitive attribute by adversary. (Mixture of Four Gaussians)Figure 15: Linear-SARL Figure 16: Kernel-SARL Figure 17: Gaussian Mixture: Lower and upper bounds on adversary loss, αmin and αmax, computed on training set. The loss achieved by our solution as we vary λ is shown on the training and testing sets, αtrain and αtest, respectively. (Mixture of Four Gaussians)Figure 18: Adult Dataset: Magnitude of learned encoder weights ΘE for each semantic input feature. (Fair Classification)Figure 19: CIFAR-100: Trade-off between target performance and leakage of sensitive attribute by adversary. (CIFAR-100)Figure 20: Linear-SARL Figure 21: Kernel-SARL Figure 22: CIFAR-100: Lower and upper bounds on adversary loss, αmin and αmax, computed on training set. The loss achieved by our solution as we vary λ is shown on the training and testing sets, αtrain and αtest, respectively. (CIFAR-100)Figure 23: CIFAR-100: Optimal embedding dimensionality learned by SARL. At small values of λ, the objective favors the target task which predicts 20 classes. Thus, embedding dimensionality of 19 is optimal for a linear target regressor. At large values of λ, the objective only seeks to hinder the adversary. Thus, SARL determines the optimal dimensionality of the embedding as one. (CIFAR-100)Figure 24: Kernelized Adversarial Representation Learning consists of four entities, a kernel φx(·), an encoder E that obtains a compact representation z of the mapped input data φx(x), a predictor T that predicts a desired target attribute y and an adversary that seeks to extract a sensitive attribute s, both from the embedding z. (Non-linear Extension Through Kernelization)›