We study the problem of learning mixtures of linear classifiers under
Gaussian covariates. Given sample access to a mixture of $r$ distributions on
$\mathbb{R}^n$ of the form $(\mathbf{x},y_{\ell})$, $\ell\in [r]$, where
$\mathbf{x}\sim\mathcal{N}(0,\mathbf{I}_n)$ and
$y_\ell=\mathrm{sign}(\langle\mathbf{v}_\ell,\mathbf{x}\rangle)$ for an unknown
unit vector $\mathbf{v}_\ell$, the goal is to learn the underlying distribution
in total variation distance. Our main result is a Statistical Query (SQ) lower
bound suggesting that known algorithms for this problem are essentially best
possible, even for the special case of uniform mixtures. In particular, we show
that the complexity of any SQ algorithm for the problem is
$n^{\mathrm{poly}(1/\Delta) \log(r)}$, where $\Delta$ is a lower bound on the
pairwise $\ell_2$-separation between the $\mathbf{v}_\ell$'s. The key technical
ingredient underlying our result is a new construction of spherical designs
that may be of independent interest.

学习高斯协变量下的线性分类器混合问题，主要结果是一个统计查询（SQ）下界暗示已知算法对于该问题基本上是最佳的，甚至对于均匀混合的特殊情况。

学习线性分类器混合模型的 SQ 下界

SQ Lower Bounds for Learning Mixtures of Linear Classifiers

We study the asymptotic generalization of an overparameterized linear model
for multiclass classification under the Gaussian covariates bi-level model
introduced in Subramanian et al.~'22, where the number of data points,
features, and classes all grow together. We fully resolve the conjecture posed
in Subramanian et al.~'22, matching the predicted regimes for generalization.
Furthermore, our new lower bounds are akin to an information-theoretic strong
converse: they establish that the misclassification rate goes to 0 or 1
asymptotically. One surprising consequence of our tight results is that the
min-norm interpolating classifier can be asymptotically suboptimal relative to
noninterpolating classifiers in the regime where the min-norm interpolating
regressor is known to be optimal.
The key to our tight analysis is a new variant of the Hanson-Wright
inequality which is broadly useful for multiclass problems with sparse labels.
As an application, we show that the same type of analysis can be used to
analyze the related multilabel classification problem under the same bi-level
ensemble.

本文研究了高超参数线性模型在多类别高斯协变量下的渐近泛化，包括对 Subramanian 等人所提出的双层模型的研究，提出了新的下界，证明了该模型的渐近一致性，并提供了一个在稀疏标签多类问题中广泛适用的 Hanson-Wright 不等式的变体。

过参数化线性模型的多类分类精确渐近推广

Precise Asymptotic Generalization for Multiclass Classification with  Overparameterized Linear Models

Polynomial regression is a basic primitive in learning and statistics. In its
most basic form the goal is to fit a degree $d$ polynomial to a response
variable $y$ in terms of an $n$-dimensional input vector $x$. This is extremely
well-studied with many applications and has sample and runtime complexity
$\Theta(n^d)$. Can one achieve better runtime if the intrinsic dimension of the
data is much smaller than the ambient dimension $n$? Concretely, we are given
samples $(x,y)$ where $y$ is a degree at most $d$ polynomial in an unknown
$r$-dimensional projection (the relevant dimensions) of $x$. This can be seen
both as a generalization of phase retrieval and as a special case of learning
multi-index models where the link function is an unknown low-degree polynomial.
Note that without distributional assumptions, this is at least as hard as junta
learning.
In this work we consider the important case where the covariates are
Gaussian. We give an algorithm that learns the polynomial within accuracy
$\epsilon$ with sample complexity that is roughly $N = O_{r,d}(n
\log^2(1/\epsilon) (\log n)^d)$ and runtime $O_{r,d}(N n^2)$. Prior to our
work, no such results were known even for the case of $r=1$. We introduce a new
filtered PCA approach to get a warm start for the true subspace and use
geodesic SGD to boost to arbitrary accuracy; our techniques may be of
independent interest, especially for problems dealing with subspace recovery or
analyzing SGD on manifolds.

在高斯协变量的条件下，使用过滤的 PCA 方法和测地线 SGD 技术，本文提出一个新算法，能够以较小的样本复杂度和运行时间来学习低维数据中的多项式回归问题，并给出了复杂度的理论分析。

学习少量相关维度的多项式

Learning Polynomials of Few Relevant Dimensions

This paper rigorously establishes that the existence of the maximum
likelihood estimate (MLE) in high-dimensional logistic regression models with
Gaussian covariates undergoes a sharp `phase transition'. We introduce an
explicit boundary curve $h_{\text{MLE}}$, parameterized by two scalars
measuring the overall magnitude of the unknown sequence of regression
coefficients, with the following property: in the limit of large sample sizes
$n$ and number of features $p$ proportioned in such a way that $p/n \rightarrow
\kappa$, we show that if the problem is sufficiently high dimensional in the
sense that $\kappa > h_{\text{MLE}}$, then the MLE does not exist with
probability one. Conversely, if $\kappa < h_{\text{MLE}}$, the MLE
asymptotically exists with probability one.

本文通过建立高维逻辑回归模型中最大似然估计 MLE 存在性的分界曲线，证明 MLE 的存在性具有 “相变” 的特性，当问题具有足够高的维数时 MLE 几乎不可能存在，曲线参数由回归系数未知序列的整体大小确定。