Proves detection of RGG vs. ER is impossible for d ≫ (n h(p))^3 and d ≥ (1+ε)n, resolving the detection threshold conjecture in the regime p ≳ n^{-2/3}/log n.
hub
Introduction to the non-asymptotic analysis of random matrices
42 Pith papers cite this work. Polarity classification is still indexing.
42
Pith papers citing it
abstract
This is a tutorial on some basic non-asymptotic methods and concepts in random matrix theory. The reader will learn several tools for the analysis of the extreme singular values of random matrices with independent rows or columns. Many of these methods sprung off from the development of geometric functional analysis since the 1970's. They have applications in several fields, most notably in theoretical computer science, statistics and signal processing. A few basic applications are covered in this text, particularly for the problem of estimating covariance matrices in statistics and for validating probabilistic constructions of measurement matrices in compressed sensing. These notes are written particularly for graduate students and beginning researchers in different areas, including functional analysts, probabilists, theoretical statisticians, electrical engineers, and theoretical computer scientists.
hub tools
citation-role summary
background 3
citation-polarity summary
fields
cs.LG 11 stat.ML 11 stat.ME 5 math.ST 4 math.OC 3 math.PR 3 eess.IV 2 econ.EM 1 eess.SY 1 math.NA 1roles
background 3representative citing papers
Differential privacy requires poly(d) samples for k-sparse covariance estimation and PCA, creating an exponential gap from non-private poly(k, log d) bounds when k=polylog(d), plus a poly(k, log d) upper bound for eigenvector-sparse PCA.
Introduces hybrid noise and novel coupling analysis to achieve the first convergent hidden-state DP bound for zeroth-order optimization.
For quadratic targets in d dimensions, two-layer quadratic networks achieve lower risk when fully trained than in random features or neural tangent regimes if hidden units < d.
Transformers converge globally to the optimal DDPM denoiser for multi-token GMMs via self-attention mean denoising, with explicit token and iteration requirements.
Direction-magnitude decomposition yields two new methods for low-rank matrix factorization that converge exponentially faster than standard gradient descent on the Burer-Monteiro formulation.
Introduces Boltzmann margin to prove near-exponential convergence rates for kNN classification.
Bounded overestimation of the number of factors in PCA preserves √T-valid inference and consistent factor-space recovery under a random-matrix local law.
A solvable hierarchical model with power-law feature strengths yields explicit power-law scaling of prediction error through sequential recovery of latent directions by a layer-wise spectral algorithm.
New analysis without global strong convexity yields tight scaling laws: NS error ~Θ(kd/n²) and NS-IF difference ~Θ((k+d)√(kd)/n²) for well-behaved logistic regressions.
Develops a joint Catoni-type framework that simultaneously estimates parameters and variance in heavy-tailed models via coupled equations, achieving oracle-matching non-asymptotic bounds under 2β-moment assumptions using a Poincaré-Miranda proof technique.
A connection between Huber's contamination and heavy-tailed models yields unified robust mean estimators that are both computationally efficient and statistically optimal under certain conditions.
Alternating minimization with spectral-plus-random-search initialization converges geometrically and attains near-minimax optimal estimation rates for max-affine regression when k is fixed and the design is random.
ABGD parametrizes piecewise linear functions as difference of max-affine functions and converges linearly to an epsilon-accurate solution with O(d max(sigma/epsilon,1)^2) samples under sub-Gaussian noise, which is minimax optimal up to logs.
Multi-layer transformers can implement in-context logistic regression by performing normalized gradient descent steps layer by layer, obtained via supervised training of a single attention layer followed by recurrent application with convergence and OOD guarantees.
A stagewise greedy algorithm for semiparametric contextual dynamic pricing achieves regret T to the max of 1/2 and 3 over (2 beta plus 1) for linear m, with a matching lower bound proving optimality.
An adaptive fused orthogonal estimator recovers latent clusters exactly with high probability and achieves pooled parametric rates plus asymptotic normality matching an oracle in semiparametric heterogeneous clustered multitask learning.
The limiting distribution of the LS estimator in panel models with interactive fixed effects is invariant to over-specifying the number of factors.
PrivacyCredit is a machine learning method that combines traditional and alternative data for credit risk prediction while satisfying privacy-preserving, model-confidential, and lossless properties.
Establishes convergence guarantees for overparameterized 2-layer ReLU networks in flow matching, generalization bounds for the velocity-field objective, and Wasserstein guarantees for generated samples, using multi-task representation learning bounds.
Proposes a sparsity-plus-fusion-penalty federated estimator for tail index regression with non-asymptotic rates, oracle group recovery, ADMM solver, and debiased inference that improves on target-only methods.
A non-asymptotic bound on compression error for signal parameterizations derived from differences in predictions at varying compression levels, verified empirically across fitting and inverse problems.
RankElastor mitigates embedding collapse via spectrum-robust token mixing and GLU-based P-FFNs, yielding better performance and scaling on industrial recommendation datasets.
Matrix-weighted regularization for robust multi-task regression achieves optimal MSE under weaker spectral assumptions and performs no worse than independent learning when balancedness is poor.
citing papers explorer
-
Resolution of the Detection Threshold Conjecture for Random Geometric Graphs in the $d>n$ Regime
Proves detection of RGG vs. ER is impossible for d ≫ (n h(p))^3 and d ≥ (1+ε)n, resolving the detection threshold conjecture in the regime p ≳ n^{-2/3}/log n.
-
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Differential privacy requires poly(d) samples for k-sparse covariance estimation and PCA, creating an exponential gap from non-private poly(k, log d) bounds when k=polylog(d), plus a poly(k, log d) upper bound for eigenvector-sparse PCA.
-
Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States
Introduces hybrid noise and novel coupling analysis to achieve the first convergent hidden-state DP bound for zeroth-order optimization.
-
Limitations of Lazy Training of Two-layers Neural Networks
For quadratic targets in d dimensions, two-layer quadratic networks achieve lower risk when fully trained than in random features or neural tangent regimes if hidden units < d.
-
Transformers Learn the Optimal DDPM Denoiser for Multi-Token GMMs
Transformers converge globally to the optimal DDPM denoiser for multi-token GMMs via self-attention mean denoising, with explicit token and iteration requirements.
-
Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics
Direction-magnitude decomposition yields two new methods for low-rank matrix factorization that converge exponentially faster than standard gradient descent on the Burer-Monteiro formulation.
-
Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
Introduces Boltzmann margin to prove near-exponential convergence rates for kNN classification.
-
Fixed-order PCA: Theory for Overestimated Factor Models
Bounded overestimation of the number of factors in PCA preserves √T-valid inference and consistent factor-space recovery under a random-matrix local law.
-
Scaling Laws from Sequential Feature Recovery: A Solvable Hierarchical Model
A solvable hierarchical model with power-law feature strengths yields explicit power-law scaling of prediction error through sequential recovery of latent directions by a layer-wise spectral algorithm.
-
On the Accuracy of Newton Step and Influence Function Data Attributions
New analysis without global strong convexity yields tight scaling laws: NS error ~Θ(kd/n²) and NS-IF difference ~Θ((k+d)√(kd)/n²) for well-behaved logistic regressions.
-
Tuning free Catoni type joint robust estimation
Develops a joint Catoni-type framework that simultaneously estimates parameters and variance in heavy-tailed models via coupled equations, achieving oracle-matching non-asymptotic bounds under 2β-moment assumptions using a Poincaré-Miranda proof technique.
-
A Unified Approach to Robust Mean Estimation
A connection between Huber's contamination and heavy-tailed models yields unified robust mean estimators that are both computationally efficient and statistically optimal under certain conditions.
-
Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
Alternating minimization with spectral-plus-random-search initialization converges geometrically and attains near-minimax optimal estimation rates for max-affine regression when k is fixed and the design is random.
-
Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions
ABGD parametrizes piecewise linear functions as difference of max-affine functions and converges linearly to an epsilon-accurate solution with O(d max(sigma/epsilon,1)^2) samples under sub-Gaussian noise, which is minimax optimal up to logs.
-
Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent
Multi-layer transformers can implement in-context logistic regression by performing normalized gradient descent steps layer by layer, obtained via supervised training of a single attention layer followed by recurrent application with convergence and OOD guarantees.
-
Optimal Semiparametric Dynamic Pricing with Feature Diversity
A stagewise greedy algorithm for semiparametric contextual dynamic pricing achieves regret T to the max of 1/2 and 3 over (2 beta plus 1) for linear m, with a matching lower bound proving optimality.
-
Adaptive Estimation and Inference in Semi-parametric Heterogeneous Clustered Multitask Learning via Neyman Orthogonality
An adaptive fused orthogonal estimator recovers latent clusters exactly with high probability and achieves pooled parametric rates plus asymptotic normality matching an oracle in semiparametric heterogeneous clustered multitask learning.
-
Linear Regression for Panel With Unknown Number of Factors as Interactive Fixed Effects
The limiting distribution of the LS estimator in panel models with interactive fixed effects is invariant to over-specifying the number of factors.
-
Privacy-Preserving Credit Risk Prediction with Alternative Data
PrivacyCredit is a machine learning method that combines traditional and alternative data for credit risk prediction while satisfying privacy-preserving, model-confidential, and lossless properties.
-
A Theory on Flow Matching with Neural Networks
Establishes convergence guarantees for overparameterized 2-layer ReLU networks in flow matching, generalization bounds for the velocity-field objective, and Wasserstein guarantees for generated samples, using multi-task representation learning bounds.
-
Efficient Federated Estimation and Inference for High-Dimensional Tail Index Regression
Proposes a sparsity-plus-fusion-penalty federated estimator for tail index regression with non-asymptotic rates, oracle group recovery, ADMM solver, and debiased inference that improves on target-only methods.
-
Bounding Global and Local Compression Error of Signal Parameterizations
A non-asymptotic bound on compression error for signal parameterizations derived from differences in predictions at varying compression levels, verified empirically across fitting and inverse problems.
-
Expand More, Shrink Less: Shaping Effective-Rank Dynamics for Dense Scaling in Recommendation
RankElastor mitigates embedding collapse via spectrum-robust token mixing and GLU-based P-FFNs, yielding better performance and scaling on industrial recommendation datasets.
-
Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness, and Safety
Matrix-weighted regularization for robust multi-task regression achieves optimal MSE under weaker spectral assumptions and performs no worse than independent learning when balancedness is poor.
-
Concentration Inequalities for Sample Cross-Covariances
Proves sharp operator-norm concentration and expectation bounds for sample cross-covariances of sub-Gaussian and Gaussian vectors, governed by effective ranks of the marginal covariances.
-
Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing
Develops a two-stage system identification plus sensor allocation algorithm with non-asymptotic guarantees for near-optimal sensor counts in unknown high-dimensional linear systems.
-
Discrepancies are Virtue: Weak-to-Strong Generalization through Lens of Intrinsic Dimension
In ridgeless regression with low intrinsic dimension, discrepancy between weak and strong models reduces W2S generalization variance by dim(V_s)/N in the discrepant subspace while inheriting it in the overlap.
-
Best Policy Learning from Trajectory Preference Feedback
PSPL maintains posteriors over reward models and dynamics to deliver the first Bayesian simple regret guarantees for PbRL and outperforms baselines on simulation and image generation tasks.
-
Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models
SPIN lets weak LLMs become strong by self-generating training data from previous model versions and training to prefer human-annotated responses over its own outputs, outperforming DPO even with extra GPT-4 data on benchmarks.
-
Sliced Inner Product Gromov-Wasserstein Distances
A sliced IGW distance is introduced with closed-form 1D expressions, rotational invariance, and studied structural and computational properties for efficient data alignment.
-
Transfer Learning for Degree-Corrected Mixed Membership Network Models
Transfer learning from informative source networks improves target DCMM estimation accuracy by enlarging the eigenvalue gap of the connection probability matrix, with algorithms to avoid negative transfer.
-
Restart and Adaptive Acceleration in Stochastic Gradient Methods
Restart schemes for SGD on KL-satisfying non-smooth weakly convex problems deliver accelerated convergence robust to exponent misspecification, with optimal schedules resembling Polyak steps.
-
A Two-Sided Sketching Algorithm for Low-rank Tensor Train Approximation
A two-sided sketching algorithm with subspace iteration for low-rank tensor train approximation, including error bounds and numerical tests on synthetic and real data.
-
Efficient Propose-Test-Release for Optimal Differentially Private Estimation
Introduces ePTR pipeline using safety lower bound testing to enable optimal DP mechanisms for sensitive estimators in classification and regression.
-
On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains
A method is given to determine eigenvalue decay rates of NTK and related kernels on general domains, leading to minimax optimality results for wide neural networks under smoothness assumptions on the target function.
-
Exact Crystalline Structure Recovery in X-ray Crystallography from Coded Diffraction Patterns
Coded apertures enable exact crystalline structure recovery from fewer diffraction patterns via sparsity in the Fourier domain.
-
Anchored Spectral Estimator for Rigid Motion Synchronization
ASE is a spectral method for rigid motion synchronization that delivers uniform estimation error bounds and outperforms two-stage rotation-then-translation approaches on synthetic and registration tasks.
-
Adversarial Contamination Meets Hard Thresholding: An Iterative Algorithm with Signal Adaptivity and Minimax Optimality
AC-IHT is a two-stage iterative algorithm for contaminated high-dimensional regression that attains minimax near-optimal rates, signal adaptivity under suitable conditions, and the strong oracle property.
-
High Dimensional Change Point Models for Two-Directional Data
Develops methodology and asymptotic theory for single and multiple change point recovery in high-dimensional two-directional mean processes, with climate data application.
-
A Refined Non-asymptotic Tail Bound of Sub-Gaussian Matrix
Derives refined non-asymptotic tail bound for largest singular value of sub-Gaussian matrices with application to Gaussian Toeplitz matrices.
- Sparse Convexification for High-Dimensional Constrained Regression
- Fast Near-Optimal Estimation over Symmetric Norm Balls