Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise
Authors: Shuyao Li
Sushrut Karmalkar
Ilias Diakonikolas
Jelena Diakonikolas
Venue: NeurIPS 2024 poster (2024)
Keywords: Distributionally-Robust Optimization
Nonconvex Optimization
Primal-Dual Algorithm
Primary area: learning_theory

Abstract: We study the problem of learning a single neuron with respect to the $L_2^2$-loss in the presence of adversarial distribution shifts, where the labels can be arbitrary, and the goal is to find a "best-fit" function.
More precisely, given training samples from a reference distribution $p_0$, 
the goal is to approximate the vector $\mathbf{w}^*$
which minimizes the squared loss with respect to the worst-case distribution 
that is close in $\chi^2$-divergence to $p_{0}$.
We design a computationally efficient algorithm that recovers a vector $ \hat{\mathbf{w}}$
satisfying 
$\mathbb{E}\_{p^*} (\sigma(\hat{\mathbf{w}} \cdot \mathbf{x}) - y)^2 \leq C \hspace{0.2em}  \mathbb{E}\_{p^*} (\sigma(\mathbf{w}^* \cdot \mathbf{x}) - y)^2 + \epsilon$, where $C>1$ is a dimension-independent constant and $(\mathbf{w}^*, p^*)$ is the witness attaining the min-max risk
$\min_{\mathbf{w}:\|\mathbf{w}\| \leq W} \max\_{p} \mathbb{E}\_{(\mathbf{x}, y) \sim p} (\sigma(\mathbf{w} \cdot \mathbf{x}) - y)^2 - \nu \chi^2(p, p_0)$.
Our algorithm follows the primal-dual framework and is 
designed by directly bounding the risk with respect to the original, nonconvex $L_2^2$ loss.
From an optimization standpoint, our work opens new avenues for the design of primal-dual algorithms under structured nonconvexity.

Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise
Shuyao Li
Sushrut Karmalkar" University of Wisconsin-Madison skarmalkaree waiinaakkwwwiii........ edu
University of Aiaconsin-Madison shuyao. li@wisc. edu
Ilias Diakonikolas University of Eisconsin-Madison ilias@cs. wisc. edu
Jelena Diakonikolas University of Wisconsin-Madist jelenašcs wwsc. edu
Abstract
We study the problem of learning a single neuron with respect the L the presence of adversarial distribution shifts, where the labels can be arbitrary, find a "best-fit" function. More precisely, given training samples from a reference distribution Po. the goal is to approximate the vector w" which minimizes the squared loss with respect to the worst-case distribution that close x" d'-divergence to po. We design a computationally efficient algorithm that recovers a vector satisfying Ep- (a x) y)² S C.E,, (a x) - y)) + e, where C >>> is a dimension-independeer
and the goal
constant and (w", , )) is the witness attaining the man-mmx risk min [W max, (m),))> (wwww)
(p.p)). Our algorithm follows primal-dual framework and is designed by directly bounding the risk with respect to the original, nonconvex L3 loss. From an optimization standpoint, work opens avenues for the design of primal-dual algorithms under structured nonconvexity.
Introduction
The problem of learning a single neuron from randomly drawn labeled examples is fundamental problem extensively studied in the machine learning literature. Given labeled examples {(x,, B4) (x,, V1) E Rd RJ,, drawn from reference distribution pu. the goal in this context is to recover parameter vector wi that minimizes the squared loss Ag, (w) over a ball of radius W > 0:
w = arg min (o.n((w);; Ao,pa (w) = B(a. (a(w x) y)?
WER+:||llaSS
where R known (typically non-linear) non-decreasing activation function (e.g., the ReLU activation (1) max(0,t) and we denote by OPT, = min w w|l Ao,no (w) the minimum squared loss. In the realizable setting - where = o (w) x) and thus OPT, =
this problem YS20 The results for the realizable setting also naturally extend to zero-mean founded-variant label noise.
well-understood and by now part of the folklore (see, e.g., [KS09 11 Sol17
The more realistic agnostic model [Hau92 KSS92 (a.k.a. adversarial label noise) aims to identify
the best-fitting neuron for reference distribution of the examples, without any assumptions on label structure. However, it is known that in this setting finding parameter vector with square loss
OPT, +e requires d time, even if the x --marginal distribution is Gaussian [GKK19 DKZ20 GGK20 Dia+21 DKR23). Even if we relax our goal to achieve error O(PPT,) + 6, efficient
'Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

algorithms only exist under strong distributional assumptions. In fact, without such assumptions, this problem is NP-hard [Sim02, MR18]. Recent work has also shown that (under cryptographic assumptions) no polynomial-time constant-factor improper learner exists even for distributions supported on the unit ball [Dia+22b). Given these intractability results, recent work has focused on developing efficient constant- factor approximate learners under minimal distributional assumptions (see, c.g.. 20 FCG20 Dia+22a; ATV23
Gol+233 Wan+23a Zar+24))
This recent progress notwithstanding, prior work primarily focused on the setting where only the labels might be corrupted, without considering possible distributional shifts or heterogeneity of the data. Such distributional corruptions are frequently observed in practice and have motivated a long line of research in areas such as domain adaptation and (related it) distributionally robust optimization (DRO): see e.g,, (BEN09; ND16 RM22 Bla+24) and references therein. Thus, the main question motivating our work is:
How do adversarial changes in the underlying distribution impact the learnability of neuron?
We study this question within the DRO framework, where the goal is to minimize the model's loss on a worst-case distribution from a set of distributions close to the reference distribution 2 This set of distributions, known as the ambiguity set, models possible distributional shifts of the data. In addition to being interesting on its own merits, the DRO framework arises in diverse contexts, including algorithmic faireess [Has+ 18b] and class imbalance [xu+20]. Moreover, it has recently found a range of applications in reinforcement learning [Kal+22 Liu+22 Lot+23
Wan+23b Y3n+23
Yu+23), J, robotics [Sha+20), language modeling (Liu+21], sparse neural network training Sap+23] and defense against model extraction [Wn+23c]..
Despite a range of impressive results in the DRO literature (see, e.g.. recent surveys Kuh+19 CP20 RM22; Bla+24) and references therein), algorithmic results with rigorous approximation guarantees for the loss have almost exclusively been obtained under fairly strong assumptions about the loss function involving both convexity and either smoothness or Lipschitzness, with linear regression being the prototypical example; see, e.g., [CP18] BMN2 DN21]. Unfortunately, this vanilla setting does not capture a range of machine learning applications, where a typical loss function is nonconvex. In particular, even the simplest ReLU learning problem in the realizable setting (with noise-free labels) is nonconvex. Further, existing DRO approaches for nonconvex loss functions such as (SND18) Qi+21] only guarantee convergence to stationary point, which is insufficient for learning a ReLU neuron even without distributional ambiguity (YS20J. Motivated by this gap in our understanding, in this work we initiate a rigorous algorithmic investigation of learning a neuron (arguably the simplest non-convex problem) in the DRO setting. We hope that this work will stimulate future research in this direction, potentially addressing more complex models in principled manner.
Due to space constraints, we defer further discussion of related work to Appendix
1.1 Problem Setup
To formally define our setting, we recall the definition of xi-divergence between distributions p dp
and p', given by (2, p²) == f app' - -1) 'p'. We focus on the class of monotone unbounded activations introduced in [Dia+22a for which we additionally assume convexity. Example activations in this class include the ReLU, leaky ReLU, exponential linear unit (ELU), and normalized SoftPlus.
Definition 1.1 (Unbounded [Dia+22a] + Convex Activation). Let a IR + R be a non-decreasing convex function, and let ax, 3 >>>00 0. We say is (ax, uunbuuddd if it satisfies the following: (1) is
3-Lipschitz; (ii) (t1) (t2)) 2 a(t - t2) for all t 2 to 2 0, and (iti) (0) = O.
To formally state the problem, we further define the loss, risk, and optimal value (denoted by OPT). Definition 1.2 (Loss, Risk, and OPT). Given a regularization parameter v and a reference distribution Po. let @ = (po) denote the set of all distributions that are absolutely continuous with respect to
We contrast here robustness to perturbed data distribution studied within the DRO framework to robust- ness perturbed data examples referred to as the adversarial robustness in modem deep learning literature (e.g.. (GSSI4). ) Our paper is concerned with the former (and not the latter) model robustness.
Normalization, which ensures o (0) 0, is without loss of generality, as it corresponds to simple change of variable: ot) t att) (0) and ğ y + (0), which does not affect the loss value or its approximation.

---

Po and (W) == fwo: 2ll2 S W). We define the following:
(w,, p: Po) := B(a x)- - u)² - v Ra) = ( - up. (p)
R( ( po) == max La (w, p2; po). qw == arg max La (0;,;;))) pES(pp))
(EP()))
w" arg min R( R(;; po); n² = 1/w",
wE OPT ((a.))) (o x) y)² Ao,p' (w").
We say that Lo (w, p. po) is the regularized square loss function of a vector w and distribution E P; and R(w; Pa) is the DRO risk of w with respect to Po- We call p the target distribution.
The minimization of the DRO risk defined above corresponds to the regularized/penalized DRO formulation studied in prior work; see, e.g., [SND18) Wan+23e, MDH24). An alternate formulation would have been to instead optimize over restricted domain. The two are equivalent because of Lagrangian duality. We show in Claim E. a concrete relation between our regularization parameter and the chi-squared distance between the population distribution p2o and the target distribution p²
We further require that is sufficiently large to ensure that the resulting x (12 (2)) is smaller than an absolute constant, which is in line with the DRO being used for not too large ambiguity sets (RM22).
Empirical Version If the reference distribution is the uniform distribution on N labeled examples (a,, 8:) E Fd x R drawn from Po. call it Poo (N)) and similarly define p E ( Note that R(w"; Po) = maxaes( ((( (o x) y)² - vx"(f.. Po): if we let f denote the distribution that achieves the maximum, p has the same support Po and can be interpreted the reweighting of the samples that maximizes the regularized loss.
Formally, our goal is to solve the following learning problem.
Problem 1.3 (Robustly Learning a Single Neuron Under Distributional Shifts). Given error parame- ters e, (0, 1), regularization parameter > O, set radius W > O, and sample access to labeled examples (xx 2) drawn i.i.d. from an unknown reference distribution p2o output a parameter vector v (W) that is competitive with the DRO risk minimizer w" arg min minlwes((W) R(w; po) in the sense that with probability at least 6, ④ w" 112 < COPT + e for an absolute constant C.
While the stated goal is expressed in terms of || w" l|2, under mild distributional assumptions that we make on the reference and target distributions, this guarantee implies being competitive with the best-fit function p in terms of both the square loss and the risk, namely A (v)) = ((PPT) +o and R(w, Po) min R Ū; Po) I O(OPT) + c. Further, our algorithm is primal-dual and it outputs a distribution p that is close p in the chi-squared divergence.
Since the solution to Problem 1.3 has an error of (OPPT) + e, when we use the term "convergence" in our paper, we refer to the following weaker notion: the iterates of our algorithm converge to the (set of) solutions such that asymptotically all iterates lie within the set of ((OPT) + solutions, which are the target solutions, as stated in Problem L.3
1.2
Main Result
Our main contribution is the first polynomial sample and time algorithm for learning a neuron in distributionally robust setting for a broad class of activations (Definition I.1 and under mild distributional assumption on the target distribution (Assumptions 2.1 and 2.2 in Section 2.1p.
Theorem 1.4 (Main Theorem - Informal). Suppose that the learner has access to N = ②(d/e²
samples drawn from the reference distribution po- all samples are bounded and the distribution p satisfies the "margin-like" condition and concentration (Assumptions] [2. (.2 Section 2.7). then after Ō (dlog(1/E) iterations, each running in sample near near-linear time, with high probability Algorithml I recovers such that [ w01 112 I CPT +c, for an absolute constant C.
We emphasize that Theorem I. /simultaneously addresses two types of robustness: firstly, robustness concerning labels (y); and secondly, robustness due to shifts in the distribution (z10 being perturbed). This result is new even when specialized to any nontrivial activation like ReLU, realizable case (where OPT = 0), and the simplest Gaussian m-maiinaal distribution. Without distributional robustness, existing approaches, as previously discussed, yield error of O(OPT) + under certain
3

---

z- e-marginal conditions. We demonstrate that this error rate can be also achieved with respect to p in a distributionally robust context, as long as p meets the same conditions specified in [Wan+23a) among the mildest in the literature addressing non-distributionaly robust agnostic setting.
1.3 Technical Overview
Our technical approach relies three main components, described below:
Local Error Bounds Our work is inspired by optimization- -thoory local error bounds ("sharpness") obtained for learning a single neuron with monotone unbounded activations under structured distri- butions without considering distributional shift or ambiguity [MBM18] Wan+23a]. These bounds are crucial as they quantify growth of a loss function outside the set of target solutions, essentially acting as a "signal" to guide algorithms toward target solutions in our learning problems. Concretely,
under distributional assumptions p from [Wan+23a], the following sharpness property can be established: there is an absolute constant C1 > 0 such that Vw E (8(2 (l])).
1 w 112 = ((OPT) + (w) - A (wx) 2 c1 | - w
(2)
The local error bounds in [MBM18 [an+23a] assume identical reference and target distributions. as in our work - invalidates this assumption, and as a result necessary distributional assumptions for sharpness may not apply to all distributions in the ambiguity set. In this work, distributional assumptions are exclusively applied to the target distribution to exploit the sharpness property proved in [Wan+23a]. We also assume that the sample covariates from the reference distribution are polynomially bounded; this assumption, which is without loss of generality, impacts only the sample and computational complexities and is satisfied by standard distributions.
Introducing distributional ambiguity -
Primal-Dual Dual Algorithm Our algorithm is a principled, primal-dual algorithm leveraging the sharpness property on the target distribution, the structure of the square loss, and properties of chi-squared divergence. We control a "gap-like" function of the iterates, Gap( W, p2; iPo) := Lo (w, f2 fuo) - Lo (w" fo; foo). The idea of approximating a gap and showing reduces rate 1/Ag, where Aş is a monotonically increasing function of k; comes from [DO19) and has been extended to primal-dual methods, including DRO settings, in (SWD21 Dia+22c Son+22 MDH24].
Unlike past work (SWD2I Dia+22c; Son+22 MDH24], our primal problem is nonconvex, even for ReLU activations without distributional ambiguity. Unfortunately, the previously mentioned results relying on convexity do not apply in our setting. Additionally, sharpness - which appears crucial to approximating the target loss- is local property, applying only to such that ||/|||2 2|[ 1|2, where |///"] 12 is unknown. This condition is trivially met at initialization, but proving it holds for all iterates requires convergence. We address this issue via an inductive argument, effectively coupling convergence amalysis with localization of the iterates.
Additionally, standard primal-dual methods [CPIT] Cha+18 SWD21; ACW22 Son+22 rely on
bilinear coupling between primal and dual variables in L (ww p: po ). In our case, Lo (w, p: Po) is nonlinear and nonconvex in the first argument. Recent work (MDH24) handled nonlinearity by lincarizing the function using convexity of the loss, which makes the function bounded below by its linear approximation any point. However, this approach cannot be applied to our problem as the loss is nonconvex. Instead, we control the chi-squared divergence between the target distribution and the algorithm dual iterates to bound L.g (w, p=; Pa)) from below, using key structural result that we establish in Lemma 3.4 The challenges involved in proving this structural result require us to rely on chi-squared regularization and convex activation a. Generalizing our result all monotone unbounded activations and other strongly convex divergences like KL would need a similar structural lemma under these broader assumptions.
(w.
An interesting aspect of our analysis is that we do not rely on a convex surrogate for our problem. Instead, we constructively bound quantity related to the DRO risk of the original square loss, justifying our algorithmic choices directly from the analysis. Although we do not consider convex surrogates, the vector field vaw; æ. y). scaled by 2,3, corresponds to the gradient of the convex surrogate loss (a((( y) dt, which has been used in prior literature learning single neuron under similar settings without distributional ambiguity [Kak+11] Dia+20 Wan+23a]. In our analysis, the vector field v(w; ar, y) is naturally motivated by the argument in the proof of Lemma 3.4
"Concentration" of the Target Distribution we need to prove both upper bound and lower bound for Gap(w, (, p; Po). The lower bound relies
To prove that our primal-dual algorithm converges,

---

on sharpness; however, we need it to hold for the empirical target distribution (δ*). This requires us translate distributional assumptions and/or their implications from p to p Unfortunately, f is not the uniform distribution over samples drawn from p.. Rather, it is the maximizing distribution in the empirical DRO risk, defined w.r.t. Po. This means that prior uniform convergence results do not apply. Additionally, minimax risk rates from prior statistical results, such as those in [DN2T], relate R(w: Po) and R(w;; po). However, they do not help in our algorithmic analysis since they do not guarantee that the sharpness holds for f²".
To address these challenges, we prove (in Corollary is a simple closed- form expression for f as a function of Pu and an analogous relationship holds between p and po- This allows to leverage the fact that expectations of bounded functions with respect to Po closely approximate those with respect to Po to show that expectations with respect to pa and n are similarly close. This result then implies that the sharpness also holds for p (Lemma C.6p. Full details are provided in Appendix C
that as long as is sufficiently large, there
2 Preliminaries
In this section, we introduce the necessary notation and state basic facts used in our analysis.
Notation Given a positive integer N, [N] denotes the set [1,2,..., 22....,N, N]. Given a set E, go denotes the complement of & when the universe is clear from the context. We use Tig to denote the characteristic function of set '6: 1g(z) = if x E '6 and 1g (x) = otherwise. For vectors æ and E from the d-dimensional Euclidean space Rd we use (x, @) and x to denote the standard inner product, while || 1|2 = v..-) denotes the & norm. We use (xx(2), _,(2),.... x(()) to denote the entries of æ E IRd We write æ I & to indicate xú < a for all coordinates j. For r 0, B(r) = {a: ||a|||2 < r denotes the centered ball of radius r. We use AN denote the probability simplex: A, == fær E RRN. ΣS" (0)) 1, [M] 5 2 0}. We denote by Ia the identity matrix of size d x d. We write A = B to indicate that x. (A B)a 2 0 for all x E IRd, For two functions f and g. we say We use notation O-(-) and (-) to hide polynomial factors in (typically absolute constant) parameters c. For two distributions ze and p', we use μ < p to denote that is absolutely continuous with respect to p', i.e., for all measurable sets A, p' (A)
Ögg) if
Ogg log"())) for some constant ks and similarly define Ω.
implies (AA) O. Typically, and á empirical distributions, and ğ < q is equivalent to the condition that the support of p is a subset of the support of q. For p < p', we use de to denote their Radon-Nikodym derivative, which is dp"
the quotient of probability mass functions for discrete distributions. We use (p,,p)) to denote the chi-squared divergence of p w.r.t. p', i.e. x² = [ 1)2dp'.
2.1 Distributional Assumptions
Similar to [Wan+23a] we make two assumptions about the target distribution of the covariates (nā)). First, we assume that the optimal solution w= satisfies the following "margin-like" condition:
Assumption 2.1 (Margin). There exist absolute constants X, E (0, such that [|= ž AI, where pa is the x-marginal distribution of p".
Egapp xx T
I
>>>>>>>>>"" a
We also assume that Pz is subexponential with parameter B, which is an absolute constant. Assumption 2.2 (Subexponential Concentration). There exists a parameter B >> 0 such that for any u E (1) and any r 2 1, holds that PTæ~p; [lu x
2 r] S exp(-Br).
Appendix E of Wan+23a shows that Assumptions 2.1 and 2.2 are satisfied by several important fam- ilies of distributions including Gaussians, discrete Gaussians, all isotropic log-concave distributions, the uniform distribution over {-1,0, 1,3 etc.
For simplicity, we assume the labeled samples (z) ()) drawn from the reference distribution are bounded. This assumption, which does not affect the approximation constant for Problem [.3] only impacts iteration and sample complexitics. We state the bound on the covariates below, while a bound on the labels follows from prior work 2.6 in the next subsection).
Assumption 2.3 (Boundedness). There exists parameter S such that for any fixed u E B(1) holds that u - S for all sample covariates x in the support of po-
5

---

We also assume without loss of generality that 1| 12 C C'PT +C for some absolute constant C, since otherwise O would be a valid O(PPT) e solution. Algorithmically, we can first compute the empirical risk (per Corollary C.3 of the output from our algorithm and of in 0 and then output the solution with the lower risk to get an O(PPT) + solution; see Claim F.2 for detailed discussion.
2.2 Auxiliary Facts
To achieve the claimed guarantees, we leverage structural properties of the loss function on the target distribution, implied by our distributional assumptions (Assumptions 2. [nd 2.2 Specifically, make use of Lemma 2.2 and Fact C.4 from 2Wan+23a], summarized in the fact below.
Fact 2.4 (Sharpness (Wan+23a )). Suppose p and w* satisfy Assumptions
and 2.2
Ler
aAa For all w E ((2l( []) and u E 9B(1),
208 co-
Be (o a:) - a(w" xx)) . x - w² x)) 2 co Goller w²11
Ex-p; 1(x u S 5B for T = 2, 4.
Fact 2.4 applies to the population version of the problem. Such a result also holds for the target distribution of the empirical problem, which we state below. Note that this result cannot be obtained by appealing to uniform convergence results for learning neuron (without distributional robustness).
Lemma 2.5 (Empirical Sharpness; Informal. See Lemma C.6). Under Assumptions 2. to 2..3 for sufficiently large sample size N function of B, W, S, 1/, az Y X, d and with high probability, for all w (B []) with || w") 2 Ve and u E (1),
Ex (lo(w-a xx) oww- .x))
=))( w
w x)] (co/2)ll w ~ 11
E Ex [ J 6B for 2, 4.
(4)
As a consequence, for C1 = c2/() and any w E (WW) (where co is defined in Fact 2.4
we have
c w0 En (a(w (w- x) a(w ))) S 6B w w 12
(5)
where the left inequality uses Cauchy- Schwarz and the right inequality uses B L-iipschiss of o (-). 233) also showed that the labels y can be assumed to be bounded without loss of generality.
Fact 2.6. Suppose P² and w" sutisfy Assumption 2.7 and Assumption 2.2 Let vf
sign(y) max( (y), M) where for some sufficiently large absolute constant C' we define
M = = W B3 B3
(6)
Then Ep. (aww" x) 1//²
Epp (oww-- x) y) + +E.
We also make use of the following facts from convex analysis. First, let Ø R. + IR be differentiable function and the Bregman divergence of ø for any x. y E RN be defined by
Daly, x) = p(y) <(x)) (V y x).
Fact 2.7. Let vb(x)) = ((x) ) + (a, x)) + for some a E N and E R. Then (w(y, Doly. x) for all x, y E N.N, ie., the Bregman divergence blind to the addition of affine terms to function Φ)
Second, we state the first-order necessary conditions that a local maximizer must satisfy.
Fact 2.8 (First-Order Optimality Condition). Let Q be closed, convex. and nonempty set and let f: Ω + R be continuously difserentiable. If xt" is local maximizer of J on Ω, then it holds that f((x)) (y x²) for all y Q.
If f is also concave, then Equation
7 implies that xx is a global maximizer of f.
3 Algorithm and Convergence Analysis
In this section, we introduce our algorithm and state our main results, summarized in Theorem 3.1 We highlight the main components of our technical approach, while most of the technical details are deferred to the appendix, due to space constraints.

---

To facilitate the presentation of results, we introduce the following auxiliary notation: E(w;; æ, y) == (a(w x> -))- y) n(w; æ, y) := ( =z)
y) and ÖPT -(n=))=--((u) ((w"; æ, y). We also note that Assumption 2.3 implies that for all samples { y4 the function + v (w; 3i yi) is bounded above by G and K- s--Lipchiiz for all i [V] and u E (W),, where = 2,55 225 S M) and 5d (see Lemma B.4jin Appendix B). Starting from this section, we write L(w,, p)) to denote Lo (w. p: Pu). hiding the dependence on Pu and σ. We also write Gap( wz p)) for Gap(us w. p; Pa)
Our main algorithm (Algorithm [ is an iterative primal-dual method with extrapolation on the primal side via g.- The vector Egg (v(20 [0;; y)] equals the (scaled) gradient of surrogate loss used in prior works [Kak+ Dia+20 Wan+23a]. In contrast to prior work, we directly bound the original square loss, with Be, [ wi æ, y) naturally arising from our analysis. Both updates w, and pa are efficiently computable; w; involves simple projection onto a Euclidean ball, and p. involves projection onto probability simplex, computable near-linear time [Duc+08].
Algorithm 1: Main algorithm
Input: v > 0, K, G, C1 = 7683* Be/c1, sample set {<t;, vi) Jim a-1 Ao ao w-1 ww 0, p1 po:
Initialization: for i = -....,, do
k
a, (1 2 max (}.
(w /8) i-1
i-1 min voo 1/4]/ maxfk G}), A, = a, + A
vww; x. y) = 2 - x) - sygn(y) max (lyl, M Jaa where M is defined in Equation (6)
9--1 = p (1; v)] a-_ (E [0(
1: 11; y)] Ep. (0 x));
w, = arg min wex(WW) (g-1,, w) + 1+0.5c1
w w
p. arg maxper (a:L(w;,f) (vo + MA Dx (2, 1)
Theorem 3.1 (Main Theorem). Under Assumptions 2.7 to 2.3
suppose the sample size is such that
N = SBS.BB.am... p (1 +1+ ) + W (10)) and v 2 /BB 8 /OPT(2)
te/c1, where With probability at least 8, for all
OPT (2) = Eg ae-(e(ww": :/ww=:a> x.,)) y) and er is defined in Lemmal 2.5 iterates w Pk. it holds that
Do
60,3
wx DD p2k) < A
+
C1
where Do = -
w - woll + 2p" poo) and x 2p", , poo) S ci / B) (and therefore Do does not depend the sample size N).
In particular, after most k Ō ma [in(
log( Da iterations, it holds that
| w0 ||2 I C3vOPT Ve, E( [f(wx: x, y)] < (2+ (2+20 OPT+10% Be, R(wki Ro)
(8)
(9)
min R(w; pa) R(ws; po) R(w" :oo) C.(OPT +c),
(10)
wER((W)
where C3 163 /Be and C4 + 2113 + ei )1 + 5B
We focus the convergence of iterates claimed in Equation 8): the loss bound (Equation (9)
follows directly from the iterate convergence, while the risk bound (Fquation (T0) requires a more involved analysis. Complete details for Equations (9) and (T)) are provided in Appendix FF
Our strategy for the convergence analysis is as follows. Consider {a:}, a sequence of positive step sizes, and define A, as their cumulative sum Σ aj- Our algorithm produces a sequence of primal-dual pairs w;, P.. tracking a quantity related to the primal-dual gap, defined by:
Gap(w,, 2.) = L(w;, (2 22 L(w", f.:) = (L(w., L(w", f2')) + (L(w", -2")-((wx L(w"
We view (L(w, P)) L(w", )) as the "primal gap" and (L(w", , 2²) L(w", p2.)) as the "dual gap." Since the squared loss for ReLU and similar activations is nonconvex, L(w, is nonconvex its first argument. Note that this gap function not trivially non-negative (see Remark B.7). requiring explicit lower bound proof.
7

---

Our strategy consists of deriving "sandwiching" inequalities for the (weighted) cumulative gap Ei=1 a, Gap(w,, f2.) and deducing convergence guarantees for the algorithm iterates from them. A combination of these two inequalities leads to the statement of Theorem 3.11 from which we can deduce that unless already have an O(OPT) + solution, the iterates must be converging the target solutions at rate 1/Ag, which we argue can be made geometrically fast.
The rest of this section is organized as follows under the standard assumptions we state this paper, Lemma 3.2 we prove lower bound on Gap(w, ju) for any choice of w and f.. This can be used to get corresponding lower bound on the weighted sum > 0g a;Gap(w; p:).
Organization
In Lemma 3.3 we then state an upper bound on Σ a, Gap(w,, P:): the proof of this technical argument is deferred to Appendix D These two bounds together give us the first inequality in Theorem 3.1 Claim B.6 then bounds below the convergence rate for our choice of a; in Algorithm
I
and indicates that it is geometric. Finally, we put everything together to prove Theorem 3.1
To simplify the notation, use <(p) (f, Pa) throughout this section. Note that (p
Do ΣE Di=1
(7(t) -
for any p and in the domain.
Po
3.1 Lower Bound on the Gap Function
We begin the convergence analysis by demonstrating a lower bound on Gap(w; w, P.). Lemma 3.2 (Gap Lower Bound), Under the setting which Lemma 2.5 holds, for all w E B wn (22, Gap(w, f2) 2 1292 ÖPT + 2 w DD f2).
Proof. Writing (o(w- x) - y)² (lolw x) oww x)) + (a(ww x) -y))² and expanding the square, we have
L(w, L(w", f²)) p) wlo(w x) - y)² (a(w" x) y)
- -22 [[o(w" x) ( -ooox))) x)
ow" x))] Ep [[[o[w x) aww" ( =))
By the Cauchy-Schwand inequality, we further have that
BR-l(o [(a(ww x) - v)(www (wwwww-- x) - "ww" xx)]
B5- (lo a)) w)2 [(o x)) olw" =(w*+)))) 2
s BBVBBV OPT
w' 112
(11)
where in the second inequality we used the definition of OPT and Bewey (( - -o(w" -=)=)))))) <
6 ( |/w w011 112 from the right inequality in Equation 5
On the other hand, by the left inequality in Equation ( we also have
Ep [(ow(w æ) - -ow"" x)) 2 e - w013 f-llww"'l
(12)
Thus, combining Equation 11 and Equation 12 we get
I(w, - L(w", ,P') 2 -23 6B
w
w
OPT + + w w0
12 B
OPT
+
w w
(13)
C1
where the last inequality is by 23 w w²1l2 / OPT <
68 comes from an application of Young's 's inequality (Fact [B.I) 2eg
OPT + 9 || w0 11. which
Finally, we use the optimality of f. which achieves the maximum over all ñ E 9o for L(w", 22). By the definition of Bregman divergence, Fact 2.7| and first-order necessary condition in Fact 2.8
-L(w", P) (-I(w", p))) - (V p2)), p²) D- (P 2 vD P).
(14)
Summing up Equation
13 and Equation completes the proof.
8

---

3.2 Upper Bound on the Gap Function
Having obtained lower bound on the gap function, we now show an upper bound, leveraging our algorithmic choices. The proof is rather technical and involves individually bounding L(w; f=) above and bounding L(w", fo;) below to obtain an upper bound on the gap function, which equals T(w;, p²) T.(w", p..). We state this result in the next lemma, while the proof is in Appendix D
Lemma 3.3 (Gap Upper Bound). Let wi, Pi, ai, A; evolve according to Algorithm 7 where we lake, by convention, a-1 A- 0g Ao O and w-1 wo: P-1 Po- Assuming Lemma 2.5
applies, then, for all k 2 1, Ei=1 as a,Gap(ws (w; Pei) is bounded above by
+ 0.5c, Av
1w
wall
DD Po)
1
1x (vD + DoL))Do PP))
2
8 v 6B V
OPT (2)
48,3² BOPTA
100
wi
Σ
C1
C1
A critical technical component in the proof of Lemma 3.3 is how we handle issues related to nonconvexity. key technical result that we prove and use is the following.
Lemma 3.4. Let S; == Ep, ((o (w" (-=-=w"")--" o )]
(w, (w) () -o (w; x
w, evolve according to Line 6 in Algorithm]] 7 and suppose we are in the setting where Lemma 2.5 holds. Then, S Eqg [( x., v), w-
wi)) Es where
F C1 - w1112+ VBB GB (2 x(( va + (488BB/))OPT. OPT.
(15)
This bound is precisely what forces to choose chi-squared as the measure of divergence between distributions and introduce a dependence on (P) One pathway to generalize our results to other divergences would be to find a corresponding generalization to Lemma 3.4
3.3 Proof of Main Theorem
Combining Lemma
3.2 and Lemma
3.3
we now ready prove our main result.
Proof of Theorem 3.7 Combining the lower bound on the gap function from Lemma 3 with the
upper bound from Lemma 3.3 and rearranging, whenever ||w: 222 S 2||w=|| f| for all k so that Lemma 2.5 applies, we get that
B
ОРТА,
lww,
w"
112 +
Σ
va,Do(p' .pi) S a, BaGGp(w... P.)
C1
i=1
1 1 0.5c,
A
<
-wll?
+
(p" Poo)
1|0" - wk 112 (wo + vA ) ( Pax)
2
2
8,32 VBBBB / OPT
Σ aaxx ( f*) + 2 BÖPTA
+ Σ
C1 |w' w111
a
c1
e1
1=1
To reach the first claim of the theorem, we first argue that
Σ ai (4,32 MLB oaT
- vDa(f' fi)) S 0. This follows from (1)
Corollary C.2 by which we have p06) 2 P0 /2 for all j E [N], hence
(²)
Σ -6- 2 //10))/7=100 JE[N]
< Σ (6) p(11p/pp)== 2D' P..)
JEIN]
and (2) our choice of v, which ensures, with high probability, that v 2 8,3 OPT te/c1 2
8.32 / GB ÖPT
(2)/11, where the last inequality is because for the specified sample size, we have
that OPT (2) + 2 ( by Corollary C.9

---

Second, we similarly have that with probability 1 - OPT v OPT +e. Hence, since Bregman
divergence convex function is non-negative, whenever ||w I 2 112 for all S k, we have
||w0 - wx12 < Iww ----woll
woll 12 + 200 Po)
2403
+
(OPT +6)
(16)
1 0.5c A
C1
110 wo woll2/2 + (p Po)
603 B
P Px)
(OPT +6)
(17)
Vo + AA
V
The bound x (m pP) S c1/ B) is proved in Claim E.1
Finally, in Appendix
we
inductively prove the following claim so that assumptions in Lemma 2.5 are satisfied.
Claim 3.5. For all iterations
0, || ll2 s 2||ur*
The bound on the growth of Aş follows by standard arguments and is provided as Claim B.6 Since
max(x,G) and since Do + 7) S can Aş grows exponentially with (1 + r7)h where y min/v.c//81
be enforced by setting (1 + 1/1) log(Do/e) 2 log log(Da/e)/ log(1 + 11), have that after O max(x.G) log(Do/c) iterations either ||w - w0112 I / or Iw; - w" ll S CvOPT.
min(u.e1)
Conclusion
In this paper, we study the problem of learning single neuron in the distributionally robust setting, with the square loss regularized by the chi-squared distance between the reference and target distribu- tions. Our results serve as a preliminary exploration this area, paving the way for several potential extensions. Future work includes generalizing our approach to single index models with unknown activations, expanding to neural networks comprising multiple neurons, and considering alternative ambiguity sets such as those based on the Wasserstein distance or Kullback-Leible divergence.
Acknowledgement
Shuyao Li was supported in part by AFOSR Award FA9550-21-1-0084 and the U.S. Office of Naval Research under award number N00014-22-1-222 1-244.. Sushrut Karmalkar supported by NSF under Grant #2127309 to the Computing Research Association for the CIFellows 2021 Project. Iliss Diakonikolas supported by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. Jelena Diakonikolas was supported in part by the U.S. Office of Naval Research under contract number N00014-22-1-2535 expressed this material are those of the author(s) and do not necessarily reflect the views of the U.S. Department of Defense.
Any opinions, findings and conclusions recommendations
10

---

References
[ACW22]
A. Alacaoglu, V. Cevher, and S. Wright. "On the complexity of a practical primal-dual coordinate method". In: arXiv preprint arXiv:2201 0006044744444 (2022).
[AHW95]
P. Auer, M. Herbster, and M. K. K. Warmuth. "Exponentially many local minima for single neurons". In: Advances in Neural Information Processing Systems. 1995.
[ATV23]
Awasthi, A. Tang, and A. Vijayaraghavan. "Agnostic Learning of General ReLU Activation Using Gradient Descent". In: The Eleventh International Conference Learning Representations, ICLR. 2023.
[Bec17]
A. Beck. First-order methods in optimization. SIAM, 2017.
[Ben+10]
S. Ben--avid, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan. "A theory of learning from different domains". In: Machine learning 79 (2010).
[BEN09]
A. Ben-Tal, I.. El Ghaoui, and A. Nemirovski. Robust optimization. Vol. 28. Princeton university press, 2009.
[BBS07]
S. Bickel, M. Brückner, and T. Scheffer. "Discriminative learning for differing training and test distributions". In: Proceedings of the 24th international conference on Machine learning. 2007.
[BMN21]
J. Blanchet, K. Murthy, and A. Nguyen. "Statistical analysis of Wasserstein distribu- tionally robust estimators", In: Tutorials in Operations Research: Emerging Optimiza- tion Methods and Modeling Techniques with Applications. INFORMS, 2021.
[Bla+24]
J. Blanchet, Li, Lin, and X. Zhang. "Distributionally Robust Optimization and Robust Statistics", In: 2024.
[Cha+18]
A. Chambolle, M. J. Ehrhardt, P. Richtárik, and C.-B. Schonlieb. "Stochastic primal- dual hybrid gradient algorithm with arbitrary sampling and imaging applications". In:
SIAM Journal Optimization 28.4 (2018).
[CP11]
A. Chambolle and T. Pock. "A first-order primal-dual algorithm for convex problems with applications to imaging". In: Journal of mathematical imaging and vision 40 (2011).
[CP18]
R. Chen and C. Paschalidis. robust learning approach for regression models based on distributionally robust optimization". In: Journal of Machine Learning Research 19.13 (2018). R. Chen and I. C. Paschalidis. "Distributionally robust learning". : In: Foundations and Trends@ in Optimization 4.1-2 (2020). pp. 1-243.
[CP20]
[Che+20]
Chen, Koehler, Moitra, and M. Yau. "Classification under misspecification: Halfspaces, generalized linear models, and evolvability". In: Advances in Neural Infor- mation Processing Systems 33 (2020).
[Dia+20]
I. Diakonikolas, Goel, Karmalkar, A. R. Klivans, and Soltanolkotabi. "Approx- imation Schemes for ReL.U regression", In: Conference on Learning Theory, COLT
2020. 2020.
[DKZ20]
I. Diakonikolas, D. Kane, and N. Zarifis. "Near-Optimal SQ Lower Bounds for Ag- nostically Learning Halfspaces and ReLUs under Gaussian Marginals" In: Annual Conference on Neural Information Processing Systems. 2020.
[Dia+21]
I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. "The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model". In: Proceedings of Machine Learning Research vol 134 (2021).
[Dia+22a]
I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. "Learning a Single Neuron with Adversarial Label Noise via Gradient Descent". In: Conference on Learning Theory (COLT). 2022, pp. 4313-4361.
[DPT21]
I. Diakonikolas, J. H. Park, and C. Tzamos. "ReLU Regression with Massart Noise". In: Advances in Neural Information Processing Systems 34 (2021).
[Dia+22b]
I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren. "Hardness of Learning Single Neuron with Adversarial Label Noise". In: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. 2022.
[DKR23]
1. Diakonikolas, D. Kane, and L.. Ren. "Near-optimal cryptographic hardness of agnos- tically learning halfspaces and relu regression under gaussian marginals". In: Interna- tional Conference Machine Learning. PMLR. 2023.
11

---

[Dia+22c]
J. Diakonikolas, C. Li, S. Padmanabban, and C. Song. "A fast scale-invarian algo- rithm for non-negative least squares with non-negative data". In: Advances in Neural Information Processing Systems (2022).
[DO19]
J. Diakonikolas and L. Orecchia. "The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods". In: SIAM Journal on Optimization 29.1 (2019), pp. 660-689.
[DN19]
J. Duchi and H. Namkoong. "Variance- regularization with convex objectives".
In: Journal of Machine Learning Research (2019).
[Duc+08]
J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. "Efficient projections onto the & f-ablll for learning high dimensions". In: Proceedings of the 25th international conference on Machine learning. 2008.
[DGN21]
J. C. Duchi, P. W. Glynn, and H. Namkoong. "Statistics of robust optimization: A generalized empirical likelihood approach". In: Mathematics of Operations Research 46.3 (2021).
[DN21]
J. C. Duchi and H. Namkoong. "Learning models with uniform performance via distributionally robust optimization". In: The Annals of Statistics 49.3 (2021).
[Dwo+12]
C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. "Fairness through aware- ness". In: Proceedings of the 3rd Innovations in Theoretical Computer Science Confer- ence. 2012.
[FCG20]
S. Frei, Y. Cao, and Q. Gu. "Agnostic learning of a single neuron with gradient descent". In: Advances in Neural Information Processing Systems 33 (2020).
[GGK20]
S. Goel, A. Gollakota, and A. R. Klivans. "Statistical-Query Lower Bounds via Func- tional Gradients". In: Annual Conference on Neural Information Processing Systems. 2020.
[GKK19] S. Goel, S. Karmalkar, and A. R. Klivans. "Time/ Tradeoffss for Learning a ReLU with respect Gaussian Marginals". In: Advances in Neural Information Processing Systems 32. 2019.
[Gol+23]
A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. "Agnostically Learning Single-Indes Models using Omnipredictors". In: Thirty-seventh Conference on Neural
Information Processing Systems. 2023.
[GSS14]
I. J. Goodfellow, J. Shlens, and C. Szegedy. "Explaining and harnessing adversarial examples". In: arXiv preprint arXiv:1412.6572 (2014).
[HM13]
M. Hardt and A. Moitra. "Understanding Alternating Minimization for Matrix Comple- tion". In: 2013.
[Has+18a]
T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. "Fairness Without Demo- graphics in Repeated Loss Minimization". In: ICML. 2018.
[Has+18b]
T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. "Faimess without demo- graphics in repeated loss minimization". In: International Conference on Machine Learning. PMLR. 2018.
[Hau92]
D. Haussler. "Decision theoretic generalizations of the PAC model for neural net and other learning applications". In: Information and Computation 100 (1992), pp. 78-150. W. Hu, G. Niu, I. Sato, and M. Sugiyama. "Does distributionally robust supervised learning give robust classifiers?" In: ICMI. 2018.
[Hu+18]
[Hua+06]
J. Huang, A. Gretton, K. Borgwardt, B. Schölkopf, and A. Smola. "Correcting sample selection bias by unlabeled data". In: Advances in neural information processing systems 19 (2006).
[Kak+11]
S. M. Kakade, V. Kanade, O. Shamir, and A. Kalai. "Efficient learning of generalized linear and single index models with isotonic regression". In: Advances in Neural Information Processing Systems 24 (2011).
[KS09]
A. T. Kalai and R. Sastry. "The Isotron Algorithm: High- Biggh-Dimessioal Isotonic Regres- sion." " In: COLT. 2009.
[KSA19]
S. M. M. Kalan, M. Soltanolkotabi, and S. Avestimehr. "Fitting relus via sgd and quantized sgd". In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE. 2019.
[Kal+22]
N. Kallus, X. Mao, K. Wang, and Zhou. "Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning". In: ICML. 2022.
12

---

[KMM20]
S. Karmakar, A. Mukherjee, and R. Muthukumar. "A Study of Neural Training with Iterative Non-Gradie GradGretent Methods". In: arXiv e-prints (2020), arXiv-2005.
[KSS92]
M. Kearns, R. E. Schapire, and L. M. Sellie. "Toward efficient agnostic learning". In: Proceedings of the fifth annual workshop Computational learning theory. 1992.
[KKM17]
A. R. Klivans, P. K. Kothari, and R. Meka. "Leearning Halfspaces and Neural Net- works with Random Initialization.. In: Proceedings of the 30th Annual Conference on Learning Theory. 2017.
[Kuh+19] D. Kuhn, M. Esfahani, A. Nguyen, and S. Shaficezadeh- Abadeh. "Wasserstein distributionally robust optimization: Theory and applications in machine learning". In: Operations research & management science in the age of analytics. Informs, 2019, pp. 130-166.
[Lam13]
H. Lam. "Robust Sensitivity Analysis for Stochastic Systems". In: Mathematics of Operations Research (2013).
[Liu+21]
B. Z. Liu, B. Haghgoo, A. S. Chen, A. Raghunathan, P. W. Koh, S. Sagawa, P. Liang,
and C. Finn. "Just Train Twice: Improving Group Robustness without Training Group Information". In: ICML. 2021.
[Liu+22]
Z. Liu, Q. Bai, J. Blanchet, P. Dong, W. Xu, Z. Zhou, and Z. Zhou. "Distributionally Robust Q-Learning". In: ICMI.. 2022.
[Lot+23]
K. Lotidis, N. Bambos, J. Blanchet, and J. Li. "Wasserstein Distributionally Robust Linear- Qucer--uadcaaic Estimation under Martingale Constraints". In: AISTATS. 2023.
[MMR09]
Y. Mansour, M. Mohri, and A. Rostamizadeh. "Domain adaptation: Learning bounds and algorithms". In: arXiv preprint arXiv:0902.3444 (2009).
[MR18]
P. Manurangsi and D. Reichman. "The computational complexity of training relu (s)".
In: arXiv preprini arXiv: /8 0.4007 (2018).
[MDH24]
R. Mehta, J. Diakonikolas, and Z. Harchaoui. "A Primal-Dual Algorithm for Faster Distributionally Robust Optimization". In: arXiv preprint arXiv:2403. 10763 (2024).
[MBM18]
S. Mei, Y. Bai, and A. Montanari. "THE LANDSCAPE OF EMPIRICAL RISK FOR NONCONVEX LOSSES". In: The Annals of Statisticc 46.6A (2018), pp. 2747-2774.
[ND16]
H. Namkoong and C. Duchi. "Stochastic gradient methods for distributionally ro- bust optimization with f-divergences". In: Advances in neural information processing systems 29 (2016).
[NW72]
J. A. Nelder and R. W. M. Wedderburn. "Generalized linear models". In: Journal of the Royal Statistical Society: Series A (General) 135.3 (1972).
[Ore+19]
Y. Oren, S. Sagawa, T. B. Hashimoto, and P. Liang. "Distributionally robust language (2019).
modeling". In: arxiv preprini urXiv:/909.028
[PY09]
S. J. Pan and Q. Yang. "A survey on transfer learning". In: IEEE Transactions on knowledge and data engineering 22.10 (2009).
[Pat+15]
M. Patel, R. Gopalan, R. Li, and R. Chellappa. "Visual domain adaptation: A survey of recent advances". In: IEEE signal processing magazine 32.3 (2015).
[Qi+21]
Q Qi, Z. Guo, Y. Xu, R. Jin, and T. Yang. "An online method for class of distri- butionally robust optimization with non-convex objectives". In: Advances in Neural Information Processing Systems 34 (2021), pp. 10067-10080.
[RM22]
H. Rahimian and S. Mehrotra. "Frameworks and results distributionally robust optimization". In: Open Journal of Mathematical Optimization (2022).
[Sap+23]
H. Sapkota, D. Wang, Z. Tao, and Q. Yu. "Distributionally Robust Ensemble of Lottery Tickets Towards Calibrated Sparse Network Training". In: NeurIPS. 2023.
[Sha17]
A. Shapiro. "Distributionally robust stochastic programming". In: SIAM Journal on
Optimization 27.4 (2017).
[Sha+20]
V. D. Sharma, M. Toubch, L. Zhou, and P. Tokekar, "Risk-Aware Planning and Assign- ment for Ground Vehicles using Uncertain Perception from Acrial Vehicles". In: 2020 IEEE/RSJ (IROS).2022
[Shi00]
H. Shimodaira. "Improving predictive inference under covariate shift by weighting the
log- likelihooodd function". In: Journal of statistical planning and inference 90.2 (2000). J. Sima. "Training a single sigmoidal neuron is hard". In: Neural computation 14.11
[Sim02]
(2002).
13

---

[SNDI8]
A. Sinha, H. Namkoong, and J. Duchi. "Certifying Some Distributional Robustness with Principled Adversarial Training". In; International Conference on Learning Rep- resentations. 2018.
[Sol17]
M. Soltanolkotabi. "Learning ReLUs via gradient descent". In: Advances in neural information processing systems 30 (2017).
[Son+22]
C. Song. C. Y. Lin. S. Wright, and J. Diakonikolas. "Coordinate Linear Variance Reduction for Generalized Linear Programming". In: NeurIPS. 2022.
[SWD21]
C. Song, J. Wright, and Diakonikolas. "Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums". In: Proc. ICML'2). 2021.
[SJ19]
M. Staib and S. Jegelka. "Distributionally robust optimization and generalization in kernel methods". In: Advances in Neural Information Processing Systems 32 (2019).
[Tan+18]
C. Tan, F. Sun, T. Kong, W. Zhang, C. Yang, and Liu. "A survey on deep transfer learning". In: Artificial Neural Networks and Machine Learning-ICANN 2018. Springer. 2018.
[Wan+23a]
P. Wang, N. Zarifis, I. Diakonikolas, and Diakonikolas. "Robustly Learning a Single Neuron via Sharpness". In: Proceedings of the 40th International Conference Machine Learning. Vol. 202. Proceedings of Machine Learning Research. PMLR, July 2023, pp. 36541-36577.
[Wan+23b]
Wang. N. Si, Blanchet, and Z. Zhou. "A Finite Sample Complexity Bound for Distributionally Robust Q-learning" In: AISTATS. 2023.
[Wan+23c]
Z. Wang. L. Shen, T. Liu, T. Duan, Y. Zhu, D. Zhan, D. S. Doermann, and M. Gao. "Defending against Data-Free Model Extraction by Distributionally Robust Defensive Training". In: NIPS. 2023.
[Xu+20]
Z. Xu, C. Dan, J. Khim, and Ravikumar. "Class-weighted classification: Trade-offs and robust approaches". In: International conference on machine learning. PMLR. 2020.
[Yan+23]
Yang. Guo, P. Xu, A. Liu, and A. Anandkumar. "Distributionally Robust Policy Gradient for Offline Contextual Bandits". In: AISTATS. 2023.
[YS20]
G. Yehudai and O. Shamir. "Learning a single neuron with gradient methods". In: Conference on Learning Theory. 2020, pp. 3756-3786.
[Yu+23]
Z. Yu, L. Dai. S. Xu, S. Gao, and C. P. Ho. "Fast Bellman Updates for Wasserstein Distributionally Robust MDPs". In: NeurIPS. Curran Associates, Inc., 2023.
[Zar+24]
N. Zarifis, P. Wang. I. Diakonikolas, and Diakonikolas. "Robustly Learning Single- Index Models via Alignment Sharpness". In: 41th International Conference on Machine Learning, arXiv preprint: 2402. 17756 (2024).
[Zha+21]
R. Zhai, C. Dan, Z. Kolter, and P. Ravikumar. "DORO: Distributional and Outlier Robust Optimization". In: Proceedings of the 38th International Conference on Machine Learning. Vol. 139. Proceedings of Machine Learning Research. PMLR, July 2021, pp. 12345-12355.
[Zhu+20]
J.-J. Zhu, W. Jitkrittum, M. Diehl, and B. Schölkopf. "Kernel distributionally robust optimization". In: arXiv preprint arXiv:2006.069: (2020).
14

---

Supplementary Material
Organization In Appendix A we briefly discuss related work. In Appendix B we up some additional preliminaries for the rest of the appendix. In Appendix C we show that expectations of some important functions with respect to ş are close to their expectation with respect p'. In Appendix D we give a detailed proof of an upper bound on the gap of the iterates our algorithm generates (i.e. Lemma 3.3). Finally, in Appendix [ we show that the estimate of w² our algorithm returns is a constant factor approximation to the squared loss of w" with respect to the target distribution.
A Related Work
Learning Noisy Neurons The problem of learning noisy neurons has been extensively explored in
recent decades; notable works include [Kak+11 KS09 KKM17 NW72]. In the recent past, the focus has shifted towards specific activation functions such as ReLUs, under both easy noise models such
as realizable/random additive noise [KSA19 So117 YS20) and more difficult ones like adversarial label noise 20 DKZ20
Dia+21
22a
Dia+22b
GGK20 GKKI9
Wan+23a].
Even with clean labels, this problem has exponentially many local minima when using squared loss [AHW95]. Unfortunately, directly minimizing the squared loss using (S)GD on a bounded distribution does not converge to the global optimum with probability (S20). Even so, gradient based methods can achieve suboptimal rates in the agnostic setting (v (VOTT, vs OPTn) for distributions with mild distributional assumptions (FCG20). Making slightly stronger assumptions the marginal does allow us to get efficient constant factor approximations. (Dia+20) developed an efficient learning method that able handle this in the presence of adversarial label noise and for isotropic logconcave distributions of the covariates. This was later extended to broader classes of activation functions and
under weaker distributional assumptions by [Dia+22a Wan+23a| Without specific distributional
assumptions, learning remains computationally difficult Dia+22b HM13). The challenges extend to distribution-free scenarios with semi-random label noise, where methods like those in (DPT21) address bounded noise, and [KMM20) and [Che+20) explore stricter forms of Massart noise in learning neuron with noise. In this paper, we consider the harder setting of distributionally robust optimization, where an adversary is allowed to impose not only errors in the labels, but also adversarial shifts in the underlying distribution of the covariates.
Distributionally Robust Optimization Distributional mismatches in data have been extensively studied in the context of learning from noisy data. This includes covariate shift, where the marginal dis-
tributions might be perturbed, [BBS07, Hua+06, [Shi00], and changes in label proportions (Dwo+17 12]
Xu+20). This research also extends to domain adaptation and transfer learning [Ben+10; MMR09
PY09 Pat+ Tan+18] Tan++88
Distributionally robust optimization (DRO) has rich history in optimization
BBN09 Shal7] and has gained traction in machine learning (DGN2I, DN21 Kuh+19 ND16
SJ19 2hu+20j, showing mixed success across applications like language modeling [Ore+ 19 class
imbalance correction [Xu+20), and group fairness [Has+18h)
Specifically this has also been studied in the context of linear regression and other function approxi- mation [BMN2] CP18 DN2I]. Typically, DRO is often very sensitive to additional sources of noise, such outliers (Has+ Sa Hu+18 Zha+21J). However, prior work makes strong assumptions on the label noise as well as requiring convexity of the loss. We study the problem of learning a neuron where the labels have guaranteed structure, effectively studying the setting for a combination of two notions of robustness agnostic learning as well as covariate shift.
B Supplementary Preliminaries
B.1
Additional Notation
Given an x matrix A, the operator norm of A is defined in the usual way | sup(ll AmI1a : i R., ||ae||2 < 1). For problems (P) and (P"), we use (P) = (P') to denote the equivalence of (P) and (P"). For a vector space E, we use EE* to denote its dual space.
15

---

B.2 Standard Facts and Proofs
Fact B.1 (Young's ' inequality). Ifa 2 and are nonnegative real numbers and p > and q > 1 are real numbers such that
+ 1,
p q
then
a
68
ab v
p
Equality holds if and only 69.
Fact B.2 (Hoeffding's Inequality). Let X1, X.....,
, Xn be independent random variables such that Σx X, Then, for any t 0,
a, S X; b, almost surely for all Let X n
2nt
Pr Pr[ - E[X 2 S 2 exp
Ei=1 (b; az)3
Fact 2.7. Let (b(x)) ((x)) + (a, 10) + for some R and E R. Then D (y Doly, x)
for all a. y RRN, ie., the Bregman divergence blind to the addition of affine terms to function
Proof of Fact 2.7 The Bregman divergence Do and D. are defined by:
D = <b()) ((x) (V)(w)), y x))
Do x) = (b()) vxx)) (Vv(x), y x).
Since Vi((x) = VΦ(x)) + a, substituting in the definition gives:
(v) o0y) + (a. + - (6(x) + (a. 2) + b) (Vo(x) a. - x)
((v) ((x) (V y - x) a))y,a))
Thus, the Bregman divergence is blind to the addition linear terms to the function Φ.
B.3 Auxiliary Facts
We first state and prove Lemma B.3 to obtain upper bounds on the norm of each point, projections onto vectors of norm at most W. and the loss value each point.
Lemma B.3 (Boundedness). Fix
B(W).. For all samples (z. v.) with truncated labels
lyl < M as per Fact 2.6 and bounded covariates as per Assumption 2.3 holds that
w 0; < WS
(18)
|am||2 < Svd
(19)
(a(w 2.) y:)² < 232 C2 B² (ogg(((BB)))) (WB3/c)
(20)
Proof. Equation
18 follows from Assumption 233
w 23
||00|
1
x
|wll2S < W.S
w
l
To prove Equation (19 for each coordinate [d], we have |ab()) sign(x(())ez S S, by
again using Assumption 2.3 Therefore, ||m||| Svd.
For Equation (20). we recall Fact 2.6
2.6 that for some sufficiently large absolute constant Car, holds
that lyl < M == CmW B33 log( 3BW)e.. Thus, Equation (20) follows from Young's 's inequality
(Fact B.1 and Equation 19 since [a()) S //44. which follows from J-Liipchhitzness of and
(0) 0.
D
16

---

Lemma B.4 (Bounds on v). Let
v(w; x. y) = 2(o(w x) y)3x
Then is uniformly bounded by G in fz-norm and k-Lipschitz for all samples y. with truncated labels yl M and bounded covariates per Assumption 2.3 where G 23Sv M) and K = St..
Proof. We first uniformly upper bound v. An application of Lemma B.3 gives us,
||o(w;; x; v)1 4,3 (o(w x) - u)² ||0||
< , (2 + M²) S²d.
Taking square roots, we get ||o(w; a, 12 - 235 235 /dw33 M) =: G.
We now upper bound the Lipschitz constant k. We will use the fact that a is s-Lipschitz.
Vww(ww y)ll2 = 2/10'(u 2>) +>||<>>1|| l12
= =28lo (w x) 2>112
28 S = 2,3
Corollary B.5. Fix a reference distribution pa- Suppose |owww ,,,ll12 S for all almost surely. Then for all distributions pa, P ((p)) it holds that
E (ww; x, v)] [ (w(w; x. v)ll DZ
Proof.
/ u oww; x (dp -d)) d
Em (ww; æ, v)] - Eg (ww æ, v)]l =
/ v(w)
dp
dq
dpo
dpo
dpo
((w))
dp
d
dg
11: dpo
dpp
dpp
(2)
(dpp
dp dq
2
G²
dpo
drp
dpn
D2 (p, 4),
where (i) an application of Jensen's inquality and (ii) follows from Lemma B.4
Claim B.6 (Convergence Rate), For all > let a be defined as in Line 3 Then it holds that 2G?a.² 2
I Mu + VA,-1 and 2x a. 2
< A: for all i. Moreover, As = E
140.5c1 A:
1+0. Ar
((1+ 2max(x.G]
(i.e/p.rr/8)) )² 1) min (mo, 1/4}/ min(v.c188).
In order for both iterations i, it suffices that
Proof.
< vo + vA and 2naa, A,0.5c,
2G
1+0.5e,4, < 1+0.5c to hold for all
4 max (G, a,
< min(ro, 1/4] +
+ 0.5c, A;
for which it suffices to enforce
4 max x3, (min(Po, 1/4) min(v.cc/8444-1))
where we used A;- A,
Taking a square root on both sides using a; > 0, we obtain
max G, kJa, min 1/4} + min(v,ci/8).4. Ai-)
17

---

Solving this recurrence relation using Mathematica, we compute that for all iterations i and k.
a: = (1+ m i-1
2 2mxx(nx G} min 1/4)/(2 G})
min(v,c1/8] 1) min(vo, 1/43/ min(u,c1/55)
Σ a, = ((1+
max G}
i=0
Remark B.7. Note that in our case, the gap is not guarenteed to be non-negative as is usually the case for convex-concave min-max problems. Recall that Gap(w, w p)) (L(w, pp)) L(w", p pp)) (L(w", L(w", ,
Consider the following example:
Let Pa be the uniform distribution over f(-2, 2), (2, 1.5)). o= ReLU and v Then, w² and is the distribution which places all its mass on (2, 1.5). Then, Gap(1, p²) = L(1, p²)
L(-1, 72 = 0.25 2.25 <
This is why we also need an explicit lower bound on the Gap that we have shown in Lemma 3.2
C
Concentration
Recall that that Toe is not guaranteed to an empirical estimate of 4um because cannot draw samples from the (unknown) distribution tu but only from n² In this section, we show that for certain important functions f. holds that Eg [f] [g.[[]]. We will abuse terminology and say that f "concentrates" with respect to fw.
Organization: In Appendix C.I we derive closed-form expressions for quo and Tue terms of po and Pu respectively. Note that bounded functions concentrate with respect to pa. In Appendix C.2 we use the closed-form expressions found in Appendix C. to translate these concentration properties to 7w. Finally, in Appendix C.3 OPT (2)-
we show that p satisfies sharpness, OPT R OPT and OPT (2) R
C.1 Closed-form expression
The following lemma gives us closed-form expression for yro and Teo terms of po and po. respectively.
We start with an additional definition to Definition 1.2
R( w: Po) == max E (e (ow x)- - y)² (P, Po), with the maximum achieved by tw
per
Lemma C.1 (Closed-form 4w). Let poo be a fixed distribution. Then, there exists & E R such that,
dqw (ær, v) max[f(w;; x 3) E + 2v, 0} dpc
2v
When pa is the empirical distribution Pu this result implies that there exists & E R such that
(1) max{ (fx((((ww (w; x., y:) E 2v,0) for all i E [N].
4u
Po
2v
The constants and & can be interpreted as normalization that ensures dqp f d 1.
Proof. Recall that the dual feasible set is given by P = =P(p)) = {p < po: dp = 1, 2 0} = du dpo 1, dp
{p < po Tpo
> 0} and the function p2 L(w, p2) is strongly concave.
apo
Consider the following optimization problem
max L(w, p) max (mz kww; x y) - " 2 p). (po()))
pE (po)))o)
18

---

By Fact 2.8 the first-order necessary and sufficient condition that corresponds to 4w == arg magmax,eee pe L(w, p) is the following: for any p (po)).
/ VpL(W, )w) 9w) / V vpL(W, (w)
dp d
0
(Apo
dpp.
(21)
dpo dpo
where we recall that both Vp [(w, Aww) and Radon Radon-Nikodyn derivatives apo measurable functions on Rd R. We will also write E(w"", ;.:)) for short.
dp dew
are real-valued
dno
We claim Equation 21 is satisfied if there exists E IR and bounded measurable function + 2 0 such that
E E (x
if dqw dRa
0 otherwise.
VpL(W, qw (x,
(22)
Indeed, for any p E (po),
/
dp
d dpp
V L(w, qw)
dpo
dpo
-/ dow 20 dog
dp
dow
dp dpo
V n L(W, qw)
(w)
dpo +
L 9m)
dpo
dpo
dew dow= =0 do0
dpo
{ dp
dow
/ dam =0 Tho
dp dpo
dpo
+
(E - v) dpo
dem 0 Thi
dpo
dpo
dp
dqw
& dp dpo dpp
dpo
dew >0 dea
ddpo
dpo
dow =0 dog
dp dpo
dp dpo
d dpo
{
E
{
dem 00 dro
dpo
daw T0o
dpo
dane >0 Jag
dpo
dp dpo
d
( E E 0,
E
dpo
dpo
dew 50 8Po
dpa
where (i) is because
saaw B8g
dow dpe
dpo
[(
dew dpe
dp20-
30
Observe from the definition of L(w, qw) that Vp Lww, qw) (x. 8) = E(w; x. -) dew dRo
(xx y) -1).
Plugging this into Equation
(22 and rearranging, we have,
dp"
120-6-5 2v
if dgs
dno
dyau
if dgw 0
20
dno
For the case where dpo On the other hand, if the above condition fails, it has to be the case that dés 0. Combining, we have
dn"
0, dn"
20+t- so the condition
dew 0 becomes 2y + l - >> 0.
apo
2v
dpo
dpp
d dyo
{ Puttl 0
if + - 0
max + 1----.00 0,
otherwise
2y
Instead of using the expression in Lemma C.I we will set y to be big enough to ensure that there is no maximum the expression for qw. This captured Corollary C.2
Corollary C.2 (Simpler Closed-form 4w) Fix w E Rdd If 2 1 (ww), then
d (xx y) = l(w; x, v) Epp ((w)
dpn
2v
Similarly, if 2 1p ((w). then qu (1) > foror all i E [N]. and
qe (+) = Pb + Elw; wi y:) - Ep ((w) ((1
Po
for all i E [N].
2v
19

---

Furthermore, if Bio ((w), then, in particular, for each coordinate j [N], we have
3 Pg /2
Similarly, if 2 Ep ((w), then for any negatiie function 9, we have
1 / 9 d72
g dpew
Recall from Definition 1.2 that when w ww,, we define p² qw- and p = Fwa If 2 8,3² GB, /OPT(2) te/c1 as assumed in Theorem 3.1 then both conditions v 2 Eio ((w) and
V 2 P El (w) hold.
Proof. Setting v 2 Pp {(w) and = Epo ((()) Lemma C.1
implies E(w; x, y) Ep E(w;; x, y)
2v > 0, which, in turn, means
dow (x. dpo
max (f(w0; v)
Eo ((w; ar.y) 2v, 0}
2v
f(w: æ, y)
EP (ww; x. y) + 2v
2v
The empirical version follows analogously.
To establish the last claim, we show that 8,3 6BB (PT ((w). By Corollary C.9 it holds that
V OPPT (2) 2 OPT = (a--(o x)) - yy) 3/22 Re-(( x)) - -1)² (x² P4)) Il(w",, ,,")
By definition of po", we have I(ww,,"' 2 I(w", Poo) Ep (a (w= x)) y)² ux (po: poo)
Ep (oww" x) - w? Combining, we obtain 8,3 /BB ( 2 Ep 8,3 /B cc. We conclude by observing 8,3 V6B/c//// 2 1.
Another consequence of Corollary C.2 is closed form expression for the risk, variance- regularized loss, similar to [NN99
Lam
Corollary C.3. Fix an arbitrary distribution pao Recall the risk defined in Definition 1.2
R(w; Po): := max (( www; x, y) 2 (p.P)) Po).
If 2 ((w), holds that
( qw (pW) = Epp [p]le(w))] - (Epn[((w))) [(ww)))
4u2
Ep (ww) (E (
R(w; po) Epo [l(ww) +
4v
Proof. Both of these follow from Corollary
C.2
To see the first equality holds, observe that,
dd dpa
(w: Aw: po) = Epo
-1 1
(c(w; x, y) Epg ((w; x; u))²
Epo
4
Epg 162 (w)) - (Lpp [((w)))2
4u2
The second equality follows by similar substitution.
20

---

Setting d as per Corollary
we get
dow
R(w; po)
po
((w)
VX (w Pu)
dpo
1+ [(w) Epo (()
E (eo(e(())) - (Eppo [((w]])
po
[(w)
2v
4v
E po ((o))()))) (E [((2))))
E 12 ( [e())) - (E po (e( [((w)))
po [((w)]
+
2v
4v
Epo [eo)e(()) - (Bpu ((w)))
=
Eo [pp)(())]+
+
4v
Finally, important consequence of Lemma C.I is that it is possible to efficiently compute the risk of a given vector w with respect to pon We use this to compare the risk of our final output with the risk that is achieved by the zero vector.
C.2
Concentration
The expression we get in Corollary properties of Po to p We first state and prove a helper lemma, Lemma [.m that shows Po ((=((ww))))))) Ri Ep, (p"). Note that this is for the reference distribution po. and not the target distribution p="
C.2 for f2 in terms of pao allows us to translate concentration
For ease of notation, we define U = for the loss value Equation (20) throughout this section.
Cā B2 (W which is the upper bound
Lemma C.4. Suppose Pa satisfies Assumption holds that
2.3
Then for any fixed w B(W) and all L >>
E ((w)
E (N) S
PN with probability at least 1 - exp 3(F- B2 BB/C))) inequality holds for wn.
In particular, the above
Proof. By Equation 20 now implies that, for all
Vi [N], (o(w- xxi) y1)² 2 < U. Hoeffding's inequality (Fact B.2
N
-12N
Pr
((ww F.,
; yi) Expo f(w=) 20 s 2exp
202
Rearranging and plugging the definition of U, we get the lemma.
We now Lemma show that bounded Lipschitz functions concentrate with respect p² Lemma C.5. Fix > O. Let h h(2; x. v) B(() x Rd x R R. be measurable function with respect to æ; that satisfies the condition that [h(z;::)) S b almost surely. Then, for N
OB,5,
12 W log" (W/e) log(1/6)) samples drawn from the reference distribution po to us
construct Pu(NN, for any fixed E B(C), with probability at least 48, it holds that
- (1: m, v)] B( (1(2; az v)] $ t.
Moreover, suppose z + h(2; x,y) y) is a- Lipsshhiitz Then, for
b2 N O.,
W4 Wolo"" (W//))
) (dlog(Ca/l) + 1og(1/8))
p
v2
with probability at least 1 48, it holds that for all E B((),
B [h(2; x, v)] E(a [h(2; x0]= St.
21

---

Proof. We use Lemma C.1 to change the distribution with respect to which we are taking the expectation.
Ep. [b[=]] = Ego [M(2; æ 2) [[w=";,,) Bp <(w"; v) + 2
2v
Lemma C.4 now implies that with probability 1 - 1-2 -xxp( 10spp-22Nt' /bU (bb)))))²)
B [x]] Ppo [M(:: x. ((w=;; a. v) Enp (ww" ; v) + 20
2v
4
We now show that the expectation on the right hand side concentrates. To this end, we will use Hoeffding's inequality (Fact B.2). To apply this, we will need bound on the quantity in the expectation. We bound this via application of Equation (20) and the fact that [/| to get,
M[z; x v) (ww)
2)
Ep ((ww(w)))))) + 2v
S <b(1+
1+
U
2v
2v
This means, with probability at least 22xppp 21 N/2NN/(2(1 + U/22)23))
Bno [[(z) ((w")
Epg (l (2w) + 2v Eign
(( (w))
Ep ((ww)(ww)))))) 2v
h(z)
- 2
(23)
2v
2v
Since h(w) is a-Lipschitz, standard net argument over (xp log (a)t)) vectors yields: with probability at least 2 (og(((/)))) (b² U/2v) ))) B()),
it holds that for all
E h(2) ((ww) Eo ((w") + 2v
-Epo [1()) (((00) - En ((ww)((w))))))))))"))) 2v
St.
(24)
2v
Putting things together, we see that if we choose
6²
U
N Ω
1
(dlog((a/t) loog +lo((1/6))
v2
with probability at least
46, for all E B((),
Ex [h(2]] Ep- [h(=)]] s
C.3 Sharpness and Optimal Loss Value
Finally, consequence of Lemma C.5
we can derive that p satisfies sharpness, OPT ~ OPT
and ÖPT (2) (P) (2)-
Lemma C.6 (Shaprness for fDt) Suppose Assumptions 2.1 N:
2.3 are satisfied, then for large enough
W4 W log llog(((1)) (1/e) (d + log(1/5))
N Öp.S.A.a.
[1
v2
with probability at least 1 f5r for all E B(2[|w0 II) with || w"1l 2 Ve and u E B(1),
E Ex (o x) oww- + w" x)) (co/2)
ww /// w u²113
(25)
Em [( u) 6B for 2, 4.
(26)
Proof. Fact 2.4 shows that p the conditions above (with different constants). We need to translate these to p. For each of the incqualities above, we will do this via an application of Lemma C,5
Proof of Equation (25) Set l in Lemma C.5 to be hu( (w; x, y) == (a (w-www))or -o (t)==))))(()) (w-w-w-00 --= --'-) -x).
We proceed to set the constants a and that used in Lemma C.5 Equation (18) implies that
for all (xt, y) in the support of po. [a(w; x. v) < 42 =: b. Also, w + h(w) is ==
2W S ( + Vdd--isschhi
consequence of Equations 18 and (9).
22

---

Lemma C.5 now gives us that for N Ö B,9,8
W4
W (1/e) [1+
+ log(1/8)))
with proba-
12
6²
bility at least
46, for all [8 w0 |])
Eg (o x) a(w" =)) w²
x)] coll
w'
Using the fact that |1 w0 112 2 Ve, we set l = - c giving us the sample complexity
W [1
W log (1/6) (d + log(1/6)))
N = =BB.ABAA
(27)
u²
Proof of Equation 266: This follows analogously to the proof above. Set hiu; a, (x- u 7 in
Lemma C.3 for T = 4 and we proceed to calculate constants a, b. By Equations (18) and (19).
holds that h (u) - S² =: b and u + h(u) a = 45 /d-Liishhc Setting & B, by Lemma C.5
w (W//e) (d log(1/))) the conclusion follows. Note that this is
for N B
2²
dominated by Equation 27
We now show that OPT & ОPT. Lemma C.7. Suppose Assumptions and N ÖB.3,8 W log" (1/6) W log (1/6) 22
2.1
2.3
are satisfied and the sample size N is large enough log(L/6)). Then for any fixed w B(W) and
all > 0, it holds that
Eg f(w;; ar y) Bg- (ww;; a. u)1 S
with probability least 1 46. In particular, the above inequality holds for w i.e., 1OPT-0PT) S t.
Proof. Set (252 + 2C3, B² log (B33))) 2 [((w))l22 in Lemma C.5 where
the inequality a consequence of Lemma B.3 Then, with N ÖB,S. W4 log (1/e)
w logee//) log(1/6) samples, with probability 48, [EE E(w;; æ, v) Eg al x, w)1 S
Finally, we show (2) (2)
Lemma C.8. Suppose Assumptions (1
2.1
2.3
are satisfied and the sample size N is large enough log(1/8)). Then for any fixed us (B()) and
and N = ÖB,s,8 w log" (1/c)
W
log (1/c)
2²
all > 0, holds that
( x, v) Bp- Bx-l (w; St
with probability at least 1 45. In particular, the above inequality holds for w,, ie.. (OPT() OPPT st.
Proof. Analogous to the previous proof, observe that |[((w)ll S 83"W4(S$
C (ogg(WB) BB/c) b. By Lemma C.S. with N ÖB.S,8 w8 (1/e)
w (1/c) log(1 (1))) with probability 46, it holds that [R,,- e (un; x. v) Ezg l2 (un; [un; x. y) S
t.
We capture properties of OPT and OPT(2) in the following corollary. Corollary C.9 (Properties ОPT, (PT(2)) Suppose Assumptions 2.1 to 2.3 are satisfied and the
sample size N is large enough and N B. w (1/e)
log (1/e)
log(1/5)) Then
for all t O, the following hold:
1. With probability - 46, OOPT (2) -OPT (2)] Sh
2. With probability 1- 48, JOPT -OPT <t.
23

---

3. OPT & ()) and OPT S VOpTØR
Proof. The first two items follow immediately from Lemma C.8 and Lemma C.7 consequence of Cauchy-Schwarz.
The third item is
D Gap Upper Bound
To prove Lemma 3.3 we need to construct an upper bound on the gap Gap(w, f2.) L(w,, f)') L(w", p..) To achieve this, establish upper bound on L(w,, p'), which motivates the update rule for p.. We also establish lower bound on L(w", Pi), which guides the update rule for w, and the construction of gt. Note that the construction of the lower bound is more challenging here, due to the nonconvexity of the square loss. This is where most the (non-standard) technical work happens. To simplify the notation, we use ((p) = x2 (p, Po) throughout this section.
Upper bound on L(w.;f'') We begin the analysis with the construction of the upper bound, which is used for defining the dual updates. Most of this construction follows similar argument as used in other primal-dual methods such as 22ia+22c SWD21).
Lemma D.1 (Upper Bound on a, L(W,, )))) Let P. evolve as outlined in Line 7 Then, for all i 2 1,
a, [,w, p S 0; (w;; po:) + (vo + v - (R po--) - (vo + DA P..)
(vo + - 1 (Ps:: P)-
Proof. Recall that == x= Po). Observe that L(w,, (() as function of p is linear minus the nonlinearity vo. We could directly maximize this function and define P. correspondingly (which would lead valid upper bound); however, such approach appears insufficient for obtaining our results. Instead, adding and subtracting (vo + D D 1 Pi-1), we have
a; L(w, ) = a; L(w,, fT) (vo + VA D' 11 + (vo + IAi-)) ,
h(p') + (vo + iAA:1)) P):1),,
(28)
where we define, for notational convenience:
h(p) = a==[;, P) - (vo + DA,,1) P)-1).
Observe that by the definition of pas, l((2)) is maximized by pa.. Hence, using the definition of Bregman divergence, we have that
h( )- = (((2,) + (Vh(A), - (.)) + (2 (f",, p..) < h()))) (vo + v. p..).
where in the inequality we used that (Vh(p.), ~' - (as po maximizes h) and ( .
-(vo + Ds. ( Pi: (as h()) can be expressed as (m + =A:))(p))) plus terms that are either linear in fa or independent of it. See Fact 2.7). Combining with Equation (28 and the definition of
and simplifying, the claimed bound follows.
An important feature of Lemma D.I is that the first two Bregman divergence terms usefully telescope, while the last one is negative and can be used in controlling the error terms arising from the algorithmic choices.
Lower bound on L(w", P..). The more technical part of our analysis concerns the construction of
a lower bound on L(w", P.)) which leads to update rule for wt. In standard, Chambolle- Poyk-- primal-dual algorithms (AC222 CPII SWD21J, where the coupling L(w, f)) between the primal and the dual is bilimear, the lower bound would be constructed using an analogue of the upper bound, with small difference to correct for the fact that w; is updated before p. and one cannot information about P. in the w; update. This is done using an extrapolation idea, which replaces p; with extrapolated value from prior two iterations and controls for the introduced error.
In our case, however, the coupling is not only nonlinear, but also nonconvex because E(w; a. !) (a(w w x) y is nonconvex. Nonlinearity is an issue because if we were follow an analogue of
24

---

the construction from Lemma D.I. we would need to assume that we can efficiently minimize over w the sum of L(w, pi) and convex function (e.g., a quadratic), which translates into proximal point updates for the T.2 loss for which efficient computation is generally unclear. Nonlinearity alone (but assuming convexity) has been handled in the very recent prior work [MDH24), where this issue addressed using convexity of the nonlinear function to bound it below by its linear approximation around w, Unfortunately, as mentioned before, this approach cannot apply here as we do not have convexity. Instead, we use a rather intricate argument that relies on monotonicity and Lipschitzness properties of the activation a and structural properties of the problem which only hold with respect to the target distribution p (and the empirical target distribution p=, due to our results from Lemma 2.5 Handling these issues related to nonconvexity of the loss in the construction of the upper bound is precisely what forces to choose chi-square the measure of divergence between distributions; see Lemma D.3 and the discussion therein.
Proposition D.2. Consider the sequence {w0,} evolving as per Line Under the setting in which Lemma 2.3 holds, we have for all 2 1,
0; (w P..) 2 L(w;; 12:) - a, a, - (vo + (Pi
+ 1 0,5c,
1 0.5c,
||0e wwl1
1w0 - wi
2
2
1 0.5c1
Ai-1
1 0.5c, A 2
+
||w0 - wi
|00;11 - 20:2211
4
4
+ a. (Bpg ((
W x. y)1 Ep,
[(( x. y),, w² w/)
01-1 (Bp._, (ow 22, y)] Ep. ( (o 23 0, w)), w0- -0,111
where is E, is defined by Equation 37
Proof. From the definition of L(w", fai); we have:
L(w", p..) = Ep, [(a x) - -) - vD(
Writing (a(w". .x) y) (lo(w" x) o ow, .)) + (a(no, a:) y))² and expanding the square, we have
L(w", p..) = Ex. (oow: x) - yy - DD(p: Po)) + Eg, (wo xx) - oww, xx))²1 + Ep. (2 (w; x) (o .)
o(w, x))]
= L(w,, Pa:) St,
(29)
where for notational convenience we define
S, = Eeg Fa m)) alw; =² | + Ep, [2 x)) - (a -x)) a =))]- (30)
Observe that L(w:, p.:) on the right-hand side also appears in the upper bound L(w;, f²) in Lemma D. and so it will get cancelled out when L(w", fu:) is subtracted from L(w,, x²) in the gap computation. Thus, we only need to focus on bounding S.. This requires rather technical argument, which we defer to Lemma D.3 below. Instead, we call on Lemma D.3 to state that
S, 2 E.p ((v(u,;; x. y), w" w:)] E,
(31)
and carry out the rest of the proof under this assumption (which is proved in Lemma D.3
At this point, we have obtained a "'inearization" that was needed to continue by mimicking the construction of the upper bound. However, v(w;; x, y) depends w,, and trying to define w, based on this quantity would lead to an implicitly defined update, which is generally not efficiently computable. Instead, here we use the idea of extrapolation: instead of defining step w.r.t. w;, we replace Ep, [w(w;; x, y)] by an "extrapolated gradient" defined by (cf. Line in Algorithm I]:
gi-1 = Ep... (o (w0 x,,)),)))) v)]
0i-1 (E (ww v)] Ep. 21
0
Combining with the bound on S, from Equation 31 and simplifying, we now have
a,S, 2 a,(gi- :" w.) a,E,
(32)
+ a, (B,, (w(w;; x, v) gi- w0 - -w:).
25

---

Let ( = a; (, w) + - m|l w; 112 and observe that (by Line 6 in A Algorithm !
w; arg w (w)). Then, by similar argument as in the proof of Lemma D.1 since 1 IS minimized by w; and is quadratie function in wi we have
+ 0.5c| Ai- 1
1 0.500..444-.
0: 0, w w:) >
100 w;-112
2
2
(33)
+ + 0.5c1
A1-1
1|00 -.
2
On the other hand, by the definition of 9s: we have
a, p. (w;; æ, y)] 91-1. w" - w(}
a. P, [w v)] Bg._, [w x. y)], w0 -wi)
(34)
0 (Bp: [o(w;-1; a., w)] - Bp, (w w)], w= wi-1)
+ 0 (Bp, [ww;:1::;; 8)] ( 8)1. w; -
The first two terms on the right-hand side of Equation (34 telescope, so we focus on bounding the last term. We do using Young's inequality (Fact B. followed by s-Lipschitzness of u, which leads to
[2( (1 x, y)1 - ER, 2 (w x, y)), w. ww,-) a, (E
a, 2
1 0.5c, A:-1
[ | [w( v)] E3 [w
v)11
||0; w.-1l1
1 0.5c|.A. Ai
4
20 2x²
2a, 2 G2
1 + 0.5c1
As-1
1 w.-211 11 + 1 0.5c, A A,-1
(p, +
110, w,-1l13
0.5c, A4-1
4
(0)
+ 0.5c, A(-2
+ 0.5c|
[1:1
w 11
(w: wi w111112
(vo vA, D 22:
(35)
20c-1 2x
G S vo + VA; which both 1+0.5e A1-2 and T+0.5c,
where in (ii) we used
1+0.5e; A:-1 S
hold by the choice of the step size, while (i) follows by boundedness and r--Lipschitzness of v and
Corollary B.5 using
|E [w(w;-1:22 x. v)] - E (0 v)113
||Eg._, (00,,,1;3,, E2 (0010 E (10;; y)1 Ex,,, (V y)lll
< 2| (w0 y)1 Rgg [w( v) + 2 ( y)] - Exg (w0 a;
v)
< 2G Das (P + 2k ||00-1 2222112
(36)
Combining Equations 32 to 35
we now have
+ 0.5c, Ai
1 0.5c, A,-
a:S; 2 0; F4 +
1/00"
wol12
122
/w0 w0;-112
2
2
(vo + v. 2
D Dp(p,-11 P:-2)
+ 0.5c0.... A,-1
+
[w w,
11:=1 - w112112
4
4
+ a, (Bp. [u( (w;; x, y)] pp, [o 1w Φ, 4)1, w" - wi)
-0-1 (B [w 2, v)] Ep.., [w 21 x, U}1 w" w1-1).
To complete the proof, it remains to combine the last inequality with Equation 29
Lemma D.3. Let S, be defined by Equation 30 Then, under the setting of Proposition D.2 we have
S. 2 Ep, (ww x, y), w"
wi)l - E.,
where
E,
C1 I wi + 4
832 6B
6B
ÖPT (2)
x2 (P+
48,3 BOPT
(37)
C1
C1
26

---

Proof. Define the event 8 = {(x. v) oww; x) - y 2 0}. Then,
Ep, [2(o(w; x) v)(o(w" x) oww; [();;,))]]]]
= 1E,, (u x) - u)(a(w' x) oww, +}}lı + (w; x) - v)(o -
- ]
2 RT (u: m) - v),'(w; x)( x w; w,
+ E,, [1g. (w x) y) (w" x) x w; x)]
where the last inequality
convexity of (.) to bound the term that involves 13 and concavity of
--( to bound the term that involves Lgg- and where denotes any subderivative of a (guaranteed
to exist, due to convexity and Lipschitzness).
Recall that o(w;; æ. y/ (, æ) - y)æ. Using that o') = 3 (d'(t) (3) for all and combining with the inequality above, we see
E (2(o(w;; x) (o -x) o(w; [[),
2 Ep. [[([((w;: x, y), wt - -wi)]
+ 2 pr [Tv(o x) ())(''unn x)) - () x w. a;]
(38)
+ pEp, [Ig. (oww, x) () xx) - () x w; x)
(39)
and so to prove the lemma we only need to focus on bounding the terms in the last two lines.
Recall that assumed to monotonically increasing and B-Lipschitz, and S d'ww" x) S 3. Thus, we have
(a(w; x) (wwwwww a) () w; 2))
(o(w" x) y) x) B)(w" w; x))
+ (o(w; x) alw" ())(('(w") (w" x)- 3)( w. xx, xx)
2 (a(w" x) y)(o'(w" .x) () wi w))
(40)
where we have used o'ww" x) - - < (by Lipschitzness) and (o x) o(w" xx))(w"
wi x) S 0 (by monotonicity of o). By the same argument,
(o(w, x) () (w: x) B)(" x w; x) 2 (a(w" x) () (w: x) () wi x)
To complete the proof of the lemma, remains to bound the expectation of the term in Equation (40) We proceed using that lo'(w x)) - 3 < B, Vw, and thus for w E w.
(a(w" x) () (w x) (w x w. x)) < (w x) y/| ///lw". x w. x].
Taking the expectation on both sides, and combining with Equation 40 we further have
2E,, [I (w; x) - y)(o x) - (w x - we x)] 2.p | (o(w, x) y) x) - () x w; x))
I 2. E,,, (lls + (llg)) (ow"" x) yl|w" x w. x[]
= 2,3 Ep, [lo x) - yylw" x w. x!]
28 / la( law"" x)) vllw" w, a/
23 / loww" x)) - =|lw" x w, aldpp
/ |a(w" x)) "l|w" wi (dpp; dp²)).
+ 2B
(41)
In the last equality, the first integral is just the expectation with respect to p and thus using Cauchy- Schwarz inequality, the definition of OPT, and Lemma C.6 the first term in Equation (41 can be
27

---

bounded by
1o(w" x) - -1|20= x w. x/dp"
Bp- 110 a) 1) [(w0 -::000.0 2x)
OPT V 66 wt wPl12
2488OPT
w: 12
(42)
C1
163
where the last line is by Young's inequality and the second last line uses Lemma 2.5
For the remaining integral in Equation (41p, using the definition of chi-square divergence and Cauchy- Schwarz inequality, we have
/ lo(w" .x) - -yllw"
x:(pp; - -dp")
/ lo(w0 xx) - --yllww "...... x wi x (dp: dp²)
ddp
dpp
2
/x2 (f(ii..2*))) f2t) [[o x) (w" x wi x221
(20
$ X (Pi,. 11 (loww" x)) - 1)111/= I(w" x -2;; xx)
(1))
1 (p; (();,2")
(2) (6Bl 20/102PPT
1/4
(w0) 43v6B,
OPT (2)
x² (pi f2))
163 1|
wi w..1.
(43)
where (i) is by Cauchy-Schwand (fi) is by Cauchy-Schwarze again, (iit) is by the definition of OPT and Lemma C.6 and (iv) by Young's inequality.
(2)
To complete the proof, remains to plug Equations simplify.
(4
to
43) back into Equation 39 and
Gap upper bound proof of Lemma 3.3
Combining the upper and lower bounds from Lemma D.I
and Proposition D.2) now ready prove Lemma 3.3 which restate below.
Lemma 3.3 (Gap Upper Bound), Let ws, Pi, ai A, evolve according to Algorithm where take, by convention, a A-1 = dg = Ao = O and w-1 Wu, P-1 = P Assuming Lemma 2.5 applies, then, for all k 2 1, Ek a, Gap(w:;> p).) is bounded above by
+ 0.5c, A Il"= -ww-=wll2 (1o (AA) pPx)
w0l12 1D Po)
2
8
VBB
OPT
48,32 48,32 BOPTA
1w0
w
axxx (Fx,)));"")
[= 4
C1
C1
Proof. Combining the upper bound on a. aLW,, P() from Lemma D. with the lower bound on
a,L(w" P.) from Proposition D.2 and recalling that Gap(w,, p.) L w. f²) L(w", P.) and
28

---

A, = A,-1 + as. we have
a,Gap(w; P..) s a,Ei
+ (wo + vo( p.-1)
(wo + +vA, pii)
+ (mp + Do p2-2)
(16 -v Do Pii-1)
+ 1 + 0.5c,
1 0.5c A:
/w" -0:-1:
w1-1ll2
1|'2" wull
2
2
1 + 0.5c, Ai-2
+ 0.5cI
A:-1
+
10:-1 w. 211
||e, 11:11
4
+ 0: (B (w y)] - B 10 23 2, 8)), w² ww:-1
as (Bpp [0 (w: 2, y)] Ep. |0 (w 2; 2, w² w.))
Observe that except for the first line on the right-hand side of the above inequality, all remaining terms telescope. Summing over i = 1, 2....... and recalling that, by convention, ao = An = a-1 A-1 0, w-1 = wo, and p-1 = poo have
1 / 1100 woll + Do .Po))
a Gap wi, P2:)
Σ a, E,
i=1
1 + 0.5c1Ar
- - - (vp + A&) pox)
(44)
2
ax. (P, (10ss xr, x2, - -Rp. |0 v. w)], ~0 -wa)
1 + 0.5c, Ax-1
100k wk wk= 112 (wo + A Do (Pece p2x
4
To complete the proof, it remains to bound ag (Ep, [ww x, y)] p. [w y)], w - -wx)l which is done similarly in the proof of Proposition D.2 In particular,
ax K15 [w x, y)] - Ep. (ww y)], w" wx)l
ax²
E [u(wx; v\] E p. 10 v)]11 + + 0.5cI A 1| wwxl
1 0.5c, Ap
4
(9)
ax²
- 0.5c; Ak
Ph- 1) + 2n²² 2
|w
we w/--113) 113) +
||20"
uxx11
+ 0.5c, Aμ
4
(m)
1 1 0.5c1
As-
1 +
Ar
(no + vA
(pk, 1)-1)+
| w
112 +
1/"=
wxx12.
4
(45)
where (i) is by Young's 's inequality and (ti) is by Equation (36), and (fii is by 140.5c Ag
20a 2
S vo
and 2x 2x²ag² Ac
A+0.sc4Aa-1 which both hold by the choice of the step sizes in Algorithm
To complete the proof, it remains to plug Equation (45) back into Equation
use the definition of
F2 from Equation (37 and simplify.
E Omitted Proofs in Main Theorem
Claim 3.5. For all iterations & 2 0, ||wx|ll2 22 I 21|20"
29

---

Proof of Claim 3.5 It trivially holds that 0 = Wo E [8(2| w0 l12).
Suppose ||w:|12 S 21|2011 1|2 for all
iterations
where 0. Then
1232 B
OPTАR Σ
ai
C1 ww
w0
10
Σ
va, Dop"" , + aaat Gap pk+1)
1=1
R+1
ag Gap( W) P2:)
1 1 0.50g
Iww
woll
120" wk+1ll (vo + 1AA+1)D&(f pk+11)
2
8,2 V6B v ÖPT
k+1
4852 BRSTBOPPAR++
0 100 wil2
axx 2 (2))
C1
C1
where we used the gap upper bound Lemma 3.3 again as it does not require wo E 88[ w l|2). We proceed to deduce different lower bound for (ap(ww++1: Pk+1). Similar to Lemma 3.2 break into two terms L(w", px+1) - (-L(ww, )))) 2 vDo (Pp Pk+1)
and L(w p*) L(w" pD) =
Ex- [( x) y²² (a(w" Φ)) y) 2 OPT, where the first term is bounded the same
way as in Lemma 3.2 Hence, Gap( Pk+1) 2 OPT.. Therefore, we simplify as before
0.5c
1w0 - wi+1 113 + (vo +
C1 ,2+1)) 04 7 1 - W6+1
2
1
1 woll2 " 12,²B ОPTА + OPT 48,3 BÖPT
2
C1
which implies by nonnegativity of Bregman divergence that:
wx+1l1 - I|" -woll uDD( Po)) + 600 B + C1 Ak I
As + akt1 (1 48
OPT.
4
C
Rearranging and using 2 + c1 2 2,
112 S 1| - wo 1 + 2nd Dolk" (2a)+ + 2403BB
4a
(1 +1+ 48,3
||w- We++
OPT.
2 ca A
Our choice of stepsizes implies
< 1/ ///mfax, 1i, G} < 1, hence 9111 A+
288,3 B
||00 - wK+1 12 Iw" -woll 1 + 2n Do ,
ÖPT.
of
max Kx, GJ
Claim E.1. For u 8/8 OPT
(2)/11, it holds that
Varz, (f(w")
ÓPT (2)
28 P0o)
S (153633 B).
4v2
2v
Similarly, for v 2 po ((w"), 8,832 /6B /OPT / it holds that
x2pp".p0 = Var (elwo(((())) (l(w")
(PT(2)
S [c1((13663' B).
4v2
2v
Eg, 1e2 (w" "I -1-,,, ([(, [e(w=))>"
Egg (w= (w"))
Proof of Claim E.
By Corollary C.3
x2 ,7))
4e
4u
OPT < c (1536 B). where the second last inequality uses f 2 Po/2 from Corollary 2nd the last inequality comes from lower bound on v in the assumption.
C.2
and
The population version follows analogously.
Since Do( Po) (f" by choosing 76834 Be/ci, ensure 20 ,P)) S
30

---

By choosing Vo small enough and initialization wp = =0, it holds that
228832 B c
| WE+1
OPT.
max (ni, G}
288, B because both and G' is (d) We may assume without loss of generality that [M,
of
but the right hand side is an absolute constant. We may also assume without loss of generality that
300 ÖPT -e S 2 [ 1 thus completing the induction step || w 1l2 S 2/220112. The reason for the last loss of generality is the following: otherwise,
compare, per Claim H.2
the empirical risk of the output from our algorithm and of ú = 0 and output the solution with the lower risk get O(OPT) + solution.
Claim E.2 Zero-Tester) In the setting of Theorem 3.1 it is possible to efficiently check if R(0; Po) R(w; Po) or not; where is the output of Algorithm
Proof. Observe that L(w, P) = E f. x) - - (p. ) is 1/v-strongly concave in (p ..... (.)) Now, since R(w; Po) max; L(w, p),, we can estimate the risk any given w using standard maximization techniques (such as gradient descent).
To test which risk is larger, we estimate R(O; poo and R(w; (u) necessary accuracy and then compare.
F Parameter Estimation to Loss and Risk Approximation
Theorem 3.1 shows that Algorithm recovers vector u such that || w"112 S VOPT + Ve, where OPT := (a xx)
F1 Loss Approximation
In this section show that this implies that the neuron recover achieves constant factor approximation to the optimal squared loss.
Lemma F.1. Let p² satisfy Assumption 2. and Assumption 2.2
Suppose (w, P)) is the solution returned by Algorithm 1 when given N samples drawn from po- Then, Eyg (a( x)) y)² < OO,T(OPT)+H
Proof. Recall that a is --Lipschitz, and Fact gives us E. (u x²2 & 5B for all unit vectors u. These together imply,
Ep (a x) - v) < 2E, (a(w" x)) - y)² + 2Ep (a(w" x)) - o . xx))
w
20PT +2 i w11l E.p
@ w
20PT +2. +2T+2c) 5B
< (2 2 20B3*c OPT Be.
F.2
Risk Approximation
Fix to as output by Algorithm and w" as defined in Definition 1.2 Since we are bounding the population risk throughout this subsection, write R(w) R(w; in short. The goal of this subsection is to show
R(w) R(w")= < O(OPT) +
We first introduce some convex analysis results that rely in this subsection:
31

---

Fact F.2 (Strong convexity of chi-square divergence). Consider the space P(p)) = {p p & po)- For p E (po), we denote by dp the Radon- -ikkoyy derivative of p with respect to po. and we Tpo
is 2-strongly convex with respect to Il Fact F.3. Consider the space P ((p)) = {R < po) Denote by (o:))o the inner product (E1, f2ddp and denote by Ill1lpo the correponding norm. Then I1-1 is the dual norm of I1-1iko defined in F.c
define II - S de )ddpo- Then +
Definition F.4 (Convex conjugate). Given a convex function defined on vector space E denoted by f: :E R, its convex conjugate is defined as:
I" (v) sup (1y - [x))
zEE
for all y E E* where Ex is the dual space E and (y. denotes the inner product. Fact F5 (Conjugate Correspondence Theorem, [Bec17 Theorem 5.26)). Let v > 0. If a v-strongly convex continuous function, then its convex conjugate f E" - R is -mmooth
R is
We are then able to state and prove the key technical corollary in this subsection:
Corollary F... For any Po-measurable fumction é : R x R + I., let R (E) = ma Epp (p, Pp) The function (.) is 122o)ot with respect to the norm I|-1 defined Fact
A3
the convex conjugate of the function ux² 2( Pa). Since the function ux2((- (-, po) is 20-strongly convex with respect to the norm Il- by
Proof. Observe by definition of the convex conjugate that (R) Rt
Fact F22 it follows from Fact F.5 that (.) is 1 122o)-tmmotth with respect to the norm I1-1Ino- U
For ease of presentation, we define the following quantities: let (xx y) = (a(w" x) - y)² and
Ü(x, y) = (o(w x) - y)² We first compute V (E*) by conjugate subgradient theorem.
Fact F.7 (Conjugate Subgradient Theorem [Bec17] Theorem 4.20)). Let f f :E R be convex and continuous. The following claims are equivalent for any E E and E EE;
1. (v,x) = fxx) (z)
2. y 0f(z)
3. x E (f)
Corollary F.8. Let p. be as defined in Definition 1.2 Then p² E (E*)
Proof. We verify that R (E*) max, < Epo la x y) vx2 (p. Pa) = lo-loo(w x 3) [09]-x2((p) po) Ep- l "x²(p" Po) = (p* vx2(p" po). where the second equality is the definition of p= and the third equality is the definition of t.. By Fact F.7 and observing that (-). is the convex conjugate of the function vx²(,, po). we have p= 0,90
Theorem F.9. Suppose Corollary distribution. Then
C.2 holds for both w" and w with respect the population
R( po) R(w" po) ((OPT+c))
where 11=1+ + ci 2 Cz. In particular, Corollary C.2 holds for both w"
and w is satisfied under the assumptions in Theorem 3.1
Proof. By the definition of smoothness, holds that for any p E (etR(e),, we have
1
R( [ po) - R(w": po) = ( R(") < (p, 8 - Er) + 11e
11
2v
Hence it follows from Corollary
F88 that
1
R(w; po) R(w"; po) S (p-,e (()) + _ 11ē e- 11
2v
= E,, (o x)) - y)² - (a(w" x) - -) + E (( x) v (o(w" .x) - - ?)
2v
32

---

We use the following shorthand for ease of presentation.
az y) = oww" x)) - y,
A A 3) ( x) oww" x).
Then
R(i;; po) R(w"; po)) (p", 8 (*) + 2v 18 e" e'p
=Bp Ep-1(A + ) - w 1 + 2v
E po [14 + w2²² - v0 2
-
= =Ep- [A + | +
po
2 + 2
2V
S E [A + 2 - p. A 2 (A 422)1.
where the last inequality is the standard inequality (a + b)² I 2a² - -2b².
Recall in Fact 2.4 that Ey, [AV] 2 colli w"11 and Ep [(:: (u w ))= S 5B u w² 21.-
From the second- and fourth-moment bounds, we have ( E.p - ((o (a: wb) a( w )² S ST [[x (w ==] < 5B37 || w" 1 for 7 2, 4, where the second last inequality follows from (-Lipschitzzess of (-). Taking t = 2 gives us bound for Ep- [A
For E [. it follows from Cauchy-Schwand that AVv] S
102
R
/5B OPT
u w"
112-
By Corollary C.2 we have Epp A < 2E. [A < 5B33 - w 1
Finally, similarly by Corollary C.2 it follows additionally from Cauchy- Schwarz that EE 2 I
2Ep- A A S 2 Ep.
Ep V I 2 i w" 11 /PB By Theorem 3.1 we have
2 8
(2) te/c by assumption, hence 4E,,, A ///// call w 112
Combining the above four bounds and the guarantec of Theorem 3.1 that 1 2Cg OPT +2c, we have
w01 1
R(w; po) R(w":
< 53 I u 22 OPT i - -w" 122 + c |1 w0 5B
w 11///
< OPT + + w0 w01l//v) -
+
OPT OPT+2(1033+++ c1) OPT +c) + 40 OPT +2//u.
By Corollary
C.9
OPT S VOPT (2), hence V
2 83 tc/c1 2
GB max (OPT, Ve,/e,, hence
po)
< OPT 00FT-1000335+0111100001+14+--010
+e)) max V
< OPT 2001--/000F-.111000.711)-1111111
(1 + +000833-0000--007333370000111130 +1
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly outline the open problem we provide the
first results for, clearly state the assumptions involved (cf. Section 1.I Problem Setup and
Section 1.2
Main Result), and give a detailed technical overview of our algorithm (cf. Technical Overview).
Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations are clearly stated in the statements of each theorem and are discussed in the introduction of the paper and description of the key lemma (Lemma 3.4).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Each theorem statement provides all the assumptions and we provide complete proofs for all statements that are either in the main body of the paper or in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
35

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
publ ic / gu des / CodeeSuomee i s.s onPol P icy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https)
/ //nips. cc/ httpp/ulllcc// wwalii//qiieee siuid//// CCoeeooeSuuua Subeeuumiisee wsi.nsolisyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
36

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/ttt:///eettte /hepppi:////euips.... hwwpaaaww...cc.pp...c.ccaaaaaaaa
Answer: [Yes]
Justification: Our research conforms in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is theoretical and we do not see any major or immediate implications
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
37

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work is theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paper thcode com dataaettettt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
39


Reviews:
[{"review_id": "sU6hBeI05K", "reviewer": "Reviewer_3Jnc", "summary": "This work considers the labels with noise and possible distribution shifts of the data. The authors aim to minimize the model's loss on a worst-case distribution from a set of distributions close to the reference distribution, which is defined as ambiguity set. The activation functions used to produce labels are nonconvex, including ReLU, leaky ReLU, exponential linear unit, and normalized SoftPlus. In such situation, the distributionally robust optimization can achieve a stationary point, which is insufficient for learning a ReLU neuron. To close the gap, this work proposed the first polynomial sample and time algorithm for learning a neuron in a distributionally robust setting for a broad class of activations. \n\nTo this end, the authors make two assumptions about the target distribution covariates. Then, the loss function on the target distribution is claimed to be sharp. The algorithm is proposed to produce a sequence of primal-dual pairs w, p given a sequence of positive step sizes. The difference between optimal w and empirical w is called gap. The gap function is bounded, which further leads to the convergence of the algorithm as shown in Theorem 3.1.", "questions": "1. What is the time complexity and memory cost of the algorithm?\n\n3. Where do authors consider label noise in Theorem 3.1?\n\n4. How to control distribution shift is not discussed in Theorem 3.1.", "limitations": "The time and memory cost is not provided. It may limit the applications in real-world applications.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work considers the labels with noise and possible distribution shifts of the data. Existing works do not consider both of the concerns. \n\nThe problem is with practical interests.\n\nThe authors propose the novel algorithm to solve the problem.", "weaknesses": "1. The variable \\hat{p}_i in Algorithm 1 (line 261 on page 7 ), is not updated in other iterations. \n\n2. The analysis about time complexity and memory cost is missing. \n\n3. It is not clear where the noise of labels is discussed in Theorem 3.1 on page 6. \n\n4. How to control distribution shift is not discussed in Theorem 3.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\n\n**Line 261, page 7:**  \nThe 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.\n\n**Memory cost and runtime:**  \nThe 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)$.\n\n**Adversarial label noise:**  \nWe explain this in the common response.  \n\n**Accounting for distribution shift:**  \nThe 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.\n\n**Ethical review:**  \nOur 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.\n\nWe appreciate the opportunity to address these points and are open to further clarifications or suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SCEFQJafTs", "reviewer": "Reviewer_ehoc", "summary": "The authors study the problem of computing a distributionally robust optimization with \\ell_2^2 loss functions with sample distribution p, and a chi-square regularizer that ensures that p is close to a given p0 for a single d-dimensional neuron with monotone lipschitz activation function. Their main contribution is an efficient primal dual algorithm which recovers a weight w close to the optimal weight (in \\ell_2^2 norm) in O(d) iterations, as long as the optimal distribution p^* satisfies certain sub-exponential concentration properties.", "questions": "Can this be extended to two single neuron GANs? The min-max structure might be a simple yet tractable extension to your single neuron setting.", "limitations": "No societal impact, theory result.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is natural and a practically important one since distribution shifts issues occur in practice and before we study large neural nets, it's important to be able to answer the question for a single neuron. The proofs are fairly detailed, which is often missing in many conference papers.", "weaknesses": "The crux of the paper is Theorem 3.1 which bounds the error in each iterate of their primal dual algorithm. The proof of the theorem lies in bounding the primal dual gap and while the argument is interesting, the ideas are elementary and do not seem to be new to the area. I am happy to be corrected if I have missed any significantly new intuition or novelty in their arguments in Lemma 3.2 or 3.3 (which is the crux of their proof).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\n\n**On the intricacies of proving Theorem 3.1 (Main Theorem):**\n\nBroadly speaking, the proof of this theorem relies on two technical contributions as we discussed in Section 1.3:\n\n1. **Concentration of the target distribution:**  \n   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.\n\n2. **Optimization algorithm analysis (Lemmas 3.2 and 3.3):**  \n   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:\n\n   - **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).\n   - **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]).\n   - **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.\n\n**Challenges of learning neural networks:**\n\nThank 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.\n\nWe 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.\n\nWe appreciate the opportunity to address these points and are open to further clarifications or suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Oia8GKVqqJ", "reviewer": "Reviewer_aZHR", "summary": "This paper addresses the problem of learning a single neuron in a distributionally robust setting, where both the input distribution and labels can be adversarially perturbed. The authors propose an efficient primal-dual algorithm that achieves a constant-factor approximation to the optimal loss, with respect to the worst-case distribution within a chi-squared divergence neighborhood of the reference distribution.\n\nThe proposed algorithm iteratively updates both the weight vector and a reweighting of the empirical distribution. The analysis relies on carefully bounding a gap function related to the primal-dual objective. A key technical lemma bounds the nonconvex parts of the objective, allowing the analysis to go through despite the nonconvexity.", "questions": "Please see weanknesses part.", "limitations": "They discussed the limitations. This is a pure theory paper so I do not see potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Learning single neuron is an important problem towards understanding deep learning. This paper extends the prior works to the setting of distributionally robust loss. They give concrete primal-dual algorithm to optimize, and provide rigorous theoretical generalization guarantees of the algorithm. The algorithm is computationally efficient, with polynomial ($O(d/\\epsilon)$) sample complexity.\nThe analysis introduces novel techniques for handling nonconvexity in primal-dual methods, which to me, is interesting. Their theory also applies to various activation function, not restricted to ReLU.", "weaknesses": "It seems that [Dia+22a] and [Dia+22b] also studied robustly learning single neuron. I am not familiar with those literatures, so I cannot give a very accurate judgement on the degree of technical novelty of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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).  \n\n- **Distributionally Robust Optimization (DRO) setting:**  \n  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.\n\n- **Algorithmic Approach:**  \n  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:\n\n> **(2) Optimization algorithm analysis (Lemmas 3.2 and 3.3):**  \n> 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:\n> \n> - **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).\n> - **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]).\n> - **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.\n\nWe appreciate the opportunity to address these points and are open to further clarifications or suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b7fer7NDlH", "reviewer": "Reviewer_ef6F", "summary": "The authors consider the problem of fitting a single neuron with respect to distributional uncertainty modeled by a $\\chi^2$ divergence. The authors prove convergence to within a constant factor of the optimal value. The proof of this results proceeds by calculating lower and upper bounds on a duality gap. Unfortunately, prior work shows that finding an algorithm that converges to optimality is in general computationally infeasible, so this is the best result one could hope for.", "questions": "Does your algorithm actually converge? The classical perceptron algorithm is not guaranteed to converge when OPT$\\neq 0$. \n\n\nDo you have a stopping criterion for your algorithm?\n\n\nOther comments:\n\n\nIn the introduction/title/abstract: when you discuss \"robustness\" and \"adversarial\" you should make it clear that you don't mean adversarial robustness\n\n\n1st equation below line 74: The $(=\\Lambda_{\\sigma,\\rho}\\ldots)$ portion is very confusion\n\n2nd equation below line 74: why is there another expectation over $(\\mathbf x ,y)\\sim \\rho)$? This expectation was already computed in the definition of $L_\\sigma$ in the line above\n\nlines 84-88: it seems your algorithm only considers \"reweightings\" of the sampled points for $\\hat \\rho$. Does this suffice for modelling the entire $\\chi^2$ ball around $\\hat p_0$?\n\n\nline 144-145: \"This condition is ..requires convergence\". It's really not obvious that this condition holds at initialization, or that convergence would imply that it holds for all iterates\n\nline 204: What is $h(r)$?\n\nline 212-213: Shouldn't Assumption 2.3 always be true because the sample data set is finite? \n\nline 250: $M$ was not defined\n\nline 273: Why would one consider looking at $\\sum_{i=1}^k a_iGap(w_i,\\hat p_i)$? Can you better motivate this quantity?\n\nlines 274-276: this was hard to understand\n\nline 214-216: this comment was also non obvious", "limitations": "Yes. The authors acknowledge that their theorems don't prove convergence.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "Learning with a single neuron (aka the perceptron algorithm) is a well-studied method in machine learning that sheds light on the behavior of more complicated methods. The authors seek to understand this method in the context of distributional uncertainty modeled by a chi-squared divergence.", "weaknesses": "1. **Main concern 1**.  The steps and intermediate quantities of Algorithm 1 were not sufficiently explained.  For instance: the step size  $a_i$ is chosen to always be larger than 1. Why does the algorithm not diverge with such a choice? What is the \"interpolated quantity\" $g_i$? Can you explain the choices for $v$ and $w$ in lines 4 and 6?\n\n2. **Main concern 2**. The set $\\mathcal P (p_0)$ is not sequentially compact. Thus one cannot conclude the existence of the maximizer $q_w$ defined in the second equation below line 74 just from compactness. The existence of this maximizer seems to be related to properties of the $\\chi^2$ divergence. Could you elaborate?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On our problem formulation and the perceptron algorithm:**\n\nWe 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.\n\nThe 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.\n\n**On the “convergence” of Algorithm 1:**\n\nRecall 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].\n\nThe 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.\n\n**On stopping criteria:**\n\nWe 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.\n\n**On the existence of the maximizer $q_{\\mathbf{w}}$:**\n\nEven 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$.\n\n**On the motivations behind the steps and intermediate quantities of Algorithm 1 and its analysis with Gap functions:**\n\nThe 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.\n\nOn 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).\n\n**On sufficiency of reweighting of samples:**\n\nBecause 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^*$.\n\nPlease 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:\n\n- Line 250: $M$ is defined in Eq (6).\n- Line 214 – 216: We will cite Claim E.2, where this point was explained formally.\n- 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.\n- 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$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their valuable time and feedback. We are encouraged by the reviewers’ positive comments about novelty (3Jnc) and importance of the problem (ehoc, aZHR).  
  
Here we address some common concerns and give more detailed responses to the reviewers’ specific concerns below.  
  
# Adversarial label noise versus adversarial robustness
  
Our paper explores the problem of learning a single neuron robustly in the presence of adversarial label noise and distributional shifts. It is important to distinguish between different models of robustness.  
  
**Adversarial label noise:**  
  
There are several ways to model the label noise. In this paper, we consider the standard agnostic setting where the goal is to find the best-fit function (in our case, in terms of the $L_2^2$ loss) to arbitrary given labels; as explained in Lines 24–26 of our paper. In the case of boolean functions, [KSS92] proved that the agnostic setting is equivalent to learning with maliciously corrupted labels.  
  
**Adversarial robustness:**  
  
In modern deep learning literature (e.g., [GSS14]), robustness to perturbed inputs at test time is often referred to as adversarial robustness. This type of robustness guards against small perturbations to the inputs of neural networks that lead to incorrect model outputs. While our paper does not address this model directly, we acknowledge the distinction and will add a sentence to clarify our focus. Additionally, there are existing works (e.g., [SND18]) that discuss the relationship between distributionally robust optimization (DRO) and adversarial robustness.  
  
**References:**  
[GSS14] Goodfellow, I. J., Shlens, J., & Szegedy, C. (2014). Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572.

Meta-review: This paper studies PAC learning of a single neuron under distributional shifts of covariates and adversarial label noise. Prior works have established hardness results for distribution-independent learning and for exact learning (where approximation ratio must be 1). This paper gives a polynomial-time algorithm that achieves a constant-approximation ratio guarantee when the underlying distribution is well-behaved. A major technical novelty of the algorithm is utilizing the primal-dual toolkit to track a potential function and showing that it is decreasing over the iterations.

The paper is overall well written and reviewers agree that it carries out novel technical contributions and the results look sound. The proposed approach may inspire a line of research on bridging optimization and structural nonconvexity.
Decision: Accept (poster)