Publications (92)
An arithmetic-geometric mean inequality for products of three matrices
Arie Israel, Felix Krahmer, Rachel Ward
Consider the following noncommutative arithmetic-geometric mean inequality: given positive-semidefinite matrices , the following holds for each i…
Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone
Marah Abdin, Jyoti Aneja, Hany Awadalla +126
We introduce phi-3-mini, a 3.8 billion parameter language model trained on 3.3 trillion tokens, whose overall performance, as measured by both academic benchmarks and internal test…
Side Effects of Learning from Low-dimensional Data Embedded in a Euclidean Space
Juncai He, Richard Tsai, Rachel Ward
The low-dimensional manifold hypothesis posits that the data found in many applications, such as those involving natural images, lie (approximately) on low-dimensional manifolds em…
Learning to Forecast Dynamical Systems from Streaming Data
Dimitris Giannakis, Amelia Henriksen, Joel A. Tropp +1
Kernel analog forecasting (KAF) is a powerful methodology for data-driven, non-parametric forecasting of dynamically generated time series data. This approach has a rigorous founda…
Concentration of Random Feature Matrices in High-Dimensions
Zhijun Chen, Hayden Schaeffer, Rachel Ward
The spectra of random feature matrices provide essential information on the conditioning of the linear system used in random feature regression problems and are thus connected to t…
The sample complexity of weighted sparse approximation
Bubacarr Bah, Rachel Ward
For Gaussian sampling matrices, we provide bounds on the minimal number of measurements required to achieve robust weighted sparse recovery guarantees in terms of how well a gi…
An introduction to how chi-square and classical exact tests often wildly misreport significance and how the remedy lies in computers
William Perkins, Mark Tygert, Rachel Ward
Goodness-of-fit tests based on the Euclidean distance often outperform chi-square and other classical tests (including the standard exact tests) by at least an order of magnitude w…
TinyGSM: achieving >80% on GSM8k with small language models
Bingbin Liu, Sebastien Bubeck, Ronen Eldan +5
Small-scale models offer various computational advantages, and yet to which extent size is critical for problem-solving abilities remains an open question. Specifically for solving…
Testing Hardy-Weinberg equilibrium with a simple root-mean-square statistic
Rachel Ward, Raymond J. Carroll
We provide evidence that a root-mean-square test of goodness-of-fit can be significantly more powerful than state-of-the-art exact tests in detecting deviations from Hardy-Weinberg…
Clustering subgaussian mixtures by semidefinite programming
Dustin G. Mixon, Soledad Villar, Rachel Ward
We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a deno…
A symbol-based algorithm for decoding bar codes
Mark Iwen, Fadil Santosa, Rachel Ward
We investigate the problem of decoding a bar code from a signal measured with a hand-held laser-based scanner. Rather than formulating the inverse problem as one of binary image re…
Chi-square and classical exact tests often wildly misreport significance; the remedy lies in computers
William Perkins, Mark Tygert, Rachel Ward
If a discrete probability distribution in a model being tested for goodness-of-fit is not close to uniform, then forming the Pearson chi-square statistic can involve division by ne…
Exact Recovery of Chaotic Systems from Highly Corrupted Data
Giang Tran, Rachel Ward
Learning the governing equations in dynamical systems from time-varying measurements is of great interest across different scientific fields. This task becomes prohibitive when suc…
Bootstrapping the error of Oja's algorithm
Robert Lunde, Purnamrita Sarkar, Rachel Ward
We consider the problem of quantifying uncertainty for the estimation error of the leading eigenvector from Oja's algorithm for streaming principal component analysis, where the da…
Improved bounds for sparse recovery from subsampled random convolutions
Shahar Mendelson, Holger Rauhut, Rachel Ward
We study the recovery of sparse vectors from subsampled random convolutions via -minimization. We consider the setup in which both the subsampling locations as well as the…
Sparse Legendre expansions via minimization
Holger Rauhut, Rachel Ward
We consider the problem of recovering polynomials that are sparse with respect to the basis of Legendre polynomials from a small number of random samples. In particular, we show th…
Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
Xiaoxia Wu, Simon S. Du, Rachel Ward
Adaptive gradient methods like AdaGrad are widely used in optimizing neural networks. Yet, existing convergence guarantees for adaptive gradient methods require either convexity or…
Lower bounds for the error decay incurred by coarse quantization schemes
Felix Krahmer, Rachel Ward
Several analog-to-digital conversion methods for bandlimited signals used in applications, such as Sigma Delta quantization schemes, employ coarse quantization coupled with oversam…
Learning Dynamical Systems and Bifurcation via Group Sparsity
Hayden Schaeffer, Giang Tran, Rachel Ward
Learning governing equations from a family of data sets which share the same physical laws but differ in bifurcation parameters is challenging. This is due, in part, to the wide ra…
One-bit compressive sensing with norm estimation
Karin Knudson, Rayan Saab, Rachel Ward
Consider the recovery of an unknown signal from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that is sparse, and tha…
Low-rank matrix recovery via iteratively reweighted least squares minimization
Massimo Fornasier, Holger Rauhut, Rachel Ward
We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algo…
Compressed Sensing with Cross Validation
Rachel Ward
Compressed Sensing decoding algorithms can efficiently recover an N dimensional real-valued vector x to within a factor of its best k-term approximation by taking m = 2klog(N/k) me…
First Proof
Mohammed Abouzaid, Andrew J. Blumberg, Martin Hairer +8
To assess the ability of current AI systems to correctly answer research-level mathematics questions, we share a set of ten math questions which have arisen naturally in the resear…
Concentration Inequalities for Sums of Markov Dependent Random Matrices
Joe Neeman, Bobby Shi, Rachel Ward
We give Hoeffding and Bernstein-type concentration inequalities for the largest eigenvalue of sums of random matrices arising from a Markov chain. We consider time-dependent matrix…
Phi-4 Technical Report
Marah Abdin, Jyoti Aneja, Harkirat Behl +24
We present phi-4, a 14-billion parameter language model developed with a training recipe that is centrally focused on data quality. Unlike most language models, where pre-training…
Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
De Huang, Jonathan Niles-Weed, Rachel Ward
We analyze Oja's algorithm for streaming -PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. $…
The local convexity of solving systems of quadratic equations
Chris D. White, Sujay Sanghavi, Rachel Ward
This paper considers the recovery of a rank positive semidefinite matrix from scalar measurements of the form (i.e…
Two-subspace Projection Method for Coherent Overdetermined Systems (Technical Report)
Deanna Needell, Rachel Ward
In this technical report we present a Projection onto Convex Sets (POCS) type algorithm for solving systems of linear equations. POCS methods have found many applications ranging f…
Compressed sensing with a jackknife and a bootstrap
Mark Tygert, Rachel Ward, Jure Zbontar
Compressed sensing proposes to reconstruct more degrees of freedom in a signal than the number of values actually measured. Compressed sensing therefore risks introducing errors --…
Convergence of Alternating Gradient Descent for Matrix Factorization
Rachel Ward, Tamara G. Kolda
We consider alternating gradient descent (AGD) with fixed step size applied to the asymmetric matrix factorization objective. We show that, for a rank- matrix $\mathbf{A} \in \m…
Recovery guarantees for exemplar-based clustering
Abhinav Nellore, Rachel Ward
For a certain class of distributions, we prove that the linear programming relaxation of -medoids clustering---a variant of -means clustering where means are replaced by exem…
On Robustness Properties of Beta Encoders and Golden Ratio Encoders
Rachel Ward
The beta-encoder was recently proposed as a quantization scheme for analog-to-digital conversion; in contrast to classical binary quantization, in which each analog sample x in [-1…
A unified framework for linear dimensionality reduction in L1
Felix Krahmer, Rachel Ward
For a family of interpolation norms on , we provide a distribution over random matrices parametrized by spars…
Stable and robust sampling strategies for compressive imaging
Felix Krahmer, Rachel Ward
In many signal processing applications, one wishes to acquire images that are sparse in transform domains such as spatial finite differences or wavelets using frequency domain samp…
Stable image reconstruction using total variation minimization
Deanna Needell, Rachel Ward
This article presents near-optimal guarantees for accurate and robust image recovery from under-sampled noisy measurements using total variation minimization. In particular, we sho…
Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
Deanna Needell, Nathan Srebro, Rachel Ward
We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic depende…
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
Rachel Ward, Xiaoxia Wu, Leon Bottou
Adaptive gradient methods such as AdaGrad and its variants update the stepsize in stochastic gradient descent on the fly according to the gradients received along the way; such met…
Sparse recovery for spherical harmonic expansions
Holger Rauhut, Rachel Ward
We show that sparse spherical harmonic expansions can be efficiently recovered from a small number of randomly chosen samples on the sphere. To establish the main result, we verify…
Weighted eigenfunction estimates with applications to compressed sensing
Nicolas Burq, Semyon Dyatlov, Rachel Ward +1
Using tools from semiclassical analysis, we give weighted L^\infty estimates for eigenfunctions of strictly convex surfaces of revolution. These estimates give rise to new sampling…
Linear Convergence of Adaptive Stochastic Gradient Descent
Yuege Xie, Xiaoxia Wu, Rachel Ward
We prove that the norm version of the adaptive stochastic gradient method (AdaGrad-Norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-…
Completing Any Low-rank Matrix, Provably
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi +1
Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a…
Relax, no need to round: integrality of clustering formulations
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar +3
We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering:…
New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer, Rachel Ward
Consider an m by N matrix Phi with the Restricted Isometry Property of order k and level delta, that is, the norm of any k-sparse vector in R^N is preserved to within a multiplicat…
A polynomial-time relaxation of the Gromov-Hausdorff distance
Soledad Villar, Afonso S. Bandeira, Andrew J. Blumberg +1
The Gromov-Hausdorff distance provides a metric on the set of isometry classes of compact metric spaces. Unfortunately, computing this metric directly is believed to be computation…
AdaOja: Adaptive Learning Rates for Streaming PCA
Amelia Henriksen, Rachel Ward
Oja's algorithm has been the cornerstone of streaming methods in Principal Component Analysis (PCA) since it was first proposed in 1982. However, Oja's algorithm does not have a st…
Extracting structured dynamical systems using sparse optimization with very few samples
Hayden Schaeffer, Giang Tran, Rachel Ward +1
Learning governing equations allows for deeper understanding of the structure and dynamics of data. We present a random sampling method for learning structured dynamical systems fr…
Overparameterization and generalization error: weighted trigonometric interpolation
Yuege Xie, Hung-Hsu Chou, Holger Rauhut +1
Motivated by surprisingly good generalization properties of learned deep neural networks in overparameterized scenarios and by the related double descent phenomenon, this paper ana…
First Proof Second Batch
Mohammed Abouzaid, Nikhil Srivastava, Rachel Ward +1
To assess the ability of current AI systems to correctly solve research-level mathematics problems, we tested several AI systems on a set of ten problems in a broad range of mathem…
Computing the confidence levels for a root-mean-square test of goodness-of-fit, II
William Perkins, Mark Tygert, Rachel Ward
This paper extends our earlier article, "Computing the confidence levels for a root-mean-square test of goodness-of-fit;" unlike in the earlier article, the models in the present p…
Iterative thresholding meets free discontinuity problems
Massimo Fornasier, Rachel Ward
Free-discontinuity problems describe situations where the solution of interest is defined by a function and a lower dimensional set consisting of the discontinuities of the functio…
The Future of Artificial Intelligence and the Mathematical and Physical Sciences (AI+MPS)
Andrew Ferguson, Marisa LaFleur, Lars Ruthotto +97
This community paper developed out of the NSF Workshop on the Future of Artificial Intelligence (AI) and the Mathematical and Physics Sciences (MPS), which was held in March 2025 w…
Testing goodness-of-fit for logistic regression
Mark Tygert, Rachel Ward
Explicitly accounting for all applicable independent variables, even when the model being tested does not, is critical in testing goodness-of-fit for logistic regression. This can…
Batched Stochastic Gradient Descent with Weighted Sampling
Deanna Needell, Rachel Ward
We analyze a batched variant of Stochastic Gradient Descent (SGD) with weighted sampling distribution for smooth and non-smooth objective functions. We show that by distributing th…
The Hanson-Wright Inequality for Random Tensors
Stefan Bamberger, Felix Krahmer, Rachel Ward
We provide moment bounds for expressions of the type where denotes the Kronecker pro…
Concentration inequalities for random matrix products
Amelia Henriksen, Rachel Ward
Suppose is a sequence of bounded independent random matrices with common dimension and common expectation . Under t…
Scalable symmetric Tucker tensor decomposition
Ruhui Jin, Joe Kileel, Tamara G. Kolda +1
We study the best low-rank Tucker decomposition of symmetric tensors. The motivating application is decomposing higher-order multivariate moments. Moment tensors have special struc…
WNGrad: Learn the Learning Rate in Gradient Descent
Xiaoxia Wu, Rachel Ward, Léon Bottou
Adjusting the learning rate schedule in stochastic gradient methods is an important unresolved problem which requires tuning in practice. If certain parameters of the loss function…
Extracting Sparse High-Dimensional Dynamics from Limited Data
Hayden Schaeffer, Giang Tran, Rachel Ward
Extracting governing equations from dynamic data is an essential task in model selection and parameter estimation. The form of the governing equation is rarely known a priori; howe…
A near-stationary subspace for ridge approximation
Paul G. Constantine, Armin Eftekhari, Jeffrey Hokanson +1
Response surfaces are common surrogates for expensive computer simulations in engineering analysis. However, the cost of fitting an accurate response surface increases exponentiall…
Adaptively Weighted Data Augmentation Consistency Regularization for Robust Optimization under Concept Shift
Yijun Dong, Yuege Xie, Rachel Ward
Concept shift is a prevailing problem in natural tasks like medical image segmentation where samples usually come from different subpopulations with variant correlations between fe…
How catastrophic can catastrophic forgetting be in linear regression?
Itay Evron, Edward Moroshko, Rachel Ward +2
To better understand catastrophic forgetting, we study fitting an overparameterized linear model to a sequence of tasks with different input distributions. We analyze how much the…
Two-subspace Projection Method for Coherent Overdetermined Systems
Deanna Needell, Rachel Ward
We present a Projection onto Convex Sets (POCS) type algorithm for solving systems of linear equations. POCS methods have found many applications ranging from computer tomography t…
Interpolation via weighted minimization
Holger Rauhut, Rachel Ward
Functions of interest are often smooth and sparse in some sense, and both priors should be taken into account when interpolating sampled data. Classical linear interpolation method…
Recovery guarantees for polynomial approximation from dependent data with outliers
Lam Si Tung Ho, Hayden Schaeffer, Giang Tran +1
Learning non-linear systems from noisy, limited, and/or dependent data is an important task across various scientific fields including statistics, engineering, computer science, ma…
Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering
Yijun Dong, Kevin Miller, Qi Lei +1
Despite the empirical success and practical significance of (relational) knowledge distillation that matches (the relations of) features between teacher and student models, the cor…
Johnson-Lindenstrauss Embeddings with Kronecker Structure
Stefan Bamberger, Felix Krahmer, Rachel Ward
We prove the Johnson-Lindenstrauss property for matrices where has the restricted isometry property and is a diagonal matrix containing the entries of a Kronec…
Freedom through Imperfection: Exploiting the flexibility offered by redundancy in signal processing
Rachel Ward
This thesis consists of four chapters. The first two chapters pertain to the design of stable quantization methods for analog to digital conversion, while the third and fourth chap…
Greedy Variance Estimation for the LASSO
Christopher Kennedy, Rachel Ward
Recent results have proven the minimax optimality of LASSO and related algorithms for noisy linear regression. However, these results tend to rely on variance estimators that are i…
Stability for second-order chaotic sigma delta quantization
Lauren Bandklayder, Rachel Ward
We prove that that second-order (double-loop) chaotic sigma-delta schemes are stable - within a certain parameter range, all state variables of the system are guaranteed to remain…
An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models
Nhat Ho, Tongzheng Ren, Sujay Sanghavi +2
Using gradient descent (GD) with fixed or decaying step-size is a standard practice in unconstrained optimization problems. However, when the loss function is only locally convex,…
Large-Time Analysis of the Langevin Dynamics for Energies Fulfilling Polyak-Åojasiewicz Conditions
Massimo Fornasier, Lukang Sun, Rachel Ward
In this work, we take a step towards understanding overdamped Langevin dynamics for the minimization of a general class of objective functions . We establish well-pose…
Robust Implicit Regularization via Weight Normalization
Hung-Hsu Chou, Holger Rauhut, Rachel Ward
Overparameterized models may have many interpolating solutions; implicit regularization refers to the hidden preference of a particular optimization method towards a certain interp…
Faster Johnson-Lindenstrauss Transforms via Kronecker Products
Ruhui Jin, Tamara G. Kolda, Rachel Ward
The Kronecker product is an important matrix operation with a wide range of applications in supporting fast linear transforms, including signal processing, graph theory, quantum co…
On the complexity of Mumford-Shah type regularization, viewed as a relaxed sparsity constraint
Boris Alexeev, Rachel Ward
We show that inverse problems with a truncated quadratic regularization are NP-hard in general to solve, or even approximate up to an additive error. This stands in contrast to the…
Sample Efficiency of Data Augmentation Consistency Regularization
Shuo Yang, Yijun Dong, Rachel Ward +3
Data augmentation is popular in the training of large neural networks; currently, however, there is no clear theoretical comparison between different algorithmic choices on how to…
Quiet sigma delta quantization, and global convergence for a class of asymmetric piecewise affine maps
Rachel Ward
In this paper, we introduce a family of second-order sigma delta quantization schemes for analog-to-digital conversion which are `quiet' : quantization output is guaranteed to fall…
Significance testing without truth
William Perkins, Mark Tygert, Rachel Ward
A popular approach to significance testing proposes to decide whether the given hypothesized statistical model is likely to be true (or false). Statistical decision theory provides…
Computing the confidence levels for a root-mean-square test of goodness-of-fit
William Perkins, Mark Tygert, Rachel Ward
The classic chi-squared statistic for testing goodness-of-fit has long been a cornerstone of modern statistical practice. The statistic consists of a sum in which each summand invo…
Compressive Sensing with Redundant Dictionaries and Structured Measurements
Felix Krahmer, Deanna Needell, Rachel Ward
Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary .…
Implicit Regularization and Convergence for Weight Normalization
Xiaoxia Wu, Edgar Dobriban, Tongzheng Ren +5
Normalization methods such as batch [Ioffe and Szegedy, 2015], weight [Salimansand Kingma, 2016], instance [Ulyanov et al., 2016], and layer normalization [Baet al., 2016] have bee…
The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance
Matthew Faw, Isidoros Tziotis, Constantine Caramanis +3
We study convergence rates of AdaGrad-Norm as an exemplar of adaptive stochastic gradient methods (SGD), where the step sizes change based on observed stochastic gradients, for min…
SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning
Yuege Xie, Bobby Shi, Hayden Schaeffer +1
Sparse shrunk additive models and sparse random feature models have been developed separately as methods to learn low-order functions, where there are few interactions between vari…
A comparison of the discrete Kolmogorov-Smirnov statistic and the Euclidean distance
Jacob Carruth, Mark Tygert, Rachel Ward
Goodness-of-fit tests gauge whether a given set of observations is consistent (up to expected random fluctuations) with arising as independent and identically distributed (i.i.d.)…
Generalization Bounds for Sparse Random Feature Expansions
Abolfazl Hashemi, Hayden Schaeffer, Robert Shi +3
Random feature methods have been successful in various machine learning tasks, are easy to compute, and come with theoretical accuracy bounds. They serve as an alternative approach…
Arbitrary-length analogs to de Bruijn sequences
Abhinav Nellore, Rachel Ward
Let be a length- cyclic sequence of characters from a size- alphabet such that the number of occurrences of any length- string on $\mathcal{A}…
Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks
Zhenghao Xu, Yuqing Wang, Tuo Zhao +2
We study the convergence rate of first-order methods for rectangular matrix factorization, which is a canonical nonconvex optimization problem. Specifically, given a rank- matri…
On the fast convergence of minibatch heavy ball momentum
Raghu Bollapragada, Tyler Chen, Rachel Ward
Simple stochastic momentum methods are widely used in machine learning optimization, but their good practical performance is at odds with an absence of theoretical guarantees of ac…
Near-optimal compressed sensing guarantees for total variation minimization
Deanna Needell, Rachel Ward
Consider the problem of reconstructing a multidimensional signal from an underdetermined set of measurements, as in the setting of compressed sensing. Without any additional assump…
Bias of Homotopic Gradient Descent for the Hinge Loss
Denali Molitor, Deanna Needell, Rachel Ward
Gradient descent is a simple and widely used optimization method for machine learning. For homogeneous linear classifiers applied to separable data, gradient descent has been shown…
AdaLoss: A computationally-efficient and provably convergent adaptive gradient method
Xiaoxia Wu, Yuege Xie, Simon Du +1
We propose a computationally-friendly adaptive learning rate schedule, "AdaLoss", which directly uses the information of the loss function to adjust the stepsize in gradient descen…
Matrix Concentration for Products
De Huang, Jonathan Niles-Weed, Joel A. Tropp +1
This paper develops nonasymptotic growth and concentration bounds for a product of independent random matrices. These results sharpen and generalize recent work of Henriksen-Ward,…
Fast Cross-Polytope Locality-Sensitive Hashing
Christopher Kennedy, Rachel Ward
We provide a variant of cross-polytope locality sensitive hashing with respect to angular distance which is provably optimal in asymptotic sensitivity and enjoys $\mathcal{O}(d \ln…