- 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
** 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 . […]
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, , which is smaller than . 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 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 . When , 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, if its objective is at most that of the zero network, and 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 . 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 and its outgoing weights by 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 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 input–output paths. We minimize the multi-class hinge loss with weight decay by SGD, use the 10,000 test images as the validation set and , with three runs per setting.
We thank the reviewer for their thoughtful and positive comments.
** W1
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/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 TG, λ, ϵ and n. This term needs a bound on ∣∣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)] 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 TG and does not depend on n or the data. No explicit norm constraint is imposed, and no radius has to be chosen in advance.
"The choice of ϵ is left open." As with the posterior variance in PAC-Bayesian perturbation bounds (Neyshabur et al., 2018; Dziugaite and Roy, 2017), ϵ 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 ϵ 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=10 trained on 30,000 images, the root-mean-square weight is 0.019. At ϵ=0.01, about half of this value, the perturbed network agrees with the trained one on 98.2 % of the training points, and the agreement drops only once ϵ exceeds the typical weight (92% at ϵ=0.02, 46% at ϵ=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 1 with ϵ comparable to the typical weight, at a noise level the trained networks tolerate (Table F)