Optimization and Control
Risk or Replace: Efficient Asymptotics for Data-Driven Maintenance
Poulad Moradi, Joachim Arts, Melvin Drent et al. (+1 more)
Condition-based maintenance (CBM) is an approach that plans interventions for deteriorating systems according to their observed operational state. CBM reduces unplanned downtime and extends usable lifetime. We study a heterogeneous population of components that degrade over time according to a
stochastic processes with non-negative and i.i.d. increments that are characterized by component-specific parameters that remain unobservable to the decision maker. We rely on degradation data to estimate these parameters and determine replacement actions at equidistant epochs. The goal is to minimize the long-run average cost, which incorporates fixed replacement costs, failure costs, and operating costs. This problem can be formulated as a high-dimensional partially observable Markov decision process (POMDP), which is generally intractable. We develop a tractable, data-driven CBM policy that estimates the optimal policy of a hypothetical Oracle that has full information of the underlying degradation parameters and call this policy the Estimated Oracle's Optimal Policy (EOP). We introduce a scaling regime where both the failure thresholds and cost parameters increase proportionally, reflecting practical settings in which component lifetimes and maintenance costs are large relative to the time between two consecutive CBM decision moments. We show that the regret of the EOP, defined as the difference between its long-run average cost and that of the Oracle, converges to zero in the scaling regime when the parameter
estimator is consistent. Across extensive experiments using both real and simulated data, the EOP achieves very low regret and, whenever the optimal POMDP policy can be computed exactly, a negligible optimality gap.
Read the full abstract ▾
All authors Poulad Moradi, Joachim Arts, Melvin Drent, Collin Drent
General Mathematics
A Composition Theorem for Binomially Weighted Averages
Andy Liu and Michael Reilly
We study binomially weighted summation methods given by \[ (x_n)_{n\in \mathbb{N}} \mapsto \left(\sum_{k=0}^n\binom{n}{k}r^k(1-r)^{n-k}x_k\right)_{n\in \mathbb{N}} \] for $r\in (0,1)$, and their behavior under composition with summation methods of the form \[ (x_n)_{n\in \mathbb{N}} \mapsto \left(\sum_{k=0}^n\lambda_k x_{n-k}\right)_{n\in \mathbb{N}}. \] Our main result shows that if the binomially weighted averages of a sequence $(x_n)_{n\in \mathbb{N}}$ converge to a limit then the binomially weighted averages of the sequence $\left(\sum_{k=0}^n\lambda_kx_{n-k}\right)_{n\in \mathbb{N}}$ converge to the same limit whenever $(\lambda_n)_{n\in\mathbb{N}}$ is an absolutely summable sequence with $\sum_{k=0}^{\infty}\lambda_k = 1$. This result disproves a
theorem appearing in the literature. Additionally, we discuss applications and extensions of our main result to compositions with weighted Cesàro averages.
Read the full abstract ▾
Dynamical Systems
Solvable Lie Foliations on Compact Five-Manifolds: Classification, Cohomological Obstruction, and Non-Homogeneous Examples
Ameth Ndiaye
We study $\GA$-Lie foliations on compact five-
manifolds. We establish a structural classification of the holonomy group $\Gamma$ into five types according to its algebraic structure inside $\GA$. For three of these types (I, II, IIIa) we prove homogeneity via Meigniez's
theorem and the Matsumoto–Tsuchiya
theorem. For Type~IIIb we prove non-homogeneity by exhibiting a non-polycyclic holonomy group, extending the Dathe–Ndiaye construction \cite{DN11}. We introduce a cohomological class $[F]\in H^2(\Gamma^{\mathrm{ab}},[\Gamma,\Gamma])$ as a necessary obstruction to homogeneity: if $\mathcal{F}$ is homogeneous and $\Gamma$ is polycyclic then $[F]=0$. We show that Type IIIb foliations satisfy $[F]\neq 0$. For Type IIIc, we prove that certain foliations are non-homogeneous by a direct argument when the generating translations are $\Q(\lambda)$-linearly independent; we exhibit explicit homogeneous examples showing that this type is not universally non-homogeneous. Finally, we construct the first known non-homogeneous $\mathrm{Sol}$-Lie foliation in dimension five by a verified
lattice deformation.
Read the full abstract ▾
Numerical Analysis
Geometric Integrators for Nonholonomic Systems on Lie Groups
Viyom Vivek, David Martin de Diego and Ravi N. Banavar
We present a general framework for constructing structure-preserving numerical integrators for nonholonomically constrained mechanical systems evolving on Lie groups using retraction maps. Retraction maps generalize the exponential map and provide a convenient tool for performing numerical integration on
manifolds. In nonholonomic mechanics, the constraints restrict the dynamics to a nonintegrable distribution rather than the entire tangent bundle. Using the Hamel formulation, the equations of motion can be expressed in local coordinates adapted to this constraint distribution. We then specialize the framework to the case of Lie groups, where both the dynamics and the constraints exhibit
symmetries, allowing a simplified formulation of the numerical scheme. The resulting integrator respects the constraint distribution and enforces the nonholonomic constraints at each discrete time step. The approach is illustrated using the Suslov problem.
Read the full abstract ▾
Statistics Theory · Cross-listed from stat.ML
Identification and Inference in Nonlinear Dynamic Network Models
Diego Vallarino
We study identification and inference in nonlinear dynamic systems defined on unknown interaction networks. The system evolves through an unobserved dependence
matrix governing cross-sectional shock propagation via a nonlinear operator. We show that the network structure is not generically identified, and that identification requires sufficient spectral heterogeneity. In particular, identification arises when the network induces non-exchangeable covariance patterns through heterogeneous amplification of eigenmodes. When the spectrum is concentrated, dependence becomes observationally equivalent to common shocks or scalar heterogeneity, leading to non-identification. We provide necessary and sufficient conditions for identification, characterize observational equivalence classes, and propose a semiparametric
estimator with asymptotic theory. We also develop tests for network dependence whose power depends on spectral properties of the interaction
matrix. The results apply to a broad class of economic models, including production networks, contagion models, and dynamic interaction systems.
Read the full abstract ▾
Combinatorics · Cross-listed from cs.DM
Census Dual Graphs: Properties and Random Graph Models
Sara Anderson, Sarah Cannon, Brooke Feinberg et al. (+1 more)
In the computational study of political redistricting, feasibility necessitates the use of a discretization of regions such as states, counties, and towns. In nearly all cases, researchers use a dual graph, whose vertices represent small geographic units (such as census blocks or voting precincts) with edges for geographic adjacency. A political districting plan is a partition of this graph into connected subgraphs that satisfy certain additional properties, such as connectedness, compactness, and equal population. Though dual graphs underlie nearly all computational studies of political redistricting, little is known about their properties. This is a unique graph class that has been described colloquially as `nearly planar, nearly triangulated,' but thus far there has been a lack of evidence to support this description. In this paper we study dual graphs for counties, census tracts, and census block groups across the United States in order to understand and characterize this graph class. We also consider several random graph models (most based on randomly perturbing grids or Delauney triangulations of random point sets), and determine which most closely resemble dual graphs under key metrics. This work lays an initial foundation for understanding and modeling the properties of dual graphs; this will provide invaluable insight to researchers developing
algorithms using them to understand, assess, and quantify the properties of political districting plans.
Read the full abstract ▾
All authors Sara Anderson, Sarah Cannon, Brooke Feinberg, Anne Friedman
Dynamical Systems
Entropy formula for C1 expanding maps
Eleonora Catsigeras and Fernando Valenzuela Gómez
We prove that the (necessarily existing) pseudo-physical or SRB-like measures of C1 expanding dynamical systems on a compact Riemannian
manifold satisfy Pesin
entropy formula. We include examples of C1 (non C1 plus Holder) expanding maps on the circle and on the 2
torus and study their pseudo-physical measures.
Read the full abstract ▾
Dynamical Systems
Effective stability estimates close to resonances with applications to rotational dynamics
Alessandra Celletti, Anargyros Dogkas and Alessia Francesca Guido
We consider nearly-integrable
Hamiltonian systems defined over a non-resonant domain. In the neighborhood of resonances, we use Nekhoroshev-like estimates to provide effective stability bounds for the action variables over long time. The applicability conditions of these estimates allow some freedom in the choice of parameters. Hence, we develop an optimization
algorithm for choosing parameters that maximize the stability time. To further improve the stability estimates, we use perturbation theory to reduce the norm of the perturbing function. We implement this procedure (effective stability estimates and perturbation theory) to analyze the stability of sequences of irrational (Diophantine) frequencies converging to frequencies corresponding to resonances. We consider two applications to models describing problems of rotational dynamics in Celestial Mechanics: the
spin-orbit problem, described by a 1D time-dependent
Hamiltonian, and the
spin-
spin-orbit model, described by a 2D time-dependent
Hamiltonian. We show stability results for orbits close to the main resonances associated with such models.
Read the full abstract ▾
Commutative Algebra
Generalized square-difference factor absorbing submodules of modules over commutative rings
Violeta Leoreanu-Fotea, Ece Yetkin Celikel, Tarik Arabaci et al. (+1 more)
In this paper, we introduce and study the class of generalized square-difference factor absorbing (gsdf-absorbing) submodules of modules over commutative rings. We provide various characterizations and properties of gsdf-absorbing submodules and examine the behavior of this class of submodules in some module extensions, including localization, homomorphic images, direct products, idealization, and amalgamation. We also characterize all gsdf-absorbing submodules of the Z-module Z. Several examples are provided to illustrate the results and to distinguish this class from related notions.
Read the full abstract ▾
All authors Violeta Leoreanu-Fotea, Ece Yetkin Celikel, Tarik Arabaci, Unsal Tekir
Analysis of PDEs
Axis Regularity in the 5D Corridor
Rishad Shahmurov
We study axisymmetric Navier–Stokes flow with swirl through the five-dimensional lift of the azimuthal-vorticity equation. We prove the weighted identities behind the corridor method: zero capacity of the axis, a sign-safe Hardy inequality, the exact circulation Caccioppoli formula, five-dimensional velocity recovery, a logarithmic source-mass estimate, and negative-norm compactness of the swirl source. These estimates yield a precise conditional reduction from axis regularity to a finite set of scale-uniform closure statements. We also prove that a natural weighted quartic inequality cannot provide that closure in the proposed corridor. The paper is a rigorous reduction
theorem; it does not prove unconditional regularity for arbitrary swirl.
Read the full abstract ▾
Analysis of PDEs
Modification to Maxwell's Equations
Shangbin Cui
A fixed electric charge is an electric current relative to a moving
magnetic field, so that it is subjected to the force of the moving
magnetic field. This means that not only time-varying
magnetic field produces electric field, but moving
magnetic field produces electric field as well. Maxwell neglected this fact in deriving his equations for the description of dynamical behavior of electromagnetic field so that the two equations (A) $\nabla\cdot\bfE=\epsln_0^{-1}\rho$ and (B) $\partial_t\bfE-\epsln_0^{-1}\mu_0^{-1}\nabla\times\bfB=-\epsln_0^{-1}\bfJ$ are incorrect. In this paper we modify the equation (A) into $\nabla\cdot(\bfE+\overline{\bfu}\times\bfB)= \epsln_0^{-1}\rho$, where $\overline{\bfu}$ denotes the mean velocity of the charges in the electric current, and the equation (B) is correspondingly modified. The modified equations are invariant under Galilean transformation. As a byproduct of this work, we see that Einstein's theory of special relativity is wrong.
Read the full abstract ▾
Analysis of PDEs
The lens cluster and triod cluster uniquely minimize the anisotropic perimeter in $\mathbb{R}^2$
Paula Benitez
(N, M)-clusters are partitions of $\mathbb{R}^d$ into N+M regions, where N chambers have prescribed finite measure and M chambers have infinite measure. Locally minimizing clusters are the configurations which minimize the perimeter among all competitors with compact support satisfying the same measure constraints. The characterization of these partitions has been widely studied for the standard (isotropic) perimeter. In the present paper, we investigate the corresponding problem for anisotropic perimeters, considering a general anisotropy. More specifically, we focus on (1,2)-clusters and (1,3)-clusters in $\mathbb{R}^2$. Our main results provide a
geometric characterization of these local minimizers: for regular (smooth, symmetric, and uniformly convex) anisotropies, we prove that a cluster is a local minimizer if and only if, up to translations, it is a standard anisotropic lens cluster in the (1,2)-cluster case, or a standard anisotropic triod cluster in the (1,3)-cluster case. In addition, using an approximation argument, we extend the minimizing property of these configurations to general anisotropies.
Read the full abstract ▾
Mathematical Physics · Cross-listed from hep-th
Poisson Vertex Algebra of Seiberg-Witten Theory
Ahsan Z. Khan
The space of local operators in the $Q$-
cohomology of the holomorphic-topological supercharge in a four-dimensional $\mathcal{N}=2$ theory carries the structure of a Poisson vertex
algebra. This note studies the Poisson vertex
algebra associated to the pure $\mathcal{N}=2$ gauge theory with gauge group $SU(2)$. We propose an explicit Poisson vertex
algebra $A$, claimed to be isomorphic to the
algebra of holomorphic-topological observables to all orders in perturbation theory. We compute the
Hilbert-Poincaré series of $A$ and show that it refines the Schur index of the pure $SU(2)$ theory. We show that $A$ admits a further differential $Q_{\text{inst}}$ which we hypothesize captures non-perturbative corrections, and compute the
cohomology of this differential. We thus present an explicit candidate for the space of non-perturbative holomorphic-topological observables of Seiberg-Witten theory.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.LG
Improving Feasibility via Fast Autoencoder-Based Projections
Maria Chzhen and Priya L. Donti
Enforcing complex (e.g., nonconvex) operational constraints is a critical challenge in real-world learning and control systems. However, existing methods struggle to efficiently enforce general classes of constraints. To address this, we propose a novel data-driven amortized approach that uses a trained autoencoder as an approximate projector to provide fast corrections to infeasible predictions. Specifically, we train an autoencoder using an
adversarial objective to learn a structured, convex latent representation of the feasible set. This enables rapid correction of neural network outputs by projecting their associated latent representations onto a simple convex shape before decoding into the original feasible set. We test our approach on a diverse suite of constrained optimization and reinforcement learning problems with challenging nonconvex constraints. Results show that our method effectively enforces constraints at a low computational cost, offering a practical alternative to expensive feasibility correction techniques based on traditional solvers.
Read the full abstract ▾
Combinatorics
Totally nonnegative maximal tori and opposed Bruhat intervals
Grant T. Barkley and Steven N. Karp
Lusztig (2024) recently introduced the space $\mathcal{T}_{>0}$ of totally positive maximal
tori of an algebraic group $G$. Each such
torus is the intersection of a totally positive Borel subgroup and a totally negative Borel subgroup. Lusztig defined a map from the totally positive part of $G$ to $\mathcal{T}_{>0}$ and conjectured that it is surjective. We verify this
conjecture. We also examine the closure of $\mathcal{T}_{>0}$, by studying when a totally nonnegative Borel subgroup is opposed to a totally nonpositive Borel subgroup. Our main result reduces this problem to a new combinatorial relation between pairs of Bruhat intervals of the Weyl group $W$, which we call 'opposition'. We provide a characterization of opposition when $G = \text{SL}_n$ (and $W$ is the symmetric group). Along the way, we disprove another
conjecture of Lusztig (2021) on totally nonnegative Borel subgroups. Finally, we connect $\mathcal{T}_{>0}$ to the amplituhedron introduced by Arkani-Hamed and Trnka (2014) in theoretical physics, by showing that $\mathcal{T}_{>0}$ can be regarded as a 'universal flag amplituhedron'. This gives further motivation for studying $\mathcal{T}_{>0}$ and its closure.
Read the full abstract ▾
Information Theory · Cross-listed from cs.AI
Contextual Control without Memory Growth in a Context-Switching Task
Song-Ju Kim
Context-dependent sequential decision making is commonly addressed either by providing context explicitly as an input or by increasing recurrent
memory so that contextual information can be represented internally. We study a third alternative: realizing contextual dependence by intervening on a shared recurrent latent state, without enlarging recurrent dimensionality. To this end, we introduce an intervention-based recurrent architecture in which a recurrent core first constructs a shared pre-intervention latent state, and context then acts through an additive, context-indexed operator. We evaluate this idea on a context-switching sequential decision task under partial observability. We compare three model families: a label-assisted baseline with direct context access, a
memory baseline with enlarged recurrent state, and the proposed intervention model, which uses no direct context input to the recurrent core and no
memory growth. On the main
benchmark, the intervention model performs strongly without additional recurrent dimensions. We also evaluate the models using the conditional mutual information (I(C;O | S)) as a
theorem-motivated operational probe of contextual dependence at fixed latent state. For task-relevant phase-1 outcomes, the intervention model exhibits positive conditional contextual information. Together, these results suggest that intervention on a shared recurrent state provides a viable alternative to recurrent
memory growth for contextual control in this setting.
Read the full abstract ▾
Logic
Towards Trans-Exponential O-minimal Expansion of $(\mathbb{R},+,\cdot, 0, 1 <)$
Yayi Fu
We add an analytic trans-exponential function $\varphi$ to $\mathbb{R}_{an,\exp}$. We reduce the o-minimality of $\mathbb{R}_{an,\exp,\varphi}$ to the existence of "many" regular values for some definable systems of functions, which is a necessary condition for the o-minimality of $\mathbb{R}_{an,\exp,\varphi}$.
Read the full abstract ▾
Optimization and Control
Scheduling Electricity Production Units to Mitigate Severe Weather Impact: An Efficient Computational Implementation
Yongzheng Dai, Antonio J. Conejo and Feng Qiu
Extreme weather events in electric power systems can cause line trips or physical damage to transmission infrastructure, potentially leading to large-scale load shedding. To mitigate this risk, we propose a framework that strategically pre-positions the commitment of generation units–particularly slow-start units–to adapt to transmission
topologies that may arise following such events. The objective is to minimize load shedding under worst-case conditions. This paper makes two main contributions. First, we provide a more accurate representation of the underlying physical laws than those used in prior studies. Second, we develop a highly efficient solution
algorithm that outperforms state-of-the-art, off-the-shelf solvers. The proposed framework is formulated as a two-stage robust optimization model. In the first stage, generation units are scheduled in anticipation of disruptions. In the second stage, power dispatch decisions are optimized to minimize load shedding under the worst-case transmission
topology. To ensure system reliability and security, we incorporate convexified AC power flow constraints. The resulting model is a tri-level mixed-integer nonlinear optimization problem. To address its computational complexity, we design a problem-specific outer approximation
algorithm embedded within a column-and-constraint generation framework. Computational results show that the proposed model and solution approach can achieve solutions within a standard optimality gap in a reasonable time for moderately large instances.
Read the full abstract ▾
Algebraic Geometry
On nice $\mathbb{G}_m$-actions arising from locally nilpotent derivations with slice
Luis Cid
Let $k$ be an algebraically closed field of characteristic zero and $B$ a finitely generated $k$-domain. Given a locally nilpotent derivation $D$ on $B$ admitting a slice $s$, the derivation $\partial=NsD$ ($N\in\mathbb{Z}\setminus\{0\}$) is semisimple and defines a regular $\mathbb{G}_m$-action on $\mathrm{Spec}(B)$. We show that this derivation provides a new explicit description of the $\mathbb{G}_m$-action introduced by Freudenburg in terms of the infinitesimal generator $\partial=NsD$. In the nice case ($D^2(x_i)=0$ for all generators), we prove a linearizability criterion: the associated $\mathbb{G}_m$-action is linearizable if and only if $D$ is automorphically conjugate to $\partial/\partial x_n$ and the slice becomes affine-linear in the distinguished variable; moreover, this criterion is independent of the choice of slice.
Read the full abstract ▾
Numerical Analysis
D-splitting methods: 2N -storage embedded explicit pseudo-geometric Runge-Kutta methods using splitting methods
Sergio Blanes and Alejandro Escorihuela-Tomàs
Low-storage explicit Runge-Kutta schemes are particularly popular for the numerical integration of time-dependent partial differential equations based on the method-of-lines due to their efficiency and their reduced
memory requirements. We show that D-splitting methods, splitting methods on the extended phase space, can be used as high performance 2N-storage embedded explicit RK methods without a third storage register. They are pseudo-
geometric methods preserving some of the qualitative properties of the exact solution up to a higher order than the order of the method. Some of their properties are analysed, to build new tailored methods, and are tested on numerical examples.
Read the full abstract ▾
Optimization and Control
SDP Approach to Quadratic Vertex-Disjoint Paths Problem
Mingming Xu and Hao Hu
We study the quadratic $k$-vertex-disjoint paths problem (Q-$k$-VDP), which seeks $k$ vertex-disjoint paths in a directed graph that minimize a nonconvex quadratic objective function. We formulate the problem as a binary quadratic program and apply a systematic graph reduction to manage its dimensionality. To obtain a tractable bounding model, we drop the subtour-elimination constraints and derive a semidefinite programming (SDP) relaxation. We then solve this relaxed model within a branch-and-bound framework, where the bounds are computed from the SDP relaxation using a tailored alternating direction method of multipliers. Computational results show that our proposed method consistently outperforms Gurobi by solving more instances to optimality, especially on challenging large-scale instances.
Read the full abstract ▾
Optimization and Control
High-Order Matrix Control Barrier Functions: Well-Posedness and Feasibility via Matrix Relative Degree
Samuel G. Gessow, Pio Ong, Aaron D. Ames et al. (+1 more)
Control barrier functions (CBFs) provide an effective framework for enforcing safety in dynamical systems with scalar constraints. However, many safety constraints are more naturally expressed as
matrix-valued conditions, such as positive definiteness or
eigenvalue bounds - scalar formulations introduce potential nonsmoothness that complicates analysis.
Matrix control barrier functions (MCBFs) address this limitation by directly enforcing
matrix-valued safety constraints. Yet for constraints where the control input does not appear in the first derivative, high-order formulations are required. While such extensions are well understood in the scalar case, they remain largely unexplored in the
matrix case. This paper develops high-order
matrix control barrier functions (HOMCBFs) and establishes conditions ensuring well-posedness and feasibility of the associated constraints, enabling enforcement of
matrix-valued safety constraints for systems with high-order dynamics. We further show that, using an optimal-decay HOMCBF formulation, forward invariance can be ensured while requiring control only over the minimum eigenspace. The framework is demonstrated on a double-integrator localization problem by enforcing positive definiteness of the information
matrix.
Read the full abstract ▾
All authors Samuel G. Gessow, Pio Ong, Aaron D. Ames, Brett T. Lopez
Analysis of PDEs
Three-spheres theorem for harmonic functions (non-concentric case)
Norair U. Arakelian and Norayr Matevosyan
A direct analog of Hadamard's three-circle
theorem is obtained for harmonic functions (in weighted L^2-norm) in case of (n-1)-dimensional non-concentric spheres in R^n. The result extends the concentric case to correlated non-concentric, non-touching spheres via an inversion technique. Applications to propagation of smallness and uniqueness for harmonic functions are given.
Read the full abstract ▾
Combinatorics
New minor minimal non-apex graphs
Andrei Pavelescu, Elena Pavelescu and Madeline Potter
A graph is apex if it becomes planar after the deletion of one vertex. The family of apex graphs is closed under taking minors, so it is characterized by a finite set of forbidden minors. Determining the finite set of forbidden minors for apex graphs remains an open question. In this paper, we list all forbidden minors for apex graphs with 12 or fewer vertices and all forbidden minors for apex graphs with 26 and fewer edges. We also present graphs outside of these ranges. We show that a graph with 13 vertices and minimal degree 6 is either apex or contains a $K_6$ minor, proving Jørgensen's
conjecture for order 13.
Read the full abstract ▾
Combinatorics · Cross-listed from cs.LG
Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization
Mohammadreza Rostami and Solmaz S. Kia
Submodular maximization under matroid constraints is a fundamental problem in combinatorial optimization with applications in sensing, data summarization, active learning, and resource allocation. While the Sequential Greedy (SG)
algorithm achieves only a $\frac{1}{2}$-approximation due to irrevocable selections, Continuous Greedy (CG) attains the optimal $\bigl(1-\frac{1}{e}\bigr)$-approximation via the multilinear relaxation, at the cost of a progressively dense decision vector that forces
agents to exchange feature
embeddings for nearly every ground-set element. We propose ATCG (\underline{A}daptive \underline{T}hresholded \underline{C}ontinuous \underline{G}reedy), which gates gradient evaluations behind a per-partition progress ratio $\eta_i$, expanding each
agent's active set only when current candidates fail to capture sufficient marginal gain, thereby directly bounding which feature
embeddings are ever transmitted. Theoretical analysis establishes a
curvature-aware approximation guarantee with effective factor $\tau_{\mathrm{eff}}=\max\{\tau,1-c\}$, interpolating between the threshold-based guarantee and the low-
curvature regime where ATCG recovers the performance of CG. This shows that the problem structure, as captured by
curvature, determines the amount of coordination and communication required to approach full-CG performance. Experiments on a class-balanced prototype selection problem over a subset of the CIFAR-10 animal
dataset show that ATCG achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.
Read the full abstract ▾
Spectral Theory
Geometric bounds for Steklov and weighted Neumann eigenvalues on Euclidean domains
Denis Vinokurov
We obtain sharp upper bounds for the first two nonzero Steklov
eigenvalues among bounded domains in Euclidean spaces of dimension $d \geq 7$ under a natural normalization involving volume and boundary measure. These bounds are derived from a characterization of optimal domains and weights for the first two nonzero weighted Neumann
eigenvalues. In dimensions $3 \leq d \leq 6$, we obtain strict upper bounds. We further establish strict upper bounds for all higher Steklov
eigenvalues on planar simply connected domains with continuous boundary, extending previous results which, beyond the second nonzero
eigenvalue, were known only for smooth planar domains.
Read the full abstract ▾
Classical Analysis and ODEs
The Kakeya conjecture, after Wang and Zahl
Larry Guth
This is a Seminaire Bourbaki survey of the proof of the Kakeya
conjecture in three dimensions. The survey is written for a broad mathematical audience. We sketch all the ideas in the proof, with many pictures.
Optimization and Control · Cross-listed from eess.SY
Two-Timescale Asymptotic Simulations of Hybrid Inclusions with Applications to Stochastic Hybrid Optimization
Max F. Crisafulli and Andrew R. Teel
Convergence properties of model-free two-timescale asymptotic simulations of singularly perturbed hybrid inclusions are developed. A hybrid inclusion combines constrained differential and difference inclusions to capture continuous (flow) and discrete (jump) dynamics, respectively. Sufficient conditions are established under which sequences of iterates and step sizes constitute a two-timescale asymptotic simulation of such a system, with limiting behavior characterized via weakly invariant and internally chain-transitive sets of an associated boundary layer and reduced system. To illustrate the applicability of these results, conditions are given under which a two-timescale
stochastic approximation of a hybrid optimization
algorithm asymptotically recovers the behavior of its deterministic counterpart.
Read the full abstract ▾
Combinatorics · Cross-listed from cs.DS
Improved Upper Bounds for the Directed Flow-Cut Gap
Greg Bodwin and Luba Samborska
We prove that the flow-cut gap for $n$-node directed graphs is at most $n^{1/3 + o(1)}$. This is the first improvement since a previous upper bound of $\widetilde{O}(n^{11/23})$ by Agarwal, Alon, and Charikar (STOC '07), and it narrows the gap to the current lower bound of $\widetilde{\Omega}(n^{1/7})$ by Chuzhoy and Khanna (JACM '09). We also show an upper bound on the directed flow-cut gap of $W^{1/2}n^{o(1)}$, where $W$ is the sum of the minimum fractional cut weights. As an auxiliary contribution, we significantly expand the network of reductions among various versions of the directed flow-cut gap problem. In particular, we prove near-equivalence between the edge and vertex directed flow-cut gaps, and we show that when parametrizing by $W$, one can assume unit capacities and uniform fractional cut weights without loss of generality.
Read the full abstract ▾