@article{molina-fructuoso_murray_2024, title={EIKONAL DEPTH: AN OPTIMAL CONTROL APPROACH TO STATISTICAL DEPTHS}, volume={4}, ISSN={["2639-8001"]}, DOI={10.3934/fods.2024016}, abstractNote={Statistical depths provide a fundamental generalization of quantiles and medians to data in higher dimensions.This paper proposes a new type of globally defined statistical depth, based upon control theory and eikonal equations, which measures the smallest amount of probability density that has to be passed through in a path to locations on the boundary of the support of the distribution or spatial infinity for distributions with unbounded support.This depth is easy to interpret and compute, expressively captures multi-modal behavior, and extends naturally to data that is non-Euclidean.We prove various properties of this depth, and provide discussion of computational considerations.In particular, we demonstrate that this notion of depth is robust under an approximate isometrically constrained adversarial model, a property which is not enjoyed by the Tukey depth.Finally we give some illustrative examples in the context of two-dimensional mixture models and MNIST.}, journal={FOUNDATIONS OF DATA SCIENCE}, author={Molina-Fructuoso, Martin and Murray, Ryan}, year={2024}, month={Apr} } @article{murray_wilcox_2024, title={NON-LINEAR SINGULARITY FORMATION FOR CIRCULAR VORTEX SHEETS (vol 82, pg 81, 2024)}, volume={2}, ISSN={["1552-4485"]}, DOI={10.1090/qam/1688}, abstractNote={This paper serves as a short corrigendum, describing an error in the derivation of the linearized equation. The main theorems remain correct, but they are based upon an incorrect linearization of the Birkhoff-Rott equation and hence are not directly applicable to the original physical problem.}, journal={QUARTERLY OF APPLIED MATHEMATICS}, author={Murray, Ryan and Wilcox, Galen}, year={2024}, month={Feb} } @article{murray_wilcox_2023, title={NON-LINEAR SINGULARITY FORMATION FOR CIRCULAR VORTEX SHEETS}, volume={5}, ISSN={["1552-4485"]}, DOI={10.1090/qam/1659}, abstractNote={We study the evolution of vortex sheets according to the Birkhoff-Rott equation, which describe the motion of sharp shear interfaces governed by the incompressible Euler equation in two dimensions. In a recent work, the authors demonstrated within this context a marginal linear stability of circular vortex sheets, standing in sharp contrast with classical instability of the flat vortex sheet, which is known as the Kelvin-Helmholtz instability. This article continues that analysis by investigating how non-linear effects induce singularity formation near the circular vortex sheet. In high-frequency regimes, the singularity formation is primarily driven by a complex-valued, conjugated Burgers equation, which we study by modifying a classical argument from hyperbolic conservation laws. This provides a deeper understanding of the mechanisms driving the breakdown of circular vortex sheets, which are observed both numerically and experimentally.}, journal={QUARTERLY OF APPLIED MATHEMATICS}, author={Murray, Ryan and Wilcox, Galen}, year={2023}, month={May} } @article{trillos_murray_thorpe_2023, title={Rates of convergence for regression with the graph poly-Laplacian}, volume={21}, ISSN={["2730-5724"]}, DOI={10.1007/s43670-023-00075-5}, abstractNote={Abstract In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularization. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularization in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset $$\{x_i\}_{i=1}^n$$ { x i } i = 1 n and a set of noisy labels $$\{y_i\}_{i=1}^n\subset \mathbb {R}$$ { y i } i = 1 n R we let $$u_n{:}\{x_i\}_{i=1}^n\rightarrow \mathbb {R}$$ u n : { x i } i = 1 n R be the minimizer of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When $$y_i = g(x_i)+\xi _i$$ y i = g ( x i ) + ξ i , for iid noise $$\xi _i$$ ξ i , and using the geometric random graph, we identify (with high probability) the rate of convergence of $$u_n$$ u n to g in the large data limit $$n\rightarrow \infty $$ n . Furthermore, our rate is close to the known rate of convergence in the usual smoothing spline model.}, number={2}, journal={SAMPLING THEORY SIGNAL PROCESSING AND DATA ANALYSIS}, author={Trillos, Nicolas Garcia and Murray, Ryan and Thorpe, Matthew}, year={2023}, month={Dec} } @article{bungert_trillos_murray_2023, title={The geometry of adversarial training in binary classification}, volume={1}, ISSN={["2049-8772"]}, DOI={10.1093/imaiai/iaac029}, abstractNote={AbstractWe establish an equivalence between a family of adversarial training problems for non-parametric binary classification and a family of regularized risk minimization problems where the regularizer is a nonlocal perimeter functional. The resulting regularized risk minimization problems admit exact convex relaxations of the type $L^1+\text{(nonlocal)}\operatorname{TV}$, a form frequently studied in image analysis and graph-based learning. A rich geometric structure is revealed by this reformulation which in turn allows us to establish a series of properties of optimal solutions of the original problem, including the existence of minimal and maximal solutions (interpreted in a suitable sense) and the existence of regular solutions (also interpreted in a suitable sense). In addition, we highlight how the connection between adversarial training and perimeter minimization problems provides a novel, directly interpretable, statistical motivation for a family of regularized risk minimization problems involving perimeter/total variation. The majority of our theoretical results are independent of the distance used to define adversarial attacks.}, journal={INFORMATION AND INFERENCE-A JOURNAL OF THE IMA}, author={Bungert, Leon and Trillos, Nicolas Garcia and Murray, Ryan}, year={2023}, month={Jan} } @article{adversarial classification: necessary conditions and geometric flows_2022, volume={23}, number={187}, journal={Journal of Machine Learning Research}, year={2022}, pages={1–38} } @article{trillos_murray_thorpe_2022, title={From Graph Cuts to Isoperimetric Inequalities: Convergence Rates of Cheeger Cuts on Data Clouds}, volume={4}, ISSN={["1432-0673"]}, DOI={10.1007/s00205-022-01770-8}, abstractNote={AbstractIn this work we study statistical properties of graph-based clustering algorithms that rely on the optimization of balanced graph cuts, the main example being the optimization of Cheeger cuts. We consider proximity graphs built from data sampled from an underlying distribution supported on a generic smooth compact manifold$${\mathcal {M}}$$M. In this setting, we obtain high probability convergence rates for both the Cheeger constant and the associated Cheeger cuts towards their continuum counterparts. The key technical tools are careful estimates of interpolation operators which lift empirical Cheeger cuts to the continuum, as well as continuum stability estimates for isoperimetric problems. To the best of our knowledge the quantitative estimates obtained here are the first of their kind.}, journal={ARCHIVE FOR RATIONAL MECHANICS AND ANALYSIS}, author={Trillos, Nicolas Garcia and Murray, Ryan and Thorpe, Matthew}, year={2022}, month={Apr} } @article{molina-fructuoso_murray_2022, title={Tukey Depths and Hamilton-Jacobi Differential Equations}, volume={4}, ISSN={["2577-0187"]}, url={https://doi.org/10.1137/21M1411998}, DOI={10.1137/21M1411998}, abstractNote={Widespread application of modern machine learning has increased the need for robust statistical algorithms. This work studies one such fundamental statistical measure known as the Tukey depth. We study the problem in the continuum (population) limit. In particular, we derive the associated necessary conditions, which take the form of a first-order partial differential equation. We discuss the classical interpretation of this necessary condition as the viscosity solution of a Hamilton-Jacobi equation, but with a non-classical Hamiltonian with discontinuous dependence on the gradient at zero. We prove that this equation possesses a unique viscosity solution, and that this solution always bounds the Tukey depth from below. In certain cases we prove that the Tukey depth is equal to the viscosity solution, and we give some illustrations of standard numerical methods from the optimal control community which deal directly with the partial differential equation. We conclude by outlining several promising research directions both in terms of new numerical algorithms and theoretical challenges.}, number={2}, journal={SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE}, author={Molina-Fructuoso, Martin and Murray, Ryan}, year={2022}, pages={604–633} } @article{swenson_murray_poor_kar_2022, title={Distributed Gradient Flow: Nonsmoothness, Nonconvexity, and Saddle Point Evasion}, volume={67}, ISSN={["1558-2523"]}, url={https://doi.org/10.1109/TAC.2021.3111853}, DOI={10.1109/TAC.2021.3111853}, abstractNote={The article considers distributed gradient flow (DGF) for multiagent nonconvex optimization. DGF is a continuous-time approximation of distributed gradient descent that is often easier to study than its discrete-time counterpart. The article has two main contributions. First, the article considers optimization of nonsmooth, nonconvex objective functions. It is shown that DGF converges to critical points in this setting. The article then considers the problem of avoiding saddle points. It is shown that if agents’ objective functions are assumed to be smooth and nonconvex, then DGF can only converge to a saddle point from a zero-measure set of initial conditions. To establish this result, the article proves a stable manifold theorem for DGF, which is a fundamental contribution of independent interest. In a companion article, analogous results are derived for discrete-time algorithms.}, number={8}, journal={IEEE TRANSACTIONS ON AUTOMATIC CONTROL}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Swenson, Brian and Murray, Ryan and Poor, H. Vincent and Kar, Soummya}, year={2022}, month={Aug}, pages={3949–3964} } @article{murray_fokoue_2021, title={Dropout Fails to Regularize Nonparametric Learners}, volume={15}, ISSN={["1559-8616"]}, url={https://doi.org/10.1007/s42519-020-00158-9}, DOI={10.1007/s42519-020-00158-9}, number={2}, journal={JOURNAL OF STATISTICAL THEORY AND PRACTICE}, publisher={Springer Science and Business Media LLC}, author={Murray, Ryan W. and Fokoue, Ernest}, year={2021}, month={Jan} } @article{bressan_murray_2020, title={On self-similar solutions to the incompressible Euler equations}, volume={269}, ISSN={["1090-2732"]}, DOI={10.1016/j.jde.2020.04.005}, abstractNote={Recent numerical simulations have shown the existence of multiple self-similar solutions to the Cauchy problem for the 2-dimensional incompressible Euler equation, with initial vorticity in L l o c p ( R 2 ) , 1 ≤ p < + ∞ . Toward a rigorous validation of these computations, in this paper we analytically construct self-similar solutions (i) on an outer domain of the form { | x | > R } , and (ii) in a neighborhood of the points where the solution exhibits a spiraling vortex singularity. The outer solution is obtained as the fixed point of a contractive transformation, based on the Biot-Savart formula and integration along characteristics. The inner solution is constructed using a system of adapted coordinates, following the approach of V. Elling (2016) [17] .}, number={6}, journal={JOURNAL OF DIFFERENTIAL EQUATIONS}, author={Bressan, Alberto and Murray, Ryan}, year={2020}, month={Sep}, pages={5142–5203} } @article{swenson_murray_kar_2020, title={Regular potential games}, volume={124}, url={https://doi.org/10.1016/j.geb.2020.09.005}, DOI={10.1016/j.geb.2020.09.005}, abstractNote={Abstract A fundamental problem with the Nash equilibrium concept is the existence of certain “structurally deficient” equilibria that (i) lack fundamental robustness properties, and (ii) are difficult to analyze. The notion of a “regular” Nash equilibrium was introduced by Harsanyi. Such equilibria are isolated, highly robust, and relatively simple to analyze. A game is said to be regular if all equilibria in the game are regular. In this paper it is shown that almost all potential games are regular. That is, except for a closed subset with Lebesgue measure zero, all potential games are regular. As an immediate consequence of this, the paper also proves an oddness result for potential games: In almost all potential games, the number of Nash equilibrium strategies is finite and odd. Specialized results are given for weighted potential games, exact potential games, and games with identical payoffs. Applications of the results to game-theoretic learning are discussed.}, journal={Games and Economic Behavior}, publisher={Elsevier BV}, author={Swenson, Brian and Murray, Ryan and Kar, Soummya}, year={2020}, month={Nov}, pages={432–453} } @article{trillos_murray_2020, title={y A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors}, volume={2}, ISSN={["2577-0187"]}, url={https://doi.org/10.1137/19M1245372}, DOI={10.1137/19M1245372}, abstractNote={We study asymptotic consistency guarantees for a non-parametric regression problem with Laplacian regularization. In particular, we consider $(x_1, y_1), \dots, (x_n, y_n)$ samples from some distribution on the cross product $\mathcal{M} \times \mathbb{R}$, where $\mathcal{M}$ is a $m$-dimensional manifold embedded in $\mathbb{R}^d$. A geometric graph on the cloud $\{x_1, \dots, x_n \}$ is constructed by connecting points that are within some specified distance $\varepsilon_n$. A suitable semi-linear equation involving the resulting graph Laplacian is used to obtain a regressor for the observed values of $y$. We establish probabilistic error rates for the uniform difference between the regressor constructed from the observed data and the Bayes regressor (or trend) associated to the ground-truth distribution. We give the explicit dependence of the rates in terms of the parameter $\varepsilon_n$, the strength of regularization $\beta_n$, and the number of data points $n$. Our argument relies on a simple, yet powerful, maximum principle for the graph Laplacian. We also address a simple extension of the framework to a semi-supervised setting.}, number={3}, journal={SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Trillos, Nicolas Garcia and Murray, Ryan W.}, year={2020}, pages={705–739} } @article{murray_young_2020, title={Neutral competition in a deterministically changing environment: Revisiting continuum approaches}, volume={486}, ISSN={["1095-8541"]}, DOI={10.1016/j.jtbi.2019.110104}, abstractNote={Environmental variation can play an important role in ecological competition by influencing the relative advantage between competing species. Here, we consider such effects by extending a classical, competitive Moran model to incorporate an environment that fluctuates periodically in time. We adapt methods from work on these classical models to investigate the effects of the magnitude and frequency of environmental fluctuations on two important population statistics: the probability of fixation and the mean time to fixation. In particular, we find that for small frequencies, the system behaves similar to a system with a constant fitness difference between the two species, and for large frequencies, the system behaves similar to a neutrally competitive model. Most interestingly, the system exhibits nontrivial behavior for intermediate frequencies. We conclude by showing that our results agree quite well with recent theoretical work on competitive models with a stochastically changing environment, and discuss how the methods we develop ease the mathematical analysis required to study such models.}, journal={JOURNAL OF THEORETICAL BIOLOGY}, author={Murray, Ryan and Young, Glenn}, year={2020}, month={Feb} } @article{murray_swenson_kar_2019, title={Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points}, volume={64}, url={https://doi.org/10.1109/TAC.2019.2914998}, DOI={10.1109/TAC.2019.2914998}, abstractNote={The paper considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. It is shown that, contrary to GD, NGD escapes saddle points “quickly.” A serious shortcoming of GD in nonconvex problems is that it can take arbitrarily long to escape from the neighborhood of a saddle point. In practice, this issue can significantly slow the convergence of GD, particularly in high-dimensional nonconvex problems. The paper focuses on continuous-time dynamics. It is shown that 1) NGD “almost never” converges to saddle points and 2) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^*$ is at most $5\sqrt{\kappa }r$, where $\kappa$ is the condition number of the Hessian of $f$ at $x^*$. As a simple application of these results, a global convergence-time bound is established for NGD under mild assumptions.}, number={11}, journal={IEEE Transactions on Automatic Control}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Murray, Ryan and Swenson, Brian and Kar, Soummya}, year={2019}, month={Nov}, pages={4818–4824} } @article{murray_palladino_2018, title={A model for system uncertainty in reinforcement learning}, volume={122}, url={https://doi.org/10.1016/j.sysconle.2018.09.011}, DOI={10.1016/j.sysconle.2018.09.011}, abstractNote={This work provides a rigorous framework for studying continuous-time control problems in uncertain environments. The framework models uncertainty in state dynamics as a probability measure on the space of functions. Such a probability measure is permitted to change over time as agents learn about their environment. This model can be seen as a variant of either Bayesian reinforcement learning (RL) or adaptive optimal control. We study conditions for locally optimal trajectories within this model, in particular deriving an appropriate dynamic programming principle and Hamilton–Jacobi equations. Some discussion of variants of the model are also provided, including one potential framework for studying the tradeoff between exploration and exploitation in RL.}, journal={Systems & Control Letters}, publisher={Elsevier BV}, author={Murray, Ryan and Palladino, Michele}, year={2018}, month={Dec}, pages={24–31} } @article{swenson_murray_kar_poor_2018, title={Best-Response Dynamics in Continuous Potential Games: Non-Convergence to Saddle Points}, DOI={10.1109/acssc.2018.8645541}, abstractNote={The paper studies properties of best-response (BR) dynamics in potential games with continuous action sets. It is known that BR dynamics converge to the set of Nash equilibria (NE) in potential games. The set of NE in potential games is composed of local maximizers and saddle points of the potential function. The paper studies non-convergence of BR dynamics to saddle points of the potential function. Under relatively mild assumptions it is shown that BR dynamics may only converge to an interior saddle-point from a measure-zero set of initial conditions. This provides a weak stable manifold theorem in this context.}, journal={2018 52nd Asilomar Conference on Signals, Systems, and Computers}, publisher={IEEE}, author={Swenson, Brian and Murray, Ryan and Kar, Soummya and Poor, H. Vincent}, year={2018}, month={Oct} } @article{swenson_murray_kar_2018, title={On Best-Response Dynamics in Potential Games}, volume={56}, DOI={10.1137/17m1139461}, abstractNote={The paper studies the convergence properties of (continuous-time) best-response dynamics from game theory. Despite their fundamental role in game theory, best-response dynamics are poorly understoo...}, number={4}, journal={SIAM Journal on Control and Optimization}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Swenson, Brian and Murray, Ryan and Kar, Soummya}, year={2018}, month={Jan}, pages={2734–2767} } @article{trillos_murray_2017, title={A new analytical approach to consistency and overfitting in regularized empirical risk minimization}, volume={28}, DOI={10.1017/s0956792517000201}, abstractNote={This work considers the problem of binary classification: given training data x1, . . ., xn from a certain population, together with associated labels y1,. . ., yn ∈ {0,1}, determine the best label for an element x not among the training data. More specifically, this work considers a variant of the regularized empirical risk functional which is defined intrinsically to the observed data and does not depend on the underlying population. Tools from modern analysis are used to obtain a concise proof of asymptotic consistency as regularization parameters are taken to zero at rates related to the size of the sample. These analytical tools give a new framework for understanding overfitting and underfitting, and rigorously connect the notion of overfitting with a loss of compactness.}, number={6}, journal={European Journal of Applied Mathematics}, publisher={Cambridge University Press (CUP)}, author={TRILLOS, NICOLÁS GARCÍA and MURRAY, RYAN}, year={2017}, month={Jul}, pages={886–921} } @article{murray_pego_2017, title={Cutoff estimates for the linearized Becker–Döring equations}, volume={15}, DOI={10.4310/cms.2017.v15.n6.a10}, abstractNote={. This paper continues the authors’ previous study [R. Murray and R. Pego, SIAM J. Math. Anal., 48:2819–2842, 2016] of the trend toward equilibrium of the Becker–D¨oring equations with subcritical mass, by characterizing certain fine properties of solutions to the linearized equation. In particular, we partially characterize the spectrum of the linearized operator, showing that it contains the entire imaginary axis in polynomially weighted spaces. Moreover, we prove detailed cutoff estimates that establish upper and lower bounds on the lifetime of a class of perturbations to equilibrium.}, number={6}, journal={Communications in Mathematical Sciences}, publisher={International Press of Boston}, author={Murray, Ryan W. and Pego, Robert L.}, year={2017}, pages={1685–1702} } @article{leoni_murray_2019, title={Local minimizers and slow motion for the mass preserving Allen–Cahn equation in higher dimensions}, volume={147}, DOI={10.1090/proc/13988}, abstractNote={This paper completely resolves the asymptotic development of order 2 2 by Γ \Gamma -convergence of the mass-constrained Cahn–Hilliard functional. Important new results on the slow motion of interfaces for the mass preserving Allen–Cahn equation and the Cahn–Hilliard equations in higher dimension are obtained as an application.}, number={12}, journal={Proceedings of the American Mathematical Society}, publisher={American Mathematical Society (AMS)}, author={Leoni, Giovanni and Murray, Ryan}, year={2019}, month={Sep}, pages={5167–5182} } @article{murray_pego_2016, title={Algebraic Decay to Equilibrium for the Becker--Döring Equations}, volume={48}, DOI={10.1137/15m1038578}, abstractNote={This paper studies rates of decay to equilibrium for the Becker--Doring equations with subcritical initial data. In particular, algebraic rates of decay are established when initial perturbations of equilibrium have polynomial moments. This is proved by using new dissipation estimates in polynomially weighted $\ell^1$ spaces, operator decomposition techniques from kinetic theory, and interpolation estimates from the study of traveling waves.}, number={4}, journal={SIAM Journal on Mathematical Analysis}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Murray, Ryan W. and Pego, Robert L.}, year={2016}, month={Jan}, pages={2819–2842} } @article{leoni_murray_2015, title={Second-Order Γ-limit for the Cahn–Hilliard Functional}, volume={219}, DOI={10.1007/s00205-015-0924-4}, abstractNote={The goal of this paper is to solve a long standing open problem, namely, the asymptotic development of order 2 by Γ-convergence of the mass-constrained Cahn–Hilliard functional.}, number={3}, journal={Archive for Rational Mechanics and Analysis}, publisher={Springer Science and Business Media LLC}, author={Leoni, Giovanni and Murray, Ryan}, year={2015}, month={Sep}, pages={1383–1451} }