Derivatives of Stochastic Gradient Descent in parametric optimization

Summary

The paper studies stochastic optimization problems where the objective depends on a parameter, and more specifically the derivatives w.r.t. that parameter of the SGD iterates. The paper makes various quite strong albeit common assumptions, and for various more specific settings concrete convergence rates are established. The proof relies on analysis via an inexact SGD sequence. Finally, the results are illustrated by some experiments.

Strengths

The paper is well-written and the technical flow of ideas is convincing. Especially the connection to inexact SGD seems quite novel.

Weaknesses

My main concern is of a motivational nature: why is the question set out inn ll. 35-36 interesting? I do not find ll. 37 sufficiently convincing. (I may not have understood that paragraph fully.)

Questions

1. Can you elaborate on the motivation? 2. Why do you need that the gradient for the first iterates vanish (l. 194)? That appears to be an odd and strong assumption. 3. How restrictive are the assumptions? (I understand that they are mostly common in the literature.)

Rating

6

Confidence

1

Soundness

3

Presentation

3

Contribution

2

Limitations

Assumptions are discussed.

Summary

The authors consider parametric stochastic optimization problems of the form $\min_x F(\theta,x)$ where $F(\theta,x)= \mathbb E_\xi [ f(x, \theta, \xi)]$ under the condition that $f$ is strongly convex in $x$ for any fixed $\theta, \xi$. This ensures that for fixed $\theta$, there exists a unique minimizer $x^*(\theta)$. The authors construct a sequence $x_k$ by gradient descent for $F(\theta, \cdot)$ and demonstrate that an associated sequence, denoted by $\partial_\theta x_k$, converges to the parameter derivative $\partial_\theta x^*(\theta)$ of the solution map $x^*(\theta)$. They explore various regimes of stochasticity and various learning rate schedules, obtaining rates in different settings. Strong continuity assumptions are placed on $f, \nabla f, D^2f$.

Strengths

The article is generally well-written and explains its results intuitively. The statements of results are precise, yet clear.

Weaknesses

* I find the title almost misleading. The authors do not consider derivatives (modifications) of the algorithm, but they consider the derivatives of iterates with respect to an additional parameter. I would propose something along the lines of "Derivatives in parametric optimization and their behavior along SGD iteration". * I do not follow the numerical illustration in Section 4 at all. The independent parameter $\theta$ becomes a random quantity in this section, and it is unclear what stochastic gradient estimates the authors use: Only the deterministic objective function $F$ is specified (line 291), and $\xi$ is never mentioned in this section. I am not sure why the authors draw $\theta$ from a random distribution. I believe that the experiments either do not match the setting considered above or the presentation needs to be clarified considerably.

Questions

* Is there a conflict between the statement in line 131 that "[...] the initialization of the algorithm $x_0(\theta)$ depend[s] on some parameter $\theta$" and the assumption that $\partial_\theta x_0(\theta) =0$ in Theorem 2.2? * In Lemma 2.1, the restriction that $\eta_k \leq \mu/L^2$ is generally much more severe than the usual bound $\eta_k \leq 1/L$. Perhaps by considering the quadratic case, could the authors speculate whether it is necessary to ensure the convergence of derivatives or whether it could be relaxed? * In Remark 2.3, if we use a lower estimate for $\mu$, this also changes the estimate for $\kappa$: The constants $c, u$ are not independent. In fact, $\eta_0 = 1/(4\mu \kappa^2) = \mu/(4L^2)$ satisfies the necessary condition above. If we increased $c$ without adjusting $u$, we may easily enter a regime where $\eta_0> \mu/L^2$. A more careful consideration appears to be needed.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

The paper considers stochastic optimizations where the objective depends on some parameter. Instead of the SGD, the paper considers the derivatives of the iterates of the SGD with respect to that parameter in the context where the objective is strongly convex. Convergence analysis is obtained for the derivatives of the iterates of SGD, which can be viewed as an inexact SGD on a different objective, perturbed by the convergence of the original SGD.

Strengths

(1) Convergence guarantees are obtained for derivatives of SGD under certain assumptions. (2) Analysis seems to be rigorous and solid.

Weaknesses

(1) Derivatives of SGD are much less studied than SGD. As a result, it would be helpful to add more discussions about Assumption 1, Assumption 2, what kind of examples of interest satisfy these two assumptions (especially the part that is unique to the setting that involves the parameter). (2) Numerical experiments are only synthetic. It would be nice if the paper can add an experiment on real data. (3) I do not see adequate discussions whether the assumptions for the theoretical part can be satisfied for the examples considered in the numerical section. (4) Inexact SGD has been well studied in the literature. Since the paper views derivatives of SGD as an inexact SGD, it is not clear what technical novelty and contributions arise from this context.

Questions

(1) In Theorem 2.2, I understand that constant step-size is a popular choice in the SGD literature. But can you comment on the choice $\eta_{k}=\frac{1}{\mu}\frac{2}{k+8\kappa^{2}}$ for the sublinear rate regime, and moreover the interpolation regime, in which the assumption $\sigma=0$ seems to be super strong to me, and can you provide some examples of interest that satisfy this particular assumption? (2) In the paragraph after equation (1), you wrote that the error term is of order... Please specify which term is the error term. (3) To improve the readability of the paper, I suggest you state somewhere in the main paper how you view the derivatives of SGD as an inexact SGD. For example, in the proof of Theorem 2.2., you defined $e_{k+1}$, and I think you can define $e_{k+1}$, as well as $\nabla_{x}g(x_{k};\xi_{k+1})$ when you explain how you view the derivatives of SGD as an inexact SGD before you state the main results to help the readers understand better. (4) Some of the journal names in the references should be capitalized. For example, for Robbins and Monro, it should be The Annals of Mathematical Statistics.

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

More discussions on limitations should be added.

Summary

This is a theoretical paper on iterative process differentiation. The paper analyzes the behavior of the derivatives of the iterates of SGD (Stochastic Gradient Descent). Based on a set of assumptions, the paper establishes the convergence of the derivatives of SGD and conducts numerical experiments to validate its findings.

Strengths

The highlights of the paper are: (1) revealing that the behavior of the derivatives of the iterates is driven by an inexact/perturbed SGD recursion; (2) illustrating their theory with numerical experiments on synthetic tasks.

Weaknesses

I believe the main weaknesses of the paper are that the assumptions used to establish the theory are too strong; moreover, the practical significance of the theory is not clearly articulated, especially in relation to stochastic hyperparameter optimization.

Questions

The smoothness assumption in Assumption 1(b) requires that the gradient are jointly L-Lipschitz continuous in $x$ and $\theta$ . Can this assumption be relaxed?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Not applicable.