Generalization as a robust performance property of learning-enabled dynamical systems

• Generalization concerns performance on new, unseen data rather than only training samples.Source: §I · p. 1
• Classical algorithmic stability measures output changes under replacement of one training sample and supports high-probability guarantees when this change is uniformly small.Source: §I · p. 2
• Recursive trajectory-distance arguments do not explicitly capture how data perturbations are attenuated or amplified across algorithmic iterations.Source: §I · p. 2
• The proposed sensitivity system models sample replacement as an exogenous disturbance and decomposes operator discrepancy into propagated and injected sensitivity.Source: §I · p. 2
• Dissipativity and incremental quadratic constraints yield an optimization-based stability bound separating one-sample operator sensitivity from an algorithm-dependent dynamical gain.Source: §I · p. 2
• The framework complements prior contraction-based analyses by treating sample replacement explicitly as an input and applying to broader data-dependent operators and dynamics.Source: A. Related work · p. 3

• The approach covers operators learned offline through least squares or kernel ridge regression and is illustrated with a kernel-based residual controller.Source: B. Summary of contributions and paper… · pp. 4–5
• Algorithmic stability is recast as an input-output robustness property from sample-replacement disturbance to loss discrepancy.Source: B. Summary of contributions and paper… · p. 4
• A matrix-inequality dissipativity certificate produces a uniform stability bound that separates statistical operator sensitivity from interconnection-induced amplification.Source: B. Summary of contributions and paper… · p. 4
• The dynamical sensitivity gain is formulated as a semidefinite program with scalar search, enabling systematic optimization and comparison of dynamics.Source: B. Summary of contributions and paper… · p. 4
• The framework recovers contractivity-based stability for gradient descent and applies to heavy-ball and Nesterov methods even when contractivity may fail.Source: B. Summary of contributions and paper… · p. 5
• Numerical experiments indicate that nominal convergence and data sensitivity are distinct design objectives.Source: B. Summary of contributions and paper… · p. 5
• Several practical mappings have one-sample perturbation scaling as 1/N, supporting consistent, exponential, high-probability bounds.Source: B. Summary of contributions and paper… · p. 5

• An algorithm maps a dataset to a hypothesis, and its prediction accuracy is evaluated through a loss function.Source: A. Preliminaries on algorithmic… · pp. 6–7
• Uniform stability requires that replacing one training sample does not substantially change the algorithm’s output under the loss.Source: A. Preliminaries on algorithmic… · p. 7
• Uniform stability yields a probabilistic bound on the generalization gap for bounded losses.Source: A. Preliminaries on algorithmic… · p. 7
• When η scales as 1/N, the bound vanishes as N →∞, providing the stated consistency property.Source: A. Preliminaries on algorithmic… · p. 7
• Incremental input-output stability implies uniform stability when the learned operator’s neighboring-dataset difference is bounded and D = 0.Source: B. An incremental IO interpretation of… · p. 8
• Because i-IOS is difficult to verify and a terminal snapshot wastes transient sensitivity information, the paper motivates a tractable dissipativity-based approach.Source: B. An incremental IO interpretation of… · pp. 8–9

• Algorithmic stability is recast as the output of a data sensitivity system rather than solely as a static property.Source: §III · p. 10
• Replacing one sample creates an exogenous disturbance, and the stability coefficient decomposes into data injection and dynamical sensitivity terms.Source: §III · p. 10, A. Sensitivity dynamics and uniform… · p. 11
• The learned operator is assumed to satisfy an incremental IQC, while its neighboring-dataset perturbation is uniformly bounded by ζN.Source: A. Sensitivity dynamics and uniform… · pp. 10–11
• Theorem 3.3 uses a storage function and matrix inequality to bound the induced gain from the disturbance w to terminal state sensitivity ΔxT.Source: A. Sensitivity dynamics and uniform… · pp. 11–13
• A uniform stability bound follows by combining the gain certificate with a uniform bound on the data-injection signal.Source: A. Sensitivity dynamics and uniform… · p. 13
• Tight bounds consistent with N require ζN ∝1/N, which occurs for several relevant learning mappings.Source: A. Sensitivity dynamics and uniform… · pp. 11, 14

• The central object is the finite-horizon input-output mapping from data perturbation to terminal loss difference.Source: B. Robust performance interpretation · pp. 14–15
• Uniform stability requires bounding the terminal loss difference uniformly over test samples and neighboring datasets.Source: B. Robust performance interpretation · p. 15
• This structure matches a robust-performance problem in H∞/IQC theory, with a linear system driven by an exogenous disturbance.Source: B. Robust performance interpretation · p. 15
• The feedback interconnection contains a linear sensitivity-propagation system, a learned nonlinearity constrained by an IQC, and a sample-replacement channel.Source: B. Robust performance interpretation · p. 15
• The multiplier Π encodes prior knowledge about the learning mapping, while ρ controls how aggressively past sensitivity is discounted.Source: B. Robust performance interpretation · p. 15
• The certified sensitivity gain can be optimized over the certificate variables to tighten the bound for a chosen multiplier class.Source: B. Robust performance interpretation · p. 15

C. Optimizing the dynamical sensitivity gain

• The dissipativity-based perspective offers a direct optimization procedure for the sensitivity gain.Source: C. Optimizing the dynamical… · p. 16
• For fixed ρ, the matrix inequality becomes an SDP, while applying the resulting corollaries requires scalar search over [0, 1).Source: C. Optimizing the dynamical… · p. 16
• The optimized gain G⋆ yields the stability estimate η ≤κζNG⋆ and is the tightest bound certifiable by the chosen multiplier class.Source: C. Optimizing the dynamical… · p. 16

B. Gradient descent

• For gradient descent, bounded gradients imply ∥wk∥≤2B/N and therefore ζN ≤2B/N.Source: A. Gradient descent method · p. 17
• Under m-strong convexity and L-smoothness with α ∈(0, 2/(L + m)], gradient descent has contraction factor q < 1.Source: A. Gradient descent method · p. 17
• If α ∈(0, 1/L), the classical bound becomes η ≤2κB/mN.Source: A. Gradient descent method · p. 17
• The contraction factor determines how injected sensitivity accumulates: q < 1 gives geometric forgetting, q = 1 gives linear growth, and q > 1 can amplify perturbations.Source: A. Gradient descent method · p. 18
• The dissipativity theorem recovers the classical contractivity-based gradient-descent bound while assigning a systems-theoretic meaning to its factors.Source: A. Gradient descent method · p. 19

Modeling

• The heavy-ball iteration is recast as a lifted linear sensitivity dynamics with neighboring-data perturbations entering as an exogenous input.The representation uses the lifted state ˜xk := col(xk, xk−1) and matrices (AHB, BHB, CHB, DHB).Source: B. Heavy-ball algorithm · p. 19

Sensitivity bound

• A bounded-gradient assumption gives the one-sample disturbance bound ∥wk∥≤2B/N for all k ≥0.This bound supports applying the uniform stability corollary to the current-iterate hypothesis.Source: B. Heavy-ball algorithm · p. 19

Certificate

• The dissipativity certificate requires a storage function for which the closed-loop sensitivity interconnection dissipates the data-injection supply.This condition is weaker than requiring a pointwise one-step contraction estimate in a prescribed norm.Source: B. Heavy-ball algorithm · p. 20

Example

• For β = 1/4 and α = 3/4ˆϱN, the lifted heavy-ball dynamics has spectral radius 1/2 < 1 while ∥AHB∥>1.Thus the dynamics are Schur stable without being a strict Euclidean contraction.Source: B. Heavy-ball algorithm · p. 20

Implication

• Heavy-ball sensitivity nevertheless has finite data sensitivity gain, showing that the contractivity argument can fail while robust performance remains certifiable.Schur stability also permits standard Lyapunov arguments to construct a positive-definite storage certificate.Source: B. Heavy-ball algorithm · p. 20

Modeling

• The lifted Nesterov dynamics has a linear system representation with nonlinear input and system matrices (ANAG, BNAG, CNAG, DNAG).The uniform stability bound is obtained by solving the certificate conditions for this representation.Source: C. Nesterov’s accelerated gradient… · p. 21

Sensitivity bound

• Under bounded gradients, Nesterov’s neighboring-data disturbance satisfies ∥wk∥≤2B/N for all k ≥0.This yields a uniform stability bound for the current-iterate hypothesis.Source: C. Nesterov’s accelerated gradient… · p. 21

Example

• For β = 1/2 and α = 1/2ˆϱN, the lifted Nesterov dynamics has spectral radius 1/2 < 1 while ∥ANAG∥>1.The example establishes Schur stability without strict Euclidean contraction.Source: C. Nesterov’s accelerated gradient… · p. 21

Implication

• The same finite-gain conclusion as for heavy-ball applies to Nesterov’s lifted sensitivity dynamics.This demonstrates the usefulness of the dissipativity-based analysis when contractivity does not hold.Source: C. Nesterov’s accelerated gradient… · p. 21

Comparison

• The framework produces algorithm-specific certificates that compare iterative algorithms through both convergence rate and generalization capabilities.The comparison is enabled by optimizing the dynamical sensitivity gain.Source: C. Nesterov’s accelerated gradient… · p. 22

Momentum sweep

• For small momentum, heavy-ball and Nesterov gains are close to the gradient-descent baseline; increasing β rapidly increases the certified gain.The increase indicates greater amplification and longer memory of one-sample perturbations.Source: D. Numerical experiments · p. 23
• Heavy-ball loses certificate feasibility earlier than Nesterov, indicating a smaller certified robustness margin under the chosen storage and sector multiplier.Nesterov retains a larger feasible set of (α, β) combinations near the high-momentum boundary.Source: D. Numerical experiments · pp. 22–24

Convergence-sensitivity comparison

• Nominal convergence and data sensitivity are distinct properties: methods with comparable qnom can have substantially different certified gains.Nesterov attains smaller nominal convergence factors than gradient descent while maintaining moderate sensitivity over a wide β range, whereas heavy-ball’s gain rises rapidly.Source: D. Numerical experiments · pp. 23–24

Finite-horizon gains

• Although ζN scales as O(1/N), the dynamical gain multiplying it varies significantly with acceleration parameters.Smaller certified gains occur in more conservative regimes where qnom is close to one.Source: D. Numerical experiments · pp. 24–25

Learned feedback control

• In learned feedback control, empirical one-sample sensitivity and terminal closed-loop sensitivity corroborate the statistical-dynamical decomposition.The learned operator must generalize over closed-loop outputs, because approximation errors can propagate recursively and affect performance, constraints, or stability.Source: §V · pp. 25–26, Figure 6 · p. 26

Setup

• The control example learns a nonlinear residual correction offline and embeds it alongside a stabilizing nominal linear feedback.The residual has the form r(x) = −a tanh(v⊤x), while the plant is discrete-time linear.Source: A. KRR-based residual feedback control · pp. 26–27

Sensitivity mechanism

• Replacing one sample creates a neighboring dataset, a different learned controller, and a different closed-loop trajectory.The framework represents this perturbation as an exogenous disturbance in the sensitivity dynamics.Source: A. KRR-based residual feedback control · p. 27

Results

• The terminal closed-loop sensitivity exhibits the same sample-size decay, so reduced statistical perturbation is inherited by the closed-loop trajectories.This behavior persists with a nonlinear learned residual feedback.Source: A. KRR-based residual feedback control · p. 27

Interpretation

• The certificate separates one-sample operator sensitivity from dynamical amplification and is computable via semidefinite programming for comparing learning dynamics.It extends the analysis beyond optimization operators to offline-learned feedback control.Source: §VI · p. 28

Design implications

• Experiments show that nominal convergence and data sensitivity are distinct design objectives, motivating joint parameter co-design for both criteria.The algorithm realization enters the matrix inequality directly, enabling a potentially convex joint synthesis.Source: §VI · p. 28

General framework

• Replacing one sample changes the empirical average and provides the basic perturbation used to bound operator sensitivity.The framework compares an original dataset with the corresponding dataset after replacing the j-th sample.Source: A. One-sample sensitivity bounds for… · p. 30

Empirical mappings

• Bounded empirical averages and Lipschitz transformations yield sensitivity bounds proportional to 1/N for several operator classes.The listed classes include SAA mappings, Lipschitz transformations, and finite collections of empirical moments.Source: A. One-sample sensitivity bounds for… · pp. 30–31

Kernel operators

• Kernel mean embeddings satisfy ζN ≤ 2B/N when the feature-map norm is uniformly bounded by B.This gives an explicit one-sample sensitivity bound in the Hilbert-space setting.Source: A. One-sample sensitivity bounds for… · p. 31

Empirical minimizers

• Strong convexity and uniformly bounded sample-loss gradients control the change in empirical minimizers after sample replacement.The argument uses the optimality conditions of the two neighboring minimization problems.Source: A. One-sample sensitivity bounds for… · pp. 31–32

Regularized minimizers

• Regularized empirical minimizers satisfy ζN ≤ 2B/µN under µ-quadratic regularization and convex sample losses.The bound decreases with dataset size and improves with stronger regularization.Source: A. One-sample sensitivity bounds for… · p. 32

Additional operators

• The appendix also treats contractive fixed-point mappings and KRR in RKHSs as additional settings for deriving one-sample sensitivity bounds.The KRR result assumes bounded kernels and regularization, while the fixed-point result assumes contraction and Lipschitz dependence.Source: A. One-sample sensitivity bounds for… · pp. 32–33