I am reading the paper on $\ell_0$ regularization of DNNs by Louizos, Welling and Kingma (2017) (Link to arxiv).

In Section 2.1 the authors define the cost function as follows: $$ \mathcal{R}\left( \tilde{\theta}, \pi \right) = \mathbb{E}_{q(z|\pi)}\left[ \frac{1}{N} \left(\sum_{i=1}^N \mathcal{L}\left(h\left( x_i, \tilde{\theta}\circ Z\right), y_i \right) \right)\right] + \lambda\sum_{i=1}^{|\tilde{\theta}|}\pi_i. $$

In the above display, $\tilde{\theta}$ are the weights, $Z$ is a random vector of the same dimension as $\tilde{\theta}$ consisting of independent Bernoulli components $q(Z_i|\pi) \sim Bernoulli (\pi_i)$, and $\circ$ is the element-wise product.

The authors then state the following:

the first term is problematic for $\pi$ due to the discrete nature of $Z$, which does not allow for efficient gradient based optimization.

I am not sure I understand this. Denoting the first term by $\mathcal{R}_1 = \sum_{i=1}^N \frac{1}{N}R_i$ ($R_i$ defined below), and using the notation $\pi_z = \prod \pi_i^{z_i} (1-\pi_i)^{1-z_i}$ and $\mathcal{Z}$ for the set of all possible values of $Z$, we should have $$ R_i := \mathbb{E}_{q(z|\pi)}\left[ \mathcal{L}\left( h\left(x_i, \tilde{\theta}\circ z\right), y_i \right) \right] = \sum_{z \in \mathcal{Z}}\pi_z\mathcal{L}\left( h\left(x_i, \tilde{\theta}\circ z\right), y_i \right) $$

So, it seems to me that the gradient of $R_i$ with respect to $\pi_j$ can be obtained as $$ \frac{d R_i}{d\pi_j} = \sum_{z \in \mathcal{Z}}\mathcal{L}\left( h\left(x_i, \tilde{\theta}\circ z\right), y_i \right) \frac{d\pi_z}{d\pi_j} $$ and $\frac{d\pi_z}{d\pi_j} = \frac{\pi_z}{\pi_j}$ if $z_j=1$ and $-\frac{\pi_z}{1-\pi_j}$ if $z_j=0$. So, it appears that we can obtain the derivative of the first term with respect to $\pi_j$ as well.

My question is the following:

If my above calculation is correct, then the derivatives $\frac{d\mathcal{R}_1}{d\pi_j}$ can be computed, and we can perform SGD on the cost function $\mathcal{R}(\tilde{\theta}, \pi)$. But the authors claim that it cannot be obtained and hence they introduce the `hard concrete' distribution etc. to construct a differentiable cost function.

  • $\begingroup$ What's your question though? Stating it clearly will make sure you get the best answer. $\endgroup$ – DuttaA Nov 22 '18 at 13:15

Your Answer

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

Browse other questions tagged or ask your own question.