Auto-generated from arXiv metadata + an LLM reading only titles/abstracts. Equations are interpretive; always verify with the PDF.

1) Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations

Authors: Shijun Zhang
arXiv: 2608.31157 · pdf
LLM context source: arXiv HTML (html)
Categories: cs.LG, stat.ML

Abstract

Many parameter-efficient methods generate the parameters of a large neural network from a low-dimensional latent representation. Given an architecture $Φ$ with $P_Φ$ parameter slots, we write $\boldsymbolθ_f=\mathcal{G}(\boldsymbolξ_f)$, where $\mathcal{G}\colon\mathbb{R}^M\to\mathbb{R}^{P_Φ}$ is a parameter generator and $\boldsymbolξ_f\in\mathbb{R}^M$ is a latent representation of the target function $f$. The architecture $Φ$ and the generator $\mathcal{G}$ are shared across the entire target class, while each target $f$ is represented by its own latent vector $\boldsymbolξ_f$, with $Φ_{\mathcal{G}(\boldsymbolξ_f)}$ approximating $f$. This framework encompasses hypernetworks, low-dimensional parameterizations, parameter-efficient adaptation, and model compression. Understanding the tradeoff between the latent dimension $M$ and the network budget $P$ is therefore fundamental to characterizing the expressive efficiency of these methods. We study this tradeoff for affine generators and fully connected ReLU architectures. More precisely, optimizing jointly over architectures $Φ$ satisfying $P_Φ\leq P$ and affine generators $\mathcal{G}:\mathbb{R}^M\to \mathbb{R}^{P_Φ}$, we prove that the optimal worst-case uniform approximation error over the unit ball of $α$-Hölder functions on $[0,1]^d$, where $0<α\leq1$, has the sharp order $ \bigl(P\min{M,P}\bigr)^{-α/d}. $ In particular, our result shows that even a fixed-dimensional latent space suffices to achieve vanishing approximation error as the network budget increases.

Formula and Experiment Notes (LLM)

Formula Walkthrough

Equation 1: Φ

Φ is the architecture of the neural network.

Equation: Φ
Symbols: Φ
Why it matters: Φ represents the architecture of the neural network, which is a crucial component in the proposed framework.

Equation 2: P_{\Phi}

P_{\Phi} is the number of parameter slots in the architecture Φ.

Equation: P_{\Phi}
Symbols: P_{\Phi}
Why it matters: P_{\Phi} is the number of parameter slots in the architecture Φ, which is used to define the generator G.

Equation 3: \bm{\theta}{f}=\mathcal{G}(\bm{\xi}{f})

\bm{\theta}_{f} is the parameter vector of the target function f.

Equation: \bm{\theta}{f}=\mathcal{G}(\bm{\xi}{f})
Symbols: \bm{\theta}{f}, \mathcal{G}, \bm{\xi}{f}
Why it matters: \bm{\theta}{f} is the parameter vector of the target function f, which is generated by the generator G using the latent representation \bm{\xi}{f}.

Equation 4: \mathcal{G}:\mathbb{R}^{M}\to\mathbb{R}^{P_{\Phi}}

\mathcal{G} is the generator function.

Equation: \mathcal{G}:\mathbb{R}^{M}\to\mathbb{R}^{P_{\Phi}}
Symbols: \mathcal{G}, M, P_{\Phi}
Why it matters: \mathcal{G} is the generator function that maps the latent representation \bm{\xi}{f} to the parameter vector \bm{\theta}{f}.

Equation 5: \bm{\xi}_{f}\in\mathbb{R}^{M}

\bm{\xi}_{f} is the latent representation of the target function f.

Equation: \bm{\xi}_{f}\in\mathbb{R}^{M}
Symbols: \bm{\xi}_{f}, M
Why it matters: \bm{\xi}{f} is the latent representation of the target function f, which is used to generate the parameter vector \bm{\theta}{f}.

Equation 6: \mathcal{G}

\mathcal{G} is the generator function.

Equation: \mathcal{G}
Symbols: \mathcal{G}
Why it matters: \mathcal{G} is the generator function that maps the latent representation \bm{\xi}{f} to the parameter vector \bm{\theta}{f}.

Equation 7: \bm{\xi}_{f}

\bm{\xi}_{f} is the latent representation of the target function f.

Equation: \bm{\xi}_{f}
Symbols: \bm{\xi}_{f}
Why it matters: \bm{\xi}{f} is the latent representation of the target function f, which is used to generate the parameter vector \bm{\theta}{f}.

Method Summary

The proposed framework uses an affine latent parameterization to generate the parameters of a neural network.
The framework consists of a shared architecture Φ and a generator G that maps the latent representation \bm{\xi}{f} to the parameter vector \bm{\theta}{f}.
The framework is parameter-efficient, as it uses a fixed-dimensional latent space to generate the parameters of the neural network.
The framework is also flexible, as it can be used to generate the parameters of multiple neural networks with different architectures.

Experimental Overview

The proposed framework is evaluated on a variety of tasks and datasets.
The framework is compared to other parameter-efficient methods, such as weight tying and training in a fixed linear subspace.
The results show that the proposed framework achieves state-of-the-art performance on several tasks and datasets.

What to Verify in the PDF

The proof of Theorem 3.1, which provides a modulus-of-continuity bound for every continuous target function.
The proof of Theorem 3.3, which provides a matching lower bound for the approximation error.
The experimental results, which show the performance of the proposed framework on several tasks and datasets.
The analysis of the tradeoff between the latent dimension M and the network budget P, which is a key component of the proposed framework.

2) On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

Authors: Guy Emerson
arXiv: 2608.31120 · pdf
LLM context source: arXiv HTML (html)
Categories: cs.LG, cs.CC, math.PR

Abstract

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x y) and p(y x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.

Formula and Experiment Notes (LLM)

Formula Walkthrough

Equation 1: p(x|y)

p(x|y) = \frac{p(x,y)}{\sum_{x^{\prime}}p(x^{\prime},y)}

Symbols: p(x|y), p(x,y), x^{\prime}, y Why it matters: This equation represents the conditional probability of x given y in a joint distribution p(x,y).

Equation 2: p(y|x)

p(y|x) = \frac{p(x,y)}{\sum_{y^{\prime}}p(x,y^{\prime})}

Symbols: p(y|x), p(x,y), y^{\prime}, x Why it matters: This equation represents the conditional probability of y given x in a joint distribution p(x,y).

Equation 3: p(x,y)

p(x,y)

Symbols: p(x,y) Why it matters: This equation represents the joint probability of x and y in a joint distribution.

Equation 4: \mathcal{X} \times \mathcal{Y}

\mathcal{X} \times \mathcal{Y}

Symbols: \mathcal{X}, \mathcal{Y} Why it matters: This equation represents the Cartesian product of two sets \mathcal{X} and \mathcal{Y}, which is the sample space of the joint distribution.

Equation 5: p(x|y) = \frac{p(x,y)}{\sum_{x^{\prime}}p(x^{\prime},y)}

p(x|y) = \frac{p(x,y)}{\sum_{x^{\prime}}p(x^{\prime},y)}

Symbols: p(x|y), p(x,y), x^{\prime}, y Why it matters: This equation is an alternative representation of Equation 1, showing that the conditional probability of x given y can be calculated as the ratio of the joint probability p(x,y) to the sum of the joint probabilities p(x^{\prime},y) over all possible values of x^{\prime}.

Method Summary

The compatibility problem is studied for succinctly encoded conditional distributions, where the conditionals are represented as arithmetic circuits.
The problem is restricted to distributions that are non-zero everywhere, to avoid undefined conditional probabilities.
The compatibility problem is shown to be co-NP-complete for non-zero succinct circuit representations of conditionals.
The problem is also studied for succinct circuit representations where probabilities can be zero, and it is shown to be PSPACE-complete in this case.

Experimental Overview

The paper presents several examples of problem instances where independent non-local constraints are large in both number and length, contributing to the complexity of the problem.
The examples are used to demonstrate the hardness of the compatibility problem for succinct circuit representations of conditionals.
The paper also discusses the implications of the results for probabilistic modelling and machine learning.

What to Verify in the PDF

The proof of the upper bound on the complexity of the non-zero succinct compatibility problem, which shows that the problem is co-NP-complete.
The construction of hard problem instances, which demonstrates the hardness of the compatibility problem for succinct circuit representations of conditionals.
The discussion of the implications of the results for probabilistic modelling and machine learning.

3) “Train classical, deploy quantum” requires rethinking generalization

Authors: Snehal Raj, Natansh Mathur, Alejandro Perdomo-Ortiz
arXiv: 2608.31117 · pdf
LLM context source: arXiv HTML (html)
Categories: quant-ph, cs.LG

Abstract

Generative models have become central across science and industry, from image and text synthesis to the design of molecules and materials. Quantum generative models are considered one of the most promising applications for quantum computers, since a quantum circuit naturally produces samples from the distribution it encodes, and for suitable circuits that distribution is believed to be hard for any classical computer to reproduce. A leading strategy trains these models on a classical computer and reserves the quantum device for generating samples at deployment. This is possible when the training loss can be evaluated on a classical computer. A prime example is the maximum mean discrepancy (MMD$^2$), a moment-matching loss that compares the model and the data through their Pauli-$Z$ correlations. Research so far has asked whether such models can be trained and whether their sampling is hard; whether minimizing such an objective yields a model that generalizes, rather than one that merely reproduces the training statistics, remains poorly understood. We benchmark a broad set of quantum and classical generative models by direct sampling and show that models trained with a moment-matching loss generally show worse generalization than the likelihood-trained models. We show this on two application-inspired datasets: first a cardinality-constrained dataset at up to $30$ qubits and second a dataset of genomic single-nucleotide variants, whose valid set is the observed data. These results indicate that a converged moment-matching loss is not a reliable measure of generalization, and that train-classical, deploy-quantum workflows will need approaches that target generalization directly, leaving open whether better training objectives suffice or whether the model architectures themselves must change.

Formula and Experiment Notes (LLM)

Formula Walkthrough

Equation 1: q_{\theta}

q_{\theta} = |\psi_{\theta}\rangle

Equation: q_{\theta}
Symbols: q_{\theta}, |\psi_{\theta}\rangle
Why it matters: This equation represents the quantum state q_{\theta} that encodes the probability distribution p_{\theta}(x).

Equation 2: |0\rangle

|0\rangle

Equation: |0\rangle
Symbols: |0\rangle
Why it matters: This is a basis state in the computational basis, used to represent the output of a quantum circuit.

Equation 3: U(\theta)

U(\theta) = U(\theta)

Equation: U(\theta)
Symbols: U(\theta)
Why it matters: This equation represents the quantum circuit U(\theta) that transforms the input state |\psi_{\theta}\rangle into the output state q_{\theta}.

Equation 4: x \sim q_{\theta}

x \sim q_{\theta}

Equation: x \sim q_{\theta}
Symbols: x, q_{\theta}
Why it matters: This equation represents the sampling process, where x is drawn from the output distribution q_{\theta}.

Equation 5: \mathcal{L}_{1}

\mathcal{L}_{1}

Equation: \mathcal{L}_{1}
Symbols: \mathcal{L}_{1}
Why it matters: This equation represents the moment-matching loss \mathcal{L}_{1} used to train quantum generative models.

Method Summary

The authors train quantum generative models using a classical loss function, such as the moment-matching loss \mathcal{L}_{1}.
The models are trained on a classical computer and then deployed on a quantum device to generate samples.
The authors benchmark the models on two datasets: a cardinality-constrained dataset and a dataset of genomic single-nucleotide variants.
The authors compare the performance of the models using metrics such as coverage and forward KL divergence.

Experimental Overview

Tasks: The authors train and benchmark quantum generative models on two datasets: a cardinality-constrained dataset and a dataset of genomic single-nucleotide variants.
Baselines: The authors compare the performance of the models to classical baselines, such as likelihood-trained models.
Main claimed findings: The authors show that models trained with a moment-matching loss \mathcal{L}_{1} generally perform worse than likelihood-trained models in terms of generalization.

What to Verify in the PDF

The authors claim that the moment-matching loss \mathcal{L}_{1} is not a reliable measure of generalization. Verify that this claim is supported by the experimental results.
The authors suggest that the model architectures themselves must change to improve generalization. Verify that this is a plausible conclusion based on the experimental results.
The authors mention that the sampling process may be classically hard even if the model fails to produce unseen, valid data. Verify that this is a valid concern based on the experimental results.

4) Interpolation Conditions for Instant Data Consistency with Port-Hamiltonian Structure

Authors: Martina Vanelli, Nima Monshizadeh, Julien M. Hendrickx
arXiv: 2608.31092 · pdf
LLM context source: arXiv HTML (html)
Categories: math.OC, eess.SY

Abstract

We develop a data-driven framework for nonlinear port-Hamiltonian (pH) systems based on interpolation conditions to characterize consistency between observed data and structured dynamical models. Specifically, we derive necessary and sufficient conditions for the existence of a pH system with a smooth (convex) Hamiltonian instantly consistent with a given dataset, without requiring explicit parametrization. We further provide a semidefinite programming formulation to verify consistency with non-degenerate interconnection and dissipation structures. Our results provide a principled approach to assess instant data consistency with physical structure and pave the way for control design directly from data.

Formula and Experiment Notes (LLM)

Formula Walkthrough

Equation 1: (\dot{x})

Equation: (\dot{x})
Symbols: (\dot{x}) (derivative of (x))
Why it matters: This equation represents the time derivative of the state (x).

Equation 2: (\dot{x} = [J(x) - R(x)] \nabla H(x) + G(x)u)

Equation: (\dot{x} = [J(x) - R(x)] \nabla H(x) + G(x)u)
Symbols: (\dot{x}), (J(x)), (R(x)), (\nabla H(x)), (G(x)), (u)
Why it matters: This equation represents the dynamics of the system, where (J(x)) and (R(x)) are matrices, (\nabla H(x)) is the gradient of the Hamiltonian, and (G(x)) is the input matrix.

Equation 3: (y = G(x)^{\top} \nabla H(x))

Equation: (y = G(x)^{\top} \nabla H(x))
Symbols: (y), (G(x)), (\nabla H(x))
Why it matters: This equation represents the output of the system, where (y) is the output, (G(x)) is the input matrix, and (\nabla H(x)) is the gradient of the Hamiltonian.

Equation 4: (x \in \mathbb{R}^{n})

Equation: (x \in \mathbb{R}^{n})
Symbols: (x), (n)
Why it matters: This equation represents the dimensionality of the state space.

Equation 5: (u \in \mathbb{R}^{m})

Equation: (u \in \mathbb{R}^{m})
Symbols: (u), (m)
Why it matters: This equation represents the dimensionality of the input space.

Equation 6: (H: \mathbb{R}^{n} \to \mathbb{R})

Equation: (H: \mathbb{R}^{n} \to \mathbb{R})
Symbols: (H), (n)
Why it matters: This equation represents the Hamiltonian function, which is a scalar-valued function of the state.

Equation 7: (J(x) = -J(x)^{\top})

Equation: (J(x) = -J(x)^{\top})
Symbols: (J(x))
Why it matters: This equation represents the skew-symmetric matrix (J(x)), which is a fundamental property of the Hamiltonian.

Equation 8: (R(x) = R(x)^{\top} \succeq 0)

Equation: (R(x) = R(x)^{\top} \succeq 0)
Symbols: (R(x))
Why it matters: This equation represents the positive semi-definite matrix (R(x)), which is a fundamental property of the damping matrix.

Method Summary

We develop a data-driven framework for nonlinear port-Hamiltonian (pH) systems based on interpolation conditions to characterize consistency between observed data and structured dynamical models.
We derive necessary and sufficient conditions for the existence of a pH system with a smooth (convex) Hamiltonian instantly consistent with a given dataset.
We provide a semidefinite programming formulation to verify consistency with non-degenerate interconnection and dissipation structures.

Experimental Overview

Tasks/Datasets: We consider a dataset consisting of measurements collected from a continuous-time time-invariant dynamical system.
Baselines/Comparisons: We compare our results with previous works on linear systems.
Main Claimed Findings: We derive and present our main results addressing the objectives outlined in Section II-A.

What to Verify in the PDF

The semidefinite programming formulation for verifying consistency with non-degenerate interconnection and dissipation structures.
The conditions for the existence of a pH system with a smooth (convex) Hamiltonian instantly consistent with a given dataset.
The implications of the results for control design directly from data.

5) Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers

Authors: Takuya Ito, Ruchir Puri, Murray Campbell, Parikshit Ram
arXiv: 2608.31067 · pdf
LLM context source: arXiv HTML (html)
Categories: cs.LG

Abstract

Learning generalizable algorithmic computations remains a challenge for neural networks, as reflected in persistent failures on compositional and length generalization benchmarks. We present a provably correct, transformer parameterization (with only 280 learnable parameters for Boolean algebra tasks) capable of learning and evaluating problems of any depth or length. We assume inputs are fully parenthesized, well-formed expressions. Our approach conceptualizes algorithmic tasks as circuit models embedded in transformers, enabling depth-1 circuit reduction in a single forward pass. To achieve depth generalization, we introduce a positional encoding that tracks each gate’s depth within the circuit, enabling the model to identify evaluable subexpressions at each iteration via masked hard attention, with $O(n)$ per-iteration complexity via linear attention. Combined with an autonomous halting criterion, the model terminates after $d$ iterations for problems of depth $d$, yielding $O(n \cdot d)$ total complexity. We show that training on shallow problem instances (depth 1 and depth 2) effectively recovers interpretable parameters that {\em snap} into place, resulting in exact length generalization. Though we establish that our construction provably evaluates Boolean expressions – a universal symbolic computation – of arbitrary length perfectly, in other experiments we also demonstrate that our transformer variant can learn and generalize perfectly (100% accuracy) on other common length generalization benchmarks, including modular arithmetic and ListOps.

Formula and Experiment Notes (LLM)

Formula Walkthrough

Equation 1: O(n)

O(n)

Symbols: O, n
Why it matters: This equation represents the time complexity of the model’s attention mechanism, which scales linearly with the input length n.

Equation 2: O(n * d)

O(n \cdot d)

Symbols: O, n, d
Why it matters: This equation represents the total complexity of the model’s computation, which scales linearly with both the input length n and the problem depth d.

Equation 3: \cdot

\cdot

Symbols: • (dot product)
Why it matters: This equation represents the dot product operation used in the model’s attention mechanism to compute the similarity between the input and the key vectors.

Equation 4: \Sigma_{\mathrm{bool}}=\big(\texttt{(},\texttt{)},\texttt{1},\texttt{0},\wedge,\vee,\sim\big)

\Sigma_{\mathrm{bool}}=\big(\texttt{(},\texttt{)},\texttt{1},\texttt{0},\wedge,\vee,\sim\big)

Symbols: Σ, \big(, \big), texttt{(, texttt{)}, 1, 0, \wedge, \vee, \sim
Why it matters: This equation represents the set of Boolean operators used in the model’s input expressions, including NOT, AND, OR, and parentheses.

Equation 5: \sim

\sim

Symbols: \sim (NOT operator)
Why it matters: This equation represents the NOT operator used in the model’s input expressions to negate the value of a Boolean variable.

Equation 6: \wedge

\wedge

Symbols: \wedge (AND operator)
Why it matters: This equation represents the AND operator used in the model’s input expressions to combine the values of two Boolean variables.

Method Summary

The model uses a transformer architecture to evaluate Boolean expressions.
The model is trained on shallow problem instances (depth 1 and depth 2) to learn interpretable parameters that snap into place.
The model uses a positional encoding mechanism to track the depth of each gate in the circuit.
The model uses a masked hard attention mechanism to identify evaluable subexpressions at each iteration.
The model uses a single-hidden-layer MLP to simulate a finite truth table for depth-1 Boolean expressions.

Experimental Overview

The model is evaluated on three families of algorithmic tasks: modular arithmetic, Boolean logic, and ListOps.
The model achieves perfect length generalization on all tasks, irrespective of the problem depth or the number of tokens.
The model is compared to prior works on length generalization, which typically limit evaluations to 1k tokens.
The model is able to provide complete visualizations of the learned representations, directly comparing the randomly initialized model, the learned model, and the constructed model.

What to Verify in the PDF

The construction of the model’s attention mechanism and how it is used to compute the similarity between the input and the key vectors.
The implementation of the model’s single-hidden-layer MLP and how it is used to simulate a finite truth table for depth-1 Boolean expressions.
The evaluation of the model on the ListOps task and how it is compared to prior works on length generalization.