acceptodds
Under review as a conference paper at ICLR 2027

Query Complexity of Forward-Only Hebbian Learning: Theory and a Native Fit for Diffusion Models

Abstract

We study the query complexity of forward-only, gradient-free learning rules for training neural networks, motivated by settings where backpropagation is structurally unavailable: activation-tape memory that grows with depth and context, and objectives (quantized weights, non-differentiable rewards) whose exact gradient is zero almost everywhere. We analyze a three-factor Hebbian rule, an antithetic zeroth-order gradient estimator that perturbs parameters along a random probe and broadcasts a single scalar score to every synapse, and derive an exact, non-asymptotic identity for its gradient alignment as a function of probe count and problem dimension, yielding a closed-form query budget . We relate this upper bound to known minimax lower bounds for zeroth-order stochastic convex optimization, characterizing how close the rule's query complexity comes to the best possible rate for any gradient-free method. We further identify an architecture-dependent separability criterion, a measurable coupling scope and feedback bandwidth , that predicts when this query cost stays small, and confirm it empirically on a diffusion denoiser, where the per-noise-level residual gives : the rule closes most of the gap to backpropagation from scratch while eliminating its activation-memory overhead entirely, and continues to descend the loss through a quantized codebook argmin where the exact gradient is identically zero.

Primary area:
learning theory
Keywords:
query complexity, zeroth-order optimization, lower bounds, Hebbian learning, gradient-free training, diffusion models, evolution strategies, learning theory, memory-efficient training

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_eAzJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

In this paper, the authors investigate a forward-only, gradient-free learning method based on antisymmetric random perturbations and scalar feedback, interpreting it as a three-factor Hebbian learning rule. The authors derive the relationship between gradient-estimate alignment, the number of probes, and the problem dimension. They further propose a query-budget law based on the coupling range (S) and feedback bandwidth (K) to explain how different network architectures affect the efficiency of zeroth-order optimisation. The experiments cover convolutional autoencoders and denoising networks, ViT classification, vector-quantised codebooks, and multi-step DDPM generation tasks. The problem addressed by this paper is meaningful, and the proposed method avoids the need to store activations for backpropagation while achieving competitive results on some reconstruction and denoising tasks.

Critical strengths

S1: Forward-only learning avoids the need to store activations for backpropagation and offers a viable approach to optimising non-differentiable objectives. S2: The authors derive gradient alignment under Gaussian random probing and conduct supplementary simulations to examine the associated scaling laws. S3: The paper discloses discrepancies between some multi-seed results and the originally reported results, issues identified during baseline re-evaluation, and experiments that remain incomplete, helping readers assess the reliability of the current evidence.

Critical weaknesses

W1: The paper uses global scalar feedback for parameter updates but relates the query budget to the coupling range (S) and feedback bandwidth (K). However, the separability of output residuals does not necessarily imply that parameter gradients are decomposable. The authors need to further clarify this theoretical connection and the conditions under which it holds. W2: The paper establishes that the estimator is unbiased for the gradient of the Gaussian-smoothed objective. However, under the assumption that the objective is merely convex and Lipschitz continuous, treating this estimator directly as an unbiased estimate of the original objective's gradient and using it to derive the optimal query complexity lacks sufficient treatment of the smoothing bias. W3: The existing coupling experiments are primarily based on synthetic problems and do not sufficiently validate the gradient coupling structure in real CNNs/U-Nets. Nor do they establish that the idealized frequency-domain separability properties hold in practical nonlinear networks. W4: The paper does not compare the proposed method with standard SPSA or Evolution Strategies, making it difficult to establish its distinct advantages over existing methods.

Questions for authors

Q1: Please explain how global scalar feedback can support (K) independent feedback channels, and clarify the theoretical justification and conditions under which the dimension (P) in the gradient alignment formula can be replaced by the coupling range (S). Q2: Under the assumptions that the objective is only convex and Lipschitz continuous, how does Proposition 4 guarantee that the estimator is unbiased for the gradient of the original objective? Please revise the relevant assumptions or provide an analysis of the smoothing bias. Q3: Please measure cross-channel gradient coupling in practical CNNs/U-Nets and verify whether the proposed (S/K) query-budget law holds. Q4: Please compare the proposed method with standard SPSA or Evolution Strategies under matched query budgets, runtime, and peak memory usage to clarify its distinct contributions.

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

This paper studies the query complexity of forward-only Hebbian-like learning using antithetic zeroth-order gradient estimation. The authors derive analytical expressions for gradient alignment and variance, showing how the number of required forward evaluations depends on the number of trainable parameters.

The paper also introduces an architectural perspective based on coupling scope and feedback bandwidth to explain when forward-only learning can be efficient. Experiments on convolutional denoisers, diffusion models, vision Transformers, and quantized models support parts of the theoretical analysis.

The results show that forward-only learning can train neural networks without backpropagation and can optimize objectives involving non-differentiable operations. However, its performance generally remains below that of backpropagation, particularly in the full diffusion model setting.

Critical strengths

Interesting theoretical analysis of gradient estimation and query complexity

The paper provides a useful quantitative analysis of how gradient alignment and estimation variance depend on the number of forward evaluations and the problem dimension. Although it is intuitive that higher-dimensional problems require more evaluations, the analysis offers a clearer understanding of this relationship.

The connection between query complexity and architectural separability is also interesting. In particular, the discussion of coupling scope and feedback bandwidth provides a useful perspective on why forward-only learning may work better for some architectures than others.

Promising results on non-differentiable objectives

The connection to Gaussian smoothing is particularly interesting because it allows the method to optimize objectives for which ordinary backpropagation cannot provide useful gradients.

The vector-quantization experiment provides a convincing example of this capability. The experiments on diffusion denoisers and vision Transformers also demonstrate that forward-only learning can achieve meaningful results without storing activations for backpropagation.

These findings suggest that the approach may be useful in settings where gradients are unavailable or memory is limited.

Critical weaknesses

Limited novelty of the learning rule and uncertain generality of the separability analysis

The proposed gradient estimator is closely related to existing zeroth-order optimization methods, including SPSA and evolution strategies. Therefore, the main contribution appears to be the theoretical analysis and architectural interpretation rather than a new learning algorithm.

A more direct comparison with these existing methods would help clarify the contribution.

In addition, the proposed relationship between architectural separability and query complexity depends on modeling assumptions. The synthetic experiments provide encouraging evidence, but it remains unclear how accurately coupling scope and feedback bandwidth can be determined for real neural networks with shared parameters and complex interactions.

This limits the predictive value of the framework beyond the settings studied in the paper.

Experimental limitations and technical details that need clarification

The experimental results are promising, but a substantial performance gap remains between forward-only learning and backpropagation in the full DDPM setting. This suggests that the practical benefits of the proposed approach are not yet fully established for more challenging generative tasks.

The paper also reports an unresolved reproducibility discrepancy in the MNIST autoencoder experiments. Although the authors acknowledge this issue, it reduces confidence in some of the reported results.

Finally, a few mathematical details require clarification. In particular, the sign of the parameter update appears inconsistent with loss minimization, and there is a discrepancy in the dimension-dependent term of the variance expression.

These issues do not necessarily invalidate the main contributions, but resolving them would strengthen the technical soundness and experimental evidence.

Questions for authors

1. Generalizability of the separability framework.

How would the proposed analysis of coupling scope and feedback bandwidth extend to architectures with shared parameters, such as Mixture-of-Experts models?

Sparse expert activation may reduce the effective dimension of the problem, but shared parameters and routing decisions could introduce additional coupling. Could the authors clarify how these two quantities would be defined and measured in such settings?

A more concrete procedure for estimating them in real networks would help establish the predictive value of the proposed framework.

2. Comparison with existing zeroth-order methods.

Since the proposed estimator is closely related to SPSA and evolution strategies, could the authors clarify what advantages the proposed framework offers beyond these existing methods?

In particular, would the predicted query complexity and empirical performance differ when compared with standard implementations under the same computational budget?

3. Reproducibility and technical clarification.

Could the authors clarify the unresolved discrepancy in the MNIST autoencoder results and whether it affects the main experimental conclusions?

I would also appreciate clarification of the parameter update direction and the discrepancy in the variance expression.

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

The paper studies a standard zeroth-order gradient estimator based on random Gaussian perturbations of the parameters. The authors derive an exact formula, M/(M+D+1)M/(M+D+1), for a population-level measure of gradient alignment, where MM is the number of random probes and DD is the parameter dimension. The formula applies to quadratic objectives or in the small-perturbation limit for sufficiently smooth objectives, and matches the well-known linear dependence of the required probe count on the dimension.

They further propose that this cost can be reduced when the learning problem can be divided into components with independent feedback signals, deriving the law M∗K≳SM^*K \gtrsim S, where KK is the number of independent feedback channels and SS is the number of coupled residual terms. They argue that diffusion models are particularly suitable because of the structure of their denoising objective (which decomposes into separate terms in the spectral domain, leading the authors to claim that each frequency mode provides an independent feedback channel, with S=1S=1).

Experimentally, the authors evaluate the method on convolutional denoisers using MNIST, CIFAR-10, and CelebA. They show that the method can train these models from scratch (without backpropagation), achieving reasonable reconstruction performance, although it generally underperforms backpropagation. They also report substantial memory savings compared to backpropagation. The authors also evaluate the method in a setting involving a non-differentiable vector-quantization step, where standard backpropagation cannot propagate gradients through the quantization operation. In this setting, the method achieves performance close to backpropagation with a straight-through estimator (which approximates the gradient through the quantization step by the identity function).

Critical strengths

The paper provides a theoretical analysis of the query complexity of forward-only learning, together with experiments showing that zeroth-order optimization can train convolutional denoisers from scratch while substantially reducing memory usage. Although the theoretical analysis offers some useful intuition, its novelty and applicability to the experimental settings are unclear, as discussed in the weaknesses below.

Critical weaknesses

Unclear presentation and contributions. The paper is difficult to follow, particularly given the relative simplicity of much of its theoretical analysis. For example, Section 3.2 introduces the central quantities SS (coupling scope) and KK (feedback bandwidth) without precise mathematical definitions, and the relationship between the two proposed scaling laws is unclear. More generally, the paper does not clearly distinguish between rigorous theoretical results, modeling assumptions, and empirical observations. This makes it difficult to identify what is actually new and what has been established.

Limited theoretical novelty and insufficient justification of the main claims. The proposed estimator is a standard Gaussian zeroth-order estimator, and the alignment formula in Equation 3, as far as I understand, follows directly from classical variance calculations. The resulting linear dependence on the parameter dimension is well known (e.g., Nesterov and Spokoiny, 2017). The potentially novel contribution is the architecture-dependent law M∗K≳SM^*K\gtrsim S, but this law is not rigorously derived. In particular, substituting D=SD=S into Equation 3, as suggested by the authors, does not explain the dependence on K. Moreover, the claim that diffusion models have S=1S=1 is not sufficiently justified. The decomposition of the squared denoising loss into Fourier components does not imply that gradients with respect to the parameters of a nonlinear convolutional network are independent across these components.

Insufficient experimental evidence for the claimed contributions. The experiments mainly demonstrate that a known zeroth-order estimator can train relatively small neural networks without backpropagation, as already established in prior work. They do not convincingly validate the proposed architectural quantities SS and KK in practical neural networks, as the probe budgets are determined by the parameter count PP. The comparisons also lack standard zeroth-order baselines.

Questions for authors

Q1.Since the proposed update is equivalent to standard antithetic zeroth-order estimators (ES), what is the main theoretical or algorithmic contribution beyond existing work? In particular, how do the proposed query-complexity results differ from established analyses of these estimators?

Q2. Could the authors provide precise mathematical definitions of the coupling scope SS and feedback bandwidth KK, and explain how these quantities are determined for a given architecture?

Q3. Could the authors clarify how the scaling law M∗K≳SM^*K\gtrsim S in Section 3.2 is derived from the alignment identity in Eq. 3? While substituting D=SD=S gives M=Θ(S)M=\Theta(S), it is unclear how introducing KK feedback channels leads to a 1/K1/K reduction in the required number of probes.

Q4. In Section 5.1, the authors argue that the spectral decomposition of the diffusion denoising objective implies a coupling scope of S=1S=1. However, separability of the loss does not necessarily imply separability of the gradients with respect to shared neural-network parameters. Could the authors clarify why this property holds for the nonlinear convolutional denoisers used in their experiments?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.