Lichen Zhang's Homepage

Short Bio

I'm a 3rd-year Ph.D candidate at MIT Mathematics and I'm very fortunate to be advised by Professor Jon Kelner. I obtained my Bachelor and Master in Computer Science at Carnegie Mellon University, advised by Professor Gary Miller. My research interests lie at the intersection of theoretical computer science and machine learning, with a specific focus on developing efficient algorithms. I'm particularly excited about problems in optimization, sketching, and differential privacy. Additionally, I am dedicated to enhancing the efficiency of training processes in large-scale machine learning systems.

Publications (Author names in alphabetical order)

• Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (arxiv link).
  Yuzhou Gu, Nikki Lijing Kuang, Yi-An Ma, Zhao Song and Lichen Zhang.
  NeurIPS, 2024.
• Solving Attention Kernel Regression Problem via Pre-conditioner (arxiv link).
  Zhao Song, Junze Yin and Lichen Zhang.
  AISTATS, 2024.
• Fast Dynamic Sampling for Determinantal Point Processes (link).
  Zhao Song, Junze Yin, Lichen Zhang and Ruizhe Zhang.
  AISTATS, 2024.
• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (arxiv link).
  Yuzhou Gu, Zhao Song, Junze Yin and Lichen Zhang.
  ICLR, 2024.
• Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time (arxiv link, long talk).
  Zhao Song, Lichen Zhang and Ruizhe Zhang.
  ITCS, 2024.
• Convex Minimization with Integer Minima in ~O(n^4) Time (arxiv link, long talk).
  Haotian Jiang, Yin Tat Lee, Zhao Song and Lichen Zhang.
  SODA, 2024.
• Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance (arxiv link, short talk).
  Zhao Song, Xin Yang, Yuanyuan Yang and Lichen Zhang.
  ICML, 2023.
• Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability (arxiv link, short talk).
  Zhao Song, Yitan Wang, Zheng Yu and Lichen Zhang.
  ICML, 2023.
• A Nearly-Optimal Bound for Fast Regression with \ell_\infty Guarantee.
  Zhao Song, Mingquan Ye, Junze Yin and Lichen Zhang.
  ICML, 2023.
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching (arxiv link).
  S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang and Tianyi Zhou.
  ICALP, 2023.
• An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization (link).
  Lianke Qin, Zhao Song, Lichen Zhang and Danyang Zhuo.
  AISTATS, 2023.
• Dynamic Tensor Product Regression (arxiv link).
  Aravind Reddy, Zhao Song and Lichen Zhang.
  NeurIPS, 2022.
• Fast Sketching of Polynomial Kernels of Polynomial Degree (arxiv link).
  Zhao Song, David P. Woodruff, Zheng Yu and Lichen Zhang.
  ICML, 2021.

Manuscripts

• Faster Algorithms for Structured Linear and Kernel Support Vector Machines (arxiv link).
  Yuzhou Gu, Zhao Song and Lichen Zhang.
• Speeding Up Sparsification using Inner Product Search Data Structures (arxiv link).
  Zhao Song, Zhaozhuo Xu and Lichen Zhang.
• Faster Algorithm for One-Sided Kadison-Singer via Furthest-Neighbor Search (pdf).
  Zhao Song, Zhaozhuo Xu and Lichen Zhang.

Master Thesis

• Speeding Up Optimizations via Data Structures: Faster Search, Sample and Maintenance (link).