Robust Learning of a Group DRO Neuron

Guyang Cao; Jelena Diakonikolas; Shuyao Li; Sushrut Karmalkar

REVIEW 4 major objections 5 minor 13 references

Robust Learning of a Group DRO Neuron

T0 review · 4 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read Under a uniform margin condition, a primal-dual algorithm with extrapolated group weights learns a single neuron with constant-factor worst-case loss using \tilde{O}(Kd/ε²) samples, even under arbitrary label noise and group shifts.

desk verdict Genuinely new algorithmic result for nonconvex Group DRO, but the proof has a real gap near w* and leans heavily on self-cited prior work; worth a serious referee. read the letter →

arxiv 2601.18115 v2 pith:CQTZHDIS submitted 2026-01-26 cs.LG cs.DSmath.OC

Guyang Cao , Shuyao Li , Sushrut Karmalkar , Jelena Diakonikolas This is my paper · ORCID

classification cs.LGcs.DSmath.OC

keywords singleneuronGroupDROarbitrarylabelnoisedistributionalshiftprimal-dualalgorithmdualextrapolationnonconvexoptimizationconstant-factorapproximation

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 tackles learning a single neuron (σ(w·x)) under squared loss when labels can be arbitrarily corrupted and data come from K groups with distribution shifts. It aims to output a weight vector whose worst-case loss over convex mixtures of the groups is within a constant factor of the optimal robust neuron's loss. The central claim is that a primal-dual algorithm with extrapolation on the low-dimensional group weights achieves this with near-optimal sample complexity, matching the convex Group DRO rate up to log factors. The proof handles the nonconvexity through a linearization lemma and a uniform sharpness condition. A motivating LLM pretraining experiment suggests the dual-extrapolation update provides practical stability gains.

What carries the argument

The analysis centers on a primal-dual gap function Gap(w,λ) = L(w,λ*) − L(w*,λ) with a hybrid reference: population-optimal w* and empirical worst-case λ*. The lower bound on the gap comes from empirical sharpness (Lemma 2.2), while the upper bound is derived from the algorithm's updates; the key technical step is a 'linearization' lemma (Lemma 3.5) that replaces the nonconvex squared loss with an inner product using the surrogate gradient 2β(σ(w·x)−y)x plus controlled error terms. This linearization permits extrapolation on the dual variable λ (which may become negative) without breaking convexity, and removes the need for a nonzero regularization parameter ν.

What would settle it

Construct a covariate distribution that satisfies subexponential tails (Assumption 1.2) but has a narrow low-density region such that for some direction w, E[xx^T I{w·x ≥ γ||w||}] is not positive definite with the required ζ; run Algorithm 1 on K=1 group with realizable labels and check whether the distance bound ||w_n−w*|| ≤ C_3(√OPTm+√ε) still holds. If it fails, Assumption 1.3 is necessary as stated.

Watch

Extended reading notes

Core claim

The paper claims its Algorithm 1 is the first computationally efficient method with provable constant-factor guarantees for a nonconvex neuron in a Group DRO setting with arbitrary label noise. Concretely, under Assumptions 1.2 and 1.3, with N = \tilde{O}(K W^4 d/ε^2 log(1/δ)) samples, the output w_n satisfies ||w_n − w*||_2 ≤ C_3(√OPTm + √ε) and the expected loss under the worst-case mixture p* is at most (2 + 20Bβ²C_3²)OPTm + 20β²C_3² Bε, where C_3 is a constant independent of d, K, W, ε, ν. This matches the optimal sample complexity for convex unregularized Group DRO up to log factors, and the algorithm reaches this in O(K/ε) iterations, each running in near-linear time.

Load-bearing premise

The load-bearing premise is the uniform margin condition (Assumption 1.3): for every group and every weight vector w, the covariance inside the region {x : w·x ≥ γ||w||} must be uniformly well-conditioned; if some iterate w_t violates this, the empirical sharpness lemma fails and the convergence proof collapses.

Editorial extensions

If this is right

If the theorem holds, Group DRO for nonconvex models is no longer limited to stationary-point guarantees; a constant-factor approximation is achievable with polynomial time and near-optimal samples.
The dual-extrapolation design is memory-efficient (the extrapolated variable has dimension K, not d), so it can be combined with off-the-shelf optimizers like Adam in large-scale training.
The ν→0 regime connects the regularized robust formulation to classical Group DRO without penalty, and the result applies to both KL and χ² divergences.
The sample complexity \tilde{O}(Kd/ε²) means robustness to worst-case group reweighting costs essentially no extra samples over the convex case.

Reading between the lines

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

The uniform margin assumption is the bottleneck: if it could be relaxed to holding only near the optimum (as in previous single-neuron work), the algorithm would likely cover a wider class of marginals; the current proof needs it at every iterate.
The constant factor C_3 depends on the sharpness constant c1; for activations like ReLU these are benign, but the factor may become large for ill-conditioned problems, so the practical competitiveness of the constant is an open question.
The LLM pretraining result is a proof-of-concept at modest token counts; a natural testable extension is to compare the dual-extrapolation update against current state-of-the-art domain reweighting baselines at full pretraining scale.
Dual extrapolation might transfer to other nonconvex-concave minimax problems where the dual is low-dimensional; the linearization technique is a new tool for such settings.

Share X Bluesky LinkedIn Reddit HN

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

Two things to know about arXiv:2601.18115. First, it gives the first provably polynomial-time constant-factor learner for a single neuron under group-level distribution shifts with arbitrary label noise, and the dual-side extrapolation idea is a real step beyond [LKDD24]. Second, the proof as written has a load-bearing gap: the two-sided bound (5) is derived from empirical sharpness Lemma 2.2, which only holds for ∥w−w*∥ ≥ √ε, yet (5) is then applied at all distances, including near w*, in Lemma 3.2 and Lemma E.2. Without the c1∥w−w*∥² lower bound in that regime, the gap lower bound and the contraction inequality do not follow. The stress-test note is correct on this point.

What is actually new: the Group DRO formulation with f-divergence penalty, ν=0 allowed, KL and χ² divergences, removal of higher-moment assumptions, and a linearization lemma that makes dual extrapolation tractable for a nonconvex loss. That is a substantial contribution to the robust-learning literature, and the high-level approach is credible.

Where the soft spots are: (1) the small-distance gap described above; (2) Assumption 1.3 (Uniform Margin for every w) is much stronger than the w*-only margin in prior work, and the paper justifies it by examples rather than proof over the claimed family—genuinely load-bearing; (3) the intro's claim of sample complexity matching the known optimal rate hides the W^4 factor and parameter dependencies that appear in Theorem 3.1; (4) the proof of Lemma 3.3 explicitly defers to a claim in [LKDD24] without derivation, and Appendix D says it 'adapts techniques' from the same source. None of these by themselves make the central claim implausible, but they mean the theorem as stated is not fully proven in this version.

The experiments are illustrative and the authors say as much; they do not add real evidence either way.

Who is this for: theorists working on robust learning, nonconvex DRO, and provable guarantees for simple neural networks. A serious referee should engage—the result is important and the gaps look patchable, but the proof needs real work before the claims are taken at face value.

Referee Report

4 major / 5 minor

Summary. The paper studies learning a single neuron under squared loss with arbitrary label noise and group-level distributional shifts, formulated as a Group DRO problem with an f-divergence penalty on the group weights. The main contribution is a primal-dual algorithm (Algorithm 1) with extrapolation on the dual variable, together with a theoretical guarantee (Theorem 3.1): under a subexponential-tail assumption and a uniform margin assumption, the algorithm returns a weight vector that is constant-factor competitive with the optimal worst-group loss, with polynomial sample and iteration complexity. The paper also reports a small-scale LLM pretraining experiment comparing the proposed dual update with DoReMi/Sheared-LLaMA. If the proof is correct, this is the first polynomial-time constant-factor learner for a nonconvex neuron in a Group DRO setting with arbitrary label noise.

Significance. The result is significant: it extends the line of work on robustly learning a single neuron to a Group DRO setting, removes several restrictions of the prior work [LKDD24] (higher-moment assumptions, mandatory large regularization, restriction to chi-squared divergence), and proposes a dual-extrapolation scheme that is more memory-efficient in large-scale applications. The proof strategy, based on a linearization lemma and a sharpness-based gap argument, is a reasonable route to the claimed guarantee. However, the proof as written has load-bearing gaps: the empirical sharpness bound is stated beyond the regime in which it is proved, the uniform margin assumption is substantially stronger than in prior work and is not verified for the claimed distribution family, and one induction step relies on an external claim from [LKDD24] without a self-contained argument. These issues affect the central convergence theorem and must be repaired before the main claim can be accepted.

major comments (4)

[Section 2, Eq. (5)] Lemma 2.2 establishes the empirical sharpness inequality (3) only for all w with ||w - w*||_2 >= sqrt(epsilon). The two-sided bound (5), however, is stated for any w in B(W) and its lower half is derived from (3). This unrestricted form is then used in Lemma 3.2 (Eq. (16)), in Lemma E.2, and in the telescoping proof of Proposition 3.4. For iterates within sqrt(epsilon) of w*, the lower bound c1 * ||w - w*||^2 is not justified, so the gap lower bound and the contraction inequality (7) are not established in that regime. This is an internal proof gap, independent of Assumption 1.3. The authors should either extend Lemma 2.2 to the small-distance regime, or provide a separate argument showing that the quantities in question can be controlled there.
[Assumption 1.3] The uniform margin condition requires the covariance lower bound E[xx^T 1{w·x >= gamma ||w||_2}] >= zeta I_d for every w and every group. This is much stronger than the margin conditions in [WZDD23, LKDD24], which are only imposed at the target w*. The paper states that the condition holds for standard distributions because their definitions do not involve w*, but this is a plausibility argument rather than a proof. The sharpness bounds in Fact 2.1 and Lemma 2.2 are applied to every iterate w_t, so Assumption 1.3 is load-bearing. The authors should either prove the uniform margin property for the full claimed family of distributions, or explicitly restrict the theorem to a subclass for which it is verified.
[Section 3.5 and Lemma 3.3] The proof of Lemma 3.3 invokes 'claim E.2 in [LKDD24]' for a WLOG normalization that is used to conclude ||w_{n+1}||_2 <= 3||w*||_2. Since this bootstrap step is essential to keep the iterates inside the region where all previous sharpness lemmas apply, the argument is not self-contained as written. In addition, in the proof of Theorem 3.1 the text uses the high-probability bound \hat{OPT}_m <= 3(OPT_m + epsilon), but Lemma C.3 states only \hat{OPT}_m <= OPT_m + epsilon. These discrepancies must be reconciled and the cited claim either stated explicitly or proved within the paper.
[Section 1.2 and Theorem 3.1] The introduction claims that the algorithm attains sample complexity O-tilde(Kd/epsilon^2), 'matching the known optimal rate' for convex unregularized Group DRO. Theorem 3.1, however, states N = O-tilde_{beta,B,nu}(K W^4 d/epsilon^2 log(1/delta)), with an explicit W^4 factor and additional hidden dependencies on beta, B, and nu. Unless W, beta, B, nu are treated as universal constants, this does not match the cited optimal rate. The claim should be weakened or the comparison made precise.

minor comments (5)

[Fact 2.3] The truncation operation is written as y' = sign(y) max{|y|, M}; this increases the magnitude of y and does not truncate. It should presumably be sign(y) min{|y|, M}. Please correct the formula and confirm that the subsequent arguments use the truncated labels.
[Section 1.2 / Theorem 3.1] The informal statement says the learner is provided with O-tilde(...) samples 'from each' group, while Theorem 3.1 gives a total sample size N. Please state per-group versus total sample size consistently.
[Appendix A] In the related-work paragraph, the citation list '[MMR09, PY09, BDBC+10 PGLC15, TSK+18]' is missing a comma between '[BDBC+10]' and '[PGLC15]'.
[Section 4.1 / Figure 1] The claim that 'DoReMi requires at least 1.5x more training time to achieve the same accuracy' is not supported by the displayed figure or the experimental setup, which reports accuracy versus tokens, not wall-clock time. Please clarify or remove this claim.
[Theorem 3.1, constants] The approximation constant C3 = 31*beta*sqrt(B)/c1 depends on beta, B, and c1. The introduction and Problem 1.5 describe the constant as 'universal' and 'independent of d, K, W, epsilon, nu', which is misleading if these distribution-dependent parameters are not bounded. The statement should be qualified accordingly.

Circularity Check

1 steps flagged · score 4.0 of 10

Proof closure imports a load-bearing WLOG from self-cited [LKDD24]; the central dual-extrapolation analysis has independent content.

self citation load bearing [Appendix E.3, Proof of Lemma 3.3, final paragraph]
"following the similar logic of claim E.2 in [LKDD24], we can assume without loss of generality that [ ... ] \OPTm + epsilon <= ||w*||^2, otherwise we can compare the empirical risk of the output from our algorithm and of w_hat=0 and output the solution with the lower risk to obtain an O(OPT)+epsilon solution."

Lemma 3.3 is the induction step that keeps every iterate in B(3||w*||), which is the region needed to apply the empirical sharpness bound Lemma 2.2 and the two-sided bound (5). The proof does not close this step from the paper's stated Assumptions 1.2/1.3; it defers to 'claim E.2 in [LKDD24]', a prior paper with overlapping authors. The main contraction (Theorem 3.1, Eq. (7)) depends on the gap lower bound Lemma 3.2, which in turn depends on Lemma 3.3. Thus a central part of the convergence proof is justified only by a self-cited technical claim rather than by a self-contained derivation.

full rationale

The paper contains substantial independent technical content: the dual-side extrapolation analysis, the linearization Lemma 3.5, and the heavy-tailed uniform-convergence machinery are new relative to the cited prior work. However, one load-bearing step is not self-contained: the proof of Lemma 3.3 explicitly imports a WLOG bound on the empirical optimum from 'claim E.2 in [LKDD24]' with overlapping authors. Without that imported claim, the induction preserving ||w_t|| <= 3||w*|| is not established, and the subsequent sharpness-based gap lower bound is not available. I am not scoring the separate correctness issue that Equation (5) is used for all w although Lemma 2.2 only proves the sharpness inequality for ||w-w*|| >= sqrt(epsilon); that is a proof gap, not an input-output tautology. Overall, the central claim still has independent algorithmic content, but the reliance on self-cited prior work for a structural induction step warrants a score of 4 rather than 0-2.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on two domain assumptions (subexponential tails, uniform margin over all w), a structured-activation class, strong convexity of the f-divergence, and standard sharpness/moment and truncation facts lifted from prior work. No free parameters are fitted to data. No new entities (particles, forces, dimensions) are introduced. The most fragile item is Assumption 1.3 because it must hold for every w, not just the target.

assumptions (5)

domain assumption Assumption 1.2 (Sub-Exponential Tails): Pr_{x~p_i}(|u·x| ≥ r) ≤ exp(−r/B) for all unit u, r ≥ 1.
Used to establish uniform concentration of empirical expectations (Lemma C.2) and moment bounds; if violated, the high-probability sharpness and moment estimates fail.
domain assumption Assumption 1.3 (Uniform Margin): E_{x~p_i}[xx^T I{w·x ≥ γ||w||_2}] ⪰ ζI_d for every w ∈ R^d and every group i.
Stronger than prior margin conditions that only require the bound at w*; it enables empirical sharpness (Lemma 2.2) for every iterate wt, which is load-bearing for the gap lower bound. Coverage of the claimed distribution family is argued by example, not fully proven.
domain assumption Activation σ is (α, β)-unbounded (Definition 1.1): non-decreasing, β-Lipschitz, α-growth on t1 ≥ t2 ≥ 0, σ(0)=0.
Needed for the surrogate gradient v(w;x,y)=2β(σ(w·x)−y)x, the linearization Lemma 3.5, and the Lipschitz-based moment controls.
domain assumption The f-divergence used in the regularizer is strongly convex over Δ_K (e.g., KL, χ²).
The dual update uses Bregman divergences D_φ derived from the divergence potential; strong convexity is required for the telescoping inequalities and the TV-via-divergence bound (Claim E.3).
standard math Fact 2.1 (population sharpness and moment bounds) from [WZDD23]; Fact 2.3 (label truncation with M = O(WBβ log(βBW/ε))) is w.l.o.g.
The proofs treat these as granted: the sharpness constant c1 and the bounded-label assumption are inherited from prior work, and provide the basis for Lemma 2.2 and the error bounds involving OPTm.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Robust Learning of a Group DRO Neuron." pith.science (2026). https://pith.science/paper/CQTZHDIS

@misc{pith2026260118115,
  author       = {Pith},
  title        = {Pith review of: Robust Learning of a Group DRO Neuron},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQTZHDIS}},
  note         = {Machine review of arXiv:2601.18115}
}

abstract

We study the problem of learning a single neuron under standard squared loss in the presence of arbitrary label noise and group-level distributional shifts, for a broad family of covariate distributions. Our goal is to identify a ''best-fit'' neuron parameterized by $\mathbf{w}_*$ that performs well under the most challenging reweighting of the groups. Specifically, we address a Group Distributionally Robust Optimization problem: given sample access to $K$ distinct distributions $\mathcal p_{[1]},\dots,\mathcal p_{[K]}$, we seek to approximate $\mathbf{w}_*$ that minimizes the worst-case objective over convex combinations of group distributions $\boldsymbol{\lambda} \in \Delta_K$, where the objective is $\sum_{i \in [K]}\lambda_{[i]}\,\mathbb E_{(\mathbf x,y)\sim\mathcal p_{[i]}}(\sigma(\mathbf w\cdot\mathbf x)-y)^2 - \nu d_f(\boldsymbol\lambda,\frac{1}{K}\mathbf1)$ and $d_f$ is an $f$-divergence that imposes (optional) penalty on deviations from uniform group weights, scaled by a parameter $\nu \geq 0$. We develop a computationally efficient primal-dual algorithm that outputs a vector $\widehat{\mathbf w}$ that is constant-factor competitive with $\mathbf{w}_*$ under the worst-case group weighting. Our analytical framework directly confronts the inherent nonconvexity of the loss function, providing robust learning guarantees in the face of arbitrary label corruptions and group-specific distributional shifts. The implementation of the dual extrapolation update motivated by our algorithmic framework shows promise on LLM pre-training benchmarks.

Figures

Figures reproduced from arXiv: 2601.18115 by the authors.

**Figure 1.** Compute-performance curve on Sheared-LLaMA-1.3B. Y-axis is the unweighted overall accuracy scores, X-axis is the number of tokens trained. Setup We isolate the impact of our reweighting algorithm by integrating our primal-dual method with KLdivergence regularization (PD-KL) directly into the Sheared LLaMA framework [XGZC24]. Starting from the Sheared-LLaMA-1.3B model—a 1.3B parameter version pruned from LLaMA2-7B [… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references

[1]

This contributes ton= ˜O B2τ ϵ2 log 1 δ in the stated sample complexity

If S is determined by the bias term (the first term), thenn must satisfy: n≥ 8 log(4/δ) ϵ2 Blog Cτ Bτ ϵ 2τ . This contributes ton= ˜O B2τ ϵ2 log 1 δ in the stated sample complexity
[2]

If S is determined by the clipping probability term (the second term), we get a recursive condition on n: n≥ 8 log(4/δ) ϵ2 (Blog(4n/δ)) 2τ . This is a recursive inequality of the form n≥Klog 2τ (n) where K= 8B2τ log(4/δ) ϵ2 ; by the standard technique for solving such recursive inequalities this is satisfied by alln≥max((2τ e)2τ ,2Klog 2τ (2K)) = Θ(Klog 2...
[3]

clipped” part and a “tail

If S is determined by the threshold term t0 (the third term), then S=t 0 and we need: n≥ 8 log(4/δ) ϵ2 t2 0. This contributesn=O t2 0 ϵ2 log(1/δ) to the sample complexity. The total sample complexity is the maximum of these three requirements, giving us the sample complexity stated in the lemma. 22 C Uniform Convergence and Population Approximation In Sec...
[5]

By Assumption 1.3, its true expectation is lower bounded: Ep[i][h1(w;x)]≥c 0∥w−w ∗∥2

Sharpness Bound.Let h1(w;x) = (σ(w·x)−σ(w ∗ ·x))(w·x−w ∗ ·x) . By Assumption 1.3, its true expectation is lower bounded: Ep[i][h1(w;x)]≥c 0∥w−w ∗∥2
[6]

The function class {h1(w;·) :w∈B(W)} is defined over the parameter ball w∈B(W)

We want to show that with high probability, the empirical expectation is close to this value. The function class {h1(w;·) :w∈B(W)} is defined over the parameter ball w∈B(W) . Let ∆w:=w−w ∗, and assume ∥∆w∥2 ≤2W for all w under consideration. Consider the random variable Zw =h 1(w;x). Its tail behavior can be bounded as follows: Sinceσisβ-Lipschitz, we hav...
[7]

Since we consider ∥w−w ∗∥2 ≥ϵ , we can now use Lemma C.1 with a target additive error c0 4 ϵ (i.e

Note that a1(x)≤4βW S 2d≤ ˜O(βdW B2) if ∥x∥2 2 ≤dS 2 x forS x = ˜O(B). Since we consider ∥w−w ∗∥2 ≥ϵ , we can now use Lemma C.1 with a target additive error c0 4 ϵ (i.e. replace ϵ in C.2 with c0ϵ/4), and a net radius r= c0ϵ 8a1 . The required number of samples N1 is dominated by the heavy-tailed term in the sample complexity bound, which must use the para...
[8]

These are defined over the space of unit vectors, u∈S d−1

Moment Bounds.Let h2(u;x) = (u·x) 4 and h3(u;x) = (u·x) 2. These are defined over the space of unit vectors, u∈S d−1. By Assumption 1.2, the population means are bounded, Ep[i][hj]≤5B , and their tails are given by: Pr(h2(u;x)> t)≤2 exp(−t 1/4/B) (τ 2 = 4, B2 =B) Pr(h3(u;x)> t)≤2 exp(−t 1/2/B) (τ 3 = 2, B3 =B) To apply Lemma C.1, we first need upper bound...
[9]

Most of the technical work is devoted to proving Lemma E.2

Per-iteration decompositionWe combine Lemmas E.1 and E.2 (an upper bound on atL(wt, bλ∗) and a lower bound on atL(w∗, bλt), respectively) to bound from above each atGap(wt, bλt) by a sum of differences in squared distances, Bregman divergences, and a residual error Et. Most of the technical work is devoted to proving Lemma E.2

Show all 13 references

[10]

Telescoping SumSumming the per-iteration bounds from t= 1 to n causes most distance and divergence terms to telescope, leaving only boundary terms at t= 0 and t=n , plus one remaining inner product−a n PK i=1(bλn[i] − bλn−1[i])Ebp[i][⟨v(wn−1;x, y),w∗ −w n⟩]
[11]

Before we carry out these steps in detail, we first state the two necessary bounds on atL(wt, bλ∗) and atL(w∗, bλt) that are required per-iteration decomposition

Residual ControlWe bound that final inner product via Young’s inequality and our step-size choice, absorbing it back into the telescoped Bregman and distance terms. Before we carry out these steps in detail, we first state the two necessary bounds on atL(wt, bλ∗) and atL(w∗, b...
[12]

Telescoping overt= 1, . . . , n.Summing the above inequalities from t= 1 to n causes all intermediate distance and divergence terms to cancel, leaving only the boundary terms at t= 0 and t=n , plus the term −an PK i=1(bλn[i] − bλn−1[i])Ebp[i][⟨v(wn−1;x, y),w∗ −w n⟩]. Concretel...
[13]

error terms

Bounding the final residual.It remains only to absorb the term −an PK i=1(bλn[i] − bλn−1[i])· Ebp[i][⟨v(wn−1;x, y),w∗ −w n⟩]. By Young’s inequality and our choice ofα1 and step size at in Algorithm 1, we can show that (see the derivation of Equation (28) in the proof of Lemma ...
[2018]

single neurons

Springer, 2018. [W AL24] Jun-Kun Wang, Jacob Abernethy, and Kfir Y . Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization.Mathematical Programming, 205(1- 2):203–268, 2024. [WZDD23] Puqian Wang, Nikos Zarifis, Ilias Diakonikolas...

2018

Pith tools

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

[1] [1]

This contributes ton= ˜O B2τ ϵ2 log 1 δ in the stated sample complexity

If S is determined by the bias term (the first term), thenn must satisfy: n≥ 8 log(4/δ) ϵ2 Blog Cτ Bτ ϵ 2τ . This contributes ton= ˜O B2τ ϵ2 log 1 δ in the stated sample complexity

[2] [2]

If S is determined by the clipping probability term (the second term), we get a recursive condition on n: n≥ 8 log(4/δ) ϵ2 (Blog(4n/δ)) 2τ . This is a recursive inequality of the form n≥Klog 2τ (n) where K= 8B2τ log(4/δ) ϵ2 ; by the standard technique for solving such recursive inequalities this is satisfied by alln≥max((2τ e)2τ ,2Klog 2τ (2K)) = Θ(Klog 2...

[3] [3]

clipped” part and a “tail

If S is determined by the threshold term t0 (the third term), then S=t 0 and we need: n≥ 8 log(4/δ) ϵ2 t2 0. This contributesn=O t2 0 ϵ2 log(1/δ) to the sample complexity. The total sample complexity is the maximum of these three requirements, giving us the sample complexity stated in the lemma. 22 C Uniform Convergence and Population Approximation In Sec...

[4] [5]

By Assumption 1.3, its true expectation is lower bounded: Ep[i][h1(w;x)]≥c 0∥w−w ∗∥2

Sharpness Bound.Let h1(w;x) = (σ(w·x)−σ(w ∗ ·x))(w·x−w ∗ ·x) . By Assumption 1.3, its true expectation is lower bounded: Ep[i][h1(w;x)]≥c 0∥w−w ∗∥2

[5] [6]

The function class {h1(w;·) :w∈B(W)} is defined over the parameter ball w∈B(W)

We want to show that with high probability, the empirical expectation is close to this value. The function class {h1(w;·) :w∈B(W)} is defined over the parameter ball w∈B(W) . Let ∆w:=w−w ∗, and assume ∥∆w∥2 ≤2W for all w under consideration. Consider the random variable Zw =h 1(w;x). Its tail behavior can be bounded as follows: Sinceσisβ-Lipschitz, we hav...

[6] [7]

Since we consider ∥w−w ∗∥2 ≥ϵ , we can now use Lemma C.1 with a target additive error c0 4 ϵ (i.e

Note that a1(x)≤4βW S 2d≤ ˜O(βdW B2) if ∥x∥2 2 ≤dS 2 x forS x = ˜O(B). Since we consider ∥w−w ∗∥2 ≥ϵ , we can now use Lemma C.1 with a target additive error c0 4 ϵ (i.e. replace ϵ in C.2 with c0ϵ/4), and a net radius r= c0ϵ 8a1 . The required number of samples N1 is dominated by the heavy-tailed term in the sample complexity bound, which must use the para...

[7] [8]

These are defined over the space of unit vectors, u∈S d−1

Moment Bounds.Let h2(u;x) = (u·x) 4 and h3(u;x) = (u·x) 2. These are defined over the space of unit vectors, u∈S d−1. By Assumption 1.2, the population means are bounded, Ep[i][hj]≤5B , and their tails are given by: Pr(h2(u;x)> t)≤2 exp(−t 1/4/B) (τ 2 = 4, B2 =B) Pr(h3(u;x)> t)≤2 exp(−t 1/2/B) (τ 3 = 2, B3 =B) To apply Lemma C.1, we first need upper bound...

[8] [9]

Most of the technical work is devoted to proving Lemma E.2

Per-iteration decompositionWe combine Lemmas E.1 and E.2 (an upper bound on atL(wt, bλ∗) and a lower bound on atL(w∗, bλt), respectively) to bound from above each atGap(wt, bλt) by a sum of differences in squared distances, Bregman divergences, and a residual error Et. Most of the technical work is devoted to proving Lemma E.2