Uniform Convergence of Lipschitz Functions with Dependent Gaussian Samples
In many practical learning problems, training samples are not i.i.d., and there is an intrinsic dependency among samples. Therefore, theoretical study of learning with dependent data has recently gained attention. In this paper, we provide a uniform convergence bound for the class of Lipschitz functions with bounded values at zero, under the assumption that the data samples are scalar and have a possibly dependent joint Gaussian distribution. Since other than Lipschitzness, there is no heavy assumption such as convexity or boundedness on the function class, the results are applicable for many practical models including neural networks. We showcase the strength and applicability of our theorems by numerical simulation and real-data analysis.
Code (1)
Similar Papers 제목 키워드 기반
Uniform Convergence with Square-Root Lipschitz Loss
We establish generic uniform convergence guarantees for Gaussian data in terms of the Rademacher complexity of the hypothesis class and the Lipschitz constant of the square root of the scalar loss function. We show how t…
regressionRetrievalUniform Convergence of Deep Neural Networks with Lipschitz Continuous Activation Functions and Variable Widths
We consider deep neural networks with a Lipschitz continuous activation function and with weight matrices of variable widths. We establish a uniform convergence analysis framework in which sufficient conditions on weight…
Beyond Uniform Lipschitz Condition in Differentially Private Optimization
Most prior results on differentially private stochastic gradient descent (DP-SGD) are derived under the simplistic assumption of uniform Lipschitzness, i.e., the per-sample gradients are uniformly bounded. We generalize …
BenchmarkingregressionUniform Convergence Rates for Lipschitz Learning on Graphs
Lipschitz learning is a graph-based semi-supervised learning method where one extends labels from a labeled to an unlabeled data set by solving the infinity Laplace equation on a weighted graph. In this work we prove uni…
Optimal Sample Complexity of Subgradient Descent for Amplitude Flow via Non-Lipschitz Matrix Concentration
We consider the problem of recovering a real-valued $n$-dimensional signal from $m$ phaseless, linear measurements and analyze the amplitude-based non-smooth least squares objective. We establish local convergence of sub…