Minimizing Quadratic Functions in Constant Time

Abstract

A sampling-based optimization method for quadratic functions is proposed. Our method approximately solves the following $n$-dimensional quadratic minimization problem in constant time, which is independent of $n$: $z^{\ast }={\min }_{\mathbf{v}\in {\mathbb{R}}^n}⟨\mathbf{v},A\mathbf{v}⟩+n⟨\mathbf{v},\mathrm{diag}(\mathbf{d})\mathbf{v}⟩+n⟨\mathbf{b},\mathbf{v}⟩$, where $A\in {\mathbb{R}}^{n\times n}$ is a matrix and $\mathbf{d},\mathbf{b}\in {\mathbb{R}}^n$ are vectors. Our theoretical analysis specifies the number of samples $k(\delta ,\epsilon )$ such that the approximated solution $z$ satisfies $|z-z^{\ast }|=O(\epsilon n^2)$ with probability $1-\delta$. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments.

An extended abstract will appear in the proceedings of NIPS'16

Cited by in corpus (1)

• On Random Subsampling of Gaussian Process Regression: A Graphon-Based Analysis