7 papers
Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation
Shihong Ding, Fangyu Du, Cong Fang
Multi-task learning (MTL) has emerged as a pivotal paradigm in machine learning by leveraging shared structures across multiple related tasks. Despite its empirical success, the de…
Mild Over-Parameterization Benefits Asymmetric Tensor PCA
Shihong Ding, Weicheng Lin, Cong Fang
Asymmetric Tensor PCA (ATPCA) is a prototypical model for studying the trade-offs between sample complexity, computation, and memory. Existing algorithms for this problem typically…
Accelerating Single-Pass SGD for Generalized Linear Prediction
Qian Chen, Shihong Ding, Cong Fang
We study generalized linear prediction under a streaming setting, where each iteration uses only one fresh data point for a gradient-level update. While momentum is well-establishe…
Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization
Shihong Ding, Yihong Gu, Yuanshi Liu +1
We study the Order- () spiked tensor model for the tensor principal component analysis (PCA) problem: given i.i.d. observations of a -th order tensor generated…
Scaling Law for Stochastic Gradient Descent in Quadratically Parameterized Linear Regression
Shihong Ding, Haihan Zhang, Hanzhen Zhao +1
In machine learning, the scaling law describes how the model performance improves with the model and data size scaling up. From a learning theory perspective, this class of results…
PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium
Shihong Ding, Hanze Dong, Cong Fang +2
We consider the non-convex non-concave objective function in two-player zero-sum continuous games. The existence of pure Nash equilibrium requires stringent conditions, posing a ma…