# Solution of Cox Lasso dual optimization Problem

In https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-110.html, page 12-13, the authors derived a dual form of Cox model:

Some Definitions

In order to define the dual, the optimization problem for the Cox model can be rewritten,assuming the data is in a matrix $$X = [x_1,...,x_n] \in {\mathbb R}^{d\times n}$$ for $$n$$ samples and $$\beta \in {\mathbb R}^d$$. A failure times matrix can be defined as $$\Delta:= (\delta _{ij} \in \{0, 1\}^{f\times n}$$where $$f$$ is the number of unique failure times (ordered increasingly $$t_1 < \cdots < t_f$$ and $$j(i)$$ is the index of the sample failing at time $$t_i$$) and $$\delta_{ij} = 1$$ if $$j \in R_i$$ (the set of indices of samples with death or censor times occurring after $$t_i$$). $$D_i$$ is the death indicator where 1 is for when death occurred and 0 is for censoring.

Assuming $$Z={\mathbf 1}\beta ^t X \in \mathbb{R}^{f\times n}$$ such that $$Z_{ij}=\beta ^T x_j$$ for every $$i$$, where $${\mathbf 1}$$ is a vector of ones in $${\mathbb R}^f$$.

Cox likelihood

The partial likelihood for the Cox model can be written as

$$L(\beta)=\prod\limits_{i=1}^{f} \frac{\lambda_0 (t_i)e^{\beta^T x_{j(i)}}}{\sum_{j\in R_i} \lambda_0(t_i)e^{\beta^T x_{j}}}=\prod\limits_{i=1}^{f} \frac{e^{\beta^T x_{j(i)}}}{\sum_{j\in R_i} e^{\beta^T x_{j}}}$$

In cases of ties (the number of deaths $$d_i>1$$ at time $$t_i$$ ), the above the partial likelihood can be redefined as shown below

$$L(\beta)=\prod\limits_{i=1}^{f} \frac{e^{(\sum_{s\in I(i)} \beta^T x_s)}}{(\sum_{j\in R_i} e^{\beta^T x_{j}})^{d_i}}$$ where $$I(i)=\{k| D_k=1$$ and $$T_k=T_i\}$$(the set of indices where a sample fails at time $$t_i$$).

The partial log likelihood

$$l(\beta)=\log(L(\beta))=\prod\limits_{i=1}^{f} \log \frac{e^{(\sum_{s\in I(i)} \beta^T x_s)}}{(\sum_{j\in R_i} e^{\beta^T x_{j}})^{d_i}}=\prod\limits_{i=1}^{f}[(\sum_{s\in I(i)} \beta^T x_s)-d_i \log(\sum_{j\in R_i}e^{\beta^T x_{j}})]$$

Dual problem of the Cox model

The maximization problem with $$L_1$$ norm penalty can be rewritten as

$$p^*=\prod\limits_{i=1}^{f}[(\sum_{s\in I(i)} \beta^T x_s)-d_i \log(\sum_{j\in R_i}e^{\beta^T x_{j}})]-\lambda ||\beta||_1$$

$$=\max\limits_{\beta,Z}\mathbf c^T\beta-\prod\limits_{i=1}^{f}d_i \log(\sum_{j\in R_i}e^{Z_{ij}})]-\lambda ||\beta||_1$$

$$=\max\limits_{\beta,Z} \mathbf c^T\beta-\prod\limits_{i=1}^{f}d_i \log(\sum\limits_{j=1}^n \delta_{ij} e^{Z_{ij}})]-\lambda ||\beta||_1$$

where $$\mathbf c=\sum\limits_{\{i|D_i=1\}} x_i\in \mathbb R ^d$$

Using a dual variable $$U \in \mathbb R^{f\times n}$$, the dual can be written as

$$p^*=\min\limits_{U}\max\limits_{\beta,Z} \mathbf c^T\beta-\prod\limits_{i=1}^{f}d_i \log(\sum\limits_{j=1}^n \delta_{ij} e^{Z_{ij}})]-\lambda ||\beta||_1+Tr U^T(Z-{\mathbf 1}\beta ^t X)$$

Using $$U^T=[u_1,\cdots, u_f]$$ and $$Z^T=[z_1,\cdots, z_f]$$, where $$u_i, z_i \in \mathbb R^n$$, the trace can be rewritten as

$$Tr U^TZ=\sum\limits_{i=1}^f u_i^Tz_i$$

And

$$p^*=\min \limits_{U}\sum_{i=1}^f\max\limits_{z_i}u_i^Tz_i-d_i log\left(\sum_{j=1}^n \delta_{ij} e^{z_{ij}} \right)+\max \limits_{\beta} \mathbf c^T\beta-\lambda||\beta||_1-tr \beta^TXU^T\boldsymbol{1}$$

For the part contains $$\beta$$, let

$$\begin{eqnarray} f(\beta)&=&\mathbf c^T\beta-\lambda||\beta||_1-tr \beta^TXU^T\boldsymbol{1} \\ &=&\beta^T(\mathbf c-XU^T\boldsymbol{1})-\lambda||\beta||_1 \end{eqnarray}$$

$$f(\beta)$$ is convex but not smooth. Therefore let us consider its subgradient

$$(\mathbf c-XU^T\boldsymbol{1})-\lambda \mathbf v$$ where $$\mathbf v$$ is the subgraident of $$|\beta|$$

The necessary condition for $$f(\beta)$$ to attain an optimum is

$$\exists \beta '$$, such that $$0\in \partial f(\beta ')=\{(\mathbf c-XU^T\boldsymbol{1})-\lambda \mathbf v' \}$$

where $$\mathbf v'\in \partial ||\beta'||_1$$.

In other words, $$\beta ', \mathbf v'$$ should satisify $$\mathbf v‘ =\frac{(\mathbf c-XU^T\boldsymbol{1})}{\lambda}, ||\mathbf v'||_{\infty}<1, \mathbf v'^T \beta ' =||\beta '||_1$$ which is equivalent to

$$f(\beta)=0,||XU^T\boldsymbol{1}-\mathbf c||_{\infty} \le \lambda$$

Hence, the dual problem can be rewritten as

$$p^*=\min \limits_{U}\sum\limits_{i=1}^f\max\limits_{z_i}u_i^Tz_i-d_i log\left(\sum_{j=1}^n \delta_{ij} e^{z_{ij}} \right):||XU^T\boldsymbol{1}-\mathbf c||_{\infty} \le \lambda$$

The authors says, "For each i, consider each optimization problem"

$$\max\limits_{z_i}u_i^Tz_i-d_i log\left(\sum\limits_{j=1}^n \delta_{ij} e^{Z_{ij}} \right):||XU^T\boldsymbol{1}-\mathbf c||_{\infty} \le \lambda$$

where $$\Delta_j$$ is the jth column of $$\Delta$$.

The solution is

$$\begin{cases} d_i\sum\limits_{j=1}^n U_{ij}\log U_{ij} & & {u_i\ge 0,\boldsymbol{1}^Tu_i=1,\forall j:u_{ij}(1-\delta_{ij})=0}\\ +\infty & & \text{otherwise} \end{cases}$$

The dual can then be written as

$$p*=\min\limits_{U} \sum\limits_{i=1}^f d_i \sum\limits_{j=1}^n U_{ij}\log U_{ij}:||XU^T\boldsymbol{1}-\mathbf c||_{\infty} \le \lambda, U\mathbf 1=\mathbf 1, U\ge 0, U \circ \Delta=0$$

where $$\circ$$ represents element-wise multiplication.

But how to obtain the above solution and the dual? I cannot follow that.

• out of curiosity, were you able to figure out the solution to the dual? I'm working on this paper and face the same difficulty.
– Josh
Feb 24, 2020 at 0:32