In the proportional high-dimensional regime, stronger backdoor training triggers improve clean accuracy and make attack success non-monotonic for regularized GLMs on Gaussian mixtures, with closed-form proofs for squared loss and fixed-point extensions to convex losses.
A framework to characterize performance of lasso algorithms
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
abstract
In this paper we consider solving \emph{noisy} under-determined systems of linear equations with sparse solutions. A noiseless equivalent attracted enormous attention in recent years, above all, due to work of \cite{CRT,CanRomTao06,DonohoPol} where it was shown in a statistical and large dimensional context that a sparse unknown vector (of sparsity proportional to the length of the vector) can be recovered from an under-determined system via a simple polynomial $\ell_1$-optimization algorithm. \cite{CanRomTao06} further established that even when the equations are \emph{noisy}, one can, through an SOCP noisy equivalent of $\ell_1$, obtain an approximate solution that is (in an $\ell_2$-norm sense) no further than a constant times the noise from the sparse unknown vector. In our recent works \cite{StojnicCSetam09,StojnicUpper10}, we created a powerful mechanism that helped us characterize exactly the performance of $\ell_1$ optimization in the noiseless case (as shown in \cite{StojnicEquiv10} and as it must be if the axioms of mathematics are well set, the results of \cite{StojnicCSetam09,StojnicUpper10} are in an absolute agreement with the corresponding exact ones from \cite{DonohoPol}). In this paper we design a mechanism, as powerful as those from \cite{StojnicCSetam09,StojnicUpper10}, that can handle the analysis of a LASSO type of algorithm (and many others) that can be (or typically are) used for "solving" noisy under-determined systems. Using the mechanism we then, in a statistical context, compute the exact worst-case $\ell_2$ norm distance between the unknown sparse vector and the approximate one obtained through such a LASSO. The obtained results match the corresponding exact ones obtained in \cite{BayMon10,DonMalMon10}. Moreover, as a by-product of our analysis framework we recognize existence of an SOCP type of algorithm that achieves the same performance.
citation-role summary
method 1
citation-polarity summary
roles
method 1polarities
use method 1representative citing papers
DP-GD achieves minimax optimal non-asymptotic risk O(γ + γ²/ρ²) for well-conditioned high-dimensional data and power-law scaling for ill-conditioned power-law spectra, with the exponent depending on the privacy parameter ρ.
Meta Subspace Pursuit learns the invariant low-rank subspace in multi-task linear models with provable algorithmic and statistical guarantees and outperforms baselines like ANIL in experiments.
Symmetrically penalized least squares with non-separable penalties approximately matches separable penalties in high-dimensional Gaussian models, quantified by finite-sample concentration inequalities, with limited advantages when parameter distribution is known and automatic adaptation when unknown
In high-dimensional convex ERM with non-Gaussian data, the projection of the estimator onto a test covariate asymptotically follows the convolution of a generally non-Gaussian term with an independent centered Gaussian whose variance is the trace of the estimator covariance times the data second-mom
citing papers explorer
-
When Stronger Triggers Backfire: A High-Dimensional Theory of Backdoor Attacks
In the proportional high-dimensional regime, stronger backdoor training triggers improve clean accuracy and make attack success non-monotonic for regularized GLMs on Gaussian mixtures, with closed-form proofs for squared loss and fixed-point extensions to convex losses.
-
High-Dimensional Private Linear Regression with Optimal Rates
DP-GD achieves minimax optimal non-asymptotic risk O(γ + γ²/ρ²) for well-conditioned high-dimensional data and power-law scaling for ill-conditioned power-law spectra, with the exponent depending on the privacy parameter ρ.
-
Few-shot Multi-Task Learning of Linear Invariant Features with Meta Subspace Pursuit
Meta Subspace Pursuit learns the invariant low-rank subspace in multi-task linear models with provable algorithmic and statistical guarantees and outperforms baselines like ANIL in experiments.
-
Approximate separability of symmetrically penalized least squares in high dimensions: characterization and consequences
Symmetrically penalized least squares with non-separable penalties approximately matches separable penalties in high-dimensional Gaussian models, quantified by finite-sample concentration inequalities, with limited advantages when parameter distribution is known and automatic adaptation when unknown
-
Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization
In high-dimensional convex ERM with non-Gaussian data, the projection of the estimator onto a test covariate asymptotically follows the convolution of a generally non-Gaussian term with an independent centered Gaussian whose variance is the trace of the estimator covariance times the data second-mom
- High-Dimensional Statistics: Reflections on Progress and Open Problems