acceptodds
Under review as a conference paper at ICLR 2027

Training with Certificates: Global Optimality Bounds for Neural Networks

Abstract

How much better could a neural network have been trained on the same data? A flat loss curve, a small gradient, or agreement across restarts does not provide a global bound on the improvement still possible. We develop Neural MERIT, a framework that returns a feasible neural network together with a certified interval enclosing the globally optimal empirical objective, so that bounds the remaining global suboptimality of the returned solution. The central idea is to approach the target training problem through a sequence of globally solved or certified surrogate problems , and to transport each surrogate's feasible solution and global lower information back to the fixed target. For squared-loss training, we show that exact surrogate minimizers along a straight continuation yield monotonically improving target objectives even for nonconvex neural classes whose global optimizer can change discontinuously. With globally valid directional evidence, the transported certificate obeys an exact quadratic identity; in particular, a zero-gap surrogate certificate at gives target certificate width . Inexact surrogate solves incur an explicit, vanishing allowance. For exact convex prediction formulations, both certificate endpoints tighten monotonically and meet at the target optimum. Globally solvable neural classes therefore provide bank-free Neural MERIT guarantees, while a Neural Basis Bank of previously certified surrogates can strengthen the same target interval through additional and cooperative evidence. Across 24 independently verified ReLU continuation paths, every final bank-free interval contracts below (median ); a 64-record basis bank certifies 18 of 24 targets to width before continuation begins. Exact finite-network and frozen-feature experiments further show how the certificate separates optimizer stasis from globally certified training quality.

Primary area:
optimization
Keywords:
global optimization, neural network training, global optimality certificates, nonconvex optimization, continuation methods, primal-dual optimization, convex neural networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hhcwOpenReview ↗
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 (Ck=(1−2−k)YC_k=(1-2^{-k})Y) can be transferred to the original problem with targets YY. 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 YY. 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 YY (e.g. 1-hot encoded labels) by a sequence of surrogate target Ck=(1−2−k)YC_k=(1-2^{-k})Y instead. I see that C=0C=0 might be easier, but is C=0.1YC=0.1Y 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 Ck=(1−2−k)YC_k=(1-2^{-k})Y. 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 YY. So why not simply use Pilanci & Ergen (2020)'s result and directly optimize for the targets YY?
Questions for authors

See Weaknesses.

Minor:

  • Since the method requires solving a sequence a problem {Ck}\{C_k\}: how much overhead do they pay compare with simply certifying YY directly?
3 comments
AuthorsOpenReview ↗

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.

  1. Global guarantees transferred between training problems.

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.

  1. When can stored certificates improve upon one another?

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)C(t)=C_0+t(Y-C_0), the latest source dual provides at least as strong a lower bound at YY 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=I2X=I_2, β=1\beta=1, and width N≥2N\geq 2. Take two certified source targets C1=(2,0)C_1=(2,0) and C2=(0,2)C_2=(0,2), with exact source duals ν1=(1,0)\nu_1=(1,0) and ν2=(0,1)\nu_2=(0,1).

For the new target Y=(2,2)Y=(2,2), each stored dual gives a lower bound of 3/23/2, while their average gives

DY(ν1+ν22)=74.D_Y\left(\frac{\nu_1+\nu_2}{2}\right)=\frac74.

On the primal side, each stored network gives target objective 7/27/2. Reoptimization over their combined activation patterns gives a feasible network with objective 33.

The resulting certificate width decreases from 22 to 5/45/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.0827510.082751 to 0.0049140.004914, an improvement by a factor of 16.8416.84 over independently selected stored endpoints.

  1. When is certificate reuse computationally valuable?

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 66, 66, 99, and 1111 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.

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 YY. So why not simply use Pilanci & Ergen (2020)'s result and directly optimize for the targets YY?"

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 YY. 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 XX, 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 YY, we can:

  1. Evaluate the stored dual solutions at YY to obtain valid global lower bounds.
  2. Optimize the objective for YY using the activation patterns retained from earlier problems. This is a smaller convex optimization problem when relatively few patterns are needed.
  3. 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 YY 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 U=FY(θ^)U=F_Y(\hat\theta). They do not, by themselves, establish how much better another feasible network could perform. A verified global lower bound LL establishes

0≤FY(θ^)−p⋆(Y)≤U−L.0\leq F_Y(\hat\theta)-p^\star(Y)\leq U-L.

This allows us to certify that no feasible network within the specified class can improve the empirical objective by more than U−LU-L, 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.

Reviewer_XMTzOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a framework for computing global optimality bound for neural network training. In particular, the authors aim to compute an upper and lower bound of the globally optimal empirical objectives p⋆(Y)p^\star(Y). The upper bound is directly from inferencing the trained model and calculating its accuracy. The lower bound is first derived on the surrogate problem p⋆(Ck)p^\star(C_k) and then transfers the resulting bound to p⋆(Y)p^\star(Y). The authors show that as source CkC_k approaches the target YY, the lower bound on the surrogate problem can approach the lower bound on the empirical objectives.

Critical strengths

None

Critical weaknesses

Overall, I found this paper extremely hard to read. In particular, the notations are not consistent across the paper, making the mathematical equation extremely difficult to understand. For instance, the author uses θ^k\hat\theta_k to denote feasible networks in equation 1 but switches to CC in the section 2.1. It is also not clear what does the subscript kk in θ^k\hat\theta_k mean as the author did not define what kk is. I also think the author should explain some technical terms used in the paper. For instance in line 106, the authors wrote “Transport uses infima; attainment is stated when needed.”, which is not clear to me which part in equation 2 do the author refer as “transport”.

Despite not being able to fully follow the mathematical derivation in the entire paper, I understand the underlying mechanism for constructing the lower bound on globally optimal empirical objectives p⋆(Y)p^\star(Y). The central idea is to derive a lower bound on the surrogate problem p⋆(Ck)p^\star(C_k) and then transfer the bound to p⋆(Y)p^\star(Y). The authors show that as source CkC_k approaches the target YY, the lower bound on the surrogate problem can approach the lower bound on the empirical objectives. The author provides a condition for which the lower bound is sharp.

For me, the critical weakness of the method proposed in this paper is that the surrogate problem is not necessarily easier than the target problem, and the method required globally solved the surrogate problem, which is extremely unrealistic.The proposed method is also not evaluated in the experiment section under realistic setting.

Questions for authors
  1. What happen when the surrogate problem p⋆(Ck)p^\star(C_k) cannot be globally solved?
  2. Under the scenario for which p⋆(Ck)p^\star(C_k) cannot be globally solved, can the proposed method still work by solving a convex relaxation of p⋆(Ck)p^\star(C_k)? In this case, would the proposed method to be better than just solving a convex relaxation of the original training problem p⋆(Y)p^\star(Y)?
4 comments
AuthorsOpenReview ↗

Global validity with inexact surrogate solutions

Thank you for the careful questions about exact surrogate optimization and convex relaxations. Both can be answered directly from the certificate construction.

  1. What happens when the source problem cannot be solved globally?

Consider the squared-loss family

FY(θ)=12∥z(θ)−Y∥2+R(θ),F_Y(\theta)=\frac12\|z(\theta)-Y\|^2+R(\theta),

where R(θ)≥0R(\theta)\geq 0.

Suppose we have a feasible source network and any certified global lower bound

0≤ℓC≤p⋆(C).0\leq\ell_C\leq p^\star(C).

This information suffices for Theorem 2.1.

For every feasible θ\theta, the triangle inequality in the augmented prediction and regularization space gives

\geq \sqrt{2F_C(\theta)}-\|Y-C\|.$$ Taking the infimum over all feasible networks and using the certified source lower bound yields $$p^\star(Y)\geq \frac12 \left[\sqrt{2\ell_C}-\|Y-C\|\right]_+^2.$$ The bound holds for any neural parameter class satisfying the assumptions, including nonconvex classes. A sound convex relaxation can supply $\ell_C$. The source optimizer may remain unknown. Theorem 3.1 develops a sharper certificate when globally valid support information is available. Equations (8) and (9) account for the remaining source certificate gap. 2. How does this compare with applying the relaxation directly to $Y$? A freshly optimized target relaxation can produce a stronger lower bound than evaluating stored source evidence at $Y$. The motivation for transporting certificates arises when related problems have already been solved or certified and that information can be reused for subsequent targets. The quality of the resulting interval depends on source accuracy and target proximity, both quantified in the paper. The computational value depends on the cost of obtaining and reusing the global information. 3. Scope and notation. Our experiments verify these guarantees in exact finite neural classes, regularized two-layer ReLU formulations, and a quantized neural head on frozen features. Section 4 also provides a deep-relaxation construction with globally valid lower evidence and feasible repair. Its practical behavior on larger networks remains an open experimental question. We will revise the notation so that $Y$ consistently denotes the fixed target values, $C_k$ the source targets, $k$ the continuation stage, and $\hat\theta_k$ the associated feasible network. We will also define certificate transport immediately after introducing the training objective. We appreciate the focus on the assumptions supporting global validity. The short derivation above will be incorporated into the revised exposition to make the role of inexact source solves clear.

I appreciate the rebuttal, however, I don’t think the rebuttal fully addresses my concern in the current manuscript. In particular, is the proposed method actually useful in practice? A surrogate problem is not necessarily easier than the target problem, and the paper and rebuttal does not provide practical scenarios that surrogate problem is a lot easier than target problem, for which the proposed method can be applied and achieve practical improvement over existing baseline. I would like to maintain my score.

Thank you for following up. Your request for a concrete application and a direct computational comparison is well taken. We have added such a comparison to the revised manuscript. There is also a broader motivation for certification that deserves greater emphasis.

  1. A practical setting for certificate reuse.

Consider a system that repeatedly trains related neural models, such as a prediction head operating on fixed features with updated supervision or teacher predictions. Earlier training problems may already have certified solutions. Their feasible networks, globally valid lower bounds, dual information, and activation structures can be retained and applied to subsequent targets.

The practical opportunity comes from the structure of the problems encountered by an application. Although the space of possible training instances is enormous, actual instances may concentrate in a much smaller family. Recommendation systems and language models exploit recurring statistical structure in their inputs and queries. For neural certification, related training problems can similarly share useful mathematical information.

Equation (18) establishes a quantitative connection between source coverage and certificate quality. The target interval width is bounded in terms of the distance to a stored source and the uncertainty in its certificate. A collection of accurately certified sources covering the relevant target family can consequently provide useful bounds for new problems.

This gives a natural setting for amortizing earlier global computations across subsequent queries.

  1. Direct computational comparison.

The revised Section 6, Table 3, and Appendix G.6 compare direct full-pattern optimization, cold Pattern Completion, and bank-assisted certification on 192 held-out regularized ReLU targets.

Every method achieved globally verified certificate width at most 10−310^{-3}.

With four stored source records, median online certification time decreased from 0.469 seconds for direct optimization to 0.301 seconds. Including source construction amortized over 64 queries per family, mean total cost was 0.454 seconds per query, compared with 0.479 seconds for direct certification.

The comparison also reports unfavorable cases. Larger banks increase the total computational cost, and the four-record method has a slower 90th-percentile time. These measurements establish a reproducible setting where reuse provides a computational benefit and show how that benefit depends on the workload.

The experiment concerns rank-two ReLU problems with 48 activation regions. The general theory applies under its stated global-evidence assumptions, while extending the demonstrated computational gains to larger architectures remains an important research direction.

  1. The value of certification beyond computational savings.

We believe this deserves particular emphasis when assessing the practical significance of the work.

A developer who has trained a neural network may need to establish that the resulting model was optimized adequately. A plateau in training loss, a small gradient, or agreement among multiple training runs cannot generally establish how much improvement remains possible within the prescribed architecture.

A globally valid interval

L≤p⋆(Y)≤U=FY(θ^)L\leq p^\star(Y)\leq U=F_Y(\hat\theta)

provides a quantitative answer. If U−L≤εU-L\leq\varepsilon, the returned network is globally ε\varepsilon-optimal for the empirical training objective. The developer can establish that no feasible alternative within the specified class would improve that objective by more than ε\varepsilon.

This is consequential for training due diligence and accountability. When a deployed model is subsequently questioned, developers may need to explain how training quality was assessed, why optimization was stopped, and what evidence supported those decisions. The training specification, certified bounds, returned model, and supporting verification records provide a mathematical account of the optimization quality established during development.

Such documentation can be valuable in internal assurance, external audits, regulatory examinations, and legal proceedings. It establishes a specific and independently verifiable fact about training quality, which can contribute to demonstrating due diligence.

The cost of obtaining that evidence may be substantial, and in some applications the assurance can warrant more computation than training itself. This is familiar in engineering, where verification and testing may require resources beyond those used to construct the underlying system.

The certificate concerns empirical optimization within the declared model class. It provides one component of a broader assurance process that must also address generalization, robustness, and deployment safety.

Neural MERIT develops mathematical tools for obtaining and strengthening this type of evidence across related training problems. The new computational experiments examine when previously certified information can also reduce the cost of producing it.

We appreciate your request for a concrete application and baseline comparison. We hope the revised experimental results, together with the role of certification in training assurance, provide a fuller basis for evaluating the contribution.

Reviewer_iABTOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper aims to tackle an important problem to train neural networks with certified global optimality guarantee. Their method, neural MERIT, starts their guarantee by using a certified training guarantee from a certain "C", and interpolate C (which is label / target in general) with the actual problem Y to obtain rigorous lower bound guarantee. The guarantees they have include two-layer neural networks where enumerating all hyperplane arrangement patterns (or "Pattern Completion" in their words) or approximating deeper network's lower bound by using deeper relaxations.

Critical strengths

The problem that they are trying to tackle is very important, and it is conveyed quite well in the introduction - we would understand whether the network has been trained to global optimality, because we need to know whether they are trained well enough, we need more training, or we need to change the training setup.

Critical weaknesses

The critical weakness is that it is very hard to understand the paper. First, for the theoretical discussions, the motivation for each theorem is not very well shown. For instance why do we care about interpolating C and Y when we obtain guarantees? Or, why do we assume that C has a guarantee and we use this guarantee for Y, a different problem? Second, certain terms are not well defined. For instance banks. Third, the algorithm 1 is hard to understand because there are a lot of jargon and it is mostly written in natural language, which makes the algorithm hard to understand.

Another main weakness is I think the guarantees from C comes from existing work, e.g. Pilanci& Ergen 2020, so it is hard to assess the theoretical contributions. Theorems in section 2 and 3 are too generic and falls below the bar of ICLR in my opinion.

Questions for authors
  1. What is the motivation for Figure 1? If we can find global lower bound guarantee for C, we can do the same for Y? In general I had a hard time understanding why we should find the guarantees of C0, C1, C2 ... and go close to Y where we can just find guarantee for Y at first, and why this leads to a tight upper/lower bound guarantee of p*(Y).

  2. Is the proposed method practical enough? For instance what is the time complexity? I believe it could be very large because we need "Pattern Completion"

7 comments
AuthorsOpenReview ↗

Motivation for certified continuation and reuse

Thank you for the careful reading and the specific questions about Figure 1, Algorithm 1, and the motivation for the theorems. We agree that the paper should bring the mathematical purpose of continuation into focus much earlier.

Consider a training problem with fixed inputs, architecture, constraints, and regularization. We want a feasible network together with a numerical guarantee on how much its empirical objective could still improve.

Suppose a related problem, with target values CC, has already been certified. Its feasible network provides an upper bound when evaluated at the desired target YY. Its global lower information can also be transferred to YY.

Theorem 3.1 quantifies the resulting uncertainty. When the source primal and support certificates close, the target certificate has width

UC(Y)−LC(Y)=12∥Y−C∥2.U_C(Y)-L_C(Y)=\frac12\|Y-C\|^2.

Thus the quality guarantee improves quadratically with the distance to a certified source.

Theorem 2.2 adds a useful property of the returned networks. Along a straight continuation toward YY, exact source minimizers yield monotonically improving target objectives for arbitrary nonconvex neural classes satisfying the stated assumptions. This holds even when the identity of the global minimizer changes. Together, these results provide a controlled path of target solutions and certificates.

Why use this construction when we can solve YY directly?

Direct certification is appropriate when its cost is acceptable. The opportunity developed in the paper arises when globally certified information is already available for related targets. Such information can be retained and reused across later training problems.

A Neural Basis Bank stores those earlier source networks and their certificates. Its contribution can exceed selecting the closest source. Appendix G.5 evaluates 192 held-out ReLU queries, where cooperative composition reduces median certificate width from 0.0827510.082751 to 0.0049140.004914 compared with selecting stored endpoints independently.

The computational cost depends on how the source certificates are obtained. Pattern Completion solves a restricted convex problem and checks omitted activation patterns globally. The number of patterns can grow combinatorially. Our experiments establish the guarantees in neural classes where the global checks are executable, and provide initial measurements of how stored patterns reduce subsequent work.

We will revise Figure 1 to show the source and target problems directly, introduce the bank through its stored contents, and simplify Algorithm 1 around the operations needed to produce a valid target interval.

Your questions identify the explanations readers need before encountering the technical results. We appreciate the opportunity to strengthen that part of the manuscript.

  1. I think me (and also reviewer XMTz) had the same concern that "if certifying for a certain target C is not particularly easier than certifying an arbitrary target Y, what is the point"? I don't understand the setup of the paper that assumes globally certified information is already available for some targets, and I don't get whether this is a realistic assumption or not. If the authors could elaborate more on this it would be nice.

  2. Also in the rebuttal response the authors said

"A Neural Basis Bank stores those earlier source networks and their certificates."

which I could not understand. What is source network, what do you mean by storing a certificate, and why is it called a neural basis bank?

  1. At last, the answer to the practical complexity of the algorithm is not answered. I understand it could grow combinatorically - can I interpret this as the complexity is exponential to input dimension, and the suggested algorithm only works for simple architecture?

If 1 and 3 are answered sufficiently I may raise my score. But with the current rebuttal I maintain my score.

Thank you for the follow-up and for identifying the questions that remain important to your assessment. We have strengthened the manuscript with a direct computational comparison. Let us address your three questions and elaborate on the motivation for certification.

  1. Where does certified source information come from?

Consider an application that repeatedly trains neural models with the same inputs, architecture, regularization, and constraints, while the targets change. Updated supervision, teacher predictions, and retraining prediction heads on fixed representations provide examples.

A source problem is one previously encountered training problem with target values CC. Its record contains a feasible network θC\theta_C, a globally valid lower bound on p⋆(C)p^\star(C), and the evidence needed to verify that bound. For the two-layer ReLU formulation, we additionally retain activation patterns and globally feasible dual vectors.

These records form the Neural Basis Bank. The term "basis" refers to reusable solution structures and dual information. No linear independence assumption is involved.

Sources can be certified analytically, through exact convex formulations, or using sound relaxations. For example, the zero-target problem has an analytic solution in our regularized ReLU setting. Other certificates can be accumulated as training problems are encountered.

  1. Why can reuse be valuable despite combinatorial complexity?

The space of possible training problems is enormous, but the problems encountered by a particular application often have substantial structure. Recommendation systems and language models succeed in part by exploiting statistical regularities across the inputs and queries they encounter. A related opportunity arises when successive neural training problems share inputs, architecture, and reusable solution structure.

Our theory provides a quantitative connection. Equation (18) bounds the interval obtained from stored source certificates:

\leq \frac12\min_i \left(\|Y-C_i\|+\sqrt{2\bar g_i}\right)^2,$$ where $\bar g_i$ is a verified source certificate gap. Thus, the usefulness of stored certificates depends on their accuracy and how well their targets cover the training problems subsequently encountered. A structured family may admit useful coverage with relatively few sources, even when the ambient space of possible problems is much larger. 3. What is the computational complexity? Pattern Completion can have exponential worst-case complexity. More precisely, for $n$ samples and data rank $r$, the number of homogeneous ReLU activation regions satisfies $$P\leq 2\sum_{j=0}^{r-1}\binom{n-1}{j}.$$ For fixed rank, this bound grows polynomially with the number of samples. When rank grows, the number of regions can increase exponentially. Global certification of general neural networks therefore remains computationally challenging. Our experiments investigate a controlled regime with 24 samples, rank-two inputs, and 48 activation regions. We have added a direct comparison in the revised Section 6, Table 3, and Appendix G.6, using 192 held-out ReLU targets. All 960 method-query runs reached globally verified certificate width $10^{-3}$. With four stored source records, median online certification time decreased from 0.469 seconds for direct full-pattern optimization to 0.301 seconds. Including source construction amortized over 64 queries per family, the corresponding mean costs were 0.479 and 0.454 seconds per query. Larger banks incurred greater overhead, and the four-record approach had a slower tail. The experiment therefore provides a concrete example of successful reuse together with its computational tradeoffs.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.