Cover Image

Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zeng, Shiwei, Shen, Jie
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate
by: Shen, Jie
Published: (2024)

Towards Efficient Contrastive PAC Learning
by: Shen, Jie
Published: (2025)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Learning Low Degree Hypergraphs
by: Balkanski, Eric, et al.
Published: (2022)

Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
by: Diakonikolas, Ilias, et al.
Published: (2024)

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

Is Transductive Learning Equivalent to PAC Learning?
by: Dughmi, Shaddin, et al.
Published: (2024)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

PAC Learning is just Bipartite Matching (Sort of)
by: Dughmi, Shaddin
Published: (2025)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
by: McMahan, Jeremy
Published: (2024)

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
by: Wiesler, Eleanor, et al.
Published: (2026)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

Private PAC Learning May be Harder than Online Learning
by: Bun, Mark, et al.
Published: (2024)

Learning-augmented smooth integer programs with PAC-learnable oracles
by: He, Hao-Yuan, et al.
Published: (2026)

Testable Learning of General Halfspaces under Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2026)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
by: Hanneke, Steve, et al.
Published: (2026)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

Learning and Testing Convex Functions
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

On Exact Learning of $d$-Monotone Functions
by: Bshouty, Nader H.
Published: (2025)

Collaborative Learning with Different Labeling Functions
by: Deng, Yuyang, et al.
Published: (2024)

Language Generation in the Limit: Noise, Loss, and Feedback
by: Bai, Yannan, et al.
Published: (2025)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
by: Alman, Josh, et al.
Published: (2025)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

Efficient Discrepancy Testing for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Algorithms with Calibrated Machine Learning Predictions
by: Shen, Judy Hanwen, et al.
Published: (2025)

Experimental Design Using Interlacing Polynomials
by: Lau, Lap Chi, et al.
Published: (2024)

Polynomial-Time Approximability of Constrained Reinforcement Learning
by: McMahan, Jeremy
Published: (2025)

Testing Support Size More Efficiently Than Learning Histograms
by: Pinto Jr., Renato Ferreira, et al.
Published: (2024)

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
by: Chen, Sitan, et al.
Published: (2025)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
by: Chen, Peng, et al.
Published: (2025)