Author name cluster

Honghao Lin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

STOC Conference 2025 Conference Paper

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness

Elena Gribelyuk
Honghao Lin
David P. Woodruff
Huacheng Yu
Samson Zhou

We introduce a novel technique for “lifting” dimension lower bounds for linear sketches in the real-valued setting to dimension lower bounds for linear sketches with polynomially-bounded integer entries when the input is a polynomially-bounded integer vector. Using this technique, we obtain the first optimal sketching lower bounds for discrete inputs in a data stream, for classical problems such as approximating the frequency moments, estimating the operator norm, and compressed sensing. Additionally, we lift the adaptive attack of Hardt and Woodruff (STOC, 2013) for breaking any real-valued linear sketch via a sequence of real-valued queries, and show how to obtain an attack on any integer-valued linear sketch using integer-valued queries. This shows that there is no linear sketch in a data stream with insertions and deletions that is adversarially robust for approximating any L p norm of the input, resolving a central open question for adversarially robust streaming algorithms. To do so, we introduce a new pre-processing technique of independent interest which, given an integer-valued linear sketch, increases the dimension of the sketch by only a constant factor in order to make the orthogonal lattice to its row span smooth. This pre-processing then enables us to leverage results in lattice theory on discrete Gaussian distributions and reason that efficient discrete sketches imply efficient continuous sketches. Our work resolves open questions from the Banff ’14 and ’17 workshops on Communication Complexity and Applications, as well as the STOC ’21 and FOCS ’23 workshops on adaptivity and robustness.

Details

NeurIPS Conference 2025 Conference Paper

Nearly-Linear Time and Massively Parallel Algorithms for $k$-anonymity

Kevin Aydin
Honghao Lin
David Woodruff
Peilin Zhong

$k$-anonymity is a widely-used privacy-preserving concept that ensures each record in a dataset is indistinguishable from at least $k-1$ other records. In this paper, we revisit $k$-anonymity by suppression and give an $O(k)$-approximation algorithm with a nearly-linear runtime of $\tilde{O}(nd + n^{1+1/C^2}/k^{1/C^2})$ for an arbitrary constant $C$, where $n$ is the number of records and $d$ is the number of attributes. Previous algorithms with provable guarantees either (1) achieve the same $O(k)$ approximation ratio but require at least $O(n^2 k)$ runtime, or (2) provide a better $O(\log k)$ approximation ratio at the cost of an impractical $O(n^{2k})$ worst-case runtime for general $d$ and $k$. Our algorithm extends to the Massively Parallel Computation (MPC) model, where it can be adapted into an MPC algorithm requiring $\tilde{O}(\log^{1+\epsilon} n)$ rounds and total space $O(n^{1+1/C^2}(d+k))$. Empirically, we also demonstrate that our algorithmic ideas can be adapted to existing heuristic methods, leading to significant speed-ups while preserving comparable performance. Although~\citep{PS07} introduced improvements to achieve more practical runtimes for their $O(\log k)$-approximation algorithm, its worst-case runtime remains $O(n^{2k})$. A natural question arises: can we develop an algorithm with an $o(k)$ approximation ratio and a polynomial runtime? We investigate the single-point $k$-anonymity problem, where the goal is to select $k-1$ additional records to make a given record indistinguishable. Surprisingly, assuming the dense vs random conjecture in complexity theory, we show that for $n = k^c$, no algorithm can achieve a $k^{1 - O(1/c)}$ approximation in $\mathrm{poly}(k)$ time. This provides evidence of the inherent hardness of the $k$-anonymity problem.

PDF Details

FOCS Conference 2024 Conference Paper

A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches

Elena Gribelyuk
Honghao Lin
David P. Woodruff
Huacheng Yu
Samson Zhou

The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions which is fixed in advance. However, many real-world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied $\ell_{0}$ -estimation problem over turnstile, integer streams. For any linear streaming algorithm $\mathcal{A}$ which uses sketching matrix $\mathbf{A}\varepsilon \mathbb{Z}^{r\times n}$, this attack makes $\tilde{\mathcal{O}}(r^{8})$ queries and succeeds with high constant probability in breaking the sketch. Additionally, we give an adaptive attack against linear sketches for the $\ell_{0}$ -estimation problem over finite fields $\mathbb{F}_{p}$, which requires a smaller number of $\tilde{\mathcal{O}}(r^{3})$ queries. Finally, we provide an adaptive attack over $\mathbb{R}^{n}$ against linear sketches A $\in \mathbb{R}^{r\times \mathfrak{n}}$ for $\ell_{0}$ -estimation, in the setting where A has all nonzero subdeterminants at least $\frac{1}{\text{poly}(r)}$. Our results provide an exponential improvement over the previous number of queries known to break an $\ell_{0}$ -estimation sketch.

Details

NeurIPS Conference 2024 Conference Paper

Even Sparser Graph Transformers

Hamed Shirzad
Honghao Lin
Balaji Venkatachalam
Ameya Velingker
David P. Woodruff
Danica J. Sutherland

Graph Transformers excel in long-range dependency modeling, but generally require quadratic memory complexity in the number of nodes in an input graph, and hence have trouble scaling to large graphs. Sparse attention variants such as Exphormer can help, but may require high-degree augmentations to the input graph for good performance, and do not attempt to sparsify an already-dense input graph. As the learned attention mechanisms tend to use few of these edges, however, such high-degree connections may be unnecessary. We show (empirically and with theoretical backing) that attention scores on graphs are usually quite consistent across network widths, and use this observation to propose a two-stage procedure, which we call Spexphormer: first, train a narrow network on the full augmented graph. Next, use only the active connections to train a wider network on a much sparser graph. We establish theoretical conditions when a narrow network's attention scores can match those of a wide network, and show that Spexphormer achieves good performance with drastically reduced memory requirements on various graph datasets.

PDF Details DOI

ICLR Conference 2024 Conference Paper

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms

Yi Li 0002
Honghao Lin
David P. Woodruff

We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more expensive low-rank approximation computation will be. The matrix case concerns the Frobenius norm and the task is to approximate the $k$-residual $\|A - A_k\|_F$ of the input matrix $A$ within a $(1+\epsilon)$-factor, where $A_k$ is the optimal rank-$k$ approximation. We provide a tight bound of $\Theta(k^2/\epsilon^4)$ on the size of bilinear sketches, which have the form of a matrix product $SAT$. This improves the previous $O(k^2/\epsilon^6)$ upper bound in (Andoni et al. SODA 2013) and gives the first non-trivial lower bound, to the best of our knowledge. In our algorithm, our sketching matrices $S$ and $T$ can both be sparse matrices, allowing for a very fast update time. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. For the vector case, we consider the $\ell_p$-norm for $p>2$, where the task is to approximate the $k$-residual $\|x - x_k\|_p$ up to a constant factor, where $x_k$ is the optimal $k$-sparse approximation to $x$. Such vector norms are frequently studied in the data stream literature and are useful for finding frequent items or so-called heavy hitters. We establish an upper bound of $O(k^{2/p}n^{1-2/p}\operatorname{poly}(\log n))$ for constant $\epsilon$ on the dimension of a linear sketch for this problem. Our algorithm can be extended to the $\ell_p$ sparse recovery problem with the same sketching dimension, which seems to be the first such bound for $p > 2$. We also show an $\Omega(k^{2/p}n^{1-2/p})$ lower bound for the sparse recovery problem, which is tight up to a $\mathrm{poly}(\log n)$ factor.

Details

ICLR Conference 2023 Conference Paper

Learning the Positions in CountSketch

Yi Li 0002
Honghao Lin
Simin Liu
Ali Vakilian
David P. Woodruff

We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g., low-rank approximation and regression. In the learning-based sketching paradigm proposed by Indyk et al., the sketch matrix is found by choosing a random sparse matrix, e.g., CountSketch, and then the values of its non-zero entries are updated by running gradient descent on a training data set. Despite the growing body of work on this paradigm, a noticeable omission is that the locations of the non-zero entries of previous algorithms were fixed, and only their values were learned. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries. Our first proposed algorithm is based on a greedy algorithm. However, one drawback of the greedy algorithm is its slower training time. We fix this issue and propose approaches for learning a sketching matrix for both low-rank approximation and Hessian approximation for second-order optimization. The latter is helpful for a range of constrained optimization problems, such as LASSO and matrix estimation with a nuclear norm constraint. Both approaches achieve good accuracy with a fast running time. Moreover, our experiments suggest that our algorithm can still reduce the error significantly even if we only have a very limited number of training matrices.

Details

SODA Conference 2023 Conference Paper

The ℓ p -Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

Yi Li 0002
Honghao Lin
David P. Woodruff

In the ℓ p -subspace sketch problem, we are given an n × d matrix A with n > d, and asked to build a small memory data structure Q ( A, ε ) so that, for any query vector x ∈ ℝ d, we can output a number in given only Q(A, ε ). This problem is known to require bits of memory for d = Ω(log (1/ε)). However, for d = o (log(l/ε)), no data structure lower bounds were known. Small constant values of d are particularly important for estimating point queries for support vector machines (SVMs) in a stream (Andoni et al. 2020), where only tight bounds for d = 1 were known. We resolve the memory required to solve the ℓ p -subspace sketch problem for any constant d and integer p, showing that it is bits and words, where the Õ(·) notation hides poly(log(1/ε)) factors. This shows that one can beat the Ω(ε -2 ) lower bound, which holds for d = Ω(log(1/ε)), for any constant d. Further, we show how to implement the upper bound in a single pass stream, with an additional multiplicative poly(log log n) factor and an additive poly(log n ) cost in the memory. Our bounds extend to loss functions other than the ℓ p -norm, and notably they apply to point queries for SVMs with additive error, where we show an optimal bound of for every constant d. This is a near-quadratic improvement over the lower bound of Andoni et al. Further, previous upper bounds for SVM point query were noticeably lacking: for d =1 the bound was Õ(e -1/2 ) and for d = 2 the bound was Õ (ε -4//5 ), but all existing techniques failed to give any upper bound better than Õ (ε -2 ) for any other value of d. Our techniques, which rely on a novel connection to low dimensional techniques from geometric functional analysis, completely close this gap.

Details

ICML Conference 2022 Conference Paper

Learning Augmented Binary Search Trees

Honghao Lin
Tian Luo
David P. Woodruff

A treap is a classic randomized binary search tree data structure that is easy to implement and supports O(log n) expected time access. However, classic treaps do not take advantage of the input distribution or patterns in the input. Given recent advances in algorithms with predictions, we propose pairing treaps with machine advice to form a learning-augmented treap. We are the first to propose a learning-augmented data structure that supports binary search tree operations such as range-query and successor functionalities. With the assumption that we have access to advice from a frequency estimation oracle, we assign learned priorities to the nodes to better improve the treap’s structure. We theoretically analyze the learning-augmented treap’s performance under various input distributions and show that under those circumstances, our learning-augmented treap has stronger guarantees than classic treaps and other classic tree-based data structures. Further, we experimentally evaluate our learned treap on synthetic datasets and demonstrate a performance advantage over other search tree data structures. We also present experiments on real world datasets with known frequency estimation oracles and show improvements as well.

Details

ICML Conference 2022 Conference Paper

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

Nadiia Chepurko
Kenneth L. Clarkson
Lior Horesh
Honghao Lin
David P. Woodruff

We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise; these are powerful and standard techniques in randomized numerical linear algebra. With this recognition, we are able to employ the large body of work in numerical linear algebra to obtain algorithms for these problems that are simpler or faster (or both) than existing approaches. Our experiments demonstrate that the proposed data structures also work well on real-world datasets.

Details

ICLR Conference 2022 Conference Paper

Triangle and Four Cycle Counting with Predictions in Graph Streams

Justin Y. Chen
Talya Eden
Piotr Indyk
Honghao Lin
Shyam Narayanan
Ronitt Rubinfeld
Sandeep Silwal
Tal Wagner

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior “classical” algorithms that did not use oracles. In this paper, we explore the power of a “heavy edge” oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on “classical” streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.

Details

ICLR Conference 2021 Conference Paper

Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

Yu Cheng 0002
Honghao Lin

We study the problem of learning Bayesian networks where an $\epsilon$-fraction of the samples are adversarially corrupted. We focus on the fully-observable case where the underlying graph structure is known. In this work, we present the first nearly-linear time algorithm for this problem with a dimension-independent error guarantee. Previous robust algorithms with comparable error guarantees are slower by at least a factor of $(d/\epsilon)$, where $d$ is the number of variables in the Bayesian network and $\epsilon$ is the fraction of corrupted samples. Our algorithm and analysis are considerably simpler than those in previous work. We achieve this by establishing a direct connection between robust learning of Bayesian networks and robust mean estimation. As a subroutine in our algorithm, we develop a robust mean estimation algorithm whose runtime is nearly-linear in the number of nonzeros in the input samples, which may be of independent interest.

Details

ICLR Conference 2020 Conference Paper

Learning-Augmented Data Stream Algorithms

Tanqiu Jiang
Yi Li 0002
Honghao Lin
Yisong Ruan
David P. Woodruff

The data stream model is a fundamental model for processing massive data sets with limited memory and fast processing time. Recently Hsu et al. (2019) incorporated machine learning techniques into the data stream model in order to learn relevant patterns in the input data. Such techniques were encapsulated by training an oracle to predict item frequencies in the streaming model. In this paper we explore the full power of such an oracle, showing that it can be applied to a wide array of problems in data streams, sometimes resulting in the first optimal bounds for such problems. Namely, we apply the oracle to counting distinct elements on the difference of streams, estimating frequency moments, estimating cascaded aggregates, and estimating moments of geometric data streams. For the distinct elements problem, we obtain the first memory-optimal algorithms. For estimating the $p$-th frequency moment for $0 < p < 2$ we obtain the first algorithms with optimal update time. For estimating the $p$-the frequency moment for $p > 2$ we obtain a quadratic saving in memory. We empirically validate our results, demonstrating also our improvements in practice.

Details