7
$\begingroup$

I'm currently in the process of trying to understand the paper Regularization Paths for Generalized Linear Models via Coordinate Descent by Friedman et al. with regard to the regularization of logistic regression. Unfortunately, I was not able to figure out the exact algorithm that is used for optimization. I was looking for other papers that use coordinate descent in this context and came across Sparse logistic regression for text categorization by Genkin et al. They go into more detail and in section 3.1 they mention

Let $f(\beta_j)$ be the objective expressed as the function of only one component $\beta_j$ with all the rest being fixed, and $Q(\beta_j, \Delta_j)$ be an upper bound on the second derivative of $f (\cdot)$ in the $\Delta_j$-vicinity of $\beta_j$ , $\Delta_j > 0$:
$Q(\beta_j , \Delta_j ) \geq f (\beta_j + \delta)$ for all $\delta \in [−\Delta_j , \Delta_j ]$.

Later on they use the following formula as upper bound for L2-penalized logistic regression:

$Q(\beta_j , \Delta_j ) = \sum_i x_{ij}^2 F(\beta^T x_i y_i, \Delta_j x_{ij}) + 2\lambda$
$F(r, \delta) = 0.25$ if $|r| \leq |\delta|$
$F(r, \delta) = 1 / (2 + \exp(|r| - |\delta|) + \exp(|\delta| - |r|))$ otherwise.

I was surprised to see that this apparently necessary upper bound was not mentioned in the paper by Friedman et al. In addition, the bound differs between L1 and L2 penalty. What would the bound look in the generic framework proposed by Friedman et al. which is applicable for a wide range of penalties?

My second question is related to the upper bound proposed by Genkin et al. They did not provide or reference a prove that validates there choice. Am I missing something obvious here?

$\endgroup$
  • $\begingroup$ As an aside, there are better penalties to use than L1 or L2, such as the generalised double paretro, the bridge penalty, horseshoe. These penalties have much better "tail" behaviour, as they shrink the larger coefficients less (unlike L1 and L2). Further than can all be fit via the EM algorithm, using a least squares algorithm similar to IRLS (so no loss of computer time). $\endgroup$ – probabilityislogic Jul 6 '12 at 12:13
6
$\begingroup$

It took me a while to figure it out, but I thought I share my results here.

The algorithms used for optimization by Friedman et al. and Genkin et al. are different. The latter use an Majorization-Minimization algorithm and Friedman et al. use iteratively re-weighted least squares (IRLS). Both use coordinate descent inside these particular frameworks, Genkin et al. to find a solution in the MM framework and Friedman et al. to solve the penalized weighted least squares problem inside an IRLS iteration. This means they essentially apply the update formula for weighted least squares: $$ b_j^\text{new} = S \left( \frac{1}{n} \sum_{i=1}^n w_i x_{ij} \left[ y_i - \beta_0 - \sum_{\substack{k=1 \\ k \neq j}}^r \beta_k x_{ik} \right], \lambda \alpha \right) \cdot \left( \frac{1}{n} \sum_{i=1}^n w_i x_{ij}^2 + \lambda (1 - \alpha) \right)^{-1} , $$ where the right hand site is evaluated at the current estimates of $\beta$ and $S(z, \gamma) = \mathrm{sign}(z) (|z| - \gamma)$.

In the case of logistic regression the weight $w_i = \pi(x_i)(1-\pi(x_i))$ and the response $z_i$ ($= y_i$ in the formula above) becomes $$ z_i = \beta_0 + \beta^T x_i + \frac{y_i - \pi(x_i)}{\pi(x_i)(1-\pi(x_i))} ,$$ where $x_i$ denotes the $i$-th row of $X \in \mathbb{R}^{n \times r}$, $y_i \in \{0, 1\}$ the class label, and $$\pi(x_i) = \frac{ \exp(\beta_0 + \beta^T x_i) }{1 + \exp(\beta_0 + \beta^T x_i)} .$$

Substituting, the first term in the update formula becomes for logistic regression: $$ \frac{1}{n} \sum_{i=1}^n w_i x_{ij} \left[ z_i - \beta_0 - \sum_{\substack{k=1 \\ k \neq j}}^r \beta_k x_{ik} \right] \\ = \frac{1}{n} \sum_{i=1}^n w_i x_{ij} \left[ z_i - \beta_0 - \beta^T x_i + \beta_j x_{ij} \right] \\ = \frac{1}{n} \sum_{i=1}^n \pi(x_i)(1 - \pi(x_i)) x_{ij} \left[ \beta_0 + \beta^T x_i + \frac{y_i - \pi(x_i)}{\pi(x_i)(1 - \pi(x_i))} - \beta_0 - \beta^T x_i + \beta_j x_{ij} \right] \\ = \frac{1}{n} \sum_{i=1}^n \pi(x_i)(1 - \pi(x_i)) x_{ij} \left[\frac{y_i - \pi(x_i)}{\pi(x_i)(1 - \pi(x_i))} + \beta_j x_{ij} \right] \\ = \frac{1}{n} \sum_{i=1}^n x_{ij} (y_i - \pi(x_i)) + \pi(x_i)(1 - \pi(x_i)) x_{ij}^2 \beta_j . $$

The intercept $\beta_0$ can be updated by applying $$ \beta_0^\text{new} = \beta_0^\text{old} + \sum_{i=1}^n \frac{y_i - \pi(x_i)}{\pi(x_i)(1 - \pi(x_i))} .$$

Finally, Friedman et al. update $r_i = y_i - \pi(x_i)$ incrementally each time $\beta$ changes: $$ r_i = r_i - \Delta \beta_j \pi(x_i)(1 - \pi(x_i)) x_{ij} ,$$ where $\Delta \beta_j = \beta_j^\text{new} - \beta_j^\text{old}$ is the difference between the old and new estimate for $\beta_j$.

$\endgroup$
  • $\begingroup$ I realize that this is 6 months old at this point, but I do have a question regarding the equation for $z_i$. In section 3 of the Friedman paper they have it listed as $z_i = \widetilde{\beta}_0 + x_i^T\widetilde{\beta} + \dots$ whereas you have it listed as $z_i = \widetilde{\beta}_0 + \widetilde{\beta}^TX + \dots$. I'm confused where the difference between the whole set ($\beta^TX$) and the single row ($x_i^T\beta$) comes from. Any thoughts? $\endgroup$ – gallamine Dec 5 '12 at 20:12
  • $\begingroup$ That was indeed a typo, I fixed this above. $\endgroup$ – sebp Feb 28 '13 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.