Source-linked AI summary
Wasserstein approximation of measures via orthogonal frames: statistical and computational complexities
Mateo Díaz, Nicolás García Trillos, Daniel López-Castaño, Congwei Yang
TL;DR
The paper studies how to select a distinguished orthogonal basis when dimension-reduction identifies only a subspace. It formulates basis selection as Wasserstein approximation on frame axes and proves near-parametric recovery rates for empirical minimizers and locally initialized SGD under stated assumptions.
Problem
Subspace-based dimension reduction does not identify a distinguished basis, motivating methods to select coordinates in which observations are sparsely represented.
Source: §1 · p. 2Method
The paper minimizes Wasserstein approximation error over measures supported on orthogonal-frame axes and analyzes empirical minimization and locally initialized online Riemannian SGD.
Source: §1 · pp. 2, 5Results
Both empirical minimization and locally initialized SGD achieve n^-1/2 dependence up to logarithmic factors; for balanced Gaussian mixtures, the SGD bound specializes to Õ(d/√n).
Source: §1 · pp. 4–5Takeaways & Limitations
A local coarsely Lipschitz bound on the empirical gradient lets the analysis handle its switching-related jumps despite population smoothness and empirical nonsmoothness.
Source: §1 · p. 4The SGD guarantee is local and assumes subexponential sample norms and local geodesic strong convexity with a Lipschitz population gradient.
Source: §1 · pp. 4–5
Abstract
from arXiv · showhide
Dimension-reduction methods such as PCA identify a subspace capturing most of the variation in the data, but not a distinguished basis within it. Selecting a basis in which the samples are sparsely represented is a recurring task in unsupervised learning, addressed by methods in factor analysis, dictionary learning, and subspace clustering. We pose this task as Wasserstein approximation of the data distribution by measures supported on the axes of an orthogonal frame, which, in turn, reduces to a nonsmooth optimization problem over the orthogonal group $\mathrm{O}(d)$. We show that, under mild assumptions, both empirical risk minimizers and a locally initialized stochastic gradient method recover the population-optimal frame at the near-parametric rate $\widetilde{O}_d(n^{-1/2})$, where $n$ is the sample size. The main difficulty is that, although the population objective is smooth, the empirical objective is not-this mismatch precludes standard covering arguments. We overcome this issue by replacing Lipschitz continuity of the empirical gradient with a coarsely Lipschitz bound, a tool that may be of independent interest. Numerical experiments support our theoretical findings.
1 Introduction
The paper selects an orthogonal frame by approximating a data distribution with measures supported on the frame’s axes, addressing the ambiguity left by methods that identify only a subspace. It analyzes empirical frame recovery and local stochastic gradient descent despite a nonsmooth empirical objective and a smooth population objective.
1 Introduction
- The frame criterion targets vectors concentrated near one coordinate axis, complementing factor-analysis and dictionary-learning methods that seek meaningful coordinates beyond a subspace.The Wasserstein cost measures transportation from the target distribution to a measure supported on the frame’s axes.Source: §1 · p. 2
- Minimizing over measures supported on a fixed frame reduces to an explicit nearest-axis projection, leaving a finite-dimensional optimization over O(d).The pushforward under the nearest-axis projection is optimal for that frame.Source: §1 · pp. 2–3
- The population objective is smooth under mild assumptions, but nearest-axis switches make the empirical objective piecewise smooth with gradient jumps.As the frame changes, a sample’s nearest axis can switch when two projection residuals are equal.Source: §1 · p. 3
- A local coarsely Lipschitz bound controls empirical-gradient jumps through the number and size of samples whose nearest axis switches.The switching contribution is small under a margin assumption, allowing pointwise concentration to extend beyond a net.Source: §1 · p. 4
- Under subexponential-tail, margin, and local strong-convexity assumptions, empirical minimizers attain a near-parametric n^-1/2 rate up to logarithmic factors.For Gaussian mixtures concentrated near a frame, the stated bound has dimension-dependent constants and specializes to Õ(d^7/n).Source: §1 · pp. 4–5
- Locally initialized online Riemannian SGD with fresh batches also attains n^-1/2 dependence up to logarithmic factors, matching the empirical minimizer’s rate.For balanced Gaussian mixtures, the bound specializes to Õ(d/√n); the guarantee is local.Source: §1 · p. 5
1.1 Related work
- The Wasserstein frame criterion complements Varimax, Quartimax, dictionary learning, and independent component analysis by selecting axes through transportation cost.The related methods use different models and identification principles, while dictionary learning shares the goal of sparse coordinates.Source: §1 · p. 2, §1.1 · p. 6
- The paper connects its loss to orthogonal dictionary learning and contrasts its Õ_d(n^-1/2) recovery rate with roughly O_d(n^-1/4) guarantees in related work.Unlike some prior local dictionary-recovery analyses, its SGD scheme does not assume a noiseless setting.Source: §1.1 · pp. 6–7
2 Preliminaries
This section sets up the measure and geometric notation used to formulate Wasserstein approximation and optimization over orthogonal frames.
2 Preliminaries
- Axes(U) denotes the collection of unoriented one-dimensional spans of the columns of an orthogonal matrix U.The text distinguishes Euclidean distance from geodesic distance on O(d).Source: §2 · p. 8
- The squared 2-Wasserstein distance is defined through couplings of probability measures, and a minimizing coupling is an optimal transport plan.The preliminaries also define pushforward measures under Borel maps.Source: §2 · p. 8
- The orthogonal group O(d) is treated as a Riemannian manifold with tangent spaces, a Frobenius-induced metric, geodesics, and an exponential map.The Riemannian gradient is obtained by projecting the Euclidean gradient onto the tangent space.Source: §2 · p. 8
- The appendix uses the Riemannian Clarke subdifferential for locally Lipschitz functions and states that local minimizers satisfy a first-order subdifferential condition.The condition is invariant to the choice of signed-permutation representative.Source: §2 · pp. 8–9
3 Assumptions
The assumptions combine moment bounds, local regularity and identifiability of the population objective, and control of samples near switching regions. The section also gives Gaussian-mixture settings where these conditions hold and describes their dimension dependence.
3 Assumptions
- The assumptions require bounded fourth moments and sub-exponential squared sample norms.The latter condition implies finite fourth moments.Source: §3 · p. 9
- The population objective must be locally geodesically strongly convex with a Lipschitz Riemannian gradient, while a sublevel-set condition confines near-optimal frames to signed-permutation copies of the local neighborhood.The objectives are invariant under signed column permutations, so the target frame is identified only up to those transformations.Source: §3 · p. 9
- A far-region switching-margin condition limits probability mass near directions where nearest-axis assignments can change, with the assumption ruling out excessive mass near roughly 45-degree directions.The paper controls switching by defining nearby and far-away direction regions around the frame's axes.Source: §3 · p. 10
- For equal-weight Gaussian signals along the axes of U⋆, with bounded component variances and noise variance at most b+/d, the population minimizers are U⋆ up to signed permutations.The proposition states this for sufficiently large dimension under its variance and noise conditions.Source: §3 · pp. 10–11
The remaining constants satisfy
- When τ scales as d^-1/2, the model gives m and L of order d^-1, K of order 1, and Cmar of order d^1/2; the general model is also covered for sufficiently small noise at fixed d.The constants are dimension-dependent in the stated scaling regime.Source: The remaining constants satisfy · p. 11
4 Main results
The main results establish high-probability recovery of the population-optimal frame by empirical minimization and locally initialized online Riemannian SGD. Their analyses address switching in the empirical objective and provide guarantees under local regularity and sample-tail assumptions.
4 Main results
- The empirical-minimizer and SGD errors are measured after optimally aligning signs and column order.The target frame is considered modulo signed permutations.Source: §4 · p. 11
Empirical risk minimization
- O(d^5/2 log n/√n) bounds the three empirical-minimizer error terms when n ≳ d(log n)^2 and the problem constants are dimension-uniform; for fixed d, the leading switching term is O(Cmar d^2 log n/√n).The theorem assumes moment, local regularity, sublevel-set, and switching conditions.Source: §4 · pp. 11–12
- The empirical-minimizer theorem gives an explicit three-term finite-sample bound, with no relation between d and n beyond its displayed thresholds.Its dimension dependence is specified through the terms A1, A2, and A3 when the constants are not dimension-uniform.Source: §4 · pp. 11–12
Online-stochastic Riemannian gradient descent for estimation
- Online Riemannian SGD uses fresh independent batches at each iteration and has a high-probability last-iterate guarantee for a locally initialized trajectory.Under the good-noise event, the iterates remain in the strongly convex ball while controlling terminal error.Source: §4 · p. 12
5 Analysis
The analysis handles a smooth population objective with a nonsmooth empirical counterpart by controlling sample switches, obtaining uniform empirical subgradient control, and localizing empirical minimizers. It also analyzes locally initialized, fresh-batch SGD through stochastic-gradient concentration, local contraction, and confinement to a strongly convex ball.
5.1.1 Geometry of switching regions
- At scale δ = n^-1/2, switching concentration controls how many samples can change their selected axis between nearby frames.Switches are confined to neighborhoods of signed pairwise bisector spheres; a predetermined stripe cover enables simultaneous control without a union bound over data-dependent switching sets.Source: §5.1.1 · pp. 13–14
5.1.2 Coarsely Lipschitz property and uniform convergence
- The switching-count bound yields a coarsely Lipschitz empirical subgradient bound, with an additive residual for switching samples.For nonswitching samples, the selected axis is unchanged and the contribution varies Lipschitzly; switching contributions are controlled by the switching count and sample-size bound.Source: §5.1.2 · p. 14
5.1.3 Localization of the empirical minimizer
- Uniform empirical subgradient control and deterministic sublevel containment localize every empirical minimizer to the aligned neighborhood, up to a signed permutation.At empirical minimizers, the selected subgradient vanishes; the neighborhood’s radius of empirical smoothness is sample-dependent and has no sample-independent positive lower bound.Source: §5.1.2 · pp. 14–15, §5.1.3 · p. 15
5.1.4 Proof of Theorem 10
- Theorem 10’s uniform bounds yield near-parametric frame recovery for every empirical minimizer under the stated assumptions.The proof combines empirical-minimizer localization, strong convexity, and uniform control of the population-gradient/subgradient discrepancy.Source: §5.1.4 · p. 15
5.2 Stochastic gradient descent
- The SGD analysis assumes an aligned initialization inside a geodesic ball contained in the strongly convex component.Equivariance makes the induced frame iteration independent of the initial signed-permutation representative.Source: §5.2 · pp. 15–16
5.2.1 Dimension-free stochastic-gradient concentration
- Fresh independent batches make each stochastic gradient conditionally unbiased for the population gradient within the aligned neighborhood.The analysis gives dimension-free, uniform-in-time concentration for the stochastic-gradient error using Hilbert-space Bernstein bounds.Source: §5.2.1 · p. 16
5.2.2 Sharp local contraction and invariant-ball control
- Local contraction separates population progress from stochastic error, and a uniform error threshold keeps the entire trajectory inside the strongly convex ball.The one-step recursion combines contraction by qη with an additive stochastic-gradient error; the invariant-ball argument then controls confinement and terminal error on the same event.Source: §5.2.2 · pp. 16–17, §5.2.3 · p. 17
5.2.3 Proof of Theorem 11
- The fresh-batch SGD theorem uses a logarithmic iteration count and batch allocation to obtain its stated finite-moment and sub-exponential guarantees.The proof chooses the same constant for the basin condition and terminal bound in the sub-exponential regime.Source: §5.2.3 · p. 17
6 Numerical Experiments
The experiments compare frame recovery across sample sizes, dimensions, distributions, noise levels, and competing methods. They report empirical convergence patterns and benchmark differences, while noting that the plotted protocols do not certify theoretical rates or hardware-independent runtime guarantees.
6 Numerical Experiments
- The experiments use stylized examples, while the real-data illustration is not verified to satisfy the assumptions.The real-data illustration is in Appendix F; the method is presented as the s = 1 case of fixed-sparsity orthogonal dictionary learning, solved here by Riemannian gradient descent.Source: §6 · p. 17
6.1 Statistical convergence rates
- Across tested sample sizes, relative frame error curves decrease parallel to the 1/√n reference line, while vertical offsets grow with dimension.The experiments support the empirical slope pattern but do not identify worst-case dimension dependence or isolate distributional constants; the Student-t distribution violates Assumption 3.Source: Figure 2 · p. 18, §6.1 · p. 18
6.2 Computational convergence
- With fixed-sample steepest descent, error decays rapidly before reaching a floor that decreases with n and rises with d.For the misspecified double-exponential and Student-t distributions, convergence deteriorates at d ≥ 75; the protocol does not verify the predicted online-SGD squared-error rate.Source: §6.2 · pp. 18–19, Figure 3 · p. 19
6.3 Comparison with competing methods
- Both orthogonal K-SVD implementations have substantially smaller squared frame error than RSC and PCA+Varimax across the plotted dimensions.Riemannian GD and alternating minimization nearly overlap, with a largest per-trial absolute difference of approximately 4.4 × 10^-7; PCA+Varimax errors remain of order one, while RSC error grows with dimension.Source: §6.3 · pp. 19, 21, Figure 4 · p. 20
- At τ = 0.30, orthogonal K-SVD’s squared error rises to approximately 2 × 10^-3, while RSC deteriorates markedly at τ = 0.20 and 0.30.The Riemannian GD and alternating-minimization implementations track closely across the noise sweep; PCA+Varimax remains at errors of order one.Source: Figure 4 · p. 20, §6.3 · p. 21
- At d = 100, mean runtimes are approximately 0.028 seconds for alternating minimization and 6.55 seconds for Riemannian GD.These are implementation- and hardware-specific measurements, not complexity guarantees; alternating minimization uses closed-form hard-thresholding and an SVD-based Procrustes update.Source: §6.3 · p. 21
AI disclaimer
The authors describe the manuscript’s drafting and review process, including later AI assistance for technical review and other tasks.
AI disclaimer
- The initial draft predates summer 2026 and was developed without AI assistance.It already contained the reported results, including the e O_d(n^-1/2) rates for Theorems 10 and 11.Source: AI disclaimer · p. 21
- After ChatGPT 5.6 Sol’s release, the authors used it to adversarially review the manuscript for technical gaps.They report that the main theoretical change was refining a Theorem 10 covering argument, improving the dimensional dependency from exponential to polynomial.Source: AI disclaimer · p. 21
- The authors also used ChatGPT for coding assistance, writing polish, and literature searches, and take responsibility for the paper’s content.Source: AI disclaimer · p. 21
A Auxiliary results common to the main theorems
The auxiliary results connect Wasserstein approximation to a finite-dimensional frame objective and supply tools for the main statistical and computational analyses. They also verify smoothness and curvature properties for the Gaussian convolution model under stated conditions.
A.1 Wasserstein projection onto frame axes
- The nearest-axis Wasserstein projection reduces measure approximation over frame-supported measures to minimizing a finite-dimensional objective over orthogonal frames.The identity also applies to the empirical measure, and the objective attains its minimum.Source: §A.1 · p. 28
A.2 Hilbert-space concentration
- A Bennett-type Hilbert-space concentration inequality supports the empirical-subgradient and online-SGD proofs.The summands lie in the tangent space at a fixed frame, equipped with the Frobenius norm.Source: §A.2 · pp. 28–29
A.3 Metric and exponential-map comparisons
- The Frobenius discrepancy after signed-permutation alignment is bounded by the frame distance, and the exponential map is nonexpansive in Frobenius norm.The exponential-map comparison holds for all tangent vectors, including those larger than the injectivity radius.Source: §A.3 · p. 29
A.4 Active-tie nullity from differentiability
- Differentiability of the population objective implies that nonzero active ties occur with probability zero at a fixed frame.Consequently, measurable selections of active gradients agree almost surely and have expectation equal to the population gradient.Source: §A.4 · pp. 29–30
B Verification of the Gaussian convolution model
- For fixed dimension and sufficiently small noise, the Gaussian convolution model satisfies the analysis assumptions on a neighborhood of the optimal frame.For balanced Gaussian mixtures, the appendix develops dimension-uniform curvature and global-gap estimates accommodating noise scaling τ^2 ≤ b+/d.Source: B Verification of the Gaussian… · pp. 30–31
B.1 Variational formulas and noiseless curvature
- The population risk has a second-variation formula that separates active-cell contributions from moving-boundary contributions.For the noiseless signal law, the nearest-axis assignment is fixed near the optimum, enabling an exact local curvature calculation; the resulting risk is strongly convex on each signed-permutation neighborhood.Source: §B.1 · pp. 32–33
B.2 Hessian stability and fixed-dimensional local regularity
This section establishes local regularity and curvature properties for Gaussian-convolved objectives and balanced Gaussian mixtures, including strict local minimizers at signed-permutation frames and dimension-uniform bounds under a noise constraint. It also gives dimension-scaled Hessian and gradient-Lipschitz bounds on a geodesically convex ball, where reflection symmetry makes the target frame critical and a dimension threshold controls the correction relative to oracle curvature.
B.2 Hessian stability and fixed-dimensional local regularity
- Theorem 32 gives E ∈ C2 near U⋆, with geodesic strong convexity m = amin/2 and an L-Lipschitz Riemannian gradient for L = 4amax.These bounds hold for 0 < τ < τ1 on the specified neighborhood and extend to its signed-permutation translates.Source: §B.2 · pp. 34, 38
- For bounded-density axial mixtures with finite fourth moments, convolution changes the Hessian by at most O(τ^3); if τ ≤ (m/C)^(1/3) and Hess Eν ⪰ 2mI, then Hess Eµ ⪰ mI.The Hessian comparison controls both cellwise second derivatives and moving cell boundaries; C depends only on dimension and the density bound.Source: §B.2 · pp. 34, 38
- When τ < τ1, every signed-permutation frame of U⋆ is a strict local minimizer of E, and all such frames are critical points for every τ > 0.The population risk is geodesically m-strongly convex on each corresponding neighborhood, with m = amin/2; its Riemannian gradient is L-Lipschitz with L = 4amax.Source: §B.2 · pp. 34, 38, 39
B.3 Dimension-uniform curvature for balanced Gaussian mixtures
- For balanced Gaussian mixtures, Proposition 35 establishes dimension-uniform local curvature when d is sufficiently large and 0 < τ^2 ≤ b+/d.The proposition also states that the local ball is geodesically convex, has disjoint signed-permutation translates, and satisfies dframe = dg.Source: §B.3 · p. 39
- The correction is O(d^-1)||Ω||²_F, the same order as oracle curvature, allowing d0 to ensure the bound is at most (σ_-^2/(2d))||Ω||²_F.Source: §B.3 · p. 41
- The geodesically convex ball has lower Hessian bound m=σ_-^2/(2d) and intrinsic gradient-Lipschitz constant L=4σ_+^2/d; reflection symmetry makes U⋆ critical.These bounds hold for d≥d0.Source: §B.3 · p. 41
B.4 Dimension-uniform global gap for balanced Gaussian mixtures
The appendix establishes global separation and complete minimizer-orbit results for balanced Gaussian mixtures and, under Gaussian convolution, sublevel-set containment and switching-margin bounds. It then verifies the model assumptions used by the paper’s convergence analysis.
B.4 Dimension-uniform global gap for balanced Gaussian mixtures
- For balanced Gaussian mixtures with τ^2 ≤ b+/d, the risk has a positive global gap outside the aligned neighborhoods, and the signed-permutation orbit is the complete minimizer set.The stated gap scales as σ_-^2 c_r/(4d); local strong convexity identifies the unique minimizer within each aligned component.Source: §B.4 · pp. 43–44
B.5 Sublevel-set containment under Gaussian convolution
- For general axial laws at fixed dimension, Gaussian convolution transfers a positive noiseless risk gap to sublevel-set containment and identifies the complete minimizer orbit for sufficiently small noise.The proof combines the gap with uniform objective stability and local strong convexity.Source: §B.5 · pp. 44–46
B.6 Far-region switching margin under Gaussian convolution
- For Gaussian convolution, the switching-margin probability bound holds for every τ > 0, and its constant is O(Mτd) as d grows with fixed neighborhood radius and compatible η0.The small-noise restriction required for curvature and sublevel-set estimates is not required for this bound.Source: §B.6 · p. 46
B.7 Proofs of the model-verification propositions
- The model-verification proofs establish the stated assumptions for Gaussian mixtures and identify the signed-permutation orbit as the complete minimizer orbit.The verification uses the global-gap result and supplies sublevel containment and a switching-margin bound.Source: §B.7 · pp. 47–48
C.1 Subdifferential analysis of the empirical objective
The appendix characterizes the empirical objective’s subdifferential and develops concentration and geometric tools for handling frame-dependent switching. These tools connect pointwise subgradient control to sparse coverage of switching regions.
C.1 Subdifferential analysis of the empirical objective
- The empirical loss’s Riemannian Clarke subdifferential is the convex hull of its active branch gradients, and the canonical selection belongs to it.At a fixed frame in the aligned neighborhood, the selections agree almost surely; at an empirical local minimizer, the empirical subdifferential is zero and the objective is locally analytic.Source: §C.1 · pp. 48–49
C.2 Pointwise concentration of empirical subgradients
- At any fixed deterministic frame in the aligned neighborhood, nonsmoothness is almost surely invisible and ordinary i.i.d. concentration gives the parametric rate.The remaining analysis extends fixed-frame control uniformly over the aligned component while accounting for switching.Source: §C.2 · pp. 49–51
C.3 Geometry of switching sets
- The switching geometry is organized by the set of directions whose winning axis changes between two frames and by geodesic tubes around such sets.The section uses these constructions to control where changes in the selected axis can occur.Source: §C.3 · p. 51, §C.3.1 · p. 52
C.3.1 Voronoi stability under frame perturbations
- When two frames are Frobenius-close, a direction’s winning axis remains unchanged outside a neighborhood of the ambiguity set; switches are localized near that set.The corresponding switching set is covered by a geodesic tube, as formalized by the switching-localization result.Source: §C.3.1 · pp. 51–52
C.3.2 Sphere packing and stripe construction
- A maximal δ-separated sphere packing yields Voronoi cells of diameter at most 2δ and centers used to define universal stripes.The packing size is bounded above and below in Proposition 49.Source: §C.3.2 · pp. 52–53
C.3.3 Geometric properties for stripe coverage
- The switching region for δ-close frames admits a sparse cover by universal stripes, with selected centers within Euclidean distance δ of corresponding signed-bisector normals.This cover supplies the input to the subsequent sample-count bounds.Source: §C.3.3 · p. 54
C.4 Simultaneous concentration across stripes
The section controls stripe counts simultaneously, then uses that control to bound switching across nearby frames. It extends the argument to empirical subgradient control through a coarsely Lipschitz bound and a deterministic covering argument.
C.4 Simultaneous concentration across stripes
- With probability at least 1 − Mn^−(d−1), all stripes simultaneously satisfy the stated count bounds.Each stripe fails with probability at most n^−3d; the proof uses the simpler n^−(d−1) bound for comparability with other appendix bounds.Source: §C.4 · p. 55
- A cover of at most d(d − 1) eligible stripes bounds switching counts for every admissible nearby frame pair.The simultaneous stripe event controls all eligible stripes, so the bound holds even though the covering indices depend on the frame pair.Source: §C.4 · p. 56
- For margin exponent α > 0, the switching term vanishes; it preserves the near-parametric rate exactly when α ≥ 1.For α < 1 it is at most order n^−α/2 log n and dominates the rate; for α = 0 it does not vanish.Source: §C.4 · p. 56
C.5.1 Coarsely Lipschitz property
- The empirical subgradient bound separates samples whose selected axes stay fixed from switching samples, controlling the latter by their count.The non-switching contribution is bounded by 4M2δ; the switching contribution is controlled using the maximum-norm and simultaneous switching-count events.Source: §C.5.1 · pp. 56–57
C.5.2 Deterministic covering lemma
- A deterministic covering argument extends local empirical-subgradient control on a finite net to a uniform bound over the neighborhood.The extension combines the population gradient's intrinsic Lipschitz continuity with the coarsely Lipschitz empirical bound.Source: §C.5.2 · pp. 57–58
C.5.3 Proof of uniform empirical subgradient control
The proof obtains uniform empirical-subgradient control by combining concentration on a finite net with the coarsely Lipschitz estimate. Uniform objective convergence then localizes empirical minimizers to the neighborhood of the population minimizer.
C.5.3 Proof of uniform empirical subgradient control
- Finite-net concentration plus the coarsely Lipschitz estimate yields uniform empirical-subgradient control over the neighborhood.The combined good event has probability at least 1 − 3/n − psw(n).Source: §C.5.3 · p. 58
C.6 Localization of the empirical minimizer
- On the uniform-deviation event, every empirical minimizer lies in Sρ and has a unique alignment in the specified neighborhood.A point outside Sρ cannot minimize empirical risk on that event.Source: §C.6 · pp. 59–60
- Under the stated sample-size condition, the uniform objective-deviation event has probability at least 1 − β.The proof propagates finite-net deviations to all of O(d) using a Lipschitz bound.Source: §C.6 · p. 59
D Technical proofs for Theorem 11
These proofs establish the stochastic-gradient method's local behavior and escape control. They identify the mean oracle with the population gradient locally, bound stochastic-gradient noise, and show contraction and invariance within a neighborhood.
D.1 SGD estimator and centered-ball setup
- Within N, the mean oracle equals the population gradient; fresh-batch independence makes each stochastic-gradient estimate conditionally unbiased, and signed permutations preserve equivariance.The oracle's population mean is defined on O(d), while its equality to the population gradient is asserted on N.Source: §D.1 · pp. 60–61
D.2 Dimension-free stochastic-gradient concentration
- Conditional stochastic-gradient concentration is established under finite fourth moments and strengthened under sub-exponential squared norms.The bounds are applied across iterations using a union bound.Source: §D.1 · p. 60, §D.2 · p. 61
D.3 Sharp local contraction and invariant-ball control
- Inside the centered ball, strong-convexity and smoothness bounds yield local contraction; bounded gradient noise keeps iterates inside that ball.The invariant-ball argument iterates rt+1 ≤ qηrt + ηε, with rinit and ε/m no greater than rc.Source: §D.3 · p. 62
E.1 Escape probability
- The expected-error analysis accounts for trajectories that escape the strongly convex neighborhood by bounding escape probability using stochastic-gradient noise.Theorem 62 states escape-probability bounds under finite fourth moments and, with an additional assumption, sub-exponential squared norms.Source: E An in-expectation online-SGD… · p. 62, §E.1 · pp. 62–63
E.2 Expected-error bound
The expected-error guarantee combines local contraction with a bound on trajectories outside the centered ball. With the prescribed iteration horizon and batch size, the resulting estimate also controls frame distance.
E.2 Expected-error bound
- With T = ⌈citerκ log n⌉ and B = ⌊n/T⌋, the resulting estimate bounds frame distance by geodesic distance.The proof uses q²T ≤ n^−1 and B ≥ n/(2T) under its stated conditions.Source: §E.2 · pp. 63–64
- The expected-error analysis combines local contraction with a global diameter bound to account for trajectories outside the centered ball.The squared geodesic diameter of each connected component of O(d) is at most π²d.Source: §E.2 · pp. 63–64
F Real-data experiments
On the NYT corpus, independently rotating the document and word sides of one rank-eight fit concentrates mass near the coordinate axes for either interpretive goal. Concentration is uneven across coordinates, and the figure shows a 5,000-row leverage sample.
F Real-data experiments
- The NYT experiment retains a rank-eight approximation of a 300,000-document by 102,660-word matrix after preprocessing and excluding localized singular vectors.The pipeline follows degree-normalization, centering, and rank selection, with a fourth-moment diagnostic for exclusion.Source: F Real-data experiments · p. 64
- Figure 5 displays a fixed-seed, 5,000-row leverage sample, with coordinate-wise sample kurtosis on the diagonal.The top row shows document coefficients and their rotated counterparts; the bottom row shows normalized word loadings and their rotated counterparts.Source: Figure 5 · p. 65, F Real-data experiments · p. 66
- The word-side rotation uses Vk rather than scaled loadings D0, whose equal-norm columns isolate rotational sparsity from singular-value scale differences.The dictionary-learning and factor-analysis rotations are fit independently.Source: F Real-data experiments · pp. 64, 66
- After rotation, mass concentrates near the axes in both document codes and word loadings, peaking at z6 and ˜λ7.The same rank-eight fit is rotated toward dictionary learning on the document side and factor analysis on the word side; the two rotations need not agree.Source: F Real-data experiments · pp. 64, 66