This paper develops a unified framework for instance optimal sparse recovery from nonlinear observations. The main ingredient is a signal-dependent restricted approximate invertibility condition (RAIC) of some gradient, which leads to the instance optimality of iterative hard thresholding. Under Gaussian designs, we ap...
We study finite-sample parameter estimation in logistic regression with Gaussian design, where the goal is to estimate $\mathbf{\theta}^*\in \mathbb{R}^d$ with $R=\|\mathbf{\theta}^*\|_2\ge 1$ from i.i.d. samples $\{(\mathbf{x}_i,y_i)\}_{i=1}^n,$ $\mathbf{x}_i \sim N(0,\mathbf{I}_d)$, $y_i\mid \mathbf{x}_i \sim \mathrm...
The main technical component is to show that the gradient of the logistic loss satisfies a certain approximate invertibility condition (AIC) and uniformly control the deviation of the gradient from its population counterpart by covering and peeling arguments, and then show that the population GD is a contraction by a d...