Linear Regression — API Reference

Auto-generated from the source docstrings. For the problem formulation and a usage example, see the Linear Regression task page.

Types

dp_testing_platform.tasks.linear_regression.types

LinearRegressionMetadata dataclass

Metadata for linear regression.

Attributes:

Name	Type	Description
dim	int	Dimension of the feature vectors.
n_samples	int	Number of samples in the dataset.
covariate_domain	Domain | None	Domain constraint for covariates X. If None, unbounded.
response_domain	Domain | None	Domain constraint for response y. If None, unbounded.

LinearRegressionInput dataclass

Input for linear regression.

Attributes:

Name	Type	Description
X	Array2D	Feature matrix, shape (n_samples, dim).
y	Array1D	Response vector, shape (n_samples,).

LinearRegressionOutput dataclass

Output for linear regression.

Attributes:

Name	Type	Description
beta	Array1D	Estimated coefficient vector, shape (dim,).
se	Array1D | None	Per-coefficient DP standard error, shape (dim,). None when the algorithm reports a point estimate only (no inferential output).

Algorithms

dp_testing_platform.tasks.linear_regression.algorithms.ols

OLS

Bases: BaseAlgorithm

Non-private ordinary least squares (baseline).

Solves min_beta ||X @ beta - y||^2. No privacy guarantees. Standard/textbook estimator; not a DP mechanism and has no single canonical paper.

Reference

Non-private baseline; no DP source paper.

dp_testing_platform.tasks.linear_regression.algorithms.vanilla_ssp

VanillaSSP

Bases: BaseAlgorithm

Sufficient statistics perturbation (SSP) for linear regression.

Adds Gaussian noise to X^T X and X^T y. Satisfies (eps, delta)-DP at every budget.

Privacy argument (self-contained): after clipping, each sample's contribution to X^T X is x_i x_i^T with ||x_i x_i^T||_F = ||x_i||^2 <= x_clip^2, and to X^T y is x_i y_i with ||x_i y_i||_2 = |y_i| * ||x_i||_2 <= x_clip * y_clip (two-sided y clip required — see _clip). These are the add/remove-one L2 sensitivities of the two released statistics. Each release is independently calibrated to be exactly (eps/2, delta/2)-DP via the analytic Gaussian mechanism (Balle & Wang 2018, "Improving the Gaussian Mechanism for Differential Privacy", arXiv:1805.06530, Theorem 8 / Algorithm 1), and basic composition of the two releases gives (eps, delta)-DP. The symmetric noise matrix A is post-processing of a (d(d+1)/2)-dimensional Gaussian release whose sensitivity is bounded by the full Frobenius bound above, so symmetrizing does not increase sensitivity. Unlike the Wang/AdaSSP-style constant sqrt(ln(4/delta))/(eps/2) (which fails the exact characterization at high eps, e.g. (eps=11, delta=1e-5)), the analytic calibration is valid for all eps > 0, delta in (0, 1).

Reference

Balle & Wang, "Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising", ICML 2018. https://arxiv.org/abs/1805.06530

Hyperparameters

C_x_clip: Clipping constant for X. Clips rows to norm C_x_clip * sqrt(d). Default: 1.0. C_y_clip: Clipping constant for y. Clips values to C_y_clip * sqrt(d). Default: 1.0.

dp_testing_platform.tasks.linear_regression.algorithms.exponential_mechanism

ExponentialMechanism

Bases: BaseAlgorithm

Grid-based exponential mechanism for linear regression.

Selects from a grid of candidate coefficients using the exponential mechanism (McSherry & Talwar, "Mechanism Design via Differential Privacy", FOCS 2007, DOI 10.1109/FOCS.2007.66). The mechanism samples a grid point with probability proportional to exp(-eps * s(beta) / (2 * R^2)) where s is the capped squared-residual score (per-record sensitivity R^2); this is a direct application of the EM primitive to regression, with no separate canonical DP-regression paper. Satisfies eps-DP.

The Cartesian grid is scored in fixed-size chunks and sampled with Gumbel-max, so memory use does not grow with the total number of grid points. Runtime is linear in the candidate count (exponential in the dimension); grids beyond a public feasibility cap release a data-independent NoRelease bottom instead of running unbounded.

Reference

McSherry & Talwar, "Mechanism Design via Differential Privacy", FOCS 2007 (the exponential mechanism primitive). https://doi.org/10.1109/FOCS.2007.66

Hyperparameters

R: Residual capping threshold. Default: 1.0. B: Coefficient bound (searches in [-B, B]^d). Default: 1.2. num_steps: Grid points per dimension. Default: 30.

sample_grid_point

sample_grid_point(X: Array2D, y: Array1D, grids_per_dim: Sequence[Array1D], residual_cap: float, score_scale: float, seed: int) -> Array1D

Sample an exponential-mechanism grid point with bounded memory.

Gumbel-max sampling: adding an independent standard-Gumbel draw to each log-weight -score_scale * score and taking the argmax samples exactly from the categorical distribution with weights exp(-score_scale * score). Because an argmax can be tracked as a running maximum, the grid is scored one fixed-size block of indices at a time — never materialized whole.

Parameters:

Name	Type	Description	Default
X	Array2D	Regression design matrix.	required
y	Array1D	Regression response vector.	required
grids_per_dim	Sequence[Array1D]	Ordered coefficient candidates for each dimension.	required
residual_cap	float	Absolute residual cap used by the quality score.	required
score_scale	float	Exponential-mechanism multiplier on the quality score.	required
seed	int	RNG seed for the mechanism's Gumbel draws.	required

Returns:

Type	Description
Array1D	The sampled coefficient vector.

Raises:

Type	Description
NoRelease	If the grid holds more than _MAX_GRID_POINTS candidates — a data-independent feasibility bottom (the grid shape is public).

dp_testing_platform.tasks.linear_regression.algorithms.exponential_mechanism_continuous

ExponentialMechanismContinuous

Bases: BaseAlgorithm

Continuous exponential mechanism via rejection sampling.

A continuous-domain variant of the exponential mechanism (McSherry & Talwar, "Mechanism Design via Differential Privacy", FOCS 2007, DOI 10.1109/FOCS.2007.66): samples coefficients uniformly over the box and accepts with probability proportional to the EM score, so the accepted draw follows the exponential mechanism's target density. This is a direct application of the EM primitive to regression, with no separate canonical DP-regression paper.

Privacy (conditional on acceptance): The eps-DP guarantee holds CONDITIONAL ON ACCEPTANCE (the non-abort event): an accepted draw follows the exponential mechanism's target density exactly and is eps-DP. The sampler's abort path (RuntimeError after max_trials proposals are all rejected) is a data-dependent event whose likelihood ratio across neighboring datasets is unbounded, so no charged budget covers it: the abort surfaces as an execution error outside the accounted release, never as an accounted "no result" outcome that DP selection could observe. The abort message carries only public quantities (max_trials), never data-derived values.

Temporary dimension guard

The uniform-proposal rejection sampler is structurally infeasible on real data: the per-trial acceptance probability is exp(-eps * s_min / (2R^2)) where the achievable score floor s_min grows with the sample size, so the expected number of trials is exponential in eps * n and no amount of retries helps. Pending the real sampler fix, run raises NoRelease for any instance whose dimension exceeds _MAX_FEASIBLE_DIM so those cells fail honestly (a no_release engine status, counted against coverage) instead of burning the trial budget. Below the threshold the mechanism runs unchanged.

The threshold _MAX_FEASIBLE_DIM = 3 reflects the EM-family feasibility envelope: exact grid-EM is "easy" only at d <= 3, borderline at d = 5, and infeasible at d >= 6. The continuous rejection sampler is strictly harder than exact grid enumeration, so d <= 3 is the loosest defensible feasible region. This is a coverage guard, not a feasibility guarantee: even within d <= 3 the sampler can still fail at moderate n/eps (a known limitation of the rejection sampler, pending replacement).

Reference

McSherry & Talwar, "Mechanism Design via Differential Privacy", FOCS 2007 (the exponential mechanism primitive). https://doi.org/10.1109/FOCS.2007.66

Hyperparameters

R: Residual capping threshold. Default: 1.0. B: Coefficient bound (samples from [-B, B]^d). Default: 1.0. max_trials: Maximum rejection sampling attempts. Default: 100.

dp_testing_platform.tasks.linear_regression.algorithms.doubly_exponential_mechanism

DoublyExponentialMechanism

Bases: BaseAlgorithm

Two-stage exponential mechanism for linear regression.

Applies the exponential mechanism (McSherry & Talwar, "Mechanism Design via Differential Privacy", FOCS 2007, DOI 10.1109/FOCS.2007.66) twice: the first stage finds a rough estimate over a coarse grid, the second stage refines it over a finer grid centered on the rough estimate. This is a two-stage grid application of the EM primitive to regression, with no separate canonical DP-regression paper. Satisfies eps-DP with budget split 1/4 and 3/4.

Each Cartesian grid is scored in fixed-size chunks and sampled with Gumbel-max, so memory use does not grow with the total number of grid points. Runtime is linear in each stage's candidate count (exponential in the dimension); a stage grid beyond the public feasibility cap releases a data-independent NoRelease bottom instead of running unbounded.

Reference

McSherry & Talwar, "Mechanism Design via Differential Privacy", FOCS 2007 (the exponential mechanism primitive). https://doi.org/10.1109/FOCS.2007.66

Hyperparameters

R: Residual capping threshold. Default: 1.0. B1: Coefficient bound for first stage. Default: 1.2. B2: Search radius for second stage around first estimate. Default: 1.0. grid1: Grid points per dimension for first stage. Default: 5. grid2: Grid points per dimension for second stage. Default: 10.

dp_testing_platform.tasks.linear_regression.algorithms.objective_perturbation

Objective perturbation for linear regression (Approximate Minima Perturbation).

The single ObjectivePerturbation algorithm (the Approximate Minima Perturbation / AMP mechanism, plus its no-output-stage "exact" configuration) builds on a regularized-Huber objective-perturbation core. The privacy accounting is written out once in this module so it can be reviewed in one place.

Mechanism (regularized half-Huber objective perturbation; privacy profile per Redberg-Koskela-Wang, NeurIPS 2023, "Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners", arXiv:2401.00583, Theorem 3.1):

minimize_w J(w) = sum_i 0.5 * huber_L(y_i - x_i^T w) + (lamb/2) ||w||^2 + z^T w

with z ~ N(0, sigma^2 I_d) and the rows of X clipped to ||x_i|| <= R.

HALF-HUBER CONVENTION. The per-example loss is the half-Huber h(r) = 0.5 r^2 for |r| <= L and L|r| - 0.5 L^2 otherwise. We implement it as 0.5 * cp.huber(r, L) because cvxpy's huber(r, L) equals r^2 (not 0.5 r^2) in the quadratic zone, so the bare cp.huber would be the full Huber (|h'| <= 2L, h'' <= 2) and undercalibrate by a factor 2. With the 0.5 factor: * |h'(r)| <= L => per-example gradient bound ||grad l|| <= L*R * 0 <= h''(r) <= 1 => per-example Hessian spectral bound <= R^2, and the Hessian is rank one (h''(r) x x^T), the GLM structure RKW Thm 3.1 relies on for a dimension-free log-det (Jacobian) term. We write beta := R^2 for this per-record Hessian spectral bound.

ADD/REMOVE NEIGHBORS. The library standardizes on the add/remove-one (unbounded DP) relation (see core/accounting.py): two datasets are neighbors if one adds or removes a single record. RKW's analysis is stated for this relation on a SUMMED objective (which matches the sum_i above). Under add/remove the gradient sum of the data term, g(w; D) = sum_i grad l(w; d_i), changes by exactly one record's contribution, so its L2 sensitivity is

Delta = L * R (single record; NO factor of 2).

(The substitution / replace-one relation swaps one record for another and so doubles this to 2 L R -- the older Kifer-Smith-Thakurta calibration. Under add/remove that 2 is dropped.)

ACCOUNTING (RKW Thm 3.1, per the paper's Appendix D proof). Fix lamb > beta = R^2 and define

c = |log(1 - beta/lamb)| > 0 (the log-det budget, CONSUMED) m = Delta^2 / (2 sigma^2) (the Gaussian privacy-loss mean) eps_tilde = eps - c eps_hat = eps_tilde - m

The deterministic c is the log-det (Jacobian) budget of the change of variables z -> beta_hat through the rank-one-updated Hessian H + lamb I (a single GLM rank-one update bounded by beta); Lemma D.3 bounds the privacy-loss random variable by c + m + N(0, 2m), so c is SPENT from eps. NOTE: the theorem's PRINTED statement is inconsistent with its own Appendix-D proof on two points — the sign of the log-det term (printed eps - log(1 - beta/lamb) = eps + c, where the proof sets eps_hat = eps - c - m) and the branch-2 exponent/prefactor (printed L^2/sigma^2; the proof derives m = L^2/(2 sigma^2) with prefactor e^eps_hat). This module DEFERS TO THE PROOF'S DERIVED QUANTITIES (with which the RDP form, Thm 3.2, and the Lemma 3.4/Cor 3.5 Gaussian lower bound agree; as printed, delta would shrink as lamb -> beta). Do not "re-verify" this module against the printed statement. The mechanism is (eps, delta(eps))-DP with the hockey-stick profile

delta(eps) = 2 * H(sigma, eps_tilde, Delta) if eps_hat >= 0 = (1 - e^eps_hat) + e^eps_hat * 2 * H(sigma, m, Delta) otherwise

where H(sigma, a, Delta) = gaussian_mechanism_delta(sigma, a, Delta) is the exact Balle-Wang Gaussian hockey-stick term (core/accounting.py); the branches are continuous at eps_hat = 0. delta(eps) is strictly decreasing in sigma toward the floor max(0, 1 - e^{eps - c}): when eps < c the floor is positive and sigma-independent, so a cell whose target delta does not exceed it is UNCERTIFIABLE at any noise level and fails closed. Otherwise we calibrate the smallest feasible sigma by bisection (mirroring analytic_gaussian_sigma).

SCALE-AWARE REGULARIZER (feasibility). RKW Thm 3.1 requires lamb > beta = R^2, and R = C_x_clip * sqrt(d) scales with the dimension, so a fixed lamb cannot satisfy this across problems. Callers therefore expose a DIMENSIONLESS multiplier lambda_mult and compute lamb = lambda_mult * R^2 inside run from public metadata (R = C_x_clip * sqrt(d)); lambda_mult > 1 guarantees lamb > beta. Because the objective is SUMMED, lamb ~ R^2 is MILD regularization (relative strength ~ lambda_mult / n against the data curvature ~ n R^2). If lamb <= beta the cell is infeasible (the log-det term is undefined) and we raise NoRelease -- an honest "no_release" engine status rather than an unsound release.

EXACT-MINIMIZER ASSUMPTION (gap 2, the decisive caveat). The density-of-output argument is a change of variables z -> beta via the exact first-order condition grad J(beta) = 0. It collapses for an approximate minimizer. A numerical solver (cvxpy/OSQP) returns an approximate minimizer, so the "exact" no-output-stage configuration's (eps, delta)-DP claim is conditional on exact minimization, which we cannot certify -- see OBJPERT_EXACT_MIN_CAVEAT. The default two-stage ObjectivePerturbation (AMP, Iyengar et al. 2019) repairs this by solving to a certified gradient-norm tolerance and adding a second output-perturbation stage.

SOLVER NON-CERTIFICATION ABORTS. The two-stage guarantee is conditional on the solver certifying ||grad J(beta_hat)|| <= grad_tol. If certification fails (near-unreachable for this strongly convex objective), the run aborts with RuntimeError -- an execution error outside the accounted release, like any crash -- NOT a NoRelease ⊥: whether the solver certifies depends on the private data, and no budget is charged for that event (core/exceptions.py has the contract).

ObjectivePerturbation

Bases: BaseAlgorithm

Objective perturbation for linear regression (Approximate Minima Perturbation).

The single objective-perturbation algorithm for this task. The implementation is Approximate Minima Perturbation (AMP, Iyengar et al., IEEE S&P 2019): the DP-sound, solver-robust two-stage mechanism on the shared regularized half-Huber core (this module's header has the full sensitivity/accounting argument).

1. Objective perturbation calibrated for (eps_obj, delta_obj)-DP of the exact minimizer w* (RKW Thm 3.1 add/remove accounting): gradient sensitivity L*R (one record, no factor 2), deterministic log-det budget log(1 - R^2/lambda), scale-aware regularizer lambda = lambda_mult * R^2 with R = C_x_clip * sqrt(d).
2. Output perturbation covering the solver gap h(D) = w_hat - w*. The release is w_hat + xi = w*(D) + h(D) + xi. The objective is lambda-strongly convex, so any solver point w_hat with certified ||grad J(w_hat)|| <= grad_tol satisfies ||h(D)|| = ||w_hat - w*|| <= grad_tol/lambda on each dataset. Stage 1 already privatizes the exact minimizer w*(D) (covering the w*(D) -> w*(D') neighbor change), so the output Gaussian xi ~ N(0, sigma2^2 I) must cover only the between-neighbor change of the GAP: under add/remove one record, ||h(D) - h(D')|| <= 2*grad_tol/lambda (two opposite-pointing gaps). Calibrating the analytic Gaussian mechanism at output sensitivity 2*grad_tol/lambda makes the release (eps_out, delta_out)-DP relative to w*. (The single-dataset gap grad_tol/lambda is NOT a between-neighbor sensitivity; using it under-noises this stage 2x.)

Basic composition gives (eps_obj+eps_out, delta_obj+delta_out) = the requested (eps, delta). The output stage closes the exact-minimizer gap (gap 2): the guarantee holds for the certified gradient-norm tolerance regardless of how the solver reached it. If the solver fails to reach grad_tol the cell raises NoRelease. Infeasible cells (lambda <= R^2, i.e. lambda_mult <= 1) raise NoRelease.

"Exact" configuration. Setting output_budget_frac = 0 (or grad_tol = 0) allocates the entire budget to the objective stage and adds no output noise, recovering the classic objective- perturbation mechanism. This release is (eps, delta)-DP only under the exact-minimizer assumption (Redberg-Koskela-Wang 2023): the density-of-output argument needs the exact minimizer, but the numerical solver returns an approximate one, so the "exact" configuration's guarantee is NOT certifiable (see OBJPERT_EXACT_MIN_CAVEAT). Use the :meth:exact convenience constructor for this configuration; prefer the default two-stage configuration for a solver-robust sound guarantee.

The mechanism is operationally faithful to Iyengar et al. 2019; the exact theorem constants were not re-verified at the primary source, and the two-stage analysis here uses basic composition and the strong-convexity output-sensitivity bridge 2*grad_tol/lambda (add/remove: the gap's between-neighbor L2 change, twice the single-dataset gap grad_tol/lambda).

Reference

Iyengar, Near, Song, Thakkar, Thakurta & Wang, "Towards Practical Differentially Private Convex Optimization", IEEE S&P 2019. Objective-perturbation core / accounting: Redberg, Koskela & Wang, "Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners", NeurIPS 2023 (Theorem 3.1). https://arxiv.org/abs/2401.00583 Original objective-perturbation construction: Kifer, Smith & Thakurta, "Private Convex Empirical Risk Minimization and High-dimensional Regression", COLT 2012 (PMLR v23).

Hyperparameters

C_x_clip: Clipping constant for X. Clips rows to norm C_x_clip * sqrt(d). Default: 1.0. huber_L: Half-Huber loss parameter (strictly positive). Default: 1.0. lambda_mult: Dimensionless L2 regularization multiplier; the actual regularizer is lambda_mult * R^2 (R = C_x_clip * sqrt(d)). Must exceed 1 for RKW Thm 3.1 feasibility (lambda > beta = R^2). Default: 5.0. grad_tol: Certified gradient-norm tolerance for the solver (>= 0); 0 selects the no-output-stage "exact" configuration. Default: 0.1. output_budget_frac: Fraction of (eps, delta) given to the output stage, in [0, 1); 0 selects the no-output-stage "exact" configuration. Default: 0.1.

exact classmethod

exact(C_x_clip: float | None = None, huber_L: float | None = None, lambda_mult: float | None = None, name: str | None = None, description: str | None = None, metadata: dict[str, Any] | None = None) -> 'ObjectivePerturbation'

Build the no-output-stage ("exact") objective-perturbation configuration.

Constructs ObjectivePerturbation with grad_tol = 0 and output_budget_frac = 0 -- the entire budget on the objective stage, no output-perturbation stage. This is the classic objective-perturbation mechanism whose (eps, delta)-DP guarantee holds only under the exact- minimizer assumption (see the class docstring and OBJPERT_EXACT_MIN_CAVEAT); the numerical solver returns an approximate minimizer, so the released coefficients are NOT certifiably private. Prefer the default ObjectivePerturbation() (two-stage) for a solver-robust sound guarantee.

The exact-minimizer caveat is recorded as the default registered description so it travels with results.csv via the registry, and the default name distinguishes this configuration from the two-stage one in a sweep that runs both.

Parameters:

Name	Type	Description	Default
C_x_clip	float | None	Clipping constant for X (clips rows to norm C_x_clip*sqrt(d)).	None
huber_L	float | None	Half-Huber loss parameter (strictly positive).	None
lambda_mult	float | None	Dimensionless L2 regularization multiplier.	None
name	str | None	Display name; defaults to "ObjectivePerturbation(exact)".	None
description	str | None	Registered description; defaults to the exact-minimizer caveat.	None
metadata	dict[str, Any] | None	Arbitrary metadata dict.	None

Returns:

Type	Description
'ObjectivePerturbation'	An ObjectivePerturbation fixed to the no-output-stage configuration.

clip_rows

clip_rows(vectors: ArrayND, gamma: float) -> ArrayND

Clip to an L2 ball of radius gamma.

For a 2-D array each row is rescaled to norm at most gamma (the sensitivity-control clip on the design matrix X). For a 1-D array each entry is clipped symmetrically to [-gamma, gamma] (magnitude clip) so the bound holds on BOTH sides -- a one-sided a_max-only clip would leave large negatives unbounded.

objpert_profile_delta

objpert_profile_delta(sigma: float, eps: float, R: float, L: float, lamb: float) -> float

RKW Thm 3.1 hockey-stick delta(eps) at objective-perturbation noise sigma.

Implements the add/remove privacy profile documented at the top of this module — the Appendix-D proof's derived quantities; where the printed statement disagrees with its proof, the proof is followed. beta = R^2 (per-record GLM Hessian bound), gradient sensitivity Delta = L * R, log-det budget c = |log(1 - beta/lamb)| > 0 consumed from eps, and the Gaussian noise-density term H = gaussian_mechanism_delta. delta is strictly decreasing in sigma toward max(0, 1 - e^{eps - c}). Requires lamb > beta (else the log-det term is undefined); the caller enforces feasibility.

objpert_noise_scale

objpert_noise_scale(budget: ApproxDPBudget, R: float, L: float, lamb: float) -> float

Calibrate the objective-perturbation Gaussian noise scale sigma.

Inverts the RKW Thm 3.1 privacy profile (:func:objpert_profile_delta) by bisection: delta(eps) is strictly decreasing in sigma, so the returned sigma is the smallest noise level (rounded UP so the guarantee holds) achieving the target (eps, delta) under the add/remove relation, the half-Huber gradient sensitivity L*R, and the log-det budget log(1 - R^2/lamb).

Parameters:

Name	Type	Description	Default
eps		Total epsilon allotted to the objective-perturbation mechanism.	required
delta		Target delta for the privacy profile.	required
R	float	L2 clipping radius for the design-matrix rows.	required
L	float	Huber loss parameter (half-Huber, so |h'| <= L).	required
lamb	float	L2 regularization strength (must exceed beta = R^2).	required

Returns:

Type	Description
float	The standard deviation of the Gaussian objective-perturbation noise.

Raises:

Type	Description
NoRelease	If the cell is infeasible -- lamb <= beta = R^2 (RKW Thm 3.1's log-det budget is undefined), or eps < c with the target delta at or below the sigma-independent floor 1 - e^{eps - c} (no noise level certifies the cell).

solve_perturbed_huber

solve_perturbed_huber(X: Array2D, y: Array1D, L: float, lamb: float, z: Array1D) -> Array1D

Minimize the perturbed regularized half-Huber objective exactly.

Solves min_w sum_i 0.5*huber_L(y_i - x_i^T w) + (lamb/2)||w||^2 + z^T w. The 0.5 factor makes cp.huber the half-Huber loss whose constants the privacy accounting assumes (see module header).

Raises:

Type	Description
ImportError	If the cvxpy package is not installed.
RuntimeError	If the solver returns no solution.

objective_gradient_norm

objective_gradient_norm(X: Array2D, y: Array1D, w: Array1D, L: float, lamb: float, z: Array1D) -> float

L2 norm of the gradient of the perturbed objective at w.

grad J(w) = -sum_i clip(r_i, -L, L) x_i + lamb*w + z with r_i = y_i - x_i^T w (the half-Huber derivative is clip(r, -L, L)). Used by AMP to certify the solver reached the requested gradient-norm tolerance.

Lifted algorithms

M-estimation algorithms presented as native linear-regression algorithms (the squared-residual loss recovers ordinary least squares).

dp_testing_platform.tasks.linear_regression.algorithms.lifted

M-estimation algorithms lifted onto the linear-regression task.

Each class presents an m_estimation algorithm as a native linear_regression algorithm. The child->parent map fixes the squared-residual loss (ordinary least squares): the per-row design vector stacks [x_i | y_i] and the fitted M-estimation parameter vector is returned as the regression coefficient vector. lift_input is per-row (row i maps to row i), so the inner algorithm's (eps, delta)-DP guarantee transfers verbatim.

Instance generators

dp_testing_platform.tasks.linear_regression.instance_generators.gaussian_instance_generator

GaussianCovariatesAndNoise

Bases: InstanceGenerator

Gaussian instance generator for linear regression.

Generates y = X @ beta + noise where X ~ N(0, Sigma) with controllable condition number. Beta is a random unit vector.

Metrics

dp_testing_platform.tasks.linear_regression.metrics

Metric registry for the linear_regression task.

l2_error

l2_error(output: LinearRegressionOutput, reference: Array1D) -> float

L2 error between output.beta and a reference vector (ground truth or OLS).

ols_reference_beta

ols_reference_beta(evaluation_input: LinearRegressionInput) -> Array1D

Return the OLS baseline algorithm's fit of this instance's (X, y).

Uses the baseline's numpy.linalg.lstsq definition directly. The metric has no privacy allowance to hand to an algorithm, and a dummy allowance would misrepresent why the non-private computation is being performed.

key_l2_error_to_ols

key_l2_error_to_ols(output: LinearRegressionOutput, evaluation_input: LinearRegressionInput) -> float

L2 distance from output.beta to the OLS baseline fit of this (X, y).

The reference is the OLS baseline algorithm's output, so the baseline itself scores exactly 0 here by construction.

normalized_mse

normalized_mse(output: LinearRegressionOutput, evaluation_input: LinearRegressionInput) -> float

In-sample MSE of output.beta divided by the response variance var(y).

The population variance (ddof=0) makes this equal SSE/TSS. A COST (lower is better): 0 is a perfect fit, ~1 predicts no better than the response mean. Also known as the fraction of variance unexplained (FVU); equals 1 - R^2 for centered designs. Returns NaN when the response is constant (var(y) == 0, a degenerate instance).

mse

mse(output: LinearRegressionOutput, evaluation_input: LinearRegressionInput) -> float

In-sample mean squared error of output.beta on this instance's (X, y).

relative_l2_error_to_ground_truth

relative_l2_error_to_ground_truth(output: LinearRegressionOutput, ground_truth: Array1D, ols_beta: Array1D) -> float

Ratio of squared L2 error to ground truth over OLS error.

dp_clipped_SSE

dp_clipped_SSE(output: LinearRegressionOutput, evaluation_metadata: LinearRegressionMetadata, evaluation_input: LinearRegressionInput, budget: DPBudget, seed: int, clipping_bound: float) -> float

Compute DP clipped sum of squared errors with Laplace noise.

Clips individual squared errors to clipping_bound, sums them, and adds Laplace noise scaled by clipping_bound / eps.

Parameters:

Name	Type	Description	Default
output	LinearRegressionOutput	Algorithm output containing beta.	required
evaluation_metadata	LinearRegressionMetadata	Evaluation metadata (unused).	required
evaluation_input	LinearRegressionInput	Evaluation input with X, y.	required
budget	DPBudget	Privacy allowance for the Laplace release.	required
seed	int	Seed for noise generation.	required
clipping_bound	float	Upper bound for per-sample squared errors.	required

Returns:

Type	Description
float	Noisy, clipped sum of squared errors.

dp_clipped_SSE_gaussian

dp_clipped_SSE_gaussian(output: LinearRegressionOutput, evaluation_metadata: LinearRegressionMetadata, evaluation_input: LinearRegressionInput, budget: DPBudget, seed: int, clipping_bound: float) -> float

Compute DP clipped sum of squared errors with Gaussian noise (zCDP-calibrated).

Clips individual squared errors to clipping_bound, sums them, and adds Gaussian noise through the accounting seam. Approximate-DP allowances use exact analytic-Gaussian calibration; zCDP allowances use the exact sensitivity / sqrt(2*rho) scale required by zCDP-accounted selectors.

Parameters:

Name	Type	Description	Default
output	LinearRegressionOutput	Algorithm output containing beta.	required
evaluation_metadata	LinearRegressionMetadata	Evaluation metadata (unused).	required
evaluation_input	LinearRegressionInput	Evaluation input with X, y.	required
budget	DPBudget	Privacy allowance for the Gaussian release.	required
seed	int	Seed for noise generation.	required
clipping_bound	float	Upper bound for per-sample squared errors.	required

Returns:

Type	Description
float	Noisy, clipped sum of squared errors.

Raises:

Type	Description
ValueError	If the allowance cannot soundly fund Gaussian noise.

dp_median_SSE

dp_median_SSE(output: LinearRegressionOutput, evaluation_metadata: LinearRegressionMetadata, evaluation_input: LinearRegressionInput, budget: DPBudget, seed: int, beta: float) -> float

Compute DP median of squared errors via Unbounded Quantile mechanism.

Computes per-sample squared errors, then uses the Unbounded Quantile Mechanism to privately estimate their median.

Parameters:

Name	Type	Description	Default
output	LinearRegressionOutput	Algorithm output containing beta.	required
evaluation_metadata	LinearRegressionMetadata	Evaluation metadata (unused).	required
evaluation_input	LinearRegressionInput	Evaluation input with X, y.	required
budget	DPBudget	Privacy allowance delegated to the quantile mechanism.	required
seed	int	Seed for noise generation.	required
beta	float	Multiplicative step size for the Unbounded Quantile candidate grid.	required

Returns:

Type	Description
float	Noisy median of squared errors.