Could a quadratic function be empolyed instead of a linear one, for piecewise approximation to learn indexes?

It has been evaluated the use of learned piecewise segments in order to create compressed indexes that substitute classical B+-Tree structures, in order to optimize space and have higher query response speed.

We propose, instead, that given $S= \{(k_1,1), (k_2,2), \dots, (k_n,n)\}$, to employ a function:

$f(k) = a k^2 + b k + c$

where $k\in \mathbb{I}$, is the input key to be searched, and $f(k)$ will give an approximation of the proper index $i$ of $k$. It turns out that $f(k)$ can be built with Newton's Optimization on $a,b,c$ variables with the following objective function:

$E = \frac{\sum_{i=1}^n (f(k_i) - i)^2}{n}$

where $n$ is the number of points in the Cartesian plane that have to be approximated. For small values of $n$, the optimization scheme converges within an given $\epsilon$ tolerance. The idea is that a quadratic approximation function should be more precise than a linear one. The problem is, how to scale this approach to millions of data-points?