23
votes
Accepted
The proof of equivalent formulas of ridge regression
The classic Ridge Regression (Tikhonov Regularization) is given by:
$$ \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2} $$
The claim above is that ...
- 1,157
13
votes
The proof of equivalent formulas of ridge regression
It's perhaps worth reading about Lagrangian duality and a broader relation (at times equivalence) between:
optimization subject to hard (i.e. inviolable) constraints
optimization with penalties for ...
- 23k
13
votes
The proof of equivalent formulas of ridge regression
A less mathematically rigorous, but possibly more intuitive, approach to understanding what is going on is to start with the constraint version (equation 3.42 in the question) and solve it using the ...
- 52.9k
9
votes
The proof of equivalent formulas of ridge regression
They are not equivalent.
For a constrained minimization problem
$$\min_{\mathbf b} \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2\\
s.t. \sum_{j=1}^p b_j^2 \leq t,\;\;\; \mathbf b = (b_1,...,...
- 60.8k
8
votes
KKT in a nutshell graphically
The basic idea of the KKT conditions as necessary conditions for an optimum is that if they don't hold at a feasible point $\mathbf{x}$, then there exists a direction $\boldsymbol{\delta}$ that will ...
- 23k
6
votes
Accepted
SVM: Why alpha for non support vector is zero and why most vectors have zero alpha?
I have found the answer on my question which can be explained geometrically very well.
We know that the complementary condition of the KKT-conditions says:
$$\alpha\geq0, \alpha(y_i(w^Tx_i + b) - 1) = ...
- 1,039
6
votes
Why are the Lagrange multipliers sparse for SVMs?
The Lagrange multipliers in the context of SVMs are typically denoted $\alpha_i$. The fact that one often observes that most $\alpha_i=0$ is a direct consequence of the Karush-Kuhn-Tucker (KKT) dual ...
- 47.6k
5
votes
KKT in a nutshell graphically
f(x) being convex is necessary for KKT to be sufficient for x to be local minimum. If f(x) or -g(x) are not convex, x satisfying KKT could be either local minimum, saddlepoint, or local maximum.
g(x) ...
- 13.5k
5
votes
Likelihood-ratio and score tests of a (non)linear combination of coefficients
To give p values and confidence intervals of linear combinations of coefficients using the likelihood-ratio and score tests, it appears necessary to rearrange the model specification so that some ...
- 2,423
4
votes
Accepted
R built-in Breusch-Pagan Test getting different results from manual Calculation
You used 19 degrees of freedom while bptest() used only 18. The reason for this discrepancy is that you cannot include the identical regressors ...
- 16.1k
4
votes
Accepted
Calculating the value of $b^{*}$ in an SVM
For SVMs the decision boundaries are given by $\omega^{*T}x^{(i)} + b = \pm 1$, and $\frac{-b}{||\omega||}$ is the distance from the origin to the hyperplane.
The closest positive and negative ...
- 14.3k
4
votes
SVM: Why alpha for non support vector is zero and why most vectors have zero alpha?
A support is actually a vector whose $\alpha$ is non-zero. It is a definition, there is nothing to prove from the equation here.
- 10.4k
3
votes
Accepted
Maximum Entropy Discrete Distribution
You have to keep in mind that the index in the summation is a "dummy index", it is only a placeholder for $1,2,3,\cdots$. Therefore, it is not the same $i$ that appears in the derivative! We ...
- 2,690
3
votes
Calculating the value of $b^{*}$ in an SVM
I am also following Andrew Ng's note on SVM and had the same question. Inspired by OP's description and the first answer, I believe I have found a "natural" way of arriving at the solution
$$...
- 31
3
votes
Minimize $f(A,B)$ s.t. $\text{exp}(A)^T \text{exp}(B)=J_K$
I'm posting some work I've done on your problem, this is not a full answer but I think it almost covers it all.
Loss function
$f$, as you wrote it, is linear. This is good enough, but that equation ...
- 5,130
3
votes
How to choose between dual gradient descent and the method of Lagrangian multipliers?
We need to satisfy the KKT conditions(first order necessary conditions) in order to find the optimal solution.
KKT conditions for equality constraints:
$$
Stationary: \nabla_x \mathcal{L}(x,\lambda) =...
- 76
3
votes
LASSO relationship between $\lambda$ and $t$
This is the standard solution for ridge regression:
$$
\beta = \left( X'X + \lambda I \right) ^{-1} X'y
$$
We also know that $\| \beta \| = t$, so it must be true that
$$
\| \left( X'X + \lambda I \...
- 12.8k
2
votes
Can I use a spatially lagged Dependent Variable while using Spatial Error Model?
Yes, but that's essentially the Spatial Durbin Model, now. Looks like the equation below:
y = ρWy + Xβ + θWX + u
SDM synthesizes the advantages of a spatial lag ...
- 151
2
votes
LASSO relationship between $\lambda$ and $t$
This question relates to Is the magnitude coefficient vector in Ridge regression monotonic in lambda? which sketches a situation for ridge regression, but it is similar for Lasso.
Consider the ...
- 86.6k
2
votes
Accepted
Are Lagrange multipliers of regularization terms learned or set?
$\lambda$ is a hyper-parameter. Typically user must set the hyper-parameter. There are some ways of automatically selecting a hyper-parameter by optimizing an auxiliary function, for example as done ...
- 605
2
votes
Accepted
Logarithms in Karush-Kuhn-Tucker conditions
Maybe this graphic helps
So you see intuitively the minima in the points (0,0), (0,1) and (1,0).
But indeed, the functions $\log(x)$ and $\log(y)$ are not defined in those points. The problem is a ...
- 86.6k
2
votes
Accepted
How to maximize the ELBO in coordinate ascent variational inference
From (22) to (23), it involves functional derivatives. The same question can be found here.
From (23) to (24), it just set (23) equals to 0 and get the corresponding $q_j(z_j)$. The constant in the ...
- 36
2
votes
Rewrite $\frac{1}{2}||x-u||_2^2$ subject to $||x||_1\le c$ to lagrangian form with multiplier $\lambda \ge 0$
Define
$$G(x) \triangleq \sup_{\mu \geqslant 0} \mu \cdot \left( \|x\|_1 - c \right).$$
Now, if $\| x \|_1 \leqslant c$, $G(x) = 0$; otherwise, $G(x) = \infty$. Hence
\begin{align}
F(u, c) &= \...
- 1,356
1
vote
Finding the MLEs for pi in a contingency table proof
So, we can write the log-likelihood as $\sum_i\sum_jy_{ij}\log(\pi_{i.}\cdot\pi_{.j})$, which means that the Lagrangian is:
$$\mathcal L=\sum_i\sum_jy_{ij}\log(\pi_{i.}\cdot\pi_{.j})-\lambda\sum_i\pi_{...
- 2,690
1
vote
Accepted
deriving the optimal distribution
Assuming $\ell$ has a minimum at a point $(x_0,y_0)$, $\ell(h(x),y) \ge \ell(h(x_0),y_0) \equiv \ell_0$, then
$$ \iint p(x,y)\ell(h(x),y) \ge \ell_0\iint p(x,y) = \ell_0$$
which means that $\ell_0$ is ...
- 5,410
1
vote
Accepted
incorporating a distribution constraint in a minimisation objective
I would probably remove the lower bound constraint by noting that since all the probabilities are $\geq \beta$, I can optimize over the difference $p^*(x,y) = p(x,y) - \beta$ instead of over $p(x,y)$:
...
- 41.1k
1
vote
Accepted
KKT Conditions for thresholds?
Instead of differentiating w.r.t. the multipliers you should properly write the complementary slackness condition (defined in your link). In your case this is
$$-\mu_1 x=0$$
$$-\mu_2 y=0$$
$$\mu_3 (x+...
- 340
1
vote
Accepted
Convert the following expression w.r.t to the whole dataset instead of element of the dataset?
Yes, it is possible. We have:
$$ w = \sum_{i=1}^n\alpha_ix_i=\alpha_1 x_1+ \alpha_2 x_2 + ... + \alpha_n x_n$$
Then, if we define:
$$X = \begin{pmatrix}
x_1^T\\
x_2^T\\
\vdots\\
x_n^T
\end{pmatrix} \,\...
- 1,220
1
vote
What would happen to the solution of primal SVM problem we had 0 in constraint instead of 1
Then $\mathbf{w} = \mathbf{0}$, $b = 0$ satisfies every constraint, but that's not a useful solution.
Stanford Prof. Stephen Boyd has an excellent discussion in lecture 13 of his Convex Optimization ...
- 23k
Only top scored, non community-wiki answers of a minimum length are eligible