Minimax Filter: Learning to Preserve Privacy from Inference Attacks

Preserving privacy of continuous and/or high-dimensional data such as images, videos and audios, can be challenging with syntactic anonymization methods which are designed for discrete attributes. Differential privacy, which provides a more formal definition of privacy, has shown more success in sanitizing continuous data. However, both syntactic and differential privacy are susceptible to inference attacks, i.e., an adversary can accurately infer sensitive attributes from sanitized data. The paper proposes a novel filter-based mechanism which preserves privacy of continuous and high-dimensional attributes against inference attacks. Finding the optimal utility-privacy tradeoff is formulated as a min-diff-max optimization problem. The paper provides an ERM-like analysis of the generalization error and also a practical algorithm to perform the optimization. In addition, the paper proposes an extension that combines minimax filter and differentially-private noisy mechanism. Advantages of the method over purely noisy mechanisms is explained and demonstrated with examples. Experiments with several real-world tasks including facial expression classification, speech emotion classification, and activity classification from motion, show that the minimax filter can simultaneously achieve similar or better target task accuracy and lower inference accuracy, often significantly lower than previous methods.


Introduction
Privacy is an important issue when data collected from or related to individuals are analyzed and released to a third party. In response to growing privacy concerns, various methods for privacy-preserving data publishing have been proposed (see Fung et al. (2010) for a review.) Syntactic anonymization methods, such as k-anonymity (Sweeney, 2002) and l-diversity (Machanavajjhala et al., 2007) focus on anonymization of quasi-identifiers and protection of sensitive attributes in static databases. However, it is known that syntactic anonymization is susceptible to several types of attacks such as the DeFinetti attack (Kifer, 2009). An adversary may be able to accurately infer sensitive attributes of individuals from insensitive, sanitized attributes. High-dimensional data also poses a challenge for syntactic anonymization methods. For example, k-anonymity is known to be ineffective for high-dimensional sparse databases (Narayanan and Shmatikov, 2008). In addition, syntactic anonymization methods are designed for discrete attributes. Discretizing continuous attributes by binning To preserve privacy of continuous high dimensional data from inference attacks, this paper proposes an approach which differs significantly from previous syntactic or differentiallyprivate approaches. Consider a scenario where a social media user wants to obfuscate all faces in her picture with minimal distortion before posting the picture online. The obfuscation mechanism proposed in the paper is a type of filtering of the original features by a non-invertible transformation. How to choose an optimal filter is explained in the following general description. Once the filtered data (e.g., obfuscated pictures) are released, an adversary will try to infer sensitive or identifying attributes from the data in particular using machine learning predictors. Therefore the data owner needs a filter that can minimize the maximum accuracy that any adversary may achieve in predicting the sensitive or identifying attributes. This is an instance of minimax games between the data owner and the adversary. The privacy of filtered data is measured by expected risk of adversarial algorithms on specific inference tasks such as identification. However, if privacy is the only goal, near-perfect privacy is achievable with a simple mechanism that sends no or garbage data, which has no utility for any party. To avoid those trivial solutions, (dis)utility of filtered data needs to be considered as the second goal. Disutility can be measured by the amount of distortion of the original data after filtering. Alternatively, if there are particular tasks of interest to be performed on the data by non-adversarial analysts, then again the expected risk of the target tasks can be used as disutility. The two goals -achieving privacy and utility -are often mutually conflicting, and finding an optimal tradeoff between the two is a central question in privacy research (see Related work). This paper proposes to minimize the difference of two risks by the minimax optimization of (6), and will refer to an optimal solution as minimax filter. Several methods of continuous minimax optimization have been used in the literature, including the method by Kiwiel (1987) used in Hamm (2015). The paper presents a simpler optimization method based on the classic theorem of Danskin (1967).
A notable assumption this paper makes is that the training data for computing an optimal filter are independent of the test data. For example, there are publicly available data sets that can be used to compute minimax filters such as those from the UCI data repository. As the training data set is already public information, the paper considers only the privacy of the subjects who use the filter at test time. (A similar assumption is used by Hamm et al. (2016) for knowledge transfer.) After the filter is learned from training data, a new test subject can use the filter to obfuscate her data by herself without requiring a third party to collect and process her raw data. Note that this setting is analogous to the setting of local differential privacy (Duchi et al., 2013) where the entity that collects data is not trusted. Since the training procedure can only access empirical risks, the performance of the filter on test data is given in the form of expectation/probability. The paper presents an analysis of generalization error for empirical minimax optimizers in analogy with the analysis of empirical risk minimizers (ERM).
The goal of minimax filter is to prevent inference attacks, and its privacy guarantee is quite different from those of other privacy mechanisms. It is task-dependent and is given in probability or expectation rather than given absolutely, which may be considered weaker than other privacy criteria such as differential privacy. Furthermore, the sanitized data whose sensitive information is filtered out may become unsafe in the future if people's perception of which attribute is sensitive changes over time. Since the goal of minimax filter and the goal of differential privacy are very different, it is natural to ask if the two methods can be combined to take advantages of both methods. Consequently, this paper presents an extension of minimax filter called noisy minimax filter, which combines the filter with additive noise mechanism to satisfy the differential privacy criterion. Two methods of combination-preprocessing and postprocessing-are proposed (see Fig. 2.) In the preprocessing approach, minimax filter is applied before perturbation to reduce the sensitivity of transformed data, so that the same level of differential privacy is achieved with less noise. Similar ideas have been utilized before, where data are transformed by Discrete Fourier Transform (Rastogi and Nath, 2010) and by Wavelet Transform (Xiao et al., 2011) before noise is added. In the postprocessing approach, minimax filter is applied after perturbation, and its performance is compared with the preprocessing approach.
Minimax filter and its extensions are evaluated with several real-world tasks including facial expression classification, speech emotion classification, and activity classification from motion. Experiments show that publicly available continuous and high-dimensional data sets are surprisingly susceptible to subject identification attacks, and that minimax filters can reduce the privacy risks to near chance levels without sacrificing utility too much. Experiments with noisy minimax filter also yield intuitive results. Differential privacy and resilience to inference attack are indeed different goals, such that using differentially private mechanism alone to achieve the latter requires a large amount of noise that destroys utility of data. In contrast, minimax filters can suppress inference attack with little loss of utility with or without perturbation. Therefore, adding a small amount of noise to the minimax filter can provide a formal differential privacy to a degree and also high on-average taskdependent utility and privacy against inference attacks.
To summarize, the paper has the following contributions.
• The paper proposes a novel filtering approach which preserves privacy of continuous and high-dimensional attributes against inference attacks. This mechanism is different from previous mechanisms in many ways; in particular, it is a learning-based approach and is task-dependent. • The paper measures utility and privacy by expected risks, and formulates the utilityprivacy tradeoff as a min-diff-max optimization problem. The paper provides an ERM-like analysis of the generalization performance of empirical optimizers. • The paper presents a practical algorithm which can find minimax filters for a broad family of filters and losses/classifiers. The proposed optimization algorithm and supporting classes can be found on the open-source repository 1 . • The paper proposes preprocessing and postprocessing approaches to combine minimax filter with noisy mechanisms. The resulting combination can achieve resilience to inference attacks and differential privacy at the same time. • The paper evaluates proposed algorithms on real-world tasks and compare them with representative algorithms from the literature.
The rest of the paper is organized as follows. Sec. 2 compares the proposed approach further with previous approaches. Sec. 3 presents minimax filters and analyzes its generalization performance on test data. Sec. 4 explains the difficulty of solving general minimax problems, and present a simple alternating optimization algorithm. Sec. 5 presents noisy minimax filters and two methods of perturbation by additive noise. Sec. 6 evaluates minimax filters with three data sets compared to non-minimax approaches and also evaluates noisy minimax filters under varying levels of privacy. Sec. 7 concludes the paper with discussions.

Related work
Optimal utility-privacy tradeoff is one of the main questions in privacy research. Utilityprivacy tradeoff has particularly been well-studied under differential privacy assumptions (Dwork and Nissim, 2004;Dwork, 2006), in the context of the statistical estimation (Smith, 2011;Alvim et al., 2012;Duchi et al., 2013) and learnability (Kasiviswanathan et al., 2011).
Other measures of privacy and utility were also proposed. Information-theoretic quantities were proposed by Sankar et al. (2010); Rebollo-Monedero et al. (2010); du Pin Calmon and Fawaz (2012) who analyzed privacy in terms of the rate-distortion theory in communication. One problem with using mutual information or related quantity is that it is difficult to estimate mutual information of high-dimensional and continuous variables in practice without assuming a simple distribution. In contrast, this paper proposes to use classification or regression risks to measure privacy and utility, which is directly computable from data without making assumptions on the distribution. Regarding the use of risks in this paper, classification error-based quantities have been suggested in the literature (Iyengar, 2002;Brickell and Shmatikov, 2008;Li and Li, 2009). However, privacy in these works is measured either by syntactic anonymity or probabilistic divergence which are appropriate mainly for discrete attributes. In this paper, privacy and utility are both defined with risks and are therefore directly comparable when defining the tradeoff of the two. Furthermore, the proposed method explicitly preserves privacy against inference attacks, which 1. https://github.com/jihunhamm/MinimaxFilter both syntactic and differentially-private methods are known to be susceptible to (Cormode, 2011).
Most of the aforementioned works focused on the analyses of utility-privacy tradeoff using different measures and assumptions. Few studied efficient algorithms to actively find optimal tradeoff which this paper aims to do. For discrete variables, Krause and Horvitz (2008) studied the NP-hardness of optimal utility-privacy tradeoff in discrete attribute selection, and demonstrated near-optimality of greedy selection. In particular, they used a weighted difference of utility and privacy cost as the joint cost similar to this work. Ghosh et al. (2009) proposed geometric mechanism and linear programming to achieve near-optimal utility for unknown users. However, optimization problems for discrete distributions are quite different from the problems involving high-dimensional and/or continuous distributions.
Algorithms for preserving privacy of high-dimensional face images has been proposed previously. Newton et al. (2005) applied k-anonymity to images; Enev et al. (2012) proposed to learn a linear filter using Partial Least Squares to reduce the covariance between filtered data and private labels; Whitehill and Movellan (2012) also proposed a linear filter using the log-ratio of the Fisher's Linear Discriminant Analysis metrics. Xu et al. (2017) presented a related method of preserving privacy of linear predictors using the Augmented Fractional Knapsack algorithm. This paper differs from these in several aspects: it is not limited to linear filters and is applicable to arbitrary differentiable nonlinear filters such as multilayer neural networks; it directly optimizes the utility-privacy risk instead of optimizing heuristic criteria such as covariance differences or LDA log-ratios.
The noisy minimax filter proposed in Sec. 5 bears a resemblance to the work of Rastogi and Nath (2010) and Xiao et al. (2011). Rastogi and Nath (2010) presented a differentially private method of answering queries on time-series data. They used Discrete Fourier Transform to reduce the data dimension and homomorphic encryption to perform distributed noise addition, which outperformed the naive noise addition method. Xiao et al. (2011) presented a differentially private range-counting method where they used wavelets to transform the data before adding noise. Effectiveness of the method was analyzed and also demonstrated empirically. The noisy minimax filter presented in this paper, especially the preprocessing approach, is similar in concept to those works in that the combination of data transformation and perturbation is used to enhance utility. However, the transform in this paper (i.e., the minimax filter) is learned from data for specific tasks unlike the Fourier or the Wavelet transform.
Lastly, the alternating optimization algorithm (Alg. 1) presented in this paper is related to the algorithm proposed by Goodfellow et al. (2014), which solves a different problem. The algorithm in this paper solves a min-diff-max problem to find an optimal utility-privacy tradeoff, while Goodfellow et al. (2014) solve a minimax problem to learn generative models.
Parts of this paper have appeared in conference proceedings (Hamm, 2015(Hamm, , 2017. New materials in this paper include reformulations of concepts and terms, ERM-like analysis of generalization error, new closed-form examples for minimax optimization, and an alternating optimization algorithm to solve minimax problems.

Minimax Filter
In this section, the formulation of minimax filter is presented and discussed in detail, and its generalization error is analyzed.

Formulation
Minimax filter is a non-invertible transformation of raw features/attributes such that the transformed data has optimal utility-privacy tradeoff. Non-invertibility is assumed so that original features are not always recoverable from the filtered data. Let's assume the filter is deterministic; randomize filters will be discussed in Sec. 5. Let X ⊂ R D be the space of features/attributes as real-valued vectors. Note that discrete attributes can also be represented by real vectors, e.g., by one-hot vector. Let the filter be a map which continuous in x and is continuously differentiable w.r.t. the parameter u ∈ U. Given a filtered output g(x), an adversary can make a prediction h p (g(x); v) of a private variable y which can be an identifier (e.g., subject number) or a sensitive attribute (e.g., religious beliefs). The prediction function h p (g(x); v) parameterized by v ∈ V is assumed to be continuous in v and continuously differentiable w.r.t. the input g(x). The paper proposes to use expected risk to measure the privacy of filtered output against adversarial inference: where l p (·) is a continuously differentiable loss function. From the assumptions above, f priv is continuously differentiable w.r.t. the filter parameter u. Trivial solutions to maximize privacy already exist, which are the filters that output random or constant numbers independent of actual data. However, such filters have no utility whatsoever for any party. To avoid such trivial solutions, it is necessary to consider the secondary goal of maximizing utility. Let z be a target variable that is of interest to the subjects and analysts (e.g., as medical diagnosis.) An analyst can make a prediction h u (g(x); w) parameterized by w ∈ W, which is assumed to be continuous in w and continuously differentiable w.r.t. the input g(x). The (dis)utility of the filtered output for a non-adversarial analyst can also be measured by the expected risk where l u (·) is a continuously differentiable loss function, such that f util is continuously differentiable w.r.t. the filter parameter u. To facilitate analysis, the paper assumes that the constraint sets W, V, and U are compact and convex subsets of Euclidean spaces such as a ball with a large but finite radius. Along with the assumption that the filter g and the risks f priv and f util are all continuous, min and max values are bounded and attainable. In addition, the solutions to min or max problems are assumed to be in the interior of W, V, and U, enforced by adding appropriate regularization (e.g, λ w 2 ) to the optimization problems if necessary. For this reason, min or max problems that appear in the paper will be treated as unconstrained and the notations u ∈ U, v ∈ V, and w ∈ W will be omitted.
Having defined the privacy and utility measure, the goal of a filter designer is to find a filter that achieves two objectives. The first objective is to maximize privacy where min v f priv (u, v) represents the risk of the worst (i.e., most capable) adversary: the smaller the risk, the more accurately can she infer private variables. As mentioned above, this problem alone has a trivial solution such as a constant filter that outputs zeros. The second objective is to minimize disutility where min w f util (u, w) represents the risk of the best analyst: the smaller the risk, the more accurately can the analyst predict variables of interest. To achieve the two opposing goals, one solves the joint problem which is to minimize a weighted sum or equivalently a weighted difference The constant ρ > 0 determines the relative importance of utility versus privacy. For a small ρ 1, the problem is close to a trivial privacy-only task, and for a large ρ 1, the problem is close to a utility-only task. The solution to (6) or (7) will be referred to as Minimax filter 2 and is by definition an optimal filter for utility-privacy tradeoff in terms of expected risks given the family of filters and the family of losses/classifiers. Note that the choice of filter and loss/classifier families is very flexible, with the assumption of differentiability only. In practice, almost-everywhere differentiability suffices to use the algorithm in the paper. Fig. 1 shows an example filter/classifier from the class of multilayer neural networks. As an aside, the joint problem may be formulated as minimization of disutility with a hard constraint on privacy risk. When using interior-point methods, the procedure is similar to solving (7) iteratively with an increasing ρ, which is more demanding than minimizing the weighted sum only once as the paper proposes.

Notes on private and utility tasks
The private variable y can be any attribute which is considered sensitive or identifying. For example, let y be any number or string unique to a person in the data set. Such identifiers are bijective with {1, ..., S}, where S is the total number of subjects, so assume y ∈ {1, ..., S}. The private task for an adversary is then to predict the identity y from the filtered data g(x), whose inaccuracy is measured by the expected risk of the identification task. That is, the less accurate the private classifier is, the more anonymous the filtered output is. The identity variable can also be group identifiers, e.g., y is a demographic Figure 1: Minimax filter with a filter/classifiers from the class of multilayer neural networks.
grouping based on age, sex, ethnicity, etc. Another example of private tasks is to single-out a particular subject among the rest, in which case y is binary: y = −1 means 'not the target subject' and y = 1 means 'target subject'. To summarize, anonymity of filtered data in this paper means resilience to inference attacks on any identity variable y that we choose, and is no different from attacks on other non-identity type variables. This unifying approach is convenient since we need not determine whether an attribute is an identifier, a quasi-identifier or a sensitive attribute as in syntactic anonymization. Any information hidden in the continuous high-dimensional features which are relevant to the private variable y-whatever it may be-will be filtered out by construction.
Similarly, the target variable z of interest can be any attribute that is not the same as the private variable y. In the pathological case where they are the same (z = y), the objective (7) becomes which is either a trivial privacy-only problem when 0 ≤ ρ < 1, or a utility-only problem when ρ > 1. In general, z and y will be correlated to a certain degree, and the minimax filter will find the best compromise of utility and privacy risks. Also, private and target tasks need not be classification tasks only. Regression tasks can also be used as a target task, as well as unsupervised tasks that do not require label z. Unsupervised tasks are useful when the target task is unknown or non-specific. Without such knowledge, one can use least-squares autoencoding of original features as the target task where g(x; u) and h(·; w) are a encoder and a decoder respectively, such as a nonlinear autoencoder constructed from multilayer neural networks.

Multiple tasks
Extension to multiple private and target tasks is straightforward.
.., f Nu util (u, w N u ) associated with target random variables z 1 , ..., z N u . If κ 1 , ..., κ N p are the coefficients representing relative importance of private tasks, and ρ 1 , ..., ρ N u are the coefficients for utility tasks, then the joint goal is to solve the following problem Since this can be rewritten as a multiple task problem is nearly identical to the original single task problem (6), with the new utility and privacy tasks defined aŝ with ρ = 1. Using this, it is straightforward to extend the analysis and algorithms developed for single tasks to those for multiple tasks.

Generalization performance of minimax filter
The proposed privacy mechanism is a learning-based approach. An optimal filter is one that solves the expected risk optimization (6). However, in reality, an optimal filter has to be estimated from finite training samples, and we need a guarantee on the performance of the learned filter on unseen test samples. This section derives generalization bounds for empirical minimax filter, similarly to the bounds for empirical risk minimization (ERM). The joint problem for expected risks was (14) A joint loss l J is introduced for convenience: Let (u * , v * , w * ) be a solution to the expected risk optimization problem: where E D [·] is the expected value w.r.t. the unknown data distribution P (x, y). Similarly, let (û,v,ŵ) be a solution to the empirical risk minimax problem: where the empirical mean The goal in this analysis is to show that the expected and the empirical optimizers perform equally well in expectation/probability given enough training samples: The main result is the Theorem 4 which is proved in the remainder of this section. Let's define optimal parameters v(u) and w(u) given u as One can then write and similarly (24) From these definitions we have for all u, Also from definition, for all (u, v, w), These observations imply the following theorem.
Theorem 1 The risk difference of expected and empirical optimizers is at most twice of the largest difference of expected and empirical risks of any set of parameters: Proof The expected risk of empirical risk optimizers (û,v,ŵ) is upper-bounded by the risk of expected risk optimizers (u * , v * , w * ) as follows: (26)) (27)) (28)) The difference can also be lower-bounded as follows: (25)) (28)) (27)) To bound the RHS of (29), one can use the Rademacher complexity theory (e.g., Lemma 26.2 of Shalev-Shwartz and Ben-David (2014).) Lemma 2 Let F be a class of real-valued functions, and let S be a set of N samples where R(F • S) is the empirical Rademacher complexity Consider the class of real-valued functions defined from the joint loss (15): Let R(l J • H J • S) denote the empirical Rademacher complexity of the joint loss class. Furthermore, the Rademacher complexity of sum of functions can be upper-bounded by the sum of complexities: Lemma 3 The empirical Rademacher complexity of the joint privacy-utility loss is upperbounded as From Theorem 1 and Lemmas 2 and 3, we get the following generalization bounds in terms of the Rademacher complexity.
Theorem 4 A probabilistic bound instead of expected value can also be obtained by applying McDiarmid's inequality, which is omitted. The Rademacher complexity of privacy and utility losses depends on our choice of loss functions, hypothesis classes, and filter classes. For the simple case of linear filters and linear classifiers, one can compute the complexity using the following lemmas (26.9 and 26.10 from Shalev-Shwartz and Ben-David (2014)): Lemma 6 For the class of linear classifiers H = {x → w T x : w 2 ≤ 1}, .
From these lemmas and Theorem 4, we have a corollary for a simple case of linear filters and classifiers.
Corollary 7 Let the loss functions l u and l p be α-Lipschitz (e.g., α = 1 for logistic regression.) Suppose U is a d × D real matrix with a bounded norm U 2 ≤ 1, and w and v are vectors with bounded norms ( w 2 ≤ 1 and v 2 ≤ 1). If the feature domain X is also bounded with a radius r = max x∈X x 2 , then we have Alternatively, one can use the VC dimension to specify the bound.
In any case, the generalization bounds in this section justify the claim that minimax filter can preserve utility-privacy of not only the current data but also the unseen test data in expectation/probability.

Minimax Optimization
This section presents theoretical and numerical solutions of the joint problem (7), which is a variant of unconstrained continuous minimax problems. (See Rustem and Howe (2009) for a review.) The problem (7) can be written in an equivalent form The optimization above is a min-diff-max problem and can be considered as simultaneously solving two subproblems min u [max v −f priv (u, v)] and min u [− max w −f util (u, w)], but is evidently not the same as summing individual solutions Since the second subproblem min u [− max w −f util (u, w)] = min u,w f util (u, w) is a standard minimization problem, let's focus only on the first subproblem min u [max v −f priv (u, v)] which is a continuous minimax problem. Continuous minimax problems are in general more challenging to solve than standard minimization problems, as the inner optimization Φ priv (u) = max v −f priv does not usually have a closed-form solution; when it does, the whole problem can be treated as a standard minimization problem. Furthermore, there can be more than one solution to Φ priv (u) = max v −f priv . To better understand minimax problems, we look at several examples starting from a simple case where Φ priv and Φ util have closed-form solutions.

Simple case: eigenvalue problem
Consider finding a minimax filer for the following problem. The filter class is a linear dimensionality reduction (g(x; u) = U T x) parameterized by the matrix U ∈ R D×d , and the private and target tasks are least-squares regressions parameterized by the matrices V and W : In this case, Φ priv (U ) = max V −f p (U, V ) and Φ util (U ) = max W −f u (U, W ) are both concave problems with closed-form solutionŝ where The corresponding min values are The outer minimization over u is then = min where This special case problem is quite similar to the objective of Enev et al. (2012): The problem (55) can be reformulated as a generalized eigenvalue problem. Let Q = C 1/2 xx U be a D × d full-rank matrix. The problem can be rewritten as Furthermore, note that min value (55) is invariant to the right multiplication of U by any xx , and the minimax problem becomes the following eigenvalue problem: min which is the sum of the d smallest eigenvalues of A. Note that A may not be positive definite.
The paper also proposes a variant of the above eigenvalue problem, called Privacy LDS which is an analogue of linear discriminant analysis (LDS) for privacy-utility optimization problem. Define the symmetric positive semidefinite matrix C u as where Define C p similarly with The proposed Privacy LDS is a linear filter g(x; W ) = W T x, where W = [v 1 , ..., v d ] is a matrix of top eigenvectors v i 's from the following generalized eigenvalue problem: This paper uses Privacy LDS as a heuristic to find the initial linear filter before fine-tuning the parameter u using a general optimization methods presented in the following sections. Note that this initialization is applicable only to linear filters.

Saddle-point problem
Continuous minimax problems cannot be solved in closed form in general and require numerical solvers. There is a subclass of continuous minimax problems which are easier to solve than others. Saddle point problems are minimax problems for which f (u, v) is convex in u and concave in v, such as Analogous to convex problems, f (u, v) has a global optimum (u * , v * ) which satisfies The presence of global optima in saddle-point problems makes numerical optimization practical. Convergence rate of a simple subgradient-descent method for saddle-point problems was previously analyzed by Nedić and Ozdaglar (2009). Unfortunately, the minimax problem min u max v −f priv considered in this paper is not a saddle-point problem even for a relatively simple case. Suppose one chooses linear filters, convex differentiable losses (e.g., least-squares, logistic, or exponential losses) and linear classifiers for the problem. Then is the negative expected value of the composition of a convex l(·) and a linear U T x, which is concave in u as well as concave in v, which cannot be a saddle-point problem.

General problem
A general numerical solution to the optimization (44) is described in this section. Let f (u, v) be a real-valued function f : R d × V → R, where V is a compact subset of the Euclidean space. Suppose f is jointly continuous and has a continuous partial derivative ∇ u f w.r.t. the first variable u. The maximum over v has a property that Φ(u) is in general not differentiable in u even if f (u, v) is. The derivatives of Φ(u) was studied by Danskin (1967). Suppose V (u) is the set of maximizers of f given u: Danskin proved that the directional derivative D y Φ(u) in any direction y ∈ R d can be written as the maximum directional derivatives of f (u, v) over allv ∈ V (u): where D y f (u, v) is the directional derivative of f w.r.t. u. Furthermore, in the case where V (u) is a singleton {v(u)} for each u, we have There are several classic minimax optimization algorithms using this property. Suppose f (u, v) is also continuously differentiable w.r.t. v, and ∇ u f is continuously differentiable w.r.t. v. A first-order method for minimax problems was proposed by Panin (1981) and was later refined by Kiwiel (1987). The latter uses a linear approximation of f at a fixedū along the direction q and uses it to compute the approximate max value Using this approximation, a line search can be performed along the descent direction q that minimizes the max function Φ(ū + αq). In particular, with additional assumptions of Lipschitz continuity of ∇ u f and compactness of U and V, Kiwiel's algorithm monotonically decreases f for each iteration and converges to a stationary point u * , i.e., a point u for which max v ∇ u f (u * , v), q ≥ 0 for all directions q. Previously, Hamm (2015) used Kiwiel's algorithm to solve the optimization problems (44). However, one disadvantage of the method was its slow speed in practice, due to the auxiliary routine of finding the descent direction q at each iteration (described in the supplementary material of Hamm (2015).) Instead, this paper proposes a simple alternating algorithm (Alg. 1) for solving min-diffmax problem based directly on Danskin's theorem. The algorithm only assumes f priv (u, v) and f util (u, w) to be jointly continuous and have continuous partial derivatives ∇ u f priv and ∇ u f util . Additionally, if f priv (u, v) and f util (u, w) are convex in v and w respectively, then the global minima v t = arg min v f priv (u t , v) and w t = arg min can be found easily, either approximately or accurately. Furthermore, if f util and f priv are strongly convex (e.g., due to regularization), the solutions are unique. Consequently, the descent direction q t in Alg. 1 is truly the (negative) gradient of Φ(u) (44) as desired: Note that it is still a heuristic for non-convex f util and f priv such as when using neural networks for the filter and/or the classifiers. A related heuristic for minimax problems was proposed by Goodfellow et al. (2014) for solving an unrelated problem of learning generative models.
Algorithm 1 Alternating algorithm for min-diff-max Input: data {(x i , y i , z i )}, filter g, loss l, classifier h, coefficient ρ, max iteration T Output: optimal filter parameter u Begin: (75) Compute the descent direction by Perform line search along q t and update u t+1 = u t + α t · q t Exit if solution converged end for The proposed optimization algorithm and supporting classes are implemented in Python and are available on the open-source repository 3 .

Noisy Minimax Filter
The privacy guarantee that minimax filters provide is very different from that of differentiallyprivate mechanisms. As the filter is learned from data, its privacy guarantee is given only in expectation/probability. Besides, it is a deterministic mechanism which cannot provide differential privacy. This section presents noisy minimax filter that combines minimax filter with additive noise mechanism to satisfy the differential privacy criteria. Two methods of combination-preprocessing and postprocessing-are proposed and compared. For completeness, a brief introduction to differential privacy is given.

A randomized algorithm that takes data D as input and outputsf (D) is called -differentially
for all measurable S ⊂ T of the output range and for all data sets D and D differing in a single item, denoted by D ∼ D . That is, even if an adversary knows the whole data set D except for a single item, she cannot infer much more about the unknown item from the output of the algorithm. A well-known mechanism for turning a non-private function f into a private functionf is the perturbation by additive noise. When an algorithm outputs a real-valued vector f (D) ∈ R D , its global sensitivity  is defined as where · is a norm such as the Euclidean norm. An important result from  is that the perturbation by additive noisẽ where ξ has the Laplace-like probability density whose scale parameter is proportional to is -differentially private. This paper considers local differential privacy (Duchi et al., 2013) of the filter output g(x), that is, perturbation is applied by each subject before g(x) is released to a third party. Let X = {x 1 , ..., x S } be a collection of data from S subjects. Then, X = {x 1 , ..., x S } and X = {x 1 , ..., x S } are defined as neighbors if x i = x i for all i = 1, ..., S except for some j ∈ 1, ..., S. For this subject, x j and x j can be any two samples from the common feature space X of all subjects. Consequently, a randomized filterg(·) is -differentially private if for all x, x ∈ X and all measurable S ⊂ T of the output range, P r(g(x) ∈ S) ≤ e P r(g(x ) ∈ S).

Pre-processing
Post-processing data filter noise  To use additive noise mechanism (79), the sensitivity (78) of the output g(·) needs to be determined: which is finite if X is compact and g(·) is continuous. If X is unbounded, one can directly bound the diameter of g(X ) by bounding functions. Let h = g(x) be the filtered value of any sample x ∈ X . Examples of the bounding function b : R D → R D are 1. Hard-bounding by clipping: b(h) = min{1/a, 1/ h } · h for some a > 0, 2. Soft-bounding by squashing: b(h) = tanh(a h ) for some a > 0, and 3. Normalization after clipping: b(h) = h/ h .
Note that these functions enforce the sensitivity S(b(g)) to be at most 2, regardless of X or g(·). The threshold a can be determined from the training data.

Preprocessing vs postprocessing
Minimax filters can be made locally differentially private using the additive noise mechanism (79) in the signal chain of filtering. The paper proposes two approaches. In the preprocessing approach, filtering is performed first followed by perturbation. In the postprocessing approach, perturbation is applied first followed by filtering. Note that preprocessing and postprocessing approaches are similar to output perturbation and input perturbation in Sarwate and Chaudhuri (2013). Fig. 2 shows the signal chains of the two approaches. In preprocessing, the original feature x is first filtered by g(x), and then made differential private by a bounding function and perturbation b(g(x)) + ξ. In postprocessing, the original feature x is first made differentially private by a bounding function and perturbation b(x) + ξ followed by filtering g(b(x) + ξ). By adding an appropriate amount of noise, both approaches can be made -differentially private regardless of data distribution. However, when the noisy mechanism is used in conjunction with a minimax filter which is dependent on data distribution P (x, y, z), preprocessing and postprocessing approaches have different effects that depend on the distribution.
A scenario when preprocessing is preferable to postprocessing is as follows. For the convenience of explanation, let's assume that subject identification is the private task. Let y(x) be the subject identity label of sample x and let z(x) be the target label of sample x for any target task. Define between-subject diameter as the max distance of two samples x, x from different subjects that have the same target label: Similarly, define within-subject diameter as the max distance of two samples x, x from the same subject that have different target labels: Also for the purpose of explanation, assume that the filter g is an orthogonal projection onto a lower-dimensional Euclidean space. For a given data set X , if the between-subject diameter is larger than the within-subject diameter (S b > S w ) in the original feature space (Fig. 3a), then minimax filtering can potentially reduce the diameter S(g) = max x,x g(x)− g(x ) significantly. This translates to less amount of noise required to achieve the sameprivacy than the amount of noise required before filtering, as the data diameter has shrunk. This will result in better utility of the preprocessing approach over the postprocessing approach where noise is added before filtering. From the same reasoning, if the opposite is true (S w > S b ) (Fig. 3b), then the diameter S(g) after minimax filtering does not change much, and the preprocessing approach may not offer much benefit over the postprocessing approach. However, there are still other aspects to consider as well. This paper assumes that the training data are public information and their privacy is not the primary concern unlike the test data. However, if we begin to consider the privacy of training data as well, then one should be aware that the learned filters can leak private information, analogous to how the PCA components can leak information about data (Chaudhuri et al., 2012), and that the filters also need to be sanitized before release. The postprocessing approach makes the whole process simpler. After each data owner perturbs the data by herself, any subsequent postprocessing-whether it is the process of applying pretrained filters or the process of training minimax filters-does not worsen differential privacy guarantees (Dwork et al., 2014), and therefore the postprocessing approach is a safer choice when the data owners cannot trust the entity that collects training data. In the experiment, utility and privacy of two approaches are further compared using real data.

Experiments
In this section, the algorithms proposed in the paper are evaluated using three real-world data sets: face data for gender/expression classification, speech data for emotion classification, and motion data for activity classification. Firstly, minimax filters are compared with non-minimax methods in terms of privacy breach vs utility as measured by accuracy of private and target tasks classifiers on test data. Secondly, noisy minimax filters are tested under various conditions using the same data sets.  Figure 3: Two example data distributions which have the same data diameter before filtering but have different diameters after filtering. a. an example where betweensubject diameter (83) is large. b. an example where within-subject diameter (84) is large.

Methods
Filters. The following minimax and non-minimax filters are compared.
• Rand: random subspace projection with g(x; U ) = U T x, where U is a random full rank D × d matrix. • PCA: principal component analysis with g(x; U ) = U T x, where U is the eigenvectors corresponding to d largest eigenvalues of Cov(x). • PPLS: private partial least squares, using Algorithm 1 from Enev et al. (2012).
Remarks. DDD requires analytical solutions to eigenvalue problems which are unavailable for multiclass problems, and is used only in the binary problem with the face database. Also, DDD code uses a mask-type filter, and the dimension d is same as the image size. The dimension d is also irrelevant to nonlinear Minimax filter 2 since it does not use linear dimensionality reduction. The nonlinear filter is pretrained as a stacked denoising autoencoders (Vincent et al., 2008) followed by supervised backpropagation with the target task. Classifier/loss. For all experiments, binary or multinomial logistic regression is used a classifier for both utility and privacy risks, where the loss l(h(g(x; u); v), y) is the negative log-likelihood with regularization: where K is the number of classes. The regularization coefficient was λ = 10 −6 ) and the utility-privacy tradeoff coefficient was ρ = 10. The main iteration in Alg. 1 was stopped manually when the progress was slow, which was between T = 20 − 200.

Data sets
Gender/expression classification from face: The GENKI database (Whitehill and Movellan, 2012) consists of face images with varying poses and facial expressions. The original data set is used unchanged, which has N = 1740 training images (50% male and 50% female; 50% smile and 50% non-smile). The test set has 100 images (50 males and 50 females; 50 smiling and 50 non-smiling) not overlapping with the training set. The dimensionality of the original data is D = 256, and the filters are tested with d = 10, 20, 50, 100.
The data set has gender and expression labels but no subject label. Consequently, gender classification is used as the private task and expression classification is used as the target task.
Emotion classification from speech: The ENTERFACE database (Martin et al., 2006) is an audiovisual emotion database of 43 speakers from 14 nations reading predefined English sentences in six induced emotions. From the raw speech signals sampled in 48 KHz, MFCC coefficients are computed using 20 ms windows with 50% overlap and 13 Mel-frequency bands. The mean, max, min, and standard deviation of the MFCC coefficients over the duration of each sentence are computed, resulting in N = 427 samples of D = 52 dimensional feature vectors from S = 43 subjects. Each subject's samples are randomly split to generate training (80%) and test (20%) sets. Average test accuracy over 10 such trials is reported. Filters are tested with d = 10, 20, 30, 40. The target task is binary classification of 'happy' and 'non-happy' emotions from speech, and the privacy risks is multiclass (S = 43) subject classification.
Activity classification from motion: The UCI Human Activity Recognition (HAR) data set (Anguita et al., 2012) is a collection of motion sensor data on a smartphone by 30 subjects performing six activities (walking, walking upstairs, walking downstairs, sitting, standing, laying). Various time and frequency domain variables are extracted from the signal, resulting in N = 10299 samples of D = 561 dimensional features from 30 subjects which are used unchanged. Out of 30 subjects, 15 subjects are chosen randomly. For each domain, each subject's samples are randomly split to generate training (50%) and test (50%) sets. At each trial, the subjects and the training/test sets are randomized, and the average test accuracy over 10 such trials is reported. Filters with dimensions d = 10, 20, 50, 100 are used. The target task is multiclass (C = 6) classification of activity, and the privacy risks is multiclass (S = 15) subject classification risk.

Result 1: Minimax filters
Before any filter is applied, the accuracy of the target tasks with raw data is 0. against inference attack is to perform dimensionality reduction on the original data, such as Rand and PCA projections. As the dimensionality d decreases from the original value D towards zero, one can expect both the private and the target accuracy to decrease toward the chance level. This trend is indeed the case with both the non-private (Rand,PCA) and the private (PPLS,DDD,Minimax) filters used in the paper. Therefore these filters are evaluated at several different values of the dimensionality d to make fine-grained comparisons of utility-privacy. Fig. 4 shows the test accuracy with GENKI. The dotted lines are level sets of utilityprivacy tradeoff (i.e., target task accuracy -private task accuracy) shown for reference. Minimax 2 achieves the best utility (i.e., most accurate expression classification) and Minimax 1 (linear) achieves the best privacy (i.e., least accurate gender classification). For all dimensions d, Minimax 1 achieves the best utility-privacy compromise (i.e., closest to the top-left corner of the plot), with Minimax 2 and DDD performing very closely. In terms of private task accuracy, Minimax 1 achieves almost the chance level accuracy (0.5), which implies a strong privacy preservation. DDD comes close to Minimax 1, while another private method PPLS is not very successful in preventing the inference of the private variable. As expected, non-private methods Rand and PCA also do not reduce the privacy task accuracy. As dimension d increases from 10 to 100, the accuracy of both the target and the private tasks increase (toward the top-right corner of the plot) for PPLS, PCA and Rand, but the value of utility-privacy tradeoff (i.e., target task accuracy -private task accuracy) remains relatively similar even though d changes. Note that d is irrelevant to Minimax 2 and DDD. Fig. 5 shows the test accuracy of ENTERFACE. Minimax 2 achieves the best utility (i.e., most accurate emotion classification) and the best privacy (i.e., least accurate subject classification) at the same time. PPLS performs well in this task; its private and target task accuracy is close to those of Minimax 2. The private task accuracy of Minimax 2 is near the chance level (1/S = 0.02) compared to 0.4 − 0.5 of non-private methods, suggesting that seemingly harmless statistics (mean, max, min, s.d. of MFCC) are quite susceptible to identification attacks if no privacy mechanism is used. Similar to GENKI, the accuracy of both the target and the private tasks increases with the dimension d for PCA and Rand, and the value of utility-privacy tradeoff remains similar regardless of d. Fig. 6 shows the test accuracy of HAR. Minimax 1 achieves the best utility (i.e., most accurate activity recognition) and the best privacy (i.e., least accurate subject classification), while Minimax 2 and PPLS performs similarly well. The private task accuracy of Minimax 1 is lower than others close to the chance level (1/S = 0.067). The figure also shows that motion data are susceptible (0.2 − 0.7) to identification attacks when no privacy mechanism is used. For all dimensions d, Minimax 1 achieves the best compromise of all methods similar to previous experiments. Also the accuracy of both the target and the private tasks roughly increases with d for PCA and Rand, but the value of utility-privacy tradeoff remains similar.

Result 2: Noisy minimax filters
The same data sets from the previous section are used to demonstrate the effect of noisy mechanism on minimax filters. Four types of noisy filters are compared: PCA-pre, PCApost, Minimax-pre, and Minimax-post. PCA is chosen as a non-minimax reference filter which preserves the original signal in the least mean-squared-error sense. PCA-pre/post means that PCA is applied before/after the perturbation similarly to Minimax-pre/post , over the range of −1 = {0, 10 −3 , 10 −2 , 10 −1 , 10 0 , 10 1 }. Top row is the target task accuracy (higher the better) and bottom row is the private task accuracy (lower the better.) Minimax-pre/post can limit the accuracy of inference attack (bottom row) to almost chance levels regardless of the value of , while PCA-pre/post requires a significantly high to prevent inference attacks which also destroy the utility.
from Fig. 2. For Minimax-pre/post, a linear filter of the same dimension d as PCA-pre/post is used. Tests are performed for the same ranges of dimension d as in Sec 6.3. The results for d = 20 with all three data sets are summarized in Fig. 7. Results for different dimensions show similar trends and are summarized in Fig. 8. Optimization of (6) is done similarly to the previous section. All tests are repeated 10 times for different noise samples of (80), for each of 10 random training/test splits. Fig. 7 shows the following results. Firstly, within each plot, increasing the privacy level from left ( −1 =0) to right ( −1 =10) lowers the accuracy of both target and private tasks for all filter types and data sets, which is intuitively correct. Secondly, target task accuracy (top row) shows that the four filters are equally accurate with no noise ( −1 =0), with Minimaxpre/post slightly more accurate than PCA-pre/post. This observation is consistent with the results in Sec. 6.3. In GENKI and HAR, preprocessing is better than postprocessing for both PCA and Minimax, and Minimax-pre performs the best. In ENTERFACE, preprocessing and postprocessing approaches perform similarly, and all four filters is perform similarly on the target task. This result may be ascribed to the discussion of different data distribution in Sec. 5.2. Thirdly, and most importantly, private task accuracy (bottom row) is quite different between Minimax-pre/post and non-minimax PCA-pre/post. For both Minimaxpre and Minimax-post, the private task accuracy is almost as low as the chance accuracy of each data set (0.5, 0.03, 0.07) regardless of the noise level . This demonstrates that minimax filter can prevent inference attacks with little help of noise. In contrast, the non-minimax filters (PCA-pre/post) allow an adversary to infer private variables quite accurately (0.8, 0.5, 0.3) when no noise is used. Preventing such attacks for non-minimax filters requires a significant amount of additive noise (e.g., −1 ≥0.1) which destroys the utility of data. These results show that differentially privacy is indeed different from privacy against inference attacks and the combination of two methods is beneficial.

Conclusion
This work presents a new privacy-preserving mechanism for preventing inference attacks on continuous and high-dimensional data. In this mechanism, a filter transforms continuous and high-dimensional raw features to dimensionality-reduced representations of data. After filtering, information on target tasks remains but information on identifying or sensitive attributes is removed which makes it difficult for an adversary to accurately infer such attributes from the released filtered output. Minimax filters are designed to achieve the optimal utility-privacy tradeoff in terms of expected risks. The paper proves that a filter learned from empirical risks is not far from an ideal filter that is learned from expected risks as the number of samples increases. This property and its dependency on the task make this mechanism quite different from previous mechanisms, including syntactic anonymization and differential privacy. Algorithms for finding minimax filters are presented and evaluated on real-world data sets to show its practical usages. Experiments show that publicly available multisubject data sets are surprisingly susceptible to subject identification attacks, and that even simple linear minimax filters can reduce the privacy risks close to chance level without sacrificing target task accuracy by much.
This work also presents preprocessing and postprocessing approaches to combine minimax privacy and differential privacy. While differential privacy has become a popular definition of privacy, it is not without limitations, in particular against inference attacks as empirically demonstrated in the paper. This leaves room for development of new mechanisms such as the noisy minimax filter presented in the paper, which aims to achieve high on-average utility and protection against inference attacks, and a formal privacy guarantee in the worst case. The results from experiments encourage further research on potential benefits of combining different notions and mechanisms of privacy, which is left as future work.