A Generalization Result for Convergence in Learning-to-Optimize
Authors: Michael Sucker
Peter Ochs
Venue: ICML 2025 oral (2025)
Keywords: learning-to-optimize
non-smooth non-convex optimization
PAC-Bayesian guarantees
convergence
Primary area: theory->optimization
TL;DR: We present a generalization theorem that allows for establishing the convergence of learned optimization algorithms to critical points with high probability.

Abstract: Learning-to-optimize leverages machine learning to accelerate optimization algorithms. While empirical results show tremendous improvements compared to classical optimization algorithms, theoretical guarantees are mostly lacking, such that the outcome cannot be reliably assured. Especially, convergence is hardly studied in learning-to-optimize, because conventional convergence guarantees in optimization are based on geometric arguments, which cannot be applied easily to learned algorithms. Thus, we develop a probabilistic framework that resembles classical optimization and allows for transferring geometric arguments into learning-to-optimize. Based on our new proof-strategy, our main theorem is a generalization result for parametric classes of potentially non-smooth, non-convex loss functions and establishes the convergence of learned optimization algorithms to critical points with high probability. This effectively generalizes the results of a worst-case analysis into a probabilistic framework, and frees the design of the learned algorithm from using safeguards.

A Generalization Result for Convergence in Learning-to-Optinie
Michael Sucker'
Peter Ochs 2
Abstract
however, proving convergence a hard and long-standing problem. This is due to the fact that the problem instances are functions, which cannot be observed globally. Rather, the region explored during training strongly influenced by the chosen initialization and the maximal number of itera- tions. This begs a fundamental problem for the theoretical analysis:
Learning to-optimize leverages machine learning to accelerate optimization algorithms. While em- pirical results show tremendous improvements compared to classical optimization algorithms, theoretical guarantees are mostly lacking, such that the outcome cannot be reliably assured. Espe- cially, convergence is hardly studied in learning- to-optimize, because conventional convergence guarantees in optimization are based on geomet- ric arguments, which cannot be applied easily learned algorithms. Thus, develop proba- bilistic framework that resembles classical opti- mization and allows for transferring geometric arguments into toriiinggtt-oimmiiee.. Based on our new proof-strategy, our main theorem is a generalization result for parametric classes of po- tentially non-smooth, non-convex loss functions and establishes the convergence of learned opti- mization algorithms to critical points with high probability. This effectively generalizes the re- sults of a worst-case analysis into a probabilistic framework, and frees the design the learned algorithm from using safeguards.
It typically prevents the usage of both limits and the mathematical argument of induction.
As convergence is, by definition, tied to the notion of limits, this subtlety prevents proving that the learned algorithm converges. A way mitigate this problem rather easily is the usage of safeguards: The update step of the algorithm is restricted to such an extent that it can be analyzed similar to hand-crafted algorithm, independently the training. Yet, this comes at a price:
Not only the analysis of the learned algorithm, also its performance is restricted and eventually similar to hand-crafted algorithms.
Intuitively, the degradation in performance be explained by the fact that this approach attempts to directly apply traditional convergence results, which are not well-suited for saarning-to-optmiin Instead, we advocate for taking a new perspective, in which we make more use of our greatest advantage compared traditional optimization:
1. Introduction
Learning-to-one to-optimize utilizes machine learning techniques tailor an optimization algorithm to concrete family op- timization problems with similar structure. While this often leads to enormous gains performance for problems simi- lar to the ones during training, the learned algorithm might completely fail for others. Thus, to have frustworthy algo- rithms, guarantees are needed. In optimization, the best way to show that the algorithm behaves correctly is by proving its convergence to critical point. In
We can actually observe the algorithm during training.
Thus, present proof-strategy that allows derive convergence in learning-to-optimn generalization. The core idea is to show that the properties of the trajectory, which are needed to deduce convergence of the algorithm, actually generalize to unseen problems (test cases). To demonstrate this, we combine general conver- gence result from variational analysis with PAC-Bayesian generalization theorem. This results in our main theorem, which is applicable in (possibly) non-smooth non-convex optimization setup, and lower bounds the probability to ob- serve a trajectory. generated by the learned algorithm, that converges to a critical point of the loss function. Here, we want to emphasize that, while we derive a convergence re- sult for Marning-to-opting the idea is not restricted to
by means of
toptimiiie,,
Depparment of Mathematics, University of Tübingen, Tübingen, Germany *Department of Mathematics and Com- puter Science, Saarland University, Saarbrücken, Germany. Cor- respondence to: Michael Sucker emichael.suckee sucker math.uni- tucbingen.d>>, Peter Ochs < math. maath.uni-san sarr-aaaadddd....
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Generalization Result for Convergence in Learning-t--Optimize
optimization. Rather, it applies more generally to sequential prediction models that exhibit Markovian structure.
guarantees is their reliance on specific distribution. To solve this, another line of work studies the design of learned optimization algorithms and their training, and how it affects the possible guarantees (Wichrowska et al., 2017; Metz et al., 2019; 2022). Here, Liu et al. (2023) identify common properties of basic optimization algorithms and propose a math-inspired architecture. Similarly, Castera Ochs (2024) analyze widely used optimization algorithms, extract common geometric properties from them, and provide design-principles for learning-to-optmmize
2. Related Work
This work draws on the fields of PAC-Bayesian learning approach, and convergence results based on the Eojjasswwe property. For an intro- duction to learning- to-pttmize, Chen et al. (2022) provide good overview about the variety of approaches. Simi- larly, for the PAC-Bayesian approach, good introductory references are given by Guedj (2019), Alquier (2024), and Hellström et al. (2025), and for the usage of the Kurdyka- Eojasiewicz property, we refer to Attouch et al. (2013).
the
PAC-Bayesian Generalization Bounds. The PAC- Bayesian framework allows for giving high probability bounds on the risk. The key ingredient is a change-of- measure inequality, which determines the divergence or distance in the resulting bound. While most bounds involve the Kullback-Leible divergence as measure of proximity (McAllester, 2003a;b; Seeger. 2002: Langford & Shawe- Taylor, 2002: Catoni, 2004; 2007: Germain et al., 2009), more recently other divergences have been used (Honorio Jaakkola, 2014; London, 2017: Bégin et al., 2016; Alquier & Guedj, 2018: Ohnishi & Honorio, 2021; Amit et al., 2022; Haddouche & Guedj, 2023). In doing so, the PAC-bound relates the true risk to other terms such as the empirical risk. Yet, it does not directly say anything about the absolute numbers. Therefore, one typically aims to minimize the pro- vided upper bound (Langford & Caruana, 2001; Dziugaite Roy, 2017: Pérez-Ortiz al., 2021; Thiemann et al., 2017). Nevertheless, known difficulty in PAC-Bayesian learn- ing is the choice of the prior distribution, which strongly influences the performance of the learned models and the theoretical guarantees (Catoni, 2004; Dziugaite et al., 2021; Pérez-Ortiz et al., 2021). In part, this is due to the fact that the divergence term can dominate the bound, such that the posterior is close to the prior. Especially, this applies to the Kullback-Leibler divergence, and lead the idea of choosing data- distributionn-deeedden prior (Seeger, 2002; Parrado- Hernández et al., 2012; Lever et al., 2013; Dziugaite& & Roy, 2018; Pérez-Ortiz et al., 2021).
Learning-to-Optinie with Guarantees. To date, learned optimization methods show impressive perfor- mance, yet lack theoretical guarantees (Chen et al., 2022). However, in some applications convergence guarantees are indispensable: It was shown that learning- baased methods might fail to reconstruct the crucial details in a medical image (Möller et al., 2019). In the same work, the authors prove convergence of their learned method by restricting the update to descent directions. Similar safeguarding tech- niques were employed by Prémont-Schwar et al. (2022) and Heaton et al. (2023). The basic idea is constrain the learned object in such way that known convergence results are applicable, and it has been applied successfully for different schemes and under different assumptions (Sreehari et al., 2016; Chan et al.. 2017; Teodoro et al., 2017; Tirer& & Giryes, 2019; Buzzard et al., 2018; Ryu et al., 2019; Sun et al., 2019; Terris et al., 2021; Cohen et al., 2021). A major advantage of these "constrained" methods is the fact that the number of iterations is not restricted priori and that, often, some convergence guarantees can be provided. A major drawback, however, is their severe restriction: Typically, the update-step has to satisfy certain geometric properties, and the results only apply to specific algorithms and/or problems. Another approach, pioneered by Gregor& & LeCun (2010), is unrolling, which limits the number of iterations, yet can be applied to any iterative algorithm. Here, the IHT algorithm is studied by Xin et al. (2016) while Chen et al. (2018) consider the unrolled ISTA. However, in the theoretical analysis of unrolled algorithms, the notion of convergence itself is difficult, and one rather has to consider the generalization performance: This has been done by means of Rademacher complexity (Chen et al., 2020), by using a stability analysis (Kobler et al., 2022), or in terms of PAC- MAC-Bayesian generalization guarantees (Sucker & Ochs, 2023; Sucker et al., 2024). Recently, generalization guarantees based on the whole trajectory of the algorithm, for example, the expected time to reach the stopping criterion, have been proposed (Sucker & Ochs, 2024). The main drawback of generalization
The Hurdyya--Eojasieviis inequality. Single-point con- vergence of the trajectory of an algorithm is challenging problem, especially in non-smooth non-convex optimization. For example, Absil et al. (2005) show that this might fail even for simple algorithms like gradient descent on highly smooth functions. Further, they show that a remedy is pro- vided by the Lojasiewicz inequality, which holds for real analytic functions (Bierstone & Milman, 1988). The large class of tame functions definable functions excludes many pathological failure cases, and extensions of the E tojasiewicz incquality to smooth definable functions are provided by Kurdyka (1998). Similarly, extensions to the nonsmooth subanalytic or definable setting are shown by Bolte et al. (2007b), Bolte et al. (2007a), and Attouch Bolte (2009),
2

---

A Generalization Result for Convergence in Learning-to-Optimize
which yields the Kursssaa-ajassieiiiz inequality. is im- portant note that most functions in practice are definable and thus satisfy the Kurdyka-Lojasiewiicz inequality auto- matically. Using this, several algorithms have been shown to converge even for nonconvex functions (Attouch & Bolte, 2009; Attouch et al., 2010; 2013; Bolte et al., 2014; Ochs et al., 2014; Ochs, 2019).
ær has property b). and C == {a æ has property c). such that the implication translates into an inclusion:
A ABB = {a: : x satisfies a A b} C {x x satisfies c} = C.
This enables more fine-grained result: If we are given probability measure over objects 2, we can always conclude that μ{A B] S [{C), that is, is more likely to observe an object z with property e than to observe an object with properties a and b. Furthermore, if [[AnB) = 1, we deduce that e holds almost surely.
3. Contributions
We present a novel approach for deducing the conver- gence of generic learned algorithm with high proba- bility. In doing so, we effectively generalize the results of a worst-case convergence analysis into probabilis- tic setting. Furthermore, the methodology does not restrict the design of the algorithm and is widely appli- cable, that is, it can also be used for other sequential prediction models that exhibit a Markovian structure.
Most of the time, however, calculating p n B} is infea- sible, so that it needs to be estimated data set. In this case, two questions arise:
(i) Is the estimate representative for unseen data?
(ii) Why do we not
not simply estimate μu directly?
To showcase the idea, we combine the PAC-Bayesian generalization theorem provided by Sucker & Ochs (2024) with the abstract convergence theorem provided by Attouch al. (2013) to derive a new convergence result for our learned optimization algorithm on (pos- sibly) non-smooth non-convex loss- functinnt.ons. In do- ing so, we bring together highly advanced tools from non-smooth non-convex optimization, stochastic pro- cess theory, and PAC-Bayesian learning theory, and effectively solve a long-standing problem of learning- to-optimize, namely how to obtain convergence guar- antees without limiting the design of the algorithm.
The first question can be answered in terms of generaliza- tion result. By contrast, the second question can be more subtle: If the property e is observable, estimating [C(} should be preferred. However, this is not always possi- ble. In our case, for example, the objects x will be whole sequences, the property will be convergence to a critical point, and μu will be the distribution of Markov process gen- erated by the algorithm. Thus, without further assumptions it is practically impossible to observe property directly, because convergence of a sequence is a so-called asymptotic event, which belongs to the -allebr,, that is, it does not depend on any finite number of iterates and therefore cannot be observed.
We conduct two experiments show the validity of our claims: We use a neural-network based iterative optimization algorithm a) solve quadratic problems and b) to train another neural network. In both cases, the learned algorithm outperforms the baseline and converges to a critical point with high probability.
To summarize: Ultimately, are interested in how likely it is to observe an object that possesses property e (here: sequence generated by the learned algorithm that con- verges to a stationary point). For this, we need at least the distribution f of the objects x under consideration (see The- orem 6.3). Additionally, since property e is unobservable, we resort to properties and b, which imply c (see Theo- rem 6.5). Then, to be able to assign probabilities these properties, we need to translate them into measurable sets in the appropriate space (see Section 7.1). This allows for estimating the probability to observe objects æ that possess a and b, which in turn is a lower bound on how many ob- jects possess e. Finally, since this estimate depends on the training data, we need make sure that it also generalizes to unseen problems (see Theorem 7.6).
4. Simplified Key Idea
Before detailing the setup for Sarming-to-optimizze we shortly (and informally) present the main underlying idea of our proof-strategy, which otherwise might be obscured by the details: Given an object and properties a, b, and e, we are interested in the implication
x satisfies a A - satisfies c.
Whenever single object æ has properties a and we are suve that x also possesses However, given collection of objects (2.,,,....,, if the properties a and b only hold for some of these objects, the traditional "implication" is
5. Notation
invalid for the collection, and the language of probability theory seems more appropriate: Here, a, b and have to be rephrased as sets A = {x x has property a}. B == {x
We write generic sets in type-writer font, for example, A C Rd, and generic spaces in soript-font, for example,
X. Given metric space I., Bx(x) denotes the open ball
3

---

A Generalization Result for Convergence in Learning-t--Optimzzz
around x I. with radius O, and assume ev- ery metric space be endowed with the metric topology and corresponding Borel o-field 2 (X.). Similarly, given product space I x Y the product o-algebra is denoted by (xx) 69 ( We consider the space Rd with Euclidean norm ||||| and, for notational simplicity, abbreviate I := Rd and 9 : RR. The space of sequences in E is denoted by No, and we endow it with the product o-algebra, which is the smallest olllgerra, such that all canonical projections T, 3% + I, (2(N)) + z(1), are measurable. For notions from non-smooth analysis, we follow Rockafellar & Wets (1998). In short, a function f I + R U { is called proper, if f(z) < +00 for at least one 2 E I,
I iteratively to the initial state x(0) E:
2(+11) A(h, p, 2 (((+))) te No.
(I)
Here, the hyperparameters h E H allow for adjusting the algorithm, the parameters E 9 specify the loss function (()p)) the algorithm is applied to, and p((+1) E R models the (internal) randomness of the algorithm. To find suitable hyperparameters h E H, the algorithm A is trained on an i.i.d. data set of problem parameters S = (P)..., Px) in such way that its performance on is superior to that of traditional algorithms. However, in optimization "perfor- mance" is usually measured based on the whole sequence (rEN) for example, a linear rate of convergence has to hold for all iterations. Thus, to deal with such measures of performance, one needs to access the trajectories generated by A. This is where the Markovian model Sucker & Ochs (2024) comes into play: If h and p are fixed along the itera- tions, Equation (1) can be read as the functional equation of Markov process & (2(")) which defines distribu- tion on IN and thus allows for analyzing these trajectories. It is based on the following two assumptions:
and we denote its effective domain by dom f. Further, it
called lower contiionniuu if lim inf=== (z) 2 f(z) for all & E Σ. Furthermore, for E dom f. the (limiting) subdifferential of f at 2 is denoted by 0=(:). Similarly, for f x 9 > IR U (+o0), f=1, =2) denotes the (partial) subdifferential of f(-22) at ø1. In general, 0f: : = E is a set-valued mapping, and we denote its domain and graph by dom of and gph 0f, respectively. Here, a set-valued mapping T R = R is said to be outer semi-continuous at F. if simsup=-ss T(x) C T(t). where the outer limit is defined lim sumsup.... T(x) = {u (x(()) + I, (t)
Assumption 6.1. The state space B(I))),, the parameter space (P, (P)) space (H, 2 (()),, PH), and the randomization space (R. 2 (Bt), Pn) are Polish' probability spaces.
the hyperparameter
with (1) E [.. For convenience of the reader, we have collected more details in Appendix A. Also, the ex- act definition of a Kunlyka-Lojasiewicc: (KI.) function can be found there, as it is quite intricate. However, for the following, it is actually sufficient to understand that these are functions that are "sharp up to reparametrization" (At- touch et al., 2013), and that many functions encountered in real-world problems are KL-functions. Finally, the space of measures on I is denoted by M(3), and all probabil- ity measures that are absolutely continuous w.r.t. a refer- ence measure E M({) are denote by (1) == {v E M(33) v < μ and v/3c] = 13. Here, the Kullback-Leiber divergence between two measures a and v is defined as (K (4) v[log(f)) = Jxx (x)) v(dx), if v < 1 with density f. and +oo otherwise.
-vauued) loss- function : I x T + ox] and the algorithmic update A 3 x 9 x T
Assumption 6.2. The (possibly
x R + E are both measurable.
Then, Sucker & Ochs (2024) construct suitable proba- bility space (S, 2, P) that correctly models the joint dis- tribution of (H, P) on H x P x g:No, that is, the joint distribution over hyperparameters h, problem parameters p. and corresponding trajectories & generated by A(,, A(h,p.''' :..... By leveraging a well-known result due to Catoni (2007), they show that properties of trajectories &, encoded as sets A E B(P) @ ( @N,, generalize in a PAC-Bayesian way (Sucker & Ochs. 2024, Theorem 42):
Theorem 6.3. Let A C J x 3. be measurable, and define Φ ( = 1-exp( -ap) ap)
Then, for X (0, it holds that
T-exp(-o
6. Problem Setup
Ps Ps Vp E MF : (. {AH
Instead of considering a whole class of problems, we assume that we are given a parametric loss-function& e: I x ge > [0, oo] and random variable P taking values in the parame- ter space T R Here, I = Rd is the optimization space and the ultimate goal would be to solve
Σ P [ [P.....)H.. {AH
(KL PH) log (1)
}}
2 21 1
X
min ((z,p) =EI
Here, FH is the so-called prior over hyperparameters. Every is called a posterior, P( is the condi- tional distribution of the parameters with corresponding
for every realization P = Since we include non-convex optimization problems, finding the global minimum is infea- sible, and we focus on finding a critical point instead. For this, we apply an algorithmic update A H X x XF x ->
p E
' Polish space is separable topological space that admits complete metrization.
4

---

A Generalization Result for Convergence in Learning-to-Optmmize
trajectory, given the hyperparameters. and Pg is the distribu- tion of the data set S. On intuitive level, the probability to observe problem instance ((:p) and corresponding trajectory& generated by the algorithm A(h, p.,, -), which satisfies the properties encoded in A, can be bounded based on empirical estimates. It is important to note that, except for a brief remark, Sucker & Ochs (2024) do not make any further use of this result. In this paper, we observe the power of this theorem and apply it to the set of sequences that converge to critical point of l.
for deducing convergence critical point, which appears to be a common misconception.
Since we want to employ these results from variational cal- culus, we have to make the restriction I R and JP = R.. However, one could also consider a (finite- dimensional) state space I that encompasses the space of the optimization variable, that is, I = R x Rd,, and, by projecting onto IRd,, the results carry over immediately.
Assumption 6.7. We have I = Rd and 9 = =R, and the function é : Σ x P + [0, oc| is proper, lower semi- continuous, and continuous on dom L. Furthermore, the map (2.p) + 0z((2,p) is outer semi-continuous.
Definition 6.4. Let I IR U (+ be proper. A point E I is called critical for f. if 0f(z).
is crucial realize that, usually is impossible observe convergence directly, it belongs to the class of tail events, which do not depend on any finite number of iterates. Hence, to be able to apply the generalization result from above, we need abstract properties that do not depend on the imple- mentation of the algorithm, are easily observable during training, and are sufficient to deduce convergence, which, as we discussed in the related work, is highly non-trivial in the challenging setup of non-smooth non-convex optimization. Nevertheless, such conditions are provided by the following result due to Attouch et al. (2013, Theorem 2.9):
7. Theoretical Results
Now, we concretize our key idea from Section 4 for the setting of learning-to-optimizz and combine Theorem 6.3 with Theorem 6.5 to get generalization result for the con- vergence of learned algorithms critical points. In doing so, we bring together advanced tools from learning theory and optimization: We show that the probability to observe parameter and corresponding trajectory &. which con- verges to a critical point of E(,, p). generalizes. For this, we formulate the sufficient-descent condition, the relative-error condition, and the boundedness assumption as measurable sets in P x T such that their intersection is exactly the set of sequences satisfying the properties of Theorem 6.5.
Theorem 6.5. Let f I + R } be proper lower contiiiontiuuus function that is bounded from below. Fur- ther, suppose that (2(9))EN,, C. EE is a sequence satisfying the following property: There exist positive scalars a and b, such that the following conditions hold:
7.1. Measurability
(i) Sufficient-decrease. For each 1 E No. s(2((+1)) + (l|2(t+1) - 201 f(((t))
While measurability is usually dismissed as a technical- ity, it is absolutely necessary for the validity of employed theorems. Thus, to be able to apply Theorem 6.3, we have to show that these sets are actually measurable w.r.t. B(F) & B(I) % which, unfortunately, is not a given. Hence, denote the (parametric) set of critical points of & by
(ii) Relative-error: For each t E No, there exists ((++1) E (f(((+2)) with ||u(t+1)|| s 61| -1
(iii) Continuity: For any convergent subsequence
2(6) 123 2, we have f(2(t))) 1230 f(2).
Acrit == (p, E P x I 0 0E0,((z))))
Then, the section Acrit.p := E (p,z) E Aorit is the set of critical points of E(..p).
If, additionally, the sequence (2(()) is bounded and f is hurdyka-Lojasieww function, then (2(1)) )eEN converges to critical point of f.
Lemma 7.1. Suppose that Assumptions 6.1, 6.2 and 6.7 hold. Define the (parametric) set of sequences that converge to a critical point of l as
Remark 6.6. (i) The continuity condition cannot be
checked in practice. Therefore, we will have to as- sume that f(-.p) p) is continuous on its domain.
Aconv == {(p. (2(9)) E 9 x No
3x" Acrit,p s.t. lim || - 2"1 0}.
(ii) Theorem 2.9 of Attouch et al. (2013) is stated slightly different: They assume existence of convergent sub-
Then Aconv is measurable.
sequence instead of boundedness. Yet, boundedness implies existence and is standard (Bolte et al., 2014).
Proof. The proof is highly non-trivial and can be found in Appendix C. However, the idea is simple: Acony can be
(iii) In Appendix B, we provide examples to underline the
necessity of these conditions. Especially, we show that the sufficient-descent condition alone is not sufficient
FFor the cost of an even heavier notation, which is why we have omitted doing it here.
5

---

A Generalization Result for Convergence in Learning-to-Optimizee
written as countable intersection/union of measurable sets. This is possible, because we consider Polish spaces, that is, they have countable dense subset and they are complete, that is, limits of Cauchy sequences are inside the space. D
Corollary 7.5. Suppose that Assumptions 6.1, 6.2, and 6.7 hold. Furthermore, assume that E(;p)) is a Kurdyka- Lojasiewicz,functi for every E L. Then the sets Adesc N Aerr n Abound C I x In and Accuv C 9 x T are measurable, and it holds that:
Lemma 7.2. Assume that Assumptions 6.1 and 6.2 hold. Define the (parametric) set of sequences that satisfy the sufficient-descent condition as
Adesc O Aer n Abound C Aconv.
Proof. Let (p, (2(1))))))) E Adesc n Aere 7 Abound. Thus, JEEN satisfies both the sufficient-descent and the relative-error condition for E(,,),, and (=(1)) stays bounded. Further, (2(*) )EN, also satisfies the continuity condition, since we have (2l9) is continuous on its domain. Hence, Theorem 6.5 implies that (H(O),EN, J:eN, converges to critical point of P() that is, there exists x² E Acrit,p, such that lim || - z"1 0. Therefore, (p. )ENN)) E Accov-
Adese == { (p,, (2 )RENo) E x %
(=(0))EN, C dom (() and 3a > S.t. Vt E No
((2(++1), p) + all2 -2 200 ((2 .I)
dom ((.p)) and &
Then Adese is measurable.
Proof. The proof can be found in Appendix D.
In particular, if is a (probability) measure on SP x No, for example, fr = (P for a given h E H. by the monotonicity of measures it holds that:
We proceed with the relative error condition. It involves a union over all subgradients, and thus might not be mea- surable. Hence, we have to restrict to subgradients given through a measurable selection, that is, measurable func- tion dom 0,E + I, such that v(z,p) 0,((z, p) for every (z, p) E dom i.e. Under the given assumptions, its existence is guaranteed by Corollary E.3.
[= O Aerr O Abound) ) S po (r(ccon))
This idea yields our main theorem:
Suppose that Assumptions 6.1, 6.2, and 6.7 hold. Further, assume that (()p)) is a Sardyka-Lajasiewice function for every p P. Abbreviate A := Adecc O' Aerr Abouud. Then, for (0,,0), it holds that:
Theorem 7.6.
Lemma 7.3. Suppose that Assumptions 6.1, 6.2 and 6.7 hold. Define the (parametric) set of sequences that satisfy the relative-error condition as
Aer := (p., (2!"))EN))
x No
Pss Vp MG p(P(PES) {Acone H1 1111- 1-
(p, x1) E dom 0, VV E No and 36 > O.S.. V
p (P(P....)) [A$]]
[1 p)ll I (112(t-11) -2(1 }
(KI PH) log (t) (t))
}} 21 8-
Then Aerr is measurable.
X
Proof. By taking the complementary events in Corol- lary 7.5, we have PH-a.s.:
Proof. The proof can be found in Appendix E.
Lemma 7.4. Assume that Assumption 6.1 holds. Define the set of bounded sequences as:
POPc (A9 2 -P(P)) {Acom)
By Theorem 6.3, for any measurable set B C P No and
Abound = ={ (2(1)) E To
A E (0, oo), we have:
3e2 || S ScVl Sc No).
Ps { Vp E MM(H)) : P. (B)) N
Then Abound g0 x Abound is measurable.
p [PPPrr.....m.. [B)]
Proof. The proof can be found in Appendix F.
Drt PH) log (1)
}} 2 21 e
A
7.2. Convergence to critical points
Hence, using B := AS, inserting the inequality above, and rearranging the terms yields the result.
We are now position to derive our main result.
6

---

A Generalization Result for Convergence in Learning-to-Optimize
Remark 7.7. (i) The lower bound actually applies to P(P (A]. Since the difference (( er (Acone \A] is unknown, we do not know the tightness of this bound for P( ((P.))) }Acouv)
that is, if the algorithm "finds" this structure during lear- ing by itself, it can leverage on it. Like this, the given class of functions is L4-smooth and -stronggly convex, such that we use heavy-ball with friction (HBF) (Polyak, 1964) as worst-case optimal baseline. Its update is given by 2(++1) = 2(0) - 31 f)(=()) + (z(t) - z(t-1)), where the optimal worst-case convergence rate is attained for 31 =
(ii) We want to stress the following: We do not assume that the conditions of Theorem 6.5, for example, the sufficient-descent condition, do hold per se. As de- scribed in Section 4 about the underlying idea, this theorem is rather about the fact that, based on our obser- vations during training, we can deduce how often these conditions will hold on unseen problem instances.
VL.+VE= .B - (VZ+-VE=)) (Nesterov, 2018).
2
VL.+v==
Similarly, the learned algorithm A performs update of the form z((+1) 2(()) ((0) where z(t) and d(t) are predicted by separate blocks of a neural network. Here, we stress that the update is not constrained in any way. For more details on the architecture we refer to Appendix G. Since the functions are smooth and strongly convex, we only have to check the sufficient-descent condition and the relative- error condition. Obviously, in practice it is impossible to check them for all & E No- Thus, we restrict to Itrain 500 iterations. Then, given measurable selection v=2p)) E 016 p). the relative-error condition is trivially satisfied with := max (lle(2(), pp)l mineg ||2(()
(ii) For large NN, if À is chosen correctly, we can approx- imate & (-((0= R p. Assuming this holds, and abbre- viating the empirical approximation as P(P == Ex (H the inequality reads:
plP( {Acony]] 2 [P(P.)) [A]]
(p PH) + log (2)
= =(( such that we only have to check the sufficient- descent condition during training. Finally, we consider to be converged, if the loss is smaller than 10-16, For more de- tails we refer again to Appendix G. The results are shown in Figure I: The left plot shows the distance to the minimizer =* over the iterations, where HBF is shown in blue and the learned algorithm in pink, and we can see that the learned algorithm is clearly superior. The right plot shows the estimated probabilities IP (P(P.)) (A} (yellow dashed line), P ((P:S)) и [Acony] (purple dashed line), and the PAC-bound (orange dotted line) on 250 test sets of size N = 250. We can see that the PAC-bound is quite tight for (P(P.)) (A), while there is a substantial gap P ((P.)) H (Aconv \A}. Never- theless, it guarantees convergence of the learned algorithm in about 75% of the test problems.
This is intuitive: For larger N, we have more confi- dence in our estimate P (( {A], so we can choose larger À which dampens the last term and tightens the lower bound for ((P:)) {Aconvh.
8. Experiments
In this section, we conduct two experiments: The strongly convex and smooth problem of minimizing quadratic func- tions with varying strong convexity, varying smoothness, and varying right-hand side, and the non-smooth non-convex problem of training a neural network on different data sets. The code to reproduce the results can be found at ht tps: : //gi t thub. comm MMwhhiisucei Stw.chicccceer/o.222222
8.2. Training a Neural Network
8.1. Quadratic Problems
As second experiment, we train the algorithm A to train a neural network N on a regression problem. Thus, the al- gorithm predicts parameters 3 E Rd., such that N(3,.) estimates a function g : R + R from noisy observa- tions Vi.j (x²))) + Si.j
First, we train the algorithm A to solve quadratic problems. Thus, each optimization problem ((.,p) is of the form
1 2 I1 - -112, A Rddd b BER.. =ER4
1,... K iid N(0, 1). Here, we use the mean
1,..,,
min
(K 50), with E.g. square enror as loss for the neural network, and for N we use fully-connected two layer neural network with ReLU- activation functions. Then, by using the data sets as param- eters, that is, D = IR Kx2 and p. = {( yr ) the loss functions for the algorithm are given by ((5.p:) == K Σ (N(8, sr. - yi.j)², which are non-smooth and non-convex in 3. Here, the input x is transformed into the vector (z, 2² ...., rr),, such that the parameters 3 E Rd are given by the weights A₁ e 55005 A2 e IR 1x00 and
such that the parameters are given by p = (A E Rd =: P. and the optimization variable is E Rd, d = 200. The strong-convexity and smoothness constants of f are sampled randomly in the intervals [m_, m+], [L_, L4] C (x,+ and we define the ma- trix Aj. j = 1,..., N, as diagonal matrix with entries d, = -mm + L( i = d. In prin- ciple, this is a severe restriction. However, we do not use this knowledge explicitly in the design of our algorithm A,
7

---

A Generalization Result for Convergence in Learning-to-Opiimize
107
PePACc {A}
40
10a
P(P {Aconv] PAC-bound
10
30
10
21))))
10-9
Learned
Serain
10
10 10-13 13
HBF
0
0
200
400
600
800
1000
0.7
0.8
0.9
1.0
Figure 1. Quadratic problems: The left figure shows the distance to the minimizer over the iterations, where heavy-ball with friction (HBF) shown
and learned algorithm pink. The mean and median are shown as dashed and dotted lines, respectively, while the shaded region represents 95% of the test data. One can see that the learned algorithm converges way faster than HBF. The right plot shows the estimates (dashed lines) (( u (A] (orange), ((Pe)) 2 (Aconv) (purple), and the PAC-bound (dark orange). One can see that the predicted chain of incqualities 1 - $ (...) < P(PENM|A) s P(Pa)) (Acov } does hold truc.
biases bj E 50 by E R of the two fully-connecter lay- ers. Thus, the optimization space is of dimension p == 351. For the functions gi use polynomials of degree d 5, where sample the coefficients (c,,0- C1,5) uniformly in [-5,5, 5]. Similarly, formly in [-2, 2]. As baseline we use Adam (Kingma & Ba, 2015) as it is implemented in PyTTorch (Paszke et al., 2019), and we tune its step-size with a simple grid search over 100 values in [10-4, 10- such that its performance best for the given frain 250 iterations. This yields the value x = 0.008. Note that we Adam in the "full-batel setting" here, while, originally, it was introduced for the stochastic case. On the other hand, the learned algorithm performs the update (f++1) = 21t) + d(()/ /Vt, where d(() is predicted by a neural network. Again, we stress that d(1) is not constrained in any way. For more details on the archi- tecture, we refer Appendix As we cannot access the critical points directly,
9. Conclusion
We presented novel method for deducing convergence of generic learned algorithms that exhibit a Markovian struc- ture with high probability. To showcase the idea, we derived new convergence result for learned optimization algo- rithms on (possibly) non-smooth non-convex loss-functions based generalization. This was based on the fundamental insight that, contrary to traditional optimization, in learning- to-optimize we can actually observe the algorithm during training. While the approach is theoretically sound, prac- tically it has at least four drawbacks, on which we shortly want to comment: First, and foremost, one simply cannot observe the whole trajectory practice. Thus, one can only obtain approximation to this result, that is, whether the used conditions do hold up to certain number of iterations. Nevertheless, by using sufficiently many iterations, one can guarantee that the algorithm gets sufficiently close to criti- cal point. Second, instead of verifying the conditions used here, one could alternatively try observe the final result directly, for example by looking the norm of the gradient. However, when checking the proposed conditions one is guaranteed to get arbitrary close critical point, while, in the other case, one could end up with small gradient norm that is arbitrary far away from a critical point. Especially, this applics the non-smooth setting, where the subdiffer- ential does not necessarily tell anything about the distance to a critical point², or to applications where one simply can- not access critical points during training. Third, for now, training the algorithm in such way that it actually does satisfy the proposed properties majority of problems
sample the points { j=1 uni-
approximate them by running gradient descent for 5 10 iterations with step-size of 1. 10-6, starting for each problem and algorithm from the last iterate (t = 500), Similarly, we cannot estimate the convergence probability in this case, only the probability for the event A. The results this experiment are shown in Fig- ure 2: The left plot shows the distance the critical point and the plot in the middle shows the loss. Here, Adam is shown in blue, while the learned algorithm is shown in pink. Finally, the right plot shows the estimate for TP (P.))) (A) and the predicted PAC-bound. We can see that the learned algorithm does indeed seem to converge to a critical point and it minimizes the loss faster than Adam. Further, the PAC-bound is quite tight, and it guarantees that the learned algorithm will converge in about 92% of the problems.
FFor example, consider f(z) |z].
8

---

A Generalization Result for Convergence in Learning-to-Opiimizee
80
10
Learned
PAC-bound
farain
P(P.E)
[1a(t) 2²112
10a
10a
MSB(g()) Nobal
60
8(2 .p)
Adam
10a
10
40
10a
Learned
20
10-4
Berain
10a
Adam
100
200
300
400
500
0.8
IP
Figure 2. Training neural network: The left figure shows the distance to the estimated critical point and the figure in the middle shows the loss. Adam is shown in blue and the Iearned algorithm in pink. The mean and median shown dashed and dotted lines, respectively, while the shaded region represents 95% of the test data. We see that the learned algorithm minimizes the loss faster than Adam, and seems converge a critical point. right plot shows the estimate ((re)) (A] (orange dashed line) the PAC-bound (dark orange).
is quite difficult and time-consuming. Lastly, due to the sufficient-descent condition, Theorem 6.5 is not well-suited for stochastic optimization. Nevertheless, Theorem 6.3 and the proposed approach can directly be transferred to the stochastic setting, which we leave for future work.
Attouch, H. and Bolte, J. On the convergence of the proxi- mal algorithm for nonsmooth functions involving analytic features. Mathematical Programming. 116:5-16, 2009.
Attouch, H., Bolte, J., Redont, P., and Soubeyran, A. Prox- imal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Inequality. Mathematics of Opera- tions Research, 35(2):438 457, 2010.
Acknowledgements
M. Sucker and P. Ochs acknowledge funding by the German Research Foundation under Germany's Excellence Strategy EXC number 2064/1 - 3907277645.
Attouch, H., Bolte, J., and Svaiter, B. F. Convergence of descent methods semi-algebraic and tame problems: proximal algorithms, bawwardbbckwwrdd splitting, and regularized Seidel methods. Mathematical Pro- gramming, 137:91-129, 2013.
Impact Statement
We do not any negative impact of our presented work.
Bégin, L., Germain, Laviolette, F., and Roy, J.-F. PAC- Bayesian Bounds based the Rényi Divergence. In Proceedings of the 19th International Conference Ar- tificial Intelligence and Statistics, volume 51 of Proceed- ings of Machine Learning Research, pp. 435-444. PMLR, 2016.
References
Absil, P.-A., Mahony, R., and Andrews, B. Convergence of the Iterates of Descent Methods for Analytic Cost Functions. SIAM Journal on Optimization, 16(2):531- 547, 2005.
Alquier, P. User-friendl, Introduction to PAC-Bayes Bounds. Foundations and Trends@ in Machine Learning, 17(2):14-330, 2024.
Bierstone, E. and Milman, P. D. Semianalytic and subana- lytic sets. Publications Mathématiques de l'Institut des Hautes Études Scientifiques, 67:5 42, 1988.
Alquier, and Guedj. B. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5):877-902, 2018. doi: 10. 109777/009944007-566000
Bolte. J., Danilidiis A., and Lewis, A. The Lojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems. SIAM Journal on Optimization, 17(4): ((44):2055) 205-1223 2007a.
Amit, R., Epstein, B., Moran, S., and Meir, R. Integral Probability Metrics PAC- Bay-s Bounds. In Advances in Neural Information Processing Systems, volume 35, pp. 3123-3136, 2022.
Bolte, J., Danillidis, A., Lewis, A., and Shiota, M. Clarke Subgradients of Stratifiable Functions. SIAM Journal on Optimization, 18(2):556577,, 2007b.

---

A Generalization Result for Convergence in Learning-to-Optimiz
Bolte, J., Sabach, S., and Teboulle, M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1):4594494, 2014.
In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 604-612. PMLR, 2021.
Buzzard, G. T., Chan, S. H., Sreehari, S., and Bouman, C. A. Plug-and-play Unplugged: Optimization Free Re- construction Using Consensus Equilibrium. SIAM Jour- nal on Imaging Sciences, 1 1103)200112020,, 2018.
Germain, P., Lacasse, A., Laviolette, F., and Marchand, M. PAC-Bayesian Learning of Linear Classifiers. In Proceedings of the 26th Anmual International Conference on Machine Learning, pp. 353-360, 2009.
Castera, C. and Ochs, From Learning to Optimize to Learning Optimization Algorithms. arXiv preprint arXiv:2405.18222, 2024.
Gregor, K. and LeCun, Y. Learning Fast Approximations of Sparse Coding, In Proceedings of the 27th International Conference on Machine Learning, pp. 399-406, 2010.
Catoni, O. Statistical Learning Theory and Stochastic Opti- mization. Springer Berlin, Heidelberg, 2004.
Guedj. B. A Primer on PAC-Bayesian Learning. In Proceed- ings of the Second Congress of the French Mathematical Society, volume 33, 2019.
Catoni, O. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning. Lecture Notes- Monograph Series, 56, 2007.
Haddouche, M. and Guedj. B. Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation. arXiv preprint 1Xiv:2304.07045 2023.
Chan, S. H., Wang, X., and Elgendy, O. A. Buug-andPPin Play ADMM for Image Restoration: Fixed-Point Convergence and Applications. IEEE Transactions on Computational Imaging, 3(1):84-99 98, 2017.
Heaton, H., Chen, X., Wang, Z., and Yin, W. Safeguarded Learned Convex Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 3766)7788--7855 2023.
Chen, T., Chen, X., Chen, W., Heaton, H., Liu, J., Wang, Z., and Yin, W. Learning to Optimize: A Primer and A Benchmark. Journal of Machine Learning Research, 23 (189):1-59, 2022.
Hellström, F., Durisi, G., Guedj, B., and Raginsky, M. Gen- eralization Bounds: Perspectives from Information The- ory and PAC-Bayes. Foundations and Trends@ in Ma- chine Learning, 18(1):1-223, 2025.
Chen, X., Liu, J., Wang, Z., and Yin, W. Theoretical Linear Convergence of Unfolded ISTA and Its Practical Weights and Thresholds. Advances in Neural Information Pro- cessing Systems, volume 31, 2018.
Honorio, J. and Jaakkola, T. Tight Bounds for the Expected Risk of Linear Classifiers and PAC-Bayes Finite-Sampp Guarantees. In Proceedings of the Seventeenth Interna- tional Conference on Artificial Intelligence and Statistics, volume 33 of Proceedings of Machine Learning Research, pp. 384-392, PMLR, 2014.
Chen, X., Zhang, Y., Reisinger, C., and Song, L. Under- standing Deep Architecture with Reasoning Layer. In Advances in Neural Information Processing Systems, vol- ume 33, pp. 1240-1252, 2020.
Kingma, D. P. and Ba, J. Adam: A Method for Stochas- tic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
Cohen, R., Elad, M., and Milanfar, P. Regularization by Demoising via Fixed-Point Projection (RED-PRO), SIAM Journal on Imaging Sciences. 14(3):137414466, 2021. doi: 10.1 5572001137166
Kobler, E., Effland, A., Kunisch, K., and Pock, T. Total Deep Variation: A Stable Regularization Method for Inverse Problems. JEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12):916399180 2022.
Dziugaite, G. K. and Roy, D. M. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Net- works with Many More Parameters than Training Data. In Proceedings of the Thirty-This Third Conference on Uncer- tainty in Artificial Intelligence. AUAI Press, 2017
Kurdyka, K. On gradients of functions definable in o- minimal structures. In Annales de l'institut Fourier, vol- ume 48, pp. 769-783, 1998.
Langford, J. and Caruana, R. (Not) Bounding the True Error. Advances in Neural Information Processing Systems, volume 14, 2001.
Dziugaite, G. K. and Roy, D. M. Data-dependent PAC- Bayes priors via differential privacy. In Advances in Neu- ral Information P Processing Systems, volume 31, 2018.
Langford, J. and Shawe-Taylos J. PAC-Bayes & Margins. In Advances in Neural Information Processing Systems, volume 15, 2002.
Dziugaite, G. K., Hsu, K., Gharbich, W., Arpino, G., and Roy, D. On the Role of Data in PAC-Bayes Bounds.
10

---

A Generalization Result for Convergence in Learning-to-Optimize
Lever, G., Laviolette, F,, and Shawe-Taylor, J. Tighter PAC-Bayes bounds through distribution-dependent priors. Theoretical Computer Science, 473:4-28, 2013.
Heráadz- E., Ambroladze, A., Shawe-Taylor, J., and Sun, S. PAC-Bayes Bounds with Data Dependent Priors. Journal of Machine Learning Research, 13(112); 3507 3507-3531,200 2012.
Liu, J.. Chen, X., Wang, Z., Yin, W., and Cai, H. Towards Constituting Mathematical Structures for Learning to Op- timize. In Proceedings of the 40th International Confer- ence on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 21426-21449. PMLR, 2023.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z.,, Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang. E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: An Imperative Style, High- SiihhPeeffomance Deep Learning Library. In Advances in Neural Information Processing Systems, volume 32, 2019.
London, B. A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient De- scent. In Advances in Neural Information Processing Systems, volume 30, 2017.
Pérez-Ortic Ortiz. M., Rivasplata, O., Shawe-Taylor, J., and Szepesvári, C. Tighter Risk Certificates for Neural Net- works. Journal of Machine Learning Research, 22(227); 1-40, 2021.
McAllester, D. A. Simplified PAC-Bayesian Margin Bounds. In Learning Theory and Kernel Machines, pp. 203-215. Springer Berlin, Heidelberg, 2003a.
McAllester, D. A. PAC-Bayesian Stochastic Model Selec- tion. Machine Learning, 51(1):5-22 21, 2003b.
Polyak, B. T. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Metz, I.., Maheswaranathan, N., Nixon, J., Freeman, D., and Sohl-Dickstein, J. Understanding and correcting pathologies in the training of learned optimizers. In Pro- ceedings of the 36th International Conference on Ma- chine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4556-4565. PMLR, 2019.
Prémont-Schwarz, I., Vítkû, J., and Feyereisl, J. A Simple Guard for Learned Optimizers. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 17910-17925. PMLR, 2022.
Metz, L.., Freeman, C. D., Harrison, J., Maheswaranathan, N., and Sohl-Dickstein, J. Practical Tradeoff's between Memory, Compute, and Performance in Learned Optimiz- ers. In Proceedings of The 1st Conference Lifelong Learning Agents, volume 199 of Proceedings of Machine Learning Research, pp. 142-164. PMLR, 2022.
Rockafellar, R. T. and Wets, R. J.-B. Variational Analysis. Springer Berlin, Heidelberg, 1998.
Ryu, E., Liu, J., Wang, S., Chen, X., Wang. Z., and Yin, W. Boug-and-Play Methods Provably Converge with Properly Trained Denoisers. In Proceedings of the 36th Interna- tional Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5546- 5557. PMLR, 2019.
Möller, M., Möllenhoff, T., and Cremers, D. Control- ling Neural Networks via Energy Dissipation. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 3255-3264 2019.
Seeger, M. PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification. Journal of Machine Learning Research, 3:233-269, 2002.
Nesterov, Y. Lectures on Convex Optimization. Springer
Cham, 2018
Ochs, P. Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano. SIAM Journal on Optimization, 29(1):541-577 2019.
Sreehari, S., Venkatakrishnan, S. V., Wohlberg, B., Buzzard, G. T., Drummy, L. F., Simmons, J. P., and Bouman, C. A. Plug-and-Play Priors for Bright Field Electron Tomog- raphy and Sparse Interpolation. IEEE Transactions on Computational Imaging, 2(4):408 423, 2016.
Ochs, P., Chen, Y., Brox, T., and Pock, T. iPiano: Inertial Proximal Algorithm for Nonconvex Optimization. SIAM Journal on Imaging Sciences, 7(2): 2014.
Sucker, M. and Ochs, P. PPC-Baayssinn Learning of Opti- mization Algorithms. In Proceedings of The 26th Inter- national Conference Artificial Intelligence and Statis- tics, volume 206 of Proceedings of Machine Learning Research, pp. 8145-8166 146488164 PMLR, 2023.
Ohnishi, Y. and Honorio, J. Novel Change of Measure Inequalities with Applications to PAC-Bayesian Bounds and Monte Carlo Estimation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 1711-1719. PMLR, 2021.
Sucker, M. and Ochs, P. A Markovian Model for Learning- to-Optimize arXiv preprint arXiv:2408. 1629, 2024.

---

A Generalization Result for Convergence in Learning-to-Optimiz
Sucker, M., Fadili, J., and Ochs, P. Leaamin-to-OOtimizze with PAC-Bayesian Guarantees: Theoretical Consider-
ations and Practical Implementation. arXiv preprint arXiv.2404.03290, 2024.
Sun, Y., Wohlberg, B., and Kamilov, S. An Online Plug-and-Play Algorithm for Regularized Image Recon- struction. IEEE Transactions on Computational Imaging, 5(3):395 408, 2019.
Teodoro, A. M., Bioucas-Dias, M., and Figueiredo, M. A. T. Scene-Adapted plug-and-pla and-play algorithm with con- vergence guarantees. In 2017 IEEE 27th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2017.
Terris, M., Repetti, A., Pesquet, J.-C., and Wiaux, Y. En- hanced Convergent PNP Algorithms For Image Restora- tion. In 2021 IEEE International Conference Image Processing (ICIP), pp. 1684-1688. IEEE, 2021.
Thiemann, N., Igel, C.,, Wintenberger, O., and Seldin, Y. A Strongly Quasiconvex PAC-Bayesian Bound. In Proceed- ings of the 28th International Conference Algorithmic Learning Theory, volume 76 of Proceedings of Machine Learning Research, pp. 466-492. 492. PMLR, 2017.
Tirer, T. and Giryes, R. Image Restoration by Iterative Denoising and Backward Projections. IEEE Transactions on Image Processing, 2203):1220-12333 2019.
Wichrowska, O., Maheswaranathan, N., Hoffman, M. W., Colmenarejo, S. G., Denil, M., Freitas, N., and Sohl- Dickstein, J. Learned Optimizers that Scale and General- ize. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Ma- chine Learning Research, pp. 3751-3760. PMLR, 2017.
Xin, B., Wang, Y., Gao, W., Wipf, D., and Wang, B. Maxi- mal Sparsity with Deep Networks? In Advances in Neural Information Processing Systems, volume 29, 2016.
12

---

A Generalization Result for Convergence in Learning-to-Optimizee
A. Missing Definitions
The following definitions can be found in the book of Rockafellar & Wets (1998). A function f: E RU{+x} is called proper, fx) +o0 for at least one point I E I2d and f (a) -0 for all R In this case, the effective domain of the set
dom = fo E E f(z) too}.
Similarly, for a set-valued mapping T : 30 = Y the graph is defined as
gph T = {x, v) E a x y y T(x))
while its domain is defined as
dom T fx T(x) *0}
The outer limit of a set-valued map T R = R defined as:
lim sup T(x) == { y (z E. Ey y with y E T(x(1)]
Based on this, said to be outer semi-continuous at ã. if
lim sup (())) x-+2
Definition A.1. Consider a function f: IR RU [ ( and point ã E dom f. For a vector v Rd, one says that
ii) e is a regular subgradient of f at h. if
f(x) f(t) + (e, σ) + (1|= - =]])
The set of regular subgradients of f at F. denoted by 0f()) is called the regular subdifferential of at T.
(ii) is (general) subgradient of f at F, there are sequences (+()) and v()) - u with f(x()) + f(z) and (e) E ()) The set of subgradients of f at T. denoted by @ā is called the (limiting) subdifferential of f at a.
Finally, the following definition can be found in Attouch et al. (2013, Definition 2.4, p.7).
propper at T dom Øf. Definition A.2. The function ʃ Rd IR U { (+o0) is said to have the Kurdyka- Hardyka-tojjsiien Lojasiewicz property
if there exist (0, +oo), neighborhood U of F, and continuous concave function yp [0, - [0, oo), such that
(i (00) = 0. (ii Φ is C¹ (0.
(iii) for s E (). (s)) 00
(iv) for all in U < < f() n). the Kurdyka- inequality holds
/f (J(x) - f()) (0, 21
b) Proper lower semi-continuous functions which satisfy the Kurdyka-Lojjsiewiizz property each point of dom Of are called
B. Counterexamples
Example B.1 (Violation of boundedness assumption). Starting from (11) == 1, define the sequence for 2 S t E N by 2(1) =
2(t11) 1, and consider the positive and convex function f()) == exp( (0)) 2). We show that the sequence ((()))EN does
satisfy the sufficient-descene condition for f: By definition, we have the recursive formula ((((++) = f(((1)) exp (- which allows for rewriting the sufficient-descent condition as:
1 (-+11) 1(=(1).
a
Σ 1 exp
(t + 1)2
13

---

A Generalization Result for Convergence in Learning-to-Optimize
Then, have find satisfying this inequality for all E N. For / 1, the right-hand side is greater than J. such that can choose any (0, a] (rough estimate). Thus, take E (0, $). such that = 2e (0, $] and proceed by induction (note that satisfies the stated condition for = 1). Assuming that the inequality holds true for up time t, we get by the induction hypothesis:
1 1+1] (12)
(1-esp -xee (-++T) s(210)
(L + 2)
By inserting trivial three-times, the right-hand side can be written as:
t t+1 1 2 t+2
1
exp
1+1
1 (1- exp (T+z2) f(((1-1).
exp
t +
exp
r42
Here, the first term bounded by 1, the second by e, and the third by Hence, dividing both sides by 2e, we get:
+ 2) S (1 exp (..p(((+))) (-o+2) s(=((t1)),
such that (2(1)) satisfies the sufficient- dessent condition for f. Nevertheless, we have 2(1) (1--1)+ -E R
such that (2 2 oo, that is, the sequence is unbounded and does not converge.
Example B.2 (Violation of relative-error condition). Consider the smooth and strongly convex function f(21, = 1
2 22. and define the sequence ((z(9, 22 (CEN C R22 through
(2) (1+1), 22 ((+1)) (21
(0) (21 0.122 (1,
(1) 22) ().
Then we have (1 (1+1), ((++)) - (21 (1, ]1 (0.12) (0)) and it holds:
f(2 (t+1) 22 (++1))) = 21 (6) - 0.121 () +
1
22 (2) )²
2
= f(z (), 23 ()) - 0.1
22 (0) 2
(0.22 ())
+
2
f(z () 222 - 9.5 (++1)
22 (1+1))
(2) (t) 222 (1)
such that (z (t+1),,, .2 (++1)) satisfies the sufficient-descentt condition. However, for 22 (0) + 0, the sequence converges to (0, 22 (0)), which is not a critical point of f.
C. Proof of Lemma 7.1
Lemma C.1. Suppose Assumption 6.7 holds. Then, Acrit is closed.
Proof. Take (plt),20 )(() C. Acrit with (p(t),2(1 (p, E 90 E. We need to show that (2, E Aerit- Since (2,p) + 02((2,p) is outer semi-continuous, we have:
lim sup 0e((2.p) c 0,((E.p) (E.p)
By definition of the outer limit, this is the same as:
{ (uE I (0200,(0)) (2,p), () + with (1)) =,e(= p0)) c a,)(2.p).
In particular, we have that (00 - (2, and holds (2(()( ()) for all e N. Thus, setting (()) := 0 for all t E N and u 0, we conclude that E 0, p). Hence, (p, 2) E Acrit, and Actit is closed.
Now, we can prove Lemma 7.1:
14

---

A Generalization Result for Convergence in Learning-to-Optimize
Proof. To show measurability of Aconv, we adopt the notation of the limes inferior for sets from probability theory: If d is metric on P x I and > 0, define the set
(p, 2) u = { E (p( ult.)
u
U--U (6''
U
neÑo t2n
E T x L (p', E (p, z)}. Thus, (p, 3 is the (parametric) set of all sequences in E that ultimately lie in the ball with radius around (p, =). Note that (Be(p, 2) 3 is measurable w.r.t to the product o-algebra on 9P x I since it is the countable union/intersection of measurable sets, where {(y/, 2 E (p, is measurable, since it can be written as {d((p', (()), (p, 2)) < E)
Here, ((p'22") E (p. is short-hand notation for {(p',
(g (id, me)) =0. Here, id is the identity on P and g(p', z²) d((p', ; z'), (p, 2)) is continuous. Since the proof does not get more complicated by considering general Polish space P. E instead of R and Rd we prove the result in this more general setting. For this, denote the the complete metric on IP by dg, and the one on I by dr. Then we have that doxx == dæ + dy is a metric on P x E. that metrizes the product-topology. that is, it yields the same g-algebra. Similarly, denote the countable dense subset in 9 by P, and the one in I by 2. Then we have that D = P 2 a countable and dense subset of P x I. If Aerit is empty, we get that Aconv 0, which is measurable. Hence, w.l.o.g. assume that Acrit * 0. We claim that:
Aconv =
U (p.=)ED (r
(BI,((,,2) ult.).
KEN
If this equality holds, Acony is measurable as countable intersection/union of measurable sets. Thus, it remains to show the equality Aconv C, which we do by showing both inclusions. Therefore, first, take (p, )EE%) E Aconv. Then there exists 2" E I, such that (p, =*) E Acrit and lim dy (2((), =²) = 0. Hence, for any A E N. there exists ty E N, such that 200) E B1/ax(=") for all 2 (g. Now, take (Pk; =x) E DD such that ps B1/33(D) and z B1/ax(z*), ), which exists, since D is dense. Then, for all 2 ty we have:
1 T.'
døxx (p,, 20),, (Pk: =)) = (p. + d2 (z(0), 2x) S do Pk) + dz
that is, (p, (z (0) )ENN)) E (BI/A(PA, ult.). Further, we have:
2 1
dxxI(pp,2 (pk. 2x)) <
3k K
Hence, (pk, 2x) D with Acti B1/ 2x) # 0. Since such a tuple (pk, 2k) E D can be found for any N, we get:
(p. (2 )1X,)) (ex))) E
U
(Biyk(p',z') ult.), V.
(v' JED Acme Be )')
Then, however, this implies (p. )EEN)) C, which shows the inclusion Acouv C C. Now, conversely, let (p, (e())))N)) E C. Then, for every A N there exists (pk, =x) D with Acrit n (I/A(PE, =k) # 0, and t E N, such that
(9) E B1y1 (P&, 2x), Vt 2 tx.
The resulting sequence of midpoints (Pk. 24 kKEN is Cauchy in P x I. because: For k. l E N. we have that (p, 2()) e B (I/K(PE, zx) for all 2 tu. and (p, ()) E BI/r(Di, 2) for all > t.. Thus, for t 2 T == max(tr, tt), we get
(p, ()) (IyM(Pk, 2x) n Bi/ri(p,,2) 21), which allows for the following bound:
d (pb, =k), (pi, 21)) S dø x ((p), =x), (p, ((x))) + de x ((p, 2 2(1))), (p, (T))
+ doy x
((p, = (7)), (p, z (1))
- d ((p, (tt)) (1))
1
2
2
1
3
3 k. 0.
1:
k
15

---

A Generalization Result for Convergence in Learning-to-Optimizee
Hence, by completeness of & Σ, the sequence (pk ( =k)ken has limit (p", ,,²) in 90 E. First, show that p p. Since (p, ((x)) E (p 2x) for all & N, we have by continuity of the metric:
dy (p.p") = lim (p.p. k-
-
lim dexx ((p, 2(6)), (pss (6)) S k=500
lim = k=500 k
Thus, actually, (ps, 24) + (p,2*) Second, we show that (p,z*) E Acrit. that is, 2² E Aerit,pi Assume the contrary, that is, (p,2*) 2*) E Actit By Lemma C.I. the set Aerie is closed. Thus, complement Acr is open, and there exists O with (p, =*) C A that is, (p, n Aerit 0. Since (Ph: =k) (p, there exists N E N, such that dø ((pk; 2k), (p, x)) < I for all k 2 N. Then, however, taking & 2 N with 5. conclude that
(2k Axe) n Acrit = 0.
By definition of the sequence (pk, =e), this is contradiction. Hence, we have (p, =*) E Acrit and remains to show that also the sequence (z(4)) )reN converges 2². For this, assume the contrary again. Then there exists with the property that for all T E N, one can find a 2 T, such that dz (z()), =²)) 2 E. Now, choose E N large enough, such that dr (2k, 2*) S and 1 k 3. Then, since (p, (0)) E (IF 2k) for all tx. we have:
28 <E,
dz(210, s dz(2(),, 2x)) + dz (Zk, x²) v 3
VA 2 t
Again, this is contradiction and such 0 cannot exists. Thus, (2(())EEN, converges to x' E ps and we have (p, (z(9)) )tEN)) E Aconv, which concludes the proof.
D. Proof of Lemma 7.2
Proof. Since Q is dense R. we can restrict E (0) ( Q+. Then Adese can be written as
Aoie n (n
(e( p) < oo))
aEQ-
tENo
LENO
where A is given by:
(( ,p) + (( - -2(0) (00)12<((00) E(2(())))) .1)
Since o-algebras are stable under countable unions/intersection, it suffices to show that the sets (!(=(0.p) < oo) and Ant are measurable. Here, the set {L(2(0,p) p) < 2o) can be written as:
{ [(=00) < 00) = o (.d, (0)
where Φ: T x E I x T just interchanges the coordinates (which is measurable), and id is the identity on P. Since [0, oo) is a measurable set and f is assumed to be measurable, we have that (f(=(0,,) ,p) < oo) is measurable for each t E No- To show that Aa, is measurable, we define the function ga : (dom 8)² + through ((11,11), P2)) + ((2,,2) P2) - ((21,1)) + 2l - 22. Then, Jo is measurable and Ag, can be written as:
An, (,((2 .p.
2((11) p)) $ {0
(ga (m, id, Te- id) o s) (p, (=10)) $0}
(ga a (m,, id, T141, id) o 1)) (-x0,0)
where v T0 x No + No. x 2 is the diagonal inclusion (p. 2) + (2z,p), (2, p)), which measurable w.r.t. to the product-o- on (INN) No x 24),, since -1 (B1 x B₂) = B, n B2. Thus, the set Au, measurable, which concludes the proof.
16

---

A Generalization Result for Convergence in Learning-to-Optiiize
E. Existence of Measurable Selection and Proof of Lemma 7.3
Definition E.I. A set-valued mapping T : x = Rd measurable, if for every open set C R the set (-) C 9 measurable. In particular, dom T has be measurable.
Lemma E.2. Suppose Assumption 6.7 holds. Then (2.p) + 02((2, p) is closed-valued and measurable.
Proof. Since 0 [2, p) is the subdifferential of ((.,p) 2, by Rockafellar & Wets (1998, Theorem 8.6, p.302) have that the set 0, (2,((,)) p) is closed for every p E Se and every E dom ((.p)). Hence, we have that 0 (z, is closed for every (z,p) E dom& f. Further, for p) & dom é. we have 0 (2) p) = 0, which is closed, too. Therefore, (z,p) + 01((2, is closed-valued. Finally, since () + 0g (2, p) is also outer semi-continuous, Rockafellar & Wets (1998, Exercise 14.9, p.649) implies that 0,6 is measurable w.r.t B(I x P).
Corollary E.3. Suppose Assumption 6.7 holds. Then there exists a measurable selection for o,e, that is, a measurable map V: dom 0ge + I. such that u(zp) E Ōg p) for all (2.p) x
Proof. By Lemma E.2, the map (2.p) ト 02 p) is closed-valus and measurable. Hence, the result follows directly from Rockafellar & Wets (1998, Corollary 14.6, p.647).
Now, we can prove Lemma 7.3:
Proof. Again, can restrict to b Q 70, =: Q++ Thus, Aerr can be written as:
(((()()))) (N(()l))
U N bEQ+ EENo
Aerr
Bu,
dom de}
MENO
where B is given by:
B = (p. (2(%)))) E E x No [[((2(+t1), -p)l S bl(=((+1) =(100+
Hence, since alaleebras are stable under countable unions/intersections, we only have to show measurability of the sets Ba, and {(2(*), p) E dom E2 Here, holds that:
(x .) E dom 0,0} = ( o (id, mT)) (dom 0,
where id is the identity on 9, and & 9 x I + I Se just interchanges the coordinates. By Lemma E.2, dom 0, is measurable, such that {(<("),p) p) E dom 0 is measurable for each i E No- Thus, it remains to show the measurability of (dom 01 + R. ((),,P))(G (22, (22)P)) + [| - b|| - =1ll. Since
the set Bb. For this, introduce the function u is measurable, and the norm is continuous, we have that 9b is measurable. With this, we can write the set Ba. as:
By {90(2("), p, (1+1) p) < <0}
{ig o (Ie, id, T id) 1) (p, (z19) s 0}
(gr (Te, id, Mt41, id) 1) 1 (-00,
where v 99 No + No x 9))2 is the diagonal inclusion (2) 22) + ((22, 21), (1), which again is measurable.
Thus, Bb, measurable for each E No and b Q_ which concludes the proof.
F. Proof of Lemma 7.4
Proof. By definition of the product o-algebra on I x No, it suffices to show that Abound is measurable. Then, as it suffices to consider e E [0, oo) Q =: Q+, one can write Abound as:
Abound
U Un ((2()) E g. : ||x00 sc]
oEQu SENo
Co.
Thus, by the properties of a o-algebra, it suffices to show that the sets Ca, with E Q- and t No are measurable. By defining g(z) = ||=||, this follows directly from the identity Ca,t = (go [0,c].
17

---

A Generalization Result for Convergence in Learning-to-Opiimizee
G. Architecture of the Algorithm for Quadratic Problems
40
Denv2e (3, 30, bbian=?)
Corvint (30, 30, 1, bibis-
Convid c5n, 20, hiaa-))
Conv2s 10, b,baas-
Cosv2d 1, biaco
Conv2a 10, w.bb,,bise
Re23
Seelil
200)
4
2(0
20 gl0 . 201)
Linerr (4, 36, bia-=1)
Linear bino-r)
Li'narr hia--f)
Linear' 123, 13, F)
Linest 11 0, bibe-r
Linear blasiii
3et0
3et:
7e40
2000
Figure 3. Update step A: The directions d di and d @ d are inserted as different channels into the Conv2d-block, which
performs x "convolutions", that is, the algorithm acts coordinate-wise on the input. The scales (1) 84 get transformed separately by the fully-connected block.
The algorithmic update is adopted from Sucker & Ochs (2024) and consists of two blocks:
1) The first block consists of 1-convolutional layers with ReLU-activation functions and computes the update direction d(t). As features, use the normalized gradient d(" ve(2()))) .p) p) the normalized momentum term
(t-1) --00--00 Dip and their coordinate-wise product dtd @ d The normalization is done to stabilize the training.
2) The second block consists of linear layers with ReLu-activation functions and computes the step-size g(t), As features, we use the (logarithmically transformed) gradient norm 8 == log (1 + ||Vé(=(), .p)ll), the (logarithmically trans- formed) norm of the momentum term 22 log (1 + ||x(0) =((--)])), and the current and previous (logarithmically transformed) losses 83
Again, the logarithmic scaling is done to stabilize training. Here, the term " is added to map zero onto zero.
(t) == log (1 + ((2 ( p)), 54
(1) log (1
Importantly, we want to stress that the algorithmic update is not constrained in any way: the algorithm just predicts a direction and a step-size, and we do not enforce them to have any specific properties.
H. Training of the Algorithm
For training, we mainly use the procedure proposed (and described in detail) by Sucker et al. (2024); Sucker Ochs (2024). For completeness, we briefly summarize it here: In the outer loop, sample loss-function E(-, p) randomly from the training set. Then, in the inner loop, we train the algorithm on this loss-function with Erain given by
((((+)))))) (p,
Ltrai (l, (0)) 1[((=00 .p) > 0} ((z(0,p) p)
where C== =
((2 10 10-163 is the convergence set. That is, in each iteration the algorithm computes new point and observes the loss ftrain. which is used to update its hyperparameters, We run this procedure for 150 103 iterations. This yields hyperparameters (0) Hf, such that ((h()),) .) has good performance. However, typically, it is not descent method yet, that is, (= {A} } small, such that the PAC-bound would be useless. Therefore, employ the probabilistic constraining procedure proposed (and described in detail) by (Sucker et al., 2024) in progressive way; Starting from (!!), we try to find a sequence of hyperparameters (1),, _/2) such that
((P (A) < P(P.)) H= (A} < ((ee)))=aC) (A} <
18

---

A Generalization Result for Convergence in Learning-to-Optmmize
Remark H.1. The notation P(P.)) a (A] is entirely correct and is rather be understood suggestively, as the final prior distribution Py is yet be constructed. However, we think that it is easier to understand this way and therefore allow for this inaccuracy.
For this, test the probabilistic constraint every 1000 iterations, that is: Given h(),, train the algorithm (as before) for another 1000 iterations, which yields candidate ((++1), If (( {A} < P ((.)))= [A), we accept 1a(++1) = f, otherwise we reject it and start again from h60, This finally yields some hyperparameters ho that have a good performance and such that (- {A] is large enough (here: about 90%). Then, starting from /o. we construct the actual discrete prior distribution 1/ over points hi,..., Angammii E H. by a sampling procedure. Finally, we perform the (closed-form) PAC-Bayesian optimization step, which yields the posterior pa E (IPH. In the end, for simplicity, we set the hyperparameters
h arg max P² p²(he)-
(= nsample
For the construction of the prior, we use Nprior 500 functions, for the probabilistic constraint we use Nyal 500 functions, and for the PAC-Bayesian optimization step we use Ntrain 250 functions, all of which are sampled i.i.d, that is, the data are independent of each other.
Remark H.2. Training the algorithm to yield a good performance is comparably easy. On the other hand, turning into an algorithm, such that (P (A) is large enough (in our case: descent method without enforcing it geometrically) is challenging and, unfortunately, not guaranteed to work. Nevertheless, it is key to get meaningful guarantee.
I. Architecture of the Algorithm for Training the Neural Network
20)
Lineer 150, 20,200000000 bise-t:
Convaaa 14, 1, biso-T F)
Convite cht, 20, 1, blee-T)
Coceu 22c 20 1 17
Convee 1200 1. toleee m
80
Linear (20, 10, biaa-
Lacoos (6 30
We vi
Reaa
(
(1+1)
Linear (36,
023
644
u0 m
G
d
Figure 4. Algorithmic update for training the neural network: Based the given six features, the first block computes four weights Wi...,, W4, which are used to perform a weighting of the different directions g @ d di" dh"), @ de") which are used in the second block. This second block consists of Ix Ixl-convolttional blocks, which compute update direction d(t) Then, we update [(++1) = (0) + d /V.
The algorithmic update is adopted from Sucker & Ochs (2024) and consists of two blocks:
1) The first block consists of linear layers with Rel.U-activation functions and computes four weights Wi.-.. Wyg As features, we use the (logarithmically transformed) gradient norm 8 := log (1 + |[V p)ll), the (logarithmically transformed) norm of the momentum term 5 == log (1 || (t-1) []), the difference between the current and previous loss 53g
(t) : {(2(1,, ,p) ((=(t>1), p). the scalar product between the (normalized) gradient and the (normalized)
momentum term 84 the maximal absolute value of the coordinates of the gradient (8) and the iteration counter t.
(t)
2) The second block consists of 1 x 1-convolutional layers with ReLU-activation functions and computes the update v .p)
direction a(t) As features, we use the normalized gradient a(t) : [[ pill * the normalized momentum term 0 ((-1) d |x(0_ D7I and their "preconditioned" versions g C afO) and m @ (()) where the weights m, d E RRd are learned, too.
Again, we want to stress that the algorithmic update is not constrained in any way: the algorithm just predicts a direction, and we do not enforce them to have any specific properties.
19


Reviews:
[{"review_id": "usfHwDTHKy", "reviewer": "Reviewer_vfny", "summary": "This paper presents a probabilistic framework to establish convergence guarantees for L2O algorithms, addressing the challenge that conventional geometric arguments for convergence do not readily apply to learned optimizers. The key contribution is a generalization result that combines PAC-Bayesian learning theory with variational analysis, specifically leveraging the KL inequality, to show that L2O algorithms converge to critical points with high probability. The authors develop a novel proof strategy that translates worst-case convergence analysis into a probabilistic setting, removing the need for restrictive safeguard mechanisms in algorithm design. Experimental results on quadratic optimization problems and neural network training demonstrate that the learned optimizers outperform traditional methods such as heavy-ball acceleration and Adam, while the PAC-Bayesian framework provides nontrivial guarantees on their generalization.\n\n## update after rebuttal\nThe author's response has persuaded me that this is strong work, so I'm increasing my score from 3 to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to provide this detailed feedback.\nWe shortly want to comment on the stated weaknesses: \n\nWe agree that such convergence guarantees are highly desirable, but we also think that\nthis is asking for too much: We are considering an abstract algorithm (think of a neural network) and an\nabstract loss function, and such an analysis is typically performed in a problemspecific\nway, even for conventional optimization algorithms. Thus, while we could\nprovide hypothetical examples that explain our contributions for a concrete setting,\nwe do not think that we can prove the convergence of such a learned\nmethod in general, also because it additionally is influenced by the used training\nprocedure. Further, if we could perform such an analysis and provide the\ncorresponding guarantees, we might be able to do the same for the test data,\nsuch that we would not even need the generalization anymore. However, the\nkey idea is exactly that we acknowledge the fact that we are often not able to perform\nsuch an analysis, in which case we have to rely on observations during training. And for these cases we can apply our generalization result,\nwhich is widely applicable, exactly because our setting is so abstract. \\\nFurthermore, how to train optimization algorithms\nso that they do satisfy these convergence-ensuring properties for most of the\ntraining data is actually also part of future research. \\\nLastly, we want to stress again that a large part of our contribution is also the *proof-strategy* which,\nafter it has been established, can be applied or adapted quite easily to several\ndifferent applications. Here, we want to emphasize one thing, because the problem is very subtle: For many applications, convergence of the learned algorithm is a so-called asymptotic event and belongs to the tail-$\\sigma$ algebra, that is, by definition it is *practically impossible* to observe it directly. Thus, if we want to judge about it based on observations (like in L2O), we need to observe something that allows us to *deduce* it. And this is exactly what our strategy is exploiting.\n\nRegarding your claim that the presentation could be significantly improved:\nCould you please be a bit more concrete here? We are of course always interested\nin improving the clarity of our paper, but, like this, it is rather hard to see which\nparts should be restructured or presented differently, such that, for now, we would\nrather kindly disagree with this remark. For us, the paper has a clear inherent\nflow, which is the following:\n1) Start of the paper (introduction/motivation + related work)\n2) Presentation of main idea in a simplified way, so that readers can grasp it\nmore easily.\n3) Notation and background material, such that claims can be made rigorous.\n4) Recalling main idea and concretizing it for the setting of learning-to-optimize\n(lemmas preparing the main result + main result)\n5) Experiments", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not verify all the proofs in detail, but based on a high-level review, they appear to be reasonable.", "experimental_designs_or_analyses": "The experiments appear to be sound.", "relation_to_broader_scientific_literature": "L2O has been widely studied as a means of leveraging machine learning to design optimization algorithms that adapt to specific problem structures, with earlier works focusing on empirical performance but lacking rigorous convergence guarantees. This paper advances the field by introducing a probabilistic framework that integrates PAC-Bayesian generalization theory with variational analysis to provide convergence guarantees in generalization. Prior works on PAC-Bayesian learning have established generalization bounds for learning-based methods, and KL-based convergence analysis has been used in traditional optimization, but their combination in the context of L2O is novel. Additionally, the paper addresses limitations of safeguard-based approaches, which constrain learned optimizers to fit classical convergence analyses, by formulating a more flexible probabilistic guarantee.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths\n\n1. The paper tackles a really interesting and important problem—the convergence of L2O. This is an open question that very few papers have addressed, despite L2O’s growing popularity. Most work in this area has focused on empirical performance without theoretical guarantees, so I appreciate that this paper makes an effort to analyze convergence, which is a crucial missing piece in the field.  \n\n2. I also like the core idea of the paper—moving away from traditional geometric analysis, which often requires the learned optimizer to have specific properties that may not hold in practice. Since L2O relies on neural networks, their outputs are difficult to control, and enforcing geometric constraints can limit their flexibility. Instead, this paper uses a PAC-Bayesian framework combined with the KL inequality, which provides a more natural way to study convergence without imposing artificial restrictions. This makes the approach both theoretically interesting and practically relevant.\n\nWeaknesses\n\n1. One key assumption in this paper is that L2O converges on the training set, and the main focus is on whether this convergence generalizes to new optimization problems. While this assumption is reasonable and intuitive, it is itself an open question that remains unaddressed. The paper does not explore whether or under what conditions L2O is actually guaranteed to converge during training, which makes the overall analysis feel somewhat incomplete. I understand that this is beyond the scope of the paper, as the focus is on generalization rather than training dynamics, but leaving this assumption undiscussed does create some discomfort. This issue is particularly important because L2O training is not a trivial process. The convergence of NN training itself is already a complex and open problem, with theoretical frameworks like NTK providing some insights but requiring unrealistic infinite-width assumptions. L2O, being an even more complex NN that integrates both the optimization process and neural network prediction, presents a significantly harder convergence problem than standard architectures like MLPs, which are already difficult to analyze. Given this, the absence of a solid consensus on the convergence of L2O during training greatly weakens confidence in the overall framework presented in the paper.\n\n2. The presentation of the paper could be significantly improved. The structure feels disorganized, making it harder to follow the key ideas and contributions. Some sections could be better structured to improve clarity, and certain explanations—especially in the theoretical parts—could be made more intuitive. A clearer organization would help readers grasp the core insights more effectively.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "N.A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0r4iw3PC61", "reviewer": "Reviewer_FnHp", "summary": "While learning-to-optimize has shown to be a powerful paradigm to enhance the efficiency of the optimisation phase for problems similar to the one encountered during training, it is unsure how such a trained algorithm will behave on unseen problems with different internal structure. This work tackles this issue by proposing a novel PAC-Bayes generalization bound for the learning-to-optimize problem when the considered learning algorithm possesses a Markovian structure and that the (potentially non-smooth, non-convex) loss satisfies the Kurdyka-Lojasiewicz condition.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Also here, we would like to thank the reviewer for taking the time to provide this feedback. We are glad that you considered the proof-strategy as “well-explained”, because it is one of our main contributions.\n\nRegarding your question whether we could expand a bit more on the comparison between our results and those of Sucker&Ochs (2024): First, while Sucker&Ochs state Theorem 42, they only use it for a small remark, where they explain that this result can be used to bound a function r that is used to estimate something like a linear rate of convergence. If one would perform a similar analysis\nas we have done here for the case that a) the loss function has a unique minimizer and b) the algorithm does indeed converge with a linear rate, this could be used to deduce convergence, which, however, Sucker&Ochs also left completely unaddressed. \\\nFurthermore, this setting would be a very specific case in which you can get convergence by just observing a certain function-value. In general, however, this is not the case, due to the following subtle problem: Convergence is an asymptotic notion, such that it belongs to the so-called tail-$\\sigma$-algebra, that is, in practice it is *inherently non-observable*. Thus, if we want to judge about convergence from observations during training, we need to switch the perspective and try to observe properties, that allow to *deduce* convergence again. And this is what our proof-strategy accomplishes. Although this difference is very subtle, it is still crucial. For L2O this applies in particular to the non-smooth and non-convex case, because the (sub-)gradient does not necessarily say anything about the distance to a critical point. \\ \nAdditionally, we would like to point out that part of our contribution is also to show how we can actually combine results from conventional optimization theory with generalization results, such that it can be adapted to other cases quite easily. \n\nRegarding the follow-up question of whether we could state such a theorem in the appendix to highlight the originality of our contribution: What exactly do you mean by “such a theorem”? Theorem 6.3 is the theorem by Sucker&Ochs.\n\nRegarding the discussion of the prior: The prior is highly important, because the generalization bound is more tight, if the posterior stays close to prior (KL-term is smaller). On the other hand, this means that the prior should already yield some reasonable\nperformance. Therefore, a well-known remedy is that one typically has a two-step learning process: First, the prior gets optimized to yield a reasonably good performance and then the posterior gets chosen, which provides the guarantee.\nWe did not comment on it, because it is not the actual contribution of our paper and the approach is already well-known.\n\nRegarding your comment that the reference (Theorem 42, Sucker& Ochs 2024) for Theorem 6.3 seems to be wrong: We think it is correct. Maybe it is confusing, because Sucker&Ochs are again referencing to Catoni (2007). However, we think that this is just to acknowledge that their result turns out to be basically the same as the one by Catoni (who considered Bernoulli random variables).\n\nRegarding your question for Theorem 7.6: In our case, the conditional probability is simply an indicator-function (note that in your comment there is a $P_n$ missing!), because the algorithm is deterministic and everything else is given from the data. So it turns into an empirical mean over indicator functions. However, we did state it in this more general version, because the proof-idea could also be used for stochastic algorithms, in which case one would have to estimate the probability, for example over several runs of the algorithm.", "claims_and_evidence": "This is a truly solid mathematical paper, with a well-explained and convincing proof-strategy. I read the proof of measurability of Section 7 which are well-written, sound and rigorous.", "methods_and_evaluation_criteria": "I did not check the experimental protocol, however the nature of the problem (quadratic or small neural networks) look reasonable.", "theoretical_claims": "Once the setup of measurable events is well-posed and proof of the main-results are a quite straightforward combination of results of Catoni 2007 and Attouch et al. 2013.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "Could the authors expand a bit more on the comparison between your results and those of Sucker&Ochs 2024, which looks quite close according to what you say. Would it be possible to state such a theorem in the appendix to highlight the originality of your contribution?", "essential_references_not_discussed": "I do not know enough Sucker & Ochs 2024 and the associated references to be aware of the SOTA in the links between PAC-Bayes and learning-to-optimize.", "other_strengths_and_weaknesses": "None, this is a good theoretical paper involving an innovative use of PAC-Bayes. However, I may overestimate the novelty of those techniques as I was not aware of Sucker&Ochs 2024", "other_comments_or_suggestions": "None.", "questions_for_authors": "- Would it be possible to discuss more the influence of the prior in Theorem 6.3 and 7.6?\n- The reference (Theorem 42, Sucker&Ochs 2024) for theorem 6.3 does not seem correct, can you update it?\n- In Theorem 7.6 is it possible to implement the sum $\\frac{1}{N}\\sum_{i=1}^N \\mathbb{P}\\_{(P,\\xi)| H}(A^c)$ can you expand on it?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UHuKRz2F0I", "reviewer": "Reviewer_zRws", "summary": "Learn-to-optimize has been a popular research topic in recent years.\nHowever, many theoretical guarantees are still lacking.\nThis paper develops a probabilistic framework that resembles\nclassical optimization and allows for transferring geometric\narguments into learn-to-optimize. The paper establishes\na generalization result for very general loss functions and shows\nconvergence of learned optimization algorithm to critical points\nwith high probability. Numerical experiments\nare provided for solving a quadratic problem and training neural networks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for giving this feedback, and we would like to take the opportunity to shortly comment on the weaknesses and to answer the questions.\n\nRegarding your first posed weakness: It is true that, on an abstract level, in the end the result follows by combining Theorems 6.3 and 6.5. However, we think that it is still a significant step, because:\n1) There is a very subtle problem with convergence results: In general, convergence is an asymptotic notion, that is, it belongs to the so-called tail-$\\sigma$-algebra and therefore is *simply not observable* in practice. Thus, if we want to judge about convergence based on observations during training, we need to observe properties that allow to *deduce* convergence again. And this is accomplished by our new proof-strategy. \n 2) You have to know both results, which are both rather abstract and advanced in their respective fields (PAC-Bayes and non-smooth non-convex optimization), and you have to combine them in the correct way, that is, you have to see that all resulting properties have to be phrased as sets in the space of trajectories. Since we have done it now here, it will also be comparably easy to adapt for follow-up work. \n4) You have to do the proofs, which are by no means trivial in this abstract setting dealing with\nspaces of sequences. \nLastly, we want to point out that this proof-strategy is actually also part of our contribution. It bridges the gap between conventional optimization theory and generalization bounds. And finding a completely new proof-strategy is often harder than adapting an existing one to a new problem.\n\nRegarding your second posed weakness: We do not fully understand why you regard this as a weakness of our paper? Could you elaborate on that?\n\nRegarding your comments:\n1) The function $\\Phi_a$ is related to the log-Laplace transform of a Bernoulli random variable (see Catoni (2007)). This in turn is related to the moment-generating function, which can be used to characterize how the random variables concentrates. And this is commonly used to get generalization\nresults. $\\Phi_a$ and $\\Phi_a^{-1}$ a were both introduced like this by Catoni (2007). \\\n2) Thanks for the hint! We will check and update the references. \\\n3) “ult.” is an abbreviation for “ultimately” and refers to the fact that the sequences only ultimately have to lie in the ball with radius ϵ, that is, asymptotically (this is why we have this union/intersection over all iterates in the definition). This notation is used in analogy to the notation from probability theory (for example, see Kallenberg).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The paper seems to be correct though I didn't check the proofs in details.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "Learn-to-optimize has been a popular research topic in recent years.\nHowever, many theoretical guarantees are still lacking.\nThis paper develops a probabilistic framework that resembles\nclassical optimization and allows for transferring geometric\narguments into learn-to-optimize to fill in this gap.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "Strengths\n\n(1) The paper is well-written. \n\n(2) The theory is accompanied by experiments.\n\n(3) The theory is rigorously derived by paying a lot of attention to the technical details.\nFor example, the paper devotes an entire Section 7.1. to show measurability condition\nholds in order to apply some existing results. A measurability condition is often taken\nas granted. But the paper digs deep into checking this technical condition, and provides\na very details and non-trivial proof in the Appendix.\n\nWeaknesses\n\n(1) The proofs of the main results seem to be direct consequence by applying\nTheorem 6.3. and Theorem 6.5 that are both available from the recent literature.\nThis makes the paper seem to be an application built upon the very recent literature\nand makes the contributions less significant.\n\n(2) The paper mentions four weaknesses in the conclusion section, which is fair and honest. \nI think some of the weaknesses seem to be inherent. But some might be overcome which\ncan be left as future research directions.", "other_comments_or_suggestions": "(1) In Theorem 6.3. and later Theorem 7.6., $\\Phi_{a}^{-1}(p):=\\frac{1-\\exp(-ap)}{1-\\exp(-a)}$ plays a central role.\nIt would be nice if you can provide some intuition explanations what this function $\\Phi_{a}^{-1}(p)$\nis about and where it comes from.\n\n(2) In the references, please be more consistent. For example, In Langford and Caruana, the booktitle is capitalized,\nbut not in Langford and Shawe-Taylor. In addition, the book name by Nesterov should be capitalized.\n\n(3) In the proof of Lemma 7.1., you wrote $B_{\\varepsilon}(p,z)$ ult. What is ult.?", "questions_for_authors": "N.A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ah8ZjzZc8y", "reviewer": "Reviewer_685S", "summary": "This paper proposes a new method for analyzing the generalization ability of learning to optimize (L2O). The authors aim to formulate the convergence of L2O to unseen data as a random event measured by a posterior distribution of neural network's (NN) parameters. By assuming training ensures that the L2O generates a perfect convergence sequence with fast convergence and bounds on solutions, the authors bound the random event's probability by the probability of the convergence event on training data and the KL-divergence between the posterior and prior distributions of NN's parameters before and after training. Experimental results on synthetic test data demonstrate its generalization ability.\n\n## update after rebuttal\nI increase my final recommendation (from 2 to 4) due to the following reason:\n1. This paper proposes a novel probabilistic perspective to demonstrate the generalization ability of L2O.\n2. Although the proposed method imposes some strict conditions on training, the scheme shows that generalization ability can be guaranteed through well-designed training. The success of LLM seems to prove this to some extent.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to provide this feedback, even it was unfortunately rather negative.\n\nRegarding the claim that the paper is hard to follow and that most technical details are not clearly introduced: \n1) Could you please be more specific here? Otherwise, we cannot improve the paper.\n2) In principle, we agree with you that our paper is not straightforward. However, we think that this is rather due to the fact that it combines many advanced and abstract concepts (conditional distributions over the space of trajectories). This is why we have explained our main idea in a separate section, such that it does not get obscured by the technical details. On the other hand, we kindly disagree with the fact that we did not introduce the technical details: We devoted half a page for the notation, and another 1.5 pages just to explain the setup. Besides that, we have provided basically all other needed notions in the appendix or defined them in the text.\n\nRegarding methods, evaluation criteria and the experiments: \n1) We do not claim that training the algorithm in such a way that it satisfies the properties of our theorem is actually easy. In fact, we explained in the conclusion that there are cases where it is hard. Since our setting is very abstract and applies to many optimization algorithms, there will probably always be cases where training is hard, and future research should address how to make this simpler. \n2) We also train a neural network, that is, a non-smooth non-convex optimization problem. \n3) While it is true that the results are only a bit better than Adam, this does not apply to the other experiment. Additionally, the main contribution of this paper are not the experiments; they are just to showcase the validity of our theoretical claims, that is, the generalization and thus convergence of the methods.\n\nRegarding your posed weakness: We agree that there are limitations to the PAC-Bayesian approach. However, these are well-known and people have come up with ways how to circumvent them, for example data-dependent priors. We did not comment on it, because it is well-known and not the actual scope of our paper. \\\nWe partly agree and partly disagree with the claim that the used conditions are too strict:\n1) Since these conditions are based on the theorem due to Attouch et al., you basically just claim that this theorem uses unreasonably restrictive assumptions. Additionally, please note that our proof-strategy can be combined with different theorems with potentially milder assumptions!\n2) It is true that Lemmas 7.2 and 7.3 are related to the convergence rate of the algorithm. However, most of the time a faster convergence of the learned algorithm is the only reason why we use learning-to-optimize. Thus, claiming that fast convergence is problematic seems not appropriate. \n3) We agree that the boundedness condition is problematic. However, this is a common problem also for many conventional optimization algorithms, that is, even the convergence proofs of many conventional optimization algorithms rely on boundedness, such that we do not expect to solve it in this more difficult setting here. \n4) We might be mistaken, but it feels like there is a certain confusion: You claim that “These conditions are more than the empirical convergence of training but also additionally require a specific shape of sequences generated by L2O, which may be hard to satisfy in practice.”. Please note that there is a subtle yet decisive problem: *Often you simply cannot observe convergence empirically.* This is due to the fact that convergence is an asymptotic notion and therefore, by definition, not observable in practice. Thus, if we want to judge about it from observations, we need to change the perspective and try to observe properties (the \"specific shape\" of the trajectory) that allow for *deducing* convergence. And this is accomplished by our theorem.\n\nWe would like to point out again that, while these properties are used in our main theorem, a large part of our contribution is actually the *proof-strategy*, which allows to derive similar theorems under different assumptions.\n\nRegarding your questions:\n1) E.g, semi-algebraic functions satisfy the KL-inequality. These are “functions whose epigraph can be written as a finite union of sets, each defined by finitely many polynomial inequalities”, which is a very large class of functions. These are the “prototypical nonpathological functions\nin nonsmooth optimization” (Drusvyatskiy et al., ”Curves of descent”). Even more generally, functions that are definable in an o-minimal structure or that are tame do satisfy the KL-inequality (for example, see the paper by Attouch et al.). \n2) We do not claim that training necessarily ensures these conditions. Actually,sometimes it is hard, which is why future research should solve this. Anyways, one could try an explicit optimization of the parameters a and b.", "claims_and_evidence": "No. This paper is quite hard to follow. Most technical details are not clearly introduced.", "methods_and_evaluation_criteria": "No. The optimization problem (i.e., quadratic programming) in the experiment is too simple, which is insufficient to demonstrate that critical condition that training can be easily achieved. For example, non-convex and large-scale optimization problems, e.g., interference reduction problems in wireless communication, are more challenging and harder to converge even in training.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes. The performance of the proposed method is a little better than Adam's, which may be much worse than other state-of-the-art, e.g., Math-L2O ICML 2023.", "relation_to_broader_scientific_literature": "This paper aims to give a general formulation of the generalization of learning-to-optimize with a probabilistic method. The method is related to the PAC-Bayesian learning theory and the paper Sucker & Ochs (2024). The method is also related to the generalization of neural networks, which is a hot topic in the field of machine learning.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:\n1. This paper proposes a new paradigm for generalization demonstration of learning to optimize (L2O). The generalization is formulated as the random event of L2O's convergence on unseen data. The ability of generalization is measured by the posterior probability of convergence. Moreover, the probability is upper bound by the convergence of training and the KL divergence between posterior and prior distributions after and before training. \n\nWeakness:\n1. The effectiveness of the proposed method is limited. First, the main theorem, i.e., theorem 7.6 is loose, where the KL-divergence term illustrates the differences in the parameter distribution after and before training, which will be large unless training leads to little change from random initialization. Second, the conditions in lemmas 7.2-7.4 that the theorem relies on are too strict. For example, lemmas 7.2 and 7.3 require the trained L2O to converge fast and lemma 7.4 requires the solution generated by L2O to be bounded by a constant. These conditions are more than the empirical convergence of training but also additionally require a specific shape of sequences generated by L2O, which may be hard to satisfy in practice.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Can you give some explanation for the claim that most functions satisfy KL inequality? \n2. Can you demonstrate how training ensures lemmas 7.2-7.4?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper brings a rare convergence guarantee analysis to the learning to optimized framework. This is achieved thanks to an innovative usage of the PAC-Bayesian theory (partly foreseen in recent work but yet unexploited) combined with non-convex optimization and stochastic processes literature.

The reviewers agreed that this is a strong mathematical paper, as summarized by Reviewer zRws:
> The theory is rigorously derived by paying a lot of attention to the technical details. For example, the paper devotes an entire [section] to show measurability condition holds in order to apply some existing results. A measurability condition is often taken as granted. But the paper digs deep into checking this technical condition, and provides a very details and non-trivial proof in the Appendix.

Despite being performed on simple problems, the provided experiments convincingly "showcase the validity of [the] theoretical claims".
Decision: Accept (oral)