{"total":29,"rows":[{"id":"2202.05258","title":"Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks","created":"2022-02-10","cited_by_count":28,"area":null},{"id":"2101.08303","title":"From Local Pseudorandom Generators to Hardness of Learning","created":"2021-01-20","cited_by_count":24,"area":null},{"id":"2105.08675","title":"The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality","created":"2021-05-18","cited_by_count":22,"area":null},{"id":"2402.04084","title":"Provably learning a multi-head attention layer","created":"2024-02-06","cited_by_count":21,"area":null},{"id":"2201.08514","title":"How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis","created":"2022-01-21","cited_by_count":19,"area":null},{"id":"2406.01461","title":"Hardness of Learning Neural Networks under the Manifold Hypothesis","created":"2024-06-03","cited_by_count":18,"area":null},{"id":"2310.16173","title":"On the Convergence and Sample Complexity Analysis of Deep Q-Networks with $\\epsilon$-Greedy Exploration","created":"2023-10-24","cited_by_count":17,"area":null},{"id":"2107.10209","title":"Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations","created":"2021-07-21","cited_by_count":15,"area":null},{"id":"2204.01368","title":"Training Fully Connected Neural Networks is $\\exists\\mathbb{R}$-Complete","created":"2022-04-04","cited_by_count":15,"area":null},{"id":"2206.12802","title":"Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis","created":"2022-06-26","cited_by_count":15,"area":null},{"id":"2304.10524","title":"Learning Narrow One-Hidden-Layer ReLU Networks","created":"2023-04-20","cited_by_count":14,"area":null},{"id":"2402.03625","title":"Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time","created":"2024-02-06","cited_by_count":11,"area":null},{"id":"2302.07426","title":"Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy","created":"2023-02-15","cited_by_count":10,"area":null},{"id":"2502.09525","title":"Robust Learning of Multi-index Models via Iterative Subspace Approximation","created":"2025-02-13","cited_by_count":9,"area":null},{"id":"2307.12496","title":"A faster and simpler algorithm for learning shallow networks","created":"2023-07-24","cited_by_count":7,"area":null},{"id":"2111.04727","title":"Efficiently Learning Any One Hidden Layer ReLU Network From Queries","created":"2021-11-08","cited_by_count":6,"area":null},{"id":"2411.15669","title":"Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models","created":"2024-11-23","cited_by_count":6,"area":null},{"id":"2107.08090","title":"Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time","created":"2021-07-16","cited_by_count":4,"area":null},{"id":"2305.00322","title":"Toward $L_\\infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields","created":"2023-04-29","cited_by_count":4,"area":null},{"id":"2307.12840","title":"Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials","created":"2023-07-24","cited_by_count":4,"area":null},{"id":"2502.16021","title":"Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees","created":"2025-02-22","cited_by_count":4,"area":null},{"id":"2209.15265","title":"Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery","created":"2022-09-30","cited_by_count":3,"area":null},{"id":"2305.16508","title":"Most Neural Networks Are Almost Learnable","created":"2023-05-25","cited_by_count":2,"area":null},{"id":"2311.10972","title":"Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes","created":"2023-11-18","cited_by_count":2,"area":null},{"id":"2304.02972","title":"Training a Two Layer ReLU Network Analytically","created":"2023-04-06","cited_by_count":1,"area":null},{"id":"2410.03477","title":"On the Hardness of Learning One Hidden Layer Neural Networks","created":"2024-10-04","cited_by_count":1,"area":null},{"id":"2102.09798","title":"Training Neural Networks is $\\exists\\mathbb R$-complete","created":"2021-02-19","cited_by_count":0,"area":null},{"id":"2106.06097","title":"Neural Optimization Kernel: Towards Robust Deep Learning","created":"2021-06-11","cited_by_count":0,"area":null},{"id":"2110.04523","title":"An Empirical Study on Compressed Decentralized Stochastic Gradient Algorithms with Overparameterized Models","created":"2021-10-09","cited_by_count":0,"area":null}],"next_cursor":null}