Using proof techniques involving @math covering numbers, we show generalisation error bounds for deep learning with two main improvements over the state of the art. First, our bounds have no explicit dependence on the number of classes except for logarithmic factors. This holds even when formulating the bounds in terms of the @math -norm of the weight matrices, while previous bounds exhibit at least a square-root dependence on the number of classes in this case. Second, we adapt the Rademacher analysis of DNNs to incorporate weight sharing---a task of fundamental theoretical importance which was previously attempted only under very restrictive assumptions. In our results, each convolutional filter contributes only once to the bound, regardless of how many times it is applied. Finally we provide a few further technical improvements, including improving the width dependence from before to after pooling. We also examine our bound's behaviour on artificial data.
where @math is the maximum width of the network, and Here @math denotes the spectral norm, and for any matrix @math , @math . Around the same time as the above result appeared, the authors in @cite_24 used a PAC Bayesian approach to prove an analogous result with @math replaced by the quantity below Note that the result using formula can also be derived from expressing in terms of @math norms and using Jensen's inequality :
@cite_24
2950958145 2077306951 2082401067 2071020383
We consider the problem of selecting the best subset of exactly @math columns from an @math matrix @math . We present and analyze a novel two-stage algorithm that runs in @math time and returns as output an @math matrix @math consisting of exactly @math columns of @math . In the first (randomized) stage, the algorithm randomly selects @math columns according to a judiciously-chosen probability distribution that depends on information in the top- @math right singular subspace of @math . In the second (deterministic) stage, the algorithm applies a deterministic column-selection procedure to select and return exactly @math columns from the set of columns selected in the first stage. Let @math be the @math matrix containing those @math columns, let @math denote the projection matrix onto the span of those columns, and let @math denote the best rank- @math approximation to the matrix @math . Then, we prove that, with probability at least 0.8, @math This Frobenius norm bound is only a factor of @math worse than the best previously existing existential result and is roughly @math better than the best previous algorithmic result for the Frobenius norm version of this Column Subset Selection Problem (CSSP). We also prove that, with probability at least 0.8, @math This spectral norm bound is not directly comparable to the best previously existing bounds for the spectral norm version of this CSSP. Our bound depends on @math , whereas previous results depend on @math ; if these two quantities are comparable, then our bound is asymptotically worse by a @math factor. We consider the problem of estimating an unknown signal @math from noisy linear observations @math . In many practical instances, @math has a certain structure that can be captured by a structure inducing convex function @math . For example, @math norm can be used to encourage a sparse solution. To estimate @math with the aid of @math , we consider the well-known LASSO method and provide sharp characterization of its performance. We assume the entries of the measurement matrix @math and the noise vector @math have zero-mean normal distributions with variances @math and @math respectively. For the LASSO estimator @math , we attempt to calculate the Normalized Square Error (NSE) defined as @math as a function of the noise level @math , the number of observations @math and the structure of the signal. We show that, the structure of the signal @math and choice of the function @math enter the error formulae through the summary parameters @math and @math , which are defined as the Gaussian squared-distances to the subdifferential cone and to the @math -scaled subdifferential, respectively. The first LASSO estimator assumes a-priori knowledge of @math and is given by @math . We prove that its worst case NSE is achieved when @math and concentrates around @math . Secondly, we consider @math , for some @math . This time the NSE formula depends on the choice of @math and is given by @math . We then establish a mapping between this and the third estimator @math . Finally, for a number of important structured signal classes, we translate our abstract formulae to closed-form upper bounds on the NSE. Let B i be deterministic real symmetric m × m matrices, and ξ i be independent random scalars with zero mean and “of order of one” (e.g., @math ). We are interested to know under what conditions “typical norm” of the random matrix @math is of order of 1. An evident necessary condition is @math , which, essentially, translates to @math ; a natural conjecture is that the latter condition is sufficient as well. In the paper, we prove a relaxed version of this conjecture, specifically, that under the above condition the typical norm of S N is @math : @math for all Ω > 0 We outline some applications of this result, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints @math , where F is quadratic in X = (X 1,... ,X k ). We show that when F is convex in every one of X j , a natural semidefinite relaxation of the problem is tight within a factor slowly growing with the size m of the matrices @math . We consider the following norm ∥ƒ for Boolean functions ƒ: 0, 1 n × 0, 1 n → 0, 1 : ∥ƒ|| = max ¦M(ƒ∗)v¦, v ϵ R2n, ¦v¦ = 1 . Here, M(ƒ∗) denotes the 2n × 2n-matrix obtained by setting M(ƒ∗)x,y=1 if ƒ(x,y)=1−1 if ƒ(x,y)=0. Further, we refer to the usual product of real matrices and vectors and denote by ¦v¦ the Euclidean norm of real vectors v. In this paper it will be shown by geometric arguments that for each function ƒ: 0,1 n × 0,1 n → 0,1 the following is true. - The length of each probabilistic communication protocol which computes ƒ with error bounded by 12 − 1s, s ϵ N, can be estimated from below by 14(n − log2∥ƒ||−log2 √s−2). - The number of edges of any threshold circuit of depth two computing ƒ cannot be smaller than 2n−1‖ƒ‖ These results yield better lower bounds on probabilistic communication complexity as well as on the complexity of threshold circuits of depth two. Further, characterizing ∥ƒ∥ by the eigenvalues of M(ƒ∗) we obtain a method to construct iteratively functions which are hard to compute in the above models. This implies lower bounds for decision problems that previous probabilistic techniques from Yao (1983), Halstenberg and Reischuk (1988) and (1987) cannot be applied to.