Thank you
- To clarify the new scheme, the update is now $\mathbf{x_t}= \mathbf{x_{t-1}} + \alpha_t \mathbf{z_t}$, where $\alpha_t$ is sampled from an exponential distribution (which is a very light-tailed distribution with mean 1 and variance 1). So $\alpha_t$ is still used.
Via an elementary argument involving fundamental theorem of calculus and the pdf $p(\alpha) = \exp(-\alpha)$, we obtain $\mathbb{E}[F(\mathbf{x_t}) - F(\mathbf{x_{t-1}})] = \mathbb{E}[\langle \mathbf{g_t}, \mathbf{x_t} - \mathbf{x_{t-1}}\rangle]$.
This identity says that the function gap is *exactly equal* to the linearization of the function gap. In a sense, the randomization makes the first-order Taylor approximation perfectly correct. In the current submission, we sample $\mathbf{g_t}$ at $\mathbf{w_t}$ to ensure this identity. However, changing $\alpha_t$ to be exponentially distributed and multiplying the update $\mathbf{z_t}$ by $\alpha_t$ means that this is no longer necessary.
In short, although $\mathbf{w_t}$ plays a significant role, the entirety of that role is contained in establishing the identity $\mathbb{E}[F(\mathbf{x_t}) - F(\mathbf{x_{t-1}})] = \mathbb{E}[\langle \mathbf{g_t}, \mathbf{x_t} - \mathbf{x_{t-1}}\rangle]$. This other option keeps the same identity and so works just as well.
That said, if the reviewers prefer to keep the results the same as in the submitted version for which all of the analysis is completely available, we are of course happy to do so.
- Regarding why $\mathbb{E}[ F(\mathbf{w_t}) - \mathbf{g_t}|\mathbf{z_t}]=0$: this is is because $\mathbf{g_t}$ is a standard stochastic gradient oracle evaluated at $\mathbf{w_t}$ and as such $\mathbb{E}[\mathbf{g_t} | \mathbf{w_t}]=F(\mathbf{w_t})$. As a concrete illustration, suppose that $F=\mathbb{E}[f(x,r)]$, where $x$ is the model parameter, $r$ is a randomly sampled data point, and $f$ is the loss of the model on the data point. Then $\mathbf{g_t}$ can be taken to be $\nabla f(\mathbf{w_t}, r_t)$ for some i.i.d. sample $r$. This formalism exactly captures the standard approach used in training. In this case, since $r_t$ is independent of $\mathbf{w_t}$ and $\mathbf{z_t}$, we have $\mathbb{E}[ F(\mathbf{w_t}) - \mathbf{g_t} | \mathbf{z_t}]=0$.
- Regarding the clipping: You're right that this is not too common in current practice. However, we feel this is more an analytical artifact than a real change in the algorithm because the clipping should not be active in most iterations. The reason for this is that intuitively as the algorithm convergence we expect the gradients to be dominated by noise so that they look roughly like mean-zero random variables. In this case, the clipping will not occur. On the other hand, if the clipping *does* occur frequently, then an alternative analysis based upon https://jmlr.org/papers/v18/17-079.html would actually show that we converge incredibly fast. This in turn would put us in the regime in which gradients are dominated by noise, and so clipping would stop occurring.