How to check if dependency is convex, concave or none of those? Let as assume that we have a set of tuples of real numbers. Or, in other words, we have a set of (x,y) pairs. The simplest hypothesis (or assumption) about the relation between x and y is that there is a linear relation between them. We can even use a linear regression to determine what values the coefficients of the linear regression have.
But is there a way to determine if there is a statistically significant deviation of this linear dependency? Of course I am speaking about the cases when the deviation from a line is not obvious.
I assume that the question can be answered in the following way. If we have a convex function, (like square root) than a linear fit will give an underestimation in the middle and overestimation on the side of the range of x. Similarly, if we have a concave function (like exponent), we will have an overestimation in the middle and underestimation on the sides.
Is there a standard method to count (or somehow estimate) these under- and over-estimations and determine in this way if the observed measure is statistically significant?
 A: Stephen Wright has a good discussion of one approach to understanding convexity in this NIPS tutorial from 2010. It's in the context of machine learning optimization algorithms where he gives a good definition of convexity about 3:57 minutes into the presentation with topic "First-Order Methods."
http://videolectures.net/nips2010_wright_oaml/
(Apologies for the absence of formulas in this answer -- which would help clarify things -- but I don't know how to integrate mathematical symbols into my response.) 
A: A structured approach to this problem is offered in [1]
More precisely the following hypothesis test of linearity is performed:
    $$\text{H0: The data comes from a model with: $\text{med}(y|x) = \beta x + \alpha$ }$$
You will find more details these papers, more particularly in section 4.3 of 1 where the authors propose a test of linearity (the alternative is convexity/concavity). 
If you have a vector of values of $y$ and a vector of values of $x$, this approach is fairly easy to implement. Check the description of the catline in 3


*

*The Deepest Regression Method (1997). S. Van Aelst, P.J. Rousseeuw, M. Hubert, A Struyf.

*Rousseeuw P., Struyf A., (2002). A Depth Test for Symmetry, in:  Goodness-of-Fit Tests and Model Validity, Birkhauser Boston, pp.401-412.


Edit:
You might want to have a look at the recent conproj R package by     X. Liao, M. C. Meyer. There is also a JoSS article associated with it by the same authors. Among other things, this package implements a (bootrap based) test of whether the function $f$ in the model:
$$y_i=f(x_i)+e_i,\; e_i\sim\text{i.i.d.}\;\mathcal{N}(0,1)$$ 
is convex (concave) or linear.
