On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses

• URL: http://arxiv.org/abs/2503.10580v1
• Date: Thu, 13 Mar 2025 17:31:51 GMT
• Title: On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses
• Authors: Ishaq Aden-Ali,
• Abstract summary: We prove an upper bound on the expected $ell_p$ injective norm of sums of subgaussian random tensors.<n>Our proof is simple and does not rely on any explicit geometric or chaining arguments.
• Score: 2.918940961856197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove an upper bound on the expected $\ell_p$ injective norm of sums of subgaussian random tensors. Our proof is simple and does not rely on any explicit geometric or chaining arguments. Instead, it follows from a simple application of the PAC-Bayesian lemma, a tool that has proven effective at controlling the suprema of certain ``smooth'' empirical processes in recent years. Our bound strictly improves a very recent result of Bandeira, Gopi, Jiang, Lucca, and Rothvoss. In the Euclidean case ($p=2$), our bound sharpens a result of Lata{\l}a that was central to proving his estimates on the moments of Gaussian chaoses. As a consequence, we obtain an elementary proof of this fundamental result.

Related papers

• Better-than-KL PAC-Bayes Bounds [23.87003743389573]
  We show that it is possible to achieve a strictly tighter bound with a novel and better-than-KL divergence. Our result is first-of-its-kind in that existing PAC-Bayes bounds with non-KL divergences are not known to be strictly better than KL.
  arXiv  Detail & Related papers  (2024-02-14T14:33:39Z)
• High Probability Guarantees for Random Reshuffling [4.794366598086316]
  We consider the gradient method with random reshuffling ($mathsfRR$) for tackling optimisation problems. We provide first-order complexity guarantees for the method. We derive that $mathsfp$-$mathsfRR$provably escapes strict points and a high tail.
  arXiv  Detail & Related papers  (2023-11-20T15:17:20Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
  arXiv  Detail & Related papers  (2023-10-27T09:16:58Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  This nearly establishes a conjecture ofciteSaundersonCPW12, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
  arXiv  Detail & Related papers  (2022-12-21T17:48:01Z)
• A note on the smallest eigenvalue of the empirical covariance of causal Gaussian processes [1.223779595809275]
  We present a proof for bounding the smallest eigenvalue of the empirical covariance in a causal Gaussian process. We establish a one-sided tail inequality for Gaussian quadratic forms using a causal decomposition.
  arXiv  Detail & Related papers  (2022-12-19T14:44:37Z)
• Lassoed Tree Boosting [53.56229983630983]
  We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation. Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
  arXiv  Detail & Related papers  (2022-05-22T00:34:41Z)
• Tight Second-Order Certificates for Randomized Smoothing [106.06908242424481]
  We show that there also exists a universal curvature-like bound for Gaussian random smoothing. In addition to proving the correctness of this novel certificate, we show that SoS certificates are realizable and therefore tight.
  arXiv  Detail & Related papers  (2020-10-20T18:03:45Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)
• Robust $k$-means Clustering for Distributions with Two Moments [4.21934751979057]
  We consider the robust algorithms for the $k$-means clustering problem where a quantizer is constructed based on $N$ independent observations. Our main results are median of means based non-asymptotic excess distortion bounds that hold under the two bounded moments assumption in a general separable Hilbert space.
  arXiv  Detail & Related papers  (2020-02-06T16:36:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.