Gradient descent and elastic-net logistic regression

Question

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?

Answer 1

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$.