2025-06-13 | | Total: 177
We consider an unconstrained multi-criteria optimization problem with finite sum objective functions. The proposed algorithm belongs to a non-monotone trust-region framework where additional sampling approach is used to govern the sample size and the acceptance of a candidate point. Depending on the problem, the method can result in a mini-batch or an increasing sample size approach. Therefore, this work can be viewed as an extension of additional sampling trust region method for scalar finite sum function minimization presented in the literature. We show stochastic convergence of the proposed scheme for twice continuously-differentiable, but possibly non-convex objective functions, under assumptions standard for this framework. The experiments on logistic regression and least squares problems show the efficiency of the proposed scheme and its competitiveness with the relevant state-of-the-art methods for the considered problems.
Inspired by parallel developments in coarse geometry in mathematics and exact macroscopic quantization in physics, we present a family of general trace formulae which are universally quantized and depend only on large-scale geometric features of the input data. They generalize, to arbitrary dimensions, formulae found by Roe in his partitioned manifold index theorem, as well as the Kubo and Kitaev formulae for 2D Hall conductance used in physics.
The purpose of this note is to illustrate a parallel between (pre)topologies when seen among convergence spaces and (pre)approach spaces when seen among convergence approach spaces, that appears to be a more complete parallel than in the traditional presentation of these approach structures. This sheds some light on the reflector from the category of convergence approach spaces to that of approach spaces and even on the structure of approach spaces as such. This point of view allows for a characterization of approach spaces among convergence approach spaces represented as pointfree convergence frames as in [18].
Though a convergence space is connected if and only if its topological modification is connected, connected subsets differ for the convergence and for its topological modification. We explore for what subsets connectedness for the convergence or for the topological modification turn out to be equivalent. In particular, we show that the largest set containing a given connected set for which all subsets in between are connected is the adherence of the connected set for the reciprocal modification of the convergence.
The manuscript considers mathematical models for creating a topological drawing of a graph based on the methods of G. Ringel's vertex rotation theory. An algorithm is presented for generating a topological drawing of a flat part of a graph based on the selection of a basis for the cycle subspace C(G) using the Monte Carlo method. A steepest descent method for constructing a topological drawing of a flat subgraph is described in the manuscript. The topological drawing of a graph is constructed using a combination of the methods of vector intersection algebra developed by L. I. Rapport. Three stages of constructing a flat subgraph of a non-separable graph are described. The issues of constructing a Hamiltonian cycle based on constructing a flat subgraph are considered. A new method for constructing a Hamiltonian cycle of a graph based on the cycle graph of a flat subgraph is described.
The problem of computing optimal orthogonal approximation to a given matrix has attracted growing interest in machine learning. Notable applications include the recent Muon optimizer or Riemannian optimization on the Stiefel manifold. Among existing approaches, the Newton-Schulz iteration has emerged as a particularly effective solution, as it relies solely on matrix multiplications and thus achieves high computational efficiency on GPU hardware. Despite its efficiency, the method has inherent limitations - its coefficients are fixed and thus not optimized for a given matrix. In this paper we address this issue by proposing a Chebyshev-optimized version of Newton-Schulz (CANS). Based on the Chebyshev's alternance theorem, we theoretically derive optimal coefficients for the 3-rd order Newton-Schulz iteration and apply a Remez algorithm to compute optimal higher-degree polynomials. We leverage these polynomials to construct controlled approximate orthogonalization schemes, which is of interest in deep learning applications. Practically, we demonstrate the method's effectiveness in two key applications: orthogonalization in the Muon optimizer, and providing an efficient retraction alternative for Riemannian optimization on the Stiefel manifold.
This paper investigates a space-time interface-fitted approximation of a moving-interface optimal control problem with energy regularization. We reformulate the optimality conditions into a variational problem involving both the state and adjoint. This problem is shown to be equivalent to our optimal control problem. Based on fully unstructured, space-time interface-fitted meshes, we propose and analyze a Petrov-Galerkin approximation of the problem. An optimal error estimate with respect to a discrete norm is established under a specific regularity assumption on the state and adjoint. Several numerical results are presented to corroborate our theoretical results.
Given a relation $R \subseteq I \times J$ between two sets, Dowker's Theorem (1952) states that the homology groups of two associated simplicial complexes, now known as Dowker complexes, are isomorphic. In its modern form, the full result asserts a functorial homotopy equivalence between the two Dowker complexes. What can be said about relations defined on three or more sets? We present a simple generalization to multiway relations of the form $R \subseteq I_1 \times I_2 \times \cdots \times I_m$. The theorem asserts functorial homotopy equivalences between $m$ multiway Dowker complexes and a variant of the rectangle complex of Brun and Salbu from their recent short proof of Dowker's Theorem. Our proof uses Smale's homotopy mapping theorem and factors through a cellular Dowker lemma that expresses the main idea in more general form. To make the geometry more transparent, we work with a class of spaces called prod-complexes then transfer the results to simplicial complexes through a simplexification process. We conclude with a detailed study of ternary relations, identifying seven functorially defined homotopy types and twelve natural transformations between them.
We present a collection of questions related to the structure and classification of nuclear C*-algebras.
We show that deformation rings $R^{\mathrm{ps}}$ of $G$-pseudocharacters of a profinite group $\Gamma$ are noetherian, when $\Gamma$ satisfies Mazur's finiteness condition. The proof proceeds by reduction to the case when $\Gamma$ is finitely generated, where the result was previously established by the second author. This enables us to extend our work on moduli spaces of $R^{\mathrm{ps}}$-condensed representations of a finitely generated profinite group $\Gamma$, to the groups satisfying Mazur's finiteness condition. We also show that the functor from rigid analytic spaces over $\mathbb{Q}_p$ to sets, which associates to a rigid space $Y$ the set of continuous $\mathcal{O}(Y)$-valued $G$-pseudocharacters of $\Gamma$ is representable by a quasi-Stein rigid analytic space, and we study its general properties. We expect these results to be useful, when studying global Galois representations.
We investigate an optimization problem that arises when working within the paradigm of Data-Driven Computational Mechanics. In the context of the diffusion-reaction problem, such an optimization problem seeks for the continuous primal fields (gradient and flux) that are closest to some predefined discrete fields taken from a material data set. The optimization is performed over primal fields that satisfy the physical conservation law and the geometrical compatibility. We consider a reaction term in the conservation law, which has the effect of coupling all the optimality conditions. We first establish the well-posedness in the continuous setting. Then, we propose stable finite element discretizations that consistently approximate the continuous formulation, preserving its saddle-point structure and allowing for equal-order interpolation of all fields. Finally, we demonstrate the effectiveness of the proposed methods through a set of numerical examples.
This work explores Everett John Nelson's connexive logic, outlined in his PhD thesis and partially summarized in his 1930 paper \emph{Intensional Relations}, which is obtained by extending the system $\mathsf{NL}$ (reconstructed by E. Mares and F. Paoli) with a weak conjunction elimination rule explicitly assumed in the former but not in the latter. After a preliminary analysis of Nelson's philosophical ideas, we provide an algebraic-relational semantics for his logic and we investigate possible extensions thereof which are able to cope with Nelson's ideas with much more accuracy than the original system. For example, we will inquire into extensions whose algebraic-relational models are endowed with irreflexive incompatibility relations, or determine a ``weakly'' transitive entailment. Such an investigation will allow us to establish relationships between some of the trademarks of Nelson's thought and concepts of prominent importance for connexive logic, as e.g. Kapsner's strong connexivity and superconnexivity, as well as between the algebraic-relational semantics of Nelsonian logics and ordered structures that have gained great attention over the past years, namely partially ordered involutive residuate groupoids and (non-orthomodular) orthoposets.
We review the intrinsic geometry of the tangent bundle of a differentiable manifold $M$, aside from any non-natural structures. We recall the properties of the mirror map $B\in\mathrm{End}(TTM)$, known also as the canonical endomorphism or the almost-tangent structure, solve some cohomological questions and raise other induced by the $\mathrm{d}_B$ operator.
The Gittins index is a tool that optimally solves a variety of decision-making problems involving uncertainty, including multi-armed bandit problems, minimizing mean latency in queues, and search problems like the Pandora's box model. However, despite the above examples and later extensions thereof, the space of problems that the Gittins index can solve perfectly optimally is limited, and its definition is rather subtle compared to those of other multi-armed bandit algorithms. As a result, the Gittins index is often regarded as being primarily a concept of theoretical importance, rather than a practical tool for solving decision-making problems. The aim of this tutorial is to demonstrate that the Gittins index can be fruitfully applied to practical problems. We start by giving an example-driven introduction to the Gittins index, then walk through several examples of problems it solves - some optimally, some suboptimally but still with excellent performance. Two practical highlights in the latter category are applying the Gittins index to Bayesian optimization, and applying the Gittins index to minimizing tail latency in queues.
In this paper, we study the existence of normalized solutions for the following quasilinear Schrödinger equation with critical exponent: \begin{equation*} -\Delta u-u\Delta (u^2)+\lambda u=\tau|u|^{q-2}u+|u|^{2\cdot2^*-2}u,~~~~x\in\R^N, \end{equation*} under the mass constraint $\int_{\R^N}|u|^2dx=c$ for some prescribed $c>0$. Here $\tau\in \mathbb{R}$ is a parameter, $\lambda\in\R$ appears as a Lagrange multiplier, $N\ge3$, $2^*:=\frac{2N}{N-2}$ and $2<q<2\cdot2^*$. By deriving precise energy level estimates and establishing new convergence theorems, we apply the perturbation method to establish several existence results for $\tau>0$ in the Sobolev critical regime: [label=(\alph*)] \item For the case of $2<q<2+\frac{4}{N}$, we obtain the existence of two solutions, one of which is a local minimizer, and the other is a mountain pass type solution, under explicit conditions on $c>0$; \item For the case of $2+\frac{4}{N}\leq q<4+\frac{4}{N}$, we obtain the existence of normalized solutions of mountain pass type under different conditions on $c>0$; \item For the case of $4+\frac{4}{N}\leq q<2\cdot2^*$, we obtain the existence of a ground state normalized solution under different conditions on $c>0$. Moreover, when $\tau\le 0$, we derive the non-existence result for $2<q<2\cdot2^*$ and all $c>0$. Our research provides a comprehensive analysis across the entire range $q\in(2, 2 \cdot 2^*)$ and for all $N\ge3$. The methods we have developed are flexible and can be extended to a broader class of nonlinearities.
Coalescent models of bifurcating genealogies are used to infer evolutionary parameters from molecular data. However, there are many situations where bifurcating genealogies do not accurately reflect the true underlying ancestral history of samples, and a multifurcating genealogy is required. The space of multifurcating genealogical trees, where nodes can have more than two descendants, is largely underexplored in the setting of coalescent inference. In this paper, we examine the space of rooted, ranked, and unlabeled multifurcating trees. We recursively enumerate the space and then construct a partial ordering which induces a lattice on the space of multifurcating ranked tree shapes. The lattice structure lends itself naturally to defining Markov chains that permit exploration on the space of multifurcating ranked tree shapes. Finally, we prove theoretical bounds for the mixing time of two Markov chains defined on the lattice, and we present simulation results comparing the distribution of trees and tree statistics under various coalescent models to the uniform distribution on this tree space.
We establish Gromov's celebrated reconstruction theorem in Lorentzian geometry. Alongside this result, we introduce and study a natural concept of isomorphy of normalized bounded Lorentzian metric measure spaces. We outline applications to the spacetime reconstruction problem from causal set theory. Lastly, we propose three notions of convergence of (isomorphism classes of) normalized bounded Lorentzian metric measure spaces, for which we prove several fundamental properties.
In this paper, we present an efficient algorithm for solving a linear optimization problem with entropic constraints -- a class of problems that arises in game theory and information theory. Our analysis distinguishes between the cases of active and inactive constraints, addressing each using a Bregman proximal gradient method with entropic Legendre functions, for which we establish an ergodic convergence rate of $O(1/n)$ in objective values. For a specific cost structure, our framework provides a theoretical justification for the well-known Blahut-Arimoto algorithm. In the active constraint setting, we include a bisection procedure to approximate the strictly positive Lagrange multiplier. The efficiency of the proposed method is illustrated through comparisons with standard optimization solvers on a representative example from game theory, including extensions to higher-dimensional settings.
In recent papers (arXiv:2407.16507, arXiv:2408.05158) we presented results suggesting the existence of a new class of time-periodic solutions to the defocusing cubic wave equation on a one-dimensional interval with Dirichlet boundary conditions. Here we confirm these findings by rigorously constructing solutions from this class. The proof uses rational arithmetic computations to verify essential operator bounds.
In this paper, we study three quantities arising naturally from Bézout's identity, the resultant and the reduced resultant of two non-zero coprime integer polynomials. We establish several new divisibility relations among them. We also pose two conjectures by making computations.
We study representations of a deformed Heisenberg-Virasoro algebra that does not admit a triangular decomposition. Despite this, its $\mathbb{Z}$-gradation allows the classification of simple restricted modules. We show that all such modules of non-zero level arise via induction from simple modules of finite-dimensional solvable Lie algebras.
This article is concerned with homological properties of local or graded rings whose defining relations are monomials on some regular sequence. The main result of the article positively answers a question of Avramov for such a ring $R$. More precisely, we establish that an embedded deformation of $R$ corresponds exactly to a degree two central element in the homotopy Lie algebra of $R$, as well as a free summand of the conormal module of $R$. A major input in the proof is an analysis of cohomological support varieties. Other main results include establishing a lower bound for the dimension of the cohomological support variety of any complex over such rings, and classifying all possible subvarieties of affine $n$-space that are the cohomological support of rings defined by $n$ monomial relations where $n$ is five or less.
As has been shown in our previous work, the parallel-in-time direct inverse (ParaDIn) method introduced by Yamaleev and Paudel in (arXiv: 2406.00878v1, 2024) imposes some constraint on the maximum number of time levels, $N_t$, that can be integrated in parallel. To circumvent this problem and further increase the speedup, we combine the ParaDIn method with the Parareal algorithm to efficiently parallelize the first-order time derivative term in nonlinear partial differential equations discretized by the method of lines. The main idea of the proposed approach is to use a block-Jacobi preconditioner, so that each block is solved by using the ParaDIn method. To accelerate the convergence of Jacobi iterations, we use the Parareal method which can be interpreted as a two-level multigrid method in time. In contrast to the conventional Parareal algorithm whose coarse grid correction step is performed sequentially, both the coarse- and fine-grid propagators in the proposed approach are implemented in parallel by using the ParaDIn method, thus significantly increasing the parallel performance of the combined algorithm. Numerical results show that the new combined ParaDIn-Parareal method provides the speedup of up to 124 on 480 computing cores as compared with the sequential first-order implicit backward difference (BDF1) scheme for the 2-D nonlinear heat and Burgers equations with both smooth and discontinuous solutions.
Local stochastic volatility refers to a popular model class in applied mathematical finance that allows for "calibration-on-the-fly", typically via a particle method, derived from a formal McKean-Vlasov equation. Well-posedness of this limit is a well-known problem in the field; the general case is largely open, despite recent progress in Markovian situations. Our take is to start with a well-defined Euler approximation to the formal McKean-Vlasov equation, followed by a newly established half-step-scheme, allowing for good approximations of conditional expectations. In a sense, we do Euler first, particle second in contrast to previous works that start with the particle approximation. We show weak order one for the Euler discretization, plus error terms that account for the said approximation. The case of particle approximation is discussed in detail and the error rate is given in dependence of all parameters used.
We prove the Riemannian curvature-dimension condition $\mathsf{RCD}(KN,N+1)$ for an $N$-warped product $B\times_f^N F$ over a one-dimensional base space $B$ with a Lipschitz function $f: B\rightarrow \mathbb R_{\geq 0}$, provided (1) $f$ is a $Kf$-concave function, (2) $f$ satisfies a sub-Neumann boundary condition $\frac{\partial f}{\partial n}\geq 0$ on $\partial B\backslash f^{-1}(0)$ and $F$ is a compact metric measure space satisfying (3) the condition $\mathsf{RCD}(K_F (N-1), N)$ with $K_F:= \sup_B \{ (Df)^2 + Kf^2\}$. The result is sharp, i.e. we show that (1), (2) and (3) are necessary for the validity of statement provided $K_F\geq 0$. In general, only a weaker statement is true. If $f$ is assumed to be $Kf$-affine, then the condition $\mathsf{RCD}(K N, N+1)$ for the $N$-warped product holds if and only if the condition $\mathsf{RCD}(K_F(N-1), N)$ holds for $F$ for any $K_F\in \mathbb R$.