170 citations · 909 across the 66 of their papers we have counts for
16 papers · 1 filter
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…
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,…
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 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…
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…
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…
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-…
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…
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…
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…
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…
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…
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:…
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…
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…
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…