Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
Authors: Adam Block
Max Simchowitz
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
smoothed online learning
convex geometry

Abstract: Due to the drastic gap in complexity between sequential and batch statistical learning, recent work has studied a smoothed  sequential learning setting, where Nature is constrained to select contexts with density bounded by $1/\sigma$ with respect to a known measure $\mu$. Unfortunately, for some function classes, there is an exponential gap between the statistically optimal regret and that which can be achieved efficiently.  In this paper, we give a computationally efficient algorithm that is the first to enjoy the statistically optimal $\log(T/\sigma)$ regret for realizable $K$-wise linear classification. We extend our results to settings where the true classifier is linear in an over-parameterized polynomial featurization of the contexts, as well as to a realizable piecewise-regression setting assuming access to an appropriate ERM oracle.  Somewhat surprisingly, standard disagreement-based analyses are insufficient to achieve regret logarithmic in $1/\sigma$.  Instead,  we develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers. Along the way, we develop numerous technical tools of independent interest, including a general anti-concentration bound for the determinant of certain  matrix averages.

Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
Adam Block Department of Mathematics
Max Simchowitz CSAIL
MIT
MIT
Cambridge, MA 02139 ablock@mi edu
Cambridge, MA 02139 ms msimchow@csail edu
Abstract
Due the drastic gap in complexity between sequential and batch statistical learn- ing, recent work has studied smoothed sequential learning setting, where Nature is constrained to select contexts with density bounded by 1/a with respect to a known measure Unfortunately, for some function classes, there is an exponen- tial gap between the statistically optimal regret and that which can be achieved efficiently. In this paper, give computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/o regret for realizable K K-wise linear classification. We extend our results settings where the true classifier is linear an wreeetaraeteeiized polynomial featurization of the contexts, as well realizable preccewise-regresiie setting assuming access to appropriate ERM oracle. Somewhat surprisingly, standard disagreement- insufficient to achieve regret logarithmic in 1/a. Instead, develop novel characterization of the geometry of the disagreement region induced by generalized linear classifiers. Along the way, develop numerous technical tools of indepen- dent interest, including general ootiennnnetttttoon bound for the determinant of certain matrix averages.
analyses are
Introduction
In batch statistical learning, a learner faces set of independent examples drawn from a given distribution, and is tasked with generalizing to novel examples drawn from that same distribution. In sequential or online learning, however, Nature may adversarially select examples to thwart the learner's progress and success defined only in comparison the best priori predictor. Due the wide range of application and minimal set of assumptions, online learning has received considerable recent attention. For concreteness, consider binary classification, where a sequence of T examples takes the form (Z2,.) Vt.) E Rd x f-1,+11 Even in the realizable setting, where there exists true I* in a pre-specified class of functions F for which f (xx) = y: for all / 21,2,.... T), the gap between batch and statistical learning and sequential learning can be drastic: when d = 1, the class of linear thresholds (x) sign - 0) has VC dimension one and is thus learnable in the PAC framework [Wainwright, 2019]. A sequential adversary, however, can select 2, as to force the linear to misclassify 22(T') points [Littlestone, 1988].
To circumvent the pessimism of the sequential setting, recent works [Rakhlin et al., 2011, Haghtalab al., 2020, 2021, Block al., 2022, Haghtalab al., 2022] have studied the smoothed sequential learning paradigm, where the adversary is constrained to choose at random from any probability distribution p. with density at most 1/ar with respect to a known measure μ. The most current of these results point to a striking statistical computational gap: whereas there exist algorithms which attain regret that scales with /Tlog(/a), computationally efficient algorithms can only
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

hope for poly(T/o) regret in general, even against a realizable adversary [Haghtalab et al., 2022, Theorem 5.2]. In many d-dimensional settings, natural choices of μa yield thus the exponential separation in a translates into an exponential separation in dimension. This gap motivates the following question: can the statistical- conpiiaticoottttinnnnnlll gap be eliminated more structured settings? In this work, we answer the question affirmatively for variety of natural function classes. A better understanding of what function classes allow computationally efficient, statistically optimal regret-minimizing algorithms remains promising direction for future research.
exp(-I(dd), and
Contributions. We show that for certain classes of realizable smoothed online classification problems, there exists a computationally efficient algorithm which enjoys the statistically optimal log(T/o) regret scaling, when the base measure j is uniform on the unit-ball. Specifically, we provide computationally efficient algoirthms for achieving the statistically optimal regret bound for the following function classes:
For affine thresholds,
For affine thresholds in nonlinear features,
For K-elass affine classification,
For piecewise affine regression
We also provide lower bounds that demonstrate the statistical optimality of our algorithms. Further- more, we apply results to noiseless contextual bandits and get a fast algorithm that achieves optimal regret dependence on the horizon, up to logarithmic factors. Finally, we present a comple- mentary approach based the perceptron algorithm which is robust adversarial corruptions of the labels yt, and enjoys a polynomial regret in a "directional smoothness" parameter which interpolates between the log(1 1 (og(1//)-guarante))) 1-guarantees attained above in the realizable setting, and the poly(1/o (1/o) bounds from prior work. We emphasize that, though we adopt the smoothed online learning setting of Rakhlin al. [2011], 1]. Haghtalab et al. [2021], Block et al. [2022], we use entirely different techniques involving Ville's inequality [Ville, 1939], geometric measure theory, and convex geometry. Moreover, in none of these works was the question of adapting to realizability explored; thus, we provide the first regret bounds that are logarithmic in both the horizon and the smoothness parameter. We now discuss some related work:
Online Learning. Extensions of classical learning theory to the online setting have proliferated due to the scope of application. Several works [Littlestone, 1988, Blumer et al., 1989, Ben-David et al., 2009, Rakhlin et al., 2015a] have explored the gap in statistical rates between classical and online learning settings, with Littlestone [1988], Blumer et al. [1989] showing that the class of one dimensional thresholds, which is easy to learn in the batch setting, is not learnable with adversarial data. Other works, such as Rakhlin al. [2015a], Rakhlin and Sridharan [2013]. Rakhlin al. [2015b], Block et al. [2021]. Rakhlin and Sridharan [2014] have provided sequential analogues of classical notions of complexity that characterize minimax regret, as well as providing computational separation between classical and online learning [Hazan and Koren, 2016). 6]. Due to the statistical and computational hardness results presented in the aforementioned work, there has been great interest in finding realistic, robust assumptions, such smoothness, that allow for efficient learning.
Smoothed Online Learning. Smoothed analysis was first proposed in Spielman and Teng [2004] as way to explain the success of the simplex algorithm of Klee and Minty [1972] by combining the polynomial time bounds of an average-case analysis with the verisimilitude of a worst-case analysis. Since then, smoothed analysis has been applied to explain the empirical success of many algorithms (Roughgarden, 2021]. In the learning setting, Rakhlin et al. [2011] proposed smoothed adversarics and proved regret bounds for linear thresholds in IRd; their proof, however, nonconstructive and did not achieve logarithmic regret in the realizable setting. The use of smoothed adversaries was essential due to the hardness results discussed above. In a series of works Haghtalab et al. [2020, 2021] generalized Rakhlin et al. [2011 1] and showed the regret depending on the VC dimension was possible in the smoothed online learning setting, albeit with computationally inefficient algorithms.
Recently, Block et al. [2022], Haghtalab et al. [2022] generalized Haghtalab et al. [2021] to allow for continuous labels and, more importantly, provided oracle-effcciet algorithms for achieving vanishing regret in the smoothed setting. These papers also showed that the dependence on a the regret bounds of their oracle-efficient algorithms, which was polynomial, could not in general be

---

reduced to the logarithmic dependence achievable by the inefficient algorithms, thereby exposing statistical computatooo gap. Unlike other recent works such as Block et al. [2022]. Haghtalab et al. [2022], we do not use the coupling approach [Haghtalab et al., 2021] to prove our regret bounds.
Classification with Linear Thresholds. Considering the ubiquity of linear thresholds in classi- fication, the list of relevant references is far too long to include here; as such, we highlight only those most germane to our work. The perceptron algorithm was introduced in Rosenblatt [1958] and margin-based mistake bound was proved in Novikoff [1963]. There have been many variations on and applications of this bound, from Ben-David et al. [2009] using it to bound the Littlestone dimension of linear thresholds with margin to dealing with non-realizable samples [Crammer et al., 2006, Freund and Schapire, 1999]. To the best of our knowledge our work constitutes the first to explore the effect that a smoothed adversary has on the perceptron algorithm.
Disagreement Coefficient and Active Learning. Intuitively, our analysis is similar to works in active learning based on the disagreement coefficient [Hanneke, 2007, 2011, Hanneke et al., 2014, Wang, 2011]. Indeed, as we shall see, our regret bounds arise by bounding the probability that point falls into the disagreement region in similar way as, for example, Hanneke [2007] controls the label complexity of active learning. We will note in Remark 3, however, that an approach grounded purely in the disagreement coefficient cannot hope achieve regret logarithmic in in the smoothed setting. Indeed, our approach incorporates a finer understanding of the geometry, accomodated by the more limited scope of application of our techniques, which allows to prove tight rates.
In Section 2, we setup the learning problem and introduce some necessary notions from convex geometry, as well as fixing notation. In Section 3, we highlight two technical results that form the foundation of our approach, before, as warmup, applying them to the case classification with linear thresholds in Section 4. In Section 5, we generalize beyond linear thresholds to allow for offset and nonlinear features. Finally, in Section 6, we move beyond binary classification by extending our results to K -class affine classification, piecewise affine regression, and noiseless contextual bandits.
2 Preliminaries
In this section, we provide basic definitions and setup the learning problem. We begin by defining a smooth distribution, in Block al. [2022], Haghtalab et al. [2021]:
Definition 1. Let μ be probability measure a measurable space X. For some 0 < S 1, say that a measure p on X is a-smooth with respect if the likelihood de du < is uniformly bounded.
We consider the smoothed online learning setting. First, horizon T N is fixed and a distribution ji on is chosen. For each step 1 1 t S T, Nature chooses a distribution pt. possibly depending on the history, such that pt is a-smooth with respect μ and samples Fe ~ Pt well choosing some y/ E y. The learner sees It, chooses it and suffers loss E(jt, Vt). Given a function class F of functions mapping X - y, the learner attempts minimize regret, where regret is defined as:
T Σ (ff(r)).)) FEB
Regr Σ E(ir. inf
(2.1)
In the sequel, for the sake of simplicity, we take X = By to be the unit ball, f = (ad to be the uniform measure on B4, and E(jt, yc) = 11 + nt) to be the 0-1 loss.
Remark 1 (Scaling of o). A natural example of a smoothed adversary is one that is allowed to place Tt in worst-case manner, which gets perturbed by some small additive noise, chosen uniform on e Bd. to become Fy; this adversary is Ed smooth. For such situations, polynomial dependence on a in the regret translates into something exponential in dimension.
Remark 2 (Other measures μ)). Assuming the dominating measure = pa is not overly strong: if μ da
is another measure on B4 for which dua 2 >>> O, then, because our regret bounds are logarithmic
in a, our resulty will still hold with an additive term of log (t)
For much of the paper, we assume that Nature is realizable with respect to F,i.e., for some f E F, f*(x,) yi for all 1 < < T. In this case, Regr is just mistake bound: Regr =I= 11 # v.).
3

---

The foundations of our analysis consider the class of linear threshold classifiers
F = (x sign((w, w E Bt]
(2.2)
We identify Fi with the set of w's defining it, so that we may treat it as, itself, subset of Bf: other function classes are similarly identified with their parameters (without further comment).
At the core of our base algorithm is the computation of the John ellipsoid [John, 1948, Ball et al., 1997], the maximal volume ellipsoid contained in a convex body.' 1 It is well-known that given a polytope in Rd the John ellipsoid can be computed in time polynomial in d and the number of faces [Boyd and Vandenberghe, 2004]. In particular, we compute the John ellipsoid of the version space, Ft. where for any time t, we let F. {f E T (xx with 1. < T faces. An important concept in our analysis is the notion of Hausdorff measure, which generalizes the standard notions of volume and surface area in IR4; we will denote the k-dimensional Hausdorff measure (see Definition 18) by volx(-)- More detail on both the John ellipsoid and the Hausdorff measure can be found in Appendix B.
Us for all < t). which is polytope
Notation. For a set C R", we denote by Hu its boundary. We let By denote the ball of radius r around the origin in Ed and let g OB Letting denote the I'-function, let wa I74/2-1j denote the volume of Bf and let jul denote the uniform measure B normalized to be probability measure. If Φ IR" + "R" is Lipschitz, we denote the Jacobian by DΦb Lastly, we use "S" to denote inequality up universal, problem-independeer constants.
4/2
3 The Technical Workhorses
In this section we introduce the two key workhorse results that provide the technical foundation for the rest of the paper. The first result is a purely probabilistic statement that throughout the paper to turn probabilistic and geometric theorems into regret bounds in the realizable, smoothed online learning setting. The second result is geometric statement that allows us apply the black box regret bound to the case of classification with affine thresholds.
blackbox
3.1 An Abstract Decay Analysis
We begin with abstract, technical result that will form the basis for all of our regret bounds. We first introduce the following definition:
Definition Let μ. be a measure on some set Z and let & Z {0,1} be a sequence of loss functions. For R > O and 0 < c < 1, we say that the sequence (Le, z1) satisfies (R, -egoomtrii
decay with respect to μ if there exists a sequence of nonnegative numbers R₂ with R₁ = R satisfying the following two properties:
1. For all ((z l((z)= = 13) S R₂-
2. For any such that le(2x) L, we have Re+1 S cRa-
To motivate this admittedly abstract definition, consider the case of online classification with thresh- olds fo (z: = sign(x (x: - 0) from the introduction, with μ uniform on [0. 1] x {+1} (note that this does not precisely fit into the linear setting described above due to the offset); take 2; = (zz, v1) and (e(2)) [pr * yel. where the learner predicts ÿt at each time t. By realizability, (x(2) = 1 only when falls in the "region of disagreement,"i. the interval the rightmost x, labelled -1 and the leftmost v. labelled 1. To see why this is true, note that the "version space," " i.e. the set of thresholds that correctly classify all the data so far, is exactly this interval; for us to make a mistake, there must be two functions in the version space that disagree on Iy, which can only happen 24 itself is in the version space. If the learner denotes by w, the midpoint of the region of disagreement, then any mistake forces the version space, and thus the disagreement region, to shrink by a factor of 2. We see then that (le, 2)) satisfy (1, } -geometrii decay with respect to the uniform measure.
If the adversary were constrained to choose x, ~ h at each time step, is intuitive that we should not expect many mistakes to be made because, after any mistake, the probability that we make a mistake
Some authors refer the minimal volume ellipsoid containing a convex body as the John ellipsoid.

---

in some future interval decreases. In the following result, we show that this intuition holds in the more general smoothed setting:
Lemma 3 (Abstract Decay Lemma). Suppose that a sequence (Le, 2)) satisfies (R, geometric decay with respect to some μu on 2, and that for all i, there is some that is a-smooth with respect y and 2, Pr- Then for all T E N, with probability at least - 6,
log
2TR
El(=)
(3.1)
log
1-ve
Proof Sketch. We break our analysis into epochs whose lengths h. are tuned at the end of the proof. We then consider a sequence of stopping times Tm that count the number of epochs of length hm we experience in between the (m - 1)st and m time that & = 1. We then show that if h.m is not too large relative to the Probability that & = 1, then Tm Tm-1 is large with high probability and apply Ville's 's inequality [Ville, 1939] to conclude that if mr is the maximal epoch-index m such that Tm S T. then m& cannot be too large. We again apply Ville's s inequality to show that if hm is not too large then the probability of multiple mistakes per epoch is small. Because of the geometric decay property, the probability that & = decreases exponentially in the number of mistakes and thus we may let fm grow exponentially in and still not be too large to apply the above argument. We then conclude by noting that if hm are growing exponentially in m then my has to be logarithmic in T. The details can be found in Appendix C.I.
If we return to the above example of online classification with thresholds, we see that Lemma immediately yields the first regret bound for realizable, smoothed online learning with thresholds that is logarithmic both in the horizon and the smoothness parameter a. The intuition gleaned from one-dimensional thresholds that geometric decay suffices to ensure logarithmic regret will be key to the more general regret bounds we exhibit below.
3.2 A Volumetric Lemma
In the previous section, saw that in the setting of realizable, smoothed online classification with one-dimensional thresholds, the learner can force the indicator of a mistake at time to satisfy geometric decay; second workhorse result will allow to extend this fact higher dimensions. In the case of thresholds in the unit interval, the key intuition leading to geometric decay was the fact that the disagreement region was exactly the version space and thus shrinking the version space tautologically shrank the disagreement region as well. In higher dimensions the situation is significantly more complicated. We have the following result:
Lemma 4. Let ,I E Bt and suppose that y1. ,,...., .b, are realizable with respect to F Define the disugreement region
D fa B4| there exist f. E Ft such that f(x) # f'(x)}
(3.2)
where F, is the version space, defined in Section 2. Then, recalling that O3, is the boundary of Ft.
4d+1 wi
52. (a(()) pa $2.
vola-
(3.3)
Note that by controlling the size of D, by that of Fr, Lemma 4 is direct generalization of the one-dimensional case; however, in contradistinction to that setting, the proof is much more difficult and the bound includes an extra term corresponding to the surface area of F,, which is unavoidable in general. The full proof is in Appendix C.2, but we summarize the key points here. Though the conclusion of Lemma 4 is intuitive, it requires significant technical effort to prove.
Proof Sketch of Lemma 4. We first note that D; is contained in the set of points such that there is some w E 3, with (w, x) = 0: thus the conclusion Lemma reduces to a geometric statement about the volume of the set of points orthogonal to at least one point in given set can be. It may seem like this should "obviously" be the volume of a (d - di-dimensional ball multiplied by the
'Here as in the rest of the paper, we made no effort to optimize constants. We include them only to demonstrate that they are not unreasonably large.
5

---

Algorithm 1 Binary Classification with Linear Thresholds
1: Initialize W1 = =Bi, w1 = c1
2: for t = .... do
3: Recieve 2t, and predict ÿr = (wr, 2z)).
(x self classify(m))
4: Update W4+1 = W. n fw E Bfl (w, 1e9t) 2 0}
5: if ÿt * V/ then
(% self errorUpdate(xt))
6: W++1 f ---oonnllppoiCCeeeeeWW:::
7:
returns center of John Ellpsoid of given convex body
volume of Fr but this is false: J, is the equator of the sphere 5d-11, then (a(FF) = O, but the set of points orthogonal to at least one point in 9, is the entirety of Bİ. Ruling out this pathology requires several steps, including a covering argument to reduce to the case where F. is a ball, and application of (a generalized) Steiner's formula, and a deep geometric fact called Weyl's Tube Formula [Weyl, 1939, Gray, 2003] that governs how much volume we can add to F, by "fattening" to include all points distance at most E from F..
4 Warmup with Linear Classification
In this section, we begin to apply results from Section 3 to get tight regret bounds with computa- tionally efficient algorithms for learning halfspaces in the realizable, smoothed online setting:
Theorem 5. Let y be the uniform measure on B1, Suppose that we are in the smoothed, realizable online learning setting, where the adversary samples I4 from distribution that is a-smooth with respect to p. If we predict dr according to Algorithm I, then for all horizons T, with probability at least 1- - 8,
T 68
Regr S (13dlog(d) +34
+ 56.
(4.1)
Computational Efficiency. The subroutine JohnElllsoiddennter/W (We+1) can be run in time polyno- mial in T and d by solving Semi-definite Program (SDP) [Boyd and Vandenberghe, 2004, Primak and Kheyfets, 1995]. Note that we change our predictor fa only at the times / that we make mistake; thus, the number of calls to the SDP is also logarithmic in T.
Proof Sketch of Theorem 5. We apply Lemma with 2, (Zr,, 2r) and (=)=) = [ie + ye]. In order to do this we need to show that 4, satisfies (R, c) geometric decay. which amounts to finding a geometrically decreasing sequence of upper bounds on p())). By Lemma 4, it will suffice to provide such bounds on both (FF)) and vola-1 (05,). which is where the specific choice of wy becomes important. is now classical [Tarasov al., 1988. Khachiyan, 1990] that a polytope is cut by hyperplane through the center of its John ellipsoid then both halfs have John ellipsoids whose volumes are at most 8 g times the volume of the original ellipsoid; as we know that F, C d- & [John, 1948], where &, is the John ellipsoid of F., we see that μ(d &,) is an upper bound on ((F.) that decreases by S every time we make a mistake. The true utility of the center of the John ellipsoid is that it also allows us to show that 8F, decreases by constant factor. Indeed, we show that vola- (89.) S v using a simple projection argument; we then apply a result of Rivin [2007] to bound the size of dE, by ((E)). The details are in Appendix D.
Importance of the John's 's Ellipsoid. We show in Appendix D.3 that arbitrary predictions ya (2)). for fo F, in the version space, can guarantee 1/ 1/o-regret at best. Hence, selecting the correct w, is key. One natural choice of w; is the Chebyshev center of TT [Elzinga and Moore, 1975], equivalent to max-margin estimator; unfortunately it need not decrease the volume sufficiently if J, is too 'pointy.' Another choice, the centroid of F,, ensures decrease of the polytope's 's volume, but is hard to compute [Rademacher, 2007], and does not ensure decay of the surface area. The former problem can be accomodated with a sampling scheme [Bertsimas and Vempala, 2004], but the latter is critical. In contrast, the center of the John ellipsoid controls the decay of both F, and its boundary. To gain intuition as to why the decay in surface area of F, is necessary, consider the case where F, is simply an are in 5d-1. In this case, as D, is the set of points orthogonal to at least one point in in F,, follows that D, has positive measure even though Fe, being a lower dimensional set, does not; thus,

---

it is impossible in general to get guarantee on the size of Dj only in terms of the volume of Ft. without regard to the surface area. this way, we see that the choice of w, as the center of the John's 's Ellipsoid is critical to the success of our algorithm.
Remark 3 (Disagreement Coefficient). Our analysis is similar in spirit to the disagreementt-ceffciiee analysis of active learning [Hanneke, 2007], which also exhibits geometric decay of the disagreement region D.. The key difference is that the latter applies to any algorithm that selects classifier from the version space 'H, each time Again, as shown in Appendix D.3, no such analysis can recover a better than 1/o-regret bound. The culprit is that wenggreemmnt-oofffcciiin Dr shrink only probabilistically under samples 2₁ μ., and this probability may shrink by factor of a in the smoothed- online setting. In contrast, our choice of classifier as the center of the John's s ellipsoid ensures deterministic decay of the disagreement region whenever a mistake made.
arguments ensure that
Lower Bound. Before we move on to the more complicated settings, we note that this regret bound tight up to a logarithmic factor in d. proof of the following proposition, based on Ville's inequality, can be found in Appendix D.
Proposition 6. Suppose that we are in the situation of Thhorrmm 5. Then there is a realizable adversary such that any classifier experiences
E [Reg]] 2 Ω (d log (T/o)).
(4.2)
4.1 Smoothed classification via the Perceptron algorithm
Next, we present a guarantee for the classical Perceptron algorithm Rosenblatt [1958], which requires a much weaker notion of smoothness. We say that the adversary satisfies ddir directional smoothness if, for any fixed w E Sd-1, holds that for all t, (Iz, w) is dii- with respect the Lebesgue measure on the real line. As we explain in Example 2 in Appendix G, the directional smoothness aair can be nontrivial even when the smoothness parameter a = O. We now show that the perceptron satisfies the following mistake bound under directional smoothness.
Theorem 7. Fix any w" E S and b" E R. And suppose that the adversary satisfies dai directional smoothness. Then, with probability 1-8 8. the online Perceptron (Algorithm 9 in Ap- pendix G) satisfies
Regr = ET= 11 * m1 z (T/oaw)) (Nore(",, (b))) + Iog([ (1/5),
where Nen (w=,b",,)))) = 1 Σ.= Ily # sign(b" + (w)))))))} controls deviation from realizability.
For simplicity, Theorem 7 is stated relative a fixed w² Sd-1 and b* R:; uniform bounds be derived via a covering argument, at the expense of an additive d (ooo(T/ōdaaz) term in the error bound. Unlike other algorithms proposed in this paper, Theorem 7 accomodates possibly non-realizable adversaries. It is also slightly more computationally expedient, not requiring the computation of the center of John's is ellipsoid. In contrast, its bound polynomial in T' and 1/ rather than logarithmic in T and 1/a. There are situations where Algorithm performs exponentially better than the Perceptron approach: suppose 2, is uniform on an e-ball whose center is chosen by the adversary. Then we have a = = -d and so Theorem 5 implies that the John ellipsoid approach gives regret that scales as (d log(d/s) + log( whereas däir ss 1/E and Theorem 7 only ensures regret that is polynomial in e. For further comparison, consult Remark 4 in Appendix G.
5 Beyond the Linear Case
While the results of Section 4 are technically interesting and have broad applications, they are limited to the specific linear setting. In this section, we show how results can be extended, first to the more general affine setting, where the decision boundaries do not have to go through the origin, and then to more general regime where do not require linear decision boundaries.
5.1 Affine Classification
Our first generalization of TTheormm the setting where we allow our decision boundaries to be offset. Thus instead of assuming realizability with respect Id liu we will assume that the adversary
7

---

isrealizable with respect to
Fft aff
{x + ( + b)/w By and b R).
(5.1)
We have the following result: Corollary 8. Let μ be the uniform measure on B and suppose that we are in the smoothed online learning setting. where the adversary samples It from a distribution that is o-smooth with respect to p. Suppose that the adversary is realizable with respect to the function class Idd defined in (5.1). Then Algorithm
a computationally efficient algorithm for choosing St. E F such that for all T, with probability at least 1 - 6, it holds that
Appendix
Regr S 2268dlog( + 34 log (T/(aō)) + 56.
As Ty. lin C C. aff the lower bound of Proposition 6 holds and Corollary 8 is tight up to a factor logarithmic in dimension. The proof is given in Appendix E.1 and proceeds by reducing to the linear setting of Theorem 5 by imbedding the problem into an online learning problem with contexts T Rd+1 carefully randomized so as preserve their smoothness with respect 14d+11
5.2 Linear Classification Under Feature map
One limitation of the above discussion has been the assumption of linearity, which can be overly strong in many cases. In this section, we weaken this assumption in two ways. First, we show that if we transform the features with a well-behaved function, then we may still apply our above machinery. Second, we will show that our approach actually generalizes to polynomial decision boundaries through an elegant reduction. In both cases, the key technical challenge to show that transformed features remain smooth with respect to the uniform measure
ball. Note that it immediate that Φ(xz) is smooth with respect to o (dd in order to apply our results, however, we require smoothness with respect to the uniform measure. As it is not true that Pa is smooth with respect to P4 for general o, we require additional assumptions. We have the following result:
Theorem 9. Let Φ B -> B be a function such that each coordinate function, di R - RR satisfies (u) 2 a for some a > O. If we run Algorithm 4 in Appendix E.2 then, for all T, with probability at least 1 8, it holds that
Regr < 136d log (d/a) + 34 log (T/(o8)) + 56.
Algorithm 4, the algorithm that achieves the above regret bound, is actually quite simple as it just runs Algorithm 1 on the data sequence (Φ(xz), 31). A proof of more general result, which applies to larger class of maps @ is available in Appendix E.2. Even in the setting of Theorem 9, though, standard transformations like the sigmoid already apply.
We now turn to the more challenging case of polynomial features. We have the following result: Theorem 10. Let Ø: B - Br be an L-Lipschitz,unccee
whose coordinates are polynomials of degree at most & in the coordinates of x E BB. Suppose that we are in the smoothed online learning setting where the 2, are o-smooth with respect to pa and the ys are realizable with respect Ti Φ. Suppose further that the Jacobian of o satisfies for some a > O,
det (Ezopa Do(x)) 2 o².
Then Algorithm 5 in Appendix E.3 is computationally efficient algorithm such that for all T, with probability least 6.
ddTTL (G8
Reg, S mlg((m) + log
em?dloo
Algorithm 5 is a bit more complicated than simply applying Algorithm I to (δ(x,). y.) because if < m, then Φ(x²) can never be smooth with respect to jmm by dimension constraints. To escape this difficulty, we define "meta-point," I., which is the average of Φ(x;) for multiple different t. To understand why this might fix the problem, consider the identity imbedding of 5al C Bd. if we sample z uniformly on 5dt1 then the law of will not even be absolutely continuous with respect to pa but we sample two points x.
5d-1 then their average is absolutely continuous with respect to pa- We note that the conditions on are fairly mild due to the logarithmic dependence on both the Lipschitz constant and the lower bound on the determinant, which is typically no less than exponentially small in d and
8

---

Theorem 11. Suppose are in the realizable, smoothed, online learning setting where the adversary Proof Sketch of Theorem 10. Algorithm 5 proceeds initially in a similar way to Algorithm 1: we maintain a version space 3, C Iip that gets updated every round and, when we change wy, we set to be the center of the John ellipsoid of the version space. In contradistinction to the earlier algorithm, however, we not update Wy every time we make mistake. Instead, for some parameter p. we wait until we have misclassified a label p times, i.e., we guessed -1 1 but y/ was p times (or the reverse) and construct ž, to be the average of the ((x+) for each of these p mistakes. Using a novel anti-concentration bound for determinants of certain random matrices (Proposition 41) as well as some techniques from geometric measure theory (Proposition 40), we show that T, is smooth with respect pmn- We then apply the abstract decay lemma (Lemma 3) in much the same way did in the proof of Theorem 5. The details are in Appendix E.3.
Beyond Binary Classification
In the previous sections, we restricted our focus to binary classification; in this section expand our scope to a K-class setting and then further extend to a regression setting. Our results for the regression setting, combined with the reduction of Foster and Rakhlin [2020], are applied to the setting of contextual bandits in Appendix A.
6.1 Multi-Class Classification
We first generalize our results to multi-class classification. The targets are y/: E [K] some fixed K and classifications are assigned by maximum inner-product:"
F K-lin fo fw (z) arg max ( "o" ,x) w (w!,..., ....., w* E (B*)*
(6.1)
13i5K
Our algorithm is direct reduction to binary classification. For each i < j. we maintain instance A bin of Algorithm I which makes binary predictions (( of y/4-d) = sign( (wr, w! xx)). We then set our K-class prediction it as the first index i for which o) insight is that, even though the learner does not recieve feedback on all 0 ((-1) in this way, we can always assign mistake U, = Yt to an error Vi (b.J) + (!!-)) for some i <j. Formal pseudocode is given Algorithm and a proof of the following regret bound is given Appendix F.I.
1 for all j > i. The key
is realizable with respect to the 3rd K-tin in (6.1). Then, then for all T, with probability at least - 8. the regret of Algorithm is at most
Regr < 136K 13o(d)log(d) + 91KK log (08))
(6.2)
The efficiency of the above algorithm follows from the efficiency of the binary classifers A We (id)
conjecture that the dependence on X22 is an artifact of our reduction to (K) base classifiers.
6.2 Piecewise Regression
This section extends K-class classification to piecewise affine regression. We now suppose that the targets ye are realevalued, and realizable with respect the following class of functions:
{ x (x) = 9. = 9:(=()) = ((a,, for ag E IRd and f E F
Sy
K-lin
(6.3)
In contradistinction to the rest of the paper, where the adversary is allowed to play the yi adaptively subject only to the condition of realizability, in this section we suppose that the adversary is semi- oblivious in the sense that there is a ground- -tuth function chosen before the start of play and after learning begins, the adversary is only allowed to choose the contexts, 2,. This assumption is natural in the aforementioned contextual bandits application in Appendix A.
Theorem 12. Adopt the semi semi-oblivious, smoothed online learning setting, where the adversary begins by choosing 97. E 9y from (6.3), and, at each time t, draws H from a distribution that is o-soooth
For simplicity, we interpret the arg max lexicographically.

---

with respect to a and sets = gj. (mz). Then, Algorithm 7 is an algorithm that is efficient in the number of calls to an ERM oracle over 95 that satisfies for all T, with probability at least 1 - 6,
Regr < 136K 136K2dlog(d) + 91 log (TK? ((0))((())))))))))))())) + (2++
(6.4)
In Appendix F.2 we prove a more general version of the above result that allows the regression functions on each piece to be polynomial. The intuition is to reduce K K-iiece regression to K-class classification, but where each the "classes" materialize sequentially, once there are sufficiently many points observed to "determine" one of the pieces. The algorithm and proof are considerably more subtle, and are given in Appendices F.3 and F.4, respectively. We note that Algorithm 7 only requires the ERM oracle be called on sets of size independent of T, making the total runtime of the algorithm logarithmic in the horizon.
Acknowledgements
AB acknowledges support from the National Science Foundation Graduate Research Fellowship under Grant No. 1122374. We also would like thank Sofiia Dubova for her help in translating Tarasov et al. [1988] and Michel Goemans for pointing to the closely related, English-language work of Khachiyan [1990].
References
Keith Ball et al. An elementary introduction to modern convex geometry. Flavors of geometry, 31 (1-58):26, 1997.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume 3, page 1, 2009.
Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM (JACM), 51(4))540--55 2004.
Adam Block, Yuval Dagan, and Alexander Rakhlin. Majorizing measures, sequential complexities, and online learning. In Conference on Learning Theory, pages 587-590. PMLR, 2021.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. arXiv preprint urXiv:220..04690 2022.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4))9999))))9999))) 1989.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Anthony Carbery and James Wright. Distributional and _ norm inequalities for polynomials over convex bodies in R Mathematical research letters, 8(3):233-248, 2001.
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551-585, 2006.
Jack Elzinga and Thomas G Moore. A central cutting plane algorithm for the convex programming problem. Mathematical Programming, 8(1):134-145, 1975.
Herbert Federer. Geometric measure theory. Springer, 2014.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210 PMLR, 2020.
Yoav Freund and Robert E Schapire. Large margin classification using the perceptron algorithm. Machine learning, 37(3):277-266, 1999.
Alfred Gray. Tubes, volume 221. Springer Science & Business Media, 2003.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differen- tially private learning. arXiv preprint arXiv:2006. 10129, 2020.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver- saries. arxiv preprint
2021.
10

---

Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. arXiv preprint arXiv:2202.08549, 2022.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th International Conference on Machine Learning, ICML '07, page 353-360, New York, NY, USA, 2007. Association for Computing Machinery, ISBN 1755999937933 doi: 10.1145/1273496.12733
URL nttps:://oli htt///o..og///// org/10. wtt.g//...1///2/11/1 1111/1173399661..// 1273541.
Steve Hanneke. Rates of convergence in active learning. The Annals of Statistics, pages 333-361,
2011.
Steve Hanneke et al. Theory of disagreement-baasel active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-309, 2014.
Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the firtt- annual ACM symposiam Theory of Computing, pages 141, 2016.
Fritz John. Extremum problems with incqualities as subsidiary conditions, studies and essays presented to r. courant on his 60th birthday, january 8, 1948, 1948.
Leonid Genrikhovich Khachiyan. An inequality for the volume of inscribed ellipsoids. Discrete & Computational Geometry, 5(3):219-2) 2222 1990.
Victor Klee and George J Minty. How good is the simplex algorithm. Inequalities, 3(3):159-175. 1972.
Nick Littlestone.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285-318, 1988.
Martin Lotz. On the volume of tubular neighborhoods of real algebraic varieties. Proceedings of the American Mathematical Sociery, 143(5):1875- 2015.
Albert B Novikoff. On convergence proofs for perceptrons. Technical report, STANFORD RE- SEARCH INST MENLO PARK CA, 1963.
ME Primak and BL. Kheyfets. A modification of the inscribed ellipsoid method. Mathematical and computer modelling, 21 21611):6--7, 1995.
Luis A Rademacher. Approximating the centroid is hard. In Proceedings of the twenty-third annual symposium on Computational geometry, pages 302-305, 2007.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019. PMLR, 2013.
Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In Conference Learning Theory, pages 1232-1264. PMLR, 2014.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 141176--7722 2011.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexi- ties. J. Mach. Learn. Res., 16(1):155-186, 2015a
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probubility Theory and Related Fields, 161(1)1111-53,, 2015b.
Igor Rivin. Surface area and other measures of ellipsoids. Advances in Applied Mathematics, 39(4): 409-427, 2007.
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
Tim Roughgarden, editor. Beyond the Worst-Cas Analysis of Algorithms. Cambridge University
Press, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Max Simchowitz, Horia Mania, Stephen Tu, Michael Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
11

---

Daniel A Spielman and Shang- Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning. graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81-90, 2004.
Sergei Pavlovich Tarasov, Leonid Khachiyan, and Igor Erlikh. The method of inscribed ellipsoids. In Sooiitt Mathematies-Dooklude volume 37, pages 226-230, 1988.
Jean Ville. Etude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):224, 1939.
Martin J Wainwright. High--dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Liwei Wang. Smoothness, disagreement coefficient, and the label complexity agnostic active learning. Journal of Machine Learning Research, 12(7), 2011.
Henmann Weyl. On the volume of tubes. American Journal of Mathematics, 61(2):661-42, 1939.
Yomdin. The set of zeroes of an "almost polynomial" function. Proceedings of the American Mathematical Sociery, 90(())538--5) -42,, 1984.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our claimed contributions are efficiently achievable regret bounds for certain function classes in the smoothed online learning setting. Right before the related work section, we have a paragraph describing the structure and pointing to where each of the claims is discussed.
(b) Did you describe the limitations of your work? [Yes] Note that only claiming results for particular function classes in the smoothed online learning setting (see contributions).
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the statements of each proposition and lemma, along with the relevant preliminaries as needed.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are included in the appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zL7HmbJwiAs", "reviewer": "Reviewer_iruc", "summary": "This paper studies the smoothed online learning setting, where the adversary's action at each step must be drawn from a distribution with density bounded by $1/\\sigma$. This model bridges the offline/batch setting and the usual online setting. Previous upper bounds for this smoothed setting, however, have an exponential gap in the dependence on $T/\\sigma$ between computationally bounded and unbounded learners.\n\nThis work gives efficient algorithms that achieve $\\log(T/\\sigma)$-type regret, which nearly matches the optimal regret when computation is unbounded. All the following results hold under the realizable case: For linear classification, Theorem 5 gives a high-probability regret bound of $O(d\\log d + \\log(T/\\sigma))$, nearly matching an $\\Omega(d + \\log(T/\\sigma))$ lower bound in Proposition 6. This is further generalized to affine classification (Corollary 8), linear classification under a feature map (Theorems 9 and 10), and multi-class classification (Theorems 11 and 12).\n\nFor linear classification, the algorithm (Algorithm 1) is quite intuitive: maintain the (convex) set of hypotheses that are consistent with all previous examples, and predict with the center of its John ellipsoid. (The authors show that for other natural choices like the Chebyshev center or centroid, the analysis would not work.)\n\nThe analysis builds on the following two technical tools:\n- A decay analysis (Lemma 3), showing that it suffices to argue that whenever a mistake is made, the probability of making a mistake (at the next step) shrinks by a factor.\n- A geometric result (Lemma 4) that proves such a decay. While its statement is intuitive, the proof of Lemma 4 is quite technical and nontrivial.", "questions": "1. The paragraph on Lines 248-255 says that other choices of $w_t$ cannot guarantee the decay in both volume and surface area. Are there hard instances on which these choices provably incur a large regret? In other words, to what extent is the surface area decay necessary?\n\n2. What is the main difficulty in extending the results to the agnostic setting?", "limitations": "The main limitation is the results only hold for certain hypothesis classes and only under the realizable setting. This is made clear by the authors when summarizing the contribution.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies a sequential learning setting that receives much attention recently, and makes good progress in closing the computation-information gap in the optimal regret. While the proposed algorithm is simple, its analysis seems highly nontrivial even in the linear classification setting. I found the paper enjoyable to read, and thought that the authors did a good job in including both intuition and technical details of their proofs in the main paper, despite the technical difficulty in them.\n\nOne weakness is that the results are specific to the realizable setting, and it is unlikely that the current apporach/techniques could be easily extended to agnostic case. Nevertheless, given that previously no efficient algorithms are known to achieve the $\\log(T/\\sigma)$-type regret, I found the current results sufficiently significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UReHPRJzoJL", "reviewer": "Reviewer_XCuH", "summary": "This paper considers the problem of smooth online learning in the realizable setting. In the smooth online learning problem, the adversary is limited to choosing a distribution over contexts at each round which is “smooth” wrt to a dominating measure. The player knows the dominating measure. \n \nFor smooth online learning algorithms, there exists a statistical computational gap, and the main goal of this paper is to close the gap for the special case of the linear function classes in high dimensions. The main contribution of the paper is designing novel algorithms for this problem which attain the optimal statistical guarantees on the regret while computationally-efficient. \n\nThe main idea behind the proof is presented in Section 3. The authors show that if, with respect to the dominating measure, the error probability of the player decays, then with respect to any other measure that is smooth wrt to the dominating measure , we have a control over the regret. Then, as usual, to control the probability of error, the authors use the fact that a control over the size of the disagreement region can control the probability of error. They have a very nice result which provides a bound on the size of the disagreement region based on the volume of the version space in Lemma 4.\n\nIn the rest of the paper, they use their techniques to obtain optimal regret bounds for Linear Classification, Perceptron algorithm, Linear Classification Under a Feature map, and Multi-Class Classification.\n", "questions": "1- What is the definition of overly strong measures in Remark 2?\n\n2- Are your results robust to the change of the dominating measure? How can we design algorithms that are agnostic to the dominating measure?\n\n3- It seems that the algorithms designed in the paper are agnostic to the value of sigma. Is there any improvement if we assume the player knows the value of sigma? \n\n5- As mentioned in some cases, the sigma may depend on the dimension. Do we have a general approach to make sure sigma is O(1) in dimension?\n\n6- Your results strongly rely on the fact that the linear function class has a natural parameterization as vectors in dimension d. How can the results be extended to the classes without natural parametrization. \n\n", "limitations": "yes.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this paper is really strong. Also, the paper is very well-written, and the proof sketches are helpful in understanding the gist of the techniques. Moreover, the techniques used by the authors are also very interesting and novel.\nMy main concern about this paper is the “robustness” of the results and the techniques to the dominating measures. It seems in most of the results in the paper, it is assumed that the dominating measure is uniform on the unit ball of radius one in dimension d. \n\nI have a few questions which I will discuss in the next part. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SJQzk3uHptI", "reviewer": "Reviewer_pTSs", "summary": "This paper focuses on the statistical analysis of smoothed online learning for generalized linear functions. It provides the statistical \\log(T/sigma) regret for K-wise linear classification and extends the results to settings where the true classifier is linear in an over-parameterized polynomial featurization of the contexts, as well as to a realizable piecewise-regression setting assuming access to an appropriate ERM oracle. This work develops a characterization of the geometry of the disagreement region induced by generalized linear classifiers and a general anti-concentration bound for the determinant of certain matrix averages.", "questions": "This paper investigates the statistical analysis of smoothed online learning for generalized linear functions. The paper can be improved from multiple points of view.\n1)Presentation. The presentation could be improved. The logic of this paper is hard to follow. \n2)Quality. The introduction of related work can be further specified, and the comparison work can be further refined and improved. This paper adopts the smoothed online learning setting of Rakhlin et al. [2011], Haghtalab et al. [2021], Block et al. [2022]. It would be better if there is an improvement of the algorithms.\n3)Experiments. This paper mainly provides new theoretical analysis on the existing algorithms. It would be better if there are experiments to verify the results of theoretical analysis. \n4)Grammar, typos, and writing. It is suggested to further polish the writing.\nReferences are generally not used as the beginning of a sentence, such as: Rakhlin et al. [2011] proposed smoothed adversaries and proved regret bounds for linear thresholds in ...\nTenses in this paper are inconsistent. For example: \nIn line 73, Smoothed analysis was first proposed in Spielman and Teng [2004] as a way to explain the success of the simplex algorithm...\nIn line 101, Hanneke [2007] controls the label complexity of active learning...\nThe equation at the end of the sentence should be punctuated. For example, equation (2.2).", "limitations": "This paper describes the scope of application of the proposed methods in detail, and does not involve negative social impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has the following contributions: This paper studies the statistical property of certain classes of realizable smoothed online classification problems, for example affine thresholds, affine thresholds in nonlinear features, K-class affine classification, and piecewise affine regression, which have the statistically optimal regret bound. Then, this paper obtains a fast algorithm that achieves optimal regret dependence on the horizon, up to logarithmic factors, by applying the obtained results to noiseless contextual bandits. Finally, a complementary approach based on the perceptron algorithm is provided, which has a polynomial regret in a “directional smoothness” parameter. This paper adopts the smoothed online learning setting of Rakhlin et al. [2011], Haghtalab et al. [2021], Block et al. [2022]. The related work can be elaborated in more detail. It would be better to provide related experimental results to prove the rationality of the theoretical analysis.\nThe research field of this paper is significant. The organization and presentation of this paper can be further improved. There is no conclusion section.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HqA4ziMjLEC", "reviewer": "Reviewer_5Ree", "summary": "The authors study the problem of the gap that exists between the bounds for computationally feasible bounds for online learning poly(T/sigma) and exponential-complexity algorithms with a log(T/sigma). The consider a subset of this problem where the adversary or nature is allowed to select contexts with density bounded w.r.t. a known measure mu. They also provide theorems that characterize the determinant of matrix averages.", "questions": "None", "limitations": "None", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper gives a computationally efficient algorithm that closes the computational gap for a more restricted problem in online learning: where nature is restricted to select from a distribution bounded by 1/sigma from a know measure mu. This is a novel result that is interesting.\n\nThe bigger strengths of the paper are the interesting use of the John ellipsoid in their base algorithm and their use of Ville's inequality to analyze and bound the stopping time. Their theoretical results and techniques are of independent interest in addition to the their computationally efficient algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept