arvix_November2
sdiaconu · 2025
Read arvix_November2 by sdiaconu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00942.txt.
Introduction
Simona Diaconu studies a central quantity in the theory of Gaussian random processes, Talagrand's gamma two functional. For a centered Gaussian process, the expected size of its largest value is comparable to this functional, which depends only on the geometry of the index space under a natural distance.
The functional is defined as an infimum over admissible sequences, chains of ever finer approximations to the space. In practice it is mostly used to compare one process with another. Diaconu instead constructs admissible sequences that come close to optimal, treating the functional as an object worth computing in its own right. The aim is a more direct route to understanding expected suprema of Gaussian processes.
Catalog record
| CREATOR | sdiaconu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00942
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
arvix_November2 sdiaconu Abstract Suprema of random processes appear naturally in a plethora of disciplines, and Talagrand’s majorizing theorem yields a geometric interpretation for them: for a centered Gaussian random process ( X t ) t ∈ T , (X_{t})_{t\in T}, 𝔼 [ sup t ∈ T X t ] \mathbb{E}[\sup_{t\in T}{X_{t}}] is comparable to the γ 2 \gamma_{2} -functional of T , T, a quantity that depends solely on the space ( T , d ) , (T,d), where d d denotes the pseudometric d ( u , v ) = 𝔼 [ ( X u − X v ) 2 ] . d(u,v)=\sqrt{\mathbb{E}[(X_{u}-X_{v})^{2}]}. Despite the explicit definition of this functional, an infimum over admissible sequences, this tool tends to be used exclusively as a means to bound the expectation of the supremum of a random process by that of another. This work considers the γ 2 \gamma_{2} -functional as a proxy for the quantity of interest by constructing admissible sequences that are close to being optimal, and aims to provide a promising avenue towards understanding expectations of suprema of Gaussian random processes. Admissible Sequences for Talagrand’s \gamma_{2} -functional Simona Diaconu 1 1 1 Courant Institute, New York University, [email protected] 1 Introduction For a pseudometric space (T,d), Talagrand’s \gamma_{2} -functional is defined as \gamma_{2}(T)=\inf_{\mathcal{A}}{\sup_{t\in T}{\sum_{h\geq 0}{2^{h/2}\cdot d(t,\mathcal{A}_{h})}}}, (1.1) where the infimum is taken over admissible sequences 2 2 2 Tropp [ 4 ] assumes the sequence is nested, i.e., \mathcal{A}_{h}\subset\mathcal{A}_{h+1}. Both definitions yield comparable functionals by noting that \sum_{0\leq h\leq H}{2^{2^{h}}}\leq 2^{2^{H+1}}. for T, i.e., \mathcal{A}=(\mathcal{A}_{h})_{h\geq 0}\subset 2^{T},\hskip 8.5359pt|\mathcal{A}_{0}|=1,\hskip 8.5359pt|\mathcal{A}_{h}|\leq 2^{2^{h}}\hskip 14.22636pt(h\in\mathbb{N}). A remarkable feature of this quantity is the celebrated Talagrand’s majorizing measure theorem, which states that for any centered Gaussian process (X_{t})_{t\in T} and the canonical pseudodistance on T given by d(t,s)=||X_{t}-X_{s}||_{L^{2}}=\sqrt{\mathbb{E}[(X_{t}-X_{s})^{2}]}, the following holds 3 3 3 Measurability issues can arise as \sup_{t\in T}{X_{t}} is not a priori a random variable: by convention, \mathbb{E}[\sup_{t\in T}{X_{t}}]:=\sup_{S\subset T,|S|<\infty}{\mathbb{E}[\max_{t\in S}{X_{t}}]}. See subchapter 10.1.4 in Tropp [ 4 ] for alternatives. , \mathbb{E}[\sup_{t\in T}{X_{t}}]=\Theta(\gamma_{2}(T)). (1.2) In other words, there exist universal constants c,C>0 such that c\cdot\gamma_{2}(T)\leq\mathbb{E}[\sup_{t\in T}{X_{t}}]\leq C\cdot\gamma_{2}(T). This result has far-reaching consequences: suprema of random processes appear in sundry disciplines, and their expectation is oftentimes vital for understanding the suprema themselves due to their Lipschitz nature and a concentration of measure phenomenon (see, for instance, De et al [ 1 ] , a recent work containing sparsity results via Talagrand’s majorizing theorem alongside their applications to agnostic learning and tolerant property testing). This paper is concerned with (and motivated by) random matrices, specifically symmetric Gaussian matrices whose upper-diagonal submatrices have independent entries: that is, Z=(b_{ij}g_{ij})_{1\leq i,j\leq d}\in\mathbb{R}^{d\times d} (1.3) with b_{ij}\geq 0,b_{ij}=b_{ji},g_{ij}=g_{ji}, (g_{ij})_{1\leq i\leq j\leq d} i.i.d., and g_{11}\overset{d}{=}N(0,1). It is known that the operator norm of such random matrices is comparable in expectation to the maximal length of their columns (or equivalently rows). That is, \mathbb{E}[||Z||]=\Theta(\mathbb{E}[\max_{1\leq i\leq d}{||Ze_{i}||}]), (1.4) a result by Latala et al. [ 2 ] from 2018. The lower bound is immediate from ||M||=\sup_{u\in\mathbb{S}^{d-1}}{||Mu||}\geq\max_{1\leq i\leq d}{||Me_{i}||}, an inequality that holds for all symmetric matrices M\in\mathbb{R}^{d\times d}, whereas optimal upper bounds require careful handling of what is sometimes called the variance pattern of Z, (b^{2}_{ij})_{1\leq i,j\leq d}. In particular, the upper bound is far from trivial: as van Handel [ 5 ] shows (see Theorem 1.2 therein), the right-hand side is comparable to a quantity that can be succinctly described in terms of the variance pattern, \mathbb{E}[\max_{1\leq i\leq d}{||Ze_{i}||}]=\Theta(\max_{1\leq i\leq d}{\sqrt{\sum_{1\leq j\leq d}{b^{2}_{ij}}}}+\max_{1\leq i\leq d}{(\sqrt{\log{(i+1)}}b_{\sigma(i)(1)})}), (1.5) where b_{i(1)}=\max_{1\leq j\leq d}{b_{ij}}, and \sigma is a permutation of \{1,2,\hskip 1.42271pt...\hskip 1.42271pt,d\} with b_{\sigma(1)(1)}\geq b_{\sigma(2)(1)}\geq...\geq b_{\sigma(d)(1)}. However, most methods yield bounds some logarithmic factor away from the right size: for instance, a consequence of theorem 1 in Oliveira [ 3 ] is that \mathbb{E}[||Z||]\leq(\sqrt{2\log{(2d)}}+\frac{\sqrt{2\pi}}{2})\cdot\max_{1\leq i\leq d}{\sqrt{\sum_{1\leq j\leq d}{b^{2}_{ij}}}} (his result is more general than this as the model considered is Z=\sum_{1\leq i\leq n}{\epsilon_{i}A_{i}} for deterministic symmetric matrices (A_{i})_{1\leq i\leq n}\subset\mathbb{R}^{d\times d}, (\epsilon_{i})_{1\leq i\leq n} i.i.d. with \epsilon_{1}\overset{d}{=}N(0,1) or \mathbb{P}(\epsilon_{1}=1)=\mathbb{P}(\epsilon_{1}=-1)=\frac{1}{2}: the bounds obtained are polynomial in ||\sum_{1\leq i\leq n}{A_{i}^{2}}|| and \log{d} ), while theorem 1.3 in van Handel [ 5 ] gives that \mathbb{E}[||Z||]=O(\sqrt{\log{\log{d}}}\cdot\mathbb{E}[\max_{1\leq i\leq d}{||Ze_{i}||}]). Regarding proof techniques, Oliveira [ 3 ] uses a matrix extension of \mathbb{P}(|X|\geq a)\leq e^{-a^{2}}\cdot\mathbb{E}[X^{2}] for a>0, sometimes called Bernstein’s trick, \mathbb{P}(||X||\geq a)\leq e^{-a^{2}}\cdot\mathbb{E}[tr(e^{X^{2}})], whereas van Handel [ 5 ] employs trace computations. The latter method plays a crucial role in the proof of ( 1.4 ) by Latala et al. [ 2 ] : both results rely on block decompositions of the matrix of interest and careful combinatorics that allow fine bounds for the trace expectations of their powers. The dimensions of the blocks grow at the rate of the maximal sizes of sets forming admissible sequences, i.e., 2^{2^{h}},h\in\mathbb{N}: this scale, not surprising in light of Talagrand’s majorizing measure theorem, is, up to an extent, another of its merits. This paper aims to investigate the \gamma_{2} -functional by finding admissible sequences whose corresponding contributions to the infimum underlying \gamma_{2} are small, i.e., close to optimal. The reason for this is twofold: there seem to be no works that exploit ( 1.2 ) via definition ( 1.1 ), and the thrust of the majorizing theorem appears to be not fully taken advantage of. The trace method has far reaching applications and its merits can be hardly overestimated: nonetheless, one of its shortcomings is that it generally does not yield information about eigenvectors. The majorizing theorem can yield delocalization properties of the leading eigenvectors since for Gaussian random matrices Z, a common choice for the random process X, yielding the operator norm ||Z||, is X_{t}=t^{T}Zt,t\in\mathbb{S}^{d-1}, and thus subsets T of the unit sphere with \gamma_{2}(T) small relatively to \gamma_{2}(\mathbb{S}^{d-1}) can render a form of localization (or lack thereof) for the leading eigenvector. When it comes to the \gamma_{2} -functional, a difficulty in bounding it lies within the square roots underpinning it: for X_{t}=t^{T}Zt\hskip 28.45274pt(t\in\mathbb{R}^{d}), and Z given by ( 1.3 ), d(x,y)=\sqrt{\mathbb{E}[(X_{x}-X_{y})^{2}]}=\sqrt{\sum_{1\leq i\leq d}{b_{ii}^{2}(x_{i}^{2}-y^{2}_{i})^{2}}+4\sum_{1\leq i<j\leq d}{b_{ij}^{2}(x_{i}x_{j}-y_{i}y_{j})^{2}}}, (1.6) and the easier-to-handle quantity \sum_{h\geq 0}{2^{h}\cdot(d(t,\mathcal{A}_{h}))^{2}} solely yields a lower bound for \gamma_{2} via the inequality \sqrt{\sum_{1\leq i\leq r}{a_{i}}}\leq\sum_{1\leq i\leq r}{\sqrt{a_{i}}} for r\in\mathbb{N},(a_{i})_{1\leq i\leq r}\subset[0,\infty), \inf_{\mathcal{A}}{\sup_{t\in T}{\sum_{h\geq 0}{2^{h}\cdot(d(t,\mathcal{A}_{h}))^{2}}}}\leq(\gamma_{2}(T))^{2}. (1.7) Before proceeding with this series, a few remarks on ||Z|| and \sup_{t\in T}{X_{t}} are in order. Since solely an upper bound for \mathbb{E}[||Z||] is needed, this can be taken as O(\gamma_{2}(T)): theorem 8.5.3 in Vershynin [ 6 ] implies that \mathbb{E}[\sup_{t\in T}{|X_{t}-X_{t_{0}}|}]=O(\gamma_{2}(T)) for any t_{0}\in T, whereby \mathbb{E}[||Z||]=\mathbb{E}[\sup_{t\in T}{|X_{t}|}]=O(\gamma_{2}(T)+\mathbb{E}[|X_{t_{0}}|]) and letting t_{0}=(1,0,\hskip 1.42271pt...\hskip 1.42271pt,0)\in\mathbb{R}^{d} produces the desired result as X_{t_{0}}\overset{d}{=}N(0,b^{2}_{11}). Return now to ( 1.7 ): the main contribution of this work can be summarized as follows. Theorem 1 . There exists an admissible sequence (\mathcal{A}_{h})_{h\geq 0} for T=\mathbb{S}^{d-1} with \sup_{t\in T}{\sum_{h\geq 0}{2^{h}\cdot(d(t,\mathcal{A}_{h}))^{2}}}\leq 121,931,520\cdot C^{2}, (1.8) where C=\max{(\max_{1\leq i\leq d}{\sqrt{\sum_{1\leq j\leq d}{b^{2}_{ij}}}},\max_{1\leq i\leq d}{(\sqrt{\log_{2}{(i+1)}}b_{\sigma(i)(1)})})} (1.9) for \sigma as defined immediately below ( 1.5 ). A few remarks on Theorem 1 are in order (the description of (\mathcal{A}_{h})_{h\geq 0} requires additional notation, and this is completed in section 3 ). First, once diagonal matrices, i.e., b_{ij}=0 (i\neq j), are taken care of, it is perfectly natural to attempt to generalize the rationale employed for them. A somewhat subtle advantage in this special situation is that the signs of