Category Theory · Cross-listed from cs.LO
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Monday 27 July
Categories with finite biproducts play a central role in category theory, providing an abstract setting in which additive and linear structures can be studied uniformly. In this paper, we introduce categories with convex biproducts, which intuitively restrict the linear structures to convex ones. We show that, whereas categories with finite biproducts give rise to a matrix calculus based on arbitrary linear combinations, convex biproduct categories instead induce a matrix calculus based on stochastic (more generally, substochastic) matrices. This perspective yields a refined algebraic and compositional framework tailored to probabilistic settings. We exploit this connection to establish an isomorphism that underpins probabilistic tape diagrams, a graphical formalism for bimonoidal (also known as rig) categories, and we demonstrate its effectiveness by providing a complete axiomatisation of probabilistic Boolean circuits.
Analysis of PDEs
Non-singular hotspots between closely spaced high-index nanoparticles
We study the concentration of the field between two nearly touching high-index dielectric resonators in three dimensions. The model is a scalar Helmholtz transmission problem in the resonant regime, wherein the wavelength inside the resonators of the same order as their typical diameter. The material contrast enters only a lower-order term of the equation and not its principal part. As a consequence, the gradient of the field stays bounded independently of the distance separating the particles, and does not blow up. Nevertheless, simulations and experiments show that the gradient still concentrates in the gap: as the particles approach, it grows like the inverse of their separation over an intermediate range of distances and then saturates once they are very close. We explain this pre-asymptotic effect through a weak-coupling regime, in which the resonant modes of the pair are perturbations of the modes of each isolated particle. When such a mode keeps a nonzero contrast between the two facing boundaries, a mean value argument across the gap accounts for the growth of the gradient; this requires strengthening the standard spectral perturbation estimates from an average to a pointwise control. The growth stops once the interaction between the particles is no longer weak and the perturbation theory fails. Numerical experiments confirm the transition from amplification to saturation.
Read the full abstract
Information Theory
On the Power Distance Representation of Bregman Divergences
We express Bregman divergences between parameters as power distances between corresponding weighted points, and investigate several applications of this representation. First, we show that the Bregman closest pair and diameter problems can be reformulated as bichromatic weighted point problems under the power distance. This reformulation enables Bregman nearest and farthest neighbor queries under power distances to be handled in practice through corresponding Euclidean neighbor queries in one additional dimension, after offsetting the weights. Next, we revisit the problem of computing minimum enclosing Bregman balls (Bregman MEBs) and establish their equivalence to double-sided weight power MEBs. We further show that Bregman MEBs can be approximated by relaxing the double-sided weight power MEB problem to its single-sided weight counterpart. We then present two approaches to solving general power MEB problems: An exact algorithm based on the LP-type framework and an arbitrarily accurate approximation scheme based on iterative Frank-Wolfe optimization. Finally, we show that the potential-function lifting transformations used to construct Bregman Voronoi diagrams can be reinterpreted as classical paraboloid lifting transformations applied to the corresponding weighted point sets. This establishes a direct connection between Bregman Voronoi diagrams and power diagrams, further illustrating how Bregman divergences can be represented as power distances.
Read the full abstract
Optimization and Control
Automatic Model-Order Selection for Nonnegative Matrix Factorization via Column $\ell_{2,0}$ Regularization
Nonnegative matrix factorization represents nonnegative signals as additive combinations of latent components, but its factorization rank, and hence the model order, must usually be specified beforehand. An underestimated order discards signal structure, whereas an overestimated order produces redundant components and unstable decompositions. We propose a column $\ell_{2,0}$-regularized formulation that estimates the model order from an initial upper bound by suppressing inactive columns in both factors. A warm-started regularization path progressively removes redundant components without changing the factor dimensions, and a marginal reconstruction-loss criterion selects an order along the path. To solve the resulting nonconvex and discontinuous problem, we develop an inertial proximal alternating linearized minimization method, a scale-balanced variant, and a proximal active-set method based on P-stationarity. The balancing operation equalizes the norms of paired factor columns while preserving their rank-one products. We characterize the critical points and local minimizers of the model, provide a sufficient-condition result for rank recovery, and prove whole-sequence convergence of the proposed algorithms under explicit step-size and inertial-parameter conditions using the Kurdyka–Łojasiewicz framework. Dedicated experiments show that the warm-started $\lambda$-path is more efficient than increasing- and decreasing-order discrete $r$-paths, while scale balancing yields a more stable rank-selection path. Experiments on synthetic data and diverse signal benchmarks show that both iPALM and PASM provide reliable model-order estimates with favorable computational efficiency.
Read the full abstract
Information Theory
LLM-based Source Code Compression via Thresholded Symbol Ranking
We study the problem of lossless compression of source code, motivated by the storage demands of large-scale software archives, such as Software Heritage (https://www.softwareheritage.org/). General-purpose compressors (e.g., zstd, bzip2) offer a good trade-off between compression ratio and speed, but fail to exploit all special regularities inherent in source code. Recent approaches leverage Large Language Models (LLMs) within Shannon's symbol-ranking framework, relying on a scheme in which the predicted rank can grow arbitrarily. While effective at reducing space, this setting incurs significant throughput degradation, and leaves open the question whether it is necessary to explicitly encode all ranks. In this work, we introduce LLM-based compressors deploying two novel symbol-ranking variants that bound predictions to the top-$T$ ranks ($T=1$ or $63$), with out-of-threshold symbols stored as exceptions and compressed jointly with the rank stream via general-purpose compressors. We conduct the first large-scale evaluation of LLM-based source code compression across 30 LLMs, including general-domain, code-specialized, and quantized models. Our $T$-bounded approach outperforms prior LLM-based compressors both in compression ratio (up to 37% relative improvement) and compression throughput (40% faster). Compared to general-purpose compressors (e.g., zstd, bzip2), we obtain up to 82% relative compression gain but at a lower speed, thus offering a new trade-off point in the compression-speed spectrum. We also show that these gains are stronger on source code than on natural language, suggesting an interesting indication, namely that source code exposes regularities captured by LLMs but missed by general-purpose exact-match-based compressors. We conclude by commenting on open problems that offer theoretical and practical avenues of research.
Read the full abstract
Group Theory
The Diophantine problem in the Baumslag-Gersten group
We show that, for every positive prime number $p$, the Baumslag-Gersten group $G_p = \langle a, t \mid (tat^{-1}) a(tat^{-1})^{-1} = a^p \rangle$ has an undecidable Diophantine problem. This gives the first known examples of one-relator groups with undecidable Diophantine problems. Furthermore we apply this to show that the one-relator group $G_p \ast \mathbb{Z}$ has an undecidable single equation problem.
Read the full abstract
Mathematical Physics
A doubled Gordon threshold for palindromic quasiperiodic Schrödinger operators
We consider one-frequency quasiperiodic Schrödinger operators \[ (H_{v,\alpha,\theta}u)(n) = u(n+1)+u(n-1) + v(\theta+n\alpha)u(n) \] acting on $\ell^2(\mathbb Z)$, where $\alpha\notin\mathbb Q$ and $v\in C^2(\mathbb T,\mathbb R)$ is an even function. We develop a new Gordon-type method that exploits approximate repetitions and palindromic symmetries simultaneously. Denote by $L(E)$ the Lyapunov exponent and let \[\beta(\alpha) = \limsup_{|k|\to\infty} -\frac{\log\|k\alpha\|_{\mathbb R/\mathbb Z}}{|k|}. \] We prove that, for every completely resonant phase $2\theta\in\alpha\mathbb Z+\mathbb Z$, $E$ cannot be an eigenvalue if $L(E)<2\beta(\alpha)$. As an application, consider the almost Mathieu operator \[ (H_{\lambda,\alpha,\theta}u)(n) = u(n+1)+u(n-1) + 2\lambda\cos\bigl(2\pi(\theta+n\alpha)\bigr)u(n). \] We show that if $2\theta\in\alpha\mathbb Z+\mathbb Z$ and $1<|\lambda|<e^{2\beta(\alpha)}$, then $H_{\lambda,\alpha,\theta}$ has purely singular continuous spectrum. This resolves the remaining absence-of-eigenvalues part of a conjecture of Avila and Jitomirskaya concerning the sharp spectral transition for completely resonant phases.
Read the full abstract
Combinatorics
Kazhdan-Lusztig polynomials of matroids need not be unimodal
We construct, over every finite field, representable matroids whose Kazhdan-Lusztig polynomials are not unimodal. In particular, the conjectures that all Kazhdan-Lusztig polynomials of matroids are log-concave and that they are real-rooted are both false. Our examples are obtained by deleting points from finite projective geometries. More generally, we prove that, under a half-rank degree condition in each contraction quotient, the Kazhdan-Lusztig polynomial of every contraction enumerates the subspaces whose projective points lie in the corresponding deleted set, while the $Z$-polynomial agrees with that of the full projective geometry.
Read the full abstract
Information Theory
Secrecy Energy Efficiency for IRS-Assisted Low-Altitude Communications: A D3QN-PER Based Approach
To address the security and energy efficiency challenges in low-altitude economy (LAE) wireless communications, we develop a secure synergistic network integrating unmanned aerial vehicle (UAV) and intelligent reflecting surface (IRS), with an emphasis on maximizing secrecy energy efficiency (SEE) for downlink transmission scenarios. In particular, firstly, we establish the channel transmission models for UAV-IRS assisted LAE communications network. Then, we formulate a non-convex fractional optimization problem for SEE maximization, involving three tightly coupled variables, i.e., the beamforming, IRS phase and UAV trajectory. To tackle the fractional structure and variable coupling, Dinkelbach's method and equivalent transformations are leveraged to reformulate the objective function, which is then decoupled and decomposed into three independent subproblems via an alternating optimization strategy for iterative resolution. Slack variables and Semidefinite Relaxation (SDR) are further employed to convexify the subproblems of beamforming and IRS phase shift optimization, thereby obtaining their optimal solutions. For the UAV trajectory optimization subproblem, we propose a D3QN-PER algorithm, which integrates a Dueling Double Deep Q-Network with Prioritized Experience Replay, to tackle the slow convergence and training instability inherent in conventional Deep Q-Network (DQN). Numerical simulations validate the performance for our proposed joint optimization scheme. Comparative results demonstrate that the developed D3QN-PER-based algorithm outperforms existing state-of-the-art learning approaches which verifies its superiority in improving SEE for UAV-IRS-assisted LAE wireless communications network.
Read the full abstract
Dynamical Systems
Hausdorff dimension of non-uniquely ergodic directions in eigenform loci
We consider the eigenform locus $\mathcal{E}_D$ in $\mathcal{H}(1,1)$ where $D$ is not a square. We prove that for any translation surface $(X,\omega) \in \mathcal{E}_D$, the set of non-uniquely ergodic directions has Hausdorff dimension $1/2$, except when $D=5$ and $(X,\omega)$ lies in the Teichmüller curve generated by the regular decagon.
Read the full abstract
Representation Theory
The proper stable module category of a group algebra
We introduce the proper stable module category for an arbitrary discrete group over any commutative ring by means of cotorsion pairs and abelian model structures. This category is a well-generated tensor-triangulated category and is compactly generated in case the commutative ring is regular. Our construction resembles the topological approach via proper equivariant stable homotopy theory. Moreover, it agrees with the Mazza-Symonds stable module category, whenever the latter is defined, and with various other stable categories associated to hierarchically defined groups. Along the way, we introduce certain homological dimensions and study them in detail, comparing them with the classical notions.
Read the full abstract
Probability
On non-monotonicity of logarithmic energy for random matrices
We construct a finite-energy Wigner counterexample and a concrete one-parameter family of Gaussian-regularised Bernoulli entry laws yielding counterexamples to the conjectural dimensional monotonicity of the quadratically penalised logarithmic energy for mean empirical spectral distributions by Chafaï, Dadoun, and Youssef.
Read the full abstract
Analysis of PDEs
Supersolution Construction and Optimal Hardy Inequality for Fractional Laplacians
We give a new criterion to show optimality of Hardy weights for general operators on graphs via the supersolution construction. For Laplacians on graphs without killing terms this always gives rise to an optimal Hardy weight via the Green's function without any further assumptions. Furthermore, in contrast to earlier results, our result is not restricted to locally finite graphs. This allows us in particular to obtain optimal Hardy weights for the fractional Laplacian on general graphs. For the fractional Laplacian on the Euclidean lattice, we then obtain an optimal Hardy weight with the constant and asymptotics as it is expected from the continuous setting.
Read the full abstract
Probability
Strong convergence of Euler-Maruyama schemes for additive fractional SDEs with Lipschitz drift
We study the strong convergence rate of the Euler–Maruyama scheme for additive stochastic differential equations driven by a fractional Brownian motion with Hurst parameter $H\in(0,1)$. Assuming the drift coefficient to be Lipschitz continuous, we establish strong convergence bounds of order $1$ if $H\in(1/2,1)$, and $1/2+H-\varepsilon$, for any $\varepsilon>0$, if $H\in(0,1/2]$. The main ingredient is a shifted stochastic sewing argument, which exploits the conditional Gaussian structure of fractional Brownian motion to control the noise discretization error.
Read the full abstract
Probability
The KLS constant is $O(\log^{1/4} n)$
We confirm the Kannan–Lovász–Simonovits conjecture for quadratic forms: if $X \sim \mu$ is an isotropic log-concave random vector in $\mathbb{R}^n$, then for any symmetric matrix $M$ one has $$ \operatorname{Var}_{X \sim \mu}(\langle MX,X\rangle) \leq 2\,\mathbb{E}_{X \sim \mu}|\nabla\langle MX,X\rangle|^2. $$ As an application, we apply the above to $M=\mathbb{E}_{X \sim \mu}(\langle X,\theta\rangle X\otimes X)$ for $\theta\in S^{n-1}$ and show that the Kannan–Lovász–Simonovits constant $\psi_n$ satisfies $$ \psi_n\leq C\log^{1/4}n $$ for some absolute constant $C>0$.
Read the full abstract
Number Theory
Slowly Divergent Trajectories for Weighted Singular Vectors in R^2
Let $w=(w_1,w_2)$ satisfy $w_1>w_2>0$ and $w_1+w_2=1$. For every function $f:[0,\infty)\to(0,\infty)$ with $f(t)\to0$, we prove that the set of $w$-singular vectors whose weighted shortest-vector function satisfies $W_x(t)\ge\log f(t)$ for all sufficiently large $t$ has Hausdorff dimension $s_w=2-(1+w_1)^{-1}$, equal to the full Hausdorff dimension of $\operatorname{Sing}_w(2)$. For every $0<\nu<1$ and $\mu>0$, a separate power schedule gives Hausdorff dimension $s_w$ for the weighted uniform approximation set with rate $Q^{-1}\exp\bigl(-\mu(\log Q)^\nu\bigr)$, whereas the lower-envelope theorem gives the same dimension for its complement in $\operatorname{Sing}_w(2)$. We give a direct proof of the lower-envelope theorem by adapting the self-affine construction of Liao–Shi–Solan–Tamam to a variable sequence of return times and using an empty-denominator-window argument to control intermediate cusp excursions without further pruning the tree.
Read the full abstract
Symplectic Geometry
Namikawa–Weyl groups of symplectic quotient singularities
We classify the Namikawa–Weyl groups associated to symplectic quotient singularities $V/G$ when $G$ is a symplectic reflection group. Our classification shows that every irreducible Weyl group can be realized as a factor of the Namikawa–Weyl group of $V/G$ for a suitable $G$.
Combinatorics
Nerve-type and invariance theorems for asymptotic dimension
Asymptotic dimension of metric spaces is a large-scale analog of covering dimension of topological spaces. An intersection graph of a family of sets is the graph whose vertices are the members of the family and whose edges correspond to pairs of members with non-empty intersection. Our first main result connects the asymptotic dimension of the intersection graph of a family ${\mathcal F}$ and the Assouad-Nagata dimension of the ambient metric space containing members of ${\mathcal F}$ under some mild and necessary assumptions. We prove that if ${\mathcal F}$ is a family of subsets of a metric space of Assouad-Nagata dimension $n$ such that every ball of radius $r$ intersects at most $f(r/s)$ pairwise disjoint members of ${\mathcal F}$ of diameter at least $s$ for some function $f$, then the asymptotic dimension of the intersection graph of ${\mathcal F}$ is at most $n+1$. This result is optimal both quantitatively and qualitatively in several senses. As a corollary of this result, the asymptotic dimension of the intersection graph of any family of compact convex sets of bounded aspect ratio in ${\mathbb R}^n$, such as a family of balls in ${\mathbb R}^n$, is at most $n+1$. Our second main result states that the asymptotic dimension of the intersection graph of a family ${\mathcal F}$ of connected closed sets of a connected topological space with connected boundary equals the asymptotic dimension of the intersection graph of the family of the boundary of the sets in ${\mathcal F}$, under a mild condition. In particular, the asymptotic dimension of the intersection graphs of families of spheres in ${\mathbb R}^n$ equals $n$ or $n+1$ when $n \geq 2$.
Read the full abstract
Algebraic Geometry
Roots of Bernstein-Sato polynomials for projective hypersurfaces with ordinary double points
Let $X\subset{\mathbb P}^{n-1}$ be a hypersurface of degree $d\ge3$ with ordinary double points, where $n\ge3$. The roots of Bernstein-Sato polynomial of its defining polynomial $f$ are given up to sign by 1, $(n-1)/2$, and $j/d$ for $j\in{\mathbb Z}\cap[n,nd-n-p_f]$ with $p_f$ a positive integer. Here $p_f$ is bounded above by the minimal positive integer $q_s$ satisfying $\binom{q_s+n-1}{n-1}>s:=|{\rm Sing}\,X|$, and we can verify that $p_f$ coincides with $q_s$ in the case the singular points of $X$ are in “general position". We show that this upper bound is sharp in the case $\binom{\lfloor d/2\rfloor+n-2}{n-1}\ge s$ or $\binom{d+n-3}{n-1}\ge sn$ by providing a homogeneous polynomial of degree $d$ such that the associated projective hypersurface has ordinary double points at given $s$ points in sufficiently general position and is nonsingular outside them (using a theorem of Alexander and Hirschowitz for the second case). It is conjectured that the above sharp bound under the first hypothesis can be extended naturally to the case where $X$ has only $A_2$-singularities instead of ordinary double points.
Read the full abstract
Complex Variables
Perron envelopes with globally bounded minorants
Let $f$ be an upper semicontinuous function on a domain $\Omega$, and let $V$ be the Perron envelope of $f$ formed only with subharmonic minorants that are bounded above on all of $\Omega$. The usual argument for upper semicontinuity of Perron envelopes breaks down, since the regularization $V^*$ need not be bounded above; one only knows that $V=V^*$ outside a polar set. We show that nevertheless $V=V^*$ everywhere in $\mathbb{R}^d$, using a local harmonic correction given by a Poisson integral on a ball. The plurisubharmonic analogue fails. We construct an explicit bounded B-regular Hartogs domain in $\mathbb{C}^n$, $n\geq2$, and a positive pluriharmonic function $W$ whose envelope of bounded-above plurisubharmonic minorants equals $W$ off an analytic disc and vanishes on it, although $W$ admits a positive plurisuperharmonic majorant $G$ with $W\leq\varepsilon G+C_\varepsilon$ for all $\varepsilon>0$. For pluriharmonic $W$, we show that the envelope recovers $W$ exactly on the union of the sets where such majorants are finite. The question arises in the study of quasibounded plurisubharmonic functions.
Read the full abstract
Numerical Analysis
Randomized Krylov-Projected Iterated Tikhonov Regularization for Large-Scale Ill-posed Problems Under A Posteriori Stopping Rule
We introduce two novel randomized iterative regularization frameworks, termed RIGKT and RIAT, for solving large-scale linear ill-posed inverse problems governed by systems of equations. The proposed methods combine randomized iterated Tikhonov regularization with Krylov subspace projection techniques, utilizing Golub–Kahan bidiagonalization for general rectangular systems (RIGKT) and Arnoldi decomposition for square systems (RIAT). Unlike existing deterministic schemes that rely on fixed iteration counts, our framework incorporates randomized equation selection, an adaptive step-size strategy, and a global, discrepancy-based a posteriori early-stopping rule tailored specifically to the stochastic setting. We present a comprehensive regularization analysis establishing Bregman-distance monotonicity, finite termination, exact-data convergence, and pathwise stability under noise. Furthermore, we prove that the stopped iterates converge almost surely and in the mean-square sense to the true solution, establishing a rigorous regularization property. To the best of our knowledge, this is the first theoretical framework to simultaneously account for randomization, Krylov-subspace dimension reduction, and implementable early stopping. Numerical experiments involving two-dimensional X-ray computed tomography (CT) and image deblurring demonstrate that RIGKT and RIAT reliably reconstruct structural features across various noise regimes.
Read the full abstract
History and Overview of Mathematics
How to read Mathematics? A study guide
Reading a math textbook isn't like reading a novel. You've probably already figured that out on your own. But how *do* you read mathematical texts? And how can you actually learn from a book or lecture notes? This document is a guide to independently reading and working through mathematical texts. Originally written as supplementary material for a flipped classroom course for first year math students it may serve as a detailed reading guide for anybody interested in math.
Read the full abstract
Analysis of PDEs
Global Existence and Pathwise Uniqueness for a Stochastic Parabolic-Parabolic Keller-Segel System
In this paper, we study a stochastic parabolic-parabolic Keller-Segel system driven by nonlocal, nonlinear multiplicative noise in a two-dimensional bounded domain. Under suitable assumptions, we establish global existence and pathwise uniqueness of a strong solution for arbitrary initial data, without imposing any smallness conditions. This sharply contrasts with the deterministic two-dimensional Keller-Segel system, which typically requires smallness assumptions on initial mass. The main analytical challenges stem from the fully parabolic coupling, combined with a lack of coercivity and global Lipschitz continuity in both the chemotactic drift and noise terms. To overcome this, we introduce a tailored truncated system to establish local existence via Banach's fixed point theorem. Using this local existence and pathwise uniqueness, we construct a maximal local strong solution. Finally, by introducing a specialized Lyapunov functional, we derive uniform estimates to extend this solution globally.
Read the full abstract
Group Theory
Brauer Relations for Symmetric Groups: Young–Wreath Quotients and the n-Cycle Mark Obstruction
Let $K(S_n)$ be the kernel of the linearization map from the Burnside ring of the symmetric group $S_n$ to its rational representation ring. We denote by $N_n$ the free $\mathbb{Z}$-sublattice with basis given by the standard Brauer relations $\Theta_H$, indexed by the $S_n$-conjugacy classes of subgroups that are either intransitive or transitive imprimitive and are not conjugate to Young subgroups. We also let $J_n$ be the $\mathbb{Z}$-lattice of relations induced from the kernels of the linearization maps for proper Young subgroups and standard wreath subgroups $S_a\wr S_b$, and put $O_n=N_n/J_n$. For every composite integer $n\geq 4$, we construct, using the $C_n$-mark and the Young section, an integral homomorphism $\omega_n:N_n\to\mathbb{Z}$ and prove directly over $\mathbb{Z}$ that $J_n=\ker(\omega_n|_{N_n})$ and $O_n\cong\mathbb{Z}$. We further construct a natural comparison homomorphism from $O_n$ to the primitive quotient $\operatorname{Prim}(S_n)$, obtained by factoring out all imprimitive relations arising from proper subquotients. Combined with the classification theorem of Bartel–Dokchitser, this shows that $O_n\xrightarrow{\sim}\operatorname{Prim}(S_n)$ for composite $n\geq 6$, while for $n=4$ the comparison map is reduction modulo $2$ under the identifications $O_4\cong\mathbb{Z}$ and $\operatorname{Prim}(S_4)\cong\mathbb{Z}/2\mathbb{Z}$. On the other hand, for prime $n\geq 5$, one has $O_n=0$, whereas $\operatorname{Prim}(S_n)\cong\mathbb{Z}$. Finally, we study the monomial Burnside ring over $C_2$ and show, via an additive map that we call index-two permutation reduction, that the resulting quotient is canonically isomorphic to the ordinary Young–wreath quotient.
Read the full abstract
Classical Analysis and ODEs
Optimal bounds for the ratio of differences of quadratic, arithmetic, and harmonic means
We determine the optimal constants in inequalities comparing the differences of the quadratic, arithmetic, and harmonic means of $n$ nonnegative real numbers. Specifically, we prove that for $n\ge3$ the sharp double inequality \[ \frac{1}{\sqrt{n}}\le \frac{A_n-H_n}{Q_n-H_n}\le \sqrt{\frac{n-1}{n}} \] holds true. This extends earlier results by T. Mitev, which established the sharp bounds only for the cases $n=3,4,$ and $5$. Our approach is based on a variant of the classical optimization method of Cauchy and Maclaurin, in which a quadratic symmetric function is optimized under simultaneous constraints on the arithmetic and harmonic means.
Read the full abstract
Optimization and Control
On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs
In this paper, we exhibit a randomized first-order algorithm to compute Goldstein approximate second-order stationary points of $L$-smooth functions, using tools from randomized smoothing. The algorithm has oracle complexity $\widetilde{O}({ n^2}/{\varepsilon^9}+{ n^3}/{\varepsilon^7})$, where $n=1,2,\ldots$ is the input dimension and $\varepsilon>0$ is the (common) tolerance. We also present extensions to weakly convex functions and applications to bilevel optimization.
Read the full abstract
Dynamical Systems · Cross-listed from physics.soc-ph
Nonlinear Model Reduction of Complex Networks via Spectral Submanifolds
Complex networked systems are prevalent in biology, engineering, and the social sciences, yet their high-dimensional, nonlinear dynamics pose major challenges for analysis and prediction. A mathematically rigorous route to simplification is to represent system behavior on a low-dimensional, smooth invariant manifold known as a spectral submanifold (SSM). Here we present a comprehensive SSM reduction framework and its globalized extension (gSSM) for dimensionality reduction in large-scale nonlinear networks. Our approach yields accurate global and node-level predictions across synthetic and real networks, including highly heterogeneous topologies and systems with higher-order interactions. Crucially, SSM is a robust tipping-point predictor: even at low truncation order (e.g., $O(2)$) it reliably identifies the onset of sustained activity, while higher orders and gSSM capture post-onset amplitudes and saturation. Consistently, the reduction collapses the full network dynamics to a one-dimensional system, offering clarity and efficiency. Across all the realizations, SSM/gSSM consistently outperform classical spectral and mean-field methods in modeling critical transitions at both microscopic and macroscopic scales, establishing SSM-based reduction as a robust, interpretable tool for nonlinear networked systems with broad applicability to epidemiology, ecology, and engineered networks.
Read the full abstract
Optimization and Control
On the hardness of deterministic second-order optimization of functions with Lipschitz gradients
We show that no deterministic zero-respecting algorithm (resp., (general) deterministic algorithm) can compute Goldstein approximate second-order stationary points of functions with Lipschitz continuous gradients within a finite number of (resp., no more than $n-3$ with $n$ being the input dimension) second-order oracle calls. This, among other consequences, shows that deterministic second-order weakly convex optimization is intractable.
Read the full abstract
Optimization and Control
Optimal Control with Expectation Constraint in a Smooth Boundary Case
As in Bouchard et al. (2010) and Bouchard and Nutz (2014), we study a utility maximization problem with expectation constraint. We first consider a uniformly elliptic case in which the endogenous state boundary associated with the constraint in expectation is proved to be smooth. This allows one to derive a proper Dirichlet condition for the value function of the optimal control problem on this boundary. We then propose a new truncation argument in the martingale representation of the expectation constraint. This leads to an approximating sequence of auxiliary systems of PDEs for which comparison holds. Convergence to the initial optimal control problem is proved. In the degenerate case, we propose another approximation which consists in adding a small noise term to recover uniformly ellipticity. Convergence is also proved. To the best of our knowledge, it is the first time that a full analysis is performed for such control problems, so as to open the doors to the use of numerical schemes. Numerical resolution in a toy example is performed using neural networks. It is complemented by an estimation of the numerical error, also performed by using a neural network approach.
Read the full abstract
Representation Theory
On Representations of Weyl Groups attached to Spherical Varieties
To any smooth spherical $G$ variety $X$ we attach two representations of the Weyl group of $G$. The first is constructed geometrically using Borel Moore homology. The second is constructed combinatorially using the structure of the Borel orbits on $X$. Using the Fourier Sato transform, we show that both representations are isomorphic. We use this result to translate (in the cotangent case) a conjecture of Finkelberg-Ginzburg-Travkin in the relative Langlands program to a combinatorial problem. We solve this combinatorial problem for several examples.