Pith. sign in

REVIEW 4 major objections 5 minor 41 references

Transformers versus the EM Algorithm in Multi-class Clustering

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A transformer pretrained on labeled clustering examples provably reaches the minimax error rate for multi-class Gaussian clustering.

desk verdict The EM approximation construction is genuinely useful, but the minimax-optimality claim sits on a mis-cited, unproved lower bound and an internal rate inconsistency. read the letter →

arxiv 2502.06007 v1 pith:KNT7YGSA submitted 2025-02-09 stat.ML cs.LG

Yihan He , Hong-Yu Chen , Yuan Cao , Jianqing Fan , Han Liu This is my paper · ORCID
classification stat.MLcs.LG MSC 62H3068T07
keywords transformerEMalgorithmLloyd'sGaussianmixtureclusteringminimaxratesoftmaxattentionuniversalapproximationpretrainedgeneralization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Transformers are usually studied as supervised in-context learners; this paper asks whether a transformer can learn a classical unsupervised algorithm—clustering a mixture of Gaussians—from labeled pretraining instances. The paper's central claim is that softmax attention layers can simulate the two steps of Lloyd's algorithm (the EM update for Gaussian mixtures): softmax-weighted averages compute the expectation step, and a scaled softmax approximates the hard assignment step. The authors prove constructive approximation bounds for both steps and show that the empirical risk minimizer over a bounded transformer class reaches the minimax optimal error rate for multi-class Gaussian clustering, provided the pretraining set is large enough—of order $\exp(\Delta^2/(2\sigma^2))$ instances—and a spectral/k-means++ initialization is used. If the claim holds, it provides a provable route by which pretraining teaches a transformer to run a classical inference algorithm on fresh problem instances, and it identifies the closest-pair separation $\Delta/\sigma$ as the quantity that governs the difficulty of clustering.

What carries the argument

The load-bearing object is the softmax attention layer treated as an arithmetic unit. The Expectation step of Lloyd's algorithm is a weighted average whose weights are exactly softmax outputs; the Maximization step is an argmax that a temperature-scaled softmax approximates exponentially well (Lemma B.1). To carry both steps, the paper proves a new universal approximation bound (Lemma 3.1 and Appendix Lemma A.2): sums of softmax functions can approximate any elementwise $(R, C_\ell)$-smooth mapping $f: [-R,R]^d \to \mathbb{R}^{d_1}$ to accuracy $C(f) d \sqrt{(d^2/M)\log(MR/d^2)}$ using $M$ heads. A constructive layer-by-layer design embeds $\tau$ Lloyd iterations into a transformer of depth $L = \tau(3+3k)$ applied to a context-augmented matrix $H$ that stacks the data, the initial centroids, the one-hot memberships, and auxiliary rows; the un-normalized attention variant of the architecture removes the $O(1/N)$ error of the softmax-weighted averaging and yields the faster $N^{-100.5}$ rate.

What would settle it

Run the pre-training protocol with k=2, isotropic Gaussians, separation $\Delta/\sigma$, and $n = \exp(\Delta^2/(2\sigma^2))$ instances, optimizing by gradient descent: if the achieved loss stays above $\exp(-\Delta^2/(8\sigma^2))$ by a gap larger than the stated $n^{-1/4}$ terms as $n$ grows, Theorem 3.3's rate is not realized in the training regime it claims to describe. Alternatively, compute the minimax risk for the soft-margin loss directly: if it decays slower than $\exp(-\Delta^2/(8\sigma^2))$, then Remark 2 is false and the matching claim collapses.

Watch

Extended reading notes

Core claim

The central claim is that a transformer can be made to execute Lloyd's algorithm—the EM update for Gaussian mixtures—entirely through its softmax attention layers, and that a transformer pre-trained on labeled clustering instances then matches the information-theoretic limit of the problem. Concretely, Theorem 3.3 shows that, with probability at least $1-\delta-5n^{-1}-2\exp(-\Delta/\sigma)$, the empirical risk minimizer over a bounded transformer class attains $L(TF_{\hat\theta}(H), P_1(z)) \lesssim \exp(-(1+o(1))\Delta^2/(8\sigma^2)) + \sqrt{k}\,n^{-1/4} C d \sqrt{\mathrm{Polylog}(n)} + N^{-3/2}$, where $\Delta$ is the closest centroid separation and $\sigma$ the noise scale. When the number of pretraining instances is $n \asymp \exp(\Delta^2/(2\sigma^2))$, this matches the minimax lower bound of Lemma 2.1, so the paper claims that the transformer reaches the fundamental limit of multi-class Gaussian clustering. The same statement holds for the Transformer+ architecture, which attains a faster $N^{-100.5}$ dependence on the number of points per instance. The paper reads this as evidence that pretraining teaches transformers to run classical inference algorithms on new problem instances.

Load-bearing premise

The theorem's optimality claim rests on the unproved assumption (Remark 2) that the minimax lower bound, derived for 0–1 prediction error, also holds for the soft-margin loss used in Theorem 3.3; the theorem also bounds the empirical risk minimizer, not the stochastic-gradient-trained network that practitioners actually run.

Editorial extensions

If this is right

  • With $n \asymp \exp(\Delta^2/(2\sigma^2))$ pretraining instances, the empirical risk minimizer reaches the minimax rate $\exp(-(1+o(1))\Delta^2/(8\sigma^2))$ plus $n^{-1/4}$ terms for multi-class Gaussian clustering (Theorem 3.3).
  • The construction is explicit: $\tau$ Lloyd iterations are embedded in $\tau(3+3k)$ layers with $M \asymp n^{1/4}$ heads, so depth plays the role of algorithmic iterations.
  • The Transformer+ variant, which adds un-normalized attention layers, improves the dependence on the per-instance sample size $N$ from $N^{-1}$ to $N^{-100.5}$.
  • The proof establishes a universal approximation bound for softmax networks over multivariate $(R, C_\ell)$-smooth mappings, a technical result that stands on its own for the expressivity of transformers.
  • The theory relies on a context-augmented input (data, initial centroids, and memberships), yet the simulations omit this auxiliary matrix and still show strong performance, matching the predicted trends.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the open right-product softmax approximation problem is solved, the un-normalized attention layer becomes unnecessary, so the same minimax claim would hold for vanilla transformers.
  • Because optimality needs $n \asymp \exp(\Delta^2/(2\sigma^2))$, the minimax regime is reached only for well-separated clusters; at practical separations the $n^{-1/4}$ generalization term dominates, which suggests the simulations operate in a generalization-dominated regime rather than the minimax one.
  • A testable corollary of the 'learns algorithms, not classifiers' reading: a transformer pretrained on well-separated Gaussian mixtures should degrade smoothly with cluster overlap (rate governed by the closest pair) when tested on heavier-tailed mixtures, rather than failing abruptly.
  • The guarantee assumes a spectral-clustering plus k-means++ initialization; testing random initializations would show how much of the claimed capability comes from the transformer itself rather than from a good starting point.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies whether pretrained Transformers can perform multi-class clustering on Gaussian mixture models by simulating Lloyd's algorithm (a special case of EM). It constructs Transformer weights that approximate the expectation and maximization steps of Lloyd's algorithm, states softmax universal-approximation bounds, gives an ERM generalization bound for the pretraining problem, and claims that with enough pretraining instances the empirical risk minimizer attains a minimax-optimal clustering rate matching an exponential lower bound in the signal-to-noise ratio. The paper also reports simulations on synthetic data varying separation, dimension, sample size, number of classes, and class imbalance.

Significance. If the central claims were fully established, the paper would make a useful contribution: it provides a constructive link between softmax attention and iterative clustering, an approximation lemma for multivariate functions by softmax networks, and a generalization bound for ERM-based pretraining. The experiments are reasonably extensive and the comparison with Lloyd's algorithm is informative. I do not regard the use of an external algorithm as a proof device as circular; such constructions are standard. However, the main 'minimax optimality' claim is currently not supported: the lower-bound target is attributed to a reference that does not contain it, its extension to the paper's loss and feasible set is asserted rather than proved, and the feasible set as written cannot yield the claimed exponential rate. The proof of Theorem 3.3 also conflicts with its own stated parameter scaling. These are load-bearing gaps rather than presentation issues.

major comments (4)
  1. [Section 2.2.1, Lemma 2.1 and Remark 2] The minimax lower bound is not established for the problem actually analyzed. Lemma 2.1 is cited to Yu et al. (2015), which is a paper on a variant of the Davis–Kahan theorem and contains no minimax lower bound for Gaussian mixture clustering; Remark 2 then asserts without proof that a 0–1 loss lower bound extends to the matrix loss L over Θ_A. Moreover, as written Θ_A = {A : Σ_{j=1}^N A_{ij}=1 for all i} enforces unit row sums, whereas the target P1(z) has row sums equal to the cluster sizes. For any A in this row-stochastic set, L(A,P1(z)) ≥ (N−k)/N by the triangle inequality, so the exponential lower bound cannot be a tight target for the matching upper bound. This needs a correct citation, a correct feasible set (presumably column-stochastic matrices), and a proof of the loss-transfer step.
  2. [Theorem 3.3 and Section B.4] The proof of Theorem 3.3 does not implement the theorem's stated scaling. The theorem states M ≍ n^{1/2}, but the proof in Section B.4 sets M = n^{1/4} and then concludes the rate √k n^{−1/4} C d √Polylog(n). With M = n^{1/4}, the approximation term √(log M / M) is of order n^{−1/8}, not n^{−1/4}, so the displayed conclusion does not follow from the preceding displayed inequality. The proof should be carried out with M ≍ n^{1/2}, or the theorem must be restated with the rate actually proved.
  3. [Appendix A, Lemma A.1 and its proof] The approximation lemma underlying the construction is not proved as written. Lemma A.1 is a statement about sigmoid networks, but its proof replaces Sigmoid with Softmax throughout and applies Softmax to the scalar [x^⊤,1]v, although Definition 2.1 defines Softmax only for vectors. Since Lemma A.2 and consequently Theorems 3.1–3.2 rely on Lemma A.1, a corrected proof or a precise definition of the scalar softmax/sigmoid convention is required before the softmax approximation results can be considered established.
  4. [Appendix A, Lemma A.3] The condition in Lemma A.3 appears to have the inequality direction reversed: it states a bound for M < (CR/R)^d · (1/ε^2) log(1+C/ε), but the approximation error contains 1/M, so the claimed approximation becomes meaningful only when M is sufficiently large. This affects the normalization step used in the construction for Theorem 3.2 and should be corrected.
minor comments (5)
  1. [Definition 2.1] The displayed SoftMax formula has a typographical error: the denominator in the last entry is written as Σ_{i=1}^d exp(x_d) instead of Σ_{i=1}^d exp(x_i).
  2. [Algorithm 2] The initialization algorithm attributes k-means++ to Kumar et al. (2004), but that reference is a (1+ε)-approximation algorithm for k-means; the k-means++ seeding method is due to Arthur and Vassilvitskii. The citation should be corrected.
  3. [Remark 6] Remark 6 refers to 'the non-activated Attention layer in Softmax+', but the model was defined as Transformer+; this is presumably a typo.
  4. [Section 4] The simulations remove the auxiliary matrix P from the input and use cross-entropy rather than the theoretical matrix loss, as the authors acknowledge in Section 5. The text that the experiments 'verified our theory' should be softened accordingly, since the experimental setup is not the theoretical setup.
  5. [Proposition 3.1] The statement of Proposition 3.1 omits the conditioning event E used in its proof in Section B.3; as written, the probability statement and the bound involving ‖μ^{(j)}_i‖_2 are not fully specified.

Circularity Check

1 steps flagged · score 2.0 of 10

No significant circularity: the transformer-to-EM derivation is constructive and the minimax claim is composed of external lower bounds and external Lloyd-error bounds; only a minor self-citation in the generalization proof is flagged.

  1. other [Appendix B.3, Proof of Proposition 3.1]
    "Then we obtain generalization bound under the event E using the proof machine created by Bai et al. (2024) J.2 He et al. (2025) Proposition 1, where we note that the multi-layered Transformer satisfies the following conditions ..."

    Proposition 3.1's generalization bound is the source of the n^{-1/4} term in Theorem 3.3, so the minimax-rate claim inherits this bound. The proof is imported from the authors' own prior work (He et al. 2025), although the external Bai et al. (2024) is cited in the same sentence and the paper lists the required Lipschitz/entropy conditions. This is a minor, partially inherited self-citation rather than a definitional reduction: the central claim still rests mainly on the external Lloyd/EM analysis (Lu & Zhou 2016) and on the lower bound, so the self-citation is not the sole load-bearing step.

full rationale

The derivation chain is largely non-circular. Theorems 3.1 and 3.2 construct a Transformer that approximates Lloyd's/EM steps with hand-set parameters, not parameters fitted to the test loss; Theorem 3.3 composes that approximation with an ERM generalization bound and an external Lloyd-error guarantee (Lu & Zhou 2016) to match an external lower bound. The Transformer class is not defined in terms of the loss L, and no fitted quantity is relabeled as a prediction. Two caveats, both correctness risks rather than circularity, should be weighed: (i) Lemma 2.1 attributes the minimax lower bound to Yu et al. (2015), which is a Davis-Kahan paper and states no such bound, and Remark 2 asserts without proof that the 0-1 lower bound extends to the paper's loss L over the row-stochastic set Theta_A; until a valid lower bound for this exact loss and feasible set is supplied, the 'matching upper bound' has no established target. (ii) The proof of Proposition 3.1 imports generalization machinery from the authors' own He et al. (2025); because Bai et al. (2024) is cited alongside and the conditions are listed, this is a minor inheritance, not a load-bearing self-citation. These findings justify a low circularity score despite the significant correctness concerns.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The paper's central results depend on several choices and imported results. The number of heads M, the number of layers L, the number of Lloyd iterations tau, and the softmax temperature scale are chosen by hand to make the proof work; they are not data-fitted but they are free in the sense that different choices change the final rate. The main axioms are the sub-Gaussian model, balanced clusters, the spectral initialization, the correctness of the minimax lower bound and its extension to the soft loss, and the generalization bound machinery borrowed from prior work, some of it by the present authors.

free parameters (4)
  • Number of attention heads M = M of order n^{1/2} in Theorem 3.3 (proof uses M = n^{1/4}, inconsistent)
    Chosen to balance softmax approximation error (sqrt(log M / M)) against generalization error; the theorem's final n^{-1/4} rate depends on this choice.
  • Number of layers L = L of order k log n
    Chosen to allow tau = O(log n) iterations of the EM simulator; any larger L would worsen the generalization bound.
  • Lloyd iterations tau = tau > 4 log n
    Set to ensure Lloyd's algorithm reaches the good event from Lu and Zhou (2016); the approximation error accumulates linearly in tau.
  • Softmax inverse temperature scale = C log N for a constant C
    Chosen so that softmax approximates hardmax with error N^{-C}; the overall N^{-1} or N^{-100} terms depend on this scale.
assumptions (6)
  • domain assumption Sub-Gaussian noise assumption (Assumption 2.6)
    Defines the generative model for the mixture; all probability bounds rely on it.
  • domain assumption Balanced clusters and separation: Delta <= min_{i != j} ||mu_i - mu_j||, each cluster size >= alpha n
    Defines the parameter space Theta_GM; the minimax lower bound and Lu-Zhou conditions require these.
  • domain assumption Existence of a good initialization via Algorithm 2 (spectral plus k-means++)
    Algorithm 2 is assumed to produce a valid initial membership that enters the transformer input through matrix P; the proof of optimality requires the Lu and Zhou (2016) good event.
  • ad hoc to paper The minimax lower bound of Lemma 2.1 and its extension to the soft-margin loss L
    Cited to Yu et al. (2015), which appears to be a mis-citation; the extension from 0-1 loss to L is asserted without proof in Remark 2.
  • domain assumption Generalization bound machinery from Bai et al. (2024) and He et al. (2025)
    The covering number, Lipschitz, and sub-Gaussian conditions for the transformer class are imported from these papers; Proposition 3.1 restates the bound.
  • standard math Pisier's sampling inequality and Bach's smooth function representation
    Used to prove Lemma A.1 and the softmax approximation; these are published results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Transformers versus the EM Algorithm in Multi-class Clustering." pith.science (2026). https://pith.science/paper/KNT7YGSA

@misc{pith2026250206007,
  author       = {Pith},
  title        = {Pith review of: Transformers versus the EM Algorithm in Multi-class Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KNT7YGSA}},
  note         = {Machine review of arXiv:2502.06007}
}
read the original abstract

LLMs demonstrate significant inference capacities in complicated machine learning tasks, using the Transformer model as its backbone. Motivated by the limited understanding of such models on the unsupervised learning problems, we study the learning guarantees of Transformers in performing multi-class clustering of the Gaussian Mixture Models. We develop a theory drawing strong connections between the Softmax Attention layers and the workflow of the EM algorithm on clustering the mixture of Gaussians. Our theory provides approximation bounds for the Expectation and Maximization steps by proving the universal approximation abilities of multivariate mappings by Softmax functions. In addition to the approximation guarantees, we also show that with a sufficient number of pre-training samples and an initialization, Transformers can achieve the minimax optimal rate for the problem considered. Our extensive simulations empirically verified our theory by revealing the strong learning capacities of Transformers even beyond the assumptions in the theory, shedding light on the powerful inference capacities of LLMs.

Figures

Figures reproduced from arXiv: 2502.06007 by the authors.

Figure 1
Figure 1. 4-Class Clustering with Different Minimum Distance, Data Dimension, and Number of Training Data. We train a small Transformer (layer = 3, head = 2, embedding = 64) and iterate for 300 steps for each different setting. Each point in the figure is evaluated on 512 testing data. We report the 10 runs averaged result with a shaded region representing the standard deviation. Each training sample is generated according to… view at source ↗
Figure 2
Figure 2. 4-Class Clustering with Different Number of Class and Inbalance Ratio. We train a small Transformer (layer = 3, head = 2, embedding = 64) and train for 300 steps for each differ￾ent setting. Each point in the figure is evaluated on 512 testing data. We report the 10 runs averaged result with a shaded region repre￾senting the standard deviation. Each training sample is generated according to isotropic Gaussian with c… view at source ↗
Figure 3
Figure 3. Comparision between Transformer and Lloyd’s Algo￾rithm. We compare the effect of the number of layers in Trans￾formers with the number of iterations τ in Lloyd’s algorithm under the same dataset configuration. We use a 6-class dataset, where each cluster contains 50 data points in a d = 10 dimensional space. Each training sample is generated according to isotropic Gaussian with covariances σ 2 I, where σ 2 ∼ Uniform… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Comparison of Concatenated Attention and Averaged Attention on Synthetic Dataset. Top: Performance Comparision on Minimum Distance Task. Bottom: Performance Comparision on Number of Data Task. We observe similar trend of performance between concatenated multihead atten…
Figure 5
Figure 5. Figure 5: Comparison of Concatenated Attention and Averaged Attention on Synthetic Dataset. Top: Performance Comparision on Number of Classes Task. Bottom: Performance Comparision on Inbalance Ratio Task. Again, we observe a similar performance trend between concatenated multihe…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 19 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  3. [3]

    V., and Warmuth, M

    Abernethy, J., Agarwal, A., Marinov, T. V., and Warmuth, M. K. A mechanism for sample-efficient in-context learning for sparse retrieval tasks. In International Conference on Algorithmic Learning Theory, pp.\ 3--46. PMLR, 2024

    work page 2024

  4. [4]

    Transformers learn to implement preconditioned gradient descent for in-context learning

    Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. Transformers learn to implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  5. [5]

    What learning algorithm is in-context learning? investigations with linear models

    Aky \"u rek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. What learning algorithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661, 2022

    arXiv 2022

  6. [6]

    Breaking the curse of dimensionality with convex neural networks

    Bach, F. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18 0 (1): 0 629--681, 2017

    work page 2017

  7. [7]

    Transformers as statisticians: Provable in-context learning with in-context algorithm selection

    Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36, 2024

    work page 2024

  8. [8]

    On the computational power of transformers and its implications in sequence modeling

    Bhattamishra, S., Patel, A., and Goyal, N. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286, 2020

    arXiv 2006

Show all 41 references
  1. [9]

    Bishop, C. M. and Nasrabadi, N. M. Pattern recognition and machine learning, volume 4. Springer, 2006

    2006

  2. [10]

    Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality

    Chen, S., Sheen, H., Wang, T., and Yang, Z. Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality. arXiv preprint arXiv:2402.19442, 2024 a

    2024 arXiv

  3. [11]

    How transformers utilize multi-head attention in in-context learning? a case study on sparse linear regression

    Chen, X., Zhao, L., and Zou, D. How transformers utilize multi-head attention in in-context learning? a case study on sparse linear regression. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 b

    2024

  4. [12]

    Giannou, A., Yang, L., Wang, T., Papailiopoulos, D., and Lee, J. D. How well can transformers emulate in-context newton's method? arXiv preprint arXiv:2403.03183, 2024

    2024 arXiv

  5. [13]

    Learning spectral methods by transformers

    He, Y., Cao, Y., Chen, H.-Y., Wu, D., Fan, J., and Liu, H. Learning spectral methods by transformers. arXiv preprint arXiv:2501.01312, 2025

    2025 arXiv

  6. [14]

    In-context convergence of transformers

    Huang, Y., Cheng, Y., and Liang, Y. In-context convergence of transformers. arXiv preprint arXiv:2310.05249, 2023

    2023 arXiv

  7. [15]

    T., Lv, J., and Peng, X

    Huang, Z., Hu, P., Zhou, J. T., Lv, J., and Peng, X. Partially view-aligned clustering. Advances in Neural Information Processing Systems, 33: 0 2892--2902, 2020

    2020

  8. [16]

    Vision transformers provably learn spatial structure

    Jelassi, S., Sander, M., and Li, Y. Vision transformers provably learn spatial structure. Advances in Neural Information Processing Systems, 35: 0 37822--37836, 2022

    2022

  9. [17]

    J., Lee, J

    Jeon, H. J., Lee, J. D., Lei, Q., and Roy, B. V. An information-theoretic analysis of in-context learning, 2024

    2024

  10. [18]

    A simple linear time (1+/spl epsiv/)-approximation algorithm for k-means clustering in any dimensions

    Kumar, A., Sabharwal, Y., and Sen, S. A simple linear time (1+/spl epsiv/)-approximation algorithm for k-means clustering in any dimensions. In 45th Annual IEEE Symposium on Foundations of Computer Science, pp.\ 454--462. IEEE, 2004

    2004

  11. [19]

    E., Papailiopoulos, D., and Oymak, S

    Li, Y., Ildiz, M. E., Papailiopoulos, D., and Oymak, S. Transformers as algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pp.\ 19565--19594. PMLR, 2023 a

    2023

  12. [20]

    How do transformers learn topic structure: Towards a mechanistic understanding

    Li, Y., Li, Y., and Risteski, A. How do transformers learn topic structure: Towards a mechanistic understanding. In International Conference on Machine Learning, pp.\ 19689--19729. PMLR, 2023 b

    2023

  13. [21]

    Image clustering with external guidance

    Li, Y., Hu, P., Peng, D., Lv, J., Fan, J., and Peng, X. Image clustering with external guidance. In Forty-first International Conference on Machine Learning, 2024 a . URL https://openreview.net/forum?id=JSYN891WnB

    2024

  14. [22]

    M., Fan, J., and Wang, M

    Li, Z., Cao, Y., Gao, C., He, Y., Liu, H., Klusowski, J. M., Fan, J., and Wang, M. One-layer transformer provably learns one-nearest neighbor in context. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 b

    2024

  15. [23]

    T., Goel, S., Krishnamurthy, A., and Zhang, C

    Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022

    2022 arXiv

  16. [24]

    Least squares quantization in pcm

    Lloyd, S. Least squares quantization in pcm. IEEE transactions on information theory, 28 0 (2): 0 129--137, 1982

    1982

  17. [25]

    and Zhou, H

    Lu, Y. and Zhou, H. H. Statistical and computational guarantees of lloyd's algorithm and its variants. arXiv preprint arXiv:1612.02099, 2016

    2016 arXiv

  18. [26]

    Ma, Q., Zheng, J., Li, S., and Cottrell, G. W. Learning representations for time series clustering. Advances in neural information processing systems, 32, 2019

    2019

  19. [27]

    Deep transformation-invariant clustering

    Monnier, T., Groueix, T., and Aubry, M. Deep transformation-invariant clustering. Advances in neural information processing systems, 33: 0 7945--7955, 2020

    2020

  20. [28]

    Scikit-learn: Machine learning in python

    Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12: 0 2825--2830, 2011

    2011

  21. [29]

    Attention is turing-complete

    P \'e rez, J., Barcel \'o , P., and Marinkovic, J. Attention is turing-complete. Journal of Machine Learning Research, 22 0 (75): 0 1--35, 2021

    2021

  22. [30]

    Maurey-Schwartz

    Pisier, G. Remarques sur un r \'e sultat non publi \'e de b. maurey. S \'e minaire d'Analyse fonctionnelle (dit" Maurey-Schwartz") , pp.\ 1--12, 1981

    1981

  23. [31]

    Sun, L., Huang, Z., Peng, H., Wang, Y., Liu, C., and Yu, P. S. Lsenet: Lorentz structural entropy neural network for deep graph clustering. arXiv preprint arXiv:2405.11801, 2024

    2024 arXiv

  24. [32]

    Attention is all you need

    Vaswani, A. Attention is all you need. Advances in Neural Information Processing Systems, 2017

    2017

  25. [33]

    Information-theoretic methods for high-dimensional statistics

    Wu, Y. Information-theoretic methods for high-dimensional statistics. Lecture notes, Yale University, New Haven, CT, 2020

    2020

  26. [34]

    Self-attention networks can process bounded hierarchical languages

    Yao, S., Peng, B., Papadimitriou, C., and Narasimhan, K. Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115, 2021

    2021 arXiv

  27. [35]

    Yu, Y., Wang, T., and Samworth, R. J. A useful variant of the davis--kahan theorem for statisticians. Biometrika, 102 0 (2): 0 315--323, 2015

    2015

  28. [36]

    S., Reddi, S

    Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077, 2019

    1912 arXiv

  29. [37]

    and Cao, Y

    Zhang, C. and Cao, Y. Transformer learns optimal variable selection in group-sparse classification. In International Conference on Learning Representations, 2025

    2025

  30. [38]

    Zhang, R., Frei, S., and Bartlett, P. L. Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.09927, 2023

    2023 arXiv

  31. [39]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  32. [40]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  33. [41]

    Recent efforts are devoted to understand the learning capacities of Transformers at the fundamental level

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.