Greedy Learning to Optimize with Convergence Guarantees

We greatly appreciate the reviewer's detailed suggestions for improvement and positive feedback, thank you.

“The theory seems to require the knowledge of the maximum Lipschitz constant over all training examples in its regularization”:

We agree that the theory requiring knowledge of the maximum Lipschitz constant could be a challenge in practical applications where this constant is unknown. The method currently hasn’t been tested on problems with unknown Lipschitz smoothness.

However, convergence on training data can be extended to Lipschitz smooth functions with an unknown constant (if the regularization function $\lambda_t R(\tilde{\theta})$ is removed), by instead proving convergence using a comparison to backtracking line search $F(x_t) - F(x_{t+1}) \geq \alpha h_t \|\nabla F(x_t) \|^2$ for some $\alpha \in (0,1)$ and a “small enough” step size $h_t$.

Similarly, exact knowledge of the Lipschitz constant is not needed as the regularizer can be chosen to bias towards any parameters such that Gradient Descent is convergent.

“finding the regularization parameter $\lambda_T$ seems arduous”:

We agree that finding the regularization parameter $\lambda_T$ can indeed be arduous if done so as described on page 18. In our experiments, either $\lambda_t$ is constant over time (In the case of the regularized full operator in Figure 6), or $\lambda_t = 0$ for all $t<T$, then we calculate $\lambda_T$ as in page 18. We have updated lines 929-934 to replace $\lambda_t$ with $\lambda_T$ to make this more explicit.

“ It seems also that the condition for choosing \lambda_t gives that $G_{\phi}$ is positive definite, which is confusing with the initial claim that the method converges for non p.d. conditioners.”

To clarify, on the training dataset, we achieve convergence for $t \to \infty$ even when $\lambda_t = 0$ for all $t$. This means that the preconditioners need not be SPD. But it is true that when training is terminated at some iteration $T$ we need this final preconditioner to be positive definite (we have $G_{\theta_T} = \tau I + M$ with $\|M\| \leq \nu < \tau$, meaning that $x^TG_{\theta_T}x = \tau \|x\|^2 + x^TMx \geq \tau \|x\|^2 - \|M\|\|x\|^2 > 0$).

“How are the ground truths x^* computed?”

The problems we solve are toy problems, and we have access to ground-truth images (e.g. clean images, denoted by $x_{\text{true}}$ in the paper), then generate observations y by applying the forward operator A and Gaussian noise. From then we only use information of the function $f(x) = \frac12 \|Ax-y\|^2 + \alpha H_{\epsilon}(x)$ and the initialisation $x_0$. In our paper, $F(x^*)$ is used to denote the minimum value of the function $F$ defined in line 330, which is approximated as we do not have access to the exact minimiser of F. This approximation is used as $F(x^*)$ in Figures 2, 4 and 6.

We would like to thank the reviewer for noticing many other improvements to the submission.

We would first like to thank the reviewer for their constructive feedback. Specific comments are addressed below.

“an unrealistic assumption named BGD”:

The BGD assumption is saying that $g_{t, \lambda_t} (\theta_t) \leq g_{t, \lambda_t} (\tilde{\theta})$ where $\tilde{\theta}$ are the parameters that correspond to Gradient Descent.

We learn $\theta_t = \arg\min_{\theta} g_{t, \lambda_t} (\theta)$, then this value would automatically satisfy the BGD property if our parametrizations generalise Gradient Descent. It is easy to check that this is satisfied for all considered examples.

Note also that this is not very restrictive and it is simple to modify any other given parametrization to have this property.

In practice, of course, the minimization over the parameters is not solved exactly but just an approximation. However, the BGD property is verified in training by calculating and comparing $g_{t, \lambda_t} (\theta_t)$ and $g_{t, \lambda_t} (\tilde{\theta})$, and is always found to hold in our numerical experiments.

“Corollary 1 seems to give a very strong claim but no explicit proof is given”:

Theorem 2 requires

1. $G_{\theta}$ is continuous with respect to $\theta$.
2. $\theta_t$ is BGD
3. $\lim \inf \lambda_t$ > 0.

In the statement of corollary 1, we assume points 2 and 3 so all that is left to prove is point 1, which is proved in Lemma 2. The proof of corollary 1 has been extended to what is contained in this explanation.

Similar to other proofs in optimization, we also require $(x_t)_{t=1}^\infty$ to be bounded for Theorem 3 to hold. This explanation has been added to the paper.

"a limitation of the proposed scheme is inability to learn those iterative schemes which utilize memory of past iterates"

We agree with the reviewer that this is a limitation. However, our approach is able to learn over hundreds or thousands of iterations due to this and still one obtains excellent empirical performance, so it can be seen as a tradeoff.

We thank the reviewer for their detailed feedback.

“Would it be possible to guarantee that the algorithm would work on all $1/\tau$- smooth problems?”:

We thank the reviewer for this comment and acknowledge that the current form of Theorem 2 may seem weak as we provide only the existence of some $\tilde{L}$, and do not explicitly show what this constant is.

When checking the proof in detail, one observes that \tilde{L} is greater than the maximum Lipschitz constant in the training set. So the algorithm is in fact convergent on all $L_{\text{train}} = \max \{ L_1, \cdots L_N \} = 1/\tau$ - smooth functions given the theorem assumptions.

We updated the statement of the theorem to “then, there exists a final training iteration $T$ such that for all $f \in \mathcal{F}_{L train}$ and any starting point $x_0$, using Algorithm 2, we have $\nabla f(x_t) \to 0$ as $t \to \infty$”.

“The proposed algorithm still relies on hand-crafted a-priori knowledge … it does not significantly differ from alternative approaches that require safeguarding or search within a predefined set that guarantees convergence.”:

We agree that our approach utilizes a-priori knowledge to ensure convergence for generalization, but in contrast to safe-guarding it does so with soft constraints, rather than hard constraints.

Moreover, exact knowledge of Lipschitz constants is not required. Any parameter that would make gradient descent convergent on training data is sufficient for our framework.

Moreover, we believe that a key innovation of our method lies in the ability to learn parameters over hundreds or thousands of iterations, which is not seen in other L2O approaches.

“both problems are of the form $\| Ax - b \|^2$… the linear operator $A$ is fixed. This seems like an ``easy'' problem”:

You are correct that in the current experiments, the operator $A$ is fixed across training and test problems, and the variation in the function f only comes from the observation $b$. However, this is exactly the problem a practical translation would face: e.g. an imaging system (which defines a fixed A and data fit) scans dozens of patients every day ($b$ changes). The same setting is also considered in Banert et al 2024 https://epubs.siam.org/doi/epdf/10.1137/22M1532548.

Note that the objective functions used in our numerical experiments aren’t just of the form $\|Ax-b\|^2$ but $f(x) = \|Ax-b\|^2 + \alpha H{\epsilon}(x)$, with $H{\epsilon}(x)$ a non-quadratic function, adding complexity to the optimization problem.

"Convolutional preconditioners":

We accept that a comparison to non-learned convolutional preconditioners would strengthen our submission. Currently, we are working on this.

"I don't understand Eq. 16":

We apologize for the confusion around Equation 16.

Equation 16 just states that $G_{\theta} \nabla f_k(x_k^t)$ is linear in $\theta$. This means that there exists a linear operator $B_k^t$ such that $G_{\theta} \nabla f_k(x_k^t) = B_k^t \theta$.

"maintaining constant memory usage":

Thank you for raising this point. The limitation with (a standard implementation of) unrolling is that the GPU needs to store all intermediate values to backpropagate, which scales memory with O(T). However, in our case, when the parameters \theta_t are learned and the next values $x_k^{t+1}$ are calculated, $\theta_t$ and $x_k^t$ are no longer required to be stored in the GPU and therefore can just be saved to disk, meaning that the GPU memory requirement scales as O(1) instead of O(T). This explanation will be added in the revised draft.

We thank the reviewer for the other suggestions for clarification.

We thank the reviewer for their detailed constructive feedback.

“No evaluation over the whole dataset is provided.”:

We are sorry that our writing wasn't clear enough. The plots in Figure 2, Figure 4 and Figure 6 (and Tables 3 and 4 in the appendix) use the function F which is the mean function value over the entire data set (training or test, respectively) as defined in the paragraph starting in line 329.

In the revision we will add The maximum and minimum function value vs iteration for each method too to make this more clear.

“memory footprint is unclear to me”:

Thank you for raising this point. The limitation with (a standard implementation of) unrolling is that the GPU needs to store all intermediate values to backpropagate, which scales memory with O(T). However, in our case, when the parameters \theta_t are learned and the next values $x_k^{t+1}$ are calculated, $\theta_t$ and $x_k^t$ are no longer required to be stored in the GPU and therefore can just be saved to disk, meaning that the GPU memory requirement scales as O(1) instead of O(T).

“It would be interesting to see whether same behaviour is observed on more realistic image size.”:

Thank you for the feedback. A numerical experiment will be added to the paper with a 256 x 256 image size for the CT problem. For this problem, we observe very similar results to the two experiments shown in the first submission. In particular, we see that the learned algorithm using a convolutional parametrization outperforms L-BFGS and NAG on test data.

Response to Questions

“Equation 2 seems to only vary the y over the whole space. I believe this should be rewritten to emphasise what kind of functions you expect to be varying over.”:

Thank you for noticing this, you are correct and this has been changed in the revision.

Furthermore, the regularizer and the operator $A$ are fixed across training and test problems, so the variation in the function f only comes from the observation $b$. However, this is exactly the problem a practical translation would face: e.g. an imaging system (which defines a fixed A and data fit) scans dozens of patients every day ($b$ changes). The same setting is also considered in Banert et al 2024 https://epubs.siam.org/doi/epdf/10.1137/22M1532548.

“Proposition 2 - linear independence seems like a rather arbitrary assumption.”:

You are correct that it seems an arbitrary assumption. One can obtain the same result with a more general assumption, which will be included in the revised submission.

“Theorem 3 seems to assume that $x_t$ has to now be a bounded sequence, which seems to be a relatively strange assumption to appear in such a context.”

The assumption of a bounded sequence is used to ensure the convergence of our method in the greedy setting, see line 936-941, it is used to bound f(x_t) - f(x^*) in terms of | \nabla f (x_t) |.

“Section 6 - in this section what is Y?”:

Thank you for this question, $\mathcal{Y}$ is never explicitly detailed in section 6. It is the observation space, e.g. for the deblurring case $\mathcal{Y} = \mathcal{X}$. This will be added in the revised paper.

“Random question to authors: do you believe that L2O can overcome the problems discussed in https://arxiv.org/pdf/2301.06148?”:

Thank you for the question, however we are unable to answer this currently. We will look into this further.

“Line 108, you seem to choose X to be a finite dim Hilbert space - what is the value of this?”

Yes, you are correct that we can consider Euclidean spaces. Often one considers Hilbert spaces in optimization.

Lastly, we thank the reviewer for noticing inconsistencies in Equation 9 and Figure 3a.