JournalTOCs

SIAM Journal on Mathematics of Data Science
Number of Followers: 2

Hybrid journal (It can contain Open Access articles)
ISSN (Online) 2577-0187
Published by Society for Industrial and Applied Mathematics

[17 journals]

Robust Inference of Manifold Density and Geometry by Doubly Stochastic
Scaling
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Boris Landa, Xiuyuan Cheng
  Pages: 589 - 614
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 589-614, September 2023.
  Abstract. The Gaussian kernel and its traditional normalizations (e.g., row-stochastic) are popular approaches for assessing similarities between data points. Yet, they can be inaccurate under high-dimensional noise, especially if the noise magnitude varies considerably across the data, e.g., under heteroskedasticity or outliers. In this work, we investigate a more robust alternative—the doubly stochastic normalization of the Gaussian kernel. We consider a setting where points are sampled from an unknown density on a low-dimensional manifold embedded in high-dimensional space and corrupted by possibly strong, non–identically distributed, sub-Gaussian noise. We establish that the doubly stochastic affinity matrix and its scaling factors concentrate around certain population forms, and provide corresponding finite-sample probabilistic bounds. We then utilize these results to develop several tools for robust inference under general high-dimensional noise. First, we derive a robust density estimator that reliably infers the underlying sampling density and can substantially outperform the standard kernel density estimator under heteroskedasticity and outliers. Second, we obtain estimators for the pointwise noise magnitudes, the pointwise signal magnitudes, and the pairwise Euclidean distances between clean data points. Lastly, we derive robust graph Laplacian normalizations that accurately approximate various manifold Laplacians, including the Laplace–Beltrami operator, improving over traditional normalizations in noisy settings. We exemplify our results in simulations and on real single-cell RNA-sequencing data. For the latter, we show that in contrast to traditional methods, our approach is robust to variability in technical noise levels across cell types.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-07-20T07:00:00Z
  DOI: 10.1137/22M1516968
  Issue No: Vol. 5, No. 3 (2023)
Approximate Q Learning for Controlled Diffusion Processes and Its Near
Optimality
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Erhan Bayraktar, Ali Devran Kara
  Pages: 615 - 638
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 615-638, September 2023.
  Abstract. We study a Q learning algorithm for continuous time stochastic control problems. The proposed algorithm uses the sampled state process by discretizing the state and control action spaces under piecewise constant control processes. We show that the algorithm converges to the optimality equation of a finite Markov decision process (MDP). Using this MDP model, we provide an upper bound for the approximation error for the optimal value function of the continuous time control problem. Furthermore, we present provable upper bounds for the performance loss of the learned control process compared to the optimal admissible control process of the original problem. The provided error upper bounds are functions of the time and space discretization parameters, and they reveal the effect of different levels of the approximation: (i) approximation of the continuous time control problem by an MDP, (ii) use of piecewise constant control processes, and (iii) space discretization. Finally, we state a time complexity bound for the proposed algorithm as a function of the time and space discretization parameters.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-07-20T07:00:00Z
  DOI: 10.1137/22M1484201
  Issue No: Vol. 5, No. 3 (2023)
An Improved Central Limit Theorem and Fast Convergence Rates for Entropic
Transportation Costs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Eustasio del Barrio, Alberto González Sanz, Jean-Michel Loubes, Jonathan Niles-Weed
  Pages: 639 - 669
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 639-669, September 2023.
  Abstract. We prove a central limit theorem for the entropic transportation cost between subgaussian probability measures, centered at the population cost. This is the first result which allows for asymptotically valid inference for entropic optimal transport between measures which are not necessarily discrete. In the compactly supported case, we complement these results with new, faster, convergence rates for the expected entropic transportation cost between empirical measures. Our proof is based on strengthening convergence results for dual solutions to the entropic optimal transport problem.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-07-21T07:00:00Z
  DOI: 10.1137/22M149260X
  Issue No: Vol. 5, No. 3 (2023)
A Note on the Regularity of Images Generated by Convolutional Neural
Networks
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Andreas Habring, Martin Holler
  Pages: 670 - 692
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 670-692, September 2023.
  Abstract. The regularity of images generated by a class of convolutional neural networks, such as the U-net, generative networks, or the deep image prior, is analyzed. In a resolution-independent, infinite dimensional setting, it is shown that such images, represented as functions, are always continuous and, in some circumstances, even continuously differentiable, contradicting the widely accepted modeling of sharp edges in images via jump discontinuities. While such statements require an infinite dimensional setting, the connection to (discretized) neural networks used in practice is made by considering the limit as the resolution approaches infinity. As a practical consequence, the results of this paper in particular provide analytical evidence that basic [math] regularization of network weights (also known as weight decay) might lead to oversmoothed outputs.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-07-21T07:00:00Z
  DOI: 10.1137/22M1525995
  Issue No: Vol. 5, No. 3 (2023)
Optimality Conditions for Nonsmooth Nonconvex-Nonconcave Min-Max Problems
and Generative Adversarial Networks
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Jie Jiang, Xiaojun Chen
  Pages: 693 - 722
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 693-722, September 2023.
  Abstract. This paper considers a class of nonsmooth nonconvex-nonconcave min-max problems in machine learning and games. We first provide sufficient conditions for the existence of global minimax points and local minimax points. Next, we establish the first-order and second-order optimality conditions for local minimax points by using directional derivatives. These conditions reduce to smooth min-max problems with Fréchet derivatives. We apply our theoretical results to generative adversarial networks (GANs) in which two neural networks contest with each other in a game. Examples are used to illustrate applications of the new theory for training GANs.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-08-10T07:00:00Z
  DOI: 10.1137/22M1482238
  Issue No: Vol. 5, No. 3 (2023)
Algorithmic Regularization in Model-Free Overparametrized Asymmetric
Matrix Factorization
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Liwei Jiang, Yudong Chen, Lijun Ding
  Pages: 723 - 744
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 723-744, September 2023.
  Abstract. We study the asymmetric matrix factorization problem under a natural nonconvex formulation with arbitrary overparametrization. The model-free setting is considered, with minimal assumption on the rank or singular values of the observed matrix, where the global optima provably overfit. We show that vanilla gradient descent with small random initialization sequentially recovers the principal components of the observed matrix. Consequently, when equipped with proper early stopping, gradient descent produces the best low-rank approximation of the observed matrix without explicit regularization. We provide a sharp characterization of the relationship between the approximation error, iteration complexity, initialization size, and stepsize. Our complexity bound is almost dimension-free and depends logarithmically on the approximation error, with significantly more lenient requirements on the stepsize and initialization compared to prior work. Our theoretical results provide accurate prediction for the behavior of gradient descent, showing good agreement with numerical experiments.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-08-11T07:00:00Z
  DOI: 10.1137/22M1519833
  Issue No: Vol. 5, No. 3 (2023)
Satisficing Paths and Independent Multiagent Reinforcement Learning in
Stochastic Games
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Bora Yongacoglu, Gürdal Arslan, Serdar Yüksel
  Pages: 745 - 773
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 745-773, September 2023.
  Abstract. In multiagent reinforcement learning, independent learners are those that do not observe the actions of other agents in the system. Due to the decentralization of information, it is challenging to design independent learners that drive play to equilibrium. This paper investigates the feasibility of using satisficing dynamics to guide independent learners to approximate equilibrium in stochastic games. For [math], an [math]-satisficing policy update rule is any rule that instructs the agent to not change its policy when it is [math]-best-responding to the policies of the remaining players; [math]-satisficing paths are defined to be sequences of joint policies obtained when each agent uses some [math]-satisficing policy update rule to select its next policy. We establish structural results on the existence of [math]-satisficing paths into [math]-equilibrium in both symmetric [math]-player games and general stochastic games with two players. We then present an independent learning algorithm for [math]-player symmetric games and give high probability guarantees of convergence to [math]-equilibrium under self-play. This guarantee is made using symmetry alone, leveraging the previously unexploited structure of [math]-satisficing paths.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-08-24T07:00:00Z
  DOI: 10.1137/22M1515112
  Issue No: Vol. 5, No. 3 (2023)
Randomly Initialized Alternating Least Squares: Fast Convergence for
Matrix Sensing
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Kiryung Lee, Dominik Stöger
  Pages: 774 - 799
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 3, Page 774-799, September 2023.
  Abstract. We consider the problem of reconstructing rank-1 matrices from random linear measurements, a task that appears in a variety of problems in signal processing, statistics, and machine learning. In this paper, we focus on the alternating least squares (ALS) method. While this algorithm has been studied in a number of previous works, most of them only show convergence from an initialization close to the true solution and thus require a carefully designed initialization scheme. However, random initialization has often been preferred by practitioners as it is model-agnostic. In this paper, we show that ALS with random initialization converges to the true solution with [math]-accuracy in [math] iterations using only a near-optimal number of samples, where we assume the measurement matrices to be i.i.d. Gaussian and where by [math] we denote the ambient dimension. We observe that the convergence occurs in two phases. In the first phase, the iterates starting from random initialization become gradually more aligned with the true signal, and in the second phase the iterates converge linearly. Key to our proof is the observation that in the first phase the trajectory of the ALS iterates depends only very mildly on certain entries of the random measurement matrices. Numerical experiments corroborate our theoretical predictions.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-09-06T07:00:00Z
  DOI: 10.1137/22M1506456
  Issue No: Vol. 5, No. 3 (2023)
Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Philip Chodrow, Nicole Eikmeier, Jamie Haddock
  Pages: 251 - 279
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 251-279, June 2023.
  Abstract. Spectral methods offer a tractable, global framework for clustering in graphs via eigenvector computations on graph matrices. Hypergraph data, in which entities interact on edges of arbitrary size, poses challenges for matrix representations and therefore for spectral clustering. We study spectral clustering for nonuniform hypergraphs based on the hypergraph nonbacktracking operator. After reviewing the definition of this operator and its basic properties, we prove a theorem of Ihara–Bass type which allows eigenpair computations to take place on a smaller matrix, often enabling faster computation. We then propose an alternating algorithm for inference in a hypergraph stochastic blockmodel via linearized belief-propagation which involves a spectral clustering step again using nonbacktracking operators. We provide proofs related to this algorithm that both formalize and extend several previous results. We pose several conjectures about the limits of spectral methods and detectability in hypergraph stochastic blockmodels in general, supporting these with in-expectation analysis of the eigenpairs of our operators. We perform experiments in real and synthetic data that demonstrate the benefits of hypergraph methods over graph-based ones when interactions of different sizes carry different information about cluster structure.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-04-26T07:00:00Z
  DOI: 10.1137/22M1494713
  Issue No: Vol. 5, No. 2 (2023)
Causal Structural Learning via Local Graphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Wenyu Chen, Mathias Drton, Ali Shojaie
  Pages: 280 - 305
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 280-305, June 2023.
  Abstract. We consider the problem of learning causal structures in sparse high-dimensional settings that may be subject to the presence of (potentially many) unmeasured confounders, as well as selection bias. Based on structure found in common families of large random networks, we propose a new local notion of sparsity for structure learning in the presence of latent and selection variables, and develop a new version of the fast causal inference (FCI) algorithm, which we refer to as local FCI (lFCI). Under the new sparsity condition and an additional assumption that ensures that conditional dependencies can be determined locally, lFCI is consistent and offers reduced computational and sample complexity when compared to standard FCI algorithms. The new notion of sparsity allows the presence of highly connected hub nodes, which are common in real-world networks but problematic for existing methods. Our numerical experiments indicate that the lFCI algorithm achieves state-of-the-art performance across many classes of large random networks, and its performance is superior to that of existing methods for networks containing hub nodes.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-05-12T07:00:00Z
  DOI: 10.1137/20M1362796
  Issue No: Vol. 5, No. 2 (2023)
Approximation of Lipschitz Functions Using Deep Spline Neural Networks
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Sebastian Neumayer, Alexis Goujon, Pakshal Bohra, Michael Unser
  Pages: 306 - 322
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 306-322, June 2023.
  Abstract. Although Lipschitz-constrained neural networks have many applications in machine learning, the design and training of expressive Lipschitz-constrained networks is very challenging. Since the popular rectified linear-unit networks have provable disadvantages in this setting, we propose using learnable spline activation functions with at least three linear regions instead. We prove that our choice is universal among all componentwise 1-Lipschitz activation functions in the sense that no other weight-constrained architecture can approximate a larger class of functions. Additionally, our choice is at least as expressive as the recently introduced non-componentwise Groupsort activation function for spectral-norm-constrained weights. The theoretical findings of this paper are consistent with previously published numerical results.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-05-15T07:00:00Z
  DOI: 10.1137/22M1504573
  Issue No: Vol. 5, No. 2 (2023)
Taming Neural Networks with TUSLA: Nonconvex Learning via Adaptive
Stochastic Gradient Langevin Algorithms
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Attila Lovas, Iosif Lytras, Miklós Rásonyi, Sotirios Sabanis
  Pages: 323 - 345
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 323-345, June 2023.
  Abstract. Artificial neural networks (ANNs) are typically highly nonlinear systems which are finely tuned via the optimization of their associated, nonconvex loss functions. In many cases, the gradient of any such loss function has superlinear growth, making the use of the widely accepted (stochastic) gradient descent methods, which are based on Euler numerical schemes, problematic. We offer a new learning algorithm based on an appropriately constructed variant of the popular stochastic gradient Langevin dynamics (SGLD), which is called the tamed unadjusted stochastic Langevin algorithm (TUSLA). We also provide a nonasymptotic analysis of the new algorithm’s convergence properties in the context of nonconvex learning problems with the use of ANNs. Thus, we provide finite-time guarantees for TUSLA to find approximate minimizers of both empirical and population risks. The roots of the TUSLA algorithm are based on the taming technology for diffusion processes with superlinear coefficients as developed in [S. Sabanis, Electron. Commun. Probab., 18 (2013), pp. 1–10] and [S. Sabanis, Ann. Appl. Probab., 26 (2016), pp. 2083–2105] and for Markov chain Monte Carlo algorithms in [N. Brosse, A. Durmus, É. Moulines, and S. Sabanis, Stochastic Process. Appl., 129 (2019), pp. 3638–3663]. Numerical experiments are presented which confirm the theoretical findings and illustrate the need for the use of the new algorithm in comparison to vanilla SGLD within the framework of ANNs.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-05-18T07:00:00Z
  DOI: 10.1137/22M1514283
  Issue No: Vol. 5, No. 2 (2023)
Time-Inhomogeneous Diffusion Geometry and Topology
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Guillaume Huguet, Alexander Tong, Bastian Rieck, Jessie Huang, Manik Kuchroo, Matthew Hirn, Guy Wolf, Smita Krishnaswamy
  Pages: 346 - 372
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 346-372, June 2023.
  . Diffusion condensation is a dynamic process that yields a sequence of multiscale data representations that aim to encode meaningful abstractions. It has proven effective for manifold learning, denoising, clustering, and visualization of high-dimensional data. Diffusion condensation is constructed as a time-inhomogeneous process where each step first computes a diffusion operator and then applies it to the data. We theoretically analyze the convergence and evolution of this process from geometric, spectral, and topological perspectives. From a geometric perspective, we obtain convergence bounds based on the smallest transition probability and the radius of the data, whereas from a spectral perspective, our bounds are based on the eigenspectrum of the diffusion kernel. Our spectral results are of particular interest since most of the literature on data diffusion is focused on homogeneous processes. From a topological perspective, we show that diffusion condensation generalizes centroid-based hierarchical clustering. We use this perspective to obtain a bound based on the number of data points, independent of their location. To understand the evolution of the data geometry beyond convergence, we use topological data analysis. We show that the condensation process itself defines an intrinsic condensation homology. We use this intrinsic topology, as well as the ambient persistent homology, of the condensation process to study how the data changes over diffusion time. We demonstrate both types of topological information in well-understood toy examples. Our work gives theoretical insight into the convergence of diffusion condensation and shows that it provides a link between topological and geometric data analysis.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-05-22T07:00:00Z
  DOI: 10.1137/21M1462945
  Issue No: Vol. 5, No. 2 (2023)
Post-training Quantization for Neural Networks with Provable Guarantees
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Jinjie Zhang, Yixuan Zhou, Rayan Saab
  Pages: 373 - 399
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 373-399, June 2023.
  Abstract. While neural networks have been remarkably successful in a wide array of applications, implementing them in resource-constrained hardware remains an area of intense research. By replacing the weights of a neural network with quantized (e.g., 4-bit, or binary) counterparts, massive savings in computation cost, memory, and power consumption are attained. To that end, we generalize a post-training neural network quantization method, GPFQ, that is based on a greedy path-following mechanism. Among other things, we propose modifications to promote sparsity of the weights, and rigorously analyze the associated error. Additionally, our error analysis expands the results of previous work on GPFQ to handle general quantization alphabets, showing that for quantizing a single-layer network, the relative square error essentially decays linearly in the number of weights, i.e., level of overparametrization. Our result holds across a range of input distributions and for both fully connected and convolutional architectures thereby also extending previous results. To empirically evaluate the method, we quantize several common architectures with few bits per weight, and test them on ImageNet, showing only minor loss of accuracy compared to unquantized models. We also demonstrate that standard modifications, such as bias correction and mixed precision quantization, further improve accuracy.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-05-31T07:00:00Z
  DOI: 10.1137/22M1511709
  Issue No: Vol. 5, No. 2 (2023)
Moving Up the Cluster Tree with the Gradient Flow
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Ery Arias-Castro, Wanli Qiao
  Pages: 400 - 421
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 400-421, June 2023.
  Abstract. This paper establishes a strong correspondence between two important clustering approaches that emerged in the 1970s: clustering by level sets or cluster tree as proposed by Hartigan, and clustering by gradient lines or gradient flow as proposed by Fukunaga and Hostetler. This correspondence is drawn by showing that the gradient ascent flow provides a natural way to move up the cluster tree.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-05-31T07:00:00Z
  DOI: 10.1137/22M1469869
  Issue No: Vol. 5, No. 2 (2023)
Measuring Complexity of Learning Schemes Using Hessian-Schatten Total
Variation
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Shayan Aziznejad, Joaquim Campos, Michael Unser
  Pages: 422 - 445
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 422-445, June 2023.
  Abstract. In this paper, we introduce the Hessian-Schatten total variation (HTV)—a novel seminorm that quantifies the total “rugosity” of multivariate functions. Our motivation for defining HTV is to assess the complexity of supervised-learning schemes. We start by specifying the adequate matrix-valued Banach spaces that are equipped with suitable classes of mixed norms. We then show that the HTV is invariant to rotations, scalings, and translations. Additionally, its minimum value is achieved for linear mappings, which supports the common intuition that linear regression is the least complex learning model. Next, we present closed-form expressions of the HTV for two general classes of functions. The first one is the class of Sobolev functions with a certain degree of regularity, for which we show that the HTV coincides with the Hessian-Schatten seminorm that is sometimes used as a regularizer for image reconstruction. The second one is the class of continuous and piecewise-linear (CPWL) functions. In this case, we show that the HTV reflects the total change in slopes between linear regions that have a common facet. Hence, it can be viewed as a convex relaxation ([math]-type) of the number of linear regions ([math]-type) of CPWL mappings. Finally, we illustrate the use of our proposed seminorm.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-06-01T07:00:00Z
  DOI: 10.1137/22M147517X
  Issue No: Vol. 5, No. 2 (2023)
Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time
Algorithms and Adversarial Training
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Yatong Bai, Tanmay Gautam, Somayeh Sojoudi
  Pages: 446 - 474
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 446-474, June 2023.
  Abstract. The nonconvexity of the artificial neural network (ANN) training landscape brings optimization difficulties. While the traditional back-propagation stochastic gradient descent algorithm and its variants are effective in certain cases, they can become stuck at spurious local minima and are sensitive to initializations and hyperparameters. Recent work has shown that the training of a ReLU-activated ANN can be reformulated as a convex program, bringing hope to globally optimizing interpretable ANNs. However, naively solving the convex training formulation has an exponential complexity, and even an approximation heuristic requires cubic time. In this work, we characterize the quality of this approximation and develop two efficient algorithms that train ANNs with global convergence guarantees. The first algorithm is based on the alternating direction method of multipliers. It can solve both the exact convex formulation and the approximate counterpart, and it generalizes to a family of convex training formulations. Linear global convergence is achieved, and the initial several iterations often yield a solution with high prediction accuracy. When solving the approximate formulation, the per-iteration time complexity is quadratic. The second algorithm, based on the “sampled convex programs” theory, is simpler to implement. It solves unconstrained convex formulations and converges to an approximately globally optimal classifier. The nonconvexity of the ANN training landscape exacerbates when adversarial training is considered. We apply the robust convex optimization theory to convex training and develop convex formulations that train ANNs robust to adversarial inputs. Our analysis explicitly focuses on one-hidden-layer fully connected ANNs, but can extend to more sophisticated architectures.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-06-01T07:00:00Z
  DOI: 10.1137/21M1467134
  Issue No: Vol. 5, No. 2 (2023)
Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Keaton Hamm, Nick Henscheid, Shujie Kang
  Pages: 475 - 501
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 475-501, June 2023.
  Abstract. In this paper, we propose Wasserstein Isometric Mapping (Wassmap), a nonlinear dimensionality reduction technique that provides solutions to some drawbacks in existing global nonlinear dimensionality reduction algorithms in imaging applications. Wassmap represents images via probability measures in Wasserstein space, then uses pairwise Wasserstein distances between the associated measures to produce a low-dimensional, approximately isometric embedding. We show that the algorithm is able to exactly recover parameters of some image manifolds, including those generated by translations or dilations of a fixed generating measure. Additionally, we show that a discrete version of the algorithm retrieves parameters from manifolds generated from discrete measures by providing a theoretical bridge to transfer recovery results from functional data to discrete data. Testing of the proposed algorithms on various image data manifolds shows that Wassmap yields good embeddings compared with other global and local techniques.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-06-07T07:00:00Z
  DOI: 10.1137/22M1490053
  Issue No: Vol. 5, No. 2 (2023)
Probabilistic Registration for Gaussian Process Three-Dimensional Shape
Modelling in the Presence of Extensive Missing Data
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Filipa M. Valdeira, Ricardo Ferreira, Alessandra Micheletti, Cláudia Soares
  Pages: 502 - 527
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 502-527, June 2023.
  Abstract. We propose a shape fitting/registration method based on a Gaussian processes formulation, suitable for shapes with extensive regions of missing data. Gaussian processes are a proven powerful tool, as they provide a unified setting for shape modelling and fitting. While the existing methods in this area prove to work well for the general case of the human head, when looking at more detailed and deformed data, with a high prevalence of missing data, such as the ears, the results are not satisfactory. In order to overcome this, we formulate the shape fitting problem as a multiannotator Gaussian process regression and establish a parallel with the standard probabilistic registration. The achieved method, the shape fitting Gaussian process (or SFGP), shows better performance when dealing with extensive areas of missing data when compared to a state-of-the-art registration method and current approaches for registration with GP. Experiments are conducted both for a two-dimensional small dataset with several transformations and a three-dimensional dataset of ears.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-06-26T07:00:00Z
  DOI: 10.1137/22M1495494
  Issue No: Vol. 5, No. 2 (2023)
Statistical Analysis of Random Objects Via Metric Measure Laplacians
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Gilles Mordant, Axel Munk
  Pages: 528 - 557
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 528-557, June 2023.
  Abstract. In this paper, we consider a certain convolutional Laplacian for metric measure spaces and investigate its potential for the statistical analysis of complex objects. The spectrum of that Laplacian serves as a signature of the space under consideration and the eigenvectors provide the principal directions of the shape, its harmonics. These concepts are used to assess the similarity of objects or understand their most important features in a principled way which is illustrated in various examples. Adopting a statistical point of view, we define a mean spectral measure and its empirical counterpart. The corresponding limiting process of interest is derived and statistical applications are discussed.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-06-26T07:00:00Z
  DOI: 10.1137/22M1491022
  Issue No: Vol. 5, No. 2 (2023)
Data-Driven Mirror Descent with Input-Convex Neural Networks
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Authors: Hong Ye Tan, Subhadip Mukherjee, Junqi Tang, Carola-Bibiane Schönlieb
  Pages: 558 - 587
  Abstract: SIAM Journal on Mathematics of Data Science, Volume 5, Issue 2, Page 558-587, June 2023.
  Abstract. Learning-to-optimize is an emerging framework that seeks to speed up the solution of certain optimization problems by leveraging training data. Learned optimization solvers have been shown to outperform classical optimization algorithms in terms of convergence speed, especially for convex problems. Many existing data-driven optimization methods are based on parameterizing the update step and learning the optimal parameters (typically scalars) from the available data. We propose a novel functional parameterization approach for learned convex optimization solvers based on the classical mirror descent (MD) algorithm. Specifically, we seek to learn the optimal Bregman distance in MD by modeling the underlying convex function using an input-convex neural network (ICNN). The parameters of the ICNN are learned by minimizing the target objective function evaluated at the MD iterate after a predetermined number of iterations. The inverse of the mirror map is modeled approximately using another neural network, as the exact inverse is intractable to compute. We derive convergence rate bounds for the proposed learned mirror descent approach with an approximate inverse mirror map and perform extensive numerical evaluation on various convex problems such as image inpainting, denoising, and learning a two-class support vector machine classifier and a multiclass linear classifier on fixed features.
  Citation: SIAM Journal on Mathematics of Data Science
  PubDate: 2023-06-26T07:00:00Z
  DOI: 10.1137/22M1508613
  Issue No: Vol. 5, No. 2 (2023)