CS Paper Radar

Robustness Analysis via Horofunction Compactification

Harrison Bennett, Amin Farjudian

cs.LO ·submitted 2026-09-17 19:03 UTC · v2
published

Abstract

Robustness analysis plays a central role in the verification and design of computational and hybrid systems, particularly when system behaviour depends continuously on parameters subject to perturbation. Existing domain-theoretic frameworks provide a principled foundation for reasoning about such perturbations via monotone maps on lattices of closed sets. However, these frameworks face significant limitations when the underlying state space is not locally compact, as is the case for the infinite-dimensional spaces that arise in analysis, machine learning, and control theory (e.g., $\ell_p$ and $L_p$ spaces). In these settings, the lattice of closed subsets fails to be continuous, and classical compactifications either sacrifice precision or lack computable structure. We propose Gromov's horofunction compactification as a new tool for robustness analysis over a class of separable metric spaces of practical importance, including separable reflexive Banach spaces. Given a metric space $\mathbb{S}$, we show that its horofunction extension yields a compact metric space together with a Lipschitz embedding, which enables robust approximations of monotone maps via Scott-continuous maps on the compactified domain. For separable spaces, the horofunction compactification is metrizable, which provides a path toward effective domain-theoretic constructions.

Comment
42nd Conference on the Mathematical Foundations of Programming Semantics (MFPS 2026)

Closest papers

Nearest neighbours by meaning across the whole index.

Scalable Neural Safety Certification via Monotonicity

eess.SY cs.LGmath.OC ·2026-11-08 ·Amirreza Alavi, Majid Zamani, Saber Jafarpour
similarity 0.60
Abstract

Learning-based safety certification offers a promising route for verifying complex dynamical systems when explicit models are unavailable, but existing data-driven methods often scale poorly: they treat the system as a black box, rely on dense discretizations or Lipschitz bounds, and consequently suffer from sample complexity that grows exponentially with dimension. This paper shows that a common structural property of dynamical systems--monotonicity--can be used to break this curse of dimensionality. We develop a data-driven framework for robust safety verification and safe controller synthesis for unknown monotone systems using only simulator queries. Our main theoretical result proves that, for monotone systems with upper-closed unsafe sets, safety is completely characterized by the existence of monotone inductive barrier certificates. This structure reduces certificate verification over continuous state spaces to localized boundary checks over finitely many cells. To learn such certificates, we introduce Max-Monotone Networks, a monotone neural architecture with universal approximation guarantees for monotone functions. We then propose a training and refinement algorithm that, upon successful termination, returns formally valid neural barrier certificates and, under mild partition assumptions, requires only $O(n)$ simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to $13{,}659$ states and traffic networks with $1{,}000$ states, our method certifies safety in regimes where prior approaches either do not converge or exceed memory limits. These results demonstrate that exploiting order structure can make neural safety certification both scalable and formally sound.

0.13

PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems

cs.CC ·2026-10-19 ·Manon Blanc
theory similarity 0.58
Abstract

Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.

0.29

Metrization of Quasi-Uniformities, Powerset Monads, and Qualitative Robustness Analysis

cs.LO math.GN ·2026-09-02 ·Francesco Dagnino, Amin Farjudian, Eugenio Moggi
theory similarity 0.57
Abstract · 24 pages

We study the relationship between quasi-uniform spaces, topological spaces, and quantale-valued metric spaces. Our main result is a metrization theorem establishing an equivalence between the category of quasi-uniform spaces and a category of quantale-valued metric spaces. We also obtain a quantale-based metrization theorem for arbitrary topological spaces that refines existing constructions. These results identify quasi-uniformities as the appropriate qualitative counterpart of quantale-valued metrics. Building on this correspondence, we show that the Hausdorff-Smyth monad on quantale-valued metric spaces, which is used in quantitative robustness analysis, arises as a lifting of a corresponding monad on quasi-uniform spaces along the equivalence. This provides a unified categorical framework connecting topology, quasi-uniformity, and quantitative robustness analysis.

0.23

Abstract Lipschitz Continuity

cs.PL ·2026-10-27 ·Marco Campion, Isabella Mastroeni, Michele Pasqua, Caterina Urban
similarity 0.57
Abstract

We introduce Abstract Lipschitz Continuity (ALC), an extensional property of functions, in particular of program semantics, requiring that bounded differences between properties of two inputs yield proportionally bounded differences between properties of the corresponding outputs. ALC explicitly discerns between two complementary forms of approximation: property-based (or qualitative) approximations, which retain a property of the data and are formalized by upper closure operators as in abstract interpretation, and quantitative approximations, which measure the closeness of data and are formalized by pre-metrics, a weakening of metrics that covers the distances arising in program analysis. Keeping the two forms of approximation explicit has two main benefits. First, it allows us to precisely relate ALC to established extensional properties: ALC is a sufficient condition for partial completeness in abstract interpretation, for partial abstract non-interference in language-based security and, with a null Lipschitz constant, for abstract robustness in machine learning. Second, it supports reasoning about ALC of program semantics by induction on the syntax of programs: we present a sound deductive system, parametric in the property-based approximations and in the pre-metric of interest, that reduces a proof of ALC for a program to proofs for its basic commands and to some explicit side conditions, which isolate what makes ALC compositional across sequential composition, non-deterministic choice and iteration.

0.30

Robust Deep Prototype Classifiers via Lipschitz Training

cs.LG cs.AI ·2026-11-06 ·Adia Khalid Khan, Lukas Gehring, Benjamin Paaßen
theory similarity 0.52
Abstract

Robustness and interpretability are interrelated and desirable properties of machine learning models. A model that changes its prediction under imperceptible perturbations behaves inconsistently with human-recognizable features and, hence, is not interpretable. Prototype-based classifiers such as Generalized Learning Vector Quantization address both at once. They are interpretable by construction because they make the decision by comparing the input to the prototypical example; and their hypothesis margin yields a closed form robustness certificate. However, on high-dimensional data, these shallow models need deep embedding networks to achieve high accuracy, and this voids the robustness certificate. The margin is a statement about distances in the embedding space, and an unconstrained network can map an arbitrarily small input perturbation to arbitrarily large attacks in the embedding space. We close this gap with a theorem: if the embedding network is locally L-Lipschitz around a point, and the classifier is ε-robust around its embedding, then the full model is ε/L-robust in the input space. Based on this, we propose a Lipschitz training scheme to achieve L-Lipschitz properties for embedding networks. We evaluate three classification heads (linear, linear Support Vector Machine, and GLVQ) crossed with two embedding networks (standard and Lipschitz-constrained) on MNIST, CIFAR-10, and Imagenette-160, under FGS, PGD and C\&W attacks. The evaluation results show that combining a prototype-based head with a Lipschitz-constrained embedding provides the strongest robustness. This suggests that the Lipschitz constraint provides an additional robustness benefit in addition to the advantage provided by the prototype-based head. Since the Lipschitz constraint is enforced by sampling rather than by construction, the reported robustness is empirical rather than certified.

0.16

Exact Decisions and Certified Values in $L_\infty$-Norm Computation from State-Space Representations

cs.SC math.OC ·2026-11-11 ·Alban Quadrat, Fabrice Rouillier, Grace Younes
benchmark similarity 0.52
Abstract · 6 pages, 1 table. Submitted to the European Control Conference (ECC 2027)

Computing the $L_\infty$-norm of a time-invariant linear ordinary differential control system is a routine task in robust control, usually delegated to floating-point routines that perform well on most practical systems. Behind the numerical value, however, lies a discrete decision: whether a pole lies on the imaginary axis, and whether a mode of a realization is actually a pole of the transfer matrix. Floating-point arithmetic can only replace this decision with a tolerance. This paper explains, for a control audience, what reliable symbolic-numeric computation offers for this problem: exact arithmetic where a decision has to be made, and certified enclosures where a value has to be computed. We show how the problem is turned into a small polynomial system directly from state-space data, how this system is solved in practice, and what it costs. A benchmark on the {\tt COMPleib} library and on families of systems with known norms shows that two standard numerical routines err in opposite directions on the imaginary-axis decision, and never on the same system, while the certified method decides it correctly on every instance tested and computes the norm at a cost comparable to that of the numerical routines on most systems. We conclude with practical guidelines for users of numerical tools.

0.41

A Measure-Geometric Theory of Robustness in Machine Learning

cs.LG stat.ML ·2026-10-23 ·Cheng-Chao Huang
unusual similarity 0.51
Abstract

This paper develops a foundational measure-geometric theory of robustness in machine learning. Robustness is formulated as escape from a retained task state relative to a reference measure on a data-bearing manifold, a perturbation gauge, and an admissible realization mechanism. The theory distinguishes the structural possibility of escape on the reference manifold from its ambient realization under mechanism-dependent observable readouts, while placing both within a unified geometric account. It introduces a mesoscopic organization of escape geometry, through which vulnerable mass, finite-scale morphology, delivered progress, and branch coherence are characterized by explicit laws as linked but non-identical robustness phenomena. By recasting robustness as the geometric formation, organization, realization, and persistence of escape, the theory provides a structural basis for analysis beyond scalar criteria.

0.25

The Geometry of Limits in ReLU Function Spaces

cs.LG math.FAmath.GNmath.MG ·2026-10-24 ·Kathryn A. Lindsey
theory similarity 0.51
Abstract · 37 pages

We study the geometry and closure of spaces of functions realized by ReLU neural networks of fixed architecture. We first establish a general result about limits of continuous piecewise-linear (CPWL) functions: the minimum number of convex sets on which a function is affine is lower semicontinuous under pointwise convergence. The proof uses a connection to hypergraph coloring and a compactness principle, and yields quantitative bounds on the polyhedral complexity of continuous limits. We then characterize the functions realizable by shallow ReLU networks with vector-valued outputs, extending a known scalar-valued characterization. Using this and the geometry of limiting hyperplane arrangements, we prove that fixed-width shallow scalar ReLU realization spaces are closed in the weighted supremum norm on the whole input space. In contrast, we construct an explicit sequence of networks with architecture $(2,3,2\mid1)$ whose limit is not realizable by that architecture. Non-closedness holds both globally in weighted supremum norm and under uniform convergence on compact sets with nonempty interior, disproving a conjecture of Petersen, Raslan, and Voigtlaender. Finally, we show that non-closedness for a fixed scalar-output ReLU architecture necessarily involves a \emph{blow-up residue}, in which diverging output coefficients amplify an emerging linear dependence among hidden features. Together, these results provide geometric and functional-analytic tools for studying the boundaries and degenerations of ReLU realization spaces.

0.21