2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Josh
    Feb 24, 2020 at 0:32

0

You must log in to answer this question.

Browse other questions tagged .