Minimizing Quadratic Functions in Constant Time
This addresses the computational bottleneck of high-dimensional quadratic optimization, offering a potentially faster method for applications like machine learning and numerical analysis, though it appears incremental as it builds on sampling techniques.
The paper tackles the problem of minimizing quadratic functions in high dimensions by proposing a sampling-based optimization method that approximates the solution in constant time independent of dimension n, achieving an error bound of O(εn^2) with high probability and confirming performance through numerical experiments.
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^*=\min_{\mathbf{v} \in \mathbb{R}^n}\langle\mathbf{v}, A \mathbf{v}\rangle + n\langle\mathbf{v}, \mathrm{diag}(\mathbf{d})\mathbf{v}\rangle + n\langle\mathbf{b}, \mathbf{v}\rangle$, 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(δ, ε)$ such that the approximated solution $z$ satisfies $|z - z^*| = O(εn^2)$ with probability $1-δ$. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments.