acceptodds
Under review as a conference paper at ICLR 2027

Max-Total-Flow Generalization Bounds for DAG-Structured ReLU Deep Neural Networks

Abstract

Understanding generalization in over-parameterized neural networks remains a fundamental challenge. While recent path-norm frameworks address general directed acyclic graph (DAG) networks with skip connections, branching, and merging, they require computing astronomically large path-norms that render generalization bounds vacuous in practice. In this study, a new perspective is proposed by interpreting Karush–Kuhn–Tucker (KKT) optimality conditions as a flow conservation law over the DAG. At a KKT point, the squared Frobenius norms of weight matrices define non-negative flows on edges that satisfy classical conservation equations at every interior node. Using flow decomposition, we prove that at every KKT point the total parameter norm is bounded in terms of the longest source-to-sink path length of the DAG and the regularization parameter . Combining this norm control with a held-out validation set and a change-of-measure argument under a Gaussian perturbation of the weights with noise level , we show that, with probability at least , the validation loss of the trained network exceeds its expected training loss by at most , for training and validation samples. The results cover binary and multi-class classification and regression, and extend to Leaky ReLU activations.

Primary area:
learning theory
Keywords:
Deep learning, Generalisation bound, Directed Acyclic Graphs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_f6TkOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies weight-decayed ReLU networks on general DAGs. Reading the KKT conditions of a lifted formulation as a flow, where each edge carries the regularized squared norm of its weights, the authors get ‖U(S)‖² ≤ (T_G+2)/λ with T_G the longest path. This is then combined with a holdout set and a Gaussian change-of-measure argument to obtain a generalization bound. Extensions to multi-class, regression and Leaky ReLU are included.

Critical strengths

The flow view of balancedness on a DAG is clean, and the path decomposition giving dependence only on T_G is nice. The authors are also upfront that their bound is not directly comparable to uniform bounds.

Critical weaknesses

My main concern is that the generalization result doesn't really depend on the main contribution. The left-hand side of Theorem 6 contains the validation loss, which is observable, and a bound on the population risk already follows from Hoeffding on the holdout set alone. The KKT norm bound only enters the second term, which concerns E_{S|W=w}[L̂(w,S)], a posterior-averaged training loss that can't be computed. It is also a generic argument that holds for any norm-bounded algorithm. The choice of ε is left open, and it matters: with λ = 5·10⁻⁴, T_G ≈ 100 and n = 50k, the term is about 2.3/ε, so it is below 1 only when the per-coordinate noise far exceeds the typical magnitude of individual weights.

The norm bound is weaker than a simple argument: since the zero network has objective value 1, any point with objective at most 1 satisfies ‖U‖² ≤ 2/λ. The flow analysis only helps at poor KKT points, and beyond the path decomposition it is mostly a DAG extension of known balancedness results (Du et al.; Kunin et al.).

The lifted problem is an MPCC, where MFCQ fails at every feasible point. Multipliers exist away from kinks, but at zero pre-activations, which weight decay produces for dead neurons, existence is unclear. This should be addressed. Finally, Table 2 reports path norms for models the authors say are outside their setting, and there are no experiments evaluating the proposed bound.

Questions for authors

What does the second term guarantee beyond the holdout bound? When do KKT points of the lifted problem exist, and does SGD reach them?

6 comments

The flow view of balancedness on a DAG is clean, and the path decomposition giving dependence only on T_G is nice. The authors are also upfront that their bound is not directly comparable to uniform bounds.

We thank the reviewer for their thoughtful and positive comments.

** W1

My main concern is that the generalization result doesn't really depend on the main contribution. […]

The concern combines four points, which we address in turn.

  • "A bound on the population risk already follows from Hoeffding on the holdout set alone." We agree, which is why the first term of Theorem 6 is standard concentration, of order 1/r1/\sqrt{r}. A holdout set certifies the risk of a given network, but it does not use the training data. It therefore says nothing about why a network trained on its training set also performs well on new data, or how this depends on the architecture, the regularization and the sample size. For this reason, bounds that explain generalization from the training side complement test-set bounds (Langford, 2005). The second term of Theorem 6 answers this question: the held-out loss exceeds the posterior-averaged training loss by at most a term determined only by TGT_G, λ\lambda, ϵ\epsilon and nn. This term needs a bound on ∣∣U(S)∣∣|| \mathcal{U}(S) || that holds for every training set, and our main contribution is to obtain such a bound from stationarity alone (see also our reply to W2).

  • "ES∣W=w[L^(w,S)]\mathbb{E}_{S|W=w}[\hat L(w,S)] cannot be computed." Every generalization bound relates an empirical quantity to an expected one that cannot be computed: in the classical gap, the expected quantity is the population risk. In Theorem 6, the empirical quantity is the validation loss, and the expected quantity is, in the reviewer's words, the posterior-averaged training loss: the training loss averaged over the training sets that are consistent with the trained weights. As in PAC-Bayesian and information-theoretic bounds, the guarantee concerns a loss averaged over a distribution rather than a single evaluation. Its relation to the observed training loss is discussed in our reply to Reviewer QfH1 (W1, Q1). For the sampled network, it follows from the change of measure already used in equations (21)–(23) of Appendix B.

  • "It is a generic argument that holds for any norm-bounded algorithm." Yes, and this is by design. The step from a norm bound to generalization is standard, and the new part is the norm bound itself. Standard weight-decay training is a norm-bounded algorithm at every KKT point of the regularized risk, whatever the optimizer, initialization or training trajectory. The radius depends on the architecture only through TGT_G and does not depend on nn or the data. No explicit norm constraint is imposed, and no radius has to be chosen in advance.

  • "The choice of ϵ\epsilon is left open." As with the posterior variance in PAC-Bayesian perturbation bounds (Neyshabur et al., 2018; Dziugaite and Roy, 2017), ϵ\epsilon trades the size of the bound against the distance between the perturbed and the trained network (lines 155–158; reply to Reviewer QfH1, W2). How much per-coordinate noise a trained network tolerates is a property of the trained network and can be measured on the training set; since the probability in Theorem 6 is over the validation set only, choosing ϵ\epsilon in this way keeps the guarantee valid. Our experiments on MNIST show that trained networks tolerate noise of the order of their typical weight. For a DAG with TG=10T_G=10 trained on 30,000 images, the root-mean-square weight is 0.0190.019. At ϵ=0.01\epsilon=0.01, about half of this value, the perturbed network agrees with the trained one on 98.298.2 % of the training points, and the agreement drops only once ϵ\epsilon exceeds the typical weight (9292% at ϵ=0.02\epsilon=0.02, 4646% at ϵ=0.05\epsilon=0.05; Table A in our reply to W3). Perturbation-based measures of this kind were found to be among the most predictive of generalization (Jiang et al., 2020). The focus of our analysis is how the bound depends on the architecture, the regularization and the sample size.

On a larger dataset, our bound is below 11 with ϵ\epsilon comparable to the typical weight, at a noise level the trained networks tolerate (Table F)

** W2

The norm bound is weaker than a simple argument: since the zero network has objective value 1, any point with objective at most 1 satisfies ∣∣U∣∣2≤2/λ||U||^2 \leq 2/\lambda. […]

We thank the reviewer for this observation. The argument is correct: at any weights whose regularized objective does not exceed that of the zero network, ∣∣U∣∣2≤2/λ||U||^2 \le 2/\lambda, which is smaller than (TG+2)/λ(T_G+2)/\lambda. The two bounds rest on different properties, and they combine.

  • Objective value versus stationarity. The simple argument uses the objective value: it applies when the returned weights beat the zero network on every training set, which is a property of the particular optimization run. Ours uses only stationarity and holds at every KKT point, whatever its objective value (lines 73–75). The difference is not limited to poor solutions. With weight decay, the zero network is itself a strict local minimizer as soon as every input–output path has at least three weight matrices, since the network output is then of higher order than the regularizer near zero. Training must therefore leave this basin, and the stationary point it reaches can fit the data and still have a larger objective. For example, for a chain of LL scalar weights trained on a single point, the network with all weights equal to one has margin one and is a local minimizer with objective λL/2\lambda L/2. When L>2/λL>2/\lambda, this exceeds the objective of the zero network, which is then the global minimizer. The simple argument does not apply to this solution, while ours does.

  • Combining the two bounds. At every KKT point, ∣∣U(S)∣∣2≤2/λ||U(S)||^2 \le 2/\lambda if its objective is at most that of the zero network, and ∣∣U(S)∣∣2≤(TG+2)/λ||U(S)||^2 \le (T_G+2)/\lambda otherwise. Our bound therefore covers exactly the case that the simple argument leaves open.

  • Distribution of the norm. The flow analysis describes how the norm is distributed over the graph, not only its size. At a point that beats the zero network, flow conservation in a chain forces every layer to carry the same flow.

  • Relation to Du et al. (2018) and Kunin et al. (2021). These works are only tangentially related to ours. They study the training trajectory: how the norms of the weights evolve in time under gradient flow, without regularization (Du et al., 2018, Theorem 2.1) or with weight decay and a finite learning rate (Kunin et al., 2021, Eq. (20)). We study the KKT conditions of the regularized training problem, which characterize the points that training returns, whatever the trajectory. The only common ingredient is the rescaling invariance of ReLU networks. Neither work bounds the total norm, uses the margin condition at the output layer, considers general DAGs, or derives a generalization bound. Moreover, on a DAG, balance at each node does not by itself bound the total norm. Our contribution is to read the KKT conditions as a flow on the DAG and to bound the total norm through the max-total-flow problem and its path decomposition, which gives a bound that depends only on TGT_G. We will revise lines 102–105 and 287–293 to make this distinction clearer.

We will add the simple argument and its combination with ours as a remark after equation (15).

** W3

The lifted problem is an MPCC, where MFCQ fails at every feasible point. […]

We thank the reviewer for raising this point.

Multipliers. We agree that MFCQ fails at every feasible point of the lifted problem, as for every MPCC (Ye & Zhu, 1995). The relevant notion is strong stationarity (Scheel & Scholtes, 2000), which is equivalent to the KKT conditions of the lifted problem (Flegel & Kanzow, 2005). Under MPCC-LICQ, every local minimizer is strongly stationary (Scheel & Scholtes, 2000), and, as the reviewer notes, this condition can fail at zero pre-activations.

The flow identities do not need multipliers. They follow from the rescaling invariance of ReLU networks: scaling the incoming weights of a node by α>0\alpha>0 and its outgoing weights by 1/α1/\alpha leaves the network unchanged. At every Clarke-stationary point of the original problem, the component of a stationary subgradient along this rescaling direction vanishes, which gives flow conservation at each node; the same argument along the scaling of the output layer gives the bound at the sink. The argument needs only that the loss is locally Lipschitz, so it holds at any weights, including zero pre-activations, in the same way that Euler's identity holds for Clarke subgradients of homogeneous networks (Lyu & Li, 2020, Theorem B.2). Dead neurons are covered: a unit whose output is zero on every training point receives no gradient through its weights, so at a stationary point weight decay sets its incoming and outgoing weights to zero, and it carries no flow. We will state Theorems 6–8 for Clarke-stationary points and add this argument to Appendix D.

Table 2 and experiments. The pretrained models of Table 2 illustrate how large path norms become for widely used architectures, in the spirit of Table 3 of Gonon et al. (2024). They serve as motivation, not as an evaluation of our bound, and the revised Introduction states this scope (reply to Reviewer QfH1, W3). The new Section evaluates the bound on networks trained on MNIST (10 classes) that satisfy every assumption. We report all the results here, in Tables A–E (Parts 3b and 3c).

Setting. Every network satisfies all the assumptions of our analysis: each edge carries its own trainable weight matrix, included in the ℓ2\ell_2 penalty; there is a single source and a single sink; and there are no biases and no normalization layers. Our DAG is a DenseNet block (Huang et al., 2017) in which every node receives the outputs of all earlier nodes, so that it has 2TG−12^{T_G-1} input–output paths. We minimize the multi-class hinge loss with weight decay λ=0.01\lambda=0.01 by SGD, use the 10,000 test images as the validation set VV and δ=0.05\delta=0.05, with three runs per setting.

Reviewer_DXi5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies generalization for regularized DAG-structured ReLU networks at KKT points. It interprets squared weight norms as flows, bounds the total parameter norm using the longest path length, and derives a bound relating validation loss to conditional expected training loss.

Critical strengths
  1. The flow interpretation provides a clear structural connection between stationarity, regularization, and total parameter norm.
  2. The framework accommodates branching and merging in DAG architectures, with extensions to multi-class classification and regression.
Critical weaknesses
  1. Although Table 1 includes spectral-norm bounds, the additional advantage is insufficiently established, particularly when spectral norms are well controlled. Comparing simplified expressions with different target quantities does not establish improved tightness.
  2. The proposed bound is not numerically evaluated, leaving its practical informativeness unclear. Its reliance on exact KKT points and a restricted network and training setup further limits applicability.
  3. Although TGT_G has a clear architectural meaning, its relevance to actual generalization remains unclear. The paper does not demonstrate whether this quantity predicts observed generalization across architectures or provides useful guidance for architecture selection.
Questions for authors
  1. What advantage does the proposed analysis offer over spectral-norm bounds when spectral norms are controlled? Can this be demonstrated in a common setting?
  2. Can the authors provide a numerical example satisfying the assumptions where the bound is informative? How would the guarantee change for approximate KKT points reached in practice?
  3. Beyond its appearance in the bound, what evidence supports TGT_G as an informative measure of generalization? What practical conclusions can be drawn from its dependence?
8 comments

The flow interpretation provides a clear structural connection between stationarity, regularization, and total parameter norm.

The framework accommodates branching and merging in DAG architectures, with extensions to multi-class classification and regression.

We thank the reviewer for the appreciation of our work.

** W1

Although Table 1 includes spectral-norm bounds, the additional advantage is insufficiently established, particularly when spectral norms are well controlled. […]

We agree that Table 1 of the paper alone does not establish tightness, and it is not meant to: as stated in lines 161–167, the bounds concern different objects, and the table places our result in context rather than ranking the bounds. In the new experiments, all bounds are evaluated on the same trained networks; we summarize this comparison, including the case of controlled spectral norms, in our reply to Q1.

Our motivation is a different one. Bounds built on products of layer-wise norms have known limitations beyond their size:

  • Nagarajan and Kolter (2019) showed that, for SGD-trained networks, the norms entering spectrally-normalized bounds grow with the sample size. These bounds can therefore increase with nn while the test error decreases (lines 49–52). Our experiments show the same effect (reply to Q1).
  • In the large-scale study of Jiang et al. (2020), measures based on the product of spectral norms were even negatively correlated with the observed generalization. Perturbation-based (PAC-Bayesian and sharpness) measures were among the most predictive.
  • Spectral analyses extended to residual networks (He et al., 2020) still depend on the product of the norms of all weight matrices.

These observations motivate our design (lines 70–87):

  • Instead of controlling the whole hypothesis space through products of norms, we use weight decay, which is standard in practice.
  • We consider only the weights that training returns: KKT points of the regularized risk. There, the KKT conditions control the total norm additively, through the flows along the graph, and give ∣∣U(S)∣∣2≤(TG+2)/λ||\mathcal{U}(S) ||^2 \le (T_G+2)/\lambda independently of nn.
  • We then study the network in a Gaussian neighbourhood of these weights.

** W2

The proposed bound is not numerically evaluated, leaving its practical informativeness unclear. […]

We thank the reviewer for this comment.

Numerical evaluation. We now evaluate the bound on DAGs and feedforward networks trained on MNIST that satisfy every assumption (new Section 6). The results are summarized in our replies to Q1 and Q2.

Exact KKT points. The flow identities follow from the stationarity conditions together with the rescaling invariance of ReLU networks. They therefore hold at every Clarke-stationary point of the training objective, including points at ReLU kinks, and stochastic subgradient methods converge to such points (Davis et al., 2020). They also degrade gracefully at approximately stationary points, and the flows of our trained networks are nearly balanced (reply to Q2).

Setup. The restrictions on the network (ReLU activations, no biases, no normalization) are what make it positively homogeneous, the property on which the flow identities rest, and weight decay is the default when training ResNets and DenseNets. We discuss the scope of these assumptions in our reply to Reviewer QfH1 (W3).

** W3

Although TGT_G has a clear architectural meaning, its relevance to actual generalization remains unclear. […]

We thank the reviewer for this comment. We do not propose TGT_G as a stand-alone measure that predicts generalization. It is the architectural factor of our bound, and it plays the role that depth plays in existing bounds. Our experiments on MNIST support this role (reply to Q2). For DAGs with TGT_G from 3 to 20, the number of input–output paths grows from 4 to 524,288. Yet the total norm of the trained networks stays between 23.5 and 25.6 at every depth, far below (TG+2)/λ(T_G+2)/\lambda, and the observed generalization gap increases only slightly with depth, from 0.8 points on average for TG≤8T_G\le 8 to 1.0 point for TG≥9T_G\ge 9, while the number of paths is multiplied by more than 100,000. Over the same range, our bound grows as TG+2\sqrt{T_G+2}, from 12.5 to 26.2, while the DAG bound (6) of Gonon et al. (2024) grows from 270 to 901.

How a bound depends on depth is a central question in this literature:

  • the bound (5) of Neyshabur et al. (2015) grows exponentially with depth;
  • those of Bartlett et al. (2017) and Neyshabur et al. (2018), (2) and (3), grow polynomially;
  • Golowich et al. (2018), (4), reduce this to a square-root dependence;
  • Gonon et al. (2024), (6), extend the square-root dependence to DAGs, at the cost of the path norm.

For a DAG, "depth" can mean several things: the number of nodes, the number of edges, the number of paths, or the longest path. Our analysis identifies which of these matters under weight decay: the longest path. It enters because, at a KKT point, the total norm decomposes into flows along source-to-sink paths, and each source-to-sink path uses at most TGT_G edges, plus the input and output layers (lines 100–107).

What TGT_G conveys is therefore structural. The guarantee is unaffected by:

  • the width;
  • adding parallel branches;
  • adding skip or dense connections that do not lengthen the longest path.

Lengthening the longest path costs only a factor TG+2\sqrt{T_G+2}. Bounds based on the path norm behave differently: the path norm sums over all input–output paths, whose number grows rapidly with branching. We discuss the practical conclusions of this dependence in our reply to Q3.

** Q1

What advantage does the proposed analysis offer over spectral-norm bounds when spectral norms are controlled? […]

As explained in our reply to W1, our approach replaces products of norms with an additive control of the total norm at KKT points. This gives an advantage even when spectral norms are controlled:

  • Depth and width. For given λ\lambda and ϵ\epsilon, our complexity term depends on the architecture only through the longest path, as TG+2\sqrt{T_G+2}. It depends neither on the width, the number of parameters or the number of paths, nor on the sample size through the weight norms. By contrast, even when all spectral norms equal one, the bounds (2) and (3) keep a polynomial factor in depth. In their full form, they also contain sums over layers of norm ratios that grow with width and depth.
  • DAG structure. The bounds (2) and (3) are stated for chain networks. Our analysis handles branching and merging directly.

Common setting. Feedforward networks are the setting common to all these bounds: on them, the bounds for layered networks (2), (3) and (4) apply directly, as does the DAG bound (6). We trained feedforward networks on MNIST with TG=10T_G=10 and nn from 2,000 to 40,000 that satisfy every assumption, under weight decay, which keeps the layer norms controlled, and evaluated every bound on the same trained networks (new Section 5).

  • The bounds (4) and (6) stay above 24,000 at every nn.
  • For small training sets (n≤3,000n\le 3{,}000), the simplified form of (2) is smaller than our bound (62 against 87 at n=2,000n=2{,}000). From n=5,000n=5{,}000 on, ours is the smallest of all; at n=40,000n=40{,}000 it is 19.4, against 24.8 for (2) and 45.4 for (3).
  • As observed by Nagarajan and Kolter (2019), the product of the spectral norms of the trained networks grows with the sample size, from 2.8 at n=2,000n=2{,}000 to about 8 at n=20,000n=20{,}000. As a result, (2) and (3) increase from n=2,000n=2{,}000 to n=5,000n=5{,}000 (from 62 to 78 and from 100 to 125) while the validation error falls from 9.1%9.1\% to 6.8%6.8\%. Our bound depends on neither of these norms and decreases as 1/n1/\sqrt{n}, from 86.6 to 19.4.
  • These comparisons use the simplified forms of Table 1 of the paper for (2)–(4), which drop constants, log factors and the norm ratios of (2), all of which favour the existing bounds.

Table D. Feedforward networks (TG=10T_G=10): generalization-gap term of each bound on the same trained networks, mean over three runs; †^\daggersimplified form of Table 1 of the paper.

nnour boundBartlett et al. (2017)†^\daggerNeyshabur et al. (2018)†^\daggerGolowich et al. (2018)†^\daggerGonon et al. (2024)
2,00086.662.099.949,070272,966
3,00070.767.810948,782277,414
5,00054.878.012556,426302,464
10,00038.755.794.343,114225,960
20,00027.441.576.141,841211,095
30,00022.430.856.526,151129,257
40,00019.424.845.424,066117,905

On DAGs, where (6) is the only bound of Table 1 of the paper that covers both DAGs and multi-class outputs, our bound is 22 to 35 times smaller than (6) for every depth (TGT_G from 3 to 20) and every sample size. In every run, the trained norm stays 20 to 87 times below (TG+2)/λ(T_G+2)/\lambda.

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

The paper develops generalization bounds for DAG-structured ReLU networks trained with explicit weight decay. The main idea is to interpret the KKT conditions as a flow conservation law over the network graph: squared Frobenius norms of edge weights behave like non-negative flows, and flow decomposition then gives a bound on the total parameter norm in terms of the longest path in the DAG. This norm bound is combined with a Gaussian perturbation and change-of-measure argument to obtain generalization bounds for classification and regression.

Critical strengths

I found the flow interpretation quite interesting. Recasting balancedness of homogeneous networks as a network-flow problem is clean, and gives a simple dependence on the longest path rather than products of layer norms or path norms.

The analysis handles general DAGs rather than only chain networks, and the extensions to multi-class classification and regression are useful.

The paper is fairly transparent about the assumptions and also acknowledges that the results require exact KKT points and explicit regularization.

Critical weaknesses
  1. I am not convinced the main theorem is really a generalization bound in the usual sense. Theorem 1, and consequently Theorems 6-8, control L^(w,V)−ES∣W=w[L^(w,S)]\widehat L(w,V)-\mathbb E_{S\mid W=w}[\widehat L(w,S)]. This is not the gap between validation/test loss and the actual training loss of the learned model. The second quantity averages over training sets conditioned on a noisy version of the learned weights.

The discussion says that for small (\epsilon) this approaches the observed training loss, but I don't think this is true in general. For example, consider an algorithm that outputs exactly the same weights for every training set. Then WW is independent of SS, and even as ϵ→0\epsilon\to0, ES∣W=wL^(w,S)=L(w,P)\mathbb{E}_{S\mid W=w}\widehat L(w,S)=L(w,P), not the empirical loss on the particular training set that produced ww. More generally, small noise conditions on training sets producing similar weights, not on the actual observed training set.

This seems important because without a relation between this conditional expected loss and the realized training loss, it is unclear what the bound tells us about the generalization gap of the trained network.

  1. Relatedly, the role of the Gaussian perturbation makes the practical meaning of the bound unclear. As ϵ\epsilon becomes large, the second term in the bound goes to zero, but S∣W=wS\mid W=w approaches the unconditional training-set distribution. The result then essentially becomes ordinary validation-set concentration around population risk. For small ϵ\epsilon, the complexity term gets large and, as above, the conditional training loss does not necessarily become the observed training loss. I think the paper needs to explain more clearly where the useful regime of this tradeoff is and what quantity can actually be computed or bounded in practice.

  2. The applicability to modern DAG architectures is quite limited. The motivation is largely that path-norm bounds become enormous for architectures such as ResNets and DenseNets. But the theoretical setting assumes no biases, explicit ℓ2\ell_2 regularization of the trainable edges, a single source/sink, and hinge or squared loss. In particular, common parameter-free residual connections and normalization layers are outside the theory. The appendix explicitly notes that the TorchVision networks used to illustrate huge path norms do not satisfy the assumptions of the proposed bound. So there is a bit of a disconnect between the practical motivation and what the theorem currently covers.

  3. The exact KKT assumption is also quite strong. The argument requires training to return a KKT point of the lifted constrained ReLU problem. It is not clear to me how this relates to the approximate stationary points obtained by SGD in practice. Also, at ReLU kinks the complementarity formulation is degenerate and standard constraint qualifications may fail. Since the flow identities are derived directly from these KKT conditions, I think this point deserves more discussion.

  4. There is no numerical evaluation of the proposed bound itself. The paper shows that existing path-norm quantities can be astronomically large, but does not evaluate its own bound on trained networks satisfying the assumptions. It would be useful to show that the new bound is actually non-vacuous, and ideally compare it to trivial validation concentration and existing norm-based bounds. An experiment checking how closely the flow conservation identities hold near convergence would also help a lot.

Questions for authors

Can the authors relate ES∣W=wL^(w,S)\mathbb E_{S\mid W=w}\widehat L(w,S) to the actual empirical loss L^(w,Sobs)\widehat L(w,S_{\rm obs})? Under what assumptions does the claimed small-(\epsilon) interpretation hold?

Can the proposed bound be instantiated numerically on any realistically trained network, and is it non-vacuous?

How does the analysis change for approximate KKT/stationary points?

Can parameter-free residual connections be incorporated into the flow formulation?

9 comments

I found the flow interpretation quite interesting. Recasting balancedness of homogeneous networks as a network-flow problem is clean, and gives a simple dependence on the longest path rather than products of layer norms or path norms.

The analysis handles general DAGs rather than only chain networks, and the extensions to multi-class classification and regression are useful.

The paper is fairly transparent about the assumptions and also acknowledges that the results require exact KKT points and explicit regularization.

We thank the reviewer for the appreciation of our work.

W1.

I am not convinced the main theorem is really a generalization bound in the usual sense. […]

We thank the reviewer for this comment, and we apologize for the confusion caused by the statement of Theorem 1. Its setting is given just before it (lines 202–205): an i.i.d. sample is split into a training subset SS of size nn and a validation subset VV of size rr, a deterministic learning algorithm maps SS to U(S)\mathcal{U}(S), and W∣S∼N(U(S),ϵ2Id)W\mid S\sim\mathcal{N}(\mathcal{U}(S),\epsilon^2 I_d). The statement itself, however, reads "for every fixed ww" and does not repeat that WW is generated from the training subset SS. We will restate Theorem 1 so that this dependence is explicit: ES∣W=wE_{S|W=w} averages over the training subsets given that the perturbed weights WW, produced from them by the algorithm, take the value ww.

The counterexample. The example concerns the interpretation of the conditional expectation, not the validity of our results. An algorithm that returns the same weights for every training set ignores its data, which is not the setting of our main results: in Theorems 6–8, U(S)\mathcal{U}(S) is a KKT point of the regularized risk trained on SS, so WW depends on SS. Even in this degenerate case, Theorem 1 remains valid: PS∣W=w=PSP_{S|W=w}=P_S, the KL term is zero, the conditional expectation equals the population risk L(w,P)L(w,P), and the bound reduces to validation concentration (term (A), equation (20)). Since ww does not depend on SS, the observed training loss is also within O(1/n)O(1/\sqrt{n}) of the population risk by Hoeffding's inequality, so the bound still describes the gap between the validation loss and the observed training loss. The example does show that our remark on small ϵ\epsilon in lines 157–158 is imprecise, and we will revise it (reply to Q1).

Relation to the observed training loss. When U(S)\mathcal{U}(S) depends on SS, this dependence enters only through the KL term, which equation (23) bounds; for w=U(S)w=\mathcal{U}(S) in Theorem 6 it is at most 5(TG+2)/(2λϵ2)5(T_G+2)/(2\lambda\epsilon^2). The conditional expectation and the observed training loss can then be related without further assumptions (reply to Q1): for the perturbed network that is actually sampled, both are close to the population risk, at a rate controlled by the KL term. They are therefore close whenever the KL term is small compared with nn, which is the regime in which Theorem 1 is informative. The same argument yields a bound in the standard form, population risk minus observed training loss, with the confidence level entering as 1/δ1/\delta rather than ln⁡(1/δ)\ln(1/\delta).

Role of Theorem 1. Uniform-convergence bounds and norm-based PAC-Bayes bounds (Neyshabur et al., 2018) control the worst case over a norm-constrained class. This introduces products of layer norms or sums over input–output paths, which can grow exponentially with depth for DAGs such as ResNets and DenseNets (Table 1). Our approach differs in two ways.

  • We restrict attention to the networks that training actually returns: KKT points of the regularized objective, where flow conservation gives ∣∣U(S)∣∣2≤(TG+2)/λ||\mathcal{U}(S)||^2 \le (T_G+2)/\lambda (equation (15)).
  • We measure generalization locally: a validation set, which the network has not seen, provides an unbiased reference, and a change of measure around the trained network costs KL(PS∣W=w∣∣PS)\mathrm{KL}(P_{S|W=w} || P_S), which measures how much observing W=wW=w reveals about the training set (lines 193–201).

Since the set of stationary points depends on SS, a uniform bound over a fixed class cannot exploit this structure. This is why Theorem 1 conditions on the learned weights.

W2.

Relatedly, the role of the Gaussian perturbation makes the practical meaning of the bound unclear. […]

We thank the reviewer for this comment. Every term on the right-hand side of equations (16) and (17) can be evaluated from TGT_G, λ\lambda, ϵ\epsilon, nn, rr and δ\delta alone, even before training. The norm condition (15) on which it rests can be checked on the trained network, and the validation loss is computed directly; the expected training loss is related to the observed training loss in our reply to Q1. The useful regime is the largest ϵ\epsilon at which the perturbed network still agrees with the trained network on most training points, so that the bound describes a network that behaves like the trained one. Since the probability in Theorems 6 and 7 is over the validation set only, choosing ϵ\epsilon on the training set keeps the guarantee valid, and the validation set plays no part in the choice.

The new experiments illustrate this choice (reply to W5). On MNIST with λ=0.01\lambda=0.01, the perturbed network agrees with the trained network on at least 99.899.8% of the training points for ϵ≤10−3\epsilon\le 10^{-3} and on 98.298.2% at ϵ=0.01\epsilon=0.01, and then on only 9292%, 8080% and 4646% at ϵ=0.02\epsilon=0.02, 0.030.03 and 0.050.05. Meanwhile, our bound decreases as 1/ϵ1/\epsilon, from 224224 at ϵ=10−3\epsilon=10^{-3} to 22.422.4 at ϵ=0.01\epsilon=0.01. We therefore use ϵ=0.01\epsilon=0.01, the largest value at which the agreement stays above 95%95\%.

For large ϵ\epsilon, the trade-off is as the reviewer describes and as discussed in the Introduction (lines 155–157): Theorem 1 reduces to validation concentration, which remains a valid statement. For small ϵ\epsilon, our bound on the KL term grows as 1/ϵ21/\epsilon^2, and, as explained in our reply to Q1, our remark that the expected training loss approaches the observed one is imprecise; we will revise it. This trade-off is inherent to perturbation-based generalization bounds and is not specific to our analysis.

Neyshabur et al. (2018) use the same Gaussian perturbation, and their prior N(0,σ2I)\mathcal{N}(0,\sigma^2 I) plays the role of our reference density N(0,ϵ2Id)\mathcal{N}(0,\epsilon^2 I_d) (Appendix B). Their perturbation must keep the network output within γ/4\gamma/4 of the unperturbed one with probability at least 1/21/2 (their Lemma 1), so σ\sigma is set as a function of the margin γ\gamma and the product of spectral norms, and γ\gamma itself is left free (for any γ>0\gamma>0). More generally, margin-based bounds (Bartlett et al., 2017; Neyshabur et al., 2018) hold for every margin γ>0\gamma>0 and leave its choice to the user, trading the empirical margin loss against a complexity term of order 1/γ1/\gamma. Numerical PAC-Bayes bounds (Dziugaite & Roy, 2017) likewise select the perturbation scale numerically.

In contrast to Neyshabur et al., where the perturbation scale is tied to the margin and brings in the product of spectral norms, ϵ\epsilon in Theorem 1 is not tied to any margin condition. For any given ϵ\epsilon, every term of equations (16) and (17) is explicit and depends on the architecture only through TGT_G, without path norms.

W3.

The applicability to modern DAG architectures is quite limited. […]

We thank the reviewer for this comment. We are aware of the scope of our assumptions and state it explicitly in the appendix. Most of them are standard in the theoretical literature on norm-based generalization bounds.

No biases; single source and sink. Norm-based bounds are usually stated for networks without biases (Bartlett et al., 2017; Golowich et al., 2018; Neyshabur et al., 2018). Biases can be modelled as weights on a constant input, and extending our analysis to them is a direction for future work. Standard architectures such as ResNets and DenseNets take one input and produce one output, so they have a single source and a single sink; several inputs can be stacked into the single input vector received by the source node.

ℓ2\ell_2 regularization of the trainable edges. Weight decay is the default when training the architectures that motivate our work. ResNets and DenseNets are trained with weight decay 10−410^{-4} (He et al., 2016; Huang et al., 2017), and weight decay is also used to train all 121 pretrained models in TorchVision (TorchVision maintainers and contributors, 2016), which cover classification, detection, segmentation and video. Appendix A (Table 2) already computes Φ(U)\Phi(U) for 75 of these models. This regularization is exactly what produces the flow structure we analyse.

Loss functions. The loss enters the analysis only through the bound on the output weights. The paper covers the hinge loss (Lemma 1), the multi-class loss of Theorem 7 (Lemma 2) and the squared loss (Lemma 3, Theorem 8). The flow argument for the hidden nodes does not depend on the loss.

Normalization layers. Normalization makes the loss invariant to the scale of the preceding weights. With weight decay, such weights have no nonzero stationary point. Instead, training reaches a dynamic equilibrium, in which weight decay acts as a change of the effective learning rate rather than as a constraint on the norm (van Laarhoven, 2017; Li & Arora, 2020; Wan et al., 2021). Existing theory therefore treats normalized networks separately, and a stationarity-based analysis such as ours does not apply directly.

Architectures covered. The connectivity of two widely used families is a DAG of the form we analyse. In DenseNets, each node receives the outputs of all previous nodes in its block through trainable weights, and ResNets with projection shortcuts (He et al., 2016, option C) also fit. The rescaling argument of our reply to W4 extends to shortcuts with trainable scalar or diagonal gains under weight decay, since scaling such a gain keeps it in the same form. We discuss parameter-free residual connections in our reply to Q4.

Motivation and scope. The TorchVision examples illustrate how large path-based quantities become for widely used architectures. They serve as motivation, not as an evaluation of our bound, which is why the appendix notes that they fall outside our assumptions. To address the disconnect directly, the new experiments (reply to W5) evaluate the bounds on networks that satisfy every assumption of our analysis: trainable edges, no biases and no normalization. On these networks, we compare our bound with the DAG bound (6) of Gonon et al. (2024), the only bound in Table 1 that covers both DAGs and multi-class outputs. On 10-class MNIST with a DenseNet block, in which every node receives the outputs of all earlier nodes, TGT_G grows from 3 to 20 and the number of input–output paths from 4 to 524,288. Over this range, bound (6) grows from 270 to 901, while ours grows from 12.5 to 26.2; (6) is 22 to 35 times larger than ours at every depth. The revised Introduction states this scope explicitly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.