Minimizing Quadratic Functions in Constant Time
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:
n×n is a matrix and d, b ∈ 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.
complexity. However, we still need to compute the matrix-vector product of size n, which requires O(n) time. Clarkson et al. [7] proposed sublinear-time algorithms for special cases of quadratic function minimization. However, it is "sublinear" with respect to the number of pairwise interactions of the variables, which is O(n 2 ), and their algorithms require O(n log c n) time for some c ≥ 1.
Our contributions: Let A ∈ R n×n be a matrix and d, b ∈ R n be vectors. Then, we consider the following quadratic problem: 
Here, ·, · denotes the inner product and diag(d) denotes the matrix whose diagonal entries are specified by d. Note that a constant term can be included in (1); however, it is irrelevant when optimizing (1), and hence we ignore it.
Let z * ∈ R be the optimal value of (1) and let , δ ∈ (0, 1) be parameters. Then, the main goal of this paper is the computation of z with |z − z * | = O( n 2 ) with probability at least 1 − δ in constant time, that is, independent of n. Here, we assume the real RAM model [6], in which we can perform basic algebraic operations on real numbers in one step. Moreover, we assume that we have query accesses to A, b, and d, with which we can obtain an entry of them by specifying an index. We note that z * is typically Θ(n 2 ) because v, Av consists of Θ(n 2 ) terms, and v, diag(d)v and b, v consist of Θ(n) terms. Hence, we can regard the error of Θ( n 2 ) as an error of Θ( ) for each term, which is reasonably small in typical situations.
Let ·| S be an operator that extracts a submatrix (or subvector) specified by an index set S ⊂ N; then, our algorithm is defined as follows, where the parameter k := k( , δ) will be determined later.
The authors prove that it is possible to approximately compute the minimum of quadratic functions by solving a sub-sampled instance in a constant number of coordinates. Their main tool is a proving a weak-regularity lemma sort of result for quadratic functions. They utilize tools developed for defining limits of dense graphs.  The authors present evidence for the method by solving several synthetic instances, and also apply the algorithm to quickly estimate Pearson divergence in several (synthetic) instances.
The main novelty of the paper is to in fact _prove_ that as long as the quadratic minimization problem has bounded coefficients, solving a subsampled instance can provide a meaningful approximation. The statement / proof is technically challenging, even though a lot of the tools were already developed in the context of graph limits.   I am of the opinion that the paper needs to do more to convince that this can in fact be practically useful. Theoretically, the requirement for number of partitions (and hence samples) to be 2^(1/eps^2) is necessary (see Bounds for graph regularity and removal lemmas, Conlon and Fox). Such a high sample complexity would render the result not useful in practice. The authors claim that their experiments suggest that much smaller sample complexities suffice. However, to me, the (synthetic) experiments seem unconvincing. The instances are drawn from a large random distribution. For these instances, I suspect that concentration of measure phenomenon already implies that the optimas are tightly concentrated. The authors should at least report the range of optima and the range of answers generated by the algorithm, and hopefully design more experiments that can demonstrate practical impact.   Minor comments / typos: - Lem 3.2 — There is something incorrect in the claim here. The dependence on K should be K^2 because of linearity, as can be seen by applying the lemma to f / K and g/K. I suspect the first line has a mistake. An alternate proof wouldThe proof could integrate over L = {x | h(x) <= tau}, whereby there would be no tau_1, tau_2 in the integrand. - Cor 3.4 — The second last claim ‘Since P^t is a refinement of the …,’ is the key component of the proof, and needs a proof / reference. - Lem 3.5 — The lhs should also have a factor L