Fast and Reliable Parameter Estimation from Nonlinear Observations
This work addresses the challenge of efficient parameter estimation in nonlinear models for researchers and practitioners in machine learning and statistics, offering incremental improvements by precisely quantifying tradeoffs between computational and statistical resources.
The paper tackles the problem of recovering an unknown structured parameter from nonlinear observations with an unknown function, by developing a framework to characterize time-data tradeoffs for various estimation algorithms. It shows that projected gradient descent converges linearly with near-minimal samples, providing sharp convergence rates based on sample size, prior knowledge, and nonlinearity.
In this paper we study the problem of recovering a structured but unknown parameter ${\bfθ}^*$ from $n$ nonlinear observations of the form $y_i=f(\langle {\bf{x}}_i,{\bfθ}^*\rangle)$ for $i=1,2,\ldots,n$. We develop a framework for characterizing time-data tradeoffs for a variety of parameter estimation algorithms when the nonlinear function $f$ is unknown. This framework includes many popular heuristics such as projected/proximal gradient descent and stochastic schemes. For example, we show that a projected gradient descent scheme converges at a linear rate to a reliable solution with a near minimal number of samples. We provide a sharp characterization of the convergence rate of such algorithms as a function of sample size, amount of a-prior knowledge available about the parameter and a measure of the nonlinearity of the function $f$. These results provide a precise understanding of the various tradeoffs involved between statistical and computational resources as well as a-prior side information available for such nonlinear parameter estimation problems.