On our problem formulation and the perceptron algorithm:

We would like to clarify that our goal is not to understand the perceptron algorithm. We design a new method that is provably efficient and accurate for a much more challenging learning problem than the perceptron algorithm was designed to address. We would further like to note the distinction between the learning problem and the algorithm to solve it.

The perceptron algorithm efficiently learns Linear Threshold Functions with large margin in the realizable setting. We consider a far more challenging problem. We have adversarial label noise (agnostic setting) and distributional shifts. Moreover, our activations include ReLU, leaky ReLU, exponential linear unit (ELU), and normalized SoftPlus (i.e., $\sigma(0) = 0$) but not the sign activation that the perceptron deals with.

On the “convergence” of Algorithm 1:

Recall that OPT refers to the error in $L_2^2$ loss, achieved by the best-fitting solution to the data. As we discussed in Section 1 (Line 24–34), no algorithm can find a solution that achieves $OPT + \epsilon$ error in polynomial time, even if the $\mathbf{x}$-marginal distribution is Gaussian and even without considering distributional robustness [GKK19; DKZ20; 28 GGK20; Dia+21; DKR23].

The best guarantee one can hope to achieve for any polynomial-time algorithm is to find an $O(OPT) + \epsilon$ error solution. We prove that our algorithm can find such a solution (in polynomial time). Although our algorithm is not guaranteed to converge to a point in the sense that $\lim_{k \rightarrow \infty} \mathbf{w}_k$ might not exist, we prove that our algorithm efficiently finds an $O(OPT) + \epsilon$ solution in $k$ iterations, where the number of iterations $k$ is given in Theorem 3.1. In other words, the sequence generated by our algorithm converges to a set in the sense that asymptotically all iterates lie in a set of $O(OPT)$ solutions, which are the target solutions for this problem. When we use the word “convergence” in our paper, we mean this weaker notion of convergence.

On stopping criteria:

We know that Algorithm 1 finds a good solution after $k$ iterations; so if we have an upper bound $K$ for $k$, we may simply terminate the algorithm after $K$ iterations. A direct upper bound of $k$ can be obtained from Theorem 3.1 as $D_0 \le W^2 + \nu_0 c_1 / (1536 N \beta^2)$, which follows directly from Line 262.

On the existence of the maximizer $q_{\mathbf{w}}$:

Even without sequential compactness, the existence of optima is still a well-known result for a wide range of discrepancy-based ambiguity sets (e.g. Wasserstein distance, KL divergence, chi-square divergence, etc.). In fact, Lemma C.1 gives a closed-form formula for $q_{\mathbf{w}}$. The key property we used is that the function $p \mapsto L_\sigma (\mathbf{w}, p; p_0)$ is strongly concave because the chi-square divergence $\chi^2 (p, p_0)$ is strongly convex in $p$.

On the motivations behind the steps and intermediate quantities of Algorithm 1 and its analysis with Gap functions:

The accumulated gap $\sum_{i=1}^k a_i \text{Gap}(\mathbf{w}_i, p_i)$ is by now a standard quantity for tracking convergence of primal-dual methods widely used in other works that study convex-concave problems [SWD21; Dia+22d; Son+22; MDH24]. When the problem is convex-concave, this quantity is nonnegative. Such a property does not hold in our setting, as the loss is generally nonconvex. Instead, we proved in Lemma 3.2 that the gap is bounded below by a quadratic function of the distance to optimal outside the set of target $O(OPT)$ solutions, which is crucial for carrying out our argument ensuring contraction of distance to target solutions.

On the algorithm side, each step of the algorithm is fully motivated by the analysis, as detailed in Appendix D, which is not a feature of the algorithms in the prior works. For instance, the "extrapolated gradient" $\mathbf{g}_i$ is motivated in Lemma D.2 to facilitate the telescoping in Eq (32); the choice for $\mathbf{v}$ in lines 4 of the algorithm is naturally motivated by the argument in the proof of Lemma 3.4, as we explained in Section 1.3 (Line 156–162).

On sufficiency of reweighting of samples:

Because the algorithm needs to work with an empirical version of the problem, we had to prove concentration of the risk, i.e., analyzing the connection between the empirical target distribution $\hat{p}^*$ and the population target distribution $p^*$. To give more context, the definition of our Gap function relies upon the empirical target distribution and our dual updates $\hat{p}$ try to estimate it. On the other hand, population target distribution defines the risk that the solution to Problem 1.3 tries to minimize. Their connection is captured in Lemma 2.5 and Appendix C: we show that with enough samples from $p_0$, reweighting of those samples suffices to model the entire $\chi^2$ ball around $p_0$; this result is nontrivial, as uniform convergence results do not apply because $\hat{p}^*$ is not the uniform distribution over samples drawn from $p^*$.

Please refer to the global comment for a discussion about robustness and adversarial label noise. We thank the reviewer for pointing out the typos in Line 74 and Line 204. Other technical comments about the presentation:

• Line 250: $M$ is defined in Eq (6).
• Line 214 – 216: We will cite Claim E.2, where this point was explained formally.
• Line 142 – 145: We initialize at $\mathbf{w} = 0$, so the condition $\|\mathbf{w}\| \le 2 \|\mathbf{w}^*\|$ holds at initialization. We proved in Claim 3.5 that this condition holds for all iterations.
• Assumption 2.3: We would argue that this assumption is mild but nontrivial. The boundedness parameter $S$ appears in the iteration and sample complexities. To assert that we have a polynomial time algorithm, it is important that $S$ does not depend exponentially on the target error $\epsilon$ or dimension of the input $d$.

Thank you for your question. While [Dia+22a] and [Dia+22b] have made significant contributions to learning a single neuron robustly to adversarial label noise, our work additionally addresses robustness to distributional shifts, which introduces unique and complex challenges not covered in those papers. In fact, our algorithmic results are new in the DRO setting even without the robustness guarantee (i.e., in the realizable setting).

• Distributionally Robust Optimization (DRO) setting:
  Unlike the settings considered in [Dia+22a] and [Dia+22b], the DRO framework involves optimizing over the worst-case distribution within a specified ambiguity set. The results in [Dia+22a] [Dia+22b][Dia+20][Wan+23a] crucially rely on distributional assumptions that we only make for the target (loss maximizing) distribution. Once we introduce distributional shifts, it is unrealistic to assume that each distribution in the ambiguity set satisfies even basic concentration properties. This is a major challenge for our algorithm, as we cannot rely on these properties to bound the loss over iterations. To address this, we prove an additional structural result (Lemma 3.4), which we believe is of independent interest.

• Algorithmic Approach:
  All prior works [Dia+22a] [Dia+22b][Dia+20][Wan+23a] dealt with minimization problems that can be addressed by running (vanilla/projected/stochastic) gradient descent on either a convex surrogate or the $L_2^2$ loss directly. In our case, we have a nonconvex-concave non-bilinearly coupled problem, and each of these characteristics comes with their own technical challenges, as discussed in the intro (Section 1.3) and also see point (2) in response to reviewer ehoc, copied below:

(2) Optimization algorithm analysis (Lemmas 3.2 and 3.3):
We follow the general approach of primal-dual methods from the literature for clarity. However, as noted in the introduction, standard primal-dual techniques are not applicable here because:

• Negative Gap: Our gap function can be negative because the loss is nonconvex. We handle this by proving a lower bound for the gap function (Lemma 3.2).
• Nonlinear Coupling: The coupling between primal and dual variables is nonlinear, posing a challenge even for strongly concave problems in recent studies (e.g., [MDH24]).
• Absence of Lower Bounding Hyperplanes: Convex methods use lower bounding hyperplanes, which are not available in nonconvex settings. We address this by proving a new structural result (Lemma 3.4), which is vital for our analysis and noteworthy on its own.

We appreciate the opportunity to address these points and are open to further clarifications or suggestions.

Thank you for your comments.

On the intricacies of proving Theorem 3.1 (Main Theorem):

Broadly speaking, the proof of this theorem relies on two technical contributions as we discussed in Section 1.3:

1. Concentration of the target distribution:
   Recall that the target distribution is the solution to the min-max problem, while the reference distribution is where we draw samples from. We emphasize that, since the algorithm must work with an empirical version of the problem, we had to prove the concentration of risk on the target distribution. This is crucial for transferring assumptions (Assumptions 2.1 and 2.2) from the population target distribution to the empirical target distribution, which the definition of our Gap function relies on and our dual updates $\hat{p}$ try to estimate. The challenge is that typical uniform convergence results do not apply because our assumptions are only on the population target distribution. The empirical target distribution depends on samples from the empirical reference distribution, making it hard to transfer these properties. We address this by proving an interesting connection between the distributions in Lemma 2.5.

2. Optimization algorithm analysis (Lemmas 3.2 and 3.3):
   We follow the general approach of primal-dual methods from the literature for clarity. However, as noted in the introduction, standard primal-dual techniques are not applicable here because:

   • Negative Gap: Our gap function can be negative because the loss is nonconvex. We handle this by proving a lower bound for the gap function (Lemma 3.2).
   • Nonlinear Coupling: The coupling between primal and dual variables is nonlinear, posing a challenge even for (strongly) convex-concave problems in recent studies (e.g., [MDH24]).
   • Absence of Lower Bounding Hyperplanes: Convex methods use lower bounding hyperplanes, which are not available in nonconvex settings. We address this by proving a new structural result (Lemma 3.4), which is vital for our analysis and noteworthy on its own.

Challenges of learning neural networks:

Thank you for the question. Analyzing two single-neuron GANs is an interesting problem that may share similar techniques but is outside the scope of this work.

We would like to emphasize that learning a single neuron in the agnostic model, even without distributional robustness, is an ongoing research challenge. Notably, our results in the DRO setting are new even for the realizable setting (except for the special case of linear regression). Our work handles a class of problems nearly as large as those addressed without distributional robustness in a recent ICML paper [Wan+23a], demonstrating the significance and breadth of our approach.

We appreciate the opportunity to address these points and are open to further clarifications or suggestions.

Thank you for your comments.

Line 261, page 7:
The variable $\hat{p}_i$ in Algorithm 1 (line 261 on page 7), is updated in Line 7 of the current iteration and used in Line 5 of the subsequent iteration.

Memory cost and runtime:
The memory cost and runtime analysis is standard for the area and often omitted beyond the number of iterations: the memory needed to store the samples is $O(nd)$ and the variables maintained by the algorithm require $O(n + d)$, so the total memory cost is still $O(nd)$. The runtime is the number of iterations $k$ given in Theorem 3.1 multiplied by the per-iteration complexity $O(nd)$.

Adversarial label noise:
We explain this in the common response.

Accounting for distribution shift:
The problem formulation itself of the DRO model already accounts for the worst-case distribution shift. We do not discuss it explicitly because it is a standard model (see [Bla+24, Section 1]). We will add a brief commentary on how the DRO model accounts for the distributional shift, as here we are bounding the gap (Line 135) with respect to the worst-case distribution ${\hat{p}^*}$ from the ambiguity set, which corresponds to the worst-case distributional shift.

Ethical review:
Our paper only presents theoretical results, and we are confused by the need for an ethical review on Human rights (including surveillance). We are wondering if this was perhaps selected in error or if the reviewer could clarify the concern.

We appreciate the opportunity to address these points and are open to further clarifications or suggestions.