Critical points and Convexity? Function $f(x)$ has no critical points in $M$, can we say $f(x)$ is either convex or concave over $M$? 

That partially depends on what you mean by Convex. If you mean no critical points imply a second derivative of constant sign there's the counter example above. If you mean Convex in that a line drawn between any two points on one side of the curve always stays on that side of the curve, then the answer seems a little more complicated. The first version depends on the curve and its embedding in the plane. The second version is only dependent on the shape of the curve itself. Different version are needed depending on your optimization problem.  
Critical points occur where the derivative is zero or undefined. Rotate the curve about an axis perpendicular to the plane through the point of tangency, that critical point ceases to have a derivative of zero. Yet, no matter how you rotate it, slide it around, or reflect it, whether or not it is convex according to the second version remains unchanged. 
For example, there exists a rotation under which $f(x)=2x+\sin{x}$ has infinitely many critical points, though it has none if left unchanged. 
A parabola has 1 critical point and one vertex. They are not always one and the same under rotations. It is convex.  A circle has 4 critical points and is convex and has no vertices. 
Curvature better characterizes which shape is convex in the latter sense. That is proportional to the second derivative. If the second derivative is zero, so is the curvature. If a point on the curve has zero second derivative and its next highest non-zero derivative is an odd-order derivative, it is an inflection point and is not convex. If the third on up are all zero, this point doesn't disqualify convexity. 
The second derivative of $f(x)=2x+\sin{x}$ is: $f''(x)=-\sin{x}$
It has zeroes at integer multiples of $\pi$. The third derivative has an absolute value of 1 at those points. So they are all points of inflection indicating that the overall shape isnt' convex. 
