Pith. sign in

REVIEW 1 major objections 4 minor 46 references

Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models

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

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

Pith's one-line read This paper claims that high-order moment tensors of the form $\sum_i w_i v_i^{\otimes m}$ can be approximated implicitly in polynomial time via sequential tensor computations, and that this yields the first poly(d,k)-time learning…

desk verdict A wide and well-executed framework for implicit moment estimation, with two sound applications (GMM density estimation, ReLU learning); the third headline claim (poly(d,k) MLR density estimation) rests on a false tensor identity in Section 4.4. read the letter →

arxiv 2411.15669 v2 pith:H7TCKDKC submitted 2024-11-23 cs.DS cs.LGmath.STstat.MLstat.TH

Ilias Diakonikolas , Daniel M. Kane This is my paper · ORCID
classification cs.DScs.LGmath.STstat.MLstat.TH
keywords implicitmomenttensorestimationmethodofmomentsmixtureslinearregressionssphericalGaussiansone-hidden-layerneuralnetworksReLUactivationssequentialcomputationHermitetensors
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

This paper claims that moment tensors of the form $M_m = \sum_i w_i v_i^{\otimes m}$, which are too large to write down explicitly, can still be approximated implicitly in polynomial time, provided each moment has a sequential tensor computation unbiased estimator with bounded variance. On this engine it builds the first polynomial-time (in dimension $d$ and number of components $k$) learning algorithms for mixtures of linear regressions, density estimation for mixtures of spherical Gaussians with bounded means, clustering spherical Gaussians under near-optimal separation, and PAC learning positive sums of ReLU or cosine activations. If these algorithms are correct, they resolve or substantially advance several open problems in high-dimensional latent-variable learning. One of the three headline applications, however, rests on a tensor identity in Section 4.4 that is false as written, so that particular theorem is not established.

What carries the argument

The central object is the sequential tensor computation (STC): an arithmetic circuit that builds an order-$t$ tensor using only scalar multiplication, addition of same-order tensors, and tensoring an order-$k$ tensor with a vector. The proof uses recursive pseudo-projections (compositions of projections onto top singular subspaces with isometries) to represent the $k$-dimensional spans $W_t$ of the vectors $v_i^{\otimes t}$, plus an extended Hermite tensor $H_n(x,y)$ whose expectation over $y$ yields the standard Hermite tensor and which is itself an STC of size $O(n)$. Together these let the algorithm approximate inner products with $M_m$ without ever materializing the $d^m$-dimensional tensors.

What would settle it

Compute both sides of the disputed identity at $d=1$, $a=0$, $b=1$, $n=2$ with a single component $\beta_1 \neq 0$ and $w_1=1$; the left-hand side is non-zero by direct evaluation, while the right-hand side vanishes because the inner product with $e_y^{\otimes 2}$ against the identity-tensor factor is zero.

Watch

Extended reading notes

Core claim

The central claim is Proposition 3.2: given distributions whose expectations are the moment tensors $M_t$, computable as sequential tensor computations (arithmetic circuits using only scalar multiplication, addition, and tensoring by vectors), and given a tensor $T$ that is itself the expectation of such a computation with bounded second moment, there is a poly$(N,S,d)$ algorithm that approximates $\langle T, M_m\rangle$ with expected squared error bounded by $\mathrm{poly}(k,m,d,V,1/\tau,1+\sum_i w_i)(1+\max_i\|v_i\|)^{2m}/\sqrt{N}$. This implicit estimation is achieved by maintaining $k$-dimensional subspaces $W_t$ spanned by the $v_i^{\otimes t}$ via recursive pseudo-projections, bootstrapping from low to high order, so the tensors never appear explicitly. The paper then shows that in three learning problems the relevant Hermite coefficients are moment tensors of exactly this form, yielding the claimed poly$(d,k)$ learners. The proof of the mixture-of-linear-regressions density-estimation result, however, contains a false identity relating parameter moments to Hermite inner products, so that application is not established as written.

Load-bearing premise

The mixture-of-linear-regressions density-estimation theorem relies on the identity in Section 4.4 relating parameter moments to Hermite inner products, and that identity is false because the identity tensor annihilates the y-direction component; without a corrected identity the proof of that theorem collapses.

Editorial extensions

If this is right

  • Density estimation for mixtures of linear regressions would run in poly$(d,k,1/\epsilon)$ time (Theorem 4.22), assuming the proof's tensor identity holds.
  • Density estimation for mixtures of spherical Gaussians with means of norm $O(\sqrt{\log k})$ runs in poly$(d,k,1/\epsilon)$ time (Theorem 4.16).
  • Clustering spherical Gaussian mixtures under optimal separation $\Omega(\sqrt{\log(k/\epsilon)})$ is possible in poly$(d,k,1/\epsilon)$ time when largest and smallest pairwise distances are comparable (Theorem 4.19).
  • Positive linear combinations of ReLU activations are PAC-learnable in time poly$(d,k)2^{\mathrm{poly}(1/\epsilon)}$ (Corollary 4.9); for cosine activations of bounded frequency, time is $2^{O(1/\gamma^2)}\mathrm{poly}(dk/\epsilon)$ (Corollary 4.10).
  • The general implicit moment estimation engine (Proposition 3.2) provides a template for other latent-variable problems whose moment tensors admit STC unbiased estimators.

Reading between the lines

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

  • If the false identity in Section 4.4 can be repaired by an alternative expansion, the MLR density-estimation result would follow; a natural test is to verify the identity numerically for small $d,a,b,n$ before attempting a fix.
  • The recursion through top-$k$ singular subspaces suggests a general principle: any sequence of rank-$k$ moment tensors with bounded-variance STC estimators is learnable in poly$(k)$ queries, independent of the ambient dimension $d$.
  • The extended Hermite tensor trick – replacing each identity factor by a tensor power of a single random Gaussian – could reduce the cost of Hermite-based moment methods in other settings where the naive rank expansion is super-polynomial.
  • The optimal-separation clustering result without the 'comparable distances' condition is left to a recursive argument from prior work, so removing that extra assumption is a direct open test of the technique's reach.
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

1 major / 4 minor

Summary. The paper develops a general framework for implicit moment tensor estimation: for tensors M_m = sum_i w_i v_i^{⊗m}, it gives an algorithm (Proposition 3.2) that approximates inner products <T(X), M_m> in poly(N,S,d) time, provided unbiased estimators for the relevant moment tensors are available as Sequential Tensor Computations with bounded covariance. The algorithm uses recursive pseudo-projections to avoid ever forming the full high-order tensors. This framework is then applied to three families of latent-variable models: positive linear combinations of non-linear activations, mixtures of spherical Gaussians, and mixtures of linear regressions. The first two applications are argued through Hermite expansions and the extended Hermite tensor H_n(x,y). The MLR density-estimation application is argued in Section 4.4 using a purported equality between a Hermite coefficient and an inner product involving the implicit moment tensor. That equality is false as written, so the MLR theorem is not established.

Significance. Proposition 3.2 is an elegant and quite general algorithmic statement that genuinely extends the implicit moment approach of [LL22]; if the proof is correct, it is a substantial contribution with likely further uses. The STC formalism and the second-moment bound for extended Hermite tensors (Definition 4.1 and Lemma 4.3) are concrete and valuable. The GMM density-estimation and parameter-estimation results, as well as the ReLU/cosine activation results, appear to be based on the central engine without relying on the broken tensor identity. However, the MLR density-estimation result is one of the paper's three headline claims, and its proof is invalid as written; the false identity is the only bridge from Hermite coefficients to the moment tensors estimated by Proposition 3.2. The paper is self-contained in its derivations rather than circular: the estimators are unbiased by construction and the error analysis is carried out independently of the target conclusions.

major comments (1)
  1. The proof of Theorem 4.22 contains a false tensor identity in the displayed derivation of <T_n, H_n(X)>. The authors write sum_i w_i ||β_i||^{2b} <β_i^{⊗a} ⊗ e_y^{⊗(n-a)}, H_n(X)> = <M_{a+2b} ⊗ e_y^{⊗(n-a)}, H_n(X) ⊗ I_d^{⊗b}>. This is dimensionally inconsistent: the left-hand side is an inner product of order-n tensors, while the right-hand side is an inner product of order-(n+2b) tensors. Moreover, H_n(X) is defined on R^d, whereas e_y is a unit vector in the y-direction of R^{d+1}; under the natural embedding of R^d into R^{d+1}, the added I_d factors are contracted against the e_y slots and the right-hand side vanishes for b>0, while the left-hand side in general does not. An explicit instance is d=1, a=0, b=1, n=2 and β_i=1, where the left side is a nonzero multiple of (X^2-1)/√2 and the right side is 0. This identity is the only step connecting the Hermite coefficient T_n to the implicit moment tensor M_{a+2b} that Proposition 3.2 can estimate, so Theorem 4.22 and the corresponding claim in the abstract are not established as written. The defect appears localized: I did not find a similar issue in the proofs of Proposition 3.2, Theorem 4.7, or Theorem 4.16.
minor comments (4)
  1. In the proof of Claim 3.10, the displayed line ||M_m - P_m(M_m)||_2 = sum_i sqrt(w_i) ||x_i,m - P_m(x_i,m)||_2 should be an inequality by the triangle inequality, not an equality.
  2. The identity H_n(x,y) = Re((x+iy)^{⊗n})/√n! should explicitly state that the tensor power and real part are taken entrywise; as written, the expression is ambiguous.
  3. The reference list has a formatting inconsistency: '[R V17]' appears with a space in the author name and should be '[RV17]' or similar.
  4. The reduction at the start of the proof of Theorem 4.22 ('By dividing the y-values by 2') is terse; the authors should state explicitly that this is a known coordinate scaling and that a sampler for the scaled distribution is converted back to a sampler for the original distribution.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the implicit moment tensor framework and its learning applications are self-contained reductions from unbiased STC estimators; the MLR Hermite-to-moment identity is a localized correctness gap, not a circular step.

full rationale

The paper's central claim, Proposition 3.2, is derived from an explicit algorithm that estimates M_2 from samples of S_2, bootstraps recursive pseudo-projections from samples of S_{2r+2}, and evaluates the inner product of the resulting compressed estimators. The proof bounds the projection error eta_r using Lemma 3.9 and standard concentration arguments; no target quantity is assumed, fitted, or defined in terms of the conclusion. The learning applications (Theorems 4.7, 4.16, 4.19, and 4.22) instantiate the STC hypotheses with unbiased estimators such as Equation (12) and Lemma 4.23, and then apply Hermite orthogonality; these are genuine reductions rather than redescriptions of the goal. Self-citations to [DK20], [DK24], and [Kan21] supply baseline complexity bounds and parameter-free facts (e.g., E[H_n(N(mu,I))] = mu^{otimes n}/sqrt{n!} and the ReLU Hermite coefficients), which are independently checkable and do not carry the proof's load. The only notable defect is in Section 4.4: the identity connecting sum_i w_i ||beta_i||^{2b} <beta_i^{otimes a} otimes e_y^{otimes(n-a)}, H_n(X)> to <M_{a+2b} otimes e_y^{otimes(n-a)}, H_n(X) otimes I_d^{otimes b}> is dimensionally inconsistent as written, since the e_y slots appear to be contracted against the identity tensor on R^d. This threatens the proof of Theorem 4.22 as written, but it is an algebraic correctness gap, not an equivalence-by-construction or a fitted-parameter renamed as a prediction. Hence no circularity is present; the localized MLR issue should be weighed as a correctness risk rather than a circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 1 invented entities

The central claim rests on standard Hermite/Gaussian analysis, distributional assumptions on the data, and the framework condition that unbiased STC estimators with bounded covariance exist. No parameters are fitted and no new physical entities are postulated.

assumptions (7)
  • standard math Hermite analysis, Gaussian hypercontractivity, Weyl's inequality, and standard concentration bounds used throughout Sections 3 and 4.
    Unproved background facts (Fact 2.3, Fact 2.4, etc.) that the proofs rely on.
  • domain assumption Samples x are drawn from N(0,I) in MLR and activation learning; spherical GMM components have identity covariance.
    Definitions 4.6, 4.13, 4.20; the algorithms and STC estimators are built on Gaussian structure.
  • domain assumption For GMM density estimation, component means are bounded by O(sqrt(log k)).
    Theorem 4.16 and its proof use this to bound the tail of the Hermite expansion and the STC covariance.
  • domain assumption For GMM parameter estimation, separation s >= C sqrt(log(1/(alpha w_min))) and max pairwise distance is O(min pairwise distance).
    Theorem 4.19; the bounded-ratio condition is extra compared to LL22 and is omitted from the abstract.
  • domain assumption For MLR density estimation, B = max ||beta_i|| <= 1 and sigma <= 1.
    Theorem 4.22; necessary for the eigenvalue bound gamma <= 1 - sigma^2/2 and the sample complexity.
  • domain assumption For activations, weights are positive, activation is known, and Hermite coefficients satisfy the lower bound of Theorem 4.7.
    Definition 4.5 and Theorem 4.7; the coefficient lower bound is assumed, not derived.
  • domain assumption The moment tensors M_t admit sequential tensor computations with mean M_t and bounded covariance V (input condition of Proposition 3.2).
    This is the framework condition of Prop 3.2, verified for each application via Lemmas 4.3, 4.23, and Claim 4.18.
invented entities (1)
  • Extended Hermite tensor H_n(x,y)
    purpose: Represents H_n(x) as E_Y[H_n(x,Y)] and is computable by a sequential tensor computation of size O(n), enabling implicit moment estimation in the Hermite basis.
    A mathematical construction (Definition 4.1), not a physical entity; it has no independent empirical evidence, but it is not a postulated physical degree of freedom.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models." pith.science (2026). https://pith.science/paper/H7TCKDKC

@misc{pith2026241115669,
  author       = {Pith},
  title        = {Pith review of: Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H7TCKDKC}},
  note         = {Machine review of arXiv:2411.15669}
}
abstract

We study the task of learning latent-variable models. A common algorithmic technique for this task is the method of moments. Unfortunately, moment-based approaches are hampered by the fact that the moment tensors of super-constant degree cannot even be written down in polynomial time. Motivated by such learning applications, we develop a general efficient algorithm for {\em implicit moment tensor computation}. Our framework generalizes the work of~\cite{LL21-opt} which developed an efficient algorithm for the specific moment tensors that arise in clustering mixtures of spherical Gaussians. By leveraging our implicit moment estimation algorithm, we obtain the first $\mathrm{poly}(d, k)$-time learning algorithms for the following models. * {\bf Mixtures of Linear Regressions} We give a $\mathrm{poly}(d, k, 1/\epsilon)$-time algorithm for this task, where $\epsilon$ is the desired error. * {\bf Mixtures of Spherical Gaussians} For density estimation, we give a $\mathrm{poly}(d, k, 1/\epsilon)$-time learning algorithm, where $\epsilon$ is the desired total variation error, under the condition that the means lie in a ball of radius $O(\sqrt{\log k})$. For parameter estimation, we give a $\mathrm{poly}(d, k, 1/\epsilon)$-time algorithm under the {\em optimal} mean separation of $\Omega(\log^{1/2}(k/\epsilon))$. * {\bf Positive Linear Combinations of Non-Linear Activations} We give a general algorithm for this task with complexity $\mathrm{poly}(d, k) g(\epsilon)$, where $\epsilon$ is the desired error and the function $g$ depends on the Hermite concentration of the target class of functions. Specifically, for positive linear combinations of ReLU activations, our algorithm has complexity $\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/\epsilon)}$.

Figures

Figures reproduced from arXiv: 2411.15669 by the authors.

Figure 1
Figure 1. The upper circuit represents the original Sequential Tensor Computation (STC). The [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 45 canonical work pages

  1. [1]

    Ashtiani, S

    [ABH+18] H. Ashtiani, S. Ben-David, N. J. A. Harvey, C. Liaw, A. Mehrabian, and Y. Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. In Advances in Neural Information Processing Systems 31: An- nual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 , pages 3416–3425,

    work page 2018

  2. [7]

    [CLS20] S. Chen, J. Li, and Z. Song. Learning mixtures of linear regressions in subexponential time via fourier moments. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 , pages 587–600. ACM,

    work page 2020

  3. [12]

    Diakonikolas, S

    36 [DKPP24] I. Diakonikolas, S. Karmalkar, S. Pang, and A. Potechin. Sum-of-squares lower bounds for non-gaussian component analysis. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024 ,

    work page 2024

  4. [15]

    Diakonikolas, D

    [DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , pages 73–84,

    work page 2017

  5. [19]

    Goel and A

    [GK19] S. Goel and A. R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference on Learning Theory, COLT 2019 , pages 1470–1499,

    work page 2019

  6. [20]

    [GKKT17] S. Goel, V. Kanade, A. R. Klivans, and J. Thaler. Reliably learning the relu in poly- nomial time. In Proceedings of the 30th Conference on Learning Theory, COLT 2017 , pages 1004–1042,

    work page 2017

  7. [21]

    [GKL W19] R. Ge, R. Kuditipudi, Z. Li, and X. Wang. Learning two-layer neural networks with symmetric inputs. In 7th International Conference on Learning Representations, ICLR 2019,

    work page 2019

  8. [22]

    [GLM18] R. Ge, J. D. Lee, and T. Ma. Learning one-hidden-layer neural networks with landscape design. In 6th International Conference on Learning Representations, ICLR 2018,

    work page 2018

Show all 46 references
  1. [25]

    Hardt and E

    [HP15] M. Hardt and E. Price. Tight bounds for learning a mixture of two gaussians. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , pages 753–760,

    2015

  2. [27]

    [KC19] J

    Also available at https://arxiv.org/abs/2007.05912. [KC19] J. Kwon and C. Caramanis. EM converges for a mixture of many linear regressions. CoRR, abs/1905.12106,

    2007 arXiv

  3. [28]

    [KSS18] P. K. Kothari, J. Steinhardt, and D. Steurer. Robust moment estimation and im- proved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 , pages 1035–1046,

    2018

  4. [29]

    [Liu22] A. Liu. Clustering mixtures with almost optimal separation in polynomial time. Con- ference talk at STOC 2022,

    2022

  5. [30]

    [Liu24] A

    Available at https://www.youtube.com/watch?v= xkU5gSHGar4. [Liu24] A. Liu. Clustering mixtures with almost optimal separation in polynomial time. Invited talk at Workshop on New Frontiers in Robust Statistics, TTI-Chicago, June 2024,

    2024

  6. [31]

    [LL18] Y

    Available at http://www.iliasdiakonikolas.org/ttic-robust24/Liu.pdf. [LL18] Y. Li and Y. Liang. Learning mixtures of linear regressions with nearly optimal com- plexity. In Conference On Learning Theory, COLT 2018 , volume 75 of Proceedings of Machine Learning Research, pages ...

    2018

  7. [32]

    Liu and J

    [LL22] A. Liu and J. Li. Clustering mixtures with almost optimal separation in poly- nomial time. In STOC ’22: 54th Annual ACM SIGACT Symposium on The- ory of Computing, 2022 , pages 1248–1261,

    2022

  8. [33]

    [LS17] J

    Full version available at https://arxiv.org/abs/2112.00706. [LS17] J. Li and L. Schmidt. Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65 of Proceedings o...

    2017 arXiv

  9. [35]

    [MST+20] B

    Available at https://arxiv.org/abs/2410.03477. [MST+20] B. Mildenhall, P. P. Srinivasan, M. Tancik, J. T. Barron, R. Ramamoorthi, and R. Ng. Nerf: Representing scenes as neural radiance fields for view synthesis. In Computer Vision - ECCV 2020, 2020, Proceedings, Part I , volu...

    arXiv

  10. [37]

    Regev and A

    [R V17] O. Regev and A. Vijayaraghavan. On learning mixtures of well-separated gaussians. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , pages 85–96,

    2017

  11. [38]

    Sedghi, M

    [SJA16] H. Sedghi, M. Janzamin, and A. Anandkumar. Provable tensor methods for learning mixtures of generalized linear models. In Proceedings of the 19th International Confer- ence on Artificial Intelligence and Statistics, AISTATS 2016 , pages 1223–1231,

    2016

  12. [39]

    Sitzmann, J

    [SMB+20] V. Sitzmann, J. N. P. Martel, A. W. Bergman, D. B. Lindell, and G. Wetzstein. Implicit neural representations with periodic activation functions. In Advances in Neural Infor- mation Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020...

    2020

  13. [40]

    [SOAJ14] A. T. Suresh, A. Orlitsky, J. Acharya, and A. Jafarpour. Near-optimal-sample estima- tors for spherical Gaussian mixtures. In NIPS 2014 , pages 1395–1403,

    2014

  14. [42]

    [SZB21] M. J. Song, I. Zadik, and J. Bruna. On the cryptographic hardness of learning sin- gle periodic neurons. In Advances in Neural Information Processing Systems 34: An- nual Conference on Neural Information Processing Systems 2021, NeurIPS 2021 , pages 29602–29615,

    2021

  15. [43]

    Vargas, C

    [VPHA24] E. Vargas, C. V. Correa P., C. Hinojosa, and H. Arguello. Biper: Binary neural networks using a periodic function. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2024, 2024 , pages 5684–5693. IEEE,

    2024

  16. [45]

    Zhong, P

    [ZJD16] K. Zhong, P. Jain, and I. S. Dhillon. Mixed linear regression with multiple components. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Con- ference on Neur...

    2016

  17. [46]

    Zhang, J

    [ZLJ16] Y. Zhang, J. D. Lee, and M. I. Jordan. L1-regularized neural networks are improperly learnable in polynomial time. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016 , pages 993–1001,

    2016

  18. [47]

    Zhong, Z

    [ZSJ+17] K. Zhong, Z. Song, P. Jain, P. L. Bartlett, and I. S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , pages 4140–4149,

    2017

  19. [1894]

    [RNM+21] S. Rai, W. L. Neto, Y. Miyasaka, X. Zhang, M. Yu, Q. Yi, M. Fujita, G. B. Manske, M. F. Pontes, L. S. da Rosa, M. S. de Aguiar, P. F. Butzen, P.-C. Chien, Y.-S. Huang, H.-R. Wang, J.-. R. Jiang, J. Gu, Z. Zhao, Z. Jiang, D. Z. Pan, B. A. Abreu, I. Cam- pos, A. A. S. B...

    2021

  20. [1970]

    Bruna, O

    [BRST21] J. Bruna, O. Regev, M. J. Song, and Y. Tang. Continuous L WE. In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021 , pages 694–707. ACM,

    2021

  21. [1975]

    Gupte, N

    [GVV22] A. Gupte, N. Vafa, and V. Vaikuntanathan. Continuous L WE is as hard as L WE & applications to learning gaussian mixtures. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, 2022 , pages 1162–1173. IEEE,

    2022

  22. [1989]

    Daniely, R

    [DFS16] A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural net- works: The power of initialization and a dual view on expressivity. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 201...

    2016

  23. [2002]

    Vempala and J

    [VW19] S. Vempala and J. Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and SQ lower bounds. In Conference on Learning Theory, COLT 2019, pages 3115–3117,

    2019

  24. [2005]

    Bakshi, R

    [BJW19] A. Bakshi, R. Jayaram, and D. P. Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, COLT 2019 , pages 195–268,

    2019

  25. [2006]

    [GGJ+20] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. R. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 , volume 119 of Proceedings o...

    2020

  26. [2008]

    [CDG+23] S. Chen, Z. Dou, S. Goel, A. R. Klivans, and R. Meka. Learning narrow one-hidden- layer relu networks. CoRR, abs/2304.10524,

    arXiv

  27. [2013]

    [HL18] S. B. Hopkins and J. Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 , pages 1021–1034,

    2018

  28. [2014]

    [SVWX17] L. Song, S. S. Vempala, J. Wilmes, and B. Xie. On the complexity of learning neural networks. In Advances in Neural Information Processing Systems 30: Annual Confer- ence on Neural Information Processing Systems 2017 , pages 5514–5522,

    2017

  29. [2015]

    [Kan21] D. M. Kane. Robust learning of mixtures of gaussians. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2021 , pages 1246–1258. SIAM,

    2021

  30. [2016]

    Diakonikolas and D

    [DK20] I. Diakonikolas and D. M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 , pages 184–195,

    2020

  31. [2017]

    [DKS18] I

    Full version at http://arxiv.org/abs/1611.03473. [DKS18] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 , ...

    2018 arXiv

  32. [2018]

    [FOS06] J

    Full version available at https://arxiv.org/abs/1711.07211. [FOS06] J. Feldman, R. O’Donnell, and R. Servedio. PAC learning mixtures of Gaussians with no separation assumption. In COLT, pages 20–34,

    arXiv

  33. [2019]

    Diakonikolas, D

    [DKKZ20] I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and SQ lower bounds for PAC learning one-hidden-layer relu networks. In Conference on Learning Theory, COLT 2020 , volume 125 of Proceedings of Machine Learning Research, pages 1514–1539. PMLR,

    2020

  34. [2020]

    [DK24] I

    Full version available at https://arxiv.org/abs/2012.07774. [DK24] I. Diakonikolas and D. M. Kane. Efficiently learning one-hidden-layer relu networks via Schur polynomials. In The Thirty Seventh Annual Conference on Learning Theory , volume 247 of Proceedings of Machine Learn...

    2012 arXiv

  35. [2021]

    [CKM21] S. Chen, A. R. Klivans, and R. Meka. Learning deep relu networks is fixed-parameter tractable. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 696–707. IEEE,

    2021

  36. [2022]

    35 [Che20] S. Chen. Learning mixtures of linear regressions in subexponential time via fourier moments. Conference talk at STOC 2020,

    2020

  37. [2023]

    Diakonikolas, D

    [DKRS23] I. Diakonikolas, D. Kane, L. Ren, and Y. Sun. SQ lower bounds for non-gaussian com- ponent analysis with weaker assumptions. In Advances in Neural Information Process- ing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023 ,

    2023

  38. [2024]

    Diakonikolas, D

    [DKPZ23] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. SQ lower bounds for learning mixtures of separated and bounded covariance gaussians. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023 , volume 195 of Proceedings of Machine Learning Research, p...

    2023

Pith tools

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