BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Peilin Zhong

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Machine LearningData Structures and AlgorithmsComputational ComplexityArtificial IntelligenceNumerical Analysis

Catalog footprint

Research overview

9works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

9 publications

preprint2025arXiv

MS-SSM: A Multi-Scale State Space Model for Efficient Sequence Modeling

State-space models (SSMs) have recently attention as an efficient alternative to computationally expensive attention-based models for sequence modeling. They rely on linear recurrences to integrate information over time, enabling fast inference, parallelizable training, and control over recurrence stability. However, traditional SSMs often suffer from limited effective memory, requiring larger state sizes for improved recall. Moreover, existing SSMs struggle to capture multi-scale dependencies, which are essential for modeling complex structures in time series, images, and natural language. This paper introduces a multi-scale SSM framework that addresses these limitations by representing sequence dynamics across multiple resolution and processing each resolution with specialized state-space dynamics. By capturing both fine-grained, high-frequency patterns and coarse, global trends, MS-SSM enhances memory efficiency and long-range modeling. We further introduce an input-dependent scale-mixer, enabling dynamic information fusion across resolutions. The proposed approach significantly improves sequence modeling, particularly in long-range and hierarchical tasks, while maintaining computational efficiency. Extensive experiments on benchmarks, including Long Range Arena, hierarchical reasoning, time series classification, and image recognition, demonstrate that MS-SSM consistently outperforms prior SSM-based models, highlighting the benefits of multi-resolution processing in state-space architectures.

Open access
preprint2025arXiv

Nested Learning: The Illusion of Deep Learning Architectures

Despite the recent progresses, particularly in developing Language Models, there are fundamental challenges and unanswered questions about how such models can continually learn/memorize, self-improve, and find effective solutions. In this paper, we present a new learning paradigm, called Nested Learning (NL), that coherently represents a machine learning model with a set of nested, multi-level, and/or parallel optimization problems, each of which with its own context flow. Through the lenses of NL, existing deep learning methods learns from data through compressing their own context flow, and in-context learning naturally emerges in large models. NL suggests a philosophy to design more expressive learning algorithms with more levels, resulting in higher-order in-context learning and potentially unlocking effective continual learning capabilities. We advocate for NL by presenting three core contributions: (1) Expressive Optimizers: We show that known gradient-based optimizers, such as Adam, SGD with Momentum, etc., are in fact associative memory modules that aim to compress the gradients' information (by gradient descent). Building on this insight, we present other more expressive optimizers with deep memory and/or more powerful learning rules; (2) Self-Modifying Learning Module: Taking advantage of NL's insights on learning algorithms, we present a sequence model that learns how to modify itself by learning its own update algorithm; and (3) Continuum Memory System: We present a new formulation for memory system that generalizes the traditional viewpoint of long/short-term memory. Combining our self-modifying sequence model with the continuum memory system, we present a continual learning module, called Hope, showing promising results in language modeling, knowledge incorporation, and few-shot generalization tasks, continual learning, and long-context reasoning tasks.

Open access
preprint2023arXiv

Differentially Private Continual Releases of Streaming Frequency Moment Estimations

The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quantities (usually data statistics) while making a single pass through the stream and using as little space as possible. Motivated by the importance of data privacy, we develop differentially private streaming algorithms under the continual release setting, where the union of outputs of the algorithm at every timestamp must be differentially private. Specifically, we study the fundamental ℓp\ell_p (p∈[0,+∞))(p\in [0,+\infty)) frequency moment estimation problem under this setting, and give an ε\varepsilon-DP algorithm that achieves (1+η)(1+η)-relative approximation (∀η∈(0,1))(\forall η\in(0,1)) with polylog⁡(Tn)\mathrm{poly}\log(Tn) additive error and uses polylog⁡(Tn)⋅max⁡(1,n1−2/p)\mathrm{poly}\log(Tn)\cdot \max(1, n^{1-2/p}) space, where TT is the length of the stream and nn is the size of the universe of elements. Our space is near optimal up to poly-logarithmic factors even in the non-private setting. To obtain our results, we first reduce several primitives under the differentially private continual release model, such as counting distinct elements, heavy hitters and counting low frequency elements, to the simpler, counting/summing problems in the same setting. Based on these primitives, we develop a differentially private continual release level set estimation approach to address the ℓp\ell_p frequency moment estimation problem. We also provide a simple extension of our results to the harder sliding window model, where the statistics must be maintained over the past WW data items.

Open access
preprint2023arXiv

Stars: Tera-Scale Graph Building for Clustering and Graph Learning

A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, classification, graph learning, and nearest neighbor search. For these tasks, it is critical to build graphs which are sparse yet still representative of the underlying data. The benefits of sparsity are twofold: firstly, constructing dense graphs is infeasible in practice for large datasets, and secondly, the runtime of downstream tasks is directly influenced by the sparsity of the similarity graph. In this work, we present Stars\textit{Stars}: a highly scalable method for building extremely sparse graphs via two-hop spanners, which are graphs where similar points are connected by a path of length at most two. Stars can construct two-hop spanners with significantly fewer similarity comparisons, which are a major bottleneck for learning based models where comparisons are expensive to evaluate. Theoretically, we demonstrate that Stars builds a graph in nearly-linear time, where approximate nearest neighbors are contained within two-hop neighborhoods. In practice, we have deployed Stars for multiple data sets allowing for graph building at the Tera-Scale\textit{Tera-Scale}, i.e., for graphs with tens of trillions of edges. We evaluate the performance of Stars for clustering and graph learning, and demonstrate 10~1000-fold improvements in pairwise similarity comparisons compared to different baselines, and 2~10-fold improvement in running time without quality loss.

Open access
preprint2020arXiv

Average Case Column Subset Selection for Entrywise ℓ1\ell_1-Norm Loss

We study the column subset selection problem with respect to the entrywise ℓ1\ell_1-norm loss. It is known that in the worst case, to obtain a good rank-kk approximation to a matrix, one needs an arbitrarily large nΩ(1)n^{Ω(1)} number of columns to obtain a (1+ε)(1+ε)-approximation to the best entrywise ℓ1\ell_1-norm low rank approximation of an n×nn \times n matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a (1+ε)(1+ε)-approximation with a nearly linear running time and poly(k/ε)+O(klog⁡n)(k/ε)+O(k\log n) columns. Namely, we show that if the input matrix AA has the form A=B+EA = B + E, where BB is an arbitrary rank-kk matrix, and EE is a matrix with i.i.d. entries drawn from any distribution μμ for which the (1+γ)(1+γ)-th moment exists, for an arbitrarily small constant γ>0γ> 0, then it is possible to obtain a (1+ε)(1+ε)-approximate column subset selection to the entrywise ℓ1\ell_1-norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a (1+ε)(1+ε)-approximate subset selection algorithm even if one chooses any no(1)n^{o(1)} columns. This is the first algorithm of any kind for achieving a (1+ε)(1+ε)-approximation for entrywise ℓ1\ell_1-norm loss low rank approximation.

Open access
preprint2020arXiv

Low Rank Approximation with Entrywise ℓ1\ell_1-Norm Error

We study the ℓ1\ell_1-low rank approximation problem, where for a given n×dn \times d matrix AA and approximation factor α≥1α\geq 1, the goal is to output a rank-kk matrix A^\widehat{A} for which ∥A−A^∥1≤α⋅min⁡rank-k matrices A′∥A−A′∥1,\|A-\widehat{A}\|_1 \leq α\cdot \min_{\textrm{rank-}k\textrm{ matrices}~A'}\|A-A'\|_1, where for an n×dn \times d matrix CC, we let ∥C∥1=∑i=1n∑j=1d∣Ci,j∣\|C\|_1 = \sum_{i=1}^n \sum_{j=1}^d |C_{i,j}|. This error measure is known to be more robust than the Frobenius norm in the presence of outliers and is indicated in models where Gaussian assumptions on the noise may not apply. The problem was shown to be NP-hard by Gillis and Vavasis and a number of heuristics have been proposed. It was asked in multiple places if there are any approximation algorithms. We give the first provable approximation algorithms for ℓ1\ell_1-low rank approximation, showing that it is possible to achieve approximation factor α=(log⁡d)⋅poly(k)α= (\log d) \cdot \mathrm{poly}(k) in nnz(A)+(n+d)poly(k)\mathrm{nnz}(A) + (n+d) \mathrm{poly}(k) time, where nnz(A)\mathrm{nnz}(A) denotes the number of non-zero entries of AA. If kk is constant, we further improve the approximation ratio to O(1)O(1) with a poly(nd)\mathrm{poly}(nd)-time algorithm. Under the Exponential Time Hypothesis, we show there is no poly(nd)\mathrm{poly}(nd)-time algorithm achieving a (1+1log⁡1+γ(nd))(1+\frac{1}{\log^{1+γ}(nd)})-approximation, for γ>0γ> 0 an arbitrarily small constant, even when k=1k = 1. We give a number of additional results for ℓ1\ell_1-low rank approximation: nearly tight upper and lower bounds for column subset selection, CUR decompositions, extensions to low rank approximation with respect to ℓp\ell_p-norms for 1≤p<21 \leq p < 2 and earthmover distance, low-communication distributed protocols and low-memory streaming algorithms, algorithms with limited randomness, and bicriteria algorithms. We also give a preliminary empirical evaluation.

Open access
preprint2020arXiv

Towards a Zero-One Law for Column Subset Selection

There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank-kk matrix BB minimizing the sum of absolute values of differences to a given nn-by-nn matrix AA, min⁡rank-k B∥A−B∥1\min_{\textrm{rank-}k~B}\|A-B\|_1, or more generally finding a rank-kk matrix BB which minimizes the sum of pp-th powers of absolute values of differences, min⁡rank-k B∥A−B∥pp\min_{\textrm{rank-}k~B}\|A-B\|_p^p. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of poly(klog⁡n)\mathrm{poly}(k \log n) columns whose cost is no more than a poly(k)\mathrm{poly}(k) factor larger than the cost of the best rank-kk matrix. The above error measures are special cases of the following general entrywise low rank approximation problem: given an arbitrary function g:R→R≥0g:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}, find a rank-kk matrix BB which minimizes ∥A−B∥g=∑i,jg(Ai,j−Bi,j)\|A-B\|_g = \sum_{i,j}g(A_{i,j}-B_{i,j}). A natural question is which functions gg admit efficient approximation algorithms? Indeed, this is a central question of recent work studying generalized low rank models. In this work we give approximation algorithms for every\textit{every} function gg which is approximately monotone and satisfies an approximate triangle inequality, and we show both of these conditions are necessary. Further, our algorithm is efficient if the function gg admits an efficient approximate regression algorithm. Our approximation algorithms handle functions which are not even scale-invariant, such as the Huber loss function, which we show have very different structural properties than ℓp\ell_p-norms, e.g., one can show the lack of scale-invariance causes any column subset selection algorithm to provably require a log⁡n\sqrt{\log n} factor larger number of columns than ℓp\ell_p-norms; nevertheless we design the first efficient column subset selection algorithms for such error measures.

Open access
preprint2016arXiv

Distributed Low Rank Approximation of Implicit Functions of a Matrix

We study distributed low rank approximation in which the matrix to be approximated is only implicitly represented across the different servers. For example, each of ss servers may have an n×dn \times d matrix AtA^t, and we may be interested in computing a low rank approximation to A=f(∑t=1sAt)A = f(\sum_{t=1}^s A^t), where ff is a function which is applied entrywise to the matrix ∑t=1sAt\sum_{t=1}^s A^t. We show for a wide class of functions ff it is possible to efficiently compute a d×dd \times d rank-kk projection matrix PP for which ∥A−AP∥F2≤∥A−[A]k∥F2+ε∥A∥F2\|A - AP\|_F^2 \leq \|A - [A]_k\|_F^2 + \varepsilon \|A\|_F^2, where APAP denotes the projection of AA onto the row span of PP, and [A]k[A]_k denotes the best rank-kk approximation to AA given by the singular value decomposition. The communication cost of our protocols is d⋅(sk/ε)O(1)d \cdot (sk/\varepsilon)^{O(1)}, and they succeed with high probability. Our framework allows us to efficiently compute a low rank approximation to an entry-wise softmax, to a Gaussian kernel expansion, and to MM-Estimators applied entrywise (i.e., forms of robust low rank approximation). We also show that our additive error approximation is best possible, in the sense that any protocol achieving relative error for these problems requires significantly more communication. Finally, we experimentally validate our algorithms on real datasets.

Open access
preprint2016arXiv

Optimal Principal Component Analysis in Distributed and Streaming Models

We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix A∈Rm×n,A \in R^{m \times n}, a rank parameter k<rank(A)k < rank(A), and an accuracy parameter 0<ε<10 < ε< 1, we want to output an m×km \times k orthonormal matrix UU for which ∣∣A−UUTA∣∣F2≤(1+ε)⋅∣∣A−Ak∣∣F2, || A - U U^T A ||_F^2 \le \left(1 + ε\right) \cdot || A - A_k||_F^2, where Ak∈Rm×nA_k \in R^{m \times n} is the best rank-kk approximation to AA. This paper provides improved algorithms for distributed PCA and streaming PCA.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.