# logistic regression. How to get dual function?

Given pairs $(x_i, y_i), x_i \in R^n , y_i \in R$ we want to solve minimization problem (logistic regression):$\min \frac{1}{2} ||w||^2 + \sum_i^{i=m}\log(1+\exp(-y w\cdot x_i))$. How to do that? I know the dual form is: $\min_{\alpha} D(\alpha)= \frac{1}{2}\sum_{i, j}\alpha_i \alpha_j y_i y_j x_i \cdot x_j + \sum_i\alpha_i \log(\alpha_i) + (C-\alpha_i)\log(C-\alpha_i)$, subject to: $0\le \alpha_i\le C$. How to get dual?

– user88
May 24, 2012 at 12:48
• This is really a mathematical question, but it needs improving before it can be migrated. First, what kind of "dual" do you seek? Second, what is $w$? Third, why doesn't $w$ appear in your putative dual form? Fourth, there are some typos; e.g., $y$ needs to be $y_i$. Fifth, this does not appear to be any form of logistic regression (perhaps because of the typos): what exactly is the connection?
– whuber
May 24, 2012 at 14:40
• @whuber, there are typos, but why do you say it's not a form of LR? May 24, 2012 at 15:26
• @Pardis I might be able to see a connection once the argument of $\exp$ is clarified. In its current form it does not appear to be related to a log probability.
– whuber
May 24, 2012 at 15:33
• I added the explanation to my answer below. May 24, 2012 at 15:56

Tom Minka gives the derivation in this excellent paper "A comparison of numerical optimizers for logistic regression" pdf, section 9

• While this is good material, this is not an answer imo, more like a comment. Jul 22, 2016 at 20:01
• This is four years old. At this point, we could probably just leave it, unless the link is dead. Jul 22, 2016 at 20:38
• Welcome to the site. We are trying to build a permanent repository of high-quality statistical information in the form of questions & answers. Thus, we're wary of link-only answers, due to linkrot. Can you post a full citation & a summary of the information at the link, in case it goes dead? Jul 22, 2016 at 20:39

LIBLINEAR supports $\ell_2$-regularized logistic regression. According to the authors, the package implements the "trust region Newton method". Here, you can find the slides to learn more, but note that it is not based on the dual formulation.

@whuber I am explaining here, because there wasn't space in the comments...

As you know, in logistic regression, the response data are chosen to be realizations of a Bernoulli random variable $Y$. In this GLM, the conditional expectation is, $$\mathbb{E}(Y|X) = \sigma\big(\mathbf{w}^\mathsf{T}\mathbf{x}\big)$$ where $\sigma(z)$ is the logistic function $$\sigma(z) = \frac{1}{1+ \exp(-z)}.$$

Here's the likelihood \begin{aligned} \mathcal{L}(\mathbf{w}) = \operatorname{p}(\mathbf{y}|\mathbf{X};\mathbf{w}) &= \prod_{i=1}^n \operatorname{p}(y_i|\mathbf{x}_i;\mathbf{w})\\ &= \prod_{i=1}^n \sigma\big(\mathbf{w}^\mathsf{T}\mathbf{x}_i\big)^{y_i}\big(1-\sigma(\mathbf{w}^\mathsf{T}\mathbf{x}_i)\big)^{1-y_i}. \end{aligned} and the negative log-likelihood becomes \begin{align} -\ell(\mathbf{w}) = -\log \mathcal{L}(\mathbf{w}) &= -\sum_{i=1}^{n} \log \operatorname{p}(y_i| \mathbf{x}_i;\mathbf{w})\\ &= -\sum_{i=1}^{n} \log\sigma\big(y_i \mathbf{w}^\mathsf{T}\mathbf{x}_i\big)\\ &= \sum_{i=1}^{n} \log\big(1+ \exp\big(-y_i\mathbf{w}^\mathsf{T}\mathbf{x}_i\big)\big) \end{align} where the last equation follows because $y_i \in \{-1,1\}$.

The $\ell_2$-regularization term is the result of MAP estimation of the parameters with a Gaussian prior.

• I am sorry, but didn't OP ask us how to get the dual form? Jul 27, 2012 at 4:37
• that's true, I was answering the related question that came up in the comments above; additionally, I thought that the OP's main question was how to solve the $\ell_2$-regularized problem not how to obtain the dual formulation Aug 7, 2012 at 16:58
• @user1149913 seems to give a good answer to that part Aug 7, 2012 at 17:02

Why not just take partial derivative of minimization function with respect to unknown parameters? You can find a lot of material on the web.

Use the lower bound of the convex function $\log(1+x)$: $$\log (1+x) \ge \log(1+x_1) +(x-x_1)*(d(\log(1+x_1)) )$$ where $d(f)$ is the differentiation of $f$.

Note that the factor of $x$ on the right is your dual variable, which is in between $[0,1]$; now the problem is quadratic in $w$ and can be solved.

• Welcome to the site, @Ashwini. I took the liberty of using CV's $\LaTeX$ markup features to make your post more readable. Please make sure it still says what you want it to. Mar 27, 2013 at 23:38