Chi-Ning Chou

ICML Conference 2025 Conference Paper

Feature Learning beyond the Lazy-Rich Dichotomy: Insights from Representational Geometry

• Chi-Ning Chou
• Hang Le 0005
• Yichen Wang
• SueYeon Chung

Integrating task-relevant information into neural representations is a fundamental ability of both biological and artificial intelligence systems. Recent theories have categorized learning into two regimes: the rich regime, where neural networks actively learn task-relevant features, and the lazy regime, where networks behave like random feature models. Yet this simple lazy–rich dichotomy overlooks a diverse underlying taxonomy of feature learning, shaped by differences in learning algorithms, network architectures, and data properties. To address this gap, we introduce an analysis framework to study feature learning via the geometry of neural representations. Rather than inspecting individual learned features, we characterize how task-relevant representational manifolds evolve throughout the learning process. We show, in both theoretical and empirical settings, that as networks learn features, task-relevant manifolds untangle, with changes in manifold geometry revealing distinct learning stages and strategies beyond the lazy–rich dichotomy. This framework provides novel insights into feature learning across neuroscience and machine learning, shedding light on structural inductive biases in neural circuits and the mechanisms underlying out-of-distribution generalization.

STOC Conference 2022 Conference Paper

Linear space streaming lower bounds for approximating CSPs

• Chi-Ning Chou
• Alexander Golovnev
• Madhu Sudan 0001
• Ameya Velingker
• Santhoshini Velusamy

FOCS Conference 2021 Conference Paper

Approximability of all finite CSPs with linear sketches

• Chi-Ning Chou
• Alexander Golovnev
• Madhu Sudan 0001
• Santhoshini Velusamy

A constraint satisfaction problem (CSP), $\text{Max}-\text{CSP}(\mathcal{F})$, is specified by a finite set of constraints $\mathcal{F}\subseteq\{[q]^{k}\rightarrow\{0, 1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from $\mathcal{F}$ to subsequences of the $n$ variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the ( $\gamma, \beta$ )-approximation version of the problem, for parameters $0\leq\beta < \gamma\leq 1$, the goal is to distinguish instances where at least $\gamma$ fraction of the constraints can be satisfied from instances where at most $\beta$ fraction of the constraints can be satisfied. In this work we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family $\mathcal{F}$ and every $\beta < \gamma$, we show that either a linear sketching algorithm solves the problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in $o(\sqrt{n})$ space. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of $q=k=2$ where we get a dichotomy and the case when the satisfying assignments of $f$ support a distribution on $[q]^{k}$ with uniform marginals. Prior to this work, other than sporadic examples, the only systematic class of CSPs that were analyzed considered the setting of Boolean variables $q=2$, binary constraints $k=2$, singleton families $\vert \mathcal{F}\vert =1$ and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [2] and [3], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [4], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i. e. , with negations). Our techniques surprisingly allow us to get to general $q$ -ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes.

FOCS Conference 2020 Conference Paper

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat

• Chi-Ning Chou
• Alexander Golovnev
• Santhoshini Velusamy

We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant α, s. t. for any (i) there is an ( α-ε)-streaming approximation using space O(logn); and (ii) any ( α+ε)-streaming approximation requires space Ω(√n). This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was 1/2. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DICUT problem, there was a gap between an upper bound of 1/2 and a lower bound of 2/5 [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DICUT is 4/9. We also establish that the tight approximation for Max-2SAT is √2/2, and for Exact Max-2SAT it is 3/4. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for Max-kSAT is √2/2 for every k ≥ 2.

NeurIPS Conference 2019 Conference Paper

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

• Boaz Barak
• Chi-Ning Chou
• Zhixian Lei
• Tselil Schramm
• Yueqi Sheng

We consider the graph matching/similarity problem of determining how similar two given graphs $G_0, G_1$ are and recovering the permutation $\pi$ on the vertices of $G_1$ that minimizes the symmetric difference between the edges of $G_0$ and $\pi(G_1)$. Graph matching/similarity has applications for pattern matching, vision, social network anonymization, malware analysis, and more. We give the first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give a polynomial time algorithm for the graph similarity/hypothesis testing task which works for every constant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial ($n^{O(\log n)}$ time) algorithm for the graph matching task of recovering the permutation minimizing the symmetric difference in this model. This is the first algorithm to do so without requiring as additional input a ``seed'' of the values of the ground truth permutation on at least $n^{\Omega(1)}$ vertices. Our algorithms follow a general framework of counting the occurrences of subgraphs from a particular family of graphs allowing for tradeoffs between efficiency and accuracy.