How to prove mathematically that a decrease in regularization parameter would result in a decrease in the cost function? Suppose this is my cost function:
$$
J(\theta)=\frac{1}{N}\sum_{i=1}^{N}(y_i-\theta^tx_i)^2 + \lambda |\theta|^2
$$
After optimizing the equation we can find an optimal $\theta^*$, such that:
$$
\theta^*=argmin_{\theta} J(\theta)
$$
My question is: How can I prove mathematically, that a decrease in $\lambda$ would result in a decrease for the overall $J(\theta^*)$?
 A: This is one of those cases where a grand generalization gives a simple demonstration and has important applications.
Suppose, then, that $\Theta$ is any nonempty set, $g,f:\Theta\to\mathbb R$ are functions, $f$ is bounded below, and $g(\theta)\ge 0$ for all $\theta\in\Theta.$  For any number $\lambda$ define
$$\theta^{*}(\lambda) = \inf_{\theta\in\Theta} \left(f(\theta) + \lambda g(\theta)\right).$$
I claim that $\theta^{*}$ is an increasing function at $0;$ that is, for all $\lambda \ge 0,$ $\theta^{*}(\lambda)\ge \theta^{*}(0).$
Proof  Suppose not. Fix $\lambda\ge 0$ and write $$\epsilon = \theta^{*}(0) - \theta^{*}(\lambda) \gt 0.$$ From the definition of the infimum there exists $\theta_0$ for which $f(\theta_0) + \lambda g(\theta_0)$ is no greater than $\theta^{*}(\lambda) + \epsilon/2.$  Because $\lambda$ and $g(\theta_0)$ are nonnegative (by assumption), compute
$$f(\theta_0) \le f(\theta_0) + \lambda g(\theta_0) \le \theta^{*}(\lambda) + \epsilon/2 \lt \theta^{*}(\lambda) + \epsilon \lt \theta^{*}(0)$$
giving $f(\theta_0) \lt \theta^{*}(0).$
This is a contradiction, because (by definition) for every $\theta_0\in\Theta,$ $f(\theta_0) \ge \theta^{*}(0),$ QED.

Given $(x_i),$ $(y_i),$, $\Theta\subset\mathbb{R}^N,$ and any number $\lambda_1,$ take
$$f(\theta) = \frac{1}{N}\sum_{i=1}^N (y_i - \theta^\prime x_i)^2 + \lambda_1|\theta|^2$$
and 
$$g(\theta) = |\theta|^2 \ge 0$$
for all $\theta\in\mathbb{R}^N.$
Applying the claim proves a weak version of the result in the question: increasing $\lambda_1$ to $\lambda_2 = \lambda_1 + \lambda$ cannot decrease $f.$
This is the best possible general result, because there are cases where no decrease is possible.  Any situation where $\Theta$ has a single element $\theta$ and $g(\theta)=0$ can serve as an example.
A: The cost $J$ is being minimised. If for a a particular $\lambda_a$ you minimize the cost $J_a$ with a particular $\theta_a$ then that same $\theta_a$ for a different lower $\lambda_b$ should result in a lower cost $J$ and the minimized $J_b$ for that different lower $\lambda_b$ should be at least lower (because otherwise it would not be an optimum).

Let the cost be the function $J(\theta, \lambda)$. And let $\theta_a$ be the estimate/argmin/optimum for $\lambda_a$, let $\theta_b$ be the estimate/argmin/optimum for $\lambda_b$.
Then
$$J(\theta_a, \lambda_b) < J(\theta_a,\lambda_a)$$
if $$\lambda_b < \lambda_a$$
and if
$$|\theta_a| > 0$$
(the negation of the latter case $|\theta_a| = 0$ is the trivial case in which we would also have $J=0$ and there would not be anything to decrease) 
So the solution $\theta_a$ for $\lambda_b$ gives at least a lower value $J$. Then when we minimize $J$ to end up with a $\theta_b$ we must have at least 
$$\rlap{\overbrace{\phantom{J(\theta_b,\lambda_b) \leq J(\theta_a, \lambda_b)}}^{\substack{\text{The solution with $\theta_b$}\\\text{must be better than or the same as}\\\text{the solution with $\theta_a$}}}} J(\theta_b,\lambda_b) \leq \underbrace{J(\theta_a, \lambda_b) < J(\theta_a,\lambda_a)}_{\substack{\text{With the same $\theta_a$}\\\text{and $\lambda_b < \lambda_a$}\\\text{the cost will be lower}}} $$
