Summary
This paper essentially resolves the *computational sample complexity* of learning $\gamma$-margin halfspaces under the Massart noise model. Here, computational sample complexity refers to the number of samples required for polynomial-time algorithms, as opposed to general statistical estimators which may be computationally intractable. Previous works have given rigorous evidence, in the form of lower bounds against large classes of algorithms such as SQ algorithms, of an *information-computation* gap for learning $\gamma$-margin halfspaces. Without restrictions on computation, the sample complexity is $\Theta(1/(\gamma^2 \epsilon))$ for achieving zero-one loss of $\eta + \epsilon$, where $\eta$ is the uniform bound on the Massart noise. For a large class of efficient algorithms, however, the required sample complexity is at least $\Omega(1/(\gamma^2 \epsilon^2))$.
They show that the $1/(\gamma^2 \epsilon^2)$ sample complexity is essentially tight by designing a polynomial-time algorithm for learning $\gamma$-margin halfspaces. Their algorithm is based on a novel and technically insightful choice of the loss sequence for online SGD, which results in a surprisingly simple and efficient algorithm with near-optimal sample complexity.
Strengths
This is a well-written paper that stands out for being both technically insightful and simple. A simple and efficient algorithm (online SGD with a specific choice of loss sequence) achieves optimal sample complexity and lends itself to a clean analysis. It's hard to ask for more than this.
The core idea behind the algorithm is a clever choice of the loss sequence $(\ell_t)$ with respect to which one runs online SGD. Previous works have already employed the LeakyReLU loss as a convex surrogate for the zero-one loss and achieved suboptimal upper bounds on the sample complexity. LeakyReLU with parameter $\lambda > 0$ is defined by $\ell_\lambda(a) = (1-\lambda) \mathbb{1}[a \ge 0] + \lambda \mathbb{1}[a < 0]$. Applying this to the halfspace learning setting, a straightforward calculation shows that $\ell_\lambda(-y (w \cdot x)) = (\mathbb{1}[\mathrm{sign}(w\cdot x) \neq y] - \lambda)|w \cdot x|$, where $(x, y) \in \mathbb{S}^{d-1} \times \\{\pm 1\\}$ is a sample from the $\gamma$-margin halfspace distribution and $w \in \mathbb{R}^d$ is a candidate halfspace. Note the resemblance to the *shifted* zero-one loss $L(w) = \mathbb{E}_{(x,y)} \mathbb{1}[\mathrm{sign}(w\cdot x) \neq y] - \eta$ (when $\lambda = \eta$ in LeakyReLU). By the $\eta$-Massart noise assumption, $L(w^{\*}) \le 0$ for the optimal halfspace $w^{\*} \in \mathbb{R}^d$ and $L(w) \ge \epsilon$ for any halfspace $w$ with zero-one loss at least $\eta + \epsilon$.
The key difference between this shifted zero-one loss and the LeakyReLU is the $|w \cdot x|$ term. In particular, if we reweight each sample LeakyReLU loss by $1/|w \cdot x|$, we recover the shifted zero-one loss which is unfortunately non-convex. The authors overcome this issue by considering a *family* of bounded and convex loss functions $(\ell_u)$ indexed by $u \in \mathbb{R}^{d}$. Each $\ell_u$ is simply the LeakyReLU loss reweighted by $1/|u \cdot x|$. It is precisely this decoupling of the halfspace parameter $w$ and the reweighting parameter $u$ that leads to the guarantees of the algorithm. The *sequence* of reweighting parameters $(u_t)$, each of which leads to a different loss $\ell_t$, is chosen adaptively by online SGD.
Weaknesses
I did not find any significant weaknesses, only minor comments regarding the presentation.
- **The expression "(vector) v is independent of w" (line 174, 176) is confusing.** I think it's easy to confuse "independence" with statistical independence. It would be helpful to clarify this by adding that the reweighting term is *constant* with respect to the parameter $w \in \mathbb{R}^d$, and the reweighting term $W(v \cdot x, \gamma)$ remains the same when taking the gradient of $L_{v}(w)$. This is already implicit in the mathematical expressions, but providing additional explanation would benefit readers.
Questions
- Does the near-optimal online SGD algorithm fall within the class of SQ algorithms? If not, could there still exist non-SQ algorithms that achieve sample complexity with subquadratic dependence on $1/\epsilon$?