Daily Papers

We study complex saddle points of the worldline path integral for massive charged particles in two-dimensional maximally symmetric backgrounds threaded by homogeneous electric fields. Within the worldline formalism, we show that the semiclassical saddles generically require complexifying both the target spacetime and the proper-time parameter. The resulting solutions comprise two slices of a single complex family, distinguished by the direction of proper-time evolution. The one evolving in imaginary proper time carries an action that typically controls the exponential suppression of non-perturbative effects, while that evolving in real proper time may encode additional complex phases responsible for quantum interference between saddles. Treating this family as a whole, we give a prescription for constructing and classifying all topologically inequivalent instanton sectors, and we find that the worldline action depends only on their topological data, namely winding numbers around the compact directions and certain isolated punctures. Moreover, in Anti-de Sitter spacetime, the qualitative structure of the solutions is governed by the dimensionless ratio R |eE|/m (R being the curvature radius), which distinguishes sub-extremal, extremal, and super-extremal regimes. By contrast, no analogous distinction occurs in de Sitter---where the instantons are insensitive to this ratio---or in Minkowski spacetime, which lacks a curvature scale altogether. We also recast the action as a sum over residues of the relevant (non-conserved) conjugate momentum, making transparent which analytic data control each contribution. Finally, we discuss the subtleties that arise when solutions built in various local patches are lifted to global (Anti-)de Sitter space. These impose further necessary conditions on which saddles can in principle contribute to the one-loop path integral.

Training large neural networks (NNs) requires optimizing high-dimensional data-dependent loss functions. The optimization landscape of these functions is often highly complex and textured, even fractal-like, with many spurious local minima, ill-conditioned valleys, degenerate points, and saddle points. Complicating things further is the fact that these landscape characteristics are a function of the data, meaning that noise in the training data can propagate forward and give rise to unrepresentative small-scale geometry. This poses a difficulty for gradient-based optimization methods, which rely on local geometry to compute updates and are, therefore, vulnerable to being derailed by noisy data. In practice,this translates to a strong dependence of the optimization dynamics on the noise in the data, i.e., poor generalization performance. To remediate this problem, we propose a new optimization procedure: Rolling Ball Optimizer (RBO), that breaks this spatial locality by incorporating information from a larger region of the loss landscape in its updates. We achieve this by simulating the motion of a rigid sphere of finite radius rolling on the loss landscape, a straightforward generalization of Gradient Descent (GD) that simplifies into it in the infinitesimal limit. The radius serves as a hyperparameter that determines the scale at which RBO sees the loss landscape, allowing control over the granularity of its interaction therewith. We are motivated by the intuition that the large-scale geometry of the loss landscape is less data-specific than its fine-grained structure, and that it is easier to optimize. We support this intuition by proving that our algorithm has a smoothing effect on the loss function. Evaluation against SGD, SAM, and Entropy-SGD, on MNIST and CIFAR-10/100 demonstrates promising results in terms of convergence speed, training accuracy, and generalization performance.

Robustness against adversarial attacks and distribution shifts is a long-standing goal of Reinforcement Learning (RL). To this end, Robust Adversarial Reinforcement Learning (RARL) trains a protagonist against destabilizing forces exercised by an adversary in a competitive zero-sum Markov game, whose optimal solution, i.e., rational strategy, corresponds to a Nash equilibrium. However, finding Nash equilibria requires facing complex saddle point optimization problems, which can be prohibitive to solve, especially for high-dimensional control. In this paper, we propose a novel approach for adversarial RL based on entropy regularization to ease the complexity of the saddle point optimization problem. We show that the solution of this entropy-regularized problem corresponds to a Quantal Response Equilibrium (QRE), a generalization of Nash equilibria that accounts for bounded rationality, i.e., agents sometimes play random actions instead of optimal ones. Crucially, the connection between the entropy-regularized objective and QRE enables free modulation of the rationality of the agents by simply tuning the temperature coefficient. We leverage this insight to propose our novel algorithm, Quantal Adversarial RL (QARL), which gradually increases the rationality of the adversary in a curriculum fashion until it is fully rational, easing the complexity of the optimization problem while retaining robustness. We provide extensive evidence of QARL outperforming RARL and recent baselines across several MuJoCo locomotion and navigation problems in overall performance and robustness.

Two-point zeroth order methods are important in many applications of zeroth-order optimization, such as robotics, wind farms, power systems, online optimization, and adversarial robustness to black-box attacks in deep neural networks, where the problem may be high-dimensional and/or time-varying. Most problems in these applications are nonconvex and contain saddle points. While existing works have shown that zeroth-order methods utilizing Omega(d) function valuations per iteration (with d denoting the problem dimension) can escape saddle points efficiently, it remains an open question if zeroth-order methods based on two-point estimators can escape saddle points. In this paper, we show that by adding an appropriate isotropic perturbation at each iteration, a zeroth-order algorithm based on 2m (for any 1 leq m leq d) function evaluations per iteration can not only find epsilon-second order stationary points polynomially fast, but do so using only Oleft(d{mepsilon^{2}psi}right) function evaluations, where psi geq Omegaleft(epsilonright) is a parameter capturing the extent to which the function of interest exhibits the strict saddle property.

A central challenge to many fields of science and engineering involves minimizing non-convex error functions over continuous, high dimensional spaces. Gradient descent or quasi-Newton methods are almost ubiquitously used to perform such minimizations, and it is often thought that a main source of difficulty for the ability of these local methods to find the global minimum is the proliferation of local minima with much higher error than the global minimum. Here we argue, based on results from statistical physics, random matrix theory, and neural network theory, that a deeper and more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest. Such saddle points are surrounded by high error plateaus that can dramatically slow down learning, and give the illusory impression of the existence of a local minimum. Motivated by these arguments, we propose a new algorithm, the saddle-free Newton method, that can rapidly escape high dimensional saddle points, unlike gradient descent and quasi-Newton methods. We apply this algorithm to deep neural network training, and provide preliminary numerical evidence for its superior performance.

Let (M omega) be a two dimensional symplectic manifold, phi: M to M a symplectomorphism with hyperbolic fixed point x and transversely intersecting stable and unstable manifolds W^s(phi, x) cap W^u(phi, x)=:H(phi, x). The intersection points are called homoclinic points, and the stable and unstable manifold are in this situation Lagrangian submanifolds. For this Lagrangian intersection problem with its infinite number of intersection points and wild oscillation behavior, we first define a Floer homology generated by finite sets of so-called contractible homoclinic points. This generalizes very significantly the Floer homologies generated by (semi)primary points defined by us in earlier works. Nevertheless these Floer homologies only consider quite `local' aspects of W^s(phi, x) cap W^u(phi, x) since their generator sets are finite, but the number of all contractible homoclinic points is infinite. To overcome this issue, we construct a direct limit of these `local' homoclinic Floer homologies over suitable index sets. These direct limits thus accumulate the information gathered by the finitely generated local' homoclinic Floer homologies.

We show that curve enumeration invariants of complex threefolds with nef anti-canonical bundle are determined by their values on local curves. This implies the MNOP conjecture of Maulik, Nekrasov, Okounkov, and Pandharipande relating Gromov--Witten and Donaldson--Pandharipande--Thomas invariants, for all complex threefolds with nef anti-canonical bundle (in particular, all Calabi--Yau threefolds) and primary insertions (no descendents), given its known validity for local curves due to Bryan, Okounkov, and Pandharipande. The main new technical ingredient in our work is a generic transversality result for holomorphic curves in complex manifolds. Due to the rigidity of complex structures, this result is necessarily weaker than the corresponding generic transversality property for holomorphic curves in almost complex manifolds. Despite this weaker nature, it is enough to obtain our main result by following the proof of the Gopakumar--Vafa integrality conjecture by Ionel and Parker.

We present a numerical framework to treat infinite time horizon spatially distributed optimal control problems via the associated canonical system derived by Pontryagin's Maximum Principle. The basic idea is to consider the canonical system in two steps. First we perform a bifurcation analysis of canonical steady states using the continuation and bifurcation package pde2path, yielding a number of so called flat and patterned canonical steady states. In a second step we link pde2path to the two point boundary value problem solver TOM to study time dependent canonical paths to steady states having the so called saddle point property. As an example we consider a shallow lake model with diffusion.

This paper presents a novel end-to-end framework for closed-form computation and visualization of critical point uncertainty in 2D uncertain scalar fields. Critical points are fundamental topological descriptors used in the visualization and analysis of scalar fields. The uncertainty inherent in data (e.g., observational and experimental data, approximations in simulations, and compression), however, creates uncertainty regarding critical point positions. Uncertainty in critical point positions, therefore, cannot be ignored, given their impact on downstream data analysis tasks. In this work, we study uncertainty in critical points as a function of uncertainty in data modeled with probability distributions. Although Monte Carlo (MC) sampling techniques have been used in prior studies to quantify critical point uncertainty, they are often expensive and are infrequently used in production-quality visualization software. We, therefore, propose a new end-to-end framework to address these challenges that comprises a threefold contribution. First, we derive the critical point uncertainty in closed form, which is more accurate and efficient than the conventional MC sampling methods. Specifically, we provide the closed-form and semianalytical (a mix of closed-form and MC methods) solutions for parametric (e.g., uniform, Epanechnikov) and nonparametric models (e.g., histograms) with finite support. Second, we accelerate critical point probability computations using a parallel implementation with the VTK-m library, which is platform portable. Finally, we demonstrate the integration of our implementation with the ParaView software system to demonstrate near-real-time results for real datasets.

We study the joint image of lines incident to points, meaning the set of image tuples obtained from fixed cameras observing a varying 3D point-line incidence. We prove a formula for the number of complex critical points of the triangulation problem that aims to compute a 3D point-line incidence from noisy images. Our formula works for an arbitrary number of images and measures the intrinsic difficulty of this triangulation. Additionally, we conduct numerical experiments using homotopy continuation methods, comparing different approaches of triangulation of such incidences. In our setup, exploiting the incidence relations gives both a faster point reconstruction and in three views more accurate.

The task of locating first order saddle points on high-dimensional surfaces describing the variation of energy as a function of atomic coordinates is an essential step for identifying the mechanism and estimating the rate of thermally activated events within the harmonic approximation of transition state theory. When combined directly with electronic structure calculations, the number of energy and atomic force evaluations needed for convergence is a primary issue. Here, we describe an efficient implementation of Gaussian process regression (GPR) acceleration of the minimum mode following method where a dimer is used to estimate the lowest eigenmode of the Hessian. A surrogate energy surface is constructed and updated after each electronic structure calculation. The method is applied to a test set of 500 molecular reactions previously generated by Hermez and coworkers [J. Chem. Theory Comput. 18, 6974 (2022)]. An order of magnitude reduction in the number of electronic structure calculations needed to reach the saddle point configurations is obtained by using the GPR compared to the dimer method. Despite the wide range in stiffness of the molecular degrees of freedom, the calculations are carried out using Cartesian coordinates and are found to require similar number of electronic structure calculations as an elaborate internal coordinate method implemented in the Sella software package. The present implementation of the GPR surrogate model in C++ is efficient enough for the wall time of the saddle point searches to be reduced in 3 out of 4 cases even though the calculations are carried out at a low Hartree-Fock level.

In this paper, we study 6-dimensional GKM manifolds with 4 fixed points. We classify all possible GKM graphs, and for each type of graph we construct a manifold, proving the existence. We show that six types occur. (P1) complex projective space C P^3 with standard complex structure (P2) blow up of S^6 at a fixed point, diffeomorphic to C P^3 (P3) C P^3 as the homogeneous space Sp(2)/(U(1) times Sp(1)) with non-standard almost complex structure (Q1) complex quadric Q_3 with standard complex structure (Q2) blow up of S^6 along isotropy 2-sphere, diffeomorphic to Q_3 (S) S^2 times S^4, obtained as equivariant gluing along orbits of two S^6's

In the Lagrange-Newton method, where Newton's method is applied to a Lagrangian function that includes equality constraints, all stationary points are saddle points. It is therefore not possible to use a line-search method based on the value of the objective function; instead, the line search can operate on merit functions. In this report, we explore an alternative line-search method which is applicable to this case; it particulary addresses the damping of the step length in tight valleys. We propose a line-search criterion based on the divergence of the field of Newton step vectors. The visualization of the criterion for two-dimensional test functions reveals a network of ravines with flat bottom at the zero points of the criterion. The ravines are typically connected to stationary points. To traverse this ravine network in order to approach a stationary point, a zigzag strategy is devised. Numerical experiments demonstrate that the novel line-search strategy succeeds from most starting points in all test functions, but only exhibits the desired damping of the step length in some situations. At the present stage it is therefore difficult to appraise the utility of this contribution.