Agnostically Learning Single-Index Models using Omnipredictors
Authors: Aravind Gollakota
Parikshit Gopalan
Adam Klivans
Konstantinos Stavropoulos
Venue: NeurIPS 2023 poster (2023)
Keywords: generalized linear models
single-index models
agnostic learning
pac learning
logistic regression
omnipredictors
multiaccuracy
calibration

Abstract: We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable setting or required the activation to be known. Moreover, we only require the marginal to have bounded second moments, whereas all prior work required stronger distributional assumptions (such as anticoncentration or boundedness). Our algorithm is based on recent work by Gopalan et al. [2023] on Omniprediction using predictors satisfying calibrated multiaccuracy. Our analysis is simple and relies on the relationship between Bregman divergences (or matching losses) and $\ell_p$ distances. We also provide new guarantees for standard algorithms like GLMtron and logistic regression in the agnostic setting.

Agnostically Learning Single-Index Models using Omnipredictors
Aravind Gollakota Apple
Parikshit Gopalan Apple
Adam Klivans
Konstantinos Stavropoulos
UT Austin
UT Austin
Abstract
We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable setting or required the activation be known. Moreover, we only require the marginal to have bounded second moments, whereas all prior work required stronger distributional assumptions (such as anticoncentration or boundedness). Our algorithm is based recent work by Gopalan et al. [2023] on omniprediction using predictors satisfying calibrated multiaccuracy. Our analysis simple and relies on the relationship between Bregman divergences (or matching losses) and lp distances. We also provide new guarantees for standard algorithms like GLMtron and logistic regression in the agnostic setting.
Introduction
Generalized Linear Models (GLMs) and Single-Index Models (SIMs) constitute fundamental frame- works in statistics and supervised learning [McCullagh, 1984, Agresti, 2015], capturing and general- izing basic models such as linear and logistic regression. In the GLM framework, labeled examples (x, y) are assumed to satisfy u u(E[[y/x) monotone function (called the link function) and is an unknown vector. Single-Index Models (SIMs) are generalization in which the monotone link function u is also unknown.
w x (or E[ylx x] = u - x)). where u is a known
In the realizable setting where the labels indeed generated according to GLM with known Lipschitz link function, the GLMtron algorithm of Kakade et al. [201 1] is a simple and efficient learning algorithm. When the ground truth is only assumed to be SIM (i.e. the link function is unknown). can be learned efficiently by the Isotron algorithm [Kalai and Sastry, 2009, Kakade al., 2011].
In this work, we consider the significantly more challenging agnostic setting, where the labels are arbitrary and not necessarily realizable by any SIM. Importantly, we do not fix a link function in advance; our goal is to output a predictor that has squared error comparable to that of the optimal SIM with arbitrary monotone and Lipschitz link function. We can equivalently view this natural squared-ue error regression problem in which the final optimality guarantee must hold with respect to all SIMs with bounded weights and monotone, Lipschitz link functions.'
Formally, consider a distribution over T x [0, 1] and denote the squared error of function _2d IR by errz(h) Exx,))>D((> {())) Let (St(SIM) denote optimal value of erra (h) over all SIMs h with bounded weights and arbitrary 1- !-Lipschitz monotone activations (we call the inverse -1 of link function u the activation function). Given access to samples from D, the goal of an agnostic learning algorithm is to compute a predictor p Bd + [0, 1] with error erty (p))(p) that, with high probability over the samples, comparable the error of the optimal SIM:
(p) opt(SIM) +e.
In this context, in recent times it has also been common to refer to the class of GLMs (resp. SIMs) as the class of single neurons with known (resp. unknown) activation functions.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our main result is the first efficient learning algorithm with a guarantee of this form.
Theorem 1.1 (Informal, Theorem 3.1). Let SIMB denote the class of SIMs of the form x 1 u -w x) for some 1-Lipschitz function u and [| & B. Let D be any distribution over I2 x [0, 1] whose marginal on I2 has bounded second moments. There is an efficient algorithm (Algorithm 1) that agnostically learns SIMB over D up to error
err2(p) S O opt(SIBB)) +E.
This result provides a guarantee comparable to that of the Isotron algorithm [Kalai and Sastry, 2009, Kakade al., 2011] 1] (which also tackles the SIM setting, where the link function is unknown) but for the challenging agnostic setting rather than the realizable setting (where opt(SIMp, D) = 0). Moreover, Isotron's 's guarantees require the distribution to be supported on the unit ball, whereas we only require mild second moment condition.
In our view, this result helps establish Algorithm (and indeed any algorithm to compute omnipredic- tors, as we introduce and discuss shortly) as an efficient and powerful off-the--shel supervised learning algorithm, akin to random forests gradient-booste trees.
natural question is whether our guarantees are near-optimal, c.g., whether we can obtain a guarantee of the form erra(p)
opt (SIMM obtained using efficient algorithms [Goel et al., 2019, Diakonikolas et al., 2020a, Goel et al., 2020, Diakonikolas et al., 2021]. We partially justify the form of our guarantee by showing in Section 5 (adapting a result due to Diakonikolas et al. [2022a]) that one cannot avoid a dependence on the norm bound B. Further closing the gap between upper and lower bounds is important direction for future work.
However, there is strong evidence that such results cannot be
Overview of techniques. We now describe the main ingredients and techniques that go into proving Theorem 1.1. Our starting point is the connection between GLMs and so-called matching losses [Auer et al., 1995]. This connection arises from the fact that fitting GLM with known link function is equivalent to minimizing (over the class of all linear functions) a certain convex loss known as the matching loss corresponding to that link function (see Definition 1.8). (We refer the reader to [Gopalan et al., 2023, See 5.1] for a more detailed discussion.)
Importantly for us, minimizing the matching loss corresponding to link function u yields meaning- ful guarantee even in the agnostic setting, where the Bayes optimal predictor (i.e. x x E[y x)) is not necessarily a GLM at all. Specifically, it turns out to be equivalent (via Fenchel-Legende duality) to finding the closest predictor to the Bayes optimal predictor in the metric of the Bregman divergence associated with the link function u (see e.g. [Gopalan et al., 2023, Lemma 5.4)).
This is a powerful observation, but it still assumes that we have a fixed and known link function in mind. In the agnostic setting, it is arguably unrcalistic to assume that we know the best link function for the distribution at hand. Remarkably, recent work by Gopalan et al. [2022, 2023] has shown that there exist efficient learning algorithms that simultancously minimize all matching losses corresponding to arbitrary monotone and Lipschitz link functions. Their solution concept is called an onnipredictor, i.e., single predictor that is able to compete with the best-fitting classifier in class C as measured by a large class of losses (as opposed to just a single pre-specified loss, as is standard in machine learning). They obtain such predictors through calibrated multiaccuracy [Gopalan et al., 2023] or multicalibration [Gopalan et al., 2022].
From the point of view of ordinary supervised learning regression, however, optimality guarantee in terms of such matching losses or Bregman divergences is hard to interpret. A much more standard metric is simply that of squared error. The key final step for results is to find a way of translating (a) optimality (ranging over all linear functions) in terms of all matching losses simultaneously into (b) optimality (ranging over all SIMs) in terms of squared error. We do by proving simple analytic distortion inequalities relating matching losses to Ep losses, which we believe may be of independent interest.
On a technical level, to prove these distortion inequalities we first prove strong versions of such inequalities for matching losses arising from bi-Lipschitz link functions (see Lemma 2.2). We then obtain our results for general Lipschitz link functions by carefully approximating them using bi- bi-Lipschitz link functions (see Lemma 3.3).

---

Further applications. As further applications of our approach, if we let opt denote the optimal value of errz (h) over all GLMs of the form x + u ( x), where || S B, we obtain the following result about bi-Lipschitz link functions (including, for example, the Leaky ReLU).
Theorem 1.2 (Informal, see Theorem 2.1). Let u - I be bi-Lipschitz invertible link function. Then, any predictor p: IR + that an s-approximate minimizer of the population matching loss that corresponds to u, with respect to a distribution D over TR x [0, 1] satisfies
err2 (p) S ((optGGLM, 1,B)) + O(E)
This guarantee holds under milder distributional assumptions than are required by comparable prior work on agnostically learning GLMs single neurons (Frei et al., 2020, Diakonikolas al., 2022b]. Moreover, when we focus on distortion bounds between the logistic loss and the squared loss, we obtain a near-optimal guarantee of O(opt (LL,..,,)) link function (i.e., when GLM B is the class of sigmoid neurons).
v)) for logistic regression, when u is the logit
Theorem 1.3 (Informal, see Theorem 4. 4.1). Let u(t) = In( Then, any predictor p IRd IR that is an approximate s-minimizer of the population logistic loss, with respect to a distribution D over Rd x [0, 1] whose marginal on TR. has subgaussian tails every direction satisfies
(p) S ((opt(GLM.-1.s) + +(E)
While our error guarantee for this problem is weaker than that of Diakonikolas et al. [2022b], we do not make the anti-concentration assumptions their results require.
1.1 Background and Relation to Prior Work
We note that matching losses have been studied in various previous works either implicitly [Kakade al., 201 1] explicitly [Auer al., 1995, Diakonikolas et al., 2020b, Gopalan et al., 2023] and capture various fundamental algorithms like logistic and linear regression [McCullagh, 1984, Agresti, 2015]. However, to the best of our knowledge, our generic and direct approach for transforming matching loss guarantees to squared error bounds, has not been explored previously, Furthermore, our results do not depend on the specific implementation of an algorithm, but only on the matching loss bounds achieved by its output. In this sense, we provide new agnostic error guarantees for various existing algorithms of the literature. For example, our results imply new guarantees for the GLMtron algorithm of Kakade et al. [2011] in the agnostic setting, since GLMtron can be viewed as performing gradient descent (with unit step size) on the matching loss corresponding to a specified link function.
Matching losses over linear functions are also linked to the Chow parameters [O' Donnell and Servedio, 2008] through their gradient with respect w, as observed by Diakonikolas et al. [2020b]. In fact, the norm of the matching loss gradient is also linked to multiaccuracy, a notion that originates to fairness literature [Hebert-Johnson matching loss that corresponds to a GLM with link u is associated with a multiaccurate predictor [d] E xx (y p(x)) = 0. The work of
al., 2018, Kim al., 2019]. A stationary point w of a
p(x) = (w x), i.e., a predictor such that for all [Gopalan et al., 2022, 2023] on omnipredictors presents a single predictor that is better than any linear model w x for every matching loss. The results of Gopalan et al. [2022] show that a multicalibrated predictor (with respect to the features x.) is an omnipredictor for all convex losses, whereas Gopalan et al. [2023] shows that the simpler condition of calibrated multiaccuracy suffices for matching losses that arise from GL.s. In view of the relationship between multiaccuracy and the gradient of the matching loss, our results show that, while multiaccuracy implies bounds on agnostically learning GLMs, the additional guarantee of calibration is sufficient for agnostically learning all SIMs.
The work of Shalev-Shwartz et al. [201 I] showed strong agnostic learning guarantees in terms of the absolute error (rather than the squared error) of the form opt + for range of GLMs, but their work incurs an exponential dependence on the weight norm B. In comparison, for the absolute loss, we get a bound of the form B opt log(1/opt) for logistic regression (see Theorem 4.3). In more recent years, the problem of agnostically learning GLMs has frequently also been phrased as the problem of agnostically learning single neurons (with a known activation). For the ReLUU activation, work by Goel et al. [2017] showed an algorithm achieving error opt + E in time poly(d) exp(1/e) over marginals on the unit sphere, and Diakonikolas et al. [2020b] showed an algorithm achieving error
3

---

((opt) + E in fully polynomial time over isotropic Lonccveevve marginals. The work of Frei et al. [2020], Diakonikolas et al. [2022b] both show guarantees for learning general neurons (with known activations) using the natural approach of running SGD directly on the squared loss (or regularized variant thereof). Frei et al. [2020] achieves error O(opt) for any given strictly increasing activation and (opt for the ReLU activation, but they assume that the marginal distribution is bounded. In contrast, we only assume that the marginal distribution has bounded second moments and we do not consider that the activation is known. Diakonikolas et al. [2022b] proved an (opt) guarantee for a wide range of activations (including the ReLU), in the setting where the activation is known and over large class of structured marginals, which need, however, to satisfy strong concentration and amti-concentration properties.
In terms of lower bounds and hardness results for this problem. the work of [Goel et al.. 2019, Diakonikolas et al., 2020a, Goel et al., 2020, Diakonikolas et al., 2021, 2022a] has established superpolynomial hardness even for the setting of agnostically learning single ReLUS over Gaussian marginals.
Limitations and directions for future work. While we justify a certain dependence on the norm bound B in our main result on agnostically learning SIMs, we do not completely justify the exact form of Theorem 1.1. An important direction for future work is to tightly characterize the optimal bounds achievable for this problem, as well to show matching algorithms.
1.2 Preliminaries
For the following, (x. .y is used to denote a labelled sample from a distribution D over R&d y, where Y' denotes the interval [0, 1] unless it is specified to be the set {0, 1}. We note that, although we provide results for the setting where the labels lie within [0. 1], we may get similar results for any bounded label space. We use Pn (resp. p) to denote the probability (resp. expectation) over D and, similarly, Ps (resp. IEs)) to denote the corresponding empirical quantity over a set S of labelled examples. Throughout the paper, we will use the term differentiable function to mean a function that differentiable except on finitely many points. Our main results will assume the following about the marginal distribution on Rd
Definition 1.4 (Bounded moments). For À 2 and & E N. we say that distribution Dx over Rd has b-buunded 2k-th th moments if for any E gd-1 we have Ex~D, x) )2) < A.
For concept class C Rd - R. we define opt D) be the minimum squared error achievable by a concept e Rd + IR in C with respect to the distribution D. We now define our main learning task. Definition 1.5 (Agnostic learning). Let C: Rdd + E be concept class, let V [o, 1] + [0, 1] be an increasing function, let D be distribution over Rd x [o. 1] and >> O. We say that an algorithm A agnostically learns the class C up to error Vr (opt C, D)) + e if algorithm A. given number of i.i.d. samples from D, outputs, with probability least 2/3 over the samples and the randomness of A. hypothesis h d + [0, 1] with Edi(y h(x)) || < v (opt(C, +
We will also provide results that are specific to the sigmoid activation and work under the assumption that the marginal distribution is sufficiently concentrated.
Definition 1.6 (Concentrated marginals). For À > 0 and y, we say that a distribution Dx over Rd is (X, )) concentratdd if for any v E gd-1 and r 2 0 we have Px~ lIv x 2 r] S X exp(-r"). Definition 1.7 Fenchel-Leegndde pairs). We call pair of functions (f,g) a Fenchel-Legendre pair if the following conditions hold.
1. o' R IR is continuous, non-decreasing, differentiable and 1-Lipschitz with range ran (g') 2 (0, 1) and g(t) = [ (r) dr, for any E R.
2. f ran(g') - R is the convex conjugate (Fenchel- transform) of g, i.c., we have f(r) suPEER r t g(t) for any r E ran(g').
For such pairs of functions (and their derivatives g') the following are true for ran(g') and t E ran(f') (note that ran(f') is not necessarily IR when g' is not invertible).
g'()(rr) = and f(r)- = rf" gr)((r)), for ran(g') (t) = t and g(t) = tg' (t) f( (t)), for torte E ran(f")
(1.1)
(1.2)

---

Note that g' will be used as an activation function for single neurons and f corresponds to the unknown link function of SIM (or the known link function of GLM), We say that g' is bi-Lipschitz if for any 1 < L2 E R we have that (12) - I' (41))/(12 - 41) E (a, .... If g' is [ax, 3] bi-L.pschitz, then I' [g. a bi-l.ipschitz. However, the converse implication is not necessarily true when g' not strictly increasing.
Definition 1.8 (Matching Losses). For non-decreasing and Lipschitz activation g' - R, the matching loss lg y x R + I is defined pointwise as follows:
(v, = /. g'(r) - dr,
where g(t) - g'. The function by is convex and smooth with respect to its second argument. The corresponding population matching loss is
Lg(c; (x.y)~
E &o c(x))
(1.3)
In Equation (1.3), e Rd + IR is some concept and D is some distribution over 12d x [0, 1]. In the specific case where c is a linear function, i.e., c(x) = w x, for some w E R then we may alternatively denote (e(e; ; D) with (w(w; D).
We also define the Bregman divergence associated with to be for any q, r E ran()'). Note that (g,
with equality iff q r.
Definition 1.9 (SIMs and GLMs as Concept Classes). For B > O, we use SIMg to refer to the class of all SIMs of the form x + s'(w x) where ||w]]2 S and g' 1-Lipschitz monotone activation that is differentiable (except possibly at finitely many points). We define GLM,'. similarly except for the case where g' is fixed and known.
is an arbitrary
We also define the notion of calibrated multiaccuracy that we need to obtain omnipredictors in our context.
Definition 1.10 (Calibrated Multiaccuracy). predictor p Rd [0, 1] is called e-multiaccurate if for all i E [d]. [1] p(x))]l & e. It called e-calibrated Ep(x) Eeleox p(x)] & e.
2 Distortion Bounds for the Matching Loss
In this section, we propose a simple approach for bounding the squared error of a predictor that minimizes a (convex) matching loss, in the agnostic setting. We convert matching loss bounds to squared loss bounds the two losses. In particular, for given matching loss Cg. we transform guarantees on Cg that are competitive with the optimum linear minimizer of Cg to guarantees on the squared error that are competitive with the optimum GLM whose activation (g') depends on the matching loss at hand.
generic way, through appropriate pointwise distortion bounds between
We now provide the main result we establish in this section.
Theorem 2.1 (Squared Error Minimization through Matching Loss Minimization). Let D be distribution over Rd [0. 1), let < a S 3 and let (f.g) g) be Fenchel-Legendre pair such that R is Ja, bi-Lipschitz. Suppose that for a predictor p Bdd ran(g') we have
Lgll'
D); op;
5 min Cy(w; D) +
(2.1)
liw
Then also have: errz(p) < opt
23e.
The proof of Theorem 2.1 is based on the following pointwise distortion bound between matching losses corresponding bi-Lipsehitz link functions and the squared distance.
Lemma 2.2 (Pointwise Distortion Bound for bi-L link functions). Lei O < a S B and let (f.9) be a Legedre pair such that f' ran(g') - IR is [ 2) bi-Lipschirz. Then for any E ran(g") we have
f')
- (y, Dy
(u 2)2 23
(y p)²
2a
5

---

In the case that f' is differentiable on (0, 1), the proof of Lemma 2.2 follows from an application of Taylor's approximation theorem of degree 2 on the function f. since the Bregman divergence Dy (v. p) is exactly equal to the error of the second degree Taylor's approximation of f ((y) around p and (() E ( I for any & E ran(g'). The relationship between lg and y follows from property (1.2). Note that when g' is (a, (3] bi-Lipschitz, then f' [ a bi-Lipschitz.
Theorem 2.1 follows by applying Lemma 2.2 appropriately to bound the error of a predictor p by its matching loss (ff' p) and bound the matching loss of the linear function corresponding to w" by the squared error of g' (w" x). where g/ (w" x) is the element of GLMg' B with minimum squared error.
Although Theorem 2.1 only applies to bi- bi-Lipschitz activations g'. it has the advantage that the assumption it makes on corresponds to a convex optimization problem and, when the marginal distribution has certain concentration properties (for generalization), can be solved efficiently through gradient descent on the empirical loss function. As consequence, for bi-Lipschitz activations we can obtain (opt) efficiently under mild distributional assumptions in the agnostic setting.
3 Agnostically Learning -nngle-Index Models
In this section, we provide our main result on agnostically learning SIMs. We combine the distortion bounds we established in Section 2 with results from Gopalan et al. [2023] on Omniprediction, which can be used to learn a predictor p that satisfies the guarantee of Theorem 2.1 simultaneously for all bi-Lipschitz activations. By doing so, we obtain result for all Lipschitz and non-decreasing activations simultaneously.
Theorem 3.1 (Agnostically Learning SIMs). Let X, B 2 1, > and let D be a distribution over Rd x [0, 1] with second moments bounded by X. Then, Algorithm I agnostically learns the class SIMB over D up to squared ervor O(BVX / D)) + E using time and sample complexity poly B, X, 1). Moreover, the same is true for any algorithm with an onniprediction guarantee like the one of Theorem 3.2.
In order to apply Theorem 2.1, we use the following theorem which is a combination of results in Gopalan al. [2023]. where they show that the matching losses corresponding a wide class of functions can all be minimized simultaneously by an efficiently computable predictor.
Theorem 3.2 (Omnipredictors for Matching Losses, combination of results in Gopalan et al. [2023]). Let X, L. R, B 2 1, > and let D be a distribution over Rd x [o, 1] whose marginal on Rd has X-bounded second moments. Then, Algorithm 1, given sample access D, with probability at least 2/3 returns predictor p= Rdd - (0, 1) with the following guarantee. For any Fenchel-Legende pair (J,9) such that g' TR. T.. is T. L.-Läpschitz and j' takes values within the interval [- R, Ri, p satisfies
C, o p; ;D S min Lg(w; D) + +
||w |2
The algorithum requires time and sample complexity poly (X, B, R, 2).
Algorithm 1 is a version of the algorithm of Gopalan et al. [2023] for calibrated multiaccuracy. specific to our setting. For a more quantitative version of Theorem 3.2, see Theorem C.3 in the appendix.
We aim to apply Theorem 3.2 to the class of all Lipschitz activations (which is wider than the class of bi-Lipschitz activations). This is enabled by the following lemma, whose proof is based Theorem 2.1 and the fact that the eиror of a predictor is bounded by the sum of the error of another predictor and the squared expected distance between the two predictors.
Lemma 3.3. Let D be a distribution over Rd x [0, 11. Let : be some fixed activation, and I' its dual. Consider the class GLMg B. and let w be the weights achieving opt(GLMg',) D). Let o' : RR- + R be an [a, 3) bi- bi-Lipcchitz function (differentiable except possibly at finitely many points) that we wish to approximate g' by. Any predictor p : Rdd - IR that satisfies
LalS' op; D);
< min Lo(w: D) +
also satisfies the following Eg error guarantee:
233 errg v oLL BB) + 28
x))² (d((w' - 0'(w" xx)= + 2,e,.
E
a
a

---

Algorithm 1: Calibrated Multiaccuracy (modification of Algorithm 2 in Gopalan et al. [2023])
Input: Sufficiently large training set over TRd [0, 1], parameters E, X, B, I,
Output: A predictor p R + (0,1)
Form training set S' by substituting each element (x, y) in S with (x. y²) where y' {0. 1) is formed as follows. Conditioned on y, let y/ be an independent Bernoulli random variable with probability of success y-
Let A B L, C a sufficiently large universal constant and let 5 CA'AR 20 Set p 0 (the zero function).
repeat
repeat
Let S" be subset of S' with |s C' and set S' <- S' S" Form set T by substituting each element (x, of S" with (x, 2), where z²
2 == V/ - -((x).
Let Ti (x.))TT 2x.
Reject if ||v||2 3(E (VA5)/(4A).
Otherwise, let w = Bv/llvile and update to be the following predictor
x (p(x) + o(w x))10111, where (f)) = min m (t, 0}, 13 until some iteration rejects (which happens when it has found multiaccurate predictor);
Let Rdd > [0, 1] such that pd (x(x = E1 j81 (p(x) E 1j}, where
1; [ )5 (j })
Let S" be subset of S' with |S" = A"
log( AAR), set S' t S' S" and let
sy [(x. y') E S" p (x) j8}.
Estimate the calibration error [x)( (x)l p" (x))l of p" using the samples in S" according to the following expression
1/8
S SH
18
8//. where ūj
Σ
(x,y))s;
If the estimate has value at most s/2, then output o and terminate. Otherwise, update p to be the following (calibrated) predictor
1/8
Σ Us 11 (x(x) E 1
X
1=0
until some iteration terminates the execution;
By combining Theorem 3.2 with Lemma 3.3 (whose proofs can be found in Appendix C), we are now ready to prove our main theorem.
Proof of Theorem 3.1. We will combine Theorem 3.2, which states that there an efficient algorithm that simultancously minimizes the matching losses corresponding to bounded, non-decreasing and Lipschitz activations, with Lemma 3.3, which implies that minimizing the matching loss correspond- ing the nearest bi-Lipschitz activation is sufficcient to obtain small error. Note that we may assume that E < 1/2, since otherwise the problem is trivial (output the zero function and pick C = 2).
As first step. we show that link functions corresponding to bi bi-Liischitz activations are bounded (according to Definition C. for ? = 0). In particular, let o' I - I be an [a, ( bi-Lipschitz activation for some 3 2 a >> 0 such that d'(s) [-1, for some R and let v/ be the inverse of ø' (ø' is invertible since is strictly increasing). We will show that v/l ()(rr) E R, R for any E [0, 1] and R. O(ss] 1/a).
7

---

We pick ro = 0, = 11 and get that (0'(s) - - (no)) v [s) rol - 3. Hence ui (ro) 2
('(( - 2
-. Similarly, we get (r1) s 2. Therefore, (r) E (0) e e1) S
[1|s] 2 |s| + 2.1 for any r [0, 1], due monotonicity of v'..
For a given non-decreasing and L-Lipschitz g'. we will now show that there is a bounded bi- bi-Lipschitz activation o' such that if the assumption of Lemma 3.3 is satisfied for o' by predictor p. then the eиror of is bounded by
errz(p) & (B
O(AB²s)
Suppose, first, that (pt(GLMg S 8², Then, we pick (1(1)= = g (t) + st. Note that Øf is [s, 1 + bi-Lipschitz. Moreover, since opt g' BB) S E², we must have some s E R with |s| S 2XB² such that (s) E [-1,2]. Otherwise, we would have (p = [i x) -y) 2 Ellg' (w* r y)² ww' I PAB'II-P[ww--x S 2AB*] 2 PP[lw -x| S 2A = --
2XB ž = due to Chebyshev's inequality, the fact that w" W and the bounded moments assumption. Therefore, & is (R 2XB² 2.7 O)-bounded and have
E (d'(w' x) - p'("" x))
S e² B[(w" x) S <
As consequence, under the assumption of Lemma 3.3 for ø', the emror of the corresponding predictor p is er)2(p) s 2(1 + E)s 2(1 + e)EAB² + 2(1 + e) = O(A2e)).
In the case that opt (GLM gB) > x2, we pick (1) g1())+ +6 that opt(GLMg',Ft S 1/2, since otherwise any predictor with range [0, 1J will have error at most 2opt .B). Then, & is (O(AB² + ())))))bounded, ø' is (op bi- bi-Lipsehitz which gives
/oLL BV
We may also assume
Bl
E (d(ww' x) - 8' p''w"'a' x)) 27
}
Opt(GLM BD)
Bl(w" x) S opt(GLM, ,B)
B
As a consequence, under the assumption of Lemma 3.3 for ø', the error of the corresponding predictor is (p))(p) < 4(1 + + BVA (GLLM B) + 2(1 + ).. Using a similar approach as for the case (GLM gr .B) S E, we can show that eb' is polynomially bounded (as per Definition C.1), since (GLM ,B) S 3
To conclude the proof of Theorem 3.1, we apply Theorem 3.2 with appropriate (polynomial) choice of parameters (R O + BVX), ). L 2), to show that there is an efficient algorithm that outputs a predictor p= RRd - (0, 1) for which the assumption of Lemma 3.3 holds simultaneously for all bi- bi-Lipschitz activations (Ø') with sufficiently bounded inverses (v²).
4 Stronger Guarantees for Logistic Regression
In this section, we follow the same recipe we used in Section 2 to get distortion bounds similar to Theorem 2.1 for the sigmoid activation (or, equivalently, the logistic model) under the assumption that the marginal distribution is sufficiently concentrated (see Definition C. In particular, Theorem 2.1 does not hold, since the sigmoid is not bi-Lipschitz and our main Theorem 3.1 only provides a guarantee of ((vopt) for squared error. We use appropriate pointwise distortion bounds for the matching loss corresponding to the sigmoid activation and provide guarantees of Ö(ppt) for logistic regression with respect to both squared and absolute error, under appropriate assumptions about the concentration of the marginal distribution. The proofs of this section are provided in Appendix D.
For the logistic model, the link function f' is defined as fr(r) In((T")), for (0, and the corresponding activation g' is the sigmoid g' (4) I for E R. The corresponding matching loss is the logistic loss.
1
Squared error. We first provide result for squared loss minimization. In comparison to Theorem 2. the qualitative interpretation of the following theorem that, while the sigmoid activation not bi- bi-Lipschitz, it is effectively bi-Lipschitz under sufficiently concentrated marginals.
8

---

Theorem 4.1 (Squared Loss Minimization through Logistic Loss Minimization). Let D be distri- bution over Rd [0. whose marginal on IR.' is (1, conccenraaee Let g' R be the sigmoid
activation, L.e,, g'(1) (1) = (1 + for E IR. Assume that for some B > 0, E > 0 and a predictor
p: p: + (0, we have
Lg(f op;
min Co(w: D) +
(4.1)
w: w
If we let opt mwnl las errz(gw), then for the predictor and some universal constant C > 0 we also have
err2(p) S C Coplg exp
B² +
Ba log
+ 25.
opt
In particular, the squared error of is upper bounded by ( since the function t + exp(log" /2 t) asymptotically smaller than any polynomial function t + fr with O.
Once more, the proof of our result is based on an appropriate pointwise distortion bound which we provide below. It follows by the fact that the Bregman divergence corresponding to the sigmoid is the Kullback-Leibee divergence and by combining Pinsker's inequality (lower bound) with Lemma 4. of Götze al. [2019] (upper bound).
Lemma 4.2 (Pointwise Distortion Bound for Sigmoid). Let g' be the sigmoid activation. Then, for any V.P E (0, 1) we have that DD (v.p) = (vll)) = y In(u/p) (1 y) In(
+ Moreover
(')) Cg (vlll)
1 2 p)3
2
(y D)²
min (p,
We translate Lemma 4.2 to bound on the squared error of a matching loss minimizer (in this case, the logistic loss) using approach similar to the one for Theorem 2.1. In order to use the upper bound on the surrogate loss provided by Lemma 4.2, we apply it to p <- g'(w x), where g' the sigmoid function, and observe that the quantity p(I-p} is exponential in w x|. Hence, when the
marginal is (x, conccenntee (subgaussian concentration), then p(1-p) is effectively bounded.
Absolute error. All of the results we have provided so far have focused on squared error min- imization. We now show that our approach yields results even for the absolute error, which can also be viewed as learning in the p-concept model [Kearns and Schapire, 1994]. In particular, for a distribution D over Rd [0, 1], we define the absolute error of predictor p R jo, 1] follows.
erri (p) (x,g)>~> [1 - p(x)]
In the specific case when the labels are binary, i.e., y E {0, 1}. we have erri (p)
E Ilv p(x)]] = (x,9)~D
F [y + ypl
(see Proposition A.2)
where the distribution Dp is over Rd x 10. x {0.1) and is formed by drawing samples (x. y) from D and, given x, forming yp by drawing conditionally independent Bernoulli random variable with parameter p(x). We provide the following result.
Theorem 4.3 (Absolute Loss Minimization through Logistic Loss Minimization). Let D be a distribution over Rd x {0. 1} whose marginal on Rd is (1, concentaecee. Let g' IR - R. be the
sigmoid activation, i.e., g((t) = (1 +l+e e e-t)= for E R. Assume that for some B > 0, E > and a predictor p : Rdd 1) we have
(f D)
min fy(w; D) + w
(4.2)
If we let opt, = minn|w/las err, (dw), then for the predictor and some universal constant > we also have
erri (v) < C Bopt, log + opt
The corresponding distortion bound in this case between the absolute and logistic losses and works when the labels are binary.

---

Lemma 4.4 (Pointwise Distortion between Absolute and Logistic Loss), Let g' be the sigmoid activation. Then, there a constant E R such that for any y E {0, 1} and p E (0, 1), we have
((1 p)) ( ly
fl C c lV pl. 2-In
pl
The bound of Theorem 4.3 implies an algorithm for learning an unknown sigmoid neuron in the p-concept model, by minimizing a convex loss. While there are algorithms achieving stronger guarantees [Diakonikolas al., 2022b] for agnostically learning sigmoid neurons, such algorithms typically make strong distributional assumptions including concentration, anti-concentration and antiaanticonncentration or boundedness.
Moreover, it is useful to compare the bound we provide in Theorem 4.3 to a lower bound by Diakonikolas et al. [2020c, Theorem 4.1], which concerns the problem of agnostically learning halfspaces by minimizing convex surrogates. In particular, they show that even under log-concave marginals, no convex surrogate loss can achieve guarantee better than (opt log(1/opt)) where opt is measured with respect to the l eπгоr (which is equal to the probability of error). The result is not directly comparable to our upper bound, since we examine the sigmoid activation. Their setting can be viewed as a limit case of ours by letting the norm of the weight vector grow indefinitely (the sigmoid tends to the step function), but the main complication is that our upper bound is of the form O Bopt log(1 / /opt)), which scales with B. However, their lower bound concerns marginal distributions that are not only concentrated, but are also anti-concentrated and anti-anticoncentrated. while our results only make concentration assumptions.
5 Necessity of Norm Dependence
In this final section, we use a lower bound due to Diakonikolas et al. [2022a] on agnostic learning of GLMs using SQ algorithms and compare it with our main result (Theorem 3. For simplicity, we specialize to the case of the standard sigmoid or logistic function. A modification of their proof ensures that the bound holds under isotropic marginals."
Theorem 5.1 (SQ Lower Bound for Agnostically Learning GLMs, variant of [Diakonikolas et al., 2022a, Thm C.3l). Let g' Rdd - R be the standard logistic function. Any SQ algorithm ei- ther requires (1()) queries or d11(1) tolerance to distinguish between the following two labeled
distributions:
(Labels have signal.) Dsignal on Rd x IR is such that opt(GLMg' ,B, Deignai) S cxp( exp(-S((lg"/ 1/4 d)) o(1 for some B poly(d).
(Labels are random.) Draudom on Rdd x such that the labels y are drawn i.i.d. from {a. b) for certain universal constants b E 10, In particular, opt(GLMg BB, Drandom) = 2(11) for any B.
Both D Dsignal and Drandom have the same marginal on Rd, with 1-bounded second moments.
Let us consider applying our main theorem (Theorem 3.1) to this setting, with D being either Daignal or Drandom. and with the same B = poly(d) d) as is required to achieve small error in the "labels have signal" case. We would obtain a predictor with & error at most B / /opt (PpLM .BM (or indeed with SIMB place of GLMggn) Since this is (1), this guarantee insufficient to distinguish the two cases above, which is as it should be since our main algorithm indeed fits into the SQ framework.
Theorem 5.1 does, however, justify dependence on the norm B in main result. In particular, it is clear that a guarantee of the form opt apt(GLM,... (yMM)..)) _B) for any universal constant >> 0 (independent of would let distinguish the two cases above. In fact, this lower bound
B) would be too strong, rules out a large space of potential error guarantees stated as functions of B and opt .B). For instance, for sufficiently large d, it rules out any error guarantee of the form exp(O(log!) B)) (t for any universal constant e' > 0.
SSpecifically, our features correspond to all multilinear monomials (or parities) of degree at most over [+1]", whereas they use all monomials (not necessarily multilinear) of degree at most k. These yield equivalent representations since the hard distributions obtained from the uniform distribution on (=1)"
10

---

Acknowledgments and Disclosure of Funding
We wish thank the anonymous reviewers of NeurIPS 2023 for their constructive feedback. Aravind Gollakota was at UT Austin while this work was done, supported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Adam R. Klivans was supported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Konstantinos Stavropoulos was supported by NSF award AF- 1909204, the NSF AI Institute for Foundations of Machine Learning (IFML), and by scholarships from Bodossaki Foundation and Leventis Foundation.
References
Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishabiiity. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LiPics, pages 60:1 1-0:200. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2023. (document), 1, 1.1, 3, 3, 3.2, 3. I, C.1, C.3, C.1. C.1, C.1
Peter McCullagh. Generalized linear models. European Journal of Operational Research, 16(3); 285-292, 1984. ISSN 0377-2217. doi: https://doi.org//// wt..o....../../.........1 10001011660777722177499993333330 https:/ htopp:://www..e httpp://www..sceecceee www.scciiieeert...cccmc.. com/
URL
wtt./cccccccceeec// science/ article/ attiiclepp..007771177888888 /tt////327222221922222222 I, 1.1
Alan Agresti. Foundations of linear and generalized linear models. John Wiley & Sons, 2015. 1, 1.1
Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of generalized linear and single index models with isotonic regression. Advances Neural Information Processing Systems, 24, 2011. 1, 1, 1.1
Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT 2009 The 22nd Conference Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009. 1, 1
Surbhi Goel, Sushrut Karmalkar, and Adam Klivans. Time/accuracy tradeoffs for learning relu with respect gaussian marginals. Advances in neural information processing systems, 32, 2019. 1, 1.1
Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 53:13586-13599 2020a. 1, 1.1
Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147-2158, 2020. 1.1
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. The optimality of polynomial regression for agmostic learning under gaussian marginals in the sq model. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1552-1584. PMLR, 15-19 Aug 2021. 1, 1.1
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. Hardness of learning single neuron with adversarial label noise. In Gustau Camps- Valls, Francisco R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3199-8213. PMLR, 28-30 Mar 2022a. 1, 1.1, 5.1
Peter Auer, Mark Herbster, and Manfred K. K Warmuth. Exponentially many local minima for single neurons. D. Touretzky, M.C. Mozer, and M. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8. MIT Press, 1995. URL https: / http::// :/ttopeee//rroceeinggg neurips cc/ Paper pdf. 1,
paper_fille 1.1
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Om- nipredictors. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Bigsstul--Leibiiz--ee für Informatik, 2022. 1, 1.1
11

---

Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-5428, 2020. 1.1
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning a single neuron with adversarial label noise via gradient descent. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4311-3333664 PMLR, 02 02-05 Jul 2022b. URL https::/ppocced///e mlr. wwt.s//wesse/////eeeee wwwdddiiiaalaasaa
html. 1, 1, 1.1,4
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi, Approximation schemes for relu regression. In Conference Learning Theory, pages 1452-1485.
PMLR, 2020b. 1.1
Ryan O'Donnell and Rocco A Servedio. The chow parameters problem. In Proceedings of the fortieth anmual ACM symposium on Theory of computing, pages 517-526, 2008. 1.1
Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cal- ibration for the Commuuationally--denfffaa
masses. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1939-1948, PMLR, 10-15 Jul 2018. URL https://pree httpps://rroceeding.. mlr www.srresssvvvveee
vacass//vvO// http//////hhbbbbeeeeeeeeeeeeeeee https///aabebeerooooooooooooooae johnson18a. html.. 1.1
Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post- post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference AI, Ethics, and
Society, pages 247-254, 2019. 1.1
Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan. Learning kernel-based halfspaces with the 0-1 loss. SIAM Journal on Computing, 4066):1623-1646, 2011. 1.1
Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in polynomial time. In Conference on Learning Theory, pages 1004-1042. PMLR, 2017. 1.1
Friedrich Götze, Holger Sambale, and Arthur Sinulis. Higher order concentration for functions of weakly dependent random variables. Electronic Journal of Probability, 24:1-19, 2019.
Michael J Kearns and Robert E Schapire. Efficient distribution-free learning probabilistic concepts. Journal of Computer and System Sciences, 48(3):464-497, 1994.
Ilaas Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Non-convex sgd learns halfspaces with adversarial label noise. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18540- 18549. Curran Associates, Inc., 2020c. URL https: neurips cc/paper_ fi files fi1.:pprr000011110555770000//220
12

---

A Technical Lemmas
In this section, we provide some technical Lemmas that we use our proofs.
Proposition A.1 (Weak Learner for Linear Functions). Let D be distribution over Rd [-1,1 1] whose marginal on R' has X-bounded second moments and B >> O. For any & O and ó E (0, 1), there is a universal constant C' 0 and an algorithm that given a set S of i.i.d. samples from D of size at least C 8'B²² log 3. runs in time ((d and satisfies the following specifications with probability at least 8
If ((xx))=DD=(W x)] 2 E for some w E RRd with [w]l2 S B, then the algorithm accepts. Otherwise, it may or may not reject and return special symbol.
2. If the algorithm accepts then it returns w E R with |wll S B such that we have E [(x.)))D(2(W x)] 2 e/4.
Proof. We will prove the proposition for å 1/6. We may boost the probability of success with repetition.
The algorithm computes the vector Es[2x]. If ||v|22 I
4B* then the algorithm rejects and outputs special symbol. Otherwise, it outputs the vector [v]l V.
Suppose, first, that E(x,,)) <( x)] 2 E for some w with | 1w/22 S B. Then, due to Chebyshev's inequality we have for any i [d]
B2
B4 X
1
P
E
El=
S
[[x]]
(for large enough |S))
Bvd
151
6d
Hence, with probability at least 5/6. we have [s[2x] Therefore, ||v|22 2 [
- -Ep[2x] 11 S 8B. due to a union bound.
||l
En x))
3 2
7B 8
and the algorithm accepts.
8B
8B
Suppose, now, that the algorithm accepts. Then, we have ||v 5/6) we have
and (with probability least 1B
B (v x)]
E
Tvll B[2x] 2 e/4
[[vl
since
|| [s[2xx] ED[2x]]l S s This concludes the proof.
Proposition A.2. Let D be distribution over Ed x {0,1) 1} and p R2 [0, 1]. Consider the distribution Dp over Rdd x 1).1} x 10,1}, which is formed by drawing samples (x, y) from D and, given x, forming yp by drawing a conditionally independent Bernoulli random variable with parameter p(x). Then we have
erri(p)=
E (x.v)~D
fly p(x)]] (x.M.8p)~Dp
ly + Upl
Proof. Since over Dp, y and y, are conditionally independendent, we have
erri (p) E[yy p(x)]] [L - p(x)) 11 p 0}}
EE
1 0 = 1|x] Plyp
x Pl 0|x]
E Ply * yp
B Proofs from Section 2
B.1 Proof of Theorem 2.1
To prove Theorem 2.1, we first prove the following more general theorem. Theorem 2.1 may then be easily recovered from this by setting = GLMMg' and observing that f'(g'(w x)) = w X, since is invertible.
13

---

Theorem B.1 (Squared Error Minimization through Distorted Matching Loss Minimization). Let D be a distribution over R [0. 1), ler 0 < a S 3 and let (f.9) be a pair of Fenchel-Legendee dual functions such that g' I + R is continuous, non-decreasing and f" rrangg') - R is 7 al
bi- bipsiish Let & > and H C { [Rd + ran(g')}- Assume that for predictor p I + ran( we have
Cf o D) & min Cg(f" +); +
(B.1)
bEH
Then, for the predictor p, we also have: erry (p) 1 _
a min errz (h) + 235.
Proof. We apply Lemma 2.2 with y <- y and pxx) and take expectations over D on both sides. We have that
(p)) s 28 E (y (p(x)) 23 Blg f'()) Therefore, we can bound the squared error of p as follows.
errz(p) 28 (J' op; D) - 23 Q"
23 22 o h; D) - 23 Q"
(by assumption, for any h E H)
where Q (V, (1()).
We now apply Lemma 2.2 again with y f y and f- hxx) and we similarly have
E (y, fo o (x)) Q- - err
20
Therefore, for any h H. we have, in total: (p) 8 crrz (h) 2,5.
We first prove Lemma 2.2, which we restate here for convenience.
Lemma B.2. Assume I' is (/o) bi-Liphchitz and differentiable all except from a finite number of points on any bounded interval. Then for any y, E ran(g') we have
= Lgly. E
E
23 (y
p)²
(y p)²
2a
Proof. We first show that -()))))))))) =
In particular, we have
s(((v)) = -VV) = -v(),
since fp) E &ranff) and we know that g(t) = tg((t) f()( for any ran(f") as well as g'(l' = for any p E ran(g'). Therefore, we have
(y())((p)) Lv, f()) = ((f - (f) - =(f (v)) + yf
(fp) = ppf - (()) - uf - vf + f(v) + (v)
= =f(y) f(p) - (y--) (v-
Let vb : ran(g') + R be such that ('(p) = fp( and w is differentiable on the open interval
between y and p. with (E(E) E [1/3, 1/a] for any & between y and p. Let 7/ == f(y) (iv)), 7p
f(D) (()) and To = max 7ybb 1mm Then we have that
1 Dy(,,))= v(p) (y p)) (7y -7p) (0)=)00(6 (E)( pp)² - (7 7p)
1 (y p)2 2 20
1 (v p)² + 2%
Dy(,,p) E
[8
for any s as defined above (say wb E V) In particular, we have
Dy(1.P) <
(y p)² + inf weo
TV and
2a
1 p)2
Dy(u,))
2 inf 70
23
VEv
Since, we have only a finite number of points where the derivative not well defined, a simple smoothening technique may give us v such that inf Yv- = 0.
D
14

---

C Proofs from Section
C.1 Proof of Theorem 3.2
We first define a boundedness property which we use in order to apply the results from Gopalan et al. [2023]. The property states that the activation function (the partial inverse of the link function) must either have range that covers all possible labels, or has a range whose closure covers all possible labels and the rate with which the labels are covered as we tend to the limits of the domain is at least polynomial. For example, the sigmoid activation tends to 1 (resp. 0) exponentially fast as its argument increases (resp. decreases).
Definition C.1 (Bounded Functions). Let (0, 1) - I be non-decreasing function defined on the interval (0, 1). For R, 2 O, we say that u is (Rt, -bbuunded on [0, 1] if for any e > 0, there are ro ri [0, such that if we let u(ri) limm- u(r), i 0, then
! E
(oxx)-(ro).-ooo) w(r1)) -
(1 (1-ri)(u(r) - u(ri)) < for 1i and ro(u(ro) - u(r)) I & for to
Proposition C.2. Let u (0,1) - (-R, R)) non-decreasing and continuous, then u is (R, 0)- bounded.
restate a more quantitative version of Theorem 3.2 here for convenience.
Theorem C.3 (Omnipredictors for Matching Losses, combination of results in Gopalan et al. [2023]).
Let D be a distribution over Id x [0, 1] whose marginal on IR' has X-bounded second moments. There is an algorithm that, given sample access to D, with high probability returns predictor
P TR + (0. 1) with the following guarantee. For any pair of Fenchel-Legende dual functions (J g) such that g' : R -> continuous, non-decreasing and T-Llipschizz and I is (R, 7-)-ounded (see
Definition C.I), P satisfies
Cf Dp: S
min Cg(w; +E. I/ WBBB
The algorithum requires time
(BBBL and sample complexity
(
3 3+37
+ dd 2 ARA
3 4+47
10 3 12+127
log
BLAR gl+7
(BBLLR
3 3+37
+ +BB
3 10+109
log
BLAR
E clty
Proof of Theorem 3.2. The idea of the proof (given by Gopalan et al. [2023]) is that in each repetition of both the inner and the outer loop of Algorithm 1, there is potential function which reduces by some amount that bounded away above zero. The potential function is in fact the function EpI(p*(x) p] where p² (x) Eply' |x] (for us, y is formed by drawing Bernoulli random variable with probability of success y, given example (x, y) E Rdd x [0, 1] drawn from D). Since Epl(r" (x) - p E 1). the number of iterations of each of the loops has to be bounded. Moreover, after the completion of each of the inner loops, the current value of p corresponds to an approximately multiaccurate predictor and note that the algorithm terminates and only if a discretized version p of (the multiaccurate) is approximately calibrated. The output is then pd which is close to (and hence also approximately multiaccurate), but also approximately calibrated. We will now present small number of technical modifications Gopalan et al. [2023] in order to specialize it to our setting. The main difference here is that we do not consider the distribution of have bounded norm with probability 1, but we only assume it to have bounded second moments. For the following, we assume that g is 1-Lipschitz, since we can set B B L and push the Lipschitz constant in the domain of w.
need to make in the proof of
Suppose first that the marginal of D on T2d is supported on the unit ball B and that the labels are binary. Then, the result would follow from Theorems 7.7 and A.4 of Gopalan et al. [2023]. In particular,
15

---

Theorem 7.7 states that given access to weak learner with the specifications of Proposition A.1, there an efficient algorithm that computes an cacaibrrat and (C, )multiaccurate predictor p. where the notions of calibration and multiaccuracy originate to the literature of fairness and are defined, e.g.. in Definitions 3.1 and 3.2 of Gopalan al. [2023] and (x - w |w/l S B] U xx 1] (the class C. is bounded as long as ||x||2 I 1 almost surely). Theorem A.4 states that for E2 > 0. any E Ey-calibrated and (C, E1 muultaccurrte predictor p minimizes simultaneously the matching loss corresponding to any pair (f.g) F (where is (R, 7--bundedd up to error
R(1/E2) + 52
The expression above formed by proving that any pair (f.g) E F has the property that f is (#2, R((/e2)))))))))))) " japproximmatlly optimal (as per the Definition A.1 of Gopalan et al. [2023]), for any E2 > O. In particular, we would like to show that for any E2 > there exists f such that the following true for any [0, 1]
Co(r, (())) s [f(t)) S R (1/e2)7
+
We may pick / follows (for ro 11 as given by Definition C.I for +- E2, since f' is (R, 7)- bounded).
f(r), e [ro.7i] ((r) ('(o), ifr < ro
(((r), ifr>
The desired result follows from using the expression for lg. the convexity g (since g' is non decreas- ing) and the guarantees of Definition C.1. In particular, we have that f s (fo)l since f is increasing. Moreover, for [ru,ri] we have (r fr)) (g(r, (r)) and for ro we have
(r =
-rf'(())))) +f)) (())) -rf(())))) (ro(f(ro) (((())
(since g convex)
(since f' is increasing and ro) (since I' is bounded according to Definition C.1)
5 (r)( lolr, + +
Similarly, for r > 1ı, have
=
$n((mm)-((()++(((>>-----
(since g convex)
((L=))//())-((())=)0(()))))))--- (since f' is increasing, 1> r. r1) (since f' is bounded according to Definition C.1)
S + (((())))))-r
(r. +
In order acquire R(1/e2) Tei + + + S e, we 82 e/3 and (5/3)2+7/1)
However, we only assume that the marginal distribution has X-bounded second moments and we, therefore, need to make certain modifications the proof of their Theorem 7.7. In particular, the boundedness assumption used in the proofs of Lemma 7.2, Lemma 7.6 and Theorem 7.7 in Gopalan et al. [2023].
During the execution of Algorithm 1, two types of updates are made. The first type of update is done within the inner loop and corresponds to beginning from predictor Pold and acquiring Pnew which the function x + (Pota(x) + a x)) where w the output of the weak learner of our Proposition A. run with < (Ex will be specified later). To lower bound the decrease in the potential function during this type of update, we use a version of Lemma 7.6 in Gopalan et al. [2023]. In this case, one needs to pick step size that is polynomially smaller than the guarantee that the
16

---

weak learner provides. In particular, if the weak learner of our Proposition A. is run with E t E3. then one acquires (following the proof of Lemma 7.6 in Gopalan et al. [2023])
E(("" (x) Potal (x))² Ei(p (x) - Pnow (x))² 2
8. B²X0²
2
If picked be - then the quantity of interest [[(p Pola (x)) El(p" (x)
Puew (x))²) is lower bounded by T6Bax Hence the number of iterations of the inner loop is upper bounded by O Eg (or another corresponding parameter) does not appear in their proofs. The updated choice of generates a polynomial overhead in time and sample complexity. We pick E3 = } - BvA6) so that each time we exit the inner loop, we have that, with high probability, the current value of p corresponds to an (#) Bv -ulliiautaa predictor.
c3
B² Note that in their original algorithm,
picked equal E3 and this is why
The second type of update (the outer loop update) is a calibration step where Pnew set to be the following function with the notation of Algorithm
1/6 x
Σ 1 (x) 1j} 1=
In this case, Corollary 7.5 of Gopalan et al. [2023] can be used as is to acquire that Ei Pola(x)) [ El(p"
- Pnew (x))² 2 &f if we set ô S st/C for some large enough universal constant C' > 0. Hence, the number of iterations of the outer loop is upper bounded by O(1/ef).
It remains to show that once the algorithm terminates, the output is approximately calibrated and multiaccurate. Regarding multiaccuracy, whenever we exit the inner loop, the current value of corresponds (with high probability) to an (E) Bv Aō) -illmuutiaceurate predictor. The predictor yd is close to p in absolute distance and therefore can be shown be approximately multiaccurate using some version of Lemma 7.2 in Gopalan et al. [2023]. In particular, following the proof of Lemma 7.2, the multiaccuracy guarantee for pd changes to (C, a + ( -uuliacccca, where is the multiaccuracy guarantee for p. by using a Cauchy-Schwart inequality and bounding [E[(w x) by B² X. Since a ε V5, the multiaccuracy guarantee é1- The calibration guarantee follows by the fact that the termination criterion corresponds to empirically checking whether p is calibrated and by using Lemma 7.4 in Gopalan et al. [2023], the empirical estimate should be close to the true calibration error. Overall, once we terminate, the output is 5 calibrated and multiaccurate.
Since the time and sample complexity of each of the calls of the weak learner depends on E3, pick =2 c(+ so that E3 = ((E)) and 8 < T
8
required.
Sample Complexity. For each of the inner loop iterations, we require a fresh sample of size 0 B as specified by Proposition A.I (by setting the probability of success to a sufficiently si
small constant). For the outer loop, we require O 1=="X log( L+BA )) samples per iteration, so that
the calibration eиror estimate is accurate enough, according to Lemma 7.4 in Gopalan et al. [2023].
Time Complexity. Each of the inner loop iterations requires O
time and each of the outer
loop iterations requires additional O(d $
11 57"
log(
L+BA
time.
The final technical complication we need to address that their algorithm works only given binary labels. We can, however, form binary labels as follows. Let (x,y) be drawn from D. We have that
y E (0, 1]. Given y,. we draw an independent Bernoulli random variable y' with probability of success y. forming the distribution D' over Rd {0, 13. We run the algorithm of Gopalan al. [2023] on
D' and receive a predictor p such that
LJ o op; < min C. (w; D') +e, for any (f.9) E F wEW
17

---

We have that
Lg(c;D') = E [((((())) s/((x)
x.y'
= E g(((x)) - -E E [M/] M]
x c(x)
= g(c(x)) - -IE Ev x] c(x)
E [g(((x)) - yc(x)] = (o D) x.y
This concludes the proof of Theorem 3.2.
C.2 Proof of Lemma 3.3
We first apply Theorem 2.1 with g' +- ø' to get that for (x) = d'(w x), we have
B
(p) erra (or2(dw.)) 2,e
(since inequality holds for E W)
a
Moreover, have
E (v o' (www. x)) 21
err2(ow.)
E / (w" r. x) + 96 (w" x) p'(w" x)) 2
s 2 13 (v (ww". x)) 27
(g'(w' x) p'(w" xx) 27
+ 21
2opt, 2E (o'(w" x) d'(w". .x)) )²
This concludes the proof lemma 3.3.
D Proofs from Section
D.I Proof of Theorem 4.1
In the case we consider here, g' is the sigmoid activation, i.e., (() (1 (1+ f for any / E R. In particular, the pointwise surrogate loss we consider satisfies
f'()) yn + y) In I-p In2,
for any y E [0, 1] and p E (0.1). We may extend Lemma 4.2 also capture y E (0, 1}, by defining (0, (0)) (1)) - In (the inequality would hold under this definition). Hence, following similar procedure as the one used for proving Theorem B.I, we obtain the following by applying Lemma 4.2
(F12(p) s (C p) - EEe, ('()))
(D.1)
C,(w)) (V, f' < E
gg(w" x) V (1 g'(w" (y gg((w" xx))²
2
(D.2)
C, p) < (,(w))+
(D.3)
Therefore, in order to prove Theorem 4.1. it is sufficient to provide a strong enough upper bound for the quantity of the right hand side of Equation (D.2) terms of opt,. We observe that
2
g'(w' vI g'(w' xx) I 4exp((w" xl), for any x gd
18

---

It remains to bound the quantity B[elW"x((( -w (x))²]. Set Q e w Iw (x))² (Q is random variable). Then for any 2 we have
(y
[ E 1( w/""" x - r + EQQ 1( w" x x|>11 r|
S E" EV - Sw- (x)) [[ x| S r}] + Ele! w x 1f >
e opt Efe W' [ r]
To bound the quantity Ele!w w x 1( w* x > r}}. consider F(s): == P > r 2 s]. We have that
F(s) 1/s 0) Pr| w' r] Pr||w" xx 2 max(Ims,r)]
Since Eiee /w x 1( w" x > r}] - F() ds = S. Pr[]w" x 2 max(Ins, r] ds, we obtain
E[Q]= =
Pr | x 2 max r ds
3=0
In
Pr W x 2 B
ds
Pr W x
ds
(since || 12 S B)
5=0
s=c"
Se" -1/B) +
(Ins/B)² ds
(see Def. 1.6)
S=
= -c to" c1 du
(define In r)
0 te e (r/B)²
82
x
-uu- 3)
e
E
du
u=0
(r/BB)
Therefore, in total, we have that err (p) S opt + BC (re-BB/) 25 and we may obtain
Theorem 4.1 by picking r = (In 1 1/2
opt
D.2 Proof of Theorem 4.3
We first prove Lemma 4.4. We have that for any E {0, 1} and (0
Ly (p) = y In 1 +1 y) --p In = CE(y. p) In
where CE(y, p) is the cross entropy function. is sufficient to show that for E (0, 1} and E [0, 1],
1
Iy - pl S CE p) s 2/y - pl log
(D.4)
p(1 - p)
Observe that
CE(O,,) p) = log
(D.5)
1=1
where the series on the right converges for all 1.
We can also write
CE(L,) = H
(1-p)*
(D.6)
1
with the series converging for p > For the lower bound, we observe the following incqualities hold for all p E [0,
CE(O,)) 2 = 10 - pl
CE(1,p) 2 p pl.
19

---

For the upper bound, we first prove the claim for = O, where it states that
CE(O,p) = loog 1- p
v 2p log
(D.7)
p(1 p)
When p S 1/2 we can use Eq. (D.5) bound
CE(O.))
S 2p.
(D.8)
1- p
i=1
The bounds holds by observing that since p(1 - p) 2 1/4,
log
2 llog(4) 21
p(1 ((1-p)) p)
When 2 1/2, we note that
log
2 log
1-p = =CF(O.p)
p(1 p)
and 2p 2 Hence the bound holds this case too.
In the case where 1, the bound states that
- 5
1 2 p) log
1
CE p) = log
p(1 p)
This is implied by our bound for y by taking q p. This concludes the proof of Lemma 4.4 and we are ready to prove Theorem 4.3. The following are true
op) err, (p) - Lf(f p) - In2
(D.9)
1
C,(w") - 2. In
g'(w" x) 9 g'(w" x)) xx()*
-1v - g'(w" x)
(D.10)
Lg( op) s fo(w))+
(D.11)
Similarly the proof of Theorem 4.1, observe that In g'(w" x) (1 9 (w"
5 In |w" x
remains to bound the quantity [[[W" x| byy - Sw [x] Set Q = | x| by - dw (x) (Q is random variable). Then for any 2 we have
[[Q] EBQ 1 ( x| S r}] E(Q 1 f|ww" x| > r}
< < &e. (x) 1//w" x < r + Bllw" x 1[/w" x > r]]
o + | -/|w" x > r|
To bound the quantity Bi|w" x| 1[[w--
x > r}}. consider F(s) = Pr|| x| 1(|w" x| >
r} 2 s). We have that
F(s) [ 0} Pr[|w" x S r| + Pr[lw" x 2 max(s,7]) 7)]
Since Bl[ B" x 1 f||w x| > r}] _ F(s) ds f Pr[[w* x 2 max s, r]] ds, we obtain
E[Q] =
Pr Pr|lw* x| 2 max r]] ds
5=0
$ f Pr W x
ds +
Pr
W
x
ds
(since | 112 S B)
1=20
B
S rr er-e-1/B +
e B/B c ds
(see Def. 1.6)
= e r + riB
Therefore, in total, we have that err, (p) < 21 4- opt, + 2(r + B/e + 2r -ptt, + e and we
may obtain Theorem 4.3 by picking = B In 1.
opt
20


Reviews:
[{"review_id": "MCitzJqB2D", "reviewer": "Reviewer_VkT9", "summary": "This work studies the problem of agnostically learning single index models with arbitrary Monotone and Lipschitz activations. Compared prior work, this work establishes the existence of an learning algorithm under more relaxed assumptions. This work is based on recent work by Gopalan et al. [2023] on Omniprediction using predictors satisfying calibrated multiaccuracy.", "questions": "My questions are raised in the previous section. ", "limitations": "This paper may benefit from polishing up the write-up and make it more friendly for general ML researchers or practitioners. ", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "This paper studies a difficult but realistic setting, and the topic of agonistically learning single index model is very interesting and important in itself. ", "weaknesses": "I find this paper a bit difficult to read for general researchers in the machine learning community, especially those who are not familiar with the related literature. \n\nI also have a (perhaps naive) question about the claims in the abstract and line 33. It seems to claim that this paper devises an \"algorithm\" that can efficiently learn SIM in an agnostic setting, I wonder what is the algorithm actually? It seems all theoretical results in this paper are all pointing to the existence of such an algorithm, but not an actual algorithm that can be used to estimate it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the anonymous reviewer for expressing their concerns about the readability of our paper. \n\nAs we stated in the global response, we are planning to make certain modifications which we believe will significantly improve the readability of our paper by researchers of diverse backgrounds. The reason we believe so is that there were no objections on the overall structure of our paper and in particular (after resolving a small number of issues pointed to by the reviewers): The introduction section contains minimal technical formalism and should be accessible by researchers of diverse backgrounds. It contains the definition of our setting, its significance, informal versions of our main results (Theorems 1.1, 1.2, 1.3) as well as several pointers to prior work for further reading (e.g., Section 1.1). The following sections of our main paper contain some technical details, but we view this as a strength rather than a weakness, since it contributes to the precision of our statements, which is important for the problem we consider. That said, Section 1.2 provides the required background for the following sections. Hence, Sections 2, 3, 4 and 5 should also be accessible by a diverse audience, although an in-depth approach might be easier for researchers in the respective area.\n\n  Regarding the second question of the reviewer, it is implicit in our proofs that we use the algorithm of Gopalan et al. [2023] for calibrated multiaccuracy (see Section 7.2 of Gopalan et al. [2023]). In particular, the algorithm computes a calibrated and multiaccurate predictor by running a large enough alternating sequence of multiaccuracy and calibration steps (see Algorithm 2 in Gopalan et al. [2023]). The reviewer correctly points out that we should state the algorithm we use explicitly (in pseudocode), which we are planning to do for the camera-ready version of the paper exploiting the additional page allowed for the final version.\n"}, {"review_id": "ZZ17GUGXTT", "reviewer": "Reviewer_Buwi", "summary": "This paper studies the learning of Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. In SIM model, labeled examples $(x, y)$ are assumed to satisfy $E[y|x] = u^{-1}(w.x)$, where $w$ is an unknown vector, and  $u$ is an unknown monotone function (a.k.a. link function). Given IID-drawn samples from an unknown distribution $D$ over $\\mathbb{R}^d\\times [0,1]$, the learner's objective is to minimize a predefined loss (e.g., square loss) among the class of SIM models. This paper presents a learning algorithm with a square loss $O(\\sqrt{opt})+\\epsilon$ if $u^{-1}$ is 1-Lipschitz, where $opt$ is the minimum square error among all SIM models with bounded-norm  $w$.  Moreover, the authors provide related results for standard algorithms like GLMtron and logistic regression.", "questions": "Q1. When do we get the $opt+\\epsilon$ error? \n\nQ2. What about other loss functions beyond the square error and logistic loss? \n\nQ3. The bound for logistic loss scales with B as $e^{B^2}$, isn't that problematic?\n", "limitations": "See weaknesses. ", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is solid, and the proof techniques are interesting. This paper considers a harder problem of the non-realizable case ($opt \\neq 0$) and unknown activation function. Moreover, the analysis is based on more relaxed conditions compared to prior works as it requires the marginals to have bounded second moments. ", "weaknesses": "The paper claims (in the title and abstract) to prove agostic learnability. This is misleading! First, agnostic in the PAC learning context implies no distributional assumptions on the labeled samples, but a bounded second moment is assumed in this work. \nSecond, the agnostic learner has an error $opt+\\epsilon$ which is clearly not the case here! The bound in Theorem 3.1 is of the form $O(B\\sqrt{opt})+\\epsilon$, where $B$ is the bound on $||w||$. \nGiven that the paper shows \"weak learnability\" as best.   \n\nThe paper is well-written in general but there are several typos that need to be corrected: \n- The notation for sphere, $\\mathbb{S}^{d-1}$, is not defined. \n- Line 158: is $f'$ the derivative of $f$?\n- Line 169: $d$ is missing:  $c:\\mathbb{R}\\to \\mathbb{R}$ need to be  $c:\\mathbb{R}^d\\to \\mathbb{R}$\n- Line 180: $d$ is also missing. \n\n\nI think it would be better if Definition 1.4 and 1.5 were written as Assumptions. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the anonymous reviewer for their comments and for appreciating our work. \n\nYou make the point in your review that ‘agnostic learning’ should mean ‘distribution-free agnostic learning,’ as the term was defined in the 1994 Kearns Schapire paper that originally defined the model.   We would like to stress that the way we (and others) use the term ‘agnostic learning’ to mean ‘distribution-specific agnostic learning’ is now standard and has widely appeared as such in the literature over the past two decades. More concretely, the two concerns of the reviewer about our use of “agnostic learning” were the following 1) we make an assumption on the marginal distribution of the features (note that we do not make such an assumption on the labels) and 2) the form of the error guarantee. Both of these restrictions are now common in the (classical and recent) agnostic learning literature. For example, see Theorem 3 in the classical paper [1] on agnostic learning of halfspaces (note that the algorithm is still called an agnostic learner) and the more recent paper [2] where they propose an agnostic learning algorithm for a single ReLU neuron with guarantee $\\mathrm{poly}(\\mathrm{opt})$, under some assumptions about the marginal distribution. Note that both of these papers also use the term agnostic learning in their title. The term is generally used to emphasize that the learner is agnostic to how the *labels* are generated and is not tied to a specific learning scenario.\n\n  We also thank the reviewer for pointing out some typos, which we will fix in future versions of the paper. \n\nRegarding the questions posed:\n\nQ1. There have been (statistical query) lower bounds in prior work (see lines 127-130) that provide evidence for the hardness of learning up to $\\mathrm{opt} + \\epsilon$, even when the activation is fixed to be a ReLU and the marginal is the standard Gaussian. Although we have already provided pointers to such lower bounds, we will exploit the additional space provided for the camera-ready version and add more details in Section 1.1.\n\nQ2. We focus on the squared error, which is a standard loss function used in learning theory and provides results comparable to prior work in the field (e.g., [2]). However, our technique is general; our analysis is based on the idea of translating bounds with respect to matching losses to results with respect to the squared loss and it is conceivable that we could obtain results even when we substitute the squared loss with some other loss function of interest, by proving corresponding distortion bounds. We note that this might entail some technical complications, as the squared loss is usually more analytically convenient than other losses.\n\nQ3. The bound we provide for the squared error of the logistic regression algorithm scales indeed exponentially with the bound on the norm of the parameter vector. However, please keep in mind:\n\n1. Some dependence on the norm is expected (since we do not make any anti-concentration assumptions on the marginal) and the result is useful when the norm bound is constant. \n\n2. Prior work contains bounds that are quantitatively similar (with even more assumptions taken). In Theorem 3.3 of FCG [2], where it is assumed that the marginal distribution is in fact bounded, the dependence on the norm bound is also exponential (since their parameter $\\gamma$ in their Assumption 3.1 would decay exponentially with $\\rho$ when $\\sigma$ is the sigmoid). Note that our method can also yield an $O(\\mathrm{opt})$ result for learning the sigmoid if we assume the marginal to be bounded. \n\n3. Our result demonstrates that a standard algorithm (minimizing logistic loss) achieves guarantees that are state-of-the-art at least in some regime. \n4. We once more use our simple analysis approach based on distortion bounds.\n\n[1] Kalai, A.T., Klivans, A.R., Mansour, Y., & Servedio, R.A. (2005). Agnostically learning halfspaces. FOCS 2005, SICOMP 2008.\n\n[2] Frei, Spencer, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. NeurIPS 2022.\n\n"}, {"review_id": "3zNWUIsq8G", "reviewer": "Reviewer_6FFA", "summary": "The paper gives an efficient algorithm for learning Single Index Models with arbitrary monotone and Lipschitz function under the condition the marginal distribution of x has bounded variance in all directions.\n\nThe error guarantee of the algorithm is $O(B \\sqrt{\\lambda} \\sqrt{\\mathrm{opt}})+\\epsilon$ ($B=\\|w\\|_2$ and $\\lambda$ is the bound on variance) which is weaker than some previous result but this paper also has less assumption on the marginal distribution.\n\nThe authors give an SQ lower bound justifying the dependence of their error on B. However, that lower bound does not imply the error need to have a polynomial dependence on B (i.e. a $\\exp (\\log^{1/2} B$) dependence should be suffice to not contradict the lower bound).\n\nThe high level idea of the algorithm is this:\nThe authors considers matching loss as the surrogate loss function.\nIn the agnostic setting, it no longer holds that the matching loss and \nSquared loss has the same minimizer.\nInstead the authors observes that there is a “distortion bound” between matching loss (for bi-Lipschitz function $u$) and squared loss (lemma 2.2).\nNamely, this means for any prediction $p$ and true value $y$, the matching loss is at most off by some offset (which is the matching loss between $y$ and itself) and then a multiplicative factor (which depends on the bi-Lipschitz parameter of $u$). \nThis implies small matching loss implies small squared loss.\n(Up to some $O(\\mathrm{opt})$ error.)\n\nThen the argument follows that in order to learn a SIM with an unknown activation function $u$. \nWe can use existing result to learn a “omnipredictor” that has small matching loss for any bi-Lipschitz function.\nLet $u’$ be nearest bi-Lipschitz function of $u$.\nDue to the boundedness, it suffices to consider $u’$ instead of $u$.\nThis gives their algorithm for SIM.\n\nSome other result they show (using similar idea) are (ignoring the dependence on $B$ in the error):\n1. An distribution independent efficient algorithm for leaning GLM up to error $O(\\mathrm{opt})$ when the activation function is bi-Lipschitz\n2. An efficient algorithm for logistic regression up to $O(\\mathrm{opt})$ under some concentration assumption of the distribution", "questions": "It would be better if the authors can have a paragraph summarizing the high level ideas of the algorithms.", "limitations": "The authors have adequately addressed the limitations.\nThere is potential negative societal impact.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The algorithm holds under very mild assumption on the marginal distribution.\nThe distortion bound the authors prove might also have other interesting applications.", "weaknesses": "The main weakness is the authors do not have a lower bound that can match the upper bound result they give.\nIt would be interesting to see if one can get a better algorithm or prove a tighter lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their suggestions and for appreciating our results. The reviewer is right that it would be interesting to have tight results (at least in the statistical query framework). However, our work not only provides the first upper bound for learning SIMs in the agnostic setting, but also demonstrates a link between the literature of omniprediction (which is in turn connected to notions from fairness like calibration and multicalibration) and the problem of learning SIMs, which might be useful in proving better upper or lower bounds in future work."}, {"review_id": "Rjo87sAuFJ", "reviewer": "Reviewer_uXX7", "summary": "The paper studies the problem of learning SIMs agnostically. The authors proposed an algorithm achieving $B\\sqrt{opt}$ $\\ell_2$-error under mild distributional assumptions. Their main contributions are twofold: 1) they linked the $\\ell_2$ loss of a bi-lipschitz activation with its matching loss. 2) they proposed an algorithm that minimizes the matching loss for all Lipschitz activations. They also showed stronger guarantees for logistic regression and argued that the dependence of norm $B$ is inevitable in the final $\\ell_2$ loss bound achievable for any efficient algorithm.", "questions": "Can the authors provide some intuition about multi-accuracy and multi-caliberation? How do they relate to the omnipredictors for SIMs and matching loss? In particular, what exactly is the relation between multi-accuracy and the gradient of the matching loss, as mentioned in line 110?", "limitations": "I agree with the authors that the potential limitation of this work is the exact dependence of norm $B$ is not justified. It would be interesting future work to find the tightest $\\ell_2$ error bound of the SIMs.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The authors bring in the technique of fenchel duality to study the distortion bound between the $\\ell_2$ loss and the matching loss for GLMs. Even though their idea is similar to theorem 5.5 in [GHK+23], the result is original. In addition, the authors proposed a method using omnipredictors to find a predictor that minimizes the matching loss with respect to all 1-Lipschitz activations. This idea is new to the reviewer. ", "weaknesses": "The result about the $\\ell_2$ error of learning sigmoid activation (thm 4.1) seems weak, as there are already similar results in the literature, see for example, thm 3.3 [FCG20], though in [FCG20] they used lightly stronger assumptions (bounded $D_x$), their $\\ell_2$ error does not have the logarithm factor. A detailed comparison with related works would be helpful to prove the significance of this paper.\n\nThe presentation of this paper lacks clarity and is confusing. There is no clear description of the algorithm proposed by the authors, and the sample complexity and runtime are not clearly stated throughout the paper. There are also a lot of symbols used in the paper that are not defined, to name a few: the term $opt_g$ appeared in the proof of thm 3.1, the $\\varepsilon$ appeared in the statement of thm C.2, and the function $l_2$ used in the proof of thm 3.2.\n\nThe proofs lack readability. For example, in line 261, it is hard to understand why $opt_g\\geq Pr[|w^*\\cdot x|\\leq 2\\lambda B^2]$ without further clarification. It would also be helpful to have more details in the proof of thm 3.2, like the relation between $\\epsilon_1$ and $\\epsilon_2$, and the statement from line 533 to 537. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their comments.\n\n  Regarding the significance of our Theorem 4.1, we stress that our distributional assumption (subgaussian concentration) is significantly milder than assuming the marginal to be bounded (e.g., a bounded marginal is, in particular, doubly exponentially concentrated). In fact, if we assume that the marginal is bounded and follow the same approach through distortion bounds, we obtain the same ($O(\\mathrm{opt})$) guarantee as the one in [FCG20] for the sigmoid (our bounds improve from $\\tilde{O}(\\mathrm{opt})$ to $O(\\mathrm{opt})$). \n\nIn our presentation, we emphasized subgaussian distributions to highlight that our method can handle broad classes of unbounded distributions.\n\n  Moreover, Theorems 4.1 and 4.3 provide new guarantees for the standard algorithm of logistic regression (i.e., minimizing the matching loss corresponding to the logit link) through a simple approach (distortion inequalities). Interestingly, we give the best known guarantees for the case where we only assume subgaussian concentration for the marginal (and no anti-concentration or anti-anti-concentration).\n\n  The algorithm we use is the one proposed in [GHK+23], as is implied within our proofs. In particular, the algorithm computes a calibrated and multiaccurate predictor by running a large enough alternating sequence of multiaccuracy and calibration steps (see Algorithm 2 in [GHK+23]). We are going to provide the pseudocode of the algorithm in the final version of the paper as it will indeed be helpful for the reader. \n\nOur results are focused on providing accurate performance guarantees rather than optimizing the sample or time complexities. For this reason as well as for ease of presentation, we decided to not include the exact quantitative bounds on the sample and time complexity of our algorithm (although we do mention that they scale polynomially in all relevant parameters). However, the bounds are implicit in our analysis and we could extract them in case the reviewers believe this is important.\n\nRegarding the question of the reviewer about line 261, if we assume that $g’(s)\\not\\in [-1,2]$ for any $|s|\\le 2\\lambda B^2$, we have \n$$\\mathrm{opt}_g = \\mathbb{E}[(g’(w^*\\cdot x) - y)^2] \\ge \n\\mathbb{E}[(g’(w^*\\cdot x) - y)^2 \\|\\ |w^*\\cdot x| \\le 2\\lambda B^2] \\cdot Pr[|w^*\\cdot x| \\le 2\\lambda B^2] \\ge 1 \\cdot Pr[|w^*\\cdot x| \\le 2\\lambda B^2],$$\nsince $y\\in [0,1]$.\n\n\n  While multiaccuracy and calibration are indeed relevant to our results, we primarily focus on the use of existing results from the literature of Omniprediction [GHK+23] (where multiaccuracy, multicalibration and calibration notions are presented and studied thoroughly) to acquire bounds for agnostic learning through the idea of distortion inequalities. In particular, [GHK+23] establish a non-trivial connection between fairness and omniprediction, while we focus on establishing a non-trivial connection between omniprediction and classical agnostic learning. \n\nIn general, a calibrated predictor $p(x)$ has the property that conditioning $x$ on any of the level sets of $p$ (so that $p(x) = v$), the expected value of $y$ is close to the value of $p(x)$($=v$). A multiaccurate predictor is a predictor that is accurate in expectation with respect to its correlation to any function within a given concept class. A predictor that is calibrated and multiaccurate is an omnipredictor with respect to all matching losses corresponding to Lipschitz links (i.e., it minimizes all these matching losses simultaneously – see also lines 108-110 and Theorem 3.2 where the algorithm essentially computes a calibrated an multiaccurate predictor). Finally, as we mention in lines 103-105, the stationary points of a matching loss (points with zero gradient) correspond to multiaccurate predictors (see also Theorem 5.6 of [GHK+23]).\n"}]

Author rebuttal:
We wish to thank the anonymous reviewers for their constructive feedback! In this global response, we provide general responses to concerns shared by more than one of the reviewers and we provide more specific answers in the personal responses.

It is true that our upper and lower bounds on the approximation guarantee are not tight, but we are the first to obtain nontrivial bounds in this very general setting– we succeed simultaneously across all monotone Lipschitz activations.  We also make the first connection between SIM learning and multiaccuracy/omniprediction.  We leave tightening these bounds as an important open problem. 

Some of the reviewers expressed some concerns regarding the readability of our paper. Although this was not a concern shared by all of the reviewers, in order to make our work even more accessible to a more diverse audience, we have a concrete plan that consists of valuable but minimal additions and modifications for the final version (exploiting the additional space allowed). In particular, 1) we will provide a larger amount of detail in Section 1.1, so that the scope of our work with respect to the relevant literature is clearer, 2) we will add a description for the algorithm we use (which is based on the algorithm of Gopalan et al. [2023] for calibrated multiaccuracy) in pseudocode and 3) we will correct typos and make clarifications in our proofs according to the reviewers’ suggestions (or any additional suggestions they provide during the discussion period). Overall, we believe that these changes are minimal, but may resolve much of the concerns raised by some of the reviewers, since there were no major objections on the overall structure of our paper or the architecture of our proofs (i.e., hierarchy of claims/lemmas).

One reviewer compared some of our results to the FCG paper “Agnostic Learning of a Single Neuron with Gradient Descent” – please note that the FCG paper has a hidden factor of d inside their O(opt) bound even when the marginal distribution is a spherical Gaussian, yielding a very weak guarantee (additionally they must know the activation $\sigma$ beforehand).  Our bounds only depend on the second moment of the marginal distribution.  If we make the further assumption that the distribution is bounded as FCG does, then we actually obtain the identical O(opt) guarantee as FCG (we give more comments on FCG below). 


Meta-review: This paper studies the problem of learning single index models (SIMs) in the agnostic setting. The main result is an efficient algorithm that approximately learns the desired function with respect to a general class of marginal distributions within multiplicative approximation ratio of $O(B^{1/2})$, where $B$ is a bound on the $\ell_2$-norm of the parameter vector. The main technique leverages recent prior work by Gopalan et al. on omnipredictors. The problem studied is fundamental and the underlying results and techniques are interesting. Overall, the paper is a solid contribution to this literature and is appropriate for publication at NeurIPS. Some reviewers had legitimate concerns about the current presentation of the work. The authors are encouraged to revise their work accordingly.
Decision: Accept (poster)