Imagen de Portada

Improved Hardness Results for Learning Intersections of Halfspaces

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Tiegel, Stefan
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Machine Learning Statistics Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
por: Buhai, Rares-Darius, et al.
Publicado: (2024)

On the Hardness of Learning One Hidden Layer Neural Networks
por: Li, Shuchen, et al.
Publicado: (2024)

Cryptographic Hardness of Score Estimation
por: Song, Min Jae
Publicado: (2024)

Learning High-dimensional Gaussians from Censored Data
por: Bhattacharyya, Arnab, et al.
Publicado: (2025)

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
por: Bangachev, Kiril, et al.
Publicado: (2024)

Causal Discovery under Latent Class Confounding
por: Mazaheri, Bijan, et al.
Publicado: (2023)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
por: Wein, Alexander S.
Publicado: (2025)

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

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
por: Chen, Siyu, et al.
Publicado: (2025)

Low degree conjecture implies sharp computational thresholds in stochastic block model
por: Ding, Jingqiu, et al.
Publicado: (2025)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
por: Kou, Yiwen, et al.
Publicado: (2025)

Near-Optimal Learning and Planning in Separated Latent MDPs
por: Chen, Fan, et al.
Publicado: (2024)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
por: Lou, Mengqi, et al.
Publicado: (2025)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
por: Huang, Jizhou, et al.
Publicado: (2025)

Derandomizing Multi-Distribution Learning
por: Larsen, Kasper Green, et al.
Publicado: (2024)

Efficient Pauli channel estimation with logarithmic quantum memory
por: Chen, Sitan, et al.
Publicado: (2023)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
por: Zhao, Haimeng, et al.
Publicado: (2025)

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

On Computationally Efficient Multi-Class Calibration
por: Gopalan, Parikshit, et al.
Publicado: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
por: Kelner, Jonathan, et al.
Publicado: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
por: Luo, Yuetian, et al.
Publicado: (2023)

New Hardness Results for Low-Rank Matrix Completion
por: Chawin, Dror, et al.
Publicado: (2025)

Tensor cumulants for statistical inference on invariant distributions
por: Kunisky, Dmitriy, et al.
Publicado: (2024)

Detection of local geometry in random graphs: information-theoretic and computational limits
por: Bok, Jinho, et al.
Publicado: (2026)

Tight Generalization Bounds for Large-Margin Halfspaces
por: Larsen, Kasper Green, et al.
Publicado: (2025)

Learning and Generating Mixed States Prepared by Shallow Channel Circuits
por: Hu, Fangjun, et al.
Publicado: (2026)

Online Learning of Halfspaces with Massart Noise
por: Diakonikolas, Ilias, et al.
Publicado: (2024)

On the Hardness of Learning Regular Expressions
por: Attias, Idan, et al.
Publicado: (2025)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
por: Chakrabarty, Deeparnab, et al.
Publicado: (2025)

Strong Low Degree Hardness for the Number Partitioning Problem
por: Mallarapu, Rushil, et al.
Publicado: (2025)

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
por: Diakonikolas, Ilias, et al.
Publicado: (2024)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
por: Tang, Runshi, et al.
Publicado: (2026)

Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
por: Tang, Runshi, et al.
Publicado: (2026)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
por: Bresler, Guy, et al.
Publicado: (2025)

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
por: Bernasconi, Martino, et al.
Publicado: (2024)

On the Computational Hardness of Transformers
por: Saha, Barna, et al.
Publicado: (2026)

A Fine-Grained Understanding of Uniform Convergence for Halfspaces
por: Kontorovich, Aryeh, et al.
Publicado: (2026)

Unique Hard Attention: A Tale of Two Sides
por: Jerad, Selim, et al.
Publicado: (2025)

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
por: Diakonikolas, Ilias, et al.
Publicado: (2025)

Learning from Equivalence Queries, Revisited
por: Braverman, Mark, et al.
Publicado: (2026)