DSDominik Stöger

Dominik Stöger

*This is an algorithmically generated author record based on publicly available information.

Dominik Stöger has a total of 23 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Near-optimal estimates for the $\ell^p$-Lipschitz constants of deep random ReLU neural networks

    by Sjoerd Dirksen, Patrick Finke, Paul Geuchen, Dominik Stöger, Felix Voigtlaender

    This paper studies the $\ell^p$-Lipschitz constants of ReLU neural networks $Φ: \mathbb{R}^d \to \mathbb{R}$ with random parameters for $p \in [1,\infty]$. The distribution of the weights follows a variant of the He initialization and the biases are drawn from symmetric distributions. We derive high probability upper and lower bounds for wide networks that differ at most by a factor that is logarithmic in the network's width and linear in its depth. In the special case of shallow networks, we obtain matching bounds. Remarkably, the behavior of the $\ell^p$-Lipschitz constant varies significantly between the regimes $ p \in [1,2) $ and $ p \in [2,\infty] $. For $p \in [2,\infty]$, the $\ell^p$-Lipschitz constant behaves similarly to $\Vert g\Vert_{p'}$, where $g \in \mathbb{R}^d$ is a $d$-dimensional standard Gaussian vector and $1/p + 1/p' = 1$. In contrast, for $p \in [1,2)$, the $\ell^p$-Lipschitz constant aligns more closely to $\Vert g \Vert_{2}$.

  • Upper and lower bounds for the Lipschitz constant of random neural networks

    by Paul Geuchen, Dominik Stöger, Thomas Telaar, Felix Voigtlaender

    Empirical studies have widely demonstrated that neural networks are highly sensitive to small, adversarial perturbations of the input. The worst-case robustness against these so-called adversarial examples can be quantified by the Lipschitz constant of the neural network. In this paper, we study upper and lower bounds for the Lipschitz constant of random ReLU neural networks. Specifically, we assume that the weights and biases follow a generalization of the He initialization, where general symmetric distributions for the biases are permitted. For deep networks of fixed depth and sufficiently large width, our established upper bound is larger than the lower bound by a factor that is logarithmic in the width. In contrast, for shallow neural networks we characterize the Lipschitz constant up to an absolute numerical constant that is independent of all parameters.


  • Top Cited Papers

    Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

    by Mahdi Soltanolkotabi, Dominik Stöger, Changzhi Xie

    Recently, there has been significant progress in understanding the convergence and generalization properties of gradient-based methods for training overparameterized learning models. However, many aspects including the role of small random initialization and how the various parameters of the model are coupled during gradient-based updates to facilitate good generalization remain largely mysterious. A series of recent papers have begun to study this role for non-convex formulations of symmetric Positive Semi-Definite (PSD) matrix sensing problems which involve reconstructing a low-rank PSD matrix from a few linear measurements. The underlying symmetry/PSDness is crucial to existing convergence and generalization guarantees for this problem. In this paper, we study a general overparameterized low-rank matrix sensing problem where one wishes to reconstruct an asymmetric rectangular low-rank matrix from a few linear measurements. We prove that an overparameterized model trained via factorized gradient descent converges to the low-rank matrix generating the measurements. We show that in this setting, factorized gradient descent enjoys two implicit properties: (1) coupling of the trajectory of gradient descent where the factors are coupled in various ways throughout the gradient update trajectory and (2) an algorithmic regularization property where the iterates show a propensity towards low-rank models despite the overparameterized nature of the factorized model. These two implicit properties in turn allow us to show that the gradient descent trajectory from small random initialization moves towards solutions that are both globally optimal and generalize well.


  • Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches

    by Anna Ma, Dominik Stöger, Yizhe Zhu

    A common approach for compressing large-scale data is through matrix sketching. In this work, we consider the problem of recovering low-rank matrices from two noisy linear sketches using the double sketching scheme discussed in Fazel et al. [ Compressed sensing and robust recovery of low rank matrices, in Proceedings of the 42nd IEEE Asilomar Conference on Signals, Systems and Computers, 2008, pp. 1043–1047], which is based on an approach by Woolfe et al. [ Appl. Comput. Harmon. Anal., 25 (2008), pp. 335–366]. Using tools from nonasymptotic random matrix theory, we provide the first theoretical guarantees characterizing the error between the output of the double sketch algorithm and the ground truth low-rank matrix. We apply our result to the problems of low-rank matrix approximation and low-tubal-rank tensor recovery.


  • Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing

    by Kiryung Lee, Dominik Stöger

    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 [Formula: see text]-accuracy in [Formula: see text] iterations using only a near-optimal number of samples, where we assume the measurement matrices to be i.i.d. Gaussian and where by [Formula: see text] 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.


  • Open Access

    Robust recovery of low-rank matrices and low-tubal-rank tensors from noisy sketches

    by Anna Ma, Dominik Stöger, Yizhe Zhu

    A common approach for compressing large-scale data is through matrix sketching. In this work, we consider the problem of recovering low-rank matrices from two noisy linear sketches using the double sketching scheme discussed in Fazel et al. (2008), which is based on an approach by Woolfe et al. (2008). Using tools from non-asymptotic random matrix theory, we provide the first theoretical guarantees characterizing the error between the output of the double sketch algorithm and the ground truth low-rank matrix. We apply our result to the problems of low-rank matrix approximation and low-tubal-rank tensor recovery.

  • Proof Methods for Robust Low-Rank Matrix Recovery

    by Tim Fuchs, David Gross, Peter Jung, Felix Krahmer, Richard Kueng, Dominik Stöger


  • Open Access

    Rigidity for perimeter inequality under spherical symmetrisation

    by F. Cagnetti, M. Perugini, D. Stöger

    Necessary and sufficient conditions for rigidity of the perimeter inequality under spherical symmetrisation are given. That is, a characterisation for the uniqueness (up to orthogonal transformations) of the extremals is provided. This is obtained through a careful analysis of the equality cases, and studying fine properties of the circular symmetrisation, which was firstly introduced by Pólya in 1950.


  • Open Access

    Rigidity for perimeter inequality under spherical symmetrisation

    by Filippo Cagnetti, Matteo Perugini, Dominik Stöger

    Necessary and sufficient conditions for rigidity of the perimeter inequality under spherical symmetrisation are given. That is, a characterisation for the uniqueness (up to orthogonal transformations) of the extremals is provided. This is obtained through a careful analysis of the equality cases, and studying fine properties of the circular symmetrisation, which was firstly introduced by P\'olya in 1950.