The Complexity of Learning Sparse Superposed Features with Feedback
Authors: Akash Kumar
Venue: ICML 2025 poster (2025)
Keywords: Feature Learning
Sparse Features
Superposition
Dictionary Learning
Learning with feedbacks
Linear Representation Hypothesis
Primary area: general_machine_learning->representation_learning
TL;DR: Feature learning using sparse activation feedbacks.

Abstract: The success of deep networks is crucially attributed to their ability to capture latent features within a representation space. In this work, we investigate whether the underlying learned features of a model can be efficiently retrieved through feedback from an agent, such as a large language model (LLM), in the form of relative triplet comparisons. These features may represent various constructs, including dictionaries in LLMs or components of a covariance matrix of Mahalanobis distances. We analyze the feedback complexity associated with learning a feature matrix in sparse settings. Our results establish tight bounds when the agent is permitted to construct activations and demonstrate strong upper bounds in sparse scenarios when the agent's feedback is limited to distributional information. We validate our theoretical findings through experiments on two distinct applications: feature recovery from Recursive Feature Machine-trained models and dictionary extraction from sparse autoencoders trained on Large Language Models.

The Complexity of Learning Sparse Superposed Features with Feedback
Akash Kumar
Abstract
multiple avenues for elucidating how transformer- based models, including Large Language Models (LLMs), acquire
The success of deep networks is crucially at- tributed to their ability to capture latent features within representation space. this work, we in- vestigate whether the underlying learned features of model can be efficiently retrieved through feedback from agent, such large language model (LLM), in the form of relative triplet com- parisons. These features may represent various constructs, including dictionaries in LLMs or a covariance matrix of Mahalanobis distances. We analyze the feedback complexity associated with learning feature matrix in sparse settings. Our results establish tight bounds when the agent is permitted to construct activations and demonstrate strong upper bounds in sparse scenarios when the agent's feedback is limited to distributional information. We validate our theoretical find- ings through experiments on two distinct appli- cations: feature recovery from Recursive Feature Machines and dictionary extraction from sparse autoencoders trained on Large Language Models.
and represent features (Bricken al.) 2023; Doshi Velez
and Kim 2017). These advances include uncovering neural circuits that encode specific concepts (Marks et al., 2024b
Olah et al. 2020), understanding feature composition across attention layers (Yang and Huj (021b), and revealing how models develop structured representations (Elhage et al.) 2022). One line of research posits that features are encoded linearly within the latent representation space through sparse activations, concept known as the linear representation hypothesis (LRH) (Mikolov et al. 2013 Arora et al.) 2016). However, this hypothesis faces challenges in explaining how neural networks function, as models often need to represent more distinct features than their layer dimensions would thcoretically allow under purely linear encoding. This phe- nomenon has been studied extensively in the context of large language models through the lens of superposition (EF hage et al. 2022). where multiple features share the same dimensional space in structured ways.
Recent efforts have addressed this challenge through sparse coding or dictionary learning, proposing that any layer of the model learns features linearly:
RJ De (xg(ar) + <<(x),
1. Introduction
where x E IRd, Dr E Rdxp is Peationaryymatriin or (x) RR sparse representation vector, and <<(x)) R represents error terms. This approach enables retrieval of interpretable features through sparse autoencoders (Bricken et al. 2023 Marks et al. 2024b), allowing for targeted monitoring and modification of network behavior. The linear feature decomposition not only advances model interpretation but also suggests the potential for developing compact, interpretable models that maintain performance by leveraging universal features from larger architectures.
In recent years, neural network- based models have achieved ofte-off-the-ar performance across wide array of tasks. These models effectively capture relevant features con- cepts from samples, tailored to the specific prediction tasks they address (Yang and Hu 2021b Bordelon and Pehlevan 2022a Ba et al. 2022b). A fundamental challenge lies in understanding how these models learn such features and determining whether these features can interpreted or even retrieved directly (Radhakrishnan al.) (024). Recent advancements in mechanistic interpretability have opened
In this work, we explore how complex features encoded dictionary
be distilled through feedback from ei- ther advanced language models (e.g., ChatGPT, Claude 3.0 Sonnet) or human agents. Let's define a dictionary D E Rdxp where each column represents an atomic feature vector. These atomic features, denoted as t1, U2,.... Up C Rd. could correspond to semantic concepts like "tree". "house", "lawn" that are relevant to the task's sample
'qqual contribution 'Department of Computer Science gineering, University of California, San Diego, USA. Correspon- dence to: Akash Kumar @uckk002uusd.eddu
Proceedings of the 4nnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
"could both overcomplete and undercomplete.

---

Learning Sparse Superposed Features with Feedback
space. The core mechanism involves an agent (either Al or human) determining whether different sparse combi- nations of these atomic features are similar or dissimilar. Specifically, given sparse activation vectors a' E Rº,
I.. We analyze the distributional setting with sampled activations, developing results for both general and sparse representations. For sparse sampling, we ex- tend the definition of Lebesgue measure to accom- modate sparsity constraints. (see Section 5
the agent evaluates whether linear combinations such as a1 (iv("tree") + a=z(""car") + +... + augu(" (""oueee""" are equiva- lent to other combinations using different activation vectors. Precisely, we formalize these feedback relationships using relative triplet comparisons (a, 5. <) E V, where V C R" is the activation or representation space. These comparisons express that a linear combination of features using coeffi- cients a is more similar to combination using coefficients 33 than to one using coefficients Ç.
III. We validate our theoretical bounds through experi- ments with feature matrices from Recursive Feature Machines and dictionaries trained for sparse autoen- coders in Large Language Models, including Pythia- 70M (Biderman et al. 2023) and Board Game mod- els (Karvonen et al. 2024). (see Section 6
Table summarizes our feedback complexity bounds.
The objective is to determine the extent to which an obliv- ious learner-one who learns solely by satisfying the con- straints of the feedback and randomly selecting valid fea- tures can identify the feature vectors of D up normal transformation. The fundamental protocol is as follows:
2. Related Work
Dictionary learning Recent work has explored dictionary
learning to disentangle the semanticity (mono- or polysemy)
of neural network activations (Faruqui et al. 2015 Arora
The agent either constructs or selects (from a sampled pool) sparse triplets of activations (a, () E 3v and designs relative feedback of similarity 8 E [+1,0, 0, -1} satisfying sgn (IID(a= B)]l - |ID(a ()I) L, and
ct al. 2018 Zhang et al. [2019] Yun et al. 2021). lp. Dictionary
learning (Mallat and Zhang 1993] Olshausen and Field 1997) (aka sparse coding) provides a systematic approach to decompose task-specific samples into sparse signals. The sample complexity of dictionary learning (or sparse coding) has been extensively studied as an optimization problem, typically involving non-convex objectives such as l regular- ization (see (Gribonval et al. 2015 While traditional meth- ods work directly with ground-truth samples, our approach differs fundamentally as the learner only receives feedback on sparse signals or activations. Prior work in noiseless settings has established probabilístic exact recovery up to linear transformations (permutations and sign changes) un- der mutual incoherence conditions (Gribonval and Schnass 2010 Agarwal et al. 2014). Our work extends these results by proving exact recovery (both deterministic and proba- bilistic) up to normal transformation, which generalizes to rotational and sign changes under strong incoherence prop- erties (see Lemma [ In the sampling regime, we analyze k-sparse signals, building upon the noisy setting framework developed in Arora et al. 2013): Gribonnal al. (2015).
provides them to the learner.
The learner solves for
{ {sgn (Iδ(a- 3311 (i((a-aaa - (C0)a =
and outputs solution D D.
Semantically, these relative distances provide the relative information on how ground truth samples, e.g. images, text among others, relate to each other. We term the normal transformation DD for given dictionary D as feature matrices T E Rexp, which is exactly a covariance matrix. Alternatively, for the representation space V C R?, this transformation defines a Mahalanobis distance function d: V x + R. characterized by the square symmetric linear transformation & z such that for any pair of activations (ir, v) V22 their distance is given by:
d(x, v) = (x - y) 4 x 1
When & embeds samples into R", it admits a decomposition xp, ① LLL for L E Rr* where serves as a dictionary for this distance function-at formulation well-studied in metric learning literature (Kulis) 2013). In this work, we study the minimal number of interactions, termed as feedback complexity of learning feature mations to a dictionary-of the form o e Sym_ (RPxP).
Feature learning in neural networks and Linear rep- resentation hypothesis Neural networks demonstrate a remarkable ability to discover and exploit task-specific fea- tures from data (Yang and Hu 2021b: Bordelon and Pehle- van 2022b Shi et al. 2022). Recent theoretical advances have significantly enhanced our understanding of feature evolution and emergence during training (Abbe et al. 2022
transfor-
We consider two types of feedback: general activations and sparse activations, examining both constructive and distri- butional settings. Our primary contributions are:
Ba al. 2022a Damian et al., 2022;) Yang and Hu] 2021a
Zhu al.) 2022 Particularly noteworthy is the finding that the outer product of model weights correlates with the gradient outer product of the classifier averaged over layer preactivations (Radhakrishnan et al.] 2024), which directly relates to the covariance matrices central to our investigation. Building upon these insights, Elhage et al.
I. We investigate feedback complexity in the construc- tive setting, where agents select activations from RR, establishing strong bounds for both general and sparse scenarios. (see Section 4
2

---

Learning Sparse Superposed Features with Feedback
Feedback type
Standard Constructive
Sparse Constructive
Standard Sampling
Sparse Sampling
Feedback Complexity
e ( + 1
0 ((PtD)
pipt
cp
2 log ? pd
2
Prior Works
SAE
CRAFT
Probing (Marks and Tegmark
2024
Sharkey et al. 2025) Fel et al. 2023)
LR
CCS (Burns et al. 2023)
L.DA O(np² + p²)
Learning Complexity
Tnpd
nipk
Tnp
Tnp
Table 1: Comparison of feedback complexity in this work against prior feature retrieval (learning) methods. T: number of iterations, n: number of samples, p: activation dimension, d: input space dimension, k: number of latent components, r: the rank of the feature matrix, > is a constant, and Ps depends on activation distribution and sparsity s. We use to denote "almost surely" and to denote "with high probability" guarantees.
(2022) proposed that features in large language models fol- low a linear encoding principle, suggesting that the com- plex feature representations learned during training can be decomposed into interpretable linear components. This in-
3. Problem Setup
We denote by V C IPP the space of activations or repre- sentations and by X' S Rd the space of samples. For the space of feature matrices (for a dictionary or Maha- lanobis distances), denoted as MMr we consider the family of symmetric positive semi-definite matrices in RPxP, i.c. MF ( E Sym, (IE*P)) We denote a feedback set as FF which consists of triplets (z, V, 2) E V with correspond- ing signs f E (+1,0,- -13.
terpretability, in turn, could facilitate the development of simplified algorithms for complex tasks (Fawzi et al.) 2022] Camera-PPaedees et al. 2024). Recent research has focused on extracting these interpretable features in the form of dic- tionary learning by training sparse autoencoder for various language models including Board Games Models (Marks et al. 2024b Bricken et al. 2023). Our work extends this line of inquiry by investigating whether such interpretable dictionaries can be effectively transferred to a weak learner using minimal comparative feedback.
We use the standard notations in linear algebra over a space of matrices provided in Appendix B
Triplet feedback An agent provides feedback on activa- tions in V through relative triplet comparisons (x, y, z) E V. Each comparison evaluates linear combinations of feature vectors:
Triplet learning covariance matrix Learning a feature matrix (for dictionary) up to normal transformation can be viewed through two established frameworks: covariance estimation (Chen et al. 2013] Li and Voroninski (2013) and learning Mahalanobis distances (Kulis) 2013). While these frameworks traditionally rely on exact or noisy mea- surements, our work introduces a distinct mechanism based solely on relative feedback, aligning more closely with the semantic structure of Mahalanobis distances. The study of such distances has been central to metric learning re- search (Bellet et al. 2015 Kulis 2013), encompassing both supervised approaches (Weinberger and Saul 2009 Xing et al. 2002) and unsupervised methods such as LDA (Fisher 1936) and PCA (Jolliffe] 1986). [Schulzz and Joachims (2003) and Kleindessner and von Luxburg (2016) have ex- tended this framework to incorporate relative comparisons on distances. Particularly relevant to our work are studies by Schultz and Joachims| (2003) and Mason et al. (2017) that employ triplet comparisons, though these typically as- sume i.i.d. triplets with potentially noisy measurements. Our approach differs by incorporating an active learning element: while signals are drawn i.i.d, an agent selectively provides feedback on informative instances. This construc- tive triplet framework for covariance estimation represents a novel direction, drawing inspiration from machine teaching, where a teaching agent provides carefully chosen examples to facilitate learning (Zhu et al. 2018 Kumar et al. 2021
aau ("featfe i") is more similar to
Σ Viuu i") than to z,u, ("featue i")
We study both sparse and non-sparse activation feedbacks, where sparsity is defined as:
Definition 1 (s-sparse activations). An activation a E R is s s-sparse if at most s many indices of a are non-zero.
Since triplet comparisons are invariant to positive scaling of feature matrices, we define:
Definition 2 (Feature equivalence). For a feature family MF. feature matrices a' and x. are equivalent if there exists X >>> 0 such that 4' = xp"
We study a learning framework where the learner merely satisfies the constraints provided by the agent's feedback: Definition 3 (Oblivious learner). A learner is oblivious if it randomly selects a feature matrix from the set of valid solutions to a given feedbuck set F, i.e., arbitrarily chooses + E MF,F),, where MF(F) represents the set of feature matrices satisfying the constraints in F.
This framework aligns with version space learning, where VS(F, denotes the set of feature matrices in MFFF) compatible with feedback set F.
3

---

Learning Sparse Superposed Features with Feedback
Ground Truth
Feodbach: Eygreecooaasttiin
Pendbackk Sparse Consbructive
Poedhack: Random Sampling
Feedback Sparse Samplin
0,03282972
Vak
Figure 1: Features via Recursive Feature Machines. We perform monomial regression on 2 ~ NO0 0.5 with target
f*(2) = 20 21 (2g > 0). An RFM kereel machine (2) = Σ EDDrrn & (3/. 2) is trained for 5 iterations on 4000 samples to produce the ground-truth feature matrix 4* of rank (Radhakrishhan et al. 2024). We then query an agent for feedback via: eigendecomposition (Theorem TT. sparse constructive (Theorem 2). random Gaussian sampling (Theorem (3). and sparse sampling with l 0.9 (Theorem 4). Eigendecomposition, sparse constructive, and random sampling achieve the ground-truth MSE with only 55 feedbacks, whereas high-sparsity sampling yields inferior features and larger MSE.
Prior work dictionary learning has established recov- ery up to linear transformation under weak mutual incoher- ence (Gribonval and Schnass 2010). In our setting, with the agent's 's feature feedback corresponding to D (or L) E Rd the learner recovers L Lup to normal transformation. More- over, when has orthogonal rows (strong incoherence), can recover L up rotation and sign changes as stated below, with proof deferred to Appendix D
Algorithm 1 Model of Feature learning with feedback
Given: Representation space IR,, Feature family MF
In batch setting:
Teacher picks triplets F(V, 4b)
{ {xr v) E V (x - v) T 45' (x -- 2 (x 4 (f'x z)}
Learner receives F, and obliviously picks feature matrix & MMp that satisfy the set of constraints in F(V, x*)
Lemma (Recovering orthogonal representations). Assume & E Sym, (RRXP). Define the set of orthogonal Cholesky decompositions of
Learner outputs +.
WcD {U E TRxx + = -U & SU-U- U= ='iag((N [...(d.................
Lemma 2. Let 45 E MF be a target feature matrix in representation space IRP used for oblivious learning. Given feedback set
where r = rank( and \1 ......., are the eigenval- ues of in descending order. Then, for any two matrices U,U U WcD. there exists an orthogonal matrix R E TR such that U' = UR, where R is block diagonal with orthog- onal blocks corresponding to any repeated diagonal entries A in U U. Additionally, each column of U' can differ from the corresponding column of U by a sign change.
F = 2) E R
(I yy) T
(x 2
(x T) 2)},
such that any &' E VS(F, MM) is feature equivalent to $0* there exists a pairwise feedback set
We note that the recovery of L is pertaining to the assump- tion that all the rows are orthogonal, and thus rank of L is r = d. In cases where r < d, one needs additional infor- mation in the form of ground sample æ La for some activation a to recover up to a linear transformation. Fi- nally, the interaction protocol is shown in Algorithm
F =
(1V'=z F'((''=>')
2p
T Φ/ = =z =T²
such that 4' E VS(FF,
Proof. WLOG, assume + for all (z, v. F. For any
triplet (I, 2) E F: Case (i): If (rr -)) x5 y)
(x-z) 40 - =). then (x y, v---2 -xx= satisfies the equality.
Case (ii): If (x - y) x (I y) > (x- 2) x' (x 2).
4. Sparse Feature Learning with Constructive Feedback
then for some >
(x- v) 4 (x - v) = (1 +1+ A) - =) 4xxx - z)
Here, we study the feedback complexity in the setting where agent is allowed to pick/construct any activation from IR.
implying (a y, /1 + A(x =)) satisfies the equality.
Thus, each triplet in maps to pair in F¹, preserving feature equivalence under positive scaling.
Reduction to Pairwise Comparisons The general triplet feedbacks with potentially inequality constraints in Algo- rithm [ can be simplified to pairwise comparisons with equality constraints with a simple manipulation as follows.
This implies that if triplet comparisons are used in Algo- rithm [ equivalent pairwise comparisons exist satisfying:

---

Learning Sparse Superposed Features with Feedback
4.2. Feature learning of low-rank matrices
D'= = ''= λ 0, Φ E ( E MF V(y, "y T -
(Ia)
As stated in Proposition ! the learner requires at least p(++1) feedback pairs to annihilate the orthogonal com- plement Oz. However, this requirement decreases with a lower rank of 4-. We illustrate this in Fig. [ a feature matrix + IR 10 of rank 4 trained via Recursive Feature Machines (Radhakrishnan et al. 2024).
(1b)
Now, we show a reformulation of the oblivious learning problem for a feature matrix using pairwise comparisons that provide a unique geometric interpretation. Consider pair (y, 2) and matrix o. An equality constraint implies
y T yy= = z bz
{ yy - -zz =0
Consider an activation E IP in the nullspace of &* Since 4 a = 0, it follows that a T 4 = O. Moreover, for another activation 3 & span(a) in the nullspace, any linear combination ao b satisfies
where ( denotes the Frobenius inner product. Now, given of pairwise feedbacks
F(RP, "- = {vi, 2:) =i))
(aa + 63) T "=" + bB)
corresponding to the target feature matrix क , the learning problem defined by Eq. (Ib) can be formulated as:
This suggests a strategy for designing effective feedback based on the kernel Ker (T*) and the null space null $ of x (see Appendix for table of notations). This intuition is formalized by the eigendecomposition of the feature matrix:
V(y. 2) E
""), ( yy T 22 = =. (2)
Geometrically, the condition in Eq. 2 implies that any solution & should annihilate the subspace of the orthogo- nal complement that is spanned by the matrices fyy zz (y.))..F Formally, this complement is defined as:
(3)
where {A,} are the eigenvalues and { are the orthonor- mal eigenvectors. Since T* > 0 this decomposition is unique with non-negative eigenvalues.
Oz. : {S Sym( (Ø", S) = =3.
4.1. Constructive feedbacks: Worst-case lower bound
To teach g the agent can employ dual approach: teach- ing the kernel associated with the eigenvectors in this de- composition and the null space separately. Specifically, the agent can provide feedbacks corresponding to the eigenvec- tors of T kernel and extend the basis {ur} for the null space. We first present the following useful result (see proof in Appendix (F).
To learn a symmetric PSD matrix, learner needs at most p(p + 1)/2 constraints for linear programming correspond- ing to the number of degrees of freedom. So, the first ques- tion is are there pathological cases of feature matrices in MM which would require at least p(p 1)/2 many triplet feedbacks in Algorithm[] I This indeed is the case, if target matrix x- E Sym,, (RPPP) is full rank.
Lemma 3. Let (w= C IRP be set of orthogonal vectors. Then, the set of rank-1 matrices
In the following proposition proven in Appendix B we show a strong lower bound on the worst-case Φ* that turns out to be of order (pp²).
B = nn (v; + +1)((z + ( is linearly independent in the space symmetric matrices S)
Proposition 1. In the constructive setting, the worst-case feedback complexity of the class MF with general activa- tions is at the least (p(p + 1)/2- - 1).
Using this construction, the agent can provide feedbacks of the form (ui, vey) for some y E HP with Q'y * 0 and v2 4 = c. "Ty to teach the kernel of x. For an orthogonal extension (u.) where Th = 0 for all = r + I..... P. feedbacks of the form (n,, 0) suffice to teach the null space of 4²'
Proof Outline. As discussed in Eq. [I] and Eq. (2), for full- rank feature matrix x- E MM. the span of any feedback set F. i.c., span xxx - yy (x.)))))) must lie within the orthogonal complement Ox- of x0 in the space of symmetric matrices (IPPX)))). Conversely, if 4 has full rank, then Oz- is contained within this span. This necessary condition requires the feedback set to have size of at least p(p+1) 1, given that dim (Sym(IIPPP)))
This is the key idea underlying our study on feedback com- plexity in the general constructive setting that is stated below with the full proof deferred to Appendix F
p(p+1) D
Theorem 1 (General Activations). Let कh" E MMF be a target feature matrix with rank( = r. Then, in the setting of constructive feedbacks with general acti- vations, the feedback complexity has tight bound of
Since the worst-case bound is pessimistic for oblivious learn- ing of Eq. ① general question is how feedback complexity varies over the feature model Mp. Now, we study the feed- back complexity for feature model based on the rank of the matrix, showing that the bounds can be drastically reduced.
θ (r(+1)) + (p - r) - -1) for Eq. 11.
5

---

Learning Sparse Superposed Features with Feedback
Proof Oulline. As discussed above we decompose the fea- ture matrix & into its eigenspace and null space, leverag- ing the linear independence of the constructed feedbacks to ensure that the span covers the necessary orthogonal com- plements. The upper bound is established with a simple observation: r(r + 1)/2 - 1 many pairs composed of B are sufficient to teach 4* if the null space of 4- is known, whereas the agent only needs provide (p- - r) many feed- basis extension to cover the null space, and hence the stated upper bound is achieved.
Algorithm 2 Feature learning with sampled representations
Given: Representation space V C RP, Distribution over representations Dy, Feature family Mp.
In batch setting:
1. Teacher receives sampled representations Vn, ~ Dv.
2. Teacher picks pairs F(Vn, x0)
backs corresponding
{1, VaaV (a, y) E V2 TT -
3. Learner receives F; and obliviously picks a feature matrix + E MM that satisfy the set of constraints in F(V,: Φ¹)
The lower bound requires showing that a valid feedback set possesses two spanning properties of (xx - -yy") for all (z,y)= E F: (I) must include any & E O+- whose column vectors are within the span of eigenvectors of &², and (2) it must include any ev for some subset U that spans the null space of & and U.
4. Learner outputs +b
5. Sparse Feature Learning with Sampled Feedback
Learning with sparse activations In the discussion above, we demonstrated strategy for reducing the feed- back complexity when general activations are allowed. Now, we aim to understand how this complexity changes when activations are s-sparse (see Definition] [ for some s < p. Notably, there exists a straightforward construction of rank- 1 matrices using a sparse set of activations.
In general, the assumption of constructive feedback may not hold in practice, as ground truth samples from nature or induced representations of model are typically indepen- dently sampled from the representation space. The literature Mahalanobis distance learnin/dictionary learning has explored distributional assumptions on the sample/activation space (cf (Gribonval et al. 2014)).
Consider this sparse set of activations B consisting of p(p+1) items in TR? (see (Kumar and Dasgupta 2024)): )
In this section, we consider a more realistic scenario where the agent observes a set of representationsaactiitttnss Vn := {ar, ....... a,, } Dy, with Dy being an unknown mea- sure over the continuous space V S IRP. With these observa- tions, the agent designs pairs of activations teach target feature matrix 4 E (RPxX)
2
B = {es
fe, + te iisiiije p), (4)
where {ei} forms the standard basis. Using similar argu- ment to Lemma we note that the set of rank-1 matrices
Bsparse
{
[uu T
B}
As shown in Lemma 2 we can reduce inequality constraints with triplet comparisons to equality constraints with pairs in the constructive setting. However, when the agent is restricted to selecting activations from the sampled set Vn rather than arbitrarily from V, this reduction longer holds. Observe that if a; 3 ~ iid Dy and o' of non-degenerate feature matrix, then
linearly independent in the space of symmetric matrices Sy)(R**P) and forms a basis. Moreover, every activation in Bext is at most 2-sparse (see Definition I. With this, we state the main result on learning with sparse constructive feedback here.
Theorem 2 (Sparse Activations). Let 4- E <M be the target feature matrix. If an agent can construct pairs of activations from a representation space RP, then the feed- back complexity of the feature model MF with 2-sparse activations is upper bounded by p(++1)
a T -Taaa=a a
T
4
((a,a, B,8,) = 0.
i.j
This equation represents non-zero polynomial. According to Sard's Theorem, the zero set of non-zero polynomial has Lebesgue measure zero Therefore,
2
Remark: While the lower bound from Theorem I applies here, sparse settings may require even more feedbacks. Con- sider a rank-1 matrix x- vu with sparsity(v) = p. By the Pigeonhole principle, representing this using sparse activations requires at least (p/s)² rank-1 1 matrices. Thus, for constant sparsity = O(1), we need 9(p²) feed- backs likks-implying sparse representation of dense features might not exploit the low-rank structure to minimize feed- backs.
P(a.g) (fa T 3 3 3}) = 0.
Given this, the agent cannot reliably construct pairs that satisfy the required equality constraints from independently sampled activations. Since general triplet feedback only provides bits of information, exact recovery up to feature equivalence is impossible. To address these limitations, we consider rescaling the sampled activations to enable the
6

---

Learning Sparse Superposed Features with Feedback
Truth
Feedback: Sparse Sampling
Peedback:: Sampling
Feedback:
0.00181379. 4000
Feedbbcks: 00152222
MSE: 83803468,
MSS:: 0.00136753,
Feedback: Sparse Sampling
Faadback: Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
NSR: 0.00152061.
MSE: 0.00152517,
MSE: D. 0.00156888. Feedbackss
MSS:: 0.00138544,
Feedbacks:
Feedbacks:
FoedBbccks 11.00, 0.97
Figure 2: Sparse sampling. For the target (=) = #0 [(25 > 0), we apply sparse-sampling feedback with sparsity mu (the probability an entry is zeroed). As nu decreases (denser samples), the canonical complexity p(p + 1)/2 = suffices to recover 4 At high sparsity (mu = 0.97), more activations -5, 110. 1100-are required to approach ground truth, in agreement with Theorem
agent to design effective pairs for the target feature matrix 4h .MF.
under Lebesgue measure, the corresponding rank- matrices are linearly independent. This direct application of Sard's theorem on the zero set of a non-zero polynomial equation, yielding the upper bound. For the lower bound, we use some key necessary properties of feedback set as elucidated in the proof of Theorem This result essentially fixes activations that need to be spanned by feedback set, but under Lebesgue measure on a continuous domain, the probability of sampling direction zero.
Rescaled Pairs For a given matrix + * 0, a sampled input x ~ Dy is almost never orthogonal, i.e. almost surely T * This property can be utilized to rescale an input and construct pairs that satisfy equality constraints. Specif- ically, there exist scalars A > 0 such that (assuming without loss of generality x 4x Dy).
x dx A- dyy + by = (VI+ Auy T I(vI+X)ju
We consider a fairly general distribution over sparse activa- tions similar to the signal model in (Gribonval et al.) 2015).
Thus, the pair (x, straints. With this understanding, we reformulate Algo- rithm M into Algorithm 2 In this section, we analyze the feedback complexity in terms of the minimum number of sampled activations required for the agent to construct an effective feedback set achieving feature equivalence which illustrated in Fig. 2 Our first result establishes complexity bounds for general activations (without sparsity constraints) sampled from Lebesgue distribution, with the complete proof provided in Appendix H
satisfies the equality
Assumption (Sparse- Distribution), Each index of a sparse activation vector E IR. sampled i.i.d from a sparse distribution defined as: for all i,
p = 0) = ag a # Lebesgue((O, 1]).
With this we state the main theorem of the section with the proof deferred to Appendix [
Theorem 4 (Sparse Sampled Activations). Consider rep- resentation space V C I2P, Assume that the agent receives representations sampled i.i.d from sparse distribution Dy- Fix threshold >> O, and sparsity parameter <, Then, for any target feature matrix x² E MMF with a bound of n (p2 log & ))1/²²)) on the feedback complexity us- ing s-sparse feedraef feedbacks,the oblivious learner learns & up to feature equivalence with high probability using the feedback set F(V,. Φ¹), i.e.
Theorem 3 (General Sampled Activations). Consider a rep- resentation space V C TRP Assume that the agent receives activations sampled i. a Lebesgue distribution Dy. Then, for any target feature matrix $-" My. with tight bound of - n (p(rtt)) (((pt)) on the feedback complexity, the oblivious learner (almost surely) learns Ø² up to feature equivalence using the feedback set F(Vn, Φ²), i.e.,
Pv Φ' F(V.. x²), YY 0, Ø' Φ*
Py (V 4' F(V,,.
0, 3A D (1-5),
Proof Outline. The key observation that almost surely for any n S p(p+ + 1)/2 sampled activations on unit sphere S
where Ps depends on Dv. and sparasity parameter 8.

---

Learning Sparse Superposed Features with Feedback
Dreed Trrbs
Feoduact: Upandccrppettes
feediact: Sparea Constrctive
Feedbact Spanee Semplig
SALOCCO Pestunes
PL TAEOA JRV0
Samphay
Sparce Sampdng
Feodback Space Samplin
Peodback Spance Saepdiyg
Feadbodut
PIEO
ICD MARAS ARRWI
INC D4TAA LOWVERN
(a) Visualization of 100 dimensions: Feature learning dictionary retrieved for an MLP layer of ChessGPT of dimension 4096 x 512. From lefi-to-right, top-lo-bottom: ground truth SAE. Eigendecomposition (PCC= 9427. 134912 feedbacks). Sparse Constructive (PCC=9973,, 8390656 feedbacks), Sparse Sampling 2000000, 1000000, @2000000, @4000000, 10000000 feedbacks.
Method
Eigendecomp
Sparse Cons.
Sparse Sampling
Feedbacks
134912
8390656
10M
4M
2 M
1 M
PCC
0.9427
0.9773
0.9741
0.9625
0.8256
0.7152
(b) Pearson correlation coeflicient and total feedback count for each method on the same SAE dictionary.
Figure 3: Top: Feature-recovery quality as function of feedback for a dictionary (of dimension 4096 x 512) from an SAE trained for ChessGPT. Bottom: numeric PCC and feedback for each method. Sparse constructive achieves almost perfect correlation (0.9773) in only Rs 8.4M queries; sampling with smaller feedback sizes struggle until 2 4M samples.
Proof Outline. Using the formulation of Eq. we need to estimate the number of activations the agent needs to receive/sample before an induced set of p(p + 1)/2 many rank-1 linearly independent matrices are found. To estimate this, first we generalize the construction of the set B from the proof of Theorem
Feedback Methods: We evaluate four feedback mecha- nisms: (1) Figendecomposition uses Lemma 3 to construct feedback based on s's low rank structure, (2) Sparse Con- structive builds 2-sparse feedbacks using the basis Eq. (4). (3) Random Sampling generates feedbacks spanning Oz. from Lebesgue distribution, and (4) Sparse Sampling cre- ates feedbacks using s-sparse samples drawn from a sparse distribution (see Definition
Ü, (xee : [p]} U {(Aggee + 22 ;i ji<je [p]
We then analyze design matrix M. of rank-1 matrices from sampled activations and compute the probability of finding columns with entries semantically similar to those in Ug, ensuring non-trivial determinant. The quantity is the probability that a pattern these columns is sampled with sparsity at most s. The final complexity bound derived using Hoeffding's inequality and Sterling's approximation.
We implement teaching agent with ac- cess to the target feature matrix to enable numerical analysis. The agent constructs either specific basis vectors or receives activations from distributions (Lebesgue or Sparse) based on the chosen feedback method. For problems with small di- mensions, we utilize the cvxpy package solve constraints of the form {ao yy When handling larger dimen- sional features (5000 5000), where constraints scale to millions (p(p 1)/2 ~ 12.5M), we employ batch-wise gradient descent for matrix regression.
Teaching Agent:
6. Experimental Setup
We empirically validate our theoretical framework for learning feature matrices. Our sexperiments examine different feedback mechanisms and teaching strategies across both synthetic tasks and large-scale neural networks.
Features via RFM: RFM (Radhakrishnan et al. 2024)
considers trainable kemel K X X' + R cor-
responding to a symmetric, PSD matrix +. At each
8

---

Learning Sparse Superposed Features with Feedback
Algorithm 3 Optimization via Gradient Descent
matrix p, assuming 4 UU where U represents the learned dictionary. This formulation allows for efficient batch-wise optimization over the constraint set while main- taining feasible memory requirements.
1. Given dictionary U E RPX", minimize the loss L(U) := EMis((U) + Leeg (U) where MSE loss and regularization term are:
LMSE(U)- = B
Σ
LU) = Al|K i
Since there could be numerical issues in computation for these large dictionaries, to compare the learnt dictionaries, we compute the Pearson Correlation Coefficient (PCC) of the trained feature matrix &p' with the target matrix 4 to show their closeness.
where B represents the batch of samples, À = 10-4 is the regularization coefficient, and é1 is the fixed unit vector.
2. For each batch containing indices i, values v, and targets e:
Σ,,, 5 4'1( "-)
(a) Construct sparse vectors using (f, pains
p 1 t
VE.,
(') 12 Ein 10 /
0-)2
(b) Compute projections: U un and UT y where y = ex 11 (c) Calculate residuals: r; 11, U vll
Note the highest value of p is 1.
3. Update U using Adam optimizer with gradient clipping
4. Enforce fixed entries in U after cach update (U(0, 0] =
7. Discussion
is enforced to be 1.)
7.1. Limitations and Future Work
The similarity-based feature-learning framework has some major limitations: the learner observes features only up to normal transformation, except under strong coherence assumptions (Lemma D - recovery of the underlying dictionary remains open. A natural next step is to relax exact feature equivalence and ask instead for an E-accurate approximation in Frobenius norm. The complexity bounds derived here already translate to the classical statistical-leaming setting, but an intriguing open question is whether the gap between these bounds and practical sample requirements can be tightened, perhaps by exploiting the structural insights developed in this work.
iteration, the matrix &. is updated for the classifier (z) Ex.EDam (y1, 2) as follows: Pi+1
@fa,) (f/m)) We train target functions corre- sponding to monomials over samples in R using 4000 training samples. The feature matrix b, obtained after iterations is used as ground truth against learning with feed- backs. Plots are shown in Fig. and Fig. 2
EEEDIN 0z
SAE features of Large-Scale Models: We analyze dictio- naries from trained sparse autoencoders on Pythia-70M (Bi+ derman al. 2023) (see Appendix [ and Board Game Models Karvonen et al. 2024), with dictionary dimensions of 32k x 512 and 4096 x 512, respectively. We use the dictionaries corresponding to the SAES trained for vari- ous MLP layers of Board Games models: ChessGPT and OthelloGPT considered in (Karvonen et al.] 2024), with dimension 4096 x 512. Note that p(p + 1)/2 8.3.M. For the experiments, use 3-sparsity on uniform sparse distributions. We present the plots for ChessGPT in Fig. for different feedback methods. Additionally, we provide table showing the Pearson Correlation Coefficient between the learned feature matrix and the target x in Table 3b]
7.2. Conclusion
Our theoretical bounds reveal that recovering the feature dictionary of network layer (or trained SAE) demands at least quadratic sample-comples sion, which applies across standard settings, e.g., i.i.d. learn- ing, active learning, or machine teaching. This establishes an sesssvvveees-vvesss-rreeeeeeeee complex or nigh-dimensional the dictionary, the more feed- back/data is required. The quadratic scaling can, however, be reduced under additional structure-e.g, low-rank as- that leveraging such structure is essential for efficiency. Empirically, we observe that re- covery indeed becomes harder in higher dimensions, while incorporating dimensionalliy-reduciioo techniques substan- tially improves performance, motivating future work along these lines. Our results complement the Neural Feature Ansatz (Radhakrishnan et al. (2024) by clarifying when effi- cient feature recovery is possible: if task-relevant directions lie in www-dimensional subspace, the required feedback can be sharply reduced. This insight also informs model- distillation, suggesting that smaller students can inherit fea- tures efficiently when such a low-rank structure is present.
in the ambient dimen-
trade-off: the more
Memory-efficient constraint storage The high dimen- sionality of model dictionaries makes storing complete activation indices for each feature prohibitively memory- intensive. We address this by enforcing constant sparsity constraints, limiting activations to maximum sparsity of 3. This constraint enables efficient storage of large- dimensional arrays while preserving the essential character- istics of the features.
Computational optimization To efficiently handle con- straint satisfaction at scale, we reformulate the problem as a matrix regression task, as detailed in Algorithm 3 The learner maintains a low-rank decomposition of the feature

---

Learning Sparse Superposed Features with Feedback
Impact Statement
S. Arora, Y. Li, Y. Liang, T. Ma, and A. Risteski. Linear algebraic structure of word senses, with applications to polysemy. Transactions of the Association for Computa- tional Linguistics, 6:483-499 2018.
"This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here."
J. Ba, M. A. Erdogdu, T. Suzuki. Z. Wang, D. Wu, and G. Yang. High- digh-dimensional asymptoties of feature learn- ing: How one gradient step improves the representation. arXiv preprint arXiv:2205.01 01445, 2022a.
Acknowledgments
Author thanks anonymous reviewers for insightful reviews which helped revise the work in a better context. Author thanks the National Science Foundation for support under grant 5SS-2211886 in the duration of this project. Author thanks Sanjoy Dasgupta (UCSD) for helping to develop the preliminary ideas of the work. Author thanks Geelon So (UCSD) for many extended discussions on the project. Author also thanks Mikhail (Misha) Belkin (UCSD) and Enric Boix-Adserà (MIT) for helpful discussion during a visit to the Simons Insitute (UC Berkeley). The general idea of writing was developed while the author was visiting the Simons Institute (UC Berkeley) for a workshop for which the travel was supported by the National Science Foundation (NSF) and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through
J. Ba, M. A. Erdogdu, T. Suzuki, Z. Wang, D. Wu, and G. Yang. High- fiigh-dimensional asymptotics of feature learn- ing: How one gradient step improves the representation. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, edi- tors, Advances in Neural Information Processing Systems, 2022b. URL htt.:tttss///pee////// net/ forum? i id=akddwRG6PG1
A. Bellet, A. Habrard, and M. Sebban. Metric learning, volume 30 of Synth. Lect. Artif. Intell. Mach. Learn. San Rafael, CA: Morgan & Claypool Publishers, 2015. ISBN 978-1-62705-365 978-1-6211 1-627-05366-2. doi: 10.2200/ S00626ED V01 1201200 AIM030.
S. Biderman, H. Schoelkopf, Q. Anthony, H. Bradley, K. O'Brien, E. Hallahan, M. A. Khan, S. Purohit, U. Prashanth, E. Raff, A. Skowron, L. Sutawika, and O. Van Der Wal. Pythia: suite for analyzing large language models across training and scaling. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org. 2023.
awards DMS-20X 1883 and #814639.
References
E. Abbe, F. Boix-Adsera, and T. Misiakiewicz. The merged- staircase property: a necessary and nearly sufficient con- dition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782 4887. PMLR, 2022.
B. Bordelon and C. Pehlevan. Self-consistent dynam- ical field theory of kernel evolution in wide neural networks. Journal of Statistical Mechanics: The- ory and Experiment, 2023, 2022a. URL https
A. Agarwal, A. Anandkumar, P. Jain, P. Netrapalli, and R. Tandon. Learning sparsely used overcomplete dictio- naries. In M. F. Balcan, V. Feldman, and C. Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 123 137, Barcelona, Spain, 13-15 Jun 2014. PMLR. URL
//api. wwwpoolaarrrr/ooooooooooooo Corppusl:
248887466
B. Bordelon and C. Pehlevan. Self-consistent dynamical field theory of kernel evolution in wide neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Informa- tion Processing Systems, volume 35, pages 32240-32256 Curran Associates, 2022b.
ngs..... mll
press/v35/ aga.wal14.. html
S. Arora, R. Ge, and A. Moitra. New algorithms for learning incoherent and overeomplete dictionaries. In Annual Conference Computational Learning Theory, 2013. URL bttp:://api..emmntiico org/ ptr/Corpus 69:81333
T. Bricken, A. Templeton, J. Batson, B. Chen, A. Jermyn, T. Conerly, N. Turner, C. Anil, C. Denison, A. Askell, R. Lasenby, Y. Wu, S. Kravee, N. Schiefer, T. Maxwell, N. Joseph, Z. Hatfield-Dode -oddd, A. Tamkin, K. Nguyen, B. Mcl.ean, J. E. Burke, T. Hume, S. Carter, T. Henighan, and C. Olah. Towards monosemanticity: Decompos- ing language models with dictionary learning. Trans- former Circuits Thread, 2023. https:/ttrassfommer http:///w00020///oommmmmmeeeeaae
S. Arora, Y. Li, Y. Liang, T. Ma, and A. Risteski. A la- tent variable model approach to PMI-based word em- beddings. Transactions of the Association for Computa- tional Linguistics, 4:385 199,,,99,0000 2016. doi: 10.1162/tacl
a 00106.
URL
Q1 016-1028/
html.
10

---

Learning Sparse Superposed Features with Feedback
C. Burns, H. Ye, D. Klein, and J. Steinhardt. Discovering latent knowledge in language models without supervision. In International Conference on Learning Representations (ICLR), 2023.
R. Gribonval, R. Jenatton, and F. R. Bach. Sparse and spuri-
ous: Dictionary learning with noise and outliers. IEEE Transactions Information Theory, 61:62,8-6319,
2014. URL https: /topss:/app. www.nticscholstteeeeeeeeee
org/ Coopoopp::
Y. Chen, Y. Chi, and A. J. Goldsmith. Exact and stable covariance estimation from quadratic sampling via con- vex programming. IEEE Transactions on Information Theory, 61:4034-4059, 2013. URL https: //ap:
R. Gribonval, R. Jenatton, and F. Bach. Sparse and spuri- ous: Dictionary learning with noise and outliers. JEEE Transactions on Information Theory, 61(11):629863111
semant: 1 cscho waaccolar.oo org Corp:/ ID:
2015. doi: 10.11
A. Damian, J. Lee, and M. Soltanolkotabi. Neural networks can learn representations with gradient descent. In Con- ference on Learning Theory, pages 5413-5452. PMLR, 2022.
I. T. Jolliffe. Principal Component Analysis. Springer- Verlag, New York, 1986.
A. Karvonen, B. Wright, C. Rager, R. Angell, J. Brinkmann, L. R. Smith, C. M. Verdun, D. Bau, and S. Marks. Mea- suring progress in dictionary learning for language model interpretability with board game models. In The Thirty- eighth Annual Conference on Neural Information Pro- cessing Systems, 2024. URL http::::///ppeeeviere net/forum? htt.forrmmmn--scddoehhhe...
F. Doshi-Velet and B. Kim. Towards a rigorous science of interpretable machine learning, 2017. URL hts 7/arxiv. org/ abs/ 08608
N. Elhage, T. Hume, C. Olsson, N. Schiefer, T. Henighan, S. Kravec, Z. HatfieldDDodss, R. Lasenby, D. Drain, C. Chen, R. Grosse, S. Mc- Candlish, J. Kaplan, D. Amodei, M. Wattenberg, and C. Olah. Toy models of superposition. Trans- former Circuits Thread, 2022. https:/transformer- circuits. circuits.pub/20222 htwo22222tooymooo//ddeee html.
M. Kleindessner and U. von Luxburg. Kernel functions based on triplet comparisons. In Neural Information Processing Systems, 2016.
B. Kulis. Metric learning: A survey. Foundations and Trends@ in Machine Learning. 5(4):287-364, 2100-366,,11,....,. 1935-8237,
2013. ISSN
M. Faruqui, Y. Tsvetkov. D. Yogatama, C. Dyer, and N. A. Smith. Sparse overcomplete word vector representations. arXiv preprint arXiv: 000.55000000000 2015.
doi: 10. 10.1561/22000000009,
URL http:
//dx. doi. www.ddi...ooooo wttpooooo//1.11///20000000
A. Kumar and S. Dasgupta. Learning smooth distance func- tions via queries, 2024. URL htt.https:///axiv...t
A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Romera- Paredes, M. Barekatain, A. Novikov, F. J. R. Ruiz, J. Schrittwieser, G. Swirszez, D. Silver, D. Hassabis, and P. Kohli. Discovering faster matrix multiplica- tion algorithms with reinforcement learning. Nature, 610(7930)44--33, Oct. 2022. ISSN 1476-4687. doi: 10. 10.1038/4411566-22--557777 orq/10.1038/s:00 02t/-4411566002227222220 0217-22
abs/24122 21120
A. Kumar, Y. Chen, and A. Singla. Teaching via best-case counterexamples in the beaming-witt-eeuuvvleen queries paradigm. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26897 Curran Associates, Inc.,
URL https:
T. Fel, A. Picard, L. Béthune, T. Boissin, D. Vigouroux, J. Colin, R. Cadène, and T. Serre. Craft: Concept recur- sive activation factorization for explainability. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2711 June 2023.
2021. URL httpsss:/prroccedngggneeerrrrrre
Cc/ paper Daappe__LLLee//ppppp/////LLLLLL
e 222.ffabeeeeeaaaaaa7777222222662 pdf
X. Li and V. Voroninski. Sparse signal recovery from quadratic measurements via convex programming. SIAM Journal on Mathematical Analysis, 45(5):3019-3033, 2013. doi: 10.1133/120893707. httpttss:://do
R. A. Fisher. The use of multiple measurements in taxo- nomic problems. Annals of Eugenics, 172)1199-188, 1936. doi: https://doi.org/10..1111 146- 193..99999.9.01111......
org 00t...11111112230001
R. Gribonval and K. Schnass. Dictionary identifica- tion- -parre factriiaacto via & -minimization. IEEE Transactions on Information Theory, 56(7):3523- 3539, 2010. doi: 10.1 10.1109/1T:2010.2200 20444466.
S. Mallat and Z. Zhang. Matching pursuits with time- frequency dictionaries. JEEE Transactions on Signal Processing. (1(12):3397-3411 1993. doi: 10.1109/78. 258082.

---

Learning Sparse Superposed Features with Feedback
S. Marks and M. Tegmark. The geometry of truth: Emergent linear structure in large language model representations of true/false datasets, 2024. URL httpss//arxivv org htg/abs/23100 06824
M. Schultz and T. Joachims. Learning distance metric from relative comparisons. In S. Thrun, L.. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
S. Marks, A. Karvonen, and A. Mueller. dic- comarr_learning
L. Sharkey, B. Chughtai, J. Batson, J. Lindsey, J. Wu, L. Bushnaq, N. Goldowsky-Dill S. Heimersheim, A. Or- tega, J. Bloom, S. Biderman, A. Garriga-Alonso,
ht https: httpp:://gita /pss://github.. com/ saprmarks/cictiones waapcctiinrr__eerrnnit learning 2024a.
A. Commy, N. Nanda, J. Rumbelow, M. Wattenberg,
S. Marks, C. Rager, E. J. Michaud, Y. Belinkov, D. Bau, and A. Mueller. Sparse feature circuits: Discovering and editing interpretable causal graphs in language mod- els, 2024b.
N. Schoots, J. Miller, E. J. Michaud, S. Casper, M. Tegmark, W. Saunders, D. Bau, E. Todd, A. Geiger, M. Geva, Hoogland, D. Murfet, and T. McGrath. Open problems in mechanistic interpretability, 2025. URL
19647
B. Mason, L. P. Jain, and R. D. Nowak. Learning low- dimensional metrics. In Neural Information Processing Systems, 2017.
Z. Shi, J. Wei, and Y. Lian. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Confer- ence Learning Representations, 2022.
T. Mikolov, W.-t. Yih, and G. Zweig. Linguistic regularities in continuous space word representations. wende, H. Daumé III, and K. Kirchhoff, editors, Pro- ceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguis- tics: Human Language Technologies, pages 746-751, Atlanta, Georgia, June 2013. Association for Computa- tional Linguistics. URL httpst://acaaatcolleee org/N13-109
K. Q. Weinberger and L. K. Saul. Distance metric learning for large margin nearest neighbor classification. J. Mach. Learn. Res., 10:207-244, June 2009. ISSN 1532-4435.
L.. Vander-
E. Xing, A. Ng, M. I. Jordan, and S. J. Russell. Distance metric learning with application to clustering with side- information. In Neural Information Processing Systems, 2002.
G. Yang and E. Hu. Tensor Programs IV: Feature learn- ing in infinite-width neural networks. In International Conference on Machine Learning, 2021a.
C. Olah, N. Cammarata, L. Schubert, Goh, M. Petrov, and S. Carter. Zoom in: An introduction to cir- cuits. Distill, 2020. doi: 10.239 /5/distil..000224.000 https:/diisilllpp//22000ccciiiii
G. Yang and E. J. Hu. Tensor programs iv: Fea- ture learning in infinite-width neural networks. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learn- ing Research, pages 11727-11737. PMLR, 18-24 Jul 2021b. URL htttps://rrcceee:: ngs .m press/vll /v13//vv1//// 1 //t.g//ll.nggn..l.//
B. A. Olshausen and D. Field. Sparse coding with an over- complete basis set: A strategy employed by v1? Vision Research, 37(23)3331 1997. ISSN 0042-6989. doi: bttpsss/www.cceecccciircee com/ URL
sci httcc///rticclee/1//00022222
A. Radhakrishnan, D. Beaglehole, P. Pandit, and M. Belkin. Mechanism for feature learning in neural networks and free backpropagation free machine learning models. Sci- ence, (666) 2024. doi: 10.1126/sceence. adi5639.
Z. Yun, Y. Chen, B. A. Olshausen, and Y. LeCun. Trans- former visualization via dictionary learning: contextual- ized embedding as a linear superposition of transformer factors. arXiv preprint arXiv: 103. (0..///..3 /5949, 2021.
wwwp:ccce.rr//oooo org/doi/
J. Zhang, Y. Chen, B. Cheung, and B. A. Olshausen. Word embedding visualization via dictionary learning. arXiv preprint
abs/10. www.:001122ssccnnne...
B. Komera-Paredes, M. Barekatain, A. Novikov, M. Ba- log, M. P. Kumar, E. Dupont, F. R. Ruiz, J. S. El- lenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995):468-473 Jan. 2024. ISSN 1476-4687.
2019.
L. Zhu, C. Liu, A. Radhakrishnan, and M. Belkin. Quadratic models for understanding neural network dynamics. arXiv preprint arXiv:2205. 2022.
doi: 10.1038/ 4415866023-069224-6 URL httpstttsss///o.oooooo 111.66222.0034....////rrr2/////0 1038/841588-023--6555
X. Zhu, A. Singla, S. Zilles, and A. N. Rafferty. An overview of machine teaching, 2018 URL https: //arxa/xvvv orgg/bs// ab///b///1 waabb///11... 05927
12

---

Learning Sparse Superposed Features with Feedback
A. Table of Contents
Here, we provide the table of contents for the appendix the supplementary.
Appendix C
provides supplementary experimental results validating our theoretical findings.
Appendix provides comprehensive table of additional notations used throughout the paper and supplementary material.
Appendix
D
contains the proof for Lemma] 1
establishing conditions for recovering orthogonal representations.
Appendix B
completes the proof of Proposition establishing a worst-case lower bound on feedback complexity in the constructive setting.
Appendix presents the proof for the upper bound in Theorem for low-rank feature matrices.
Appendix
G
establishes the proof for the lower bound in Theorem for low-rank feature matrices.
Appendix details the proof of Theorem 3 which asserts tight bounds on feedback complexity for general sampled activations.
Appendix sampled activations.
| demonstrates the proof of Theorem esstablshing an upper bound on the feedback complexity for sparse
13

---

Learning Sparse Superposed Features with Feedback
B. Notations
Here we provide the glossary of notations followed the supplementary material.
Symbol
Description
B, 2,
Activations
col(1) (()
Set of columns of matrix +>
D, Dsparse
Distributions over activations
d
Dimension of ground-truth sample space
Dictionary matrix
Y, Ye A
Eigenvalues of matrix
(Ø', b
Element-wise product (inner product) of matrices
Ker ())
Kemel of matrix + Eigenvectors (orthogonal vectors)
Mi U, U/
mull( (
Null set of matrix 4
Oz.
Orthogonal complement of &' (yPPPPXP)
p
Dimension of representation space
4, E
Feature matrix
Entry at ith row and jth column of +
Target feature matrix
r
Rank of feature matrix
Sym( (RXX))
Space symmetric matrices Space PSD, symmetrie matrices Version space MMF wrt feedback set JF
Sym, (TROXP)
VS(F,MG
Mrl
The set {v1 U2, Up
The set (U.41....,
VIl
Complete orthonormal basis (11, .2,..... Up) Activation/Reprrsentaaii space
VC RP
X C Rdd
Ground truth sample space
14

---

Learning Sparse Superposed Features with Feedback
C. Additional Experiments
In Section 6
we provided details of our experimental setup. this appendix, we will show the results for some additional
experiments: 1) Large-scale SAEs trained on Pythia-70M, 70M (Biderman et al. 2023), and extensive experimental results (in
Appendix C.1 a synthetic task considered in Fig. and Fig. 2
Dictionary features of Pythia-70M We the publicly available repository for dictionary learning via sparse autoen- coders on neural network activations (Marks et al. 2024a). We consider the dictionaries trained for Pythia-70M (Biderman) et al. 2023) (a general-purpe
LLM trained on publicly available datasets). We retrieve the corresponding autoencoders for the attention output layers, which have dimensions 32768 x 512. Note that p(p + 1)/2 se, 512M. For the experiments, we use 3-sparsity on uniform sparse distributions. We present the plots for ChessGPT two parts in Fig. and Fig. 5 for different feedback methods.
Ground Truth
Feedback: Elgendecomposition
1 I9 41 91 19 Feedbacks:
SAE Dictionary Fostures:Pythhaa-00
Figure Feature learning on a subsampled dictionary of dimension 4500 512 SAE trained for Pythia-70M. Theorem states that Eigendecompostion method requires 135316 constructive feedback. After few 100 iterations of gradient descent shown in Algorithm PCC of 93% is achieved ground truth. For visualization, only the first 100 dimensions used.
15

---

Learning Sparse Superposed Features with Feedback
Ground Truth
Feedback: Sparse Sampling
PCC: 0.0242,
SAE Dictionary Features: Pythia-70M
Feedbacks: 200000
Feedback: Sparse Sampling
Feedback: Sparse Sampling
ar 11
h. PCC: 5000000
PCC: 2000000
Sparse Sampling
Sparse Sampling
PCC: 0.6570.
PCC: 0.7716. Feedbacks: 20000000
Feedbacks: 10000000
Figure 5: Sparse sampling for Pythia-70M: Dimension of feature matrix: 32768 x 512 and the rank is 215. Plots for varying feedback complexity sizes. Note that p(p++) 1)/2 xs 512M. We run experiments with 3-sparse activations for uniform sparse distributions. The Pearson Correlation Coefficient (PCC) to feedback size (PCC, Feedback size) improves as follows: (200k, .0242), (2M,.38) (5M,.54) .60), and (20M,.77).
16

---

Learning Sparse Superposed Features with Feedback
C.1. Verification of theoretical results on synthetic task
To validate our theoretical results, we compare the upper bounds derived in Theorem againss empirical performance on controlled synthetic task. This experiment aims to assess how tightly the theoretical feedback complexity aligns with the actual number of feedback queries required to achieve feature recovery up to linear scaling equivalence (Definition
We consider a monomial regression task defined by
y = (x) 21022331 1(x; >> 0),
which induces target feature matrix "" (as constructed by the Recursive Feature Machine (Radhakrishnan et al. 2024). see Section
Setup. Inputs æ E IR 10 are sampled from a Gaussian distribution (0, 0.5 We train an RFM classifier on 5000 training samples to obtain &,, and the teaching agent has access to this feature matrix for generating feedback.
We evaluated the following four feedback mechanisms: Eigendecomposition, Sparse Constructive, Random Sampling, and Sparse Sampling (Section and Section
For each method, we report:
1. The number of feedbacks provided.
2. The empirical mean squared error (MSE) compared to the target MSE achieved using o²
3. The theoretical upper bound the number of feedbacks.
Theoretical vs Empirical Observations. The target feature matrix 4 has rank r = 8, and the ambient input dimension p 10, giving p(p 1)/2 55 as the total number of degrees of freedom used in the stated bounds.
Eigendecomposition::
Theoretical bound (Theorem z(r+1) + p r 38. As shown in Figure this exact number of feedbacks is sufficient to match the target MSE (mean squared error) empirically.
Sparse Constructive: Using 2-sparse feedbacks (Theorem the theoretical bound remains 55. As illustrated in Figure 6, the empirical performance saturates at the target MSE within this bound.
Random Sampling: Feedback is sampled uniformly at random. We evaluate empirical performance 20%, 30%, 50%, 70%, and 100% of the theoretical bound: 55 (as computed using Theorem 3 as shown in Figure 6 The gradual reduction in MSE confirms that the learning curve aligns well with the theoretical complexity.
Remark: Given that these are sampled runs (not averaged), in some cases, the MSE might be higher even if the feedback set is increased (implying that an increase in feedback didn't 't lead to relevant independent directions). But, averaging over runs, we note that the MSE gradually reduces MSE with the stated theoretical bound.
Sparse Sampling: Our first experiment is for 4-sparse activations Figure 7 where each coordinate nonzero with probability μ 0.2, and the nonzero values are drawn from (4 1). Using success threshold of 8 0.05, Theorem 4 yields bound of 117 feedbacks. Figure shows MSE values multiples (30% 2000%) of the total number of degrees of freedom (55). As expected, MSE converges to the target MSE once the feedback size reaches the theoretical threshold.
We perform several experiments with different values of 8, and sparsity level as shown in Figure S
Remark: Since the bounds are independent of the distribution of a coordinate being non-zero, the bounds don't 't change even if we use distribution other than the uniform distribution.
17

---

Learning Sparse Superposed Features with Feedback
Feedbacki: Eigendecomposition
Feedback:
MSE: 0.00101acs.
MSE: 6.00101866,
MSE: 0.00101869,
MSE: 3.08191256,
Training points:
Feedbacks: 38,
Fescbbcks: 53,
Feedbacks: 11,
Feedback: Sampling
Feedback: Sampling
Feedback: Sampling
Feedback: Sampling
MSE: 7.8977940, Feedbacks: 16,
MSE:: 7.77560916, Feedbacks: 27,
NSE: 3,39073646, Feedbacks: 38, Theory:
MSE: 0.00101869, Feedbacks: 55, Theory:
Theory:
Figure 6: Empirical performance for Eigendecomposition, Sparse Constructive, and Random Sampling.
Ground Truth
Feedback: Sparse Sampling
Feadback: Sparse Sampling
Feedback: Sparse Sampling
NSE: 0.00101969.
MSE: 3,74420280,
MSE: 05099124,
NSE: 3.60841886,
Treming points:
Delta; 0.05, spacity: 4
Delts: 0.05, spasthy:
0-S.
Delta: 0.05 spacity: 4,
Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Samplling
NSe: 00101875. Theary 117
MéE: 0.00 0.0001880
MSE: 00101285) (yt. Theory: 117
NSē: 0.80101269,
Theory 317
Theory 2.37
Figure 7: Empirical performance for the Sparse Sampling feedback mechanism.
Ground Truth
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Feadback: Sparse Sampling
HéE: 001051177
3.53717441 Feadbeekky mus D.8. Theory: 54
8.24346433, Festbecks mus
MSÉi 184, 2330
3000
0.6. Theory 34
Theory 54
Feedbacic Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Mnd:: 3.35339992 Theory 54
NSD: 8 000005155, aperaiyy. Theory:
MSE: 0.001951477
MSS: o 0.001051447, Theory 58
Theory 54
Figure 8: Empirical performance for the Sparse Sampling feedback mechanism.
18

---

Learning Sparse Superposed Features with Feedback
Ground Truth
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
NSE: 0.08116082,
MES: 1.33251331,
MSE: 15.63191070,
MSE: 0.60566016,
5050
Delta: Theory 268
Delte: Theory 268
Theery: 268
Feedback: Sampling
Feedback: Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Hék: 0.18 e58ss, Delta leacity: 3, Theaey:
Misi: & 00133205. Delta: dpaxity: 9, Theory
Misi: D. 0.80116090) Deltt:: (pacity Theory
Méli d. 0.00 6699,
Delta: s.d5, 288
Figure 9: Empirical performance for the Sparse Sampling feedback mechanism.
Ground Truth
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
MSs: 0.60067861,
MSE: 6 0.00516G,,
MSE: 3.17076073,
MSE: 0.11788043;
5000
Delta: sparaity:
Delta: sparaht:
Deltas sparaity S; Theory
Theory
Theory
Feedback:
Feedback:
Feedback:
Feedback:
MéE: 0.0066633,
MSC: 000022530
MÉE: 80067o61,
MSE: 0.0067062
Deite: 0.65, aparaity
Delta: 0.05, sparalty:
Delta; 0-65, speralty: S,
Delta; 0-65, aparalty:
Figure 10: Empirical performance for the Sparse Sampling feedback mechanism.
Ground Truth
Feedback: Sparse Sampling
Feedback: Sparse Sampling
Feedback: Sparse Sampling
MSs: 0.00073361,
MSs:: o 0.00178993
Mis: o 0.00076873,
MSsi: o 0.00070801, belta: sparstty
3000
belta: sparsity:
Delta: spanstty &, Theory:
Theory:
Theory:
Feedback:
Feedback:
Feedback:
Feedback:
41
Més;: 19978. 35,
Méc: 806663445
Mác: 88001ic8
Más: 66077277
better B.a, speraity.
belte: 0.2, sparsity:
275, 0.9, beltar D.6. aperaity.
belta: 0.2, aperaity.
Figure 11: Empirical performance for the Sparse Sampling feedback mechanism.
19

---

Learning Sparse Superposed Features with Feedback
D. Proof of Lemma 1
In this appendix we restate and provide the proof of Lemma]
Lemma] 1 (Recovering orthogonal atoms). Let o E RPXP be a symmetric positive semi-definite matrix. Define the set of orthogonal Cholesky decompositions of as
WCO= { U Rpxr ② UU and U diag(> (.ttgg().....AAAA))) A.)).
where rank(() and A1 A2..... Ar are the eigenvalues of + descending order. Then, for any two matrices U,U U" WCD. there exists an orthogonal matrix R E grxr such that
=
where R is block diagonal with orthogonal blocks corresponding to any repeated diagonal entries in U U. Additionally, each column of U' can differ from the corresponding column of U by sign change.
Proof. Let U.U U' E WcD be two orthogonal Cholesky decompositions of Φ. Define R U will show that this matrix satisfies our requirements through the following steps:
We
First, we show that R is orthogonal. Note,
R R (U" diag(L/).....,AAA)UU 1/A,)U")
U'T diag(I/AI, 1/A,)UU diag(I/An.....I/M))
U' 1 ///a.//bdaag(/A......1///
U diag(1/A1,
1/X,)U'U diag(1/A).....; 1/A.)
U'T diag((/A)...,,1X/))))
I
Similarly,
RR
U 1/A,), IUA
U diag(1/A1 ....... 1/A, /ttp://)@@dia(//A........ 1/A,)U
1//2)))
U
U
U diag(1//\ diag(L/A)....,//// Udiagud)
I
Now we show that U' = -UR
UR = UUT diag(1/A1. 1/2,)U J
(I/A,...,,,1///
U'U U'UTTgdiag1//// 1/Ar)
U' ,,
1/b,)
U'
To show that R is block diagonal with orthogonal blocks corresponding to repeated eigenvalues, consider the partitioning based on distinct eigenvalues. Let I, = {i A > be the set of indices corresponding to the k-th distinct eigenvalue % of 4, for 1,..., K, where is the number of distinct eigenvalues. Let m. IIg denote the multiplicity of 7
Define Up and U/ as the submatrices of U and U' consisting of columns indexed by Ir. respectively.
20

---

Learning Sparse Superposed Features with Feedback
Now, consider the block Ri of R. corresponding eigenvalues 7 and 7e- For k + U2 and Uy correspond different eigenspaces (as Thk o 7e), and thus their inner product is zero. Hence,
U diag (1
U = Om Xmm.'
A1 1::
This implies Rx*- 0m Xme for k #
But then R. must be block diagonal:
R1
0
R
R
R
where each R& Im is orthogonal matrix. For eigenvalues with multiplicity (mz 1), the corresponding block Rg is 1 x orthogonal matrix. The only possibilities are:
R
[1] or R 1
representing sign change in the corresponding column of U. For eigenvalues with multiplicity greater than one (mz >> 1). each block R2 can be any my m, orthogonal matrix. This allows for rotations within the eigenspace corresponding the repeated eigenvalue "ik
Combining all steps, we have shown that:
U'=UR
where R is an orthogonal, block-diagonal matrix. Each block R, corresponds to distinct eigenvalue Y/ of T and is either x 1 matrix with entry #1 (for unique eigenvalues) arbitrary orthogonal matrix of size equal to the multiplicity of Th (for repeated eigenvalues). This completes the proof of the lemma.
E. Worst-case bounds: Constructive case
In this Appendix, provide the proof of the lower bound stated in Proposition[] Before prove this lower bound, state a useful property of the sum of symmetric, PSD matrix and general symmetric matrix in Sym(RPXP).
Lemma 5. Let & E Sym, (IRPXP) be symmetric matrix with full rank, i.e., rank( pp For any arbitrary symmetric matrix 4' Sym(BPKP), there exists a positive scalar X > 0 such that the matrix ( + >xb') is positive semidefinite.
Proof. Since 4 is symmetric and has full rank, it admits an eigendecomposition:
S Xuuu,
where (Ar are the positive eigenvalues and {u |
/= are the corresponding orthonormal cigenvectors of Φ.
Define the constant y as the maximum absolute value the quadratic forms of &' with respect to the eigenvectors of Φ:
7 = max SiSp
u, Φ u4
Let be chosen as:
A = minigisp A
21

---

Learning Sparse Superposed Features with Feedback
For each eigenvector uy, consider the quadratic form of (4 A
min X ? A min X 2 0.
u ( + A = Ar + Xua D d xy X
This shows that each eigenvector u, satisfies:
un ① Am O.
Since {u,Y_= forms an orthonormal basis for R", for any vector x E RR, we can express I as x E a, Then:
④
A J
au
1u) 20,
since each term the sum non-negative.
Therefore, { X is positive semidefinite.
Now, we provide the proof of Proposition 1 in the following:
Proof of Proposition 7 Assume, for contradiction, that there exists a feedback set MF, Φ*) for Eq. with size
[FI p(p+1)
1)
For each pair (y. 2) E $ is orthogonal (yy T -22T) T) implying that T E Oxe,, the orthogonal complement of ". Therefore,
span (Avy) - 22 ((ne)EE) C O+.
This leads to
Φ" 1 span (Lyy zz TZTT ((.))r))
Since [F] < p(p+1)
1, we have
p(p + 1)
dim (span (wyy) zz T TT))
1.
2
Adding 4² to this span increases the dimension by at most one:
p(p + 1) 1. 2
dim (span (Φ* U [yv zz H(.))rr)
Since SyM(RPXP) is a vector space with dim (Sym(RPXP))
p(p+1) 2
there exists a symmetric matrix 4/ Ox. such that
' 1 (yy² - 22T) A (y, (y,2)
By Lemma there exists À >> O such that क* A is PSD and symmetric. Since T' E Oa- and क is not scalar multiple of 4=, the matrix 4 + X is not related to x via linear scaling. However, it still satisfies Eq. (]) contradicting the minimality of F.
Thus, any feedback set must satisfy
p(p + 1)
F
1.
2
This establishes the stated lower bound on the feedback complexity the feedback set.
22

---

Learning Sparse Superposed Features with Feedback
F. Proof of Theorem 1 Upper bound
Below we provide proof of the upper bound stated in Theorem
Consider the cigendecomposition of the matrix & There exists of orthonormal vectors {1i, 02, ...,,,.,,)) U.3 with corresponding eigenvalues f71:72 72.....7 such that
(5)
Denote the set of orthogonal vectors {U1, ........8 2 as (r--
Let (1r+1,--.: :p) denoted Virrrj be orthogonal extension the vectors in Vir such that
Vir U [p-r (11, .2...... kipp
forms an orthonormal basis for Rº. Denote the complete basis {U1, U2, Up) as Vip-
Note that (Ur4I....,, }p} precisely defines the null space of &;, i.e.,
null( x-) = span { (fr+1......
The key idea of the proof is manipulate this null space satisfy the feedback set condition in Eq. 2 for the target matrix 4- Since 4 has rank S p, the number degrees of freedom is exactly r(++1), Alternatively, the span of the null space 2
of 4., which has dimension exactly p r. fixes the remaining entries $
Using this intuition, the teacher can provide pairs (y.2) 1 to teach the null space and the eigenvectors {U1, ......, 8e separately. However, it is necessary to ensure that this strategy is optimal in terms of sample efficiency. We confirm the optimality of this strategy in the next two lemmas.
F.1 Feedback set for the null space of x
Our first result is on nullifying the null set of x- in the Eq. (2). Consider a partial feedback set
Frull = u))
If the teacher provides the set Fruth then the null space of any PSD symmetric matrix ' that satisfies Eq. contains the span of (U.+1...., 1 i.e.
Lemma 6.
(Ur+l...,, mp C mull((F).
Proof. Let O' Sym,(PPx be matrix that satisfies Eq. 2 (note that & satisfies Eq. (2). Thus, have the following equality constraints:
A(0,) v) E F Frull:
Φ 0.
Since (Ur41...., {p} is set of linearly independent vectors, it suffices to show that
Vu Vid-rjo
v T
+
(6)
To prove Eq. (6) utilize general properties of the eigendecompositiion of symmetric, positive semi-definite matrix. We express Φ in its eigendecompossitin
KuauT
where (wieiz are the eigenvectors and (7/
the corresponding eigenvalues of 4'. Assume that x 3 0 E Rp satisfies
23

---

Learning Sparse Superposed Features with Feedback
Consider the decomposition
Ei=1 ag4; o' for scalars a, and v' 1 - Now, expanding the equation above,
get.
4
0g44 + vl
Φ
Σ 0g40 + v'
0g
Φ
Σ
ag44
+ to o
Σ
aglss
+
Σ
D'nn' + uo q'vn'
i=1
1=1
1=1
9
Yuzuz
Σ
atus
+ +2
7/ kuuuu of
Σ a.u
+ +o
Σ Nunu
2s of (u:)
Σ an (1gu, Janux
b.j.
a??/ =
Since 7/ > 0 for all i 1,....& (because 4 is PSD), it follows that each 0. Therefore,
T ''' 0. T J
This implies that x E null (')), thereby proving Eq.
Hence, if the teacher provides Frull, any solution Tp' Eq. must satisfy
(U.+1...... mp) S mmll((F).
With this we will argue that the feedback setup in Eq. (2 can be decomposed in two parts: first is teaching the null set
null( ($*) = span a and second is teaching S4. = span (m in the form of $- -Ei= Nuue"
Lemma 6 implies that using feedback set of the form Frull any solution 4 Sym (RRxP) to Eq. ( satisfies the property V(d-r] C m)). Furthermore, [Fnull
Sym+
F.2. Feedback set for the kernel of Φ*
Next, we discuss how to teach Viri. i.c. Vir span the rows of any solution Φ' E Sym, p) to Eq. (2 with the
corresponding eigenvalues (7:)k-> We show that if the search space of metrics in Eq. 2 is the version space MF,
which is a restriction of the space MMF to feedback set Frull. then a feedback set of size at most z(r+1)
is sufficient to teach x* up feature equivalence. Thus, we consider the reformation of the problem in Eq. (2) as
v(y,2) E F(X, (S,,); Φ²)
(yy' - zz =0
where the feedback set F(X, VS(MV, Frui), )-) is devised to solve a smaller space "S(MFFFuull (Φ E MM u O, v), E F.ull.. With this state the following useful lemma on the size of the restricted feedback set F(X, Mnun,, (*).
Lemma 7. Consider the problem as formulated in Eq. 7 in which the null set null({b") the target matrix 4 is known. Then, the teacher sufficiently and necessarily finds a set F(X, VS(Fnui), x²) of size r(r+1) for oblivious learning up to feature equivalence.
2
Proof. Note that any solution Op of Eq. has its columns spanned exactly by Vyr.- Alternatively, we consider the eigendecompostion क' then the corresponding eigenvectors exists in span (Vo))- Furthermore, note that &" is of rank r which implies there are only r(r+1) degrees of freedom, i.e. entries in the matrix $". that need be fixed.
24

---

Learning Sparse Superposed Features with Feedback
Thus, there exactly linearly independent columns of 4', indexed (fid2
-. -. Now, consider the set of matrices
(i.f) o (3)) i [d] E (i1,22, J. 83'
-1l's (4.1),5' (8,53 \ (tH)
This forms basis to generate any matrix with independent columns along the indexed set. Hence, the span of S induces subspace of symmetric matrices of dimension r(r+1) in the vector space symm (F"), i.e. the column vectors along the indexed set is spanned by elements of Sş.. Thus, it is clear that picking feedback set of size r(r+1] 1 in the orthogonal complement of 4², i.e. Og. restricted by this span sufficiently teaches $* if null((") is known. One exact form of this set is proven in Lemma 3 Since any solution &' is agnostic to the scaling of the target matrix &', we have shown that the sufficiency on the feedback complexity for o' up to feature equivalence.
2
Now, we show that the stated feedback set size necessary. The argument is similar to the proof of Lemma
For the sake of contradiction assume that there is smaller sized feedback set Fsmall. This implies that there is some matrix in M
subspace induced by span Sær, orthogonal to ($") is not in the span of F small- denoted as 4'. If 4/ is PSD then it is a solution to Eq. 77 and T' is not scalar multiple of Φ. Now, if $' is not PSD we show that there exists scalar À > 0 such that
< + X E Sym (IR*P), 5k=xxRx)))
i.c. the sum is PSD. Consider the cigendecompostion of o' (assume rank (') = =r')
Φ
8,mui
for orthogonal eigenvectors (M: and the corresponding eigenvalues (d:)i-n- Since (assume) ro S of the eigenvalues negative we can rewrite 4' as
Φ Σ 8.piia +
Σ 8 i-ra+1
Thus, if we can regulate the values of 11, 45 14, for all
ro. noting they are positive, then we can find an appropriate scalar À 0. Let m² = min,e [1 4 [4; and f max |0,). Now, setting À S achieves the desired property of x + Xd shown in the proof of Lemma
Consider that both o' and 4 are orthogonal to every element in the feedback set Fsmall- This orthogonality implies that "* is not a unique solution to equation Eq. 7 up to positive scaling factor.
Therefore, we have demonstrated that when the null set mull( of the target matrix Ø known, feedback set of size exactly 1(++1) 1 is both necessary and sufficient.
E3. Proof of Lemma 3 and construction of feedback set for Ker(Ø*)
Up until this point we haven's shown how to construct this r(r+1) 1 sized feedback set. Consider the following union: 2
{arad } U (uzuz, (12 21 (12 + T
J....U J (u,,, (v1 v,)(U1 + v,) ..... ,....,,,,,,,,,,. + (0, + ex) T
We show that this union is set of linearly independent matrices of rank 1 as stated in Lemma below. Lemma Let {we)-= C I&P be set of orthogonal vectors. Then, the set of rank-1 matrices
B 8 Tou,, (vx + v;)(u; + 1;)T [si<isr]
linearly independent in the space of symmetric matrices Sym( (PPP))
25

---

Learning Sparse Superposed Features with Feedback
Proof. We prove the claim by considering two separate cases. For the sake of contradiction, suppose that the set B is linearly dependent. This implies that there exists at least one matrix of the form u or (us + vy)(1; + vy) that can be expressed as linear combination of the other matrices in B. We now examine these two cases individually.
Case 1: First, we assume that for some i E [r], doaa can be written as a linear combination. Thus, there exists scalars that satisfy the following property
= Σ
U Ui + Σ 3x(or, + (Um + Ums
(8)
j=1
k=1
Vj,k,
aj, Bu > 0, i < mg
(9)
Now, note that we can write
(e, Umn (11, + veaa) T
Σ
Be(ur, + )r Σ
Ba + Uma )o Σ
Ba(vr, Uran D
k=
1=1
But the following sum
aju U +
Σ
Bu
+ Um Jol
Bx (1). + Umm )ume
doesn't span (as column vectors) a subspace that contains the column vector because {ui}i=z is set of orthogonal vectors. Thus, we can write
1 = Σ
Belere + Umm) Min
Σ
BLule +
Σ
Ukume oa
(10)
1=1,==
k=
k=1N==
This implies that
Σ A= 1=
BrUmx =
if = i, Bx =
(1I)
Since not all 8x 0 corresponding to 1 = (otherwise as linear combination of elements in \ [vee])
Er BEUr = 0 we have shown that a.8;7 can not be written
Case 2: Now, consider the second case where there exists some indices i, such that (v, + vy) + 0;) T is of linear combination of elements in B. Note that this linear combination can't have element of type V as it contradicts the first case. So, there are scalars such that
(u, + 0,) + [2) = Σ Bu (vr + +mme + Umz)
(12)
k=1
Vk,
la < mp
(13)
But rewrite this as
(vx + vz)oT + (ve + wz)os
Σ
Be + um,))
Be(m, + 1;)0 +
Σ
Be(ur + (mn) + vm))
k=14=
k=
k= mo35
26

---

Learning Sparse Superposed Features with Feedback
Note that 4 then the corresponding my + j and vice versa. Since (0e are orthogonal, the decomposition above implies
(0; + 1,
Σ
(x + )
(14)
lo Li
(vz + U5)0}
Σ
Ba(ur + Uz)03
(15)
m
Bu + Um (ure + Uma) ) = 0
(16)
k= Je thi, ma3
But using the arguments in Eq. (10) and Eq.
we can achieve Eq. 14 or Eq. 15
Thus, we have shown that the set of rank-1 matrices described in B are linearly independent.
In Lemma 7 we discussed that in order to teach 4- sufficiently agent needs feedback set of size r(++1) 1 if the null set
2
of 4 is known. We can establish this feedback set using the basis shown in Lemma We state this result in the following lemma.
Lemma 9. For a given target matrix Ø' = -'- nus and basis set of matrices B as shown in Lemma the following spans subspace of dimension r(r+1) 1 in Sym(B
U1 \n1yr 12222 A22yy T. (u1 + (2) + +2)
A120y
Os: = 1,U, AvrBy' ,(1 + (11 vr) - -Ar-V'" .....
(U/-1 + ur)(Ur11 + -x) A(r-13-
y$ ツ #
U 0 U y
(vi + U/
x (ve + 2z)
Vi,J,
A
Aij
(i f
yb
Proof. Since 4- has at least positive eigenvalues there exists a vector E IP such that yQ'y y * 0. It straightforward to note that Og is orthogonal to x² As OB C span(B) and 4' L',, dimaspan(Oap) +(r+1) 1.
Now, we will complete the proof of the main result of the appendix here.
Proof of Theorem! 7 Combining the results from Lemma Lemma and Lemma we conclude that the feedback setup in Eq. ( can be effectively decomposed into teaching the null space and the span of the eigenvectors of Φ* The constructed feedback sets ensure that x is uniquely identified up to a linear scaling factor with optimal sample efficiency.
27

---

Learning Sparse Superposed Features with Feedback
G. Proof of Theorem 1 Lower bound
In this appendix, we provide the proof of the lower bound as stated Theorem We proceed by first showing some useful properties on valid feedback set F .MF Φ*) for target feature matrix 4" They are stated in Lemma 10 and Lemma 11
First, we consider basic spanning property of matrices (xxx yy for any pair (x, F in the space of symmetric matrices (PPPP)))
Lemma 10. If d E Ox. such that span (col( ()) C span (V(r) then o E span (F).
Proof. Consider & E Og- such that span (col(+)) span (Vr)>. Note that the eigendecompostion of 4 (assume rank( (Φ) r <)
for orthogonal eigenvectors {1 and the corresponding eigenvalues {8 has the property that span (Im))
span (Vrr)- Using the arguments exactly as shown in the second half of the proof Lemma 7 we can show there exists such that 4- X e VS(F,MF). But then + feature equivalent 4* But this contradicts the assumption of J being a valid feedback set.
Lemma 11. There exists vectors Upp-1 C mull((")) (of size p p r) such that span (Ub-r)) mull( (*)) and for any vector V E Up--/ To E spann (F).
Proof. Assuming the contrary, there exists E span (null( such that TuT & span (FF)
Now To 1. F.F, then for any scalar > 0, + + Ave T is both symmetric and positive semi-definite and satisfies all the conditions in Eq. 1 wrt contradiction as Φ* + Awe T is not feature equivalent to $*
So, consider the case when vo Y. F. Let ( 1 be orthogonal extension of such that (U)41)..., Up-1, forms basis of null(("), i.e., in other words
v.l. (er+1:
up-13 & span ((ur41, ("-+,,...,,p,,,,, w\) null(
We will first show that there exists some E' (+ > for some À > 0) Sym orthogonal to F and furthermore (U.41...., up-1] C mull (b)).
Consider the intersection (in the space (Px()) of the orthogonal complement of the matrices (1.410,411... up-11pp- }. denote Orest i.e.,
p-1
Orest =
n $=
o
Note that
dim(Crest) = p(p + 1)/2 - p
Since wo T is in Orest and dim( > there exists some क' such that 4' Φ6, and also orthogonal to elements the feedback set F. Thus, D' has a null set which includes the subset (ur41,...,
Now, the rest of the proof involves showing existence of some scalar À such that 4 A satisfies the conditions of Eq. (1) for the feedback set F. Note that if u = 0 then the proof is straightforward as span ((rr+),... ...,, ",-,,,,,....p.,, u)}
C
mull P'), which implies span (col(4")) c span ( (.r) ). But this is precisely the condition for Lemma to hold.
"the set is not trivially empty in which case the proof follows easily
28

---

Learning Sparse Superposed Features with Feedback
Without loss of generality assume that v 0. First note that the eigendecomposition of 4' has eigenvectors that contained in Vir U {v). Consider some arbitrary choice of À > O, we will fix value later. It is straightforward that o + X is symmetric for & and & are symmetric. In order to show it is positive semi-definite, it suffices to show that
Vu E IP, (Φ* + X Ju 2 0
(17)
Since (1741)...; 3 (mmll("") mill( (')) we can simplify Eq. 17 to
Yu span (Vr U (ot), u (Φ* A 'u 0
(18)
Consider the decomposition of any arbitrary vector u E span (rri U {u}) follows:
Ur] + v', such that Upr] E span (Vri) o' span ({u))
(19)
Wir] a%% Vi ai ER
(20)
From here assume that U|r] + 0. The alternate case is trivial as of 4'v'
Now, we write the vectors as scalar multiples of their corresponding unit vectors
U(r] 6r Ür, 0r :=
[[
(p1
12
||
Mm
Σ
a
2
(21)
(r)
1=1
d' = 8w 0,
(22)
1
Remark:
Although we have computed the norm of U[r] as ||||]] [Mp in the orthonormal basis Virj, note that the norm remains unchanged (same as the f2). &2 is used for ease of analysis later on.
Using the decompasition in Eq. 19
20
we can write Eq. (88) as
(Φ* + xΦ
)u
(u(r) + 0²) (Φ - x (1()) + t')
u Uri + "ir] + X(urr) + v') x (ur) v¹)
8 a, i, + 1 a, q ür + 25,
T. 83
TT
2'0)
(23)
Since we want u TTb"" + A'D') Ju 2 O we can further simplify Eq. 23 as
82
a Φ ür ūr
a Φ ür +
Φ
0
(24)
82
+1
2
0
2
0
(25)
(2)
where we have used & 3.4 The next part of the proof we show that (1) is lower bounded by a positive constant whereas (2) is upper bounded by a positive constant and there a choice of so that (3) is always smaller than (1).
Considering (1) we note that û, is unit vector the orthonormal set of basis Vir Expanding using the eigendecomposition of Eq. (5)
a 10 0,
7 min 74 >>
Σ.
a
The last inequality follows as all the eigenvalues in the eigendecompostion are (strictly) positive. Denote this minimum eigenvalue as Ymin := min, T
Considering (2) note that only terms that are variable (i.e. could change value) & as ú TT
29

---

Learning Sparse Superposed Features with Feedback
Note that é is fixed vector and i, has fixed norm (using Eq.
21
22
Φ'ol C' for some bounded constant
C > 0 whereas 0 Φ'0 is already constant. Now, [2 á Φ'ú
exceeds
o'6 only if
12 u D 1
26
i T 29
Rightmost inequality implies that 2 u Φ constant. But since & is non-negative
0
5²
+ is negative only for an & bounded from above by positive
[2 0, 0
<
4 0'0
s C"
(bounded constant)
Now using an argument similar to the second half of the proof of Lemma it is straight forward to show that there is choice of X > 0 so that (3) is always smaller than (1).
Now, for À = T, where X" is chosen so that Xunin
X
X x we note that
X 2[C" i ir
u ū + X (ū, D'ū, + 25 0, t'
F
2 Amin
2X" > 0.
Using the equivalence in Eq. 23 arbitrary vector u E span Vr Eq. 17 This implies that +
Eq. 24 and Eq. 25 we have choice of À > 0 such that u (Φ* + X )u 2 0 for any {w}] Hence, we have achieved the conditions in Eq. 18 which is the simplification of A is positive semi-definite.
This implies that there doesn't exist a E span (mull( ()*) such that To & span (F) otherwise the assumption on F to be an oblivious feedback set for 4- is violated. Thus, the statement of Lemma 11 has to hold.
G.1. Proof of lower bound in Theorem
In the following, we provide proof of the main statement on the lower bound of the size of feedback set.
If any of the two lemmas (10 11 violated, we can show there exists À and 4 such that t= X E VS(F,M+)
In order to ensure these statements, the feedback set should have ((++1) + (d - r) -1) many elements which proves the lower bound on F.
But using Lemmal 7 and Lemma we know that the dimension of the span of matrices that satisfy the condition in Lemma I0
at the least r(r+I) - 1. We can use Lemma where = Ei= er (note Thr v * 0). Thus, any basis matrix in Og satisfy the conditions Lemma T0
2
Since the dimension of null(*") is at least (d - r) thus there are at least (d - r) directions or linearly independent matrices (in Sym(RexP) that need be spanned by F.
Thus, Lemma 10 implies there are r(r+1) linearly independent matrices (in Og-) that need to be spanned by F. 2 Similarly, Lemma implies there are p- linearly independent matrices (in Ox.) that need to be spanned by F. Note that the column vectors of these matrices from the two statements are spanned by orthogonal set of vectors, i.e. by Viri and the other by null($*) respectively. Thus, these r(r+1) 1 - (p -r)r are linearly independent in Sym(Ir**)) but this forces a lower bound on the size of F (a lower dimensional span can't contain set of vectors spanning higher dimensional space). This completes the proof of the lower bound in Theorem
30

---

Learning Sparse Superposed Features with Feedback
H. Proof of Theorem 3: General Activations Sampling
We aim to establish both upper and lower bounds on the feedback complexity for oblivious learning in Algorithm The proof revolves around the linear independence of certain symmetric matrices derived from random representations and the dimensionality required span target feature matrix.
Let us define positive index
p(p+1) 2
The agent receives representations:
Vn (11, ..,....; ur} Dy.
For each i, we define the symmetric matrix V; = u.u.
Consider the matrix M. formed by concatenating the vectorized Vi:
= [vec(V]) vec(V2)
vec(Vr)]]
where each vec(V;) is treated as column vector in R8", The vectorization operation for a symmetric matrix A Sym(RPXF) defined as:
Au As + Ayi k corresponds to (i.j), < j.
if k corresponds to (i,
vec(A):
The determinant det(Mi) is a non-zero polynomial in the entries of 81, U....., Up. Since the vectors by are drawn from a continuous distribution Dy, using Sard's theorem the probability that (MM is zero, i.e.,
Pv. (dct(M) 0) 0.
This implies that, with probability 1, the set (V1, V2,.... Vp} is linearly independent in Sym
Pv. (Luv))") } is linearly independent in Sym(RPXP)) 1.
(26)
Next, let Σ" * 0 be an arbitrary target feature matrix for learning with feedback in Algorithm Without loss of generality,
assume = 1i A 0. Define the set F of rescaled pairs as:
== (0. (Ross) E" F-vvvv -muw)) = 0, V > =0).
noting that [ = P
Assume, for contradiction, that the elements of F are linearly dependent in Sym(PPXP). Then, there exist scalars {a;} (not all zero) such that:
P Σ aa -
P
Σ
a.
vv
T
Σ
2=
i=2
1=2
However, since (u,,,T) } are linearly independent with probability 1, it must be that:
P
0 and am = 0 Vi.
Given that 7 > this implies a; 0 for all contradicting the assumption of linear dependence. Therefore, matrices induced by F are linearly independent.
This implies that F induces set of linearly independent matrices, i.e., {vo n..e } in the orthogonal complement Oz,, and since E* has at most P degrees of freedom, any matrix Σ' E Sym(BexP) satisfying:
Σ' (vv" - 700.0 T) =
Vi
must be a positive scalar multiple of Σ""
31

---

Learning Sparse Superposed Features with Feedback
Thus, using Eq. 26 with probability 1, the feedback set F is valid:
Pv. (F is a valid feedback set) = 1.
Since E" was arbitrary, the worst-case feedback complexity almost surely upper bounded by for achieving feature equivalence.
For the lower bound, consider the proof of the lower bound in Theorem D specifically Lemma 10 which asserts that for any feedback set FF in Algorithm 1 given any target matrix Σ" E Sym if Σ E Og- such that span (col(E)) C
span (2nz) then Σ E span (F) where Zpp (r S d) is defined as the set of eigenvectors in the eigendecompostion of Σ (see Eq. (5)
This implies that any feedback set F(V,; Σ*) must span certain matrices E' E SyM(P) Suppose the agent receives ! representations U1, ...... De Dy and constructs:
M = [vec(>")
vec(Vi)
vec(Vi)]
Now, consider the polynomial equation det (M)) = 0. Since every entry of M is semantically different, the determinant det(Mi) is a non-zero polynomial. Note that there are m(p++)) many degrees of freedom for the rows. Thus, it is clear that the zero set (M)) = 0} has Lebesgue measure zero if < plp+1) i.e. MI requires at least p(p+1) columns for (M) to be identically zero. But this implies that set (m:u]]] > can't span E' (almost surely) if < p(p+1) 1. Hence, (almost surely)
2
2
2
the agent can't 't devise a feedback set for oblivious learning in Algorithm 2
In other words, if 8 p(++1)
2
Pv, (agent devises a feedback set F up to feature equivalence) = 0
Hence, span E', it almost surely requires least p(p+1) representations. Therefore, the feedback complexity cannot be lower than 2 p(p+1)
2
Combining the upper and lower bounds, we conclude that the feedback complexity for oblivious learning in Algorithm 2 is tightly bounded by θ p(p+1))
2
I. Proof of Theorem 4 Sparse Activations Sampling
Here we consider the analysis for the case when the activations V are sampled from the sparse distribution as stated in Definition [
In Theorem we assume that the activations are sampled from a Lebesgue distribution. This, sufficiently, ensures that (almost surely) any random sampling of P activations induces set of linearly independent rank- matrices. Since the distribution in Assumption [ is not Lebesgue distribution over the entire support [0, 1). requiring an understanding of certain events of the sampling of activations which could lead to linearly independent rank-1 matrices.
In the proof of Theorem 2 we used a set of sparse activations using the standard basis of the vector space IR. We note that the idea could be generalized to arbitrary choice of scalars as well, i.e..
Ug (be, X + 0, < < p) U (Aigrez + Auze)) dejss Aej + 2011i<i- sp.
Here e is the ith standard basis vector. Note that the corresponding set of rank-1 matrices, denoted as Ú,
0, = (XGeee :1 ss ((Nisee + ( + \nsee)) :1sij
is linearly independent in the space of symmetric matrices on EP, i... Sym(I)XP))
Assume that activations are sampled P times, denoted as Vp. Now, consider the design matrix M = [V V22 .p. as shown in the proof of Theorem 3. We know that if (ct(M)) is non-zero then (V,)' s are linearly independent in Sym(D.))). To show a sampled set Vp exhibits this property we need to show that det(MM) is not identically zero, which could be possible for activations sampled from sparse distributions as stated in Assumption i.e. P Par-aarse (o: * 0) > 0.
32

---

Learning Sparse Superposed Features with Feedback
Note that del((M) CoEp, II. (o)) Consider the diagonal of M. Consider the situation where all the entries non-zero. This corresponds to sampling set of activations of the form Ün Consider the following random design matrix MI.
Af21
1
(p (p-1)pls 1)((1-1)
MI
X
12 pp 1)pp
A121
(p- (o--1)fp-1l (pp
Now, a random design matrix M is not identically zero for any set of P randomly sampled activations that satisfy the following indexing property:
R (u : + 0,
(27)
This is so because for identity permutation, we have II. Mi; + 0. Now, we will compute the probability that R is sampled from Deparse Using the independence sampling of each index of an activation, the probabilities the two subsets of R can be computed as follows:
activations {a1, 02 ;0t) appp Diparse such that Orea * Using independence, we have
1-1
Pi
p
Pnz (1
Pnz Pnx) )-11
1=0
Rest of p(p 1)/2 activations of R in Eq.
27 require at least two indices to be non-zero. This could be computed
a-2
P2
i+2 P
Pns (1 -Pnz) pnn) 2-2-i 2-i
i
i=0
Now, note that these P activations be permuted in P! ways and thus
(P-p)
Ovp = R) 2 P..PP P! P(P-p) P!.
p p-13
++1 Pux (1 Pmo) p-1
Σ
x-
p 2
i42 Pns (1 PPnz Pn=) p-2-1
i
(28)
Now, we will complete the proof of the theorem using Hoeffding's inequality. Assume that the agent samples N activations, we will compute the probability that c VN Consider all possible P-subsets of N items, enumerated as (1, 1,2..... (N) Now, define random variables X;
I if ith subset equals R,
X
o.w.
Now, define sum random variable X I(rr)
X₁. We want to understand the probability Pvy (X 2 1). Now note that,
[X] = Σ E Exx] = (7)
EE Vy sparse
Pvp (Vp = R)
Now, using Hoeffding's 's inequality
Per (X > 0)2 211211 -2exp 2B[X]²
> exp ~2
33

---

Learning Sparse Superposed Features with Feedback
Now, for a given choice of of d' >>> O, we want 5 2 exxp -2(r)* p2_ Using Sterling's ss approximation
NV
eNV
P
1/2P
2
log
log
log
P
Ps
82
P
82
Ps
3
8
34


Reviews:
[{"review_id": "NdZhDzwT3o", "reviewer": "Reviewer_wsQ7", "summary": "This paper investigates theoretical bounds on feedback complexity for learning feature matrices through triplet comparisons. The authors analyze both constructive settings (where agents select activations) and distributional settings (with sampled activations). In particular, for a rank-r feature matrix in p-dimensional space, they prove bounds of Θ((r(r+1)/2) + (p-r)) comparisons in the constructive setting and Θ(p(p+1)/2) for general activations sampled from a Lebesgue distribution (alongside bounds for sparse sampling settings). They validate their findings using Recursive Feature Machine-trained models and dictionaries from sparse autoencoders trained on language models like Pythia-70M and Board Game models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful questions and suggestions. Below, we provide detailed responses to the main concerns.\n\n---\n\n**1. Potential lower bound to complement the sparse sampling upper bound (Theorem 4)**\n\nWe conjecture that the dependence on $p^2$ and $\\log \\tfrac{1}{\\delta}$ in the feedback complexity bound of Theorem 4 is fundamental. A matching lower bound is likely to follow from standard statistical lower bound techniques, such as Fano’s inequality. Specifically, identifying a feature matrix from sparse feedback observations constitutes a high-dimensional hypothesis testing problem, where each feedback vector reveals limited information. Under such settings, Fano-style arguments imply that at least $\\Omega(p^2 \\log \\tfrac{1}{\\delta})$ feedbacks are necessary to achieve reliable identification with confidence $1 - \\delta$. \n\nAdditionally, the quantity $p_s$ in Theorem 4, which captures the number of monomial components affected by sparse activations, could potentially be refined. A sharper bound may be achievable by analyzing high-probability events where sampled sparse activations span the full $p^2$-dimensional space of symmetric matrices.\n\nWe note that deriving a fully rigorous tight lower bound is valuable future work.\n\n---\n\n**2. Empirical vs. theoretical feedback complexity in large-scale SAE experiments**\n\nIn Table 2 (Additional Experiments, p. 29), we report the empirical feedback complexity and the corresponding Pearson Correlation Coefficient (PCC) for various feedback mechanisms on the ChessGPT SAE. For Eigendecomposition, Sparse Constructive, and Random Sampling, the empirical observations align closely with the theoretical bounds stated in Theorems 1–3. For Sparse Sampling, we used 3-sparse activations, which result in a small $p_s$. Consequently, the PCC improves with increasing feedback but remains lower than the other mechanisms due to the fixed sparsity relative to the input dimension $p = 4096$. We observe similar patterns on Pythia-70M SAEs.\n\nTo further support the comparison between theoretical and empirical bounds, we include a synthetic experiment designed to highlight the alignment between the two (see response in bullet point 1. to Reviewer 8xsq).\n\n---\n\n**3. Challenges in scaling to large dimensions**\n\nFor models such as ChessGPT and Pythia-70M, the total number of degrees of freedom $P = p(p+1)/2$ reaches 8.3 million and 512 million, respectively. These scales present significant challenges in terms of storage and computation. Except for Eigendecomposition—which exploits the low-rank structure of the feature matrix—all feedback mechanisms require complexity scaling with $P$.\n\nTo address this, we implemented a sparse feedback representation and avoided storing full dense vectors. Without constant sparsity, storing even $10^7$ feedback vectors becomes impractical. Furthermore, solving the resulting linear systems via direct constraint satisfaction is infeasible. Instead, we use a batch-wise gradient descent method (Algorithm 3, p. 29) to solve for the feature matrix using the feedback generated by rank-1 outer products.\n\n---\n\n**4. Extending to adaptive feedback settings**\n\nWe agree that extending our framework to incorporate adaptive feedback is a compelling direction for future work. In our current setting, the learner is *oblivious*—it selects a feature matrix uniformly at random from the set of hypotheses consistent with received feedback. As a result, the teacher cannot leverage adaptivity across feedbacks.\n\nHowever, in more expressive settings where the learner uses a *preference function* to select hypotheses (e.g., minimizing Frobenius norm, promoting sparsity, or favoring identity-like solutions), adaptive feedback strategies could substantially reduce feedback complexity. Related ideas have been explored in recent work on machine teaching and interactive learning:\n\n- [Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm](https://openreview.net/forum?id=Ee7IOrpLwT)\n\n- [Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models](https://papers.nips.cc/paper_files/paper/2019/hash/4dc3ed26a29c9c3df3ec373524377a5b-Abstract.html)\n\nIncorporating such learner models into our framework would allow for interaction-aware teaching agents and could yield tighter feedback complexity bounds. This remains an exciting avenue for future investigation.\n\n---\n\n**5. Essential References**\n\nWe thank the reviewer for highlighting these relevant references. We will incorporate them into the appropriate sections of the revised paper. Additionally, we note that the work of Radhakrishnan et al. (2024) addresses low-rank matrix recovery under exact measurement conditions, whereas our setting involves relative feedback, which introduces additional complexity.\n\n---\n\nWe hope these responses address your concerns. Please let us know if you have additional feedback or comments, and we will be happy to provide further clarification.", "claims_and_evidence": "The paper's theoretical claims are supported by mathematical development in the main text, with detailed proofs referenced in appendices. \nThe authors establish a learning framework using triplet comparisons, which they reduce to pairwise comparisons with equality constraints in Lemma 2. This allows them to reformulate the learning problem in terms of matrices that annihilate a specific subspace, providing a geometric interpretation.\n\nFor constructive feedback settings, Theorem 1 proves tight bounds of Θ((r(r+1)/2) + (p-r) ) for rank-r matrices through a decomposition approach. For general sampling, Theorem 3 establishes bounds of Θ(p(p+1)/2) using Lebesgue measure properties. For sparse sampling, Theorem 4 provides an upper bound based on probability theory.\n\nThe experimental validation shows alignment with theoretical predictions. Figure 1 demonstrates that for a 10×10 feature matrix, eigendecomposition-based and sparse constructive methods achieve the predicted performance. Figure 2 shows how sparsity probability affects feedback requirements, with higher sparsity requiring more samples as predicted, with some additional results on language models like Pythia-70M and Board Game models in Appendix.", "methods_and_evaluation_criteria": "The paper establishes a well-defined mathematical framework for analyzing feedback complexity. The authors use an oblivious learner model (Definition 3) that randomly selects a feature matrix satisfying all feedback constraints, allowing them to focus on information-theoretic aspects. For evaluation, they use mean squared error (MSE) between learned and ground truth feature matrices to assess reconstruction quality. The experiments employ Recursive Feature Machines (RFMs) to generate controlled test cases with known ground truth matrices. The monomial regression task f*(z) = z₀z₁1(z₅ > 0) provides a controlled environment for testing. For large-scale experiments, the authors mention using batch-wise gradient descent for optimization with dictionaries from language models.", "theoretical_claims": "The paper presents several theoretical results that I reviewed at a high level, though I did not work through all the mathematical details:\n\n1. The key theoretical contribution is establishing bounds on the minimum number of triplet comparisons needed to learn feature matrices under different settings. The authors develop a framework where triplet comparisons are reduced to pairwise equality constraints, then analyze the problem through the lens of orthogonal complements in matrix spaces.\n2. Their approach decomposes feature matrices into eigenspace and null space components, allowing them to derive tight bounds for the constructive setting. For distributional settings, they leverage measure theory to establish bounds for general activations and probability theory for sparse activations. \n3. These theoretical developments build upon established results in linear algebra, measure theory, and probability, though a complete verification would require detailed examination of the appendices.", "experimental_designs_or_analyses": "The experimental design includes both synthetic and language model-based evaluations:\n1. RFM Experiments: The authors use monomial regression with RFMs to generate controlled test cases. They compare four feedback methods (eigendecomposition, sparse constructive, random sampling, sparse sampling) on 10×10 matrices of rank 4.\n2. Sparsity Analysis: Figure 2 investigates how sparsity probability affects feedback requirements, showing increased requirements with higher sparsity.\n3. Language Model Dictionaries: The paper mentions experiments on dictionaries from Pythia-70M and Board Game models with dimensions of 32k×512 and 4096×512 respectively, using batch-wise gradient descent for optimization.\n\nThe authors are encouraged to include experiments and discussions based on LLM dictionary learning in the main paper to demonstrate how the ideas work in realistic settings and at scale.", "relation_to_broader_scientific_literature": "The paper connects to several research domains:\n\n1. Dictionary learning: The work extends dictionary recovery approaches by focusing on learning from feedback rather than direct samples, building on prior work by Gribonval & Schnass (2010) and Arora et al. (2013).\n\n2. Mechanistic interpretability: The paper contributes to understanding feature representation in neural networks, relating to work on sparse autoencoders for interpretability by Bricken et al. (2023).\n\n3. Superposition theory: The work addresses neural network superposition as described by Elhage et al. (2022), where models represent more features than dimensions through sparse linear combinations.\n\n4. Mahalanobis distance learning: The triplet comparison framework connects to work on metric learning by Kulis (2013) and Schultz & Joachims (2003).\n\n5. Recursive Feature Machines: The experiments leverage recent work on RFMs by Radhakrishnan et al. (2024), which use the Average Gradient Outer Product for feature learning.", "essential_references_not_discussed": "Some relevant recent works that could strengthen the paper:\n1. Lan et al. (2024) \"Sparse Autoencoders Reveal Universal Feature Spaces Across Large Language Models\" (arXiv:2410.06981), which shows how SAEs transform LLM activations into interpretable spaces where feature universality can be studied.\n2. Radhakrishnan et al. (2024) \"Linear Recursive Feature Machines provably recover low-rank matrices\" (arXiv:2401.04553), which provides theoretical guarantees for RFMs in low-rank matrix recovery.\n3. Recent work from Anthropic on scaling sparse autoencoders to larger models and using them for causal interventions, that demonstrate practical applications for dictionary learning.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- More detailed analysis of language model experiments would strengthen the paper.\n- Discussion of adaptive feedback mechanisms could enhance future directions.\n- More explicit connection to interpretability applications would increase impact.", "questions_for_authors": "1. For the sparse sampling scenario, do you have insights on potential matching lower bounds to complement your upper bound? Not sure if I missed some details here.\n2. In your language model dictionary experiments, how well did the empirical feedback requirements align with your theoretical predictions? What specific challenges did you encounter at this scale?\n3. How might your theoretical framework extend to adaptive feedback scenarios, where triplets are selected based on previous responses? Could this potentially reduce the number of comparisons needed in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5lR8PhYSpQ", "reviewer": "Reviewer_gr2L", "summary": "The paper demonstrates that complex features encoded in sparse superposed representations can be effectively learned through a surprisingly minimal and indirect form of feedback. More specifically, the authors show that there is low feedback complexity required to learn sparse superposed features using relative triplet comparisons.\n\n## update after rebuttal\nI have carefully reviewed your rebuttal and found that most of my concerns are likely addressable and trust that the authors will be able to improve the draft. I do suggest the authors move the experimental information in Appendix 1 to the main text to demonstrate applicability. I will be increasing my score for the submission.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful questions and suggestions. Below, we provide detailed responses to the main concerns.\n\n---\n\n**1. Evaluation of the paper.**\n\nWe emphasize the broad relevance of our theoretical work \n\n -  They apply to feature extraction in LLMs (see Section 6 and Appendix I for additional experiments for LLMs). \n -  Our results bound sample/feedback complexity for any class of dictionaries, e.g., sparse ones.\n -  Furthermore, they inform directions for mechanistic interpretability based on Neural Feature Ansatz. [1], [2]\n\n\n**2. Lack of a discussion section or conclusion.**\n\nIn the revision, we will include a dedicated discussion section that highlights the main contributions, draws connections to related approaches in feature learning, and outlines the limitations of our work.\n\n---\n\n**3. What is the value of the constructive setting outside of theoretical considerations?**\n\nOur framework encompasses general feature learning and applies to both standard and sparse samples/activations. The constructive setting can be useful in several practical contexts:\n\n- **Machine teaching and program synthesis:**  \n  There is growing interest in understanding the *teachability* of a hypothesis space. Analyzing the best-case complexity of teaching is essential in settings where an agent selects samples to guide a learner. Similarly, in program synthesis, constructive feedback or targeted examples can be valuable for efficiently steering a learner to a fixed goal. [3], [4]\n\n- **Student-teacher models:**  \n  The bounds in the constructive setting translate directly into guarantees for interactive learning in student-teacher models. While the setting may appear contrived, the resulting bounds clarify the gap in informativeness between different types of feedback. [5]\n\n---\n\n**4. How robust are the recovery guarantees when the feedback is noisy or inconsistent?**\n\nThis is an interesting direction for future work. There are two settings worth exploring:\n\n- **Weak teaching agent:**  \n  Here, the agent provides feedback with some noise (e.g., Gaussian). This leads to an additional error-dependent factor in the feedback complexity, on average. Note that the reduction in Lemma 2 (p. 4) assumes that feedback vectors are equivalent in norm under the feature map, so exact recovery is not possible in the noisy setting. The increase in feedback complexity is due to difficulties in reliably sampling low-error feedbacks, which could be addressed via concentration bounds under specific noise models.\n\n- **Learner receives noisy feedback:**  \n  When the learner only receives relative (and noisy) feedback on activations, standard information-theoretic arguments imply that, in the worst case, the feedback complexity is unbounded. Specifically, the differences between rank-1 matrices generated by noisy feedbacks must lie in the orthogonal complement of the target feature matrix in the space of symmetric matrices—an event that occurs with zero probability in general (see related argument in Section 5). It would be interesting to study whether this can be improved in interactive settings or under structured assumptions on the feature matrix.\n\n---\n\n**5. How sensitive are the results to the assumptions on activation sparsity and the underlying distribution?**\n\nWe analyze two sampling setups:\n\n- **Random sampling:**  \n  We assume the input distribution follows a general Lebesgue measure, and we apply Sard's Theorem to derive tight bounds. Thus, unless one considers more exotic measures, the result is robust across a wide class of distributions. Since Lebesgue measures cover most distributions of practical and theoretical interest, the bounds provide a meaningful characterization of feedback informativeness in this setting.\n\n- **Sparse sampling:**  \n  For sparse activations, we follow the distributional assumptions common in the dictionary learning literature (cf. Gribonval et al., 2015). The upper bound in Theorem 4 (p. 7) does not depend on a specific distribution. Instead, it uses a pattern-matching argument and Hoeffding's inequality. The bound depends on the sparsity level and the probability of non-zero coordinates in the activation vectors. Thus, feedback complexity is lower for less sparse activations and for distributions with higher probability mass on more dimensions.\n\n---\n\n### **References**\n\n[1] [Mechanism for Feature Learning](https://www.science.org/doi/10.1126/science.adi5639)  \n\n[2] [Aggregate and conquer](https://arxiv.org/pdf/2502.03708)\n\n[3] [An Overview of Machine Teaching](https://arxiv.org/pdf/1801.05927)\n\n[4] [Program Synthesis](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf)\n\n[5] [Teacher-Student Architecture for Knowledge Distillation: A Survey](https://arxiv.org/abs/2308.04268)\n\n\n---\n\nWe hope these responses address your concerns. Please let us know if you have additional feedback or comments, and we will be happy to provide further clarification.", "claims_and_evidence": "The authors demonstrate the following differences in complexity when going from a fully general (worst-case) setting to an assumption of low-rank structure:\n\n**Worst-case scenario:**\n\n$$\\frac{p(p+1)}{2}$$\n\n- \\(p\\) denotes the dimension of the representation space\n\n**Improved complexity (low rank):**\n\n$$\\frac{r(r+1)}{2} + (p - r) - 1$$ \n\n- \\(r\\) represents the rank of the feature matrix .\n\nSince \\(\\Phi^*\\) is effectively \\(r\\)-dimensional, one can exploit that low-rank structure to reduce the number of constraints needed to recover \\(\\Phi^*\\) up to a positive scalar factor. Therefore, you only need to describe how the matrix acts on its r-dimensional subspace (where it’s nonzero).", "methods_and_evaluation_criteria": "The authors take two approaches to evaluate their claims:\n\n**Theoretical Analysis**\nThey derive upper and lower bounds on the number of feedback constraints required to identify a target feature matrix up to a positive scale factor. By contrasting constructive feedback (where any activation can be chosen) with sampling-based feedback (where activations are drawn from known distributions), the authors show how assumptions like low-rank structure dramatically reduce the needed constraints.\n\n**Empirical Evaluation**\nThey implement four feedback strategies—Eigendecomposition, Sparse Constructive, Random Sampling, and Sparse Sampling—and test them on synthetic tasks (Recursive Feature Machines) and large-scale sparse autoencoders (e.g., Pythia-70M). Key metrics include mean squared error between the reconstructed matrix and the ground truth, along with the total number of constraints each method requires.", "theoretical_claims": "As a reviewer that does not work in the domain of theory, I did not carefully assess the correctness of the proofs in this work.", "experimental_designs_or_analyses": "Outside of reviewing this paper, the soundness/validity was not checked.", "relation_to_broader_scientific_literature": "The key impact this paper makes appears to be towards the interpretability community. From this perspective, many of the formulations presented in the main text may not apply. For example, the construction setting is not possible to apply to models (like LLMs) since the activation features cannot be controlled in such a manner.", "essential_references_not_discussed": "I do not have strong familiarity with the theoretical work in this area to know if essential references are missing.", "other_strengths_and_weaknesses": "The reduction in complexity is a desirably property in the space of model interpretability. \n\nWithout a discussion section or conclusion, it was very difficulty to properly evaluate this paper. In its current form, the paper feels incomplete. Also the flow of the paper is very difficult to parse given all the different constructions of the derivations.", "other_comments_or_suggestions": "Table 1: where the row header says “Stardard Constructive” instead of “Standard Constructive.”", "questions_for_authors": "What is the value of the constructive setting outside of theoretical considerations?\n\nHow robust are the recovery guarantees when the feedback is noisy or inconsistent?\n\nHow sensitive are the results to the assumptions on activation sparsity and the underlying distribution?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CuTERoEEPt", "reviewer": "Reviewer_tvNN", "summary": "This paper proposes a new problem, inspired by the recent works in ML interpretability, specifically in the literature that posits that activations *linearly* encode concepts. (This is known as the linear representation hypothesis). \n\nThe authors suggest that we can use an agent (potentially an LLM) to generate labeled data in representation space. These labels are for triples, and indicate which of two elements of the triple are closest to the third (or equal in the case of a tie). \n\nThe goal is essentially to learn a PSD matrix for which the induced distance metric matches all the labeled data. \n\nThe authors consider 4 different constraints on the agent's data generating process. \n\n(1) Standard Constructive:  In this case, if the matrix is rank $r$, we can first provide labels that enumerate the nullspace, and then provide the remaining $O(r^2)$ points to learn the low-rank $\\Phi$.\n\n(2) Sparse Constructive: The unit vectors and their pariwise sums suffice, but we cannot exploit the rank.\n\n(3) Sampled Activations: Under the assumption each sampled representation can define a corresponding rank-1 matrix, and all are a.s. linearly independent, so the $p(p+1)/2$ can be achieved, to determine $\\Phi$\n\n(4) Sparse Sampled Activations: We only get to samples of representations that are at most $s$-sparse, as we would expect in practice. I didn't fully grasp proof--maybe the exposition can be improved.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful questions and suggestions. Below, we provide detailed responses to the main concerns.\n\n---\n\n**1. Potential lack of practicality of the first three theorems.**\n\nAs discussed in our response to Reviewer 2 (gr2L), our framework considers general feature learning. The results in Theorems 1–3 apply broadly across domains such as machine teaching, program synthesis, and student–teacher models, where best-case complexity is a central focus. These bounds provide foundational insights and can guide the design of more efficient teaching or interaction systems in these areas.\n\n---\n\n**2. Discussion of additional experiments in the main text.**\n\nIn the revised version of the paper, we will incorporate a substantial discussion of the methodology and findings from the additional experiments directly into the main text.\n\n---\n\n**3. What is $p_s$? Can you provide more information in the text?**\n\nAs detailed in Appendix H, $p_s$ is the probability of the event where $P$ sparse activations (with sparsity $s$) are sampled with a pattern such that the design matrix $\\mathbb{M}$ has non-zero determinant (see proof outline of Theorem 4, pp. 7–8). This ensures that at least $P = p(p+1)/2$ linearly independent rank-1 matrices can be constructed from these activations. We will highlight and define this quantity more clearly in the main paper.\n\n---\n\n**4. Why is sparse constructive also not $\\Omega$?**\n\nAs noted in the remark following Theorem 2, the lower bound of $\\Omega(p^2)$ holds when feedback sparsity is of constant order, i.e., $s = O(1)$. This is sufficient for cases where feedback is restricted to constant-sparse vectors. However, it remains open whether this lower bound remains tight when $s$ grows with $p$, for instance, if $s$ is strongly sublinear in $p$. The upper bound in Theorem 2 is stated for 2-sparse feedbacks, and it applies more generally to higher sparsity values as well.\n\n---\n\nWe hope these responses address your concerns. Please let us know if you have additional feedback or comments, and we will be happy to provide further clarification.", "claims_and_evidence": "The main point of this paper is a new theoretical formulation and a solution to that formulation. Given that the proofs in the appendix are correct, (the sketches for at least Thm.1-3 are quite convincing), then there is sufficient evidence of the claims. Experiments also seem to validate the claims.", "methods_and_evaluation_criteria": "Yes. Proofs for formal claims + some small experiments for additional verification.", "theoretical_claims": "I did not check the proofs in the appendix, but the proof sketches for Theorems 1-3 are sufficiently detailed (at least for upper bounds) that I am convinced that the statements are relatively easily proved. \n\nFor Theorem 4, I did not follow the proof sketch, and did not check the proof.", "experimental_designs_or_analyses": "Experiments are quite limited. For the final version, the authors might try to work on some additional experiments with greater scale/complexity. However, I don't think the experiments are needed to verify any of the claims, and I recognize that the approaches considered (esp. for Sparse Sampled Activations) might not scale well and require many samples, making them unsuited for real models.", "relation_to_broader_scientific_literature": "This paper has value in its contribution to the theoretical foundation of mechanistic interpretability. The theory and ideas are suggestive of potential new approaches for learning representations, and establish bounds on the complexity of learning from simple comparison data.", "essential_references_not_discussed": "Perhaps some limitations of linear representations could be discussed. See [1]\n\n[1] Recurrent Neural Networks Learn to Store and Generate Sequences using Non-Linear Representations, Róbert Csordás, Christopher Potts, Christopher D Manning, Atticus Geiger", "other_strengths_and_weaknesses": "I think the unique perspective of this work is in it's interesting problem framing, using agents to generate labeled data and learning.\n\nAn additional weakness is the potential lack of practicality of the first three theorems.", "other_comments_or_suggestions": "I think the \"additional experiments\" section is interesting, and worthy of inclusion at the end of the paper. I understand the challenge of presenting it though, as it deviated significantly from the approaches discussed in the theory due to practicality.", "questions_for_authors": "1. What is $p_s$? Can you provide some more information in the text?\n2. Why is sparse constructive also not $\\Theta$ (given the argument)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "gHV8NAC8O6", "reviewer": "Reviewer_8xsq", "summary": "In this work, the authors study how well the feature learned by a neural network can be retrieved by the means of some agents, e.g., an LLM, in the form of *relative triplet comparisons*. Formally, leveraging the linear feature decomposition that encodes features in a dictionary, the authors investigate how well a learner provided with sparse triplets given by an agent can identify the relevant features (up to normal transformation). After introducing the protocol with which a learner receives triplets from an agent, the authors provide bounds on the feedback efficiency, i.e., the minimal number of interactions to learn feature matrices (normal transformations of feature dictionary). The authors provide tight bounds in sparse and standard settings with an agent that gives either constructive or distributional sparse triplets.\nFinally, the authors provide empirical validation of their results on synthetic and large-scale models.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful questions and suggestions. Below, we provide detailed responses to the main concerns.\n\n---\n\n**1. Can the authors compare theoretical vs empirical bounds?**\n\nWe perform experiments based on RFM (cf Section 6, p.8) on a monomial regression task to establish a high correlation of theoretical bounds to empirical bounds. A pdf showing plots and a single Jupyter Notebook can be found here: https://anonymous.4open.science/r/rebuttal_ICML_featurelearning-2E0B/\n\n---\n\n**2. Conclusion/discussion section missing.**\n\nWe will complete a discussion section in the main text to summarize the contributions and discuss the limitations and room for future work.\n\n---\n\n**3. Benefit to the feature learning community and numerical impact on computational resources for feature retrieval.**\n\nFirst, we compare some known empirical methods for feature retrieval:\n\n- **Numerical Impact:**\n\n  - **SAEs:** SAEs are widely used to recover interpretable feature dictionaries. However, training SAEs is computationally expensive and typically scales as $\\mathcal{O}(Tnpd)$, where $T$: number of iterations, $n$: number of samples, $p$: activation dimension, and $d$: input space dimension. [1]  \n    E.g.:  \n    > \"We take a one-layer transformer with a 512-neuron MLP layer, and decompose the MLP activations into relatively interpretable features by training sparse autoencoders on MLP activations from 8 billion data points...\" [2]\n\n  - **CRAFT:** CRAFT uses non-negative matrix factorization (NMF) to extract concepts from hidden activations. It solves a dense matrix factorization problem via ADMM with per-iteration complexity $\\mathcal{O}(npr)$, where $r$ is the number of latent components [4]. This method requires access to full activations.\n\n  - **Probing:** [5] studies how semantic properties are linearly decodable from hidden representations. While not aimed at full feature recovery but rather interpretable linear concepts, these methods include:\n    - **Mass-Mean:** $\\mathcal{O}(np^2 + p^3)$\n    - **Logistic Regression:** $\\mathcal{O}(Tnp)$\n    - **Contrast-Consistent Search:** $\\mathcal{O}(mp^2)$ ($m$ is the number of contrast pairs)\n\n   - **Our Method:** Compared to the empirical performance of these baselines, our feedback-based method achieves these provable bounds:\n      - **Random/Sparse Sampling:** $\\mathcal{O}(p^2)$ or $\\tilde{\\mathcal{O}}(p^2)$ ($\\tilde{\\mathcal{O}}$ hides log and sparsity-related factors)\n      - **Eigendecomposition:** $\\mathcal{O}(r^2 + p)$ ($r$: the rank of the feature matrix)\n\n\n- **Relevance to Feature Learning:**\n\n  - **Radhakrishnan et al. (2024):** [3] posits a Neural Feature Ansatz, showing a strong correlation between weight outer products and a neural network's Average Gradient Outer Product (AGOP). Our method complements this line of work by providing insights into how efficient feature learning could be possible, leveraging low-dimensional structure of task-specific relevant directions (in AGOP). \n\n  - **Distillation:** Our results are applicable to model distillation, suggesting that more efficient algorithms can be designed by exploiting the low-dimensional structure of the features of larger models.\n\n  - **Feature Formation:** Our work highlights that learning certain classes of features can have inherent statistical and computational bottlenecks, especially in high dimensions. Even with feedback, quadratic dependence on dimension is generally unavoidable.\n\n---\n\n**4. Takeaways of the theoretical results and empirical validation.**\n\nKey takeaways:\n\n- Our results suggest potential sample complexity lower bounds on feature formation in the activation of a layer or a trained SAE for standard learning frameworks, e.g., active learning, iid learning, machine teaching.\n- There is a clear trade-off between the expressiveness of high-dimensional feature matrices and the difficulty of recovering them: more complex or expressive dictionaries generally require more feedback or data.  \n- In the general case, the required feedback scales quadratically with dimension, though this can be reduced under structural assumptions (e.g., low rank).  \n- Empirically, we find recovery becomes harder in high dimensions, and results suggest leveraging structure may improve efficiency, motivating future works to dimensionality reduction.\n\n---\n### **References**\n\n[1] [Open Problems in Mechanistic Interpretability](https://arxiv.org/abs/2501.16496)  \n[2] [Towards Monosemanticity: Dictionary Learning](https://transformer-circuits.pub/2023/monosemantic-features/index.html)  \n[3] [Mechanism for Feature Learning](https://www.science.org/doi/10.1126/science.adi5639)  \n[4] [CRAFT: Concept Recursive Activation FacTorization](https://arxiv.org/abs/2211.10154)  \n[5] [The Geometry of Truth](https://arxiv.org/abs/2310.06824)\n\n---\n\nWe hope these responses address your concerns. Please let us know if you have additional feedback or comments, and we will be happy to provide further clarification.", "claims_and_evidence": "The theoretical claims are well supported by clear and detailed proofs, and the authors also provide experimental validation of their theory on synthetic tasks and large-scale models.", "methods_and_evaluation_criteria": "The main contributions of this work are theoretical, and the authors provided detailed proofs as well as experimental computation to validate the theory both in synthetic and large-scale settings. I believe the methods and evaluation criteria make sense for the problem at hand.", "theoretical_claims": "The proofs are well thought, detailed, and clear. I find them elegant, and in my opinion, these are the main strengths of this work.\nOne does not need to be an expert in the research field of the current submission to understand the proofs and the theoretical results.", "experimental_designs_or_analyses": "The authors provided the code to reproduce their results. A quick inspection of the code seems to indicate that the experiments were well-conducted, although I did not re-run the experiments. The experimental setup is well introduced however, I have some issues with understanding how well the experiments confirm the theoretical results. The current submission would be improved by clearly stating in more detail what empirical confirmation can be seen from the figure. A comparison between the theoretical bound and the one observed in practice could also be of interest.", "relation_to_broader_scientific_literature": "I find that related work and prior works are well introduced and compared. The submission's contributions are part of a growing interest to better understand the internal mechanism at play in neural networks, especially in LLMs (e.g., prior works on Sparse Autoencoders, mechanistic interpretability). The protocol to retrieve features learned by a neural network using an agent such as a human or an LLM, along with the bounds on the feedback complexity, seems novel.", "essential_references_not_discussed": "To the best of my knowledge, there are no essential references not discussed in the current submission.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The proofs are clear and well-detailed, and notations are defined early for the reader\n- The problem considered seems original and is well explained \n- I find the proofs techniques elegant with the null space analysis and cardinal computations. I find it refreshing to see the use of algebra.\n\n**Weaknesses**\n\nI list below what I think are weaknesses, but I would be happy to be corrected if I misunderstood some important aspects of the authors' contributions.\n\n- In my opinion, the main weakness of the current work is the contextualization of the theoretical results. More discussion regarding their impact and comparison to the existing literature could greatly improve the current submission (e.g., benefits of the bounds for the feature learning community, numerical impact on the computational resources needed to retrieve neural network features, etc.).\n\n- Moreover, it is not clear to me how the experiments validate the theoretical findings, and since there is no extended intuition/explanation of them, it is quite hard to grasp their impact, and it makes the global work lack some coherence. An idea to improve the submission would be to add some comparison between theoretical vs. empirical bounds.\n\n- A conclusion/discussion section is missing to summarize the contributions and discuss limitations and future work.\n\nOverall, I find the paper well written, and the framework studied is interesting and quite original. I value the technical contributions for the bounds, however, I have trouble seeing the benefits and practical takeaways of the approach in the context of SAE and feature learning because of the lack of explanations/intuition. This is the reason for my current score. I remain open to modifying my score, provided the authors clarify the points mentioned in the weaknesses section.\n\n**Update after rebuttal**: increased score from 3 to 4.", "other_comments_or_suggestions": "I list below some potential typos:\n- Table 1 / first cell: \"Stardard Constructive\" --> \"Standard Constructive\"", "questions_for_authors": "Related to weaknesses:\n\n1) How do the bounds translate in terms of computational resources needed to retrieve features learned by neural networks in practice? The theorems indicate the convergence rate, but it could be interesting to compare it to the naive baseline or common methods used in practice. Could the authors elaborate on that?\n\n2) Could the authors add more discussion on the takeaways of theoretical results and empirical validation?\n\n3) Could the authors compare the theoretical and empirical bounds to better understand how well the theory predicts the practice (for instance, on some simple synthetic task)?\n\n4) Could the authors add a conclusion/discussion section at the end of the paper to summarize the contributions and discuss the limitations and room for future work?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper received positive feedback from all reviewers, in particular based on the originality of the proposed approach and the clear theoretical results. The main criticisms are that additional experiments from the appendix should be added to the main paper, and adding a discussion section would help understand the impact of this work. Given that the authors plan to fix these two points, I recommend accepting this paper.

Additionaly, I think that the exposition of the problem could be further improved, in particular by paragraph l.69, making it clear which part is fixed for the model (the dictionary $D$ from my understanding) and which part is learn with the feedback ($\hat D$, which is then also denoted $D$ and changes to $L$ later on). The overall flow of the paper can also be improved (**gr2L**) by stating more clearly the selection mechanisms considered in l.74, and giving a better description of how the label $l$ is constructed.
Decision: Accept (poster)