Dominik Stöger
Dominik Stöger has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Felix Krahmer
Department of Mathematics, Technical University of Munich, Garching, Germany
2 shared publications - Filippo Cagnetti
Department of Mathematics, University of Sussex, Brighton, UK
2 shared publications - Matteo Perugini
Department of Mathematics, University of Sussex, Brighton, UK
2 shared publications - Peter Jung
Faculty of Electrical Engineering and Computer Science, Technical University of Berlin, Berlin, Germany
2 shared publications Anna Ma
Department of Mathematics, University of California Irvine, Irvine, CA 92697 USA
1 shared publication- Anna Ma
Department of Mathematics, University of California, Irvine, CA 92697 USA
1 shared publication
Latest Publications
- Open Access
Near-optimal estimates for the $\ell^p$-Lipschitz constants of deep random ReLU neural networks
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}$.Open AccessNear-optimal estimates for the $\ell^p$-Lipschitz constants of deep random ReLU neural networks
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}$. - 26 March 2025
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 14 (2)
Upper and lower bounds for the Lipschitz constant of random neural networks
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.
- 26 March 2025
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 14 (2)
Upper and lower bounds for the Lipschitz constant of random neural networks
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
- 15 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2991-3037
Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing
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.
- 15 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2991-3037
Top Cited PapersImplicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing
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.
- 20 October 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 44 (4) , 1566-1588
Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
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.
- 20 October 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 44 (4) , 1566-1588
Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
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.
- 6 September 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Mathematics of Data Science
- Vol. 5 (3) , 774-799
Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing
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.
- 6 September 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Mathematics of Data Science
- Vol. 5 (3) , 774-799
Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing
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
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.
Open AccessRobust recovery of low-rank matrices and low-tubal-rank tensors from noisy sketches
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.
- 22 October 2022
- Published by Springer Nature
- p. 37-75
Proof Methods for Robust Low-Rank Matrix Recovery
- 22 October 2022
- Published by Springer Nature
- p. 37-75
Proof Methods for Robust Low-Rank Matrix Recovery
- Open Access
- 4 August 2020
- Published by Springer Nature in Calculus of Variations and Partial Differential Equations
- Vol. 59 (4) , 1-53
Rigidity for perimeter inequality under spherical symmetrisation
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.
- 4 August 2020
- Published by Springer Nature in Calculus of Variations and Partial Differential Equations
- Vol. 59 (4) , 1-53
Open AccessRigidity for perimeter inequality under spherical symmetrisation
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
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.
Open AccessRigidity for perimeter inequality under spherical symmetrisation
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.
- 30 April 2019
- Published by Springer Nature in Advances in Computational Mathematics
- Vol. 45 (3) , 1711-1728
Sparse power factorization: balancing peakiness and sample complexity
- 30 April 2019
- Published by Springer Nature in Advances in Computational Mathematics
- Vol. 45 (3) , 1711-1728
Sparse power factorization: balancing peakiness and sample complexity