I have seen in some ML tutorial that functions of the form $f(\vec x) = \vec x^T A \vec x$ ($\vec x \in \mathbb{R}^n$ and $A$ is an $n\times n$ real matrix) can be PAC learned. Can anyone point me to a reference to this fact? 
Learning Quadratic Functions
reference request;machine learning
One approach is to use linear regression.The matrix $A$ has $n^2$ entries; treat each of those entries as an unknown, so you have $n^2$ unknowns.  Now when $x$ is known, $f(x)$ is a linear function of those unknowns.  If you have a set of equations $f(x_i)=y_i$ that are all known to be exactly correct, then you can solve for the unknowns by using linear algebra.  If they are known to be approximately correct (e.g., $||f(x_i)-y_i||_2$ is small), you can use least squares to find the solution for the unknowns that minimizes the sum of the squared errors (that minimizes $\sum_i ||f(x_i)-y_i||_2$).  If a $1-\epsilon$ fraction of them are approximately correct, where $\epsilon \ll 1/n$, then you can pick a random subset of $n$ of them, guess that all of the ones in the subset are correct, use least squares to solve for the unknowns, and check whether that solution seems valid given the remaining equations, and repeat until you find a good solution.