Minimizing Quadratic Functions in Constant Time

A sampling-based optimization method for quadratic functions is proposed. Our theoretical analysis specifies the number of samples $k(\delta, \epsilon)$ such that the approximated solution $z$ satisfies $ z - z * O(\epsilon n 2)$ with probability $1-\delta$. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments. Papers published at the Neural Information Processing Systems Conference.