Buchumschlag

On the Hardness of Learning One Hidden Layer Neural Networks

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Li, Shuchen, Zadik, Ilias, Zampetakis, Manolis
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Computational Complexity Statistics Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
von: Tsirkas, Konstantinos, et al.
Veröffentlicht: (2026)

Transfer Learning Beyond Bounded Density Ratios
von: Kalavasis, Alkis, et al.
Veröffentlicht: (2024)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
von: Chen, Siyu, et al.
Veröffentlicht: (2025)

Stable Algorithms Lower Bounds for Estimation
von: Yu, Xifan, et al.
Veröffentlicht: (2026)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
von: Gamarnik, David, et al.
Veröffentlicht: (2023)

Improved Hardness Results for Learning Intersections of Halfspaces
von: Tiegel, Stefan
Veröffentlicht: (2024)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
von: Hollender, Alexandros, et al.
Veröffentlicht: (2023)

Cryptographic Hardness of Score Estimation
von: Song, Min Jae
Veröffentlicht: (2024)

Learning High-dimensional Gaussians from Censored Data
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2024)

Causal Discovery under Latent Class Confounding
von: Mazaheri, Bijan, et al.
Veröffentlicht: (2023)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
von: Wein, Alexander S.
Veröffentlicht: (2025)

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
von: Lee, Jane H., et al.
Veröffentlicht: (2024)

Low degree conjecture implies sharp computational thresholds in stochastic block model
von: Ding, Jingqiu, et al.
Veröffentlicht: (2025)

Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening
von: Kalavasis, Alkis, et al.
Veröffentlicht: (2024)

Near-Optimal Learning and Planning in Separated Latent MDPs
von: Chen, Fan, et al.
Veröffentlicht: (2024)

What is Learnable in Valiant's Theory of the Learnable?
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
von: Lou, Mengqi, et al.
Veröffentlicht: (2025)

Smoothed Analysis of Learning from Positive Samples
von: Lee, Jane H., et al.
Veröffentlicht: (2025)

Derandomizing Multi-Distribution Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2024)

A Note on Non-Negative $L_1$-Approximating Polynomials
von: Lee, Jane H., et al.
Veröffentlicht: (2026)

Efficient Pauli channel estimation with logarithmic quantum memory
von: Chen, Sitan, et al.
Veröffentlicht: (2023)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
von: Zhao, Haimeng, et al.
Veröffentlicht: (2025)

A Bayesian Proof and Interpretation of Talagrand's Majorizing Measure Theorem
von: Zadik, Ilias
Veröffentlicht: (2026)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
von: Lovig, Max, et al.
Veröffentlicht: (2025)

Information-Theoretic Bounds and Task-Centric Learning Complexity for Real-World Dynamic Nonlinear Systems
von: Bulusu, Sri Satish Krishna Chaitanya, et al.
Veröffentlicht: (2025)

On Computationally Efficient Multi-Class Calibration
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
von: Kelner, Jonathan, et al.
Veröffentlicht: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
von: Luo, Yuetian, et al.
Veröffentlicht: (2023)

Detection of local geometry in random graphs: information-theoretic and computational limits
von: Bok, Jinho, et al.
Veröffentlicht: (2026)

What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness
von: Cai, Yang, et al.
Veröffentlicht: (2025)

Tensor cumulants for statistical inference on invariant distributions
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
von: Kalavasis, Alkis, et al.
Veröffentlicht: (2026)

On the Sample Complexity of One Hidden Layer Networks with Equivariance, Locality and Weight Sharing
von: Behboodi, Arash, et al.
Veröffentlicht: (2024)

On the Hardness of Learning Regular Expressions
von: Attias, Idan, et al.
Veröffentlicht: (2025)

Improved Guarantees for Heterogeneous Treatment-Effect Estimation via Matrix Completion
von: Mehrotra, Anay, et al.
Veröffentlicht: (2026)

Node-Private Community Detection in Stochastic Block Models
von: Klopp, Olga, et al.
Veröffentlicht: (2026)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
von: Chakrabarty, Deeparnab, et al.
Veröffentlicht: (2025)

Learning and Generating Mixed States Prepared by Shallow Channel Circuits
von: Hu, Fangjun, et al.
Veröffentlicht: (2026)