Cover Image

Hardness of Learning Fixed Parities with Neural Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Shoshani, Itamar, Shamir, Ohad
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
by: Kornowski, Guy, et al.
Published: (2024)

From Tempered to Benign Overfitting in ReLU Neural Networks
by: Kornowski, Guy, et al.
Published: (2023)

When Models Don't Collapse: On the Consistency of Iterative MLE
by: Barzilai, Daniel, et al.
Published: (2025)

Limitations of SGD for Multi-Index Models Beyond Statistical Queries
by: Barzilai, Daniel, et al.
Published: (2026)

Implicit Regularization Towards Rank Minimization in ReLU Networks
by: Timor, Nadav, et al.
Published: (2022)

Depth Separation in Norm-Bounded Infinite-Width Neural Networks
by: Parkinson, Suzanna, et al.
Published: (2024)

An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization
by: Kornowski, Guy, et al.
Published: (2023)

Gradient Descent's Last Iterate is Often (slightly) Suboptimal
by: Kornowski, Guy, et al.
Published: (2026)

Generalization in Kernel Regression Under Realistic Assumptions
by: Barzilai, Daniel, et al.
Published: (2023)

On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
by: Kornowski, Guy, et al.
Published: (2022)

Open Problem: Anytime Convergence Rate of Gradient Descent
by: Kornowski, Guy, et al.
Published: (2024)

Simple Relative Deviation Bounds for Covariance and Gram Matrices
by: Barzilai, Daniel, et al.
Published: (2024)

Logarithmic Width Suffices for Robust Memorization
by: Egosi, Amitsour, et al.
Published: (2025)

The Oracle Complexity of Simplex-based Matrix Games
by: Kornowski, Guy, et al.
Published: (2024)

Beyond Benign Overfitting in Nadaraya-Watson Interpolators
by: Barzilai, Daniel, et al.
Published: (2025)

Are Convex Optimization Curves Convex?
by: Barzilai, Guy, et al.
Published: (2025)

REED-VAE: RE-Encode Decode Training for Iterative Image Editing with Diffusion Models
by: Almog, Gal, et al.
Published: (2025)

Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)

Deterministic Nonsmooth Nonconvex Optimization
by: Jordan, Michael I., et al.
Published: (2023)

Hardness of Learning Neural Networks under the Manifold Hypothesis
by: Kiani, Bobak T., et al.
Published: (2024)

On the Hardness of Training Deep Neural Networks Discretely
by: Doron-Arad, Ilan
Published: (2024)

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

HardNet++: Nonlinear Constraint Enforcement in Neural Networks
by: Goertzen, Andrea, et al.
Published: (2026)

HardNet: Hard-Constrained Neural Networks with Universal Approximation Guarantees
by: Min, Youngjae, et al.
Published: (2024)

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
by: van Rossem, Loek, et al.
Published: (2025)

A Dataset is Worth 1 MB
by: Shoshani, Elad Kimchi, et al.
Published: (2026)

Identifying Bias in Deep Neural Networks Using Image Transforms
by: Erukude, Sai Teja, et al.
Published: (2024)

DAE-HardNet: A Physics Constrained Neural Network Enforcing Differential-Algebraic Hard Constraints
by: Golder, Rahul, et al.
Published: (2025)

RAYEN: Imposition of Hard Convex Constraints on Neural Networks
by: Tordesillas, Jesus, et al.
Published: (2023)

Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
by: Larue, Guillaume, et al.
Published: (2026)

True 4-Bit Quantized Convolutional Neural Network Training on CPU: Achieving Full-Precision Parity
by: Tathe, Shivnath
Published: (2026)

Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
by: Kang, Sungwoo
Published: (2026)

Physics-Informed Neural Networks with Hard Nonlinear Equality and Inequality Constraints
by: Iftakher, Ashfaq, et al.
Published: (2025)

HANNA: Hard-constraint Neural Network for Consistent Activity Coefficient Prediction
by: Specht, Thomas, et al.
Published: (2024)

An open dataset of neural networks for hypernetwork research
by: Kurtenbach, David, et al.
Published: (2025)

Hard-Label Cryptanalytic Extraction of Neural Network Models
by: Chen, Yi, et al.
Published: (2024)

On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmetic
by: Park, Yeachan, et al.
Published: (2024)

A Mathematical Model for Curriculum Learning for Parities
by: Cornacchia, Elisabetta, et al.
Published: (2023)

Hard Constraint Projection in a Physics Informed Neural Network
by: Horne, Miranda J. S., et al.
Published: (2026)

Physics-Informed Neural Networks with Hard Linear Equality Constraints
by: Chen, Hao, et al.
Published: (2024)