Cover Image

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Huang, Jizhou, Juba, Brendan
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution
by: Huang, Jizhou, et al.
Published: (2025)

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

Distribution-Specific Auditing For Subgroup Fairness
by: Hsu, Daniel, et al.
Published: (2024)

Reliable Learning of Halfspaces under Gaussian Marginals
by: Diakonikolas, Ilias, et al.
Published: (2024)

Replicable Learning of Large-Margin Halfspaces
by: Kalavasis, Alkis, et al.
Published: (2024)

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

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
by: Blondal, Ari, et al.
Published: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

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

Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
by: Diakonikolas, Ilias, et al.
Published: (2025)

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Learning Linear Utility Functions From Pairwise Comparison Queries
by: Ge, Luise, et al.
Published: (2024)

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
by: Sinen, Tim
Published: (2026)

Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
by: Bressan, Marco, et al.
Published: (2024)

Cryptographic Hardness of Score Estimation
by: Song, Min Jae
Published: (2024)

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

Actively Learning Halfspaces without Synthetic Data
by: Black, Hadley, et al.
Published: (2025)

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

Active Learning of General Halfspaces: Label Queries vs Membership Queries
by: Diakonikolas, Ilias, et al.
Published: (2024)

Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithm
by: Lu, Miao, et al.
Published: (2024)

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

Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
by: Bressan, Marco, et al.
Published: (2025)

Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
by: Zeng, Shiwei, et al.
Published: (2025)

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

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

Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach
by: Li, Yinan, et al.
Published: (2023)

Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks
by: Tsilivis, Nikolaos, et al.
Published: (2024)

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

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

Limits of Personalizing Differential Privacy Budgets
by: Cyffers, Edwige, et al.
Published: (2026)

LENS: Learning Ensemble Confidence from Neural States for Multi-LLM Answer Integration
by: Guo, Jizhou
Published: (2025)

Near-Optimality of Contrastive Divergence Algorithms
by: Glaser, Pierre, et al.
Published: (2025)

Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
by: Ding, Yanna, et al.
Published: (2025)

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

Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
by: Iwazaki, Shogo
Published: (2025)

Auditing Near-Optimal Policies Can Be Exponentially Hard: Conditional Query Lower Bounds via Occupancy Rashomon Capacity
by: Shihab, Ibne Farabi, et al.
Published: (2026)

Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment
by: Hu, Bingshan, et al.
Published: (2021)

Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost
by: Pathegama, Madhura, et al.
Published: (2026)

Learning Safe Numeric Planning Action Models
by: Mordoch, Argaman, et al.
Published: (2023)