- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies how to certify how close a neural network solution is to global optimality. Building on existing convex neural-network formulations and duality results (Pilanci & Ergen, 2020), it shows how certificates for surrogate problems with modified targets () can be transferred to the original problem with targets . It also proposes a so called "Neural Basis Bank" that combines previously computed dual certificates to provide an improved lower bound and constructs an improved feasible network by pooling activation patterns.
Critical strengths
- The theoretical results appear technically correct.
- The neural basis-bank construction is potentially interesting, particularly the argument that combining stored activation patterns does not require increasing the network width (as long as the original network was sufficiently wide).
Critical weaknesses
Presentation It is extremely hard to assess what the stated contributions are. For instance "Global support evidence then sharpens the distance law" and "Global neural engines supply these certificates (Section 4), and basis banks strengthen them". This is a lot of terminology that has not been introduced and the statements make no specific claim. This is generally a problem throughout the text, which reads as highly AI generated, making it hard to read.
- A lot of undefined terminology: "bank-free", "source solve", "certified source engine"
- sentences like "inexact source solves change the recorded gaps, not this definition" are difficult to parse.
Relevance of contributions My main concern is that Pilanci & Ergen (2020) already establishes a certificate when solving for the target . So given that exact convex formulations and primal-dual optimality certificates for the ReLU networks already exist, does Neural MERIT bring any additional improved certificates or computational efficiency? There seem to be two extensions both of which I have issues with:
- Sequence of surrogates If I understand correctly, they replace solving the original problem with target (e.g. 1-hot encoded labels) by a sequence of surrogate target instead. I see that might be easier, but is any easier to solve than Y? Are we just replacing one difficult optimization problem with a sequence of equally difficult optimization problems?
- Neural Basis Bank Secondly, they propose a way of combining previously computed certificates and solution. I am not sure I see when this is useful:
- I think it should be possible to show that no convex combination of earlier dual solutions can improve the lower bound obtained from the closest . So the "neural basis bank" is only relevant if we wanted to reuse solutions we had to other problems.
- ... and even then, to find the new improved network the proposed solution needs to again optimize over . So why not simply use Pilanci & Ergen (2020)'s result and directly optimize for the targets ?
Questions for authors
See Weaknesses.
Minor:
- Since the method requires solving a sequence a problem : how much overhead do they pay compare with simply certifying directly?
3 comments
I do not see how this response is addressing any of my concerns. To give one example:
"We will incorporate the same-path result and the exact ReLU example into Section 5, bring the cross-target experiment into the main text, and clarify the computational accounting. These additions will help readers see both the mathematical value of certificate reuse and the conditions under which it can reduce subsequent computation."
This seems to be a very generic response that does not address the concrete question: "to find the new improved network the proposed solution needs to again optimize over . So why not simply use Pilanci & Ergen (2020)'s result and directly optimize for the targets ?"
Additionally there is more undefined vocabulary being used like "a single straight continuation" which makes it hard to understand what concern is even being addressed.
Thank you for clarifying your concern. The short answer is that we in fact do optimize over the new target . The potential computational benefit, however, comes from reusing information obtained while solving previous training problems.
For the regularized two-layer ReLU formulation, suppose we have already solved several training problems sharing the same input matrix , with different target vectors. We retain their globally feasible dual solutions and the ReLU activation patterns used by their optimal networks.
For a new target , we can:
- Evaluate the stored dual solutions at to obtain valid global lower bounds.
- Optimize the objective for using the activation patterns retained from earlier problems. This is a smaller convex optimization problem when relatively few patterns are needed.
- Check global dual feasibility over the full set of possible activation patterns. If additional patterns are needed, include them and repeat.
The final global check is essential because reusing patterns can reduce optimization work, but it does not eliminate the verification requirement.
Direct optimization instead solves the convex formulation for using the complete pattern set from the beginning. When this is inexpensive, direct optimization can be preferable from a computational cost viewpoint. We have added a matched computational comparison in Section 6, Table 3, and Appendix G.6 of the revised manuscript.
There is another important consideration when evaluating computational cost: the value of certification itself. A trained network and its achieved objective provide an upper bound . They do not, by themselves, establish how much better another feasible network could perform. A verified global lower bound establishes
This allows us to certify that no feasible network within the specified class can improve the empirical objective by more than , regardless of whether the training procedure stopped at a local minimum, a saddle point, or elsewhere.
Such assurance can justify substantial additional computation. A developer may need to document that training was carried out to a demonstrable standard, explain why optimization was stopped, and preserve evidence supporting those decisions. The model specification, achieved objective, certified bounds, and supporting verification records provide an auditable account of training quality. This can be valuable for internal due diligence, regulatory examinations, and legal proceedings. Direct globally certified optimization can provide the same assurance. Our contribution includes alternative ways to obtain and strengthen that evidence through previously certified problems, while potentially reducing its cost. The guarantee concerns global empirical optimization within the specified model class.
Certificate transfer and the value of cross-target reuse
Thank you for the thoughtful review. Your questions about direct target certification and the usefulness of combining stored certificates go to the central motivation of our work. We would like to address them through three contributions.
We build on the exact convex neural formulations of Pilanci and Ergen (2020), which provide one way to obtain the global information required by our framework. Other exact methods and sound relaxations can also supply the required information, under the respective assumptions of our theorems.
Theorems 2.1 and 3.1 establish how globally valid source information can certify a different training target. These results also apply to nonconvex neural classes when the required source evidence is available. Theorem 2.2 establishes a further property: along straight continuation, every selection of exact source minimizers yields a nonincreasing objective on the fixed target, even when global minimizers change discontinuously.
Together, these results provide a controlled progression of feasible target solutions and global quality guarantees using certified information from related problems.
Your observation about a single straight continuation is correct. In fact, we can establish a stronger result: for exact dual solutions along C(t)=C0+t(Y−C0), the latest source dual provides at least as strong a lower bound at Y as any convex combination of earlier source duals.
As you anticipated, the opportunity for cooperative improvement arises when stored certificates come from different training targets.
Consider the regularized two-layer ReLU problem (14) with X=I2, β=1, and width N≥2. Take two certified source targets C1=(2,0) and C2=(0,2), with exact source duals ν1=(1,0) and ν2=(0,1).
For the new target Y=(2,2), each stored dual gives a lower bound of 3/2, while their average gives
DY(2ν1+ν2)=47.
On the primal side, each stored network gives target objective 7/2. Reoptimization over their combined activation patterns gives a feasible network with objective 3.
The resulting certificate width decreases from 2 to 5/4. Both endpoints improve by combining previously certified neural information.
The larger experiment in Appendix G.5 examines this effect across 192 held-out ReLU queries. With 64 stored sources per family, cooperative composition reduces median interval width from 0.082751 to 0.004914, an improvement by a factor of 16.84 over independently selected stored endpoints.
For a single target with an inexpensive global solve, direct certification is a natural choice. Our interest is in families of related training problems, where the cost of earlier global computations can be shared across subsequent queries.
The Pattern Completion experiment in Appendix G.5 provides initial evidence of this opportunity. Four cold queries require 6, 6, 9, and 11 new pattern additions. With previously stored patterns, all four require zero additions. Target-side optimization and global verification still incur costs, and these must be included when assessing the computational advantage over repeated direct solves.
We will incorporate the same-path result and the exact ReLU example into Section 5, bring the cross-target experiment into the main text, and clarify the computational accounting. These additions will help readers see both the mathematical value of certificate reuse and the conditions under which it can reduce subsequent computation.
Thank you again for the careful assessment and for identifying the questions that deserve particular attention in the revision.