> Hi, thank you for your detailed responses.
Could you please comment on the convergence of the Newton’s method? Generally speaking, it is a local method. It would be helpful to discuss its convergence leveraging the special structure of the problem. Under what assumptions does it converge? What tricks (e.g., initialization) are needed to make it converge in practice? I can imagine that if we have a sequence of L hash functions, the method will not work. So some smoothness would be necessary.
We thank the AC for their question. Indeed, the performance of our method heavily depends on the behaviour of the Newton solver, and investigating its convergence property in this setting is paramount: this is the reason behind our experiments in Sec4.4 and SecE.
In general, providing theoretical global convergence guarantees for Newton is not practical (if at all feasible!). Our target system (3) does present a very specific structure, though, which guarantees some useful properties, namely
- The Jacobian is always invertible: notice it will always have identities on the main diagonal, hence all its eigenvalues are 1. This implies that the Newton sequence is well-defined
- The root is unique and hence has multiplicity one. This stems from the uniqueness of the solution of the forward substitution (sequential) procedure
Still, convergence will depend also on the (higher-order derivatives of the) step functions $f_l(z)$ which is ultimately heavily problem- and architecture-dependent. For this reason, we focused more on performing an experimental analysis rather than a theoretical one.
In general, for the problems considered we didn’t encounter issues in terms of convergence: this can be seen in Fig7, where Newton iterations remain reasonably bounded even though a non-differentiable function (ReLU) was employed. This extends to the more complex case of diffusion, too (see SecD.3). However, the AC is absolutely correct in that, if we consider extreme cases of non-differentiability (such as argmax or hash functions), the Newton procedure is likely to fail (see also reply to W2 of reviewer 7Bpu). We will make sure to further highlight this in the limitations section.
Regarding the role of initialisation, as the AC rightly assumes, we did observe that properly choosing an initial guess for the Newton solver plays a relevant role in reducing the number of iterations to convergence. Nonetheless, for the experiments considered, even employing relatively simple heuristics resulted in reasonably fast convergence: this is investigated in detail in SecE.2. For example, as an initial guess for Newton applied to the training procedure in ResNets we resorted to using the batch-average of the activations at the previous optimisation step, but already with an all-zero initialisation we can observe convergence, albeit slower (see in particular Fig18 for the effect of varying this).
> It would be nice if the algorithm reduced to the sequential complexity O(L) (and still produced correct results) in these cases instead of not converging / producing wrong results.
Best, AC
We thoroughly agree: this would make for an ideal property (and indeed the Jacobi solver in [36] does satisfy this), but it is just not feasible for our choice of solver. This is an expected trade-off for a (generally) faster solver (Jacobi is linear, Newton is quadratic). The classical workaround consists in switching solving strategy depending on the behaviour of the first (few) iterations: if Newton diverges, one can always revert to the sequential solution (although the cost of the first few iterations is indeed wasted in this case). We will explicitly point this out, too, in the paper.
We thank again the AC for their questions, and remain at their disposal for any additional clarification.