Optimization and Control · Cross-listed from cs.LG
Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints
Mohammad S. Alkousa, Fedor S. Stonyakin, Belal A. Alashqar et al. (+1 more)
Variational inequalities play a key role in machine learning research, such as generative
adversarial networks, reinforcement learning,
adversarial training, and generative models. This paper is devoted to the constrained variational inequality problems with functional constraints (inequality-type constraints). We propose some mirror descent-type
algorithms that switch between productive and non-productive steps depending on the values of the functional constraints at iterations, with many different step size rules and stopping criteria. We analyze the proposed
algorithms and prove their optimal convergence rate to achieve a solution with desired accuracy, for problems with bounded and monotone operators and Lipschitz convex functional constraints. In addition, we propose a modification of the proposed
algorithms by considering each functional constraint in the calculation when we have a productive step, as well as the first constraint that violates the feasibility. This modification can save the running time of
algorithms when we have many functional constraints. In addition, we provide an analysis of the proposed
algorithms for $\delta$-monotone operators, allowing us to apply the proposed
algorithms, as a special case, to constrained minimization problems when we do not have access to the exact information about the subgradient of the objective function. Numerical experiments that illustrate the work and performance of the proposed
algorithms are also given.
Read the full abstract ▾
All authors Mohammad S. Alkousa, Fedor S. Stonyakin, Belal A. Alashqar, Seydamet S. Ablaev
Optimization and Control · Cross-listed from cs.RO
A GPU-Accelerated Hybrid Method for a Class of Multi-Depot Vehicle Routing Problems
Zhenyu Lei and Jin-Kao Hao
Multi-depot vehicle routing problems (MDVRPs) are prevalent in a variety of practical applications. However, they are computationally challenging to solve due to their inherent complexity. This paper proposes an effective hybrid
algorithm for a class of MDVRPs. The
algorithm integrates a learning-driven, diversity-controlled route-exchange crossover and a multi-depot-supported feasible-and-infeasible search framework guided by a multi-penalty evaluation function. Two dedicated depot-related local search operators are incorporated to further strengthen the search capability in multi-depot settings. To improve computational efficiency and scalability, an enhanced version of the
algorithm is developed that uses a tensor-based GPU acceleration combined with a novel multi-move update strategy. Extensive computational experiments on
benchmark instances of three MDVRP variants show that the proposed
algorithms are highly competitive with state-of-the-art methods, especially for large-scale instances.
Read the full abstract ▾
Rings and Algebras
On monoid graded semihereditary rings
Haneen Falah Ghalib Al-Kharsan, Parviz Sahandi and Nematollah Shirmohammadi
In order to study graded left hereditary and left semihereditary rings graded by a cancelation monoid in terms of their modules, we need to revisit graded free, projective, injective, and flat modules and provide graded versions of specific results concerning these modules, like Baer's criterion on injectivity and Lazard's
theorem on flatness. Then, among other things, we can give some characterization of graded left hereditary and left semihereditary rings, in particular, of graded-Prüfer and graded-Dedekind domains.
Read the full abstract ▾
Mathematical Physics · Cross-listed from nlin.SI
The Bohlin variant of the Eisenhart lift
Anton Galajinsky
Inspired by the Bohlin transformation relating the planar harmonic oscillator to the Kepler problem, a variant of the Eisenhart lift is studied, in which a Lagrangian conservative dynamical system with d degrees of freedom is embedded into timelike geodesics of a conformally flat metric on a (d+2)-dimensional space-time of the Lorentzian signature. The uplift is used to construct novel examples of conformally flat metrics admitting higher rank Killing tensors.
Read the full abstract ▾
Mathematical Physics · Cross-listed from cs.LG
A new Uncertainty Principle in Machine Learning
V.Dolotin and A.Morozov
Many scientific problems in the context of machine learning can be reduced to the search of
polynomial answers in appropriate variables. The Hevisidization of arbitrary
polynomial is actually provided by one-and-the same two-layer expression. What prevents the use of this simple idea is the fatal degeneracy of the Heaviside and sigmoid expansions, which traps the steepest-descent
evolution at the bottom of canyons, close to the starting point, but far from the desired true minimum. This problem is unavoidable and can be formulated as a peculiar uncertainty principle – the sharper the minimum, the smoother the canyons. It is a direct analogue of the usual one, which is the pertinent property of the more familiar
Fourier expansion. Standard machine learning software fights with this problem empirically, for example, by testing evolutions, originated at randomly distributed starting points and then selecting the best one. Surprisingly or not, phenomena and problems, encountered in ML application to science are pure scientific and belong to physics, not to computer science. On the other hand, they sound slightly different and shed new light on the well-known phenomena – for example, extend the uncertainty principle from
Fourier and, later, wavelet analysis to a new peculiar class of nearly singular sigmoid functions.
Read the full abstract ▾
Algebraic Geometry
Chow groups of Chow varieties
Youming Chen and Wenchuan Hu
Let $C_{p,d}(\mathbb{P}^n)$ be the Chow variety of effective algebraic $p$-cycles of degree $d$ in complex projective $n$-space $\mathbb{P}^n$. In this paper, we compute the rational Chow groups $\mathrm{Ch}_q(C_{p,d}(\mathbb{P}^n))_\mathbb{Q}$ for $0 \le q \le d$. We show that these Chow groups are isomorphic to the corresponding rational singular homology groups $H_{2q}(C_{p,d}(\mathbb{P}^n), \mathbb{Q})$ in this range, a result that was previously known. Furthermore, we prove that the rational Chow groups of a natural completion of the Chow monoid of algebraic $p$-cycles on projective spaces coincide with the corresponding rational singular homology groups. We also establish the stability of Chow groups of Chow varieties under natural
embeddings and algebraic suspension maps within a certain range. Finally, we determine the Chow groups, up to a certain level, for the space of algebraic cycles of fixed degree.
Read the full abstract ▾
Combinatorics
The sad life of lattice triangles
Christian Aebi and Grant Cairns
This paper treats triangles in the plane whose vertices lie on the integer
lattice, i.e., the vertices have integer coordinates. It shows that apart from trivial examples, the circumcenter, centroid and orthocenter of such triangles never all lie on the integer
lattice. Several further observations are made concerning the circumcenter, centroid and orthocenter.
Read the full abstract ▾
Numerical Analysis
Surrogate-assisted global sensitivity analysis of a hybrid-dimensional Stokes–Brinkman–Darcy model
Linheng Ruan, Ilja Kröker, Sergey Oladyshkin et al. (+1 more)
Development of new multiscale mathematical models often entails considerable complexity and multiple undetermined parameters, typically arising from closure relations. To enable reliable simulations, one must quantify how uncertain physical parameters influence model predictions. We propose surrogate-assisted global sensitivity analysis that combines computational efficiency with a rigorous assessment of parameter influence. In this work, we analyze the recently proposed hybrid-dimensional Stokes–Brinkman–Darcy model, which describes fluid flows in coupled free-flow and porous-medium systems with arbitrary flow directions at the fluid–porous interface. The model results from vertical averaging and contains several unknown parameters. We perform surrogate-assisted global sensitivity analysis using Sobol' indices to investigate the sensitivity of the model to variations of physical parameters for two test cases: filtration and splitting flows. However, constructing surrogates for higher-dimensional random fields requires either many training runs or sophisticated sampling strategies. To address this, we compare
polynomial chaos surrogates, including sparse and multi-resolution representations, for their efficiency in global sensitivity analysis, using a predefined Sobol' sequence of training samples. Across the tested cases, multi-resolution approach delivers the most accurate estimation of Sobol' indices.
Read the full abstract ▾
All authors Linheng Ruan, Ilja Kröker, Sergey Oladyshkin, Iryna Rybak
Analysis of PDEs
Analysis of a Model for Electrical Discharge in MEMS
Heiko Gimperlein, Runan He and Andrew A. Lacey
We study the local well-posedness of the solution to a coupled nonlinear
elliptic-
parabolic system which models electrical discharge in a Micro-Electro-Mechanical System (MEMS). A simple MEMS capacitor device contains two plates acting as the capacitor's electrodes, one of which is flexible, and which are separated by a narrow gas-filled gap. In the event of the flexible plate approaching the other, electrical discharge can occur. This is modelled here by two
parabolic equations, for densities of electrons and positive ions, and an
elliptic equation for electric potential. We show the local-in-time existence of a weak solution for the coupled system. Compactness techniques, used previously in the study of drift-
diffusion equations, are employed in our proof.
Read the full abstract ▾
Algebraic Geometry
Deformation Theory of $\mathbb{E}_n$-Monoidal Categories
Yining Chen
In this paper, we prove that the naive deformation problem of an $\mathbb{E}_n$-monoidal stable $k$-linear $\infty$-category $\mathcal{C}$ is a $2$-proximate formal $\mathbb{E}_{n+2}$-
moduli problem, whose corresponding formal
moduli problem is controlled by the non-unital $\mathbb{E}_{n+2}$-
algebra $\mathrm{fib}\big(\mathrm{End}_{\mathcal{Z}_{\mathbb{E}_n}(\mathcal{C})}(1)\rightarrow \mathrm{End}_{\mathcal{C}}(1)\big)$, where $\mathcal{Z}_{\mathbb{E}_n}(\mathcal{C})$ is the $\mathbb{E}_n$-center of $\mathcal{C}$. If $\mathcal{C}$ is rigid monoidal and tamely compactly generated by unobstructible objects, then this naive deformation problem is equivalent to the formal
moduli problem. We also prove a uniqueness
theorem for formal deformations of certain formal
moduli problems, which can be applied to the $\mathbb{E}_1$ and $\mathbb{E}_2$-monoidal deformation problems of $\mathbf{Rep}(G)$ for a reductive algebraic group $G$ with a simple Lie
algebra $\mathfrak{g}=T_e G$. Finally, we show factorization homology is compatible with deformations.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.LG
Provably Safe Generative Sampling with Constricting Barrier Functions
Darshan Gadginmath, Ahmed Allibhoy and Fabio Pasqualetti
Flow-based generative models, such as
diffusion models and flow matching models, have achieved remarkable success in learning complex data distributions. However, a critical gap remains for their deployment in safety-critical domains: the lack of formal guarantees that generated samples will satisfy hard constraints. We propose a safety filtering framework that acts as an online shield for any pre-trained generative model. Our key insight is to cooperate with the generative process rather than override it. We define a constricting safety tube that is relaxed at the initial noise distribution and progressively tightens to the target safe set at the final data distribution, mirroring the coarse-to-fine structure of the generative process itself. By characterizing this tube via Control Barrier Functions (CBFs), we synthesize a feedback control input through a convex Quadratic Program (QP) at each sampling step. As the tube is loosest when noise is high and intervention is cheapest in terms of control energy, most constraint enforcement occurs when it least disrupts the model's learned structure. We prove that this mechanism guarantees safe sampling in discrete-time. The minimum-norm control synthesized at each step minimizes the per-step contribution to the KL divergence between the safe and original distributions. Across all experiments, we observe 100% constraint satisfaction. Our framework applies to any pre-trained flow-based sampling scheme requiring no retraining or architectural modifications. We validate the approach across constrained image generation, physically-consistent trajectory sampling, and safe robotic manipulation policies, achieving 100% constraint satisfaction while preserving semantic fidelity.
Read the full abstract ▾
Combinatorics
Total cut complexes and their duals
Andrés Carnero Bravo
We study the total $d$-cut complexes and their Alexander duals. We give some results about the connectivity in general and in terms of the grith of the graph. For $d\geq3$, the homotopy type of these complexes is calculated for: $p$th power of a cycle with at least $(2r)d$ vertices where $p\leq r$; the $r$th power of a cycle with at least $2rd-(r-1)$ vertices where $r\geq3$; and the $2$th power of a cycle with at least $3d$ vertices. These calculations solve a
conjecture of Bayer, Denker, Milutinović, Rowlands, Sundaram and Xue. The homotopy type of the $2$-total cut complex for any $r$th power of a cycle with $r\geq3$ also is calculated, solving a
conjecture of Chauhan, Shukla and Vinayak. We also study the complexes of cartesian products of paths and of cartesian products of complete graphs for the total $2$-cut complex.
Read the full abstract ▾
Statistics Theory
Causal Inference with High-Dimensional Treatments
Patrick Kramer, Edward H. Kennedy and Isaac M. Opper
In this work, we consider causal inference in various high-dimensional treatment settings, including for single multi-valued treatments and vector treatments with binary or continuous components, when the number of treatments can be comparable to or even larger than the number of observations. These settings bring unique challenges: first, the treatment effects of interest are represented by a high-dimensional vector rather than a scalar; second, positivity violations are often unavoidable; and third, estimation can be based on a smaller effective sample size. We first discuss fundamental limits of estimating effects here, showing that consistent estimation is impossible without further assumptions. We go on to propose novel doubly robust
estimators for mean potential outcomes of a high-dimensional single multi-valued treatment. We analyze the proposed
estimators under sparsity assumptions, giving finite-sample risk bounds and showing that consistent estimation is possible under these conditions. Moreover, we derive minimax lower bounds in a sparse and structure-agnostic model to characterize optimal rates of convergence and show our risk bounds are unimprovable. We then generalize our proposed
estimators as a sparse pseudo-outcome regression framework with constrained regression
estimators and error guarantees under sparsity, allowing estimation of generic functionals and different types of high-dimensional treatments. We apply the framework to derive
estimators of the mean potential outcomes for high-dimensional vector treatments. Finally, we illustrate the proposed methods through a simulation and an empirical application.
Read the full abstract ▾
Number Theory
A statistical model for points expanding in higher dimensions while being tied to bijective involutions
Cristian Cobeli, The Nguyen and Alexandru Zaharescu
Let $\mathcal{M}$ be a set with $M$ elements, let $\psi :\mathcal{M}\to\mathcal{M}$ be a bijective involution, and let~$\boldsymbol{\mathcal{X}}_{\psi}$ be the set of sequences $(x_1,\dots,x_M)\in\mathcal{M}^M$ with the property that $x_{M+1-j} = \psi(x_j)$ for $1\le j\le M$. This framework can be used to infer the possible distribution of sequences, such as the modular ones, that pose challenges for conventional methods. We prove that when $M$ is even, there exists a limit probability density function that weighs the parameter $k$ that counts the appearances of the elements of $\mathcal{M}$ among the terms of sequences $\textbf{x}\in\boldsymbol{\mathcal{X}}_{\psi}$. It turns out that the number of fixed points of $\psi$ influences the probability density function, which decomposes into two pieces, each multiplied by complementary factors, and the smaller of the two pieces appears only when $k$ is even. Applying the model, we find a threshold from which almost all sequences contain related terms with prescribed frequencies.
Read the full abstract ▾
Analysis of PDEs
The Influence of Exclusion Zones on the Coexistence of Predator and Prey with an Allee Effect
Henri Berestycki, William F. Fagan and Alex Safsten
We propose a reaction–
diffusion model of predator–prey interaction in which the predators occupy only a subset of the prey's territory, leaving a predator-free exclusion zone. Ecological examples include marine protected areas where it is illegal to fish, or buffer zones left between the territories of rival predators. The prey are subject to a strong Allee effect, so excessive predation may lead to the extinction of both species. The exclusion zone mitigates this problem by providing the prey with a refuge in which to proliferate without predation. Thus, paradoxically, a smaller predator territory may be able to support a more substantial population than a larger one. Using a topological degree argument, we show in any dimensions that, provided the exclusion zone is large enough, the system possesses spatially heterogeneous coexistence
equilibria with positive populations of both species. This result is global in the sense that it does not rely on local bifurcations from semi-trivial stationary states. We also show that as the predator domain becomes asymptotically small, the total predator population does not vanish, and in some cases may actually be maximized in this limit of shrinking predation area. Conversely, we show that as the predator domain becomes large, it may exhibit thresholding behavior, passing suddenly from a regime with coexistence solutions to one in which extinction becomes unavoidable, highlighting the need for careful analysis in the management of predator–prey systems.
Read the full abstract ▾
Analysis of PDEs · Cross-listed from cond-mat.stat-mech
Yet another look at narrow escape through a tube
Victorya Richardson, Yick Hin Ling and Sean D Lawley
The narrow escape problem concerns the time needed for a diffusing particle to exit a confining domain through a small hole in the boundary. While this problem is now well-understood, determining the escape time for a particle that must exit through a narrow tube has proven challenging. Indeed, relying on analogies with electrodynamics, parameter fits to simulations, and heuristics, a variety of conflicting estimates for this escape time have been offered over the last three decades, some of which are counterintuitive and arguably non-physical. In this paper, we combine matched asymptotic analysis and probabilistic methods to determine the exact asymptotics of the narrow escape time through a tube. We obtain a new escape time formula which reduces to the various prior estimates in certain special cases. If the diffusivity in the tube differs from the diffusivity in the rest of the domain, our results reveal the importance of the form of the multiplicative noise inherent to any diffusivity that varies in space. We discuss our results in the context of asymmetric
cell division.
Read the full abstract ▾
Mathematical Physics · Cross-listed from nlin.SI
Geometry of two- and three-dimensional integrable systems related to affine Weyl groups $W(E_8^{(1)})$ and $W(E_7^{(1)})$
Jaume Alonso and Yuri B. Suris
We find a general framework for the construction of birational involutions on two- and three-dimensional varieties obtained from $\mathbb P^2$, $\mathbb P^1\times \mathbb P^1$, and $\mathbb P^3$ by blow-up at nine, respectively eight points. Each such involution is based on a divisor class with a one-dimensional linear system with a generic element of genus zero. Classical Manin involutions represent the simplest particular case. Novel, more sophisticated cases identified here include birational involutions of $\mathbb P^2$ along conics and along nodal cubic curves, as well as birational involutions of $\mathbb P^3$ along quadratic cones and along Cayley nodal cubic surfaces. We prove a general formula for the induced action of
geometric birational involutions on the respective Picard group, and give a general result about decomposition of translational elements of the respective affine Weyl group of
symmetries into a product of two
geometric birational involutions.
Read the full abstract ▾
Geometric Topology
Absolute $\mathbb{Z}/2$ gradings in real Heegaard Floer homology
Eha Srivastava
Real Heegaard Floer homology is an invariant associated to a three-
manifold equipped with an involution with nonempty fixed set of codimension two. We show that when the image of the fixed point set is nullhomologous in the quotient, the real Heegaard Floer homology groups admit an absolute $\mathbb{Z}/2$ grading; in particular this applies to double branched covers of links in $S^3$. As an application, we define a $\mathbb{Z}$-valued invariant of
knots, which is the appropriate signed analogue of Miyazawa's degree invariant. Furthermore, we show that this invariant is equal to the Alexander
polynomial of the
knot evaluated at $i$.
Read the full abstract ▾
Mathematical Physics
A kinetic interpretation of thermomechanical restrictions of continua
Patrick E. Farrell, Josef Málek, Ondřej Souček et al. (+1 more)
Rajagopal and Srinivasa's thermodynamic framework derives constitutive relations in continuum mechanics from two scalar functions describing energy storage and
entropy production via a constrained optimization principle. In parallel, kinetic theory obtains constitutive laws through moment closure, most notably via the Chapman–Enskog expansion. This work has three objectives. First, we establish a connection between these approaches by providing a kinetic interpretation of the Rajagopal–Srinivasa principle of maximal
entropy production, under appropriate albeit restrictive hypotheses. For a Bhatnagar–Gross–Krook-type approximation, we show that the Rajagopal–Srinivasa principle is equivalent to a minimal relaxation-time principle, selecting among admissible constitutive responses the one with the fastest compatible relaxation toward
equilibrium. Second, we review the classical kinetic description of continua in a manner accessible to those familiar with continuum thermodynamics. Third, we propose a hybrid Chapman–Enskog–Rajagopal–Srinivasa approach which computes the thermodynamic relations and
entropy production from the Chapman–Enskog expansion, and then invokes the Rajagopal–Srinivasa principle to determine the other constitutive relations. This recovers the standard Euler and Navier–Stokes–
Fourier constitutive laws for monatomic gases. We also demonstrate how different choices of selection procedure can be more informative than the classical Chapman–Enskog closure in the context of an inviscid compressible Leslie–Ericksen model arising in
liquid crystals.
Read the full abstract ▾
All authors Patrick E. Farrell, Josef Málek, Ondřej Souček, Umberto Zerbinati
Combinatorics
On the spectra of k-uniform threshold hypergraphs
Miriam Abdón, Lucas Portugal, Renata Del-Vecchio et al. (+1 more)
In this article we introduce a definition of k-uniform thresholds hypergraphs through a binary sequence, a natural extension of the classical definition for thresholds graphs. We characterize some of its
eigenvalues and multiplicities by means of combinatorial numbers, derived from edge counts. An important problem addressed in Spectral Graph Theory is to find graphs with few distinct
eigenvalues. Our characterization allows us to construct k-uniform threshold hypergraphs having an arbitrary number of vertices with few distinct
eigenvalues.
Read the full abstract ▾
All authors Miriam Abdón, Lucas Portugal, Renata Del-Vecchio, Renata de Freitas
Optimization and Control
Fenchel-Young Estimators of Perturbed Utility Models
Xi Lin, Yafeng Yin and Tianming Liu
Perturbed Utility Models (PUMs) represent discrete choice as utility maximization under convex perturbation or regularization, encompassing a broad class of choice models, including Multinomial Logit (MNL) and models that permit zero choice probabilities. Because, for general perturbations, maximum likelihood may be non-convex, and the negative log-likelihood is infinite when a sparse model assigns zero probability to an observed choice, we specialize the Fenchel–Young criterion to PUM estimation. With a fixed perturbation and utilities linear in parameters, the empirical objective is globally convex and remains finite at sparse predictions. We establish probability-level Fisher consistency, parameter identification, consistency, and asymptotic normality under explicit regularity conditions. We also develop computational methods for estimation, using structured probability evaluation for additive and tree-structured perturbations and a primal-dual
algorithm for general non-separable perturbations. We then introduce Parametric Basis Estimation (PBE), a bi-level method that jointly learns utility parameters and a tree-structured perturbation through convex combinations of leaf-level and nest-level basis functions. Under explicit regularity conditions, we establish joint identification and consistency of the resulting
estimator when the bi-level problem is solved globally. We also develop an
algorithm with stationarity guarantees under stated smoothness conditions. Synthetic experiments examine structural recovery, normalization, and sensitivity to misspecification. On Swissmetro, repeated respondent-grouped nested cross-validation shows that both additive and tree-structured PBE achieve statistically significant reductions in held-out Brier score relative to MNL.
Read the full abstract ▾
Combinatorics
Signed network models for dimensionality reduction of portfolio optimization
Bibhas Adhikari
In this paper, we develop a time-series-based signed network model for dimensionality reduction in portfolio optimization, grounded in Markowitz's portfolio theory and extended to incorporate higher-order moments of asset return distributions. Unlike traditional correlation-based approaches, we construct a complete signed graph for each trading day within a specified time window, where the sign of an edge between a pair of assets is determined by the relative behavior of their log returns with respect to their mean returns. Within this framework, we introduce a combinatorial interpretation of higher-order moments, showing that maximizing skewness and minimizing kurtosis correspond to maximizing balanced triangles and balanced 4-cliques with specific signed edge configurations respectively. We establish that the latter leads to an NP-hard combinatorial optimization problem, while the former is naturally guaranteed by the structural properties of the signed graph model. Based on this interpretation, we propose a dimensionality reduction method using a combinatorial formulation of the mean-variance optimization problem through a combinatorial hedge score metric for assets. The proposed framework is validated through extensive backtesting on 199 S&P 500 assets over a 16-year period (2006 - 2021), demonstrating the effectiveness of reduced asset universes for portfolio construction using both Markowitz optimization and equally weighted strategy.
Read the full abstract ▾