Buchumschlag

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chandrasekaran, Gautam, Klivans, Adam, Kontonis, Vasilis, Meka, Raghu, Stavropoulos, Konstantinos
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
von: Klivans, Adam R., et al.
Veröffentlicht: (2026)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
von: Kou, Yiwen, et al.
Veröffentlicht: (2025)

Efficient Discrepancy Testing for Learning with Distribution Shift
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2024)

Sparse Linear Regression is Easy on Random Supports
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2024)

Iterative Chow Filtering for Learning with Distribution Shift
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2026)

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

Learning Juntas under Markov Random Fields
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

Testable Learning with Distribution Shift
von: Klivans, Adam R., et al.
Veröffentlicht: (2023)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
von: Klivans, Adam R., et al.
Veröffentlicht: (2024)

Learning Constant-Depth Circuits in Malicious Noise Models
von: Klivans, Adam R., et al.
Veröffentlicht: (2024)

Testing Noise Assumptions of Learning Algorithms
von: Goel, Surbhi, et al.
Veröffentlicht: (2025)

The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
von: Klivans, Adam R., et al.
Veröffentlicht: (2025)

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
von: Klivans, Adam R., et al.
Veröffentlicht: (2026)

Simple Mechanisms for Representing, Indexing and Manipulating Concepts
von: Li, Yuanzhi, 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)

Low-Rank Matrix Approximation for Neural Network Compression
von: Cherukuri, Kalyan, et al.
Veröffentlicht: (2025)

New Hardness Results for Low-Rank Matrix Completion
von: Chawin, Dror, et al.
Veröffentlicht: (2025)

Communication with Imperfectly Shared Randomness
von: Canonne, Clément L., et al.
Veröffentlicht: (2014)

The communication complexity of distributed estimation
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Low-degree learning and the metric entropy of polynomials
von: Eskenazis, Alexandros, et al.
Veröffentlicht: (2022)

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

Decision Tree Learning on Product Spaces
von: Moakahr, Arshia Soltani, et al.
Veröffentlicht: (2026)

Polyhedral Instability Governs Regret in Online Learning
von: Li, Yuetai, et al.
Veröffentlicht: (2026)

Large Language Models on Small Resource-Constrained Systems: Performance Characterization, Analysis and Trade-offs
von: Seymour, Liam, et al.
Veröffentlicht: (2024)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
von: Rohatgi, Dhruv, et al.
Veröffentlicht: (2025)

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
von: Brösamle, Moritz, et al.
Veröffentlicht: (2026)

A Theory of Learning with Autoregressive Chain of Thought
von: Joshi, Nirmit, et al.
Veröffentlicht: (2025)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
von: Jacot, Arthur
Veröffentlicht: (2025)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
von: Grewal, Sabee, et al.
Veröffentlicht: (2022)

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
von: Gui, Kaiwen, et al.
Veröffentlicht: (2023)

Lossless Model Compression via Joint Low-Rank Factorization Optimization
von: Zhang, Boyang, et al.
Veröffentlicht: (2024)

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

Active Learning with Simple Questions
von: Kontonis, Vasilis, et al.
Veröffentlicht: (2024)

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
von: AbdElhameed, Marwan, et al.
Veröffentlicht: (2024)

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