<commit_before>---
layout: post
title: "Implicit Generative Models - What are you GAN-na do? (and other topics)"
categories: general
author: <NAME>
excerpt_separator: <!--more-->
comments: true
---

A few weeks ago, Dar lead our discussion about the following two (mostly unrelated) papers: "Learning in Implicit Generative Models"
by Mohamed and Lakshminarayanan [1] and "A Variational Perspective on Accelerated Methods in Optimization" by Wibisono et al. [2].
The former gives a good overview of techniques for learning in implicit generative models, and has links to 
several of the areas we've discussed this past year, which I'll reference throughout. The latter is a more theoretical paper investigating the nature of accelerated
gradient methods and the natural scope for such concepts. Here we'll introduce and motivate some of the mathematical aspects used in the
paper, and talk about some interesting links of these algorithms to deep learning brought up by Dar.

<!--more-->

# Learning in Implicit Generative Models

Usually, when thinking of probabilistic methods we think of an explicit parametric specification of the distribution of a random
variable $$X$$ in which we directly specify a log-likelihood $$\log q_{\theta}(x)$$ with $$\theta$$ indexing 
a family of possible distributions, with the goal of learning $$theta$$ from the log-likelihood.
In contrast, it is frequently more natural to specify models implicitly via a latent variable 
$$Z \in \mathbb{R}^m$$ which is very easy to generate (e.g multivariate gaussian random variables) 
and then we transform via a deterministic function $$\mathcal{G}_{\theta} : \mathbb{R}^m \mapsto \mathbb{R}^n$$, again with
$$\theta$$ indexing a family of such functions.

But why is the problem of learning $$\theta$$ different here? Namely, it boils down to that the density $$q_{\theta}(x)$$ of $$X$$ 
can be highly intractable for a number of different reasons. Writing $$q(z)$$ for the density of the latent variable $$Z$$, we have
that

$$ q_{\theta}(x) = \frac{ \partial }{\partial x_1 } \cdots \frac{ \partial }{\partial x_d } \int_{z : \mathcal{G}_{\theta}(z) \leq x } 
q(z) \, dz $$

where for $$z, z' \in \mathbb{R}^m$$, $$z \leq z'$$ if and only if $$z_i \leq z'_i$$ for $$i = 1, \ldots, m$$. Although for certain
types of $$\mathcal{G}$$ (e.g when it is easily invertible) this integral is tractable, frequently we have scenarios where $$\mathcal{G}$$ 
is non-linear and is specified by a deep network. As mentioned in our discussion, it could be possible to use normalizing flows (which we've
earlier discussed in the context of [variational inference](https://casmls.github.io/general/2016/09/25/normalizing-flows.html)) to 
allow for this integral to be evaluated in certain circumstances; however if $$d > m$$ or $$\mathcal{G}$$ is not invertible, then we would have to proceed differently. We would then likely encounter several compounding issues:

* The integration region itself may be very hard to determine.
* Even if we knew the integration region, the integral itself may then be computationally demanding, depending on the geometry of
the integration region, it's dimension, and the form of the density $$q(z)$$.
* Even if we can calculate the integral, we then have to take $$d$$ partial derivatives, which in a high-dimensional scenario
is very challenging. 

We would therefore like to have a _likelihood-free_ approach to inference, for which there have been various solutions proposed, including generative adversarial networks (GANs) [3] and classifier ABC [4]. We've discussed ABC  (**A**pproximate **B**ayesian **C**omputation) before on the blog (see [Scott's blog post](https://casmls.github.io/general/2016/10/02/abc.html)
from when we discussed some ways of extending it to higher dimensions), and GANs have been a frequent reoccuring topic; for a nice quick review of GANs, see the beginning of [Robin's blog post](https://casmls.github.io/general/2017/02/23/modified-gans.html). The contribution of this paper is to discuss and bring together the ideas developed in these methods in unison, where previously they have been isolated to more specialized areas of the literature.

_**Notation**: The data are denoted by a random variable $$X$$, whose true data density is $$p^*(x)$$, with intractable model density 
$$q_{\theta}(x)$$. $$\theta$$ is reserved for model parameters; $$\phi$$ is used to denote other parameters, such as for discrminator functions._

## Likelihood-free inference via density ratios and differences

What are the advantages of generative models? Namely, we can easily draw samples from the model - the latent variables $$z$$ should be chosen so that they can be generated easily, and then we can simply evaluate the function $$\mathcal{G}_{\theta}(\cdot)$$ at that point to obtain a draw. Therefore, we should try and use methods which allow for two sets of samples to be compared in order to drive learning. We, for example, can test for whether the true data distribution $$p^*(x)$$ and the model distribution $$q_{\theta}(x)$$ are equal by **directly estimating**

* _the density difference_ $$r_{\theta}(x) = p^*(x) - q_{\theta}(x)$$, or
* _the density ratio_ $$r_{\theta}(x) = p^*(x) / q_{\theta}(x)$$.

As estimating the individual marginal likelihoods will be more difficult than estimating the above ratios/differences directly and using these for comparisons (by seeing how close they are to 0 and 1 respectively), this is therefore an attractive way to proceed. There are then four general approaches to this problem we could take:

* class-probability matching,
* divergence matching,
* ratio matching, and
* moment matching

which we'll discuss in a bit more detail now.

## Four general approaches

_Class-probability matching_ - This boils down to using a classifier which can distingush between observed data and that generated from the model. To describe the general approach, let $$Y$$ denote a random variable which assigns label $$Y = 1$$ to samples from the true data distribution, and $$Y = 0$$ to those from the model distribution, so we can write $$p*(x) = p(x|Y = 1)$$ and $$q_{\theta}(x) = p(x|Y = 0)$$. Writing $$p(y = 1) = \pi$$, it therefore follows by Bayes' formula that

$$ \frac{ p^*(x) }{q_{\theta}(x) } = \frac{ p(Y = 1|x) }{ p(Y = 0 | x) } \cdot \frac{ 1 - \pi}{\pi} $$

and so estimating the density ratio is equivalent to that of class-probability estimation, as we now only need to compute $$p(Y = 1|x)$$.

We now need to specify a scoring function or _discriminator_ $$\mathcal{D}(x; \phi) = p(Y = 1| x)$$ depending on some parameters $$\phi$$, which is linked to the density ratio via the mapping $$\mathcal{D} = \frac{r}{r+1}$$. This means we can use tools for building classifiers (e.g deep neural networks) to specify these functions. Given a scoring function, we now need to specify a proper scoring rule in order to learn parameters. Choosing a Bernoulli (logarithmic) loss, it follows that we can arrive at equation 5 of the paper, namely the GAN objective

$$ \mathcal{L}(\phi, \theta) = \pi \mathbb{E}_{p^*(x)}[ - \log \mathcal{D}(x; \phi) ] + (1 - \pi) \mathbb{E}_{q(z)}\left[ - \log\left( 1 - \mathcal{D}(\mathcal{G}_{\theta}(z); \phi) \right) \right], $$

which we then try and minimize by bi-level optimization. Of course, we can use other scoring rules if desired, with the overall strategy remaining the same. 

_Divergence minimization_ - Here the idea is to try and use a divergence between $$p^*(\cdot)$$ and $$q_{\theta}(\cdot)$$ in order to drive learning. One class of divergences is the $f$-divergence, which for a convex function $$f$$ is of the form

$$ D_f\left[ p^*(X) || q_{\theta}(X) \right] = \int q_{\theta}(x) f\left( \frac{p^*(x)}{q_{\theta}(x)} \right) \, dx. $$

If these seem completely foreign to you, then note that by the following choices of $$f$$, we can obtain some more familar measures of distance link[<sup>1</sup>](#footnotes):

* the KL-divergence - $$f(u) = u \log(u)$$
* the total variation distance - $$f(u) = \tfrac{1}{2} |u - 1|$$
* the $$\chi^2$$ divergence - $$f(u) = (u - 1)^2$$
* the Jensen-Shannon divergence - $$f(u) = u \log\left( \tfrac{2u}{1+u} \right)$$

Writing $$f'$$ for the derivative of $$f$$ and $$f^\dagger$$ for the Fenchel conjugate, this is lower bounded by 

$$ \sup_t \mathbb{E}_{p^*(x)}\left[ t(x) \right] - \mathbb{E}_{q_{\theta}(x)}[f^\dagger(t(x))] $$.

The optimum $$t^*(x)$$ is related to the density ratio via $$t^*(x) = f'(r(x))$$, and so by substituting in this to the above formula, it is equivalent to the following minimization problem in $$r_{\phi}(\cdot)$$

$$ \mathcal{L} = \mathbb{E}_{p^*(x)}\left[ - f'(r_{\phi}(X)) \right] + \mathbb{E}_{q_{\theta}(x)}\left[ f^\dagger(f'(r_{\phi}(x))) \right], $$

which we can again optimize via bi-level optimization. Here there is no discriminator persay, with its taken by the ratio function itself. We note that if we let $$f(u) = u \log(u) - (u+1) \log(u +1)$$, then we again obtain the original GAN objective; the paper on f-GANs by Nowizin et al. [5] discusses this approach further. As mentioned by the authors, there is also an equivalence link[<sup>2</sup>](#footnotes) between this and class probability estimation.

_Ratio matching_ - Writing the true density ratio as $$r^*(x) = p^*(x)\q_{\theta}(x)$$ and allowing $$r_{\phi}(x)$$ to be an approxiation parameterized by $$\phi$$, we could consider the loss 

$$ \mathcal{L} = \frac{1}{2} \int q_{\theta}(x) \left( r_{\phi}(x) - r^*(x) \right)^2 \, dx, $$

which can be generalized to trying to minimize the Bregman divergence for a given function $$f$$. Although we'll discuss more about the Bregman divergence below, for now we'll simply remark that one can show

$$ B_f\left( r^*(x) || r_{\phi}(x) \right) = \mathcal{L}\left( r_{\phi}(x) \right) + D_f\left[ p^*(x) || q_{\theta}(x) \right] $$

where $$\mathcal{L}\left(r_{\phi}(x) \right)$$ is the same ratio loss as that for divergence minimization above. However, as the divergence term is dependent on $$q_{\theta}(x)$$, which is unknown, we could consider an approximation where e.g the ratio is near-optimal, in which case $$D_f\left[ p^*(x) || q_{\theta}(x) \right] = \mathbb{E}_{q_{\theta}(x)}\left[ f(r_{\phi}(x)) \right]$$, with the corresponding approximate loss then used for learning.

_Moment matching_ - One last technique is to try and use the fact that $$p^*$$ and $$q_{\theta}$$ are identical if and only if the expectations of any test statistic $$s(x)$$ are identical under both laws, and so we try and minimize the gap

$$ \mathcal{L}(\phi, \theta) = \left( \mathbb{E}_{p^*(x)}\left[ s(x) \right] - \mathbb{E}_{q(z)}\left[ s(\mathcal{G}_{\theta}(z)) \right] \right)^2. $$

Here the choice of $$s$$ is very important to the performance of the procedure, as ideally we would like all the moments of the distributions to be matched. If the functions $$s(x)$$ belong to a reproducing kernel Hilbert space $$\mathcal{H}$$, this objective can then be reformulated to give

$$ \sup_{f \in \mathcal{F}} \mathbb{E}_{p^*(x)}\left[ f(x) \right] - \mathbb{E}_{q(z)}\left[ f(\mathcal{G}_{\theta}(z)) \right] $$

where $$\mathcal{F} \subseteq \mathcal{H}$$ is some function space, giving rise to the _maximum mean discrepancy_. We can then generalize this to other _integral probability metrics_, such as the Wasserstein distance, which is used in [Wasserstein GANs](https://casmls.github.io/general/2017/02/23/modified-gans.html). In addition, ABC also generally uses a moment matching approach to learning for these types of generative models.

## Conclusion
To conclude, although the choice of whether we implicitly define or prescribe our model affects the type of learning and inferential procedures we can use, the authors highlight that

> "Any implicit model can be easily turned into a prescribed model by adding a simple likelihood function on the generated
> outputs, so the distinction is not essential".

As a consequence, it is important to distingush between the choice of model, the choice of inference and the resulting choice of algorithms; within this, it is perhaps worth noting e.g GANs come under only this third umbrella.

# A Variational Perspective on Accelerated Methods in Optimization

Generally, whenever we are able to prove lower bound results about the performance of a class of algorithms to solve a problem, we would like a practically applicable method which attains this lower bound. In the case of optimizing a sufficiently smooth convex function $$f$$, we can obtain a lower bound of $$1/t^2$$ for the rate of convergence (after $$t$$ steps) of any procedure depending linearly on the gradients of $$f$$; however, vanilla gradient descent only attains a rate of $$1/t$$. Nesterov's _accelerated_ gradient descent, on the other hand, achieves this lower bound rate; much more widely, the phenomenon of acceleration allows us to at least improve convergence rates, if not obtaining the optimal rate.

However, the nature of acceleration is not well understood. This paper attempts to place Nesterov's approach as a methodology for the discretization of a certain class of differential equations. These differential equations are derived as solutions to the Euler-Lagrange problem of minimizing what the authors call the _Bregman Lagrangian_, a functional depending (partially) on the Bregman divergence (this being the only link to the generative models paper we also discussed). 

## Optimization in non-Euclidean geometries and the Bregman Lagrangian

Consider the optimization problem of minimizing $$f(x)$$ over $$\mathcal{X} = \mathbb{R}^d$$, where $$f: \mathcal{X} \mapsto \mathbb{R}$$ is a continuously differentiable convex function, with a unique minimizer $$x^* \in \mathcal{X}$$. To consider a non-Euclidean setting, we suppose $$\mathcal{X}$$ is endowed with a distance generation function $$h : \mathcal{X} \mapsto \mathbb{R}$$ which is continuous differentiable, convex, and is such that $$\| \nabla h(x) \| \to \infty$$ as $$ \| x\| \to \infty$$. This can then be used to define the _Bregman divergence_

$$ D_h(y, x) = h(y) - h(x) - \langle \nabla h(x), y - x \rangle $$

which is non-negative as $$h$$ is convex. (Note that this is not a metric, as it is neither necessarily symmetric not satisify the triangle inequality.) When $$y$$ and $$x$$ are close to each other, this is approximately equal to the Hessian metric

$$ \frac{1}{2} \langle y - x, \nabla^2 h(x) (y - x) \rangle.$$

The authors then introduce (albeit without much intution) the _Bregman Lagrangian_

$$ \mathcal{L}(X, V, t) = e^{\alpha_t + \gamma_t} \left( D_h(X_t + e^{-\alpha_t}V_t, X_t) - e^{\beta_t} f(X_t) \right) $$

where $$X_t \in \mathcal{X}$$ denotes position at time $$t$$, $$V_t \in \mathbb{R}^d$$ the velocity at time $$t$$, and times belong to an interval $$\mathbb{T}$$ of time. Here, the functions $$\alpha, \beta, \gamma : \mathbb{T} \to \mathbb{R}$$ are all continuously differentiable functions of time. From a physical perspective, 

* $$f$$ plays the role of a potential function, whose damping is controlled by $$\beta$$,
* $$D_h\left( \cdot, \cdot \right)$$ plays the role of the kinetic energy (which can be motivated by the approximation to the Hessian metric)
* $$\alpha$$ controls the damping of the velocity term, and $$\gamma$$ that of the overall Lagrangian.

In such a scenario, if we have kinetic energy $$T$$ and potential energy $$V$$, we would set the Lagrangian to be $$\mathcal{L} =  T - V$$; it is clear to see how the Bregman Langrangian is similar in this respect. We would then like to find a path $$\{ X_t : t \in \mathbb{T}\}$$ which minimizes the _action_

$$ \mathcal{J}[X] = \int_{\mathbb{T}} \mathcal{L}(X_t, \dot{X}_t, t ) \, dt $$

(where over-dot's denote differentiation with respect to time) which is a functional on paths. The _principle of least action_ from physics states that the true observed motion of a particle with Langrangian $$\mathcal{L}$$ corresponds to that which minimizes the action; this is the reason why we are interested in such quantities.

## The Euler-Lagrange equation

We can then use the _calculus of variations_ in order to find a curve which minimizes this functional. In order to explain how we can try and do this, we can use the following intutition for when considering the simpler problem of finding the minimizing point of a curve $$f(x)$$ for $$x \in \mathbb{R}$$, for example. Generally, the idea of a stationary point in ordinary calculus is that a function $$f$$ is stationary at a point $$x^*$$ when, after perturbing the function slightly, it _does not change too much_ in the sense that

$$ f(x^* + \epsilon) = f(x^*) + O(\epsilon^2).$$

If $$f$$ is sufficiently differentiable so that for any point $$x$$ we know that (say via Taylor's theorem)

$$ f(x + \epsilon) = f(x) + \epsilon f'(x) + O(\epsilon^2),$$

then we know that points for which $$f'(x) = 0$$ are stationary points. From this, we can then build up critera for when stationary points are local/global minima/maxima and so on.

The same idea is used in the calculus of variations; we aim to find paths $$X$$ for when we perturb them slightly by a new path, the corresponding action does not change too much. However, there is a lot more freedom in what it means to perturb away from a path than for a simple point; although this seems like it may be a problem, provided we formulate our pertubations correctly, it is actually quite advantageous. Namely, we consider perturbing the path by another $$\eta$$ so that the end-points of the new path are unchanged, and examine the behaviour as the scale of $$\eta$$ changes, which we can do simply by perturbing by $$\epsilon \eta$$ for a scalar $$\epsilon$$, and examine what happens as $$\epsilon \to 0$$. We now express this idea mathematically. 

In the simplest case, we impose boundary conditions on $$X$$ at the end points of $$\mathbb{T}$$, so if $$\mathbb{T} = [t_1, t_2]$$, we enforce that $$X(t_1) = a$$ and $$X(t_2) = b$$ (say). Given this, we then seek to find paths $$X$$ for which 

$$ \mathcal{J}[X + \epsilon \eta] = \mathcal{J}[X] + O_{\eta}(\epsilon^2) $$

whenever $$\eta$$ is a (sufficently smooth) path with $$\eta(t_1) = \eta(t_2) = 0$$, and $$\epsilon$$ here acts as a scaling of the pertubation. (The subscript $$\eta$$ on the big-Oh term denotes that the exact scaling depends on $$\eta$$.) As $$\mathcal{J}[X + \epsilon \eta]$$ is a function of $$\epsilon$$ (keeping $$\eta$$ for now fixed), by using Taylor's theorem, integration by parts and the boundary conditions $$\eta(t_1) = \eta(t_2) = 0$$, it is a straightforward exercise to show that 

$$ \mathcal{J}[X + \epsilon \eta] = \mathcal{J}[X] + \epsilon \left( \int_{\mathbb{T}} \left[ \frac{ \partial \mathcal{L}}{\partial X}(X_t, \dot(X)_t, t) - \frac{d}{dt} \left\{ \frac{\partial \mathcal{L}}{\partial V}(X_t, \dot{X}_t, t) \right\}  \right] \eta(t) \, dt \right) + O_{\eta}(\epsilon^2). $$

As we want the $$\epsilon$$ term to be equal to $$0$$ for all "pertubed paths" $$\eta$$, it follows that the $$[ \cdots ]$$ term must be equal to zero, and so stationary paths of the action correspond to solutions of the _Euler-Lagrange equation_

$$ \frac{d}{dt} \left\{ \frac{\partial \mathcal{L}}{\partial V}(X_t, \dot{X}_t, t) \right\} = \frac{ \partial \mathcal{L}}{\partial X}(X_t, \dot(X)_t, t).$$

As expected from ordinary calculus, a path being stationary is a necessary criterion for it to be a local/global minima/maxima of the action; sufficient conditions can be motivated along a similar line as to how we do so in ordinary calculus. 

## Back to the Bregman Lagrangian

The Euler-Lagrange equation for the Bregman Lagrangian gives rise to a second order differential equation of the form (under the assumption that the Hessian matrix $$\nabla^2 h$$ is invertible)

$$ \ddot{X}_t + \left( e^{\alpha_t} - \alpha_t \right) \dot{X}_t + e^{2\alpha_t + \beta_t} \left[ \nabla^2 h(X_t + e^{-\alpha_t} \dot{X}_t \right]^{-1} \nabla f(X_t) $$
$$ + e^{\alpha_t}\left( \dot{\gamma}_t - e^{\alpha}_t \right) \left[ \nabla^2 h(X_t + e^{-\alpha_t} \dot{X}_t \right]^{-1} \left( \nabla h(X_t + e^{-\alpha_t} \dot{X}_t) - \nabla h(X_t) \right) = 0. $$

In order to simplify it slightly, the authors impose the _ideal scaling_ conditions

$$ \dot{\beta}_t \leq e^{\alpha_t} \qquad \text{ and } \qquad \dot{\gamma}_t = e^{\alpha_t} $$

so that the Euler-Lagrange equation simplifies to (after using the second scaling condition)

$$ \ddot{X}_t + \left( e^{\alpha_t} - \alpha_t \right) \dot{X}_t + e^{2\alpha_t + \beta_t} \left[ \nabla^2 h(X_t + e^{-\alpha_t} \dot{X}_t \right]^{-1} \nabla f(X_t) = 0 $$

where the only change is that the last term has been removed. 

As the overall plan is to find discretized solutions for this class of ODE's and analyse their convergence properties, we first want to obtain a convergence rate for exact solutions to the Euler-Lagrange equation. A frequent tool in the analysis of ODE's and PDE's are that of energy methods - from a physical perspective, we are interested in when quantities such as energy are conserved - which allow us to analyse the behaviour of the system. The authors then define an energy functional of the form

$$ \mathcal{E}_t := D_h\left( x^*, X_t + e^{-\alpha_t}\dot{X}_t \right) + e^{\beta_t} \left( f(X_t) - f(x^*) \right) $$.

Again a physical perspective can be used to motivate this. As mentioned before, if a system has kinetic energy $$T$$ and potential energy $$V$$, we let the Lagrangian be of the form $$\mathcal{L} = T - V$$. The corresponding Hamiltonian, corresponding to the total energy of the system, would be of the form $$\mathcal{H} = T + V$$; the above energy functional therefore can be thought of corresponding to the system without the extra damping $$e^{\alpha_t + \gamma_t}$$ in the original Langrangian. However, it is worth noting that here $$\mathcal{E}_t$$ does not correspond to the true Hamiltonian, which is given by  

$$ \mathcal{H}(X, P, t) = e^{\alpha_t + \gamma_t} \left( D_{h^*}( \nabla h(X) + e^{-\gamma_t}P, \nabla h(X) ) + e^{\beta_t} f(X) \right) $$

where $$h^*$$ is the convex dual of $$h$$ and $$P$$ now corresponds to the momentum. Anyways, under the ideal scaling conditions, it is then straightforward to show that if $$X_t$$ is a solution to the Euler-Lagrange equation, $$\mathcal{E}_t$$ is non-increasing in time (this is where the first scaling condition is used), and so it follows that

$$ f(X_t) - f(x^*) \leq C e^{-\beta}_t} $$

for some constant $$C$$. The authors then show that the family of Lagrangians is closed under time dilations (that is, upon time changes $$t \mapsto \tau(t)$$) after suitable transformation of $$(\alpha, \beta, \gamma)$$.

## Discretization schemes

Letting $$p > 0$$ be a parameter, if we choose the choice of parameters

$$ \alpha_t = \log p - \log t $$
$$ \beta_t = p \log t + \log C$$
$$ \gamma_t = p \log t $$

where $$C > 0$$ is a constant, then the ideal scaling conditions are satisfied, and the corresponding Euler-Lagrange equation

$$ \ddot{X}_t + \frac{p +1}{t} \dot{X}_t + C p^2 t^{p-2} \left[ \nabla^2 h\left( X_t + \frac{t}{p} \dot{X}_t \right) \right]^{-1} \nabla f(X_t) = 0 $$

corresponds to the continuous-time limit of Nesterov's accelerated mirror descent (when $$p = 2$$) and that of Nesterov's accelerated cubic-regularized Newton's method (when $$p = 3$$). 

The idea is to now discretize the above ODE in a way so that the discrete-time algorithm attains the same convergence rate as that in the continuous time case. The authors note that a naive discretization appears to be unstable (via empirical observation), and ultimately show that, provided $$f \in \mathcal{C}^p$$ and some other smoothness constraints on $$f$$ and $$h$$ hold, and provided $$C$$ is not sufficiently large, the following discretization sceheme has an $$O(1/(\epsilon k^p))$$ convergence rate:

$$ x_{k+1} = \frac{p}{k+p} z_k + \frac{k}{k+p} y_k, $$
$$ y_k = \mathrm{argmin}_y \left\{ f_{p-1}(y; x_k) + \frac{N}{\epsilon p} \| y - x_k \|^p \right\}, $$
$$ z_k = \mathrm{argmin}_z \left\{ C p k^{(p-1)} \langle \nabla f(y_k), z \rangle + \frac{1}{\epsilon} D_h(z, z_{k-1}) \right\},$$

where $$k^{(p-1)} = k(k+1)\cdots(k+p-2)$$ is the rising factorial, and $$f_{p-1}(y;x)$$ is the $$(p-1)$$-st order Taylor approximation of $$f$$ centered at $$x$$.

## Conclusion


### References

[1] Learning/GAN's paper [link](http://arxiv.org/pdf/1503.01916)

[2] Bregman divergence paper [link](http://arxiv.org/pdf/1503.01916)

[3] Original GAN paper

[4] Classifier ABC paper

[5] f-GANs paper


...

### Footnotes
link[<sup>1</sup>](#footnotes)
<div id="footnotes"></div>
1. Strictly, only the total variation distance is actually a metric; infact, one can show that it is the only $$f$$-divergence (up to scaling) which gives rise to a proper metric.
2. Having had a quick look, I'm unsure on whether this is something which would be practically useful; it could be interesting to give this a further look for whether it is the case.<commit_msg>WIP blog post<commit_after>---
layout: post
title: "Implicit Generative Models - What are you GAN-na do? (and other topics)"
categories: general
author: <NAME>
excerpt_separator: <!--more-->
comments: true
---

A few weeks ago, Dar lead our discussion about the following two (mostly unrelated) papers: "Learning in Implicit Generative Models"
by Mohamed and Lakshminarayanan [1] and "A Variational Perspective on Accelerated Methods in Optimization" by Wibisono et al. [2].
The former gives a good overview of techniques for learning in implicit generative models, and has links to 
several of the areas we've discussed this past year, which I'll reference throughout. The latter is a more theoretical paper investigating the nature of accelerated
gradient methods and the natural scope for such concepts. Here we'll introduce and motivate some of the mathematical aspects and physical intuition used in the
paper, along side an overview of the main contributions.
<!--more-->

# Learning in Implicit Generative Models

Usually, when thinking of probabilistic methods we think of an explicit parametric specification of the distribution of a random
variable $$X$$ in which we directly specify a log-likelihood $$\log q_{\theta}(x)$$ with $$\theta$$ indexing 
a family of possible distributions, with the goal of learning $$theta$$ from the log-likelihood.
In contrast, it is frequently more natural to specify models implicitly via a latent variable 
$$Z \in \mathbb{R}^m$$ which is very easy to generate (e.g multivariate gaussian random variables) 
and then we transform via a deterministic function $$\mathcal{G}_{\theta} : \mathbb{R}^m \mapsto \mathbb{R}^n$$, again with
$$\theta$$ indexing a family of such functions.

But why is the problem of learning $$\theta$$ different here? Namely, it boils down to that the density $$q_{\theta}(x)$$ of $$X$$ 
can be highly intractable for a number of different reasons. Writing $$q(z)$$ for the density of the latent variable $$Z$$, we have
that

$$ q_{\theta}(x) = \frac{ \partial }{\partial x_1 } \cdots \frac{ \partial }{\partial x_d } \int_{z : \mathcal{G}_{\theta}(z) \leq x } 
q(z) \, dz $$

where for $$z, z' \in \mathbb{R}^m$$, $$z \leq z'$$ if and only if $$z_i \leq z'_i$$ for $$i = 1, \ldots, m$$. Although for certain
types of $$\mathcal{G}$$ (e.g when it is easily invertible) this integral is tractable, frequently we have scenarios where $$\mathcal{G}$$ 
is non-linear and is specified by a deep network. As mentioned in our discussion, it could be possible to use normalizing flows (which we've
earlier discussed in the context of [variational inference](https://casmls.github.io/general/2016/09/25/normalizing-flows.html)) to 
allow for this integral to be evaluated in certain circumstances; however if $$d > m$$ or $$\mathcal{G}$$ is not invertible, then we would have to proceed differently. We would then likely encounter several compounding issues:

* The integration region itself may be very hard to determine.
* Even if we knew the integration region, the integral itself may then be computationally demanding, depending on the geometry of
the integration region, it's dimension, and the form of the density $$q(z)$$.
* Even if we can calculate the integral, we then have to take $$d$$ partial derivatives, which in a high-dimensional scenario
is very challenging. 

We would therefore like to have a _likelihood-free_ approach to inference, for which there have been various solutions proposed, including generative adversarial networks (GANs) [3] and classifier ABC [4]. We've discussed ABC  (**A**pproximate **B**ayesian **C**omputation) before on the blog (see [Scott's blog post](https://casmls.github.io/general/2016/10/02/abc.html)
from when we discussed some ways of extending it to higher dimensions), and GANs have been a frequent reoccuring topic; for a nice quick review of GANs, see the beginning of [Robin's blog post](https://casmls.github.io/general/2017/02/23/modified-gans.html). The contribution of this paper is to discuss and bring together the ideas developed in these methods in unison, where previously they have been isolated to more specialized areas of the literature.

_**Notation**: The data are denoted by a random variable $$X$$, whose true data density is $$p^*(x)$$, with intractable model density 
$$q_{\theta}(x)$$. $$\theta$$ is reserved for model parameters; $$\phi$$ is used to denote other parameters, such as for discrminator functions._

## Likelihood-free inference via density ratios and differences

What are the advantages of generative models? Namely, we can easily draw samples from the model - the latent variables $$z$$ should be chosen so that they can be generated easily, and then we can simply evaluate the function $$\mathcal{G}_{\theta}(\cdot)$$ at that point to obtain a draw. Therefore, we should try and use methods which allow for two sets of samples to be compared in order to drive learning. We, for example, can test for whether the true data distribution $$p^*(x)$$ and the model distribution $$q_{\theta}(x)$$ are equal by **directly estimating**

* _the density difference_ $$r_{\theta}(x) = p^*(x) - q_{\theta}(x)$$, or
* _the density ratio_ $$r_{\theta}(x) = p^*(x) / q_{\theta}(x)$$.

As estimating the individual marginal likelihoods will be more difficult than estimating the above ratios/differences directly and using these for comparisons (by seeing how close they are to 0 and 1 respectively), this is therefore an attractive way to proceed. There are then four general approaches to this problem we could take:

* class-probability matching,
* divergence matching,
* ratio matching, and
* moment matching

which we'll discuss in a bit more detail now.

## Four general approaches

_Class-probability matching_ - This boils down to using a classifier which can distingush between observed data and that generated from the model. To describe the general approach, let $$Y$$ denote a random variable which assigns label $$Y = 1$$ to samples from the true data distribution, and $$Y = 0$$ to those from the model distribution, so we can write $$p*(x) = p(x|Y = 1)$$ and $$q_{\theta}(x) = p(x|Y = 0)$$. Writing $$p(y = 1) = \pi$$, it therefore follows by Bayes' formula that

$$ \frac{ p^*(x) }{q_{\theta}(x) } = \frac{ p(Y = 1|x) }{ p(Y = 0 | x) } \cdot \frac{ 1 - \pi}{\pi} $$

and so estimating the density ratio is equivalent to that of class-probability estimation, as we now only need to compute $$p(Y = 1|x)$$.

We now need to specify a scoring function or _discriminator_ $$\mathcal{D}(x; \phi) = p(Y = 1| x)$$ depending on some parameters $$\phi$$, which is linked to the density ratio via the mapping $$\mathcal{D} = \frac{r}{r+1}$$. This means we can use tools for building classifiers (e.g deep neural networks) to specify these functions. Given a scoring function, we now need to specify a proper scoring rule in order to learn parameters. Choosing a Bernoulli (logarithmic) loss, it follows that we can arrive at equation 5 of the paper, namely the GAN objective

$$ \mathcal{L}(\phi, \theta) = \pi \mathbb{E}_{p^*(x)}[ - \log \mathcal{D}(x; \phi) ] + (1 - \pi) \mathbb{E}_{q(z)}\left[ - \log\left( 1 - \mathcal{D}(\mathcal{G}_{\theta}(z); \phi) \right) \right], $$

which we then try and minimize by bi-level optimization. Of course, we can use other scoring rules if desired, with the overall strategy remaining the same. 

_Divergence minimization_ - Here the idea is to try and use a divergence between $$p^*(\cdot)$$ and $$q_{\theta}(\cdot)$$ in order to drive learning. One class of divergences is the $f$-divergence, which for a convex function $$f$$ is of the form

$$ D_f\left[ p^*(X) || q_{\theta}(X) \right] = \int q_{\theta}(x) f\left( \frac{p^*(x)}{q_{\theta}(x)} \right) \, dx. $$

If these seem completely foreign to you, then note that by the following choices of $$f$$, we can obtain some more familar measures of distance link[<sup>1</sup>](#footnotes):

* the KL-divergence - $$f(u) = u \log(u)$$
* the total variation distance - $$f(u) = \tfrac{1}{2} |u - 1|$$
* the $$\chi^2$$ divergence - $$f(u) = (u - 1)^2$$
* the Jensen-Shannon divergence - $$f(u) = u \log\left( \tfrac{2u}{1+u} \right)$$

Writing $$f'$$ for the derivative of $$f$$ and $$f^\dagger$$ for the Fenchel conjugate, this is lower bounded by 

$$ \sup_t \mathbb{E}_{p^*(x)}\left[ t(x) \right] - \mathbb{E}_{q_{\theta}(x)}[f^\dagger(t(x))] $$.

The optimum $$t^*(x)$$ is related to the density ratio via $$t^*(x) = f'(r(x))$$, and so by substituting in this to the above formula, it is equivalent to the following minimization problem in $$r_{\phi}(\cdot)$$

$$ \mathcal{L} = \mathbb{E}_{p^*(x)}\left[ - f'(r_{\phi}(X)) \right] + \mathbb{E}_{q_{\theta}(x)}\left[ f^\dagger(f'(r_{\phi}(x))) \right], $$

which we can again optimize via bi-level optimization. Here there is no discriminator persay, with its taken by the ratio function itself. We note that if we let $$f(u) = u \log(u) - (u+1) \log(u +1)$$, then we again obtain the original GAN objective; the paper on f-GANs by Nowizin et al. [5] discusses this approach further. As mentioned by the authors, there is also an equivalence link[<sup>2</sup>](#footnotes) between this and class probability estimation.

_Ratio matching_ - Writing the true density ratio as $$r^*(x) = p^*(x)\q_{\theta}(x)$$ and allowing $$r_{\phi}(x)$$ to be an approxiation parameterized by $$\phi$$, we could consider the loss 

$$ \mathcal{L} = \frac{1}{2} \int q_{\theta}(x) \left( r_{\phi}(x) - r^*(x) \right)^2 \, dx, $$

which can be generalized to trying to minimize the Bregman divergence for a given function $$f$$. Although we'll discuss more about the Bregman divergence below, for now we'll simply remark that one can show

$$ B_f\left( r^*(x) || r_{\phi}(x) \right) = \mathcal{L}\left( r_{\phi}(x) \right) + D_f\left[ p^*(x) || q_{\theta}(x) \right] $$

where $$\mathcal{L}\left(r_{\phi}(x) \right)$$ is the same ratio loss as that for divergence minimization above. However, as the divergence term is dependent on $$q_{\theta}(x)$$, which is unknown, we could consider an approximation where e.g the ratio is near-optimal, in which case $$D_f\left[ p^*(x) || q_{\theta}(x) \right] = \mathbb{E}_{q_{\theta}(x)}\left[ f(r_{\phi}(x)) \right]$$, with the corresponding approximate loss then used for learning.

_Moment matching_ - One last technique is to try and use the fact that $$p^*$$ and $$q_{\theta}$$ are identical if and only if the expectations of any test statistic $$s(x)$$ are identical under both laws, and so we try and minimize the gap

$$ \mathcal{L}(\phi, \theta) = \left( \mathbb{E}_{p^*(x)}\left[ s(x) \right] - \mathbb{E}_{q(z)}\left[ s(\mathcal{G}_{\theta}(z)) \right] \right)^2. $$

Here the choice of $$s$$ is very important to the performance of the procedure, as ideally we would like all the moments of the distributions to be matched. If the functions $$s(x)$$ belong to a reproducing kernel Hilbert space $$\mathcal{H}$$, this objective can then be reformulated to give

$$ \sup_{f \in \mathcal{F}} \mathbb{E}_{p^*(x)}\left[ f(x) \right] - \mathbb{E}_{q(z)}\left[ f(\mathcal{G}_{\theta}(z)) \right] $$

where $$\mathcal{F} \subseteq \mathcal{H}$$ is some function space, giving rise to the _maximum mean discrepancy_. We can then generalize this to other _integral probability metrics_, such as the Wasserstein distance, which is used in [Wasserstein GANs](https://casmls.github.io/general/2017/02/23/modified-gans.html). In addition, ABC also generally uses a moment matching approach to learning for these types of generative models.

## Conclusion
To conclude, although the choice of whether we implicitly define or prescribe our model affects the type of learning and inferential procedures we can use, the authors highlight that

> "Any implicit model can be easily turned into a prescribed model by adding a simple likelihood function on the generated
> outputs, so the distinction is not essential".

As a consequence, it is important to distingush between the choice of model, the choice of inference and the resulting choice of algorithms; within this, it is perhaps worth noting e.g GANs come under only this third umbrella.

# A Variational Perspective on Accelerated Methods in Optimization

Generally, whenever we are able to prove lower bound results about the performance of a class of algorithms to solve a problem, we would like a practically applicable method which attains this lower bound. In the case of optimizing a sufficiently smooth convex function $$f$$, we can obtain a lower bound of $$1/t^2$$ for the rate of convergence (after $$t$$ steps) of any procedure depending linearly on the gradients of $$f$$; however, vanilla gradient descent only attains a rate of $$1/t$$. Nesterov's _accelerated_ gradient descent, on the other hand, achieves this lower bound rate; much more widely, the phenomenon of acceleration allows us to at least improve convergence rates, if not obtaining the optimal rate.

However, the nature of acceleration is not well understood. This paper attempts to place Nesterov's approach as a methodology for the discretization of a certain class of differential equations. These differential equations are derived as solutions to the Euler-Lagrange problem of minimizing what the authors call the _Bregman Lagrangian_, a functional depending (partially) on the Bregman divergence (this being the only link to the generative models paper we also discussed). 

## Nesterov's accelerated gradient descent

## Optimization in non-Euclidean geometries and the Bregman Lagrangian

Consider the optimization problem of minimizing $$f(x)$$ over $$\mathcal{X} = \mathbb{R}^d$$, where $$f: \mathcal{X} \mapsto \mathbb{R}$$ is a continuously differentiable convex function, with a unique minimizer $$x^* \in \mathcal{X}$$. To consider a non-Euclidean setting, we suppose $$\mathcal{X}$$ is endowed with a distance generation function $$h : \mathcal{X} \mapsto \mathbb{R}$$ which is continuous differentiable, convex, and is such that $$\| \nabla h(x) \| \to \infty$$ as $$ \| x\| \to \infty$$. This can then be used to define the _Bregman divergence_

$$ D_h(y, x) = h(y) - h(x) - \langle \nabla h(x), y - x \rangle $$

which is non-negative as $$h$$ is convex. (Note that this is not a metric, as it is neither necessarily symmetric not satisify the triangle inequality.) When $$y$$ and $$x$$ are close to each other, this is approximately equal to the Hessian metric

$$ \frac{1}{2} \langle y - x, \nabla^2 h(x) (y - x) \rangle.$$

The authors then introduce (albeit without much intution) the _Bregman Lagrangian_

$$ \mathcal{L}(X, V, t) = e^{\alpha_t + \gamma_t} \left( D_h(X_t + e^{-\alpha_t}V_t, X_t) - e^{\beta_t} f(X_t) \right) $$

where $$X_t \in \mathcal{X}$$ denotes position at time $$t$$, $$V_t \in \mathbb{R}^d$$ the velocity at time $$t$$, and times belong to an interval $$\mathbb{T}$$ of time. Here, the functions $$\alpha, \beta, \gamma : \mathbb{T} \to \mathbb{R}$$ are all continuously differentiable functions of time. From a physical perspective, 

* $$f$$ plays the role of a potential function, whose damping is controlled by $$\beta$$,
* $$D_h\left( \cdot, \cdot \right)$$ plays the role of the kinetic energy (which can be motivated by the approximation to the Hessian metric)
* $$\alpha$$ controls the damping of the velocity term, and $$\gamma$$ that of the overall Lagrangian.

In such a scenario, if we have kinetic energy $$T$$ and potential energy $$V$$, we would set the Lagrangian to be $$\mathcal{L} =  T - V$$; it is clear to see how the Bregman Langrangian is similar in this respect. We would then like to find a path $$\{ X_t : t \in \mathbb{T}\}$$ which minimizes the _action_

$$ \mathcal{J}[X] = \int_{\mathbb{T}} \mathcal{L}(X_t, \dot{X}_t, t ) \, dt $$

(where over-dot's denote differentiation with respect to time) which is a functional on paths. The _principle of least action_ from physics states that the true observed motion of a particle with Langrangian $$\mathcal{L}$$ corresponds to that which minimizes the action; this is the reason why we are interested in such quantities.

## The Euler-Lagrange equation

We can then use the _calculus of variations_ in order to find a curve which minimizes this functional. In order to explain how we can try and do this, we can use the following intutition for when considering the simpler problem of finding the minimizing point of a curve $$f(x)$$ for $$x \in \mathbb{R}$$, for example. Generally, the idea of a stationary point in ordinary calculus is that a function $$f$$ is stationary at a point $$x^*$$ when, after perturbing the function slightly, it _does not change too much_ in the sense that

$$ f(x^* + \epsilon) = f(x^*) + O(\epsilon^2).$$

If $$f$$ is sufficiently differentiable so that for any point $$x$$ we know that (say via Taylor's theorem)

$$ f(x + \epsilon) = f(x) + \epsilon f'(x) + O(\epsilon^2),$$

then we know that points for which $$f'(x) = 0$$ are stationary points. From this, we can then build up critera for when stationary points are local/global minima/maxima and so on.

The same idea is used in the calculus of variations; we aim to find paths $$X$$ for when we perturb them slightly by a new path, the corresponding action does not change too much. However, there is a lot more freedom in what it means to perturb away from a path than for a simple point; although this seems like it may be a problem, provided we formulate our pertubations correctly, it is actually quite advantageous. Namely, we consider perturbing the path by another $$\eta$$ so that the end-points of the new path are unchanged, and examine the behaviour as the scale of $$\eta$$ changes, which we can do simply by perturbing by $$\epsilon \eta$$ for a scalar $$\epsilon$$, and examine what happens as $$\epsilon \to 0$$. We now express this idea mathematically. 

In the simplest case, we impose boundary conditions on $$X$$ at the end points of $$\mathbb{T}$$, so if $$\mathbb{T} = [t_1, t_2]$$, we enforce that $$X(t_1) = a$$ and $$X(t_2) = b$$ (say). Given this, we then seek to find paths $$X$$ for which 

$$ \mathcal{J}[X + \epsilon \eta] = \mathcal{J}[X] + O_{\eta}(\epsilon^2) $$

whenever $$\eta$$ is a (sufficently smooth) path with $$\eta(t_1) = \eta(t_2) = 0$$, and $$\epsilon$$ here acts as a scaling of the pertubation. (The subscript $$\eta$$ on the big-Oh term denotes that the exact scaling depends on $$\eta$$.) As $$\mathcal{J}[X + \epsilon \eta]$$ is a function of $$\epsilon$$ (keeping $$\eta$$ for now fixed), by using Taylor's theorem, integration by parts and the boundary conditions $$\eta(t_1) = \eta(t_2) = 0$$, it is a straightforward exercise to show that 

$$ \mathcal{J}[X + \epsilon \eta] = \mathcal{J}[X] + \epsilon \left( \int_{\mathbb{T}} \left[ \frac{ \partial \mathcal{L}}{\partial X}(X_t, \dot(X)_t, t) - \frac{d}{dt} \left\{ \frac{\partial \mathcal{L}}{\partial V}(X_t, \dot{X}_t, t) \right\}  \right] \eta(t) \, dt \right) + O_{\eta}(\epsilon^2). $$

As we want the $$\epsilon$$ term to be equal to $$0$$ for all "pertubed paths" $$\eta$$, it follows that the $$[ \cdots ]$$ term must be equal to zero, and so stationary paths of the action correspond to solutions of the _Euler-Lagrange equation_

$$ \frac{d}{dt} \left\{ \frac{\partial \mathcal{L}}{\partial V}(X_t, \dot{X}_t, t) \right\} = \frac{ \partial \mathcal{L}}{\partial X}(X_t, \dot(X)_t, t).$$

As expected from ordinary calculus, a path being stationary is a necessary criterion for it to be a local/global minima/maxima of the action; sufficient conditions can be motivated along a similar line as to how we do so in ordinary calculus. 

## Back to the Bregman Lagrangian

The Euler-Lagrange equation for the Bregman Lagrangian gives rise to a second order differential equation of the form (under the assumption that the Hessian matrix $$\nabla^2 h$$ is invertible)

$$ \ddot{X}_t + \left( e^{\alpha_t} - \alpha_t \right) \dot{X}_t + e^{2\alpha_t + \beta_t} \left[ \nabla^2 h(X_t + e^{-\alpha_t} \dot{X}_t \right]^{-1} \nabla f(X_t) $$
$$ + e^{\alpha_t}\left( \dot{\gamma}_t - e^{\alpha}_t \right) \left[ \nabla^2 h(X_t + e^{-\alpha_t} \dot{X}_t \right]^{-1} \left( \nabla h(X_t + e^{-\alpha_t} \dot{X}_t) - \nabla h(X_t) \right) = 0. $$

In order to simplify it slightly, the authors impose the _ideal scaling_ conditions

$$ \dot{\beta}_t \leq e^{\alpha_t} \qquad \text{ and } \qquad \dot{\gamma}_t = e^{\alpha_t} $$

so that the Euler-Lagrange equation simplifies to (after using the second scaling condition)

$$ \ddot{X}_t + \left( e^{\alpha_t} - \alpha_t \right) \dot{X}_t + e^{2\alpha_t + \beta_t} \left[ \nabla^2 h(X_t + e^{-\alpha_t} \dot{X}_t \right]^{-1} \nabla f(X_t) = 0 $$

where the only change is that the last term has been removed. 

As the overall plan is to find discretized solutions for this class of ODE's and analyse their convergence properties, we first want to obtain a convergence rate for exact solutions to the Euler-Lagrange equation. A frequent tool in the analysis of ODE's and PDE's are that of energy methods - from a physical perspective, we are interested in when quantities such as energy are conserved - which allow us to analyse the behaviour of the system. The authors then define an energy functional of the form

$$ \mathcal{E}_t := D_h\left( x^*, X_t + e^{-\alpha_t}\dot{X}_t \right) + e^{\beta_t} \left( f(X_t) - f(x^*) \right) $$.

Again a physical perspective can be used to motivate this. As mentioned before, if a system has kinetic energy $$T$$ and potential energy $$V$$, we let the Lagrangian be of the form $$\mathcal{L} = T - V$$. The corresponding Hamiltonian, corresponding to the total energy of the system, would be of the form $$\mathcal{H} = T + V$$; the above energy functional therefore can be thought of corresponding to the system without the extra damping $$e^{\alpha_t + \gamma_t}$$ in the original Langrangian. However, it is worth noting that here $$\mathcal{E}_t$$ does not correspond to the true Hamiltonian, which is given by  

$$ \mathcal{H}(X, P, t) = e^{\alpha_t + \gamma_t} \left( D_{h^*}( \nabla h(X) + e^{-\gamma_t}P, \nabla h(X) ) + e^{\beta_t} f(X) \right) $$

where $$h^*$$ is the convex dual of $$h$$ and $$P$$ now corresponds to the momentum. Anyways, under the ideal scaling conditions, it is then straightforward to show that if $$X_t$$ is a solution to the Euler-Lagrange equation, $$\mathcal{E}_t$$ is non-increasing in time (this is where the first scaling condition is used), and so it follows that

$$ f(X_t) - f(x^*) \leq C e^{-\beta}_t} $$

for some constant $$C$$. The authors then show that the family of Lagrangians is closed under time dilations (that is, upon time changes $$t \mapsto \tau(t)$$) after suitable transformation of $$(\alpha, \beta, \gamma)$$.

## Discretization schemes

Letting $$p > 0$$ be a parameter, if we choose the choice of parameters

$$ \alpha_t = \log p - \log t $$
$$ \beta_t = p \log t + \log C$$
$$ \gamma_t = p \log t $$

where $$C > 0$$ is a constant, then the ideal scaling conditions are satisfied, and the corresponding Euler-Lagrange equation

$$ \ddot{X}_t + \frac{p +1}{t} \dot{X}_t + C p^2 t^{p-2} \left[ \nabla^2 h\left( X_t + \frac{t}{p} \dot{X}_t \right) \right]^{-1} \nabla f(X_t) = 0 $$

corresponds to the continuous-time limit of Nesterov's accelerated mirror descent (when $$p = 2$$) and that of Nesterov's accelerated cubic-regularized Newton's method (when $$p = 3$$). 

The idea is to now discretize the above ODE in a way so that the discrete-time algorithm attains the same convergence rate as that in the continuous time case. The authors note that a naive discretization appears to be unstable (via empirical observation), and ultimately show that, provided $$f \in \mathcal{C}^p$$ and some other smoothness constraints on $$f$$ and $$h$$ hold, and provided $$C$$ is not sufficiently large, the following discretization sceheme has an $$O(1/(\epsilon k^p))$$ convergence rate:

$$ x_{k+1} = \frac{p}{k+p} z_k + \frac{k}{k+p} y_k, $$
$$ y_k = \mathrm{argmin}_y \left\{ f_{p-1}(y; x_k) + \frac{N}{\epsilon p} \| y - x_k \|^p \right\}, $$
$$ z_k = \mathrm{argmin}_z \left\{ C p k^{(p-1)} \langle \nabla f(y_k), z \rangle + \frac{1}{\epsilon} D_h(z, z_{k-1}) \right\},$$

where $$k^{(p-1)} = k(k+1)\cdots(k+p-2)$$ is the rising factorial, and $$f_{p-1}(y;x)$$ is the $$(p-1)$$-st order Taylor approximation of $$f$$ centered at $$x$$. Although this then gives an algorithm which works for all $$p \geq 2$$, from a practical perspective it is unclear on whether it is worthwhile considering considering higher orders of $$p$$ than 2 (due to the need to calculate $$f_{p-1}(y;x_k)$$ at each iteration).

## Conclusion

By considering discretization schemes of the Euler-Lagrange equations corresponding to a family of Lagrangians, the authors are able to recover acceleration phenomenen for convergence using techniques motivated by Nesterov's original arguments. 


### References

[1] Learning/GAN's paper [link](http://arxiv.org/pdf/1503.01916)

[2] Bregman divergence paper [link](http://arxiv.org/pdf/1503.01916)

[3] Original GAN paper

[4] Classifier ABC paper

[5] f-GANs paper


...

### Footnotes
link[<sup>1</sup>](#footnotes)
<div id="footnotes"></div>
1. Strictly, only the total variation distance is actually a metric; infact, one can show that it is the only $$f$$-divergence (up to scaling) which gives rise to a proper metric.
2. Having had a quick look, I'm unsure on whether this is something which would be practically useful; it could be interesting to give this a further look for whether it is the case.
{'fraction_non_alphanumeric': 0.12851008252033325, 'fraction_numerical': 0.0060752379633111035, 'mean_word_length': 4.341860465116279, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 35, 'https://': 8, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '209505', 'n_tokens_mistral': 15203, 'n_tokens_neox': 14336, 'n_words': 7112}