Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin

Daniel M. Kane; Ilias Diakonikolas; Pasin Manurangsi

REVIEW 3 major objections 4 minor 17 references

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper nearly settles the computational cost of proper, constant-factor agnostic learning of large-margin halfspaces, giving an algorithm with optimal sample complexity and a nearly matching ETH-based lower bound.

desk verdict Settles constant-factor proper agnostic margin learning up to sub-exponential factors, with a strong algorithmic idea and solid reductions; the main soft spot is the asserted finite-sample analysis of Algorithm 2. read the letter →

arxiv 1908.11335 v1 pith:6VRA4WNS submitted 2019-08-29 cs.LG cs.DSstat.ML

Ilias Diakonikolas , Daniel M. Kane , Pasin Manurangsi This is my paper · ORCID

classification cs.LGcs.DSstat.ML MSC 68Q3268Q2568Q17

keywords properlearningagnosticmarginhalfspacessamplecomplexityexponentialtimehypothesisPCPtheoremChowparametersspectralalgorithm

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper nearly settles the computational cost of proper, constant-factor agnostic learning of large-margin halfspaces. The learning goal is to return a halfspace whose misclassification error is at most $\alpha\cdot\mathrm{OPT}_{\gamma}+\epsilon$, where $\mathrm{OPT}_{\gamma}$ is the smallest error a halfspace can achieve while classifying points with margin $\gamma$ and $\alpha\ge 1$ is the approximation factor. The paper gives a $(1+\delta)$-approximate proper learner that draws $O(1/(\epsilon^2\gamma^2))$ samples, which is information-theoretically optimal, and runs in time $\mathrm{poly}(d/\epsilon)\cdot 2^{\widetilde{O}(1/\gamma^2)}$; setting $\delta=0.01$ realizes $\alpha=1.01$. It then proves, assuming the randomized Exponential Time Hypothesis, that any constant-factor proper learner must run in time $\mathrm{poly}(d/\epsilon)\cdot 2^{(1/\gamma)^{2-o(1)}}$, matching the upper-bound exponent up to subexponential factors. For larger approximation ratios, the paper maps the tradeoff with an $\alpha$-agnostic learner running in time $\mathrm{poly}(d)\cdot(1/\epsilon)^{\widetilde{O}(1/(\alpha\gamma)^2)}$ and hardness results for polynomial-time proper learning.

What carries the argument

The load-bearing object on the algorithmic side is the second-moment matrix $M_D=\mathbb{E}_{(x,y)\sim D}[xx^T]$ of the input distribution, and of the distribution $D^{(i)}$ obtained by conditioning on the current hypothesis $w^{(i)}$ classifying a point with margin $\gamma/2$. A structural claim (Claim 2.1) shows every optimal margin halfspace $w^*$ has $w^{*T}M_D w^*\ge\gamma^2/2$, so $w^*$ can be located through the top eigenspaces of such covariance matrices. The iterative algorithm guesses, at each stage, the projection of $w^*-w^{(i)}$ onto the span of the top $k$ eigenvectors of $M^{(i)}$ from a $\delta\gamma^3$-net; Lemma 2.6 guarantees this projection has squared norm at least $\delta k\gamma^2/8$, which gives a strictly decreasing bound on $\|w^*-w^{(i)}\|^2$ and forces termination in $O(1/(\delta\gamma^2))$ stages. For the large-$\alpha$ results, the central object is the Chow parameters vector $\mathrm{Chow}(f)=\mathbb{E}_{x\sim D_x}[f(x)x]$; Lemma 2.10 gives a margin-based stability statement, showing that functions differing from the target on probability $\nu+\mathrm{OPT}_{\gamma}$ have Chow vectors separated by at least $\nu\gamma$. The hardness direction is carried by reductions from $k$-Clique and from $\nu$-Gap-2-CSP in which constraints are encoded as sparse labeled samples and the constraint thresholds are shifted by a small multiple of the ideal solution's norm to create the $\gamma$ margin while preserving the YES/NO gap.

What would settle it

On the algorithmic side, run the finite-sample iterative procedure with $\mathrm{OPT}_{\gamma}\approx 1/m$ and $\epsilon<\mathrm{OPT}_{\gamma}$; if in repeated trials the returned halfspace's empirical $\gamma/2$-margin error exceeds $(1+\delta)\mathrm{OPT}_{\gamma}+\epsilon$, the 'essentially identical' empirical-distribution step is broken. On the hardness side, exhibiting a constant-factor proper agnostic learner running in $2^{(1/\gamma)^{1.9}}\cdot\mathrm{poly}(d/\epsilon)$ time would directly contradict the claimed randomized-ETH lower bound.

Watch

Extended reading notes

Core claim

The central claim is a near-tight characterization: for any constant approximation ratio $\alpha>1$, the complexity of properly learning $\gamma$-margin halfspaces in the agnostic PAC model is fixed by the pair $O(1/(\epsilon^2\gamma^2))$ samples and runtime $2^{\Theta(1/\gamma^2)}$, up to a $1/\gamma^{o(1)}$ factor in the exponent. The upper bound is Theorem 2.4, the formal version of the summarized Theorem 1.1: a $(1+\delta)$-agnostic proper learner, with $\alpha=1.01$ explicit, achieves this via a spectral iterative candidate-generation scheme. The lower bound, Theorem 3.1, states that under randomized ETH no constant-factor proper agnostic learner can run in time $\mathrm{poly}(d/\epsilon)\cdot 2^{(1/\gamma)^{2-o(1)}}$; the hardness reduction goes through $\nu$-Gap-2-CSP. The paper also proves Theorem 2.7 for larger $\alpha$, with runtime $\mathrm{poly}(d)\cdot(1/\epsilon)^{\widetilde{O}(1/(\alpha\gamma)^2)}$, and shows that polynomial-time proper learning cannot reach $(1/\gamma)^c$ approximation under NP$\neq$RP plus the Sliding Scale Conjecture (or $(1/\gamma)^{1/\mathrm{polyloglog}(1/\gamma)}$ under NP$\neq$RP alone). Together these results make $1/\gamma^2$ the correct margin exponent for constant-factor proper agnostic learning.

Load-bearing premise

The positive result's proof assumes that replacing the true distribution by the empirical distribution and conditioning on the events $\{y\langle w^{(i)},x\rangle\le\gamma/2\}$ leaves the iterative analysis intact, but the paper does not explicitly track the bias that conditioning introduces when those events have probability as small as $(1+\delta)\mathrm{OPT}_{\gamma}$; the hardness result additionally rests on the randomized Exponential Time Hypothesis in its quantitative form.

Editorial extensions

If this is right

Constant-factor proper agnostic learning of $\gamma$-margin halfspaces has sample complexity $\Theta(\log(1/\tau)/(\epsilon^2\gamma^2))$ and runtime $2^{\Theta(1/\gamma^2)}$ up to subexponential factors, under randomized ETH; no proper learner can simultaneously keep polynomial dependence on $1/\epsilon$ and a substantially smaller margin exponent.
The gap between the proper learner's $2^{\widetilde{O}(1/\gamma^2)}$ and known improper learners' $2^{\widetilde{O}(1/\gamma)}$ gives a computational separation between proper and improper learning for this problem under ETH.
For $\alpha=1$, no $f(1/\gamma)\cdot\mathrm{poly}(d,1/\epsilon)$-time proper learner exists under W[1] not contained in randomized FPT, so the small constant factor in the approximation is essential for the algorithm's runtime.
For larger $\alpha$, a proper learner with runtime $\mathrm{poly}(d)\cdot(1/\epsilon)^{\widetilde{O}(1/(\alpha\gamma)^2)}$ exists, and polynomial-time proper learning cannot reach $(1/\gamma)^c$ approximation under NP$\neq$RP plus the Sliding Scale Conjecture.
The same algorithms, with a small margin loss ($0.99\gamma$), give Euclidean-norm adversarially robust learners, so the upper bound transfers to that setting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves implicit that the same iterative spectral correction could be tried with higher-order moment tensors; if a projection can be found without exhaustive net search, the $2^{\widetilde{O}(1/\gamma^2)}$ runtime factor might be improvable for moderate $\gamma$.
The reduction's use of $\nu$-Gap-2-CSP means quantitative improvements in PCP constructions would automatically sharpen the lower-bound exponent; conversely, a proof of an exactly tight $2^{\Theta(1/\gamma^2)}$ lower bound would have to confront current PCP barriers.
Because the conditioning event can have probability $(1+\delta)\mathrm{OPT}_{\gamma}$, a practical implementation should replace the empirical conditional covariance with a smoothed or truncated estimator; testing that variant on low-$\mathrm{OPT}_{\gamma}$ distributions is a concrete robustness check the paper does not perform.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this paper nearly closes the complexity of constant-factor proper agnostic learning of large-margin halfspaces, and it should go to a serious referee. The main contributions are real: a proper learner with optimal O(1/(ε^2 γ^2)) samples and runtime 2^{Õ(1/γ^2)} for α = 1.01; a matching 2^{(1/γ)^{2-o(1)}} lower bound under randomized ETH; W[1]-hardness for α = 1; and polynomial-time inapproximability for (1/γ)^c under NP≠RP plus the Sliding Scale Conjecture.

What is new and good: the iterative spectral refinement is the right idea. Claim 2.5 and Lemma 2.6 say that a bad current hypothesis puts enough mass in the top eigenspace of the conditioned second-moment matrix to carve off δγ²/8 of the squared error per stage, and the integral-eigenvalue proof is valid. The reductions are also carefully engineered: the margin shifts in the k-Clique and k-CSP constructions are nontrivial, and the soundness counting (including the regularity-based fraction of constraints with variables outside Vsmall) checks out. The authors are honest about inherited conjectures and constants; they flag the non-explicit SSC constant and the ε0(α) quantifier issue themselves.

The real soft spot is Section 2.2's finite-sample analysis of Algorithm 2. The proof says the sample version is 'essentially identical' to the idealized one by replacing D with the empirical distribution and invoking Fact 2.3. That is an assertion, not a derivation. The conditioning events can have probability as low as (1+δ)OPT, which can be far below the per-sample scale, and the text never shows how conditioning bias, net errors, and uniform convergence combine into the final guarantee. I think the stress-test note is right that the algebraic lemmas probably apply to the empirical distribution verbatim, so the gap is likely repairable — but as written, the optimal-sample upper bound of Theorem 2.4 leans on missing bookkeeping. It deserves a careful independent check.

The lower-bound side rests on randomized ETH and the Moshkovitz-Raz PCP in the standard quantitative form; that's the field's usual currency. The k-Clique reduction for the α=1 case is clean and does not depend on PCP at all. Citation pattern is fine; the Chow-parameters black box from [DDFS14] is legitimate, and the [BS00]/[BS12] framing is right.

Who this is for: people working on margin learning, proper versus improper learners, and hardness of learning. It is technically dense but worth the read. My recommendation: send it to peer review. If the authors supply the missing finite-sample proof for Algorithm 2, I would accept. As is, it's a borderline accept with revisions, not a reject and certainly not a desk reject.

Referee Report

3 major / 4 minor

Summary. The paper studies proper agnostic learning of γ-margin halfspaces on the unit ball, with the goal of achieving misclassification error at most α·OPT_γ + ε. It gives a (1+δ)-approximate proper learner with O(1/(ε^2 γ^2)) samples and runtime poly(d/ε)·2^{Õ(1/(δ γ^2))} (Theorems 1.1 and 2.4), an α-approximate proper learner for larger α with runtime exponential in 1/(α γ)^2 (Theorem 2.7), and several computational lower bounds: any constant-factor proper learner requires 2^{(1/γ)^{2-o(1)}} time under randomized ETH (Theorem 3.1), 1-agnostic proper learning is not fixed-parameter tractable unless W[1] ⊆ randomized FPT (Theorem 3.2), and polynomial-time proper learners cannot achieve (1/γ)^c approximation under NP ≠ RP together with the Sliding Scale Conjecture (Theorem 3.3). The upper bounds use spectral and iterative search over second-moment matrices and Chow-parameter estimation; the lower bounds reduce from k-Clique and from gap versions of constraint satisfaction problems.

Significance. If the technical gaps identified below are repaired, this would be a significant result: it would settle, up to 1/γ^{o(1)} sub-exponential factors, the complexity of constant-factor proper agnostic margin learning, while retaining information-theoretically optimal sample complexity and exhibiting a proper-versus-improper separation. The paper's strengths include clean structural lemmas (Claim 2.1, Lemma 2.2, and the integral eigenvalue argument in Lemma 2.6), constructive algorithms with explicit candidate enumeration, and lower-bound reductions whose hardness assumptions (ETH, W[1] ≠ FPT, NP ≠ RP, SSC) are external rather than circular. The principal weaknesses are the asserted rather than proved finite-sample analysis of Algorithm 2 and an incorrect inequality direction in the proof of Lemma 3.4; both appear repairable within the manuscript's scope.

major comments (3)

[Section 2.2, analysis after Algorithm 2] The finite-sample correctness of Theorem 2.4 is asserted rather than proved. The text says the sample version is 'essentially identical' to the exact-distribution analysis by replacing D with the empirical distribution and applying Fact 2.3, but the load-bearing steps are not written out. A complete proof should (i) define w*_emp as a minimizer of the empirical γ-margin error for \hat D_m and re-run Claim 2.5 and Lemma 2.6 verbatim on \hat D_m; (ii) specify the behavior of the algorithm when the conditioning event {y⟨w(i),x⟩ ≤ γ/2} has zero empirical mass, since the conditional distribution D(i) is undefined in that case; (iii) prove the comparison OPT_{\hat D_m}^γ ≤ OPT_D^γ + O(ε), for instance by a Chernoff bound on the fixed true optimal vector; and (iv) assemble the ε/8-type constants with the stated sample size m = O(1/(ε^2 γ^2)). Because adaptive conditioning on rare events is exactly where empirical-versus-true arguments can fail, this gap is load-bearing for the claimed sample-optimal upper bound. I believe the argument can be completed, but it is not present in the manuscript as written.
[Section 3.1, proof of Lemma 3.4] The padding step in the proof of Lemma 3.4 uses the wrong inequality direction. Let γ0 be the margin produced by the reduction. The proof chooses \tilde d as the largest integer with γ(\tilde d) ≥ γ0 and then claims OPT_{D'}^{γ(\tilde d)} ≤ OPT_{D'}^{γ0}. Since err_D^γ(w) = Pr[y⟨w,x⟩ ≤ γ] is nondecreasing in γ, the opposite inequality holds, and the learner's guarantee at the larger margin γ(\tilde d) need not imply the needed completeness bound. The proof is repairable by choosing \tilde d as the smallest integer with γ(\tilde d) ≤ γ0; the regularity condition γ(d+1)/γ(d) ≥ Ω(1) then still gives γ(\tilde d) = Θ(γ0) and the same runtime bound. As written, however, the proof of the stated lemma is incorrect.
[Section 2.3, Proposition 2.8] Proposition 2.8 is stated for an 'explicit distribution' but Algorithm 3 enumerates all sequences x(1),...,x(m) from supp(D), which is only meaningful when supp(D) is finite. The statement should either require finite support or replace the enumeration by a net over the unit ball and account for the additional approximation error. In the proof of Proposition 2.8, the factor |f_w*(x) − y| ≤ 2 is also omitted when passing from the expectation E[⟨w,x⟩(f_w*(x)−y)] to the existence of a point with |⟨x(i+1),w⟩| ≥ αγ; the constants can absorb this, but the current text is not fully explicit.

minor comments (4)

[Abstract] The abstract says 'assuming the Exponential Time Hypothesis' while Theorem 3.1 is proved under the randomized ETH; the wording should be aligned with the formal statement.
[Section 2.2, Lemma 2.6] The text 'let 0 > λ_max = λ1 ≥ λ2 ≥ ...' appears to contain a typo: for a PSD matrix the largest eigenvalue satisfies λ_max ≥ 0, so the inequality should presumably read 0 ≤ λ_max.
[Section 2.1, Fact 2.3] Fact 2.3 is stated for a fixed margin γ but is later applied with margins γ/4 and γ/2; the statement should make explicit that the same sample bound applies uniformly over all margins, or the constants should be tracked explicitly.
[Section 3.3.2, Theorem 3.9] The soundness proof of Theorem 3.9 silently assumes 2ακ < 1/2 when arguing from the positivity constraint that w* > 0; the statement is still valid when the gap exceeds 1, but the proof should mention this case explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bounds are constructive against the external OPT_γ benchmark, and the lower bounds reduce from external ETH/PCP/parameterized-complexity assumptions.

full rationale

The paper's central claims are not circular. The upper bound (Theorem 2.4) is a constructive enumeration/ERM algorithm whose analysis uses algebraic structural lemmas (Claim 2.5 and Lemma 2.6) about the covariance of margin-misclassified points; these lemmas do not assume the desired error bound. The finite-sample step replaces D by the empirical distribution and invokes Fact 2.3, a standard uniform-convergence bound from [BM02, McA03]. Although the paper's compression of the finite-sample comparison in Section 2.2 is terse and may leave a bookkeeping gap, that is a completeness/correctness concern, not a reduction of the conclusion to its own input. The lower bounds (Theorems 3.1, 3.2, 3.3) are reductions from k-Clique, Gap-3SAT/CSP, and the Moshkovitz-Raz PCP under ETH, W[1] ≠ FPT, NP ≠ RP, and the Sliding Scale Conjecture; these are external hardness assumptions and do not encode the learning result. The only self-citation of note is Lemma 2.11, which imports the Chow-parameters algorithm from [TTV08, DDFS14]; one current author is a coauthor of [DDFS14], but that prior work is an independent published algorithmic result with its own stated assumptions, and the robust identifiability statement (Lemma 2.10) is proved in the present paper. No 'prediction' is a renamed fitted parameter, and no uniqueness theorem is imported solely from the authors' earlier work to forbid alternatives. The derivation chain is therefore self-contained against external benchmarks.

Assumptions & free parameters 3 free parameters · 8 assumptions · 0 invented entities

No number in the paper is fitted to data; the free_parameters entries are construction and theorem-statement constants whose correctness is proven in the text. The load-bearing inputs are the standard complexity conjectures of the field (randomized ETH, W[1] ≠ FPT, NP ≠ RP, Sliding Scale Conjecture) and one external algorithmic theorem ([TTV08, DDFS14] Chow-parameter recovery, used as a black box in Lemma 2.11). The margin framework rests on the standard uniform-convergence bound (Fact 2.3) and the benign assumption OPT_γ ≤ 1/2. Nothing is postulated ad hoc to force the central claim: the upper bounds are constructive and the lower bounds reduce from independently hard problems.

free parameters (3)

slack and shift constants of the hardness reductions (β = 1 - 0.01/n², δ = 0.1/(Δ|Σ|^{2k}), s = 10Δ|Σ|^k, 0.9 and 1.1… = β = 1 - 0.01/n²; δ = 0.1/(Δ|Σ|^{2k}); s = 10Δ|Σ|^k
Hand-chosen constants in the constraint gadgets (Sections 3.2 and 3.3) that create the margin and the error gap; correctness of each choice is proven in the completeness and soundness arguments, and none is fitted to any data. They are construction parameters, not empirical fits.
gap-to-approximation conversion α = (1/ν)^{1/k}/(40k) = (1/ν)^{1/k}/(40k)
Chosen so that 0.9·(20αk)^{-k} > ν in the soundness decoding argument (Section 3.3.2). The value is determined by the proof requirement, not by data.
error threshold ε0(α) in Lemma 3.4 = ε0 = ε0(α), existential constant
The stronger-quantifier lower bound (Section 3.1) only rules out learners that work for some ε < ε0(α); the paper discloses this and leaves generalizing to all ε < 1/2 open. This is a genuine, disclosed limitation of the lower-bound statement.

assumptions (8)

domain assumption Randomized Exponential Time Hypothesis: 3SAT requires 2^{Ω(n)} time
Unproven complexity conjecture; load-bearing for the quantitative lower bounds in Theorems 3.1 and 3.2 via Theorem 3.7 (Sections 3.3.1 and 3.3.3).
domain assumption Moshkovitz-Raz PCP (Theorem 3.7): ν-Gap-2-CSP with |Σ| = O_ν(1) cannot be solved in 2^{n^{1-o(1)}} time, assuming ETH
Converts ETH hardness into the margin-learning lower bound exponents in Theorem 3.1 and Lemma 3.4 (Section 3.3.3).
domain assumption W[1] is not contained in randomized FPT
Used in Theorem 3.2; the reduction from k-Clique (Lemma 3.5) uses the W[1]-completeness of k-Clique [DF95].
domain assumption NP ≠ RP and the Sliding Scale Conjecture (Conjecture 1: n^{-Ω(1)}-Gap-k-CSP is NP-hard for constant k)
Used in Theorem 3.3 together with the Dinur-Harsha-Kindler PCP (Theorem 3.8); the resulting hardness constant c is non-explicit, as the authors disclose.
domain assumption Chow-parameter recovery in polynomial time from approximate Chow parameters (Lemma 2.11, from [TTV08, DDFS14])
External published theorem used as a black box; one author overlaps with [DDFS14], but that is an independent peer-reviewed JACM 2014 result whose theorems do not imply the present paper's claims, so the import is not circular.
standard math Fact 2.3 uniform margin generalization bound [BM02, McA03]: with m = Ω(log(1/τ)/(ε²γ²)) samples, err_0-1(h_w) ≤ err_γ(w) + ε uniformly over all unit w
The sample-to-population bridge for all four algorithms (Section 2.1).
standard math Johnson-Lindenstrauss lemma with efficient sampling (Lemma 2.12)
Dimension reduction in Theorem 2.7 to m = O(log(α/ε)/γ²) with margin loss γ to γ/2 and OPT loss O(OPT_γ).
domain assumption OPT_γ ≤ 1/2
Invoked in Claim 2.1 to obtain ‖M_D‖ ≥ w*^T M_D w* ≥ γ²/2. Benign: if OPT_γ > 1/2, the target becomes a constant-error bound and the problem is vacuous.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin." pith.science (2026). https://pith.science/paper/6VRA4WNS

@misc{pith2026190811335,
  author       = {Pith},
  title        = {Pith review of: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6VRA4WNS}},
  note         = {Machine review of arXiv:1908.11335}
}

abstract

We study the problem of {\em properly} learning large margin halfspaces in the agnostic PAC model. In more detail, we study the complexity of properly learning $d$-dimensional halfspaces on the unit ball within misclassification error $\alpha \cdot \mathrm{OPT}_{\gamma} + \epsilon$, where $\mathrm{OPT}_{\gamma}$ is the optimal $\gamma$-margin error rate and $\alpha \geq 1$ is the approximation ratio. We give learning algorithms and computational hardness results for this problem, for all values of the approximation ratio $\alpha \geq 1$, that are nearly-matching for a range of parameters. Specifically, for the natural setting that $\alpha$ is any constant bigger than one, we provide an essentially tight complexity characterization. On the positive side, we give an $\alpha = 1.01$-approximate proper learner that uses $O(1/(\epsilon^2\gamma^2))$ samples (which is optimal) and runs in time $\mathrm{poly}(d/\epsilon) \cdot 2^{\tilde{O}(1/\gamma^2)}$. On the negative side, we show that {\em any} constant factor approximate proper learner has runtime $\mathrm{poly}(d/\epsilon) \cdot 2^{(1/\gamma)^{2-o(1)}}$, assuming the Exponential Time Hypothesis.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

[9]

Diakonikolas, G

[DKK+19] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt , and A. Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th Interna- tional Conference on Machine Learning, ICML 2019 , pages 1596–1606,

work page 2019
[11]

Diakonikolas, W

[DKS19] I. Diakonikolas, W. Kong, and A. Stewart. Eﬃcient al gorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , pages 2745–2754,

work page 2019
[1984]

[KKM18] A. R. Klivans, P. K. Kothari, and R. Meka. Eﬃcient alg orithms for outlier-robust regression. In Conference On Learning Theory, COLT 2018 , pages 1420–1430,

work page 2018
[1994]

Bhattacharyya, S

[BGS18] A. Bhattacharyya, S. Ghoshal, and R. Saket. Hardnes s of learning noisy halfspaces using polynomial thresholds. In Conference On Learning Theory, COLT 2018 , pages 876–917,

work page 2018
[2000]

Birnbaum and S

[BS12] A. Birnbaum and S. Shalev-Shwartz. Learning halfspa ces with the zero-one loss: Time- accuracy tradeoﬀs. In Advances in Neural Information Processing Systems 25: NIPS 2012, pages 935–943,

work page 2012
[2001]

Daniely, N

25 [DLS14] A. Daniely, N. Linial, and S. Shalev-Shwartz. The co mplexity of learning halfspaces using generalized linear methods. In Proceedings of The 27th Conference on Learning Theory, COLT 2014 , pages 244–286,

work page 2014
[2002]

Ben-David and H

[BS00] S. Ben-David and H. Ulrich Simon. Eﬃcient learning of linear perceptrons. In Advances in Neural Information Processing Systems (NIPS) 2000 , pages 189–195,

work page 2000
[2003]

Montasser, S

[MHS19] O. Montasser, S. Hanneke, and N. Srebro. VC classes a re adversarially robustly learn- able, but only improperly. In Conference on Learning Theory, COLT 2019 , pages 2512–2530,

work page 2019

Show all 17 references

[2007]

Diakonikolas and D

[DK19] I. Diakonikolas and D. M. Kane. Degree-d chow paramet ers robustly determine degree- d ptfs (and algorithmic applications). In Proceedings of the 51st ACM Symposium on Theory of Computing, STOC 2019 , pages 804–815,

2019
[2009]

Shalev-Shwartz, O

[SSS10] S. Shalev-Shwartz, O. Shamir, and K. Sridharan. Lea rning kernel-based halfspaces with the zero-one loss. In The 23rd Conference on Learning Theory, COLT 2010 , pages 441–450,

2010
[2010]

Nakkiran

[Nak19] P. Nakkiran. Adversarial robustness may be at odds w ith simplicity. CoRR, abs/1901.00532,

1901 arXiv
[2013]

Dinur, P

[DHK15] I. Dinur, P. Harsha, and G. Kindler. Polynomially lo w error PCPs with polyloglog n queries via modular composition. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , pages 267–276,

2015
[2014]

Degwekar, P

[DNV19] A. Degwekar, P. Nakkiran, and V. Vaikuntanathan. Co mputational limitations in robust classiﬁcation and win-win results. In Conference on Learning Theory, COLT 2019, pages 994–1028,

2019
[2016]

Diakonikolas, G

[DKK+17] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, a nd A. Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , pages 999–1008,

2017
[2017]

Diakonikolas, G

[DKK+18] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, a nd A. Stewart. Ro- bustly learning a gaussian: Getting optimal error, eﬃcient ly. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algori thms, SODA 2018 , pages 2683–2702,

2018
[2018]

Bubeck, Y

[BLPR19] S. Bubeck, Y. T. Lee, E. Price, and I. P. Razenshteyn . Adversarial examples from computational constraints. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019 , pages 831–840,

2019
[2019]

Diakonikolas, D

[DKS18] I. Diakonikolas, D. M. Kane, and A. Stewart. Learnin g geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theor y of Computing, STOC 2018 , pages 1061–1073,

2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [9]

Diakonikolas, G

[DKK+19] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt , and A. Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th Interna- tional Conference on Machine Learning, ICML 2019 , pages 1596–1606,

work page 2019

[2] [11]

Diakonikolas, W

[DKS19] I. Diakonikolas, W. Kong, and A. Stewart. Eﬃcient al gorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , pages 2745–2754,

work page 2019

[3] [1984]

[KKM18] A. R. Klivans, P. K. Kothari, and R. Meka. Eﬃcient alg orithms for outlier-robust regression. In Conference On Learning Theory, COLT 2018 , pages 1420–1430,

work page 2018

[4] [1994]

Bhattacharyya, S

[BGS18] A. Bhattacharyya, S. Ghoshal, and R. Saket. Hardnes s of learning noisy halfspaces using polynomial thresholds. In Conference On Learning Theory, COLT 2018 , pages 876–917,

work page 2018

[5] [2000]

Birnbaum and S

[BS12] A. Birnbaum and S. Shalev-Shwartz. Learning halfspa ces with the zero-one loss: Time- accuracy tradeoﬀs. In Advances in Neural Information Processing Systems 25: NIPS 2012, pages 935–943,

work page 2012

[6] [2001]

Daniely, N

25 [DLS14] A. Daniely, N. Linial, and S. Shalev-Shwartz. The co mplexity of learning halfspaces using generalized linear methods. In Proceedings of The 27th Conference on Learning Theory, COLT 2014 , pages 244–286,

work page 2014

[7] [2002]

Ben-David and H

[BS00] S. Ben-David and H. Ulrich Simon. Eﬃcient learning of linear perceptrons. In Advances in Neural Information Processing Systems (NIPS) 2000 , pages 189–195,

work page 2000

[8] [2003]

Montasser, S

[MHS19] O. Montasser, S. Hanneke, and N. Srebro. VC classes a re adversarially robustly learn- able, but only improperly. In Conference on Learning Theory, COLT 2019 , pages 2512–2530,

work page 2019