Fast and Reliable Parameter Estimation from Nonlinear Observations
share
In this paper we study the problem of recovering a structured but unknown parameter θ^* from n nonlinear observations of the form y_i=f(〈x_i,θ^*〉) for i=1,2,...,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.
READ FULL TEXT