Buchumschlag

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Buhai, Rares-Darius, Ding, Jingqiu, Tiegel, Stefan
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

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

Lasso and Partially-Rotated Designs
von: Buhai, Rares-Darius
Veröffentlicht: (2025)

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

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

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

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
von: Bangachev, Kiril, et al.
Veröffentlicht: (2024)

On the Hardness of Learning One Hidden Layer Neural Networks
von: Li, Shuchen, et al.
Veröffentlicht: (2024)

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

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
von: Chen, Sitan, et al.
Veröffentlicht: (2026)

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

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

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

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

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

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

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

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

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

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

The Quasi-Polynomial Low-Degree Conjecture is False
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2025)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
von: Zhao, Haimeng, 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)

Proper vs Improper Quantum PAC learning
von: Nayak, Ashwin, et al.
Veröffentlicht: (2024)

Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees
von: Maros, Marie, et al.
Veröffentlicht: (2022)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
von: Tang, Runshi, et al.
Veröffentlicht: (2026)

Iterative Reweighted Framework Based Algorithms for Sparse Linear Regression with Generalized Elastic Net Penalty
von: Ding, Yanyun, et al.
Veröffentlicht: (2024)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
von: Bresler, Guy, et al.
Veröffentlicht: (2025)

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

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

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

Approximate Computation via Le Cam Simulability
von: Akdemir, Deniz
Veröffentlicht: (2025)

Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gaps
von: Ma, Wanteng, et al.
Veröffentlicht: (2024)

Random Circuit Sampling: Fourier Expansion and Statistics
von: Kalai, Gil, et al.
Veröffentlicht: (2024)

Computational lower bounds for multi-frequency group synchronization
von: Kireeva, Anastasia, et al.
Veröffentlicht: (2024)

Finite-Sample Inference for Sparsely Permuted Linear Regression
von: Ota, Hirofumi, et al.
Veröffentlicht: (2026)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
von: Chen, Hongjie, et al.
Veröffentlicht: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
von: Ding, Jingqiu, et al.
Veröffentlicht: (2025)

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

Statistical Agnostic Regression: a machine learning method to validate regression models
von: Gorriz, Juan M, et al.
Veröffentlicht: (2024)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
von: Jacobs, Peter Matthew, et al.
Veröffentlicht: (2026)