3 Uncertainty Quantification in Lasso-Type Regularization Problems
87
To solve the Karush–Kuhn–Tucker conditions, we split the problem into two
cases as per Eq. (3.13), λ = 0 and h(β) = 0. We then solve Eq. (3.12) under each
equality constraint. We throw away any solution that does not satisfy primal or dual
feasibility and then choose the solution that achieves the lowest value.
For the case λ = 0, we need to find the global unconstrained minimum of f . If
the primal feasibility constraint h(β) ≤ 0 is satisfied at the global minimum of f ,
then we have found a solution. Obviously, this solution must be the optimal solution
of the original constrained problem as well.
If h(β) > 0 at the global minimum of f , then we need to find the minimum of
f under the constraint that h(β) = 0. We could do so by finding a joint solution
to the system of equations formed by Eq. (3.12) and h(β) = 0. Alternatively, we
could gradually increase λ until the global unconstrained minimum g(λ) of f + λh
satisfies h(β) = 0. Indeed, due to the form of the objective function, increasing λ
will favor β that have lower values for h(β), so eventually, h(β) = 0. By strong
duality, we also know that finding this λ is equivalent to maximizing the Lagrange
dual function g(λ) over λ ≥ 0.
3.2 Parameter Estimation
In a statistical modeling problem our task is to estimate β from the data Y and X.
There are several methods to estimate these parameters in a linear model. We will
discuss some of them and their properties.
3.2.1 Ordinary Least Squares
In OLS [5], we estimate the parameters by minimizing the sum of the squared errors:
ˆ
β
OLS := arg min
β
R(β)
(3.16)
where
R(β) :=
n
i=1
2
i =
n
i=1
(y i − x
T
i β)
2
= =Y − Xβ
2
2 .
(3.17)
We have used ·· 2 to denote the standard Euclidean norm that is z 2 :=
n
i=1 z 2
i .
A necessary condition to have a minimum for Eq. (3.17) is
∂
∂β
R(β) = −2X
T Y + 2(X
T X)β = 0.
(3.18)
87
To solve the Karush–Kuhn–Tucker conditions, we split the problem into two
cases as per Eq. (3.13), λ = 0 and h(β) = 0. We then solve Eq. (3.12) under each
equality constraint. We throw away any solution that does not satisfy primal or dual
feasibility and then choose the solution that achieves the lowest value.
For the case λ = 0, we need to find the global unconstrained minimum of f . If
the primal feasibility constraint h(β) ≤ 0 is satisfied at the global minimum of f ,
then we have found a solution. Obviously, this solution must be the optimal solution
of the original constrained problem as well.
If h(β) > 0 at the global minimum of f , then we need to find the minimum of
f under the constraint that h(β) = 0. We could do so by finding a joint solution
to the system of equations formed by Eq. (3.12) and h(β) = 0. Alternatively, we
could gradually increase λ until the global unconstrained minimum g(λ) of f + λh
satisfies h(β) = 0. Indeed, due to the form of the objective function, increasing λ
will favor β that have lower values for h(β), so eventually, h(β) = 0. By strong
duality, we also know that finding this λ is equivalent to maximizing the Lagrange
dual function g(λ) over λ ≥ 0.
3.2 Parameter Estimation
In a statistical modeling problem our task is to estimate β from the data Y and X.
There are several methods to estimate these parameters in a linear model. We will
discuss some of them and their properties.
3.2.1 Ordinary Least Squares
In OLS [5], we estimate the parameters by minimizing the sum of the squared errors:
ˆ
β
OLS := arg min
β
R(β)
(3.16)
where
R(β) :=
n
i=1
2
i =
n
i=1
(y i − x
T
i β)
2
= =Y − Xβ
2
2 .
(3.17)
We have used ·· 2 to denote the standard Euclidean norm that is z 2 :=
n
i=1 z 2
i .
A necessary condition to have a minimum for Eq. (3.17) is
∂
∂β
R(β) = −2X
T Y + 2(X
T X)β = 0.
(3.18)