# Minimizing Quadratic Functions in Constant Time

arXiv: https://arxiv.org/abs/1608.07179 · HTML: https://mlsanity.com/paper/1608.07179/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2016.

## Built on by (most cited first, 1 of 1)

- [Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning](https://mlsanity.com/paper/2301.02870/) (2023)

## Abstract (arXiv)

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^*=minv ∈ ℝnlanglev, A vrangle + nlanglev, diag(d)vrangle + nlangleb, vrangle, where A ∈ ℝn × n is a matrix and d,b ∈ ℝn are vectors. Our theoretical analysis specifies the number of samples k(δ, ε) such that the approximated solution z satisfies |z - z^*| = O(ε n2) with probability 1-δ. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments.