PaperlayerView exact revision on arXiv

Source-linked AI summary

Functional Mechanism: Regression Analysis under Differential Privacy

Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, Marianne Winslett

arXiv:1208.0219v1cs.DB

TL;DR

Existing private regression methods are limited or inaccurate, motivating a general approach for optimization-based analyses. The Functional Mechanism perturbs regression objective functions and applies to linear and logistic regression; theory and experiments report effectiveness and efficiency, while logistic approximation leaves a gap from standard regression results.

  • Problem

    Existing differentially private regression solutions are limited to non-standard regression types or produce inaccurate results.

  • Method

    The Functional Mechanism enforces privacy by perturbing optimization objective functions rather than regression results, including truncated Taylor expansions for logistic regression.

  • Results

    Theoretical analysis and experiments on real datasets demonstrate the Functional Mechanism’s effectiveness and efficiency for private regression.

  • Takeaways & Limitations

    The Functional Mechanism is reported as superior to prior methods in accuracy and efficiency, with accuracy sometimes comparable to NoPrivacy.

  • Takeaways & Limitations

    For logistic regression, objective-function approximation introduces an error and leaves a gap between approximate and standard regression results.

Abstract

from arXiv · show

ε-differential privacy is the state-of-the-art model for releasing sensitive information while protecting privacy. Numerous methods have been proposed to enforce epsilon-differential privacy in various analytical tasks, e.g., regression analysis. Existing solutions for regression analysis, however, are either limited to non-standard types of regression or unable to produce accurate regression results. Motivated by this, we propose the Functional Mechanism, a differentially private method designed for a large class of optimization-based analyses. The main idea is to enforce epsilon-differential privacy by perturbing the objective function of the optimization problem, rather than its results. As case studies, we apply the functional mechanism to address two most widely used regression models, namely, linear regression and logistic regression. Both theoretical analysis and thorough experimental evaluations show that the functional mechanism is highly effective and efficient, and it significantly outperforms existing solutions.

1. INTRODUCTION

Regression analysis is important but difficult to make differentially private because it requires optimization, and existing methods are limited or noisy. The paper proposes the Functional Mechanism, which perturbs optimization objectives rather than regression results.

  • ε-differential privacy protects records by making released-result distributions insensitive to changes in one record.
  • Regression analysis includes linear regression for fitting relationships and logistic regression for predicting class probabilities.
  • Existing private regression methods are narrow because optimization results are difficult to analyze for the minimum required noise.
  • The Functional Mechanism enforces privacy by perturbing the objective function and publishing the perturbed optimization result.
  • The paper applies the framework to linear and logistic regression and develops supporting theory, applications, and post-processing for unique optima.

2. RELATED WORK

Existing differential-privacy mechanisms primarily target aggregate or discrete outputs, while private regression methods remain limited. The paper positions its approach against objective perturbation, synthetic-data methods, and relaxed privacy.

  • The Laplace mechanism supports real-valued queries but is mostly used for aggregates or queries reducible to aggregates.
  • The exponential mechanism supports discrete output spaces and has been applied to tasks including synthetic datasets and support vector machines.
  • Prior objective-perturbation methods require convex, doubly differentiable costs and do not apply to standard logistic regression.
  • Synthetic-data regression methods generate noisy histograms and matching datasets before computing regression results.
  • The paper argues that linear and logistic regression can produce meaningful results under ε-differential privacy without using the relaxed (ε, δ)-privacy notion.

3. PRELIMINARIES

The paper formulates regression as parameterized optimization over bounded database attributes and defines privacy through neighboring databases. It reviews linear and logistic regression and the Laplace mechanism as preliminaries.

  • A regression model maps input attributes to predictions through a parameter vector ω and evaluates parameters with a cost function.
  • The optimal model parameter ω* minimizes the database cost function formed from tuple-level costs.
  • Regression models: The paper focuses on linear and logistic regression, with linear regression minimizing squared prediction error through a linear function.
  • Regression models: Logistic regression assumes boolean outcomes and predicts the probability of outcome 1 from observed attributes.
  • Differential privacy: ε-differential privacy compares randomized outputs on neighboring databases that differ in one tuple.
  • Differential privacy: The Laplace mechanism adds independent zero-mean noise scaled by query sensitivity divided by ε to real-valued query outputs.

4. FUNCTIONAL MECHANISM

The Functional Mechanism enforces ε-differential privacy for optimization-based regression by perturbing the objective function rather than the released model parameters. It represents objectives polynomially, adds Laplace noise to coefficients, and releases the minimizer of the perturbed objective.

  • Functional Mechanism: FM perturbs the regression objective function and releases its minimizer instead of adding noise directly to the regression results.The approach addresses the difficulty of analyzing sensitivity in the relationship between the database and the optimized parameters.
  • Functional Mechanism: The framework represents the objective as a polynomial in model parameters and injects Laplace noise into its polynomial coefficients.Each monomial is organized by degree, and the noisy coefficients define the perturbed objective optimized by the algorithm.
  • Privacy Guarantee: Algorithm 1 satisfies ε-differential privacy because the perturbed objective is private and subsequent optimization uses no additional information from the original database.The privacy proof establishes the guarantee for neighboring databases differing in one tuple.
  • Limitation: The noisy objective can become unbounded when the inserted noise is sufficiently large, producing meaningless regression results.The paper states that a later post-processing module addresses this issue.
  • Convergence: As database cardinality n approaches infinity, the algorithm’s output approaches the minimizer of the original objective when polynomial coefficients are bounded.The convergence argument applies to the averaged objective function and relies on the boundedness assumption for coefficient contributions.
  • Linear Regression: For linear regression, the objective contains only degree-zero, degree-one, and degree-two monomials, enabling coefficient perturbation with Lap(2(d + 1)^2/ε) noise.The stated setting assumes normalized feature vectors and responses in [−1, 1].

5. POLYNOMIAL APPROXIMATION OF OBJECTIVE FUNCTIONS

The paper approximates objective functions with bounded-degree polynomials so the functional mechanism can handle regression tasks such as logistic regression. Truncating Taylor expansions yields low-order objectives, with bounded approximation error but no matching convergence guarantee.

  • 5.1 Expansion: Taylor expansions convert suitable regression cost functions into polynomial objectives whose terms can be truncated to bounded degree.The decomposition applies when each inner function is polynomial in the model parameters.
  • 5.1 Expansion: Logistic regression is handled by expressing its cost function as a sum of composed functions and applying Taylor expansion to each outer function.The logistic cost is given as log(1 + exp(x_i^Tω)).
  • 5.2 Approximation: Truncating the Taylor series removes polynomial terms of order larger than 2, producing an objective function containing only low-order polynomials.The resulting approximated objective function is then suitable for the functional mechanism.
  • 5.2 Approximation: The approximation error depends on the function structure rather than dataset characteristics, and its average value is bounded.For logistic regression, the analysis characterizes the error using bounds on derivatives of log(1 + exp(z)).
  • 5.2 Approximation: For logistic regression, the approximation error is a small constant, but truncation creates a gap from standard regression results because no analogous convergence result exists.Experiments nevertheless report accurate regression results from the approximation approach.
  • 5.3 Application to Logistic Regression: Algorithm 2 constructs the approximated objective, applies Algorithm 1, and outputs its model parameter while retaining ϵ-differential privacy.Algorithm 1 provides privacy for any given objective function, including an approximation.
  • 5.3 Application to Logistic Regression: For the logistic-regression sensitivity calculation, the noise scale depends on d but is independent of dataset cardinality.The cited bound is ∆ = d^2/4 + 3d.

6. AVOIDING UNBOUNDED NOISY OBJECTIVE FUNCTIONS

Noise added to objective-function coefficients can make the perturbed regression objective unbounded, preventing an optimal solution. The paper considers repetition, regularization, and spectral trimming to obtain bounded objectives while managing privacy cost and solution quality.

  • Problem: Coefficient noise may render the perturbed objective function unbounded, so an optimal solution may not exist.In linear regression, the noisy quadratic can lose its minimum when its quadratic coefficient becomes unsuitable.
  • Repeated Functional Mechanism: Repeating the functional mechanism until a bounded objective appears preserves privacy but incurs 2ϵ-differential privacy.The paper characterizes this as a quick fix with higher privacy cost than the original mechanism.
  • Regularization: Regularization adds λI to the noisy quadratic coefficient matrix, increasing the likelihood that the perturbed objective is bounded.A sufficiently large λ makes the eigenvalues of M* + λI more likely to be positive, while excessive regularization can degrade solution quality.
  • Regularization: The paper reports that choosing λ as four times the standard deviation of the Laplace noise is effective in experiments.The text cautions that λ should not overwhelm the signal in M*.
  • Spectral Trimming: Regularization does not guarantee a bounded noisy objective, because non-positive eigenvalues can still remain.This motivates spectral trimming as a second approach.
  • Spectral Trimming: Spectral trimming removes non-positive eigenvalues from the regularized coefficient matrix, producing a bounded objective in the remaining transformed coordinates.The resulting function is bounded because all retained eigenvalues are positive.
  • Spectral Trimming: After minimizing the trimmed objective in transformed coordinates, the model parameters are recovered by solving Q′ω = V, although the solution is not unique.The paper argues that removing non-positive eigenvalues, which are mostly attributed to noise, may preserve useful information.

7. EXPERIMENTS

Experiments compare FM with private and non-private baselines on US and Brazil census datasets across dimensionality, cardinality, and privacy budget. FM consistently achieves stronger accuracy than FP and DPME, often approaches NoPrivacy accuracy, and runs substantially faster.

  • Experimental Setup: Experiments compare FM with DPME, FP, NoPrivacy, and Truncated using US and Brazil census datasets.The datasets contain 370,000 US records and 190,000 Brazil records, with 13 attributes each.
  • Accuracy vs. Dataset Dimensionality: FM consistently outperforms FP and DPME for linear regression as dimensionality increases, with accuracy nearly identical to NoPrivacy.FP and DPME incur especially significant errors at larger dimensionalities.
  • Accuracy vs. Dataset Dimensionality: For logistic regression, Truncated matches NoPrivacy accuracy, while FM is slightly less accurate than Truncated but substantially more accurate than FP and DPME.This supports the effectiveness of the low-order approximation used by Truncated.
  • Accuracy vs. Dataset Cardinality: FM outperforms FP and DPME across dataset cardinalities and remains close to NoPrivacy for linear regression, except at the smallest sampling rate.For logistic regression, FM’s accuracy gap from NoPrivacy and Truncated shrinks rapidly as cardinality increases, while FP and DPME remain considerably worse.
  • Accuracy vs. Privacy Budget: FM remains relatively robust as privacy budget ϵ changes and outperforms FP and DPME at every tested budget.All private methods incur higher errors as ϵ decreases because smaller budgets require more injected noise.
  • Computation Time: FM’s running time is at least one order of magnitude lower than NoPrivacy’s, while NoPrivacy is about two times faster than FP and DPME.FM’s low-order approximation reduces logistic regression to multivariate quadratic optimization; all methods become slower with greater dimensionality and cardinality, while ϵ has negligible runtime effects.

8. CONCLUSION AND FUTURE WORK

The paper presents a general differentially private regression approach based on perturbing objective functions, with polynomial and Taylor-expansion treatments for linear and logistic regression. Empirical studies on real datasets validate the theory and demonstrate effectiveness and efficiency, while future work targets broader objective functions and improved approximations.

  • The functional mechanism performs sensitivity analysis and noise insertion on objective functions, improving regression accuracy when objectives have finite polynomial representations.
  • For objectives with infinite polynomial representations, such as logistic regression, the method truncates the Taylor expansion and analyzes the resulting optimization error.
  • Empirical studies on real datasets validate the theoretical results and demonstrate the proposal’s effectiveness and efficiency.
  • The current mechanism is limited to objective functions of the form ∑_i=1^n f(t_i, ω).
  • Future work will address more complicated regression objectives, including Cox regression, and investigate analytical tools beyond Taylor expansion for greater accuracy.
Loading 1208.0219v1…