Machine Learning Theory
Near-Optimal Query-Based Learning of General ReLUs
This paper presents the first computationally efficient algorithm for agnostically learning general ReLUs under the Gaussian distribution using the squared loss. The algorithm leverages interactive query access to achieve a query complexity of O(d polylog(1/ε) + min{1/p, 1/ε}), significantly outperf…
Scale-Invariant Regret in Linear Regression is Impossible in High Dimensions Without Smoothness
This work establishes a fundamental dimensionality barrier for scale-invariant learning: while $O(\log T)$ doubly-uniform regret bounds are achievable in one dimension without assumptions on covariate magnitude, such bounds are provably impossible for dimensions $d > 1$ in the general case. The auth…
Order-Optimal Sequential 1-Bit Mean Estimation Achieved Despite Quantization Constraints
This paper introduces a novel adaptive mean estimator that achieves order-optimal sample complexity for 1-bit mean estimation across all tail regimes (k > 1). The method utilizes randomized threshold queries and demonstrates that the performance matches unquantized methods with an additional localiz…
Spectral Wasserstein Flow for Gradient Normalization in Deep Learning
This paper introduces Spectral Wasserstein distances as a framework to analyze gradient normalization techniques like Muon in deep learning. It establishes a connection between these distances and various normalization schemes, including Schatten-type norms. The framework provides theoretical founda…