arXiv Machine Learning
Oct 21
Polynomial Learning of Positive ReLU Networks under Gaussian Inputs
arXiv:2610. 25116v2 Announce Type: replace Abstract: We study positive, bias-free, one-hidden-layer ReLU networks under standard Gaussian inputs.
Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
Related stories
arXiv Machine Learning
Sep 3
Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method
The paper proposes a tensor‑optimization‑powered ensemble method that uses confidence tensors to capture how each weak base classifier performs across different classes. By integrating these tensors and a smooth, partially convex objective that emphasizes margin, the method improves both classification accuracy and generalization while requiring fewer base learners. The authors also prove a property of the loss gradient that enables efficient gradient‑based optimization of the constrained problem.
arXiv Machine Learning
Jun 26
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
arXiv:2606. 27298v1 Announce Type: cross Abstract: We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace.
arXiv Machine Learning
Jun 30
Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
arXiv:2606. 28573v1 Announce Type: new Abstract: Modern machine learning models are trained by optimizing high-dimensional non-convex empirical risk functions.
arXiv Machine Learning
Jun 16
Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model
arXiv:2606. 15219v1 Announce Type: new Abstract: In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal computational-statistical tradeoff in learning Gaussian single-index models?
arXiv Machine Learning
Jul 3
Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks
arXiv:2607. 01266v1 Announce Type: cross Abstract: We study binary classification problems whose decision sets are given by definable sets in o-minimal expansions of the real field.
arXiv Machine Learning
Jun 18
How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?
arXiv:2603. 04895v2 Announce Type: replace-cross Abstract: Overparameterized ML models, including neural networks, typically induce underdetermined training objectives with multiple global minima.
arXiv Machine Learning
Jun 3
Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
arXiv:2510. 02779v4 Announce Type: replace Abstract: Recent advances have significantly improved our understanding of the generalization performance of gradient descent (GD) methods in deep neural networks.
arXiv Machine Learning
Sep 17
Efficient Robust Learning at the Information-Theoretic Limit
The paper presents a polynomial‑time algorithm for robustly learning Boolean concept classes with respect to a fixed distribution, achieving the optimal error rate of η + ε where η is the noise rate. It builds on Blanc’s earlier, computationally inefficient algorithm and introduces no‑regret learners to overcome the previous limitations. Additionally, the authors provide an efficient method that does not require an ERM oracle for any function class admitting sandwiching polynomials under hypercontractive distributions, including a first polynomial‑time solution for learning halfspaces with Gaussian marginals at error η + ε.
arXiv Machine Learning
Jul 8
Boosting with List-Decodable Codes
arXiv:2607. 05791v1 Announce Type: cross Abstract: Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989).
arXiv Machine Learning
Jun 16
Stochastic trace estimation with tensor train random vectors
arXiv:2606. 15679v1 Announce Type: cross Abstract: Stochastic trace estimation is a standard tool for approximating the trace of a large-scale matrix available only through matrix-vector products.
arXiv Machine Learning
Jun 10
Efficiently Learning Drifting Halfspaces with Massart Noise
arXiv:2606. 11149v1 Announce Type: new Abstract: We study the problem of learning a drifting concept in the presence of Massart noise.