acceptodds
Under review as a conference paper at ICLR 2027

Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networks

Abstract

Structured low-rank and sparse-plus-low-rank parameterizations, motivated by methods such as LoRA and low-rank factorization, impose strong structural constraints on the linear transformations within neural networks. We study the expressive consequences of these constrained structures from the perspective of universal approximation. We first characterize that purely low-rank neural networks, despite being able to exactly interpolate arbitrary finite scalar datasets, can fail to approximate continuous functions that vary along directions ignored by the low-rank hidden mapping. We show that augmenting the low-rank structure with a one-parameter diagonal component suffices to overcome this geometric bottleneck, yielding a Diagonal-plus-Low-Rank (DLoR) structure. We show that a full-rank linear transformations can be reconstructed using DLoR components either by expanding network width through additive decomposition or by extending network depth through multiplicative decomposition. We term this correspondence between additive width expansion and multiplicative depth extension the Structural Correspondence framework. By combining these constructions with local linearization of the activation function, we prove that DLoR neural networks restore universal approximation for general activation functions. These results characterize how architectural width and depth can compensate for severe rank constraints without requiring unrestricted dense hidden transformations.

Primary area:
learning theory
Keywords:
Universal Approximation Theorem, Diagonal-plus-Low-Rank (DLoR)

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_kag6OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2(+1)
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the expresive power of neural networks with linear layers constrained to be diagonal-plus-low-rank (DLoR) as M=αI+UV⊤M = \alpha I + UV^{\top}, via universal approximation (UAT). They motivate this by arguing that low-rank networks can interpolate finite data but remain blind to input directions outside the row space of first-layer weight (orthogonal blindness). In their DLoR constrcution, a dense layer (with nonlinearity applied) is recoved either additively (parallel low-rank branches stacked as a tall matrix) or multiplicatively (product of DoLR factors), with the activation linerized in between. Theoretically, plugging these into known dense results (Kidger–Lyons; Siegel) yields their UAT and parameter bounds. Empirically, they trained MLPs (sawtooth, MNIST) into DLoR networks with maching accuracy as validation of the constructions.

Critical strengths

1. The paper is technically correct and easy to follow. As far as my reading goes, the technical constructions and theory seem to hold. This includes their motivating their finite-data interpolation and orthogonal blindness arguments (Lem. 1-2 and Def. 1), the width and depth constructions (Thm. 1-2), and the UAT/param-bound results (Thm. 3-6). Specical cases are handled well (e.g., ReLU activation giving exact realization, retangular or singular weights). The paper is also clear and easy to follow in general. This matters because my concerns are about novelty and significance rather than correctness.

Critical weaknesses

1. Limited theoretical novelty. Overall, the main contributions follow from known results, and little seems specific to DLoR.

  • a) Additive construction (Thms. 1 and 4). Its rank constraints live entirely within the parallel branches Mℓ=UℓVℓ⊤M_\ell = U_\ell V_\ell^{\top}. This suggests to me that the low-rank constraint does not restrict the model class, because every dense layer can be split into low-rank branches via SVD in the first place, and that this costruction is about reparametrization. Importantly, the branches do not need the diagonal at all (α=0\alpha=0), and the resulting block reduces to Bρ(Wwidex+b)B \rho(W_\text{wide} x + b). This realizes WW at first order (when ρ\rho is linearized and cancelled out within the blocks), but neither BB nor WwideW_{\text{wide}} is low-rank.
  • b) Multiplicative construction (Thm. 2). Unlike the additive one, this uses the identity term in MM, which lets the rank-rr corrections accumulate. But, the factorization is a standard technique that replaces columns iteratively, and the parameter α\alpha plays no role for expressivity, as we can simple factor α−LW\alpha^{-L}W and rescale.
  • c) UAT results (Thms 3-6). From (a) and (b), once a dense layer ρ(Wx+b)\rho(Wx+b) is approximated via either width or depth, they substitue this block into the dense results of Kidger–Lyons and Siegel, which does not appear to involve new theoretical characterizations.
  • d) Prior work exists for the same template. The overall approach (factor dense weights into structured factors, then neutralize the activation to transfer UAT) largely resembles prceding work for triangular and Toeplitz/Hankel [1], which should be cited. I talk a bit more about this in Questions.

2. Limited significance. I see little consequencesof the constructions, for example, for efficiency in pratice, and the framing seems to overstate the motivation.

  • a) Parameter cost. Simulating one dense layer via either additive or multiplicative ways costs about 2N22N^2 parameters, so neither construction gives paramater savings over the original dense layer it replaces. This seems to contradict the PEFT/compression motivation in Sec. 1, which should be tempered. If some efficiency gains are realized via structures such as sparsity beyond raw parameter count (an analogy here would be Monarch or butterfly layers), this should be stated.
  • b) Empirical results. The core experiments only verify the constructions. The sawtooth task is 1D so orthogonal blindness does not occur, and the MNIST includes no pure low-rank baselines or cost comparisons.

[1] Liu, Y., Jiao, S., & Lim, L. H. (2024). LU decomposition and Toeplitz decomposition of a neural network. Applied and Computational Harmonic Analysis, 68, 101601.

Questions for authors

Q1. Given the novelty concerns (1a-d) in Weaknesses, can the authors please clarify the paper's main technical novelty corresponding to each of (1a-b)? If any of the four weaknesses point is misattributed or incorrect, please correct me here. In addition, I'd like to ask specifically the following two points:

  • As far as I understand, [1] seem to prove UAT for networks with triangular, Toeplitz or Hankel weights, where they factor dense weights into structured factors and linearize the activation in between. They also note (after their Thm. 2.4) that their proof extends to any factorization into structures preserved under scalar multiplication, which appears to include DLoR (at least for the uniformly continuous non-polynomial activations).
  • For non-polynomial activations, Kidger & Lyons’s register model appears to already admit an implementation with hidden weights of the form of scaled identity plus a rank-≤2\le 2 correction at width n+m+1n+m+1.

If the authors could clarify on these extra points, it'd help me undersand the core novelty more clearly.

Q2. Given 2a, what does the DLoR strcuture offer in return in terms of compute, memeory, trainability, function class etc?

Reviewer_8f9sOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies neural networks whose square weight matrices have the form \alpha I+UV^\top, with low-rank updates and a single scalar identity component. They first study networks with just the low-rank updates and proved lower bounds on approximability (affine collapse and orthogonal blindness. A simple diagonal component fixes these lower bounds and give universal approximation.

Critical strengths

The main arguments appear sound based on my reading of the main text, although I have not carefully verified the appendix proofs. The framework is simple and elegant: a scalar-identity augmentation provides a straightforward way to overcome the information bottleneck of purely low-rank layers. This connects naturally to familiar residual constructions. The exposition is clear, well-written and anticipates many natural questions about the construction and the scope of its guarantees.

The paper provides an explicit route from dense networks to networks with DLoR layers. The bounded-width construction accommodates common activations under the stated regularity assumptions, while the ReLU construction is exact on compact domains. These results clarify how strongly constrained layers can retain expressive power through composition, allowing approximation guarantees for dense networks to transfer to the DLoR architecture.

Critical weaknesses

No outstanding weaknesses (see questions)

Questions for authors
  • Computational efficiency: Under what conditions can the decomposed network reduce total computation or memory after accounting for the additional depth or width? The O(N2)O(N^2) parameter accounting for a generic dense layer does not establish an asymptotic saving. Can particular matrix structures or approximation regimes yield a meaningful advantage?
  • Adaptation and optimization: How does the framework extend to low-rank updates around a fixed pretrained dense matrix? Can it characterize the rank and depth needed to represent a target adaptation? Separately, do the constructions provide insight into conditioning or whether gradient-based training can find such representations?
Reviewer_fiAJOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies universal approximation when weight matrices are constrained to be low rank. It first notes two facts about rank-one and rank-r hidden layers:

  • A rank-one hidden layer can interpolate finite scalar data.
  • A rank-r hidden layer makes the network blind to the null space of V^{⊤} ("orthogonal blindness").

The paper then adds a scalar identity term, M=α I+UV^{⊤} (DLoR). It recovers a dense layer in two ways, with activations linearized around a point where ρ'(c)≠0:

  • by summing low-rank branches (more width);
  • by multiplying ⌈ N/r⌉ DLoR factors (more depth).

From this it derives:

  • a deep UAT at width n+m+2, via Kidger & Lyons;
  • a wide UAT;
  • a theorem that transfers any dense approximation result to DLoR networks;
  • a Sobolev approximation rate, via Siegel (2023);
  • exact ReLU constructions;
  • worst-case lower bounds of order N/r on the number of factors.

The experiments rebuild a trained MLP as DLoR networks, on a 1-D sawtooth function and on MNIST. They also plot singular-value spectra of DLoR networks trained on the sawtooth.

Critical strengths

S1. The statements are precise, and the proofs I checked are correct: the factorization in Theorem 2 via a generic basis Z, the induction in D.1, Proposition 1, and Theorem 10. The authors are careful about what the h→0 limit does and does not imply (Remark 2, C.5). They also give finite-h bounds and exact ReLU and paired-branch constructions that avoid the limit.

S2. Two results are useful beyond this paper. The transfer theorem (Thms. 5-6) shows that rank-one DLoR networks keep the dense Sobolev rate up to a constant. The diagonal-rank lower bound in F.5 carries the linear rank count over to fixed-width nonlinear networks through the Jacobian. That is a neat observation I had not seen before.

Critical weaknesses

W1. Most results follow directly from known tools, and the paper doesn't separate what is new.

  • Orthogonal blindness is the trivial case of a bottleneck narrower than the input: a rank-r first layer factors through ℝʳ. This is closely related to the minimum-width results (Hanin & Sellke, 2017; Johnson, 2019; Park et al., 2021).
  • A rank-one hidden layer is a one-dimensional network in t=v^{⊤} x with free slopes and biases. So Lemma 1 follows from classical 1-D interpolation (Pinkus, 1999), which only needs σ to be non-polynomial. "Non-mean-periodic" is a stronger assumption and excludes sin, for example.
  • The multiplicative decomposition is a standard identity-plus-low-rank factorization; the proof of Lemma 5 is Householder reflections plus diagonal elementary factors. The linear lower bound is the one-line count rank(∏ₗ Mₗ-∏ₗαₗ I)≤ Lr.
  • Theorem 3 is Kidger & Lyons (2020) with each dense layer replaced by ⌈ N/r⌉ factors. Theorem 4 is a dense UAT plus Theorem 1. Theorem 6 is Siegel (2023) plus the same substitution.

The closest prior work, Lin & Jegelka (2018), gets one sentence. It shows that residual blocks with a single hidden unit (identity plus a rank-one update) are universal at width d. The paper needs to state clearly what it adds beyond all of this.

W2. The results don't address parameter efficiency, which is the paper's motivation: LoRA, PEFT, compression, and "without sacrificing parameter efficiency" in the conclusion.

  • By the paper's own count (Sec. 5.2), one simulated N× N layer uses 2N²+q(N+1) parameters. That is 2-3x the N²+N of a dense layer, for every r.
  • The exact ReLU transfer (Prop. 6) allows up to about 9N² parameters per layer at rank one.
  • On MNIST, following Remark 4 and that count, I get about 1.4M parameters for the deep replica, against 235k for the MLP it copies (6x). The wide replica's first hidden layer has 13,312 units instead of 256.

So the framework trades rank for depth or width at a higher parameter count. That shows rank constraints don't destroy expressivity. It says nothing about the regime PEFT cares about (r≪ N, with far fewer than N² parameters per layer). It also doesn't cover LoRA itself, where the base matrix is a frozen pretrained W₀ rather than α I.

The experiments don't fill this gap. Rebuilding a trained MLP only checks the algebra, and even that is loose at the chosen h:

  • The replicas reach lower training loss than the network they copy (0.0128 and 0.0125 vs 0.0172, Table 1).
  • The deep replica's maximum logit deviation is 1.26 (Table 2).

This is expected from the 1/h normalization and the ∏ₗ‖Mₗ‖ growth in C.5, but the text reads it as "the same generalization." Also, the sawtooth input is 1-D, where orthogonal blindness can't occur.

Minor issues:

  • F.2 cites Theorem 4 for the deep model and Theorem 3 for the wide one; these look swapped.
  • "Linear benefits of depth" in Sec. 5.1 should say width.
  • The contributions list claims "any nonaffine continuous activation," but Assumption 1 needs a C¹ point with ρ'(c)≠0.
  • Phrases like "perfectly overcomes," "profound consequence" and "catastrophic geometric collapse" (App. A) oversell simple results.
Questions for authors
  1. (Clarification) What, concretely, is new relative to Kidger & Lyons (2020), Lin & Jegelka (2018), and classical identity-plus-low-rank factorizations?
  2. (Clarification) Is there a setting where DLoR networks with total parameters well below the dense count approximate something that dense networks with the same budget cannot, or approximate it at a better rate? A result in the LoRA setting (frozen W₀ plus a low-rank update) would also speak to the motivation.
  3. (Experiment) Please report parameter counts and numerical precision for the MNIST replicas. Please also rebuild them with the exact ReLU or paired-branch constructions (Prop. 1, Prop. 4), so that the finite-h deviations disappear.
  4. (Experiment) Please add a small from-scratch comparison of pure rank-one, DLoR rank-one and dense networks at matched parameter counts, on Figure 4's x²+y² or a higher-dimensional target. This would directly test the central claim.

I'd raise my score if the paper either proves something that holds under a real parameter budget, or reframes its contribution more modestly as a transfer result with clear positioning against the work above.

Reviewer_jqxWOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the expressive power of Diagonal-plus-Low-Rank (DLoR) neural networks. The authors establish a structural correspondence between additive width expansion and multiplicative depth extension, showing that severely rank-constrained networks can recover universal approximation capabilities.

Critical strengths
  • The paper addresses an interesting theoretical problem concerning the expressive limitations of low-rank neural networks.

  • The structural correspondence between network width, depth, and rank constraints provides useful theoretical insights.

Critical weaknesses
  • Although each DLoR layer uses fewer parameters, reconstructing a general dense transformation may require significantly greater depth. For example, a dense layer with a 100×100100 \times 100 weight matrix requires 100×100+100=10,100100 \times 100 + 100 = 10{,}100 parameters, including biases. In contrast, a rank-1 DLoR layer parameterized as W=αI+uv⊤W = \alpha I + uv^\top requires 100+100+1+100=301100 + 100 + 1 + 100 = 301 parameters, including the two rank-1 vectors, one diagonal scalar, and biases. According to Theorem 2, reconstructing an arbitrary invertible 100×100100 \times 100 matrix can require up to ⌈N/r⌉=100\lceil N/r \rceil = 100 DLoR factors. Using 100 such layers results in 100×301=30,100100 \times 301 = 30{,}100 parameter slots, approximately three times the original dense layer. Thus, while individual DLoR layers are parameter-efficient, the overall construction does not necessarily reduce the total parameter count or computational cost.

  • The experiments are limited to Sawtooth and MNIST, primarily demonstrating the reconstruction of pretrained dense networks. The paper does not evaluate whether DLoR offers better parameter efficiency, computational efficiency, or inference latency under comparable budgets. Moreover, the experiments do not convincingly demonstrate the practical feasibility of the rank-1 setting emphasized by the theoretical results.

  • The universal approximation results establish the existence of suitable DLoR networks but do not guarantee that these architectures can be efficiently trained. The paper provides limited evidence regarding optimization difficulty and numerical stability, particularly when the rank is very small and the required depth becomes large.

Questions for authors
  • What is the actual practical impact of the proposed framework? If the resulting architectures require comparable or more parameters and substantially greater depth, what concrete advantage do they offer over standard dense networks?

  • Can the authors demonstrate parameter efficiency or computational advantages under matched parameter/FLOP budgets, rather than only representational equivalence?

  • Can the authors evaluate the rank-1 DLoR construction on more challenging datasets and report numerical stability, training convergence, and inference latency?

1 comment

Thank you for the detailed rebuttal and the substantial revisions. I appreciate the authors' efforts to address my concerns, particularly the new theoretical characterization of representation costs, the matched-parameter experiments, and the additional analysis of numerical stability.

The new results based on κ(W)\kappa(W) provide a clearer understanding of when DLoR can achieve parameter savings. I acknowledge that my original parameter-counting example represents the generic worst case, and that DLoR can be substantially more efficient for identity-centered, low-rank-perturbed matrices. This addresses an important part of my first concern.

However, my main concern regarding practical efficiency remains only partially resolved.

First, the demonstrated efficiency gains are concentrated in a specific structural regime. While the theoretical characterization is valuable, the paper does not establish how frequently this favorable regime occurs in real pretrained neural networks or whether it leads to meaningful end-to-end improvements.

Second, I appreciate the newly added matched-parameter experiments. Nevertheless, these comparisons primarily involve small synthetic tasks. In the MNIST experiments, DLoR still requires approximately 1.5 times as many parameter slots as truncated SVD to achieve comparable accuracy. Thus, the empirical evidence does not yet establish a consistent practical advantage over existing alternatives.

Third, the additional rank-1 training and conditioning analyses are useful. However, the reported sensitivity to activation choice and numerical instability at greater depths reinforces my original concerns about optimization and scalability. Moreover, the requested inference-latency evaluation remains missing. Theoretical parameter or FLOP reductions do not necessarily translate into lower inference latency, particularly when additional sequential layers are required.

Therefore, while I appreciate the improvements, I consider my original concerns about practical significance, computational efficiency, and scalability to be partially, rather than fully, addressed. Nevertheless, I still increase 1 score for your effort.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.