Stochastic Linear Optimization with Adversarial Corruption

Edmund Y. Lou; Liren Shan; Yingkai Li

REVIEW 2 major objections 6 minor 1 cited by

Stochastic Linear Optimization with Adversarial Corruption

T0 review · 2 major / 6 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 gives the first stochastic linear optimization algorithm whose regret grows only linearly in the adversary's total corruption C, without the algorithm knowing C.

desk verdict First corruption-robust bound for stochastic linear bandits, but Lemma 4.1's martingale step depends on an unstated adversary-timing assumption that the paper must clarify before the result is citable. read the letter →

arxiv 1909.02109 v1 pith:U36V4QUL submitted 2019-09-04 cs.LG stat.ML

Yingkai Li , Edmund Y. Lou , Liren Shan This is my paper · ORCID

classification cs.LGstat.ML MSC 68Q3268W27

keywords stochasticlinearbanditsadversarialcorruptionregretboundLöwner-Johnellipsoidsupportbasisexplorationepochscheduleadaptiveadversarycoordinate-wiseestimation

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

The paper extends the model of stochastic bandits with adversarial corruption from finitely many arms to stochastic linear optimization, where each action is a vector in a $d$-dimensional polytope and the hidden reward vector must be learned. It presents the Support Basis Exploration (SBE) algorithm and proves that, with probability at least $1-\delta$, its regret is $O(d^2 C \log T / \Delta + d^5 \log(d \log T/\delta) \log T / \Delta^2)$, where $C$ is the total corruption and $\Delta$ is the reward gap between the best and second-best actions. The two properties that matter are that regret grows only linearly in $C$ and that the algorithm never needs to know $C$. Prior linear-bandit methods such as confidence-ball and OFUL-style algorithms suffer linear-in-$T$ regret even under small corruption, so this is the first smooth degradation in the linear setting.

What carries the argument

The load-bearing piece is Support Basis Exploration with a Löwner-John ellipsoid: for the polytope $D$, choose an ellipsoid $E$ with $E \subseteq D \subseteq dE$ and take its principal axes $S = \{s_1,\dots,s_d\}$ as the exploration set. Corollary 2.2 ensures every $x \in D$ has coefficients $|\hat{a}_j| \le 2d$ in this basis, so each basis pull carries the maximum possible information in its direction, and the orthogonal basis makes coordinate-wise estimation unbiased and easy to concentrate. Epochs of length $n_m = \zeta \cdot 4^m$ discount old corruption by a factor of $1/8$ per epoch in the gap estimates, which is what converts a $C$-sized adversary into an additive $O(C)$ regret term. The estimated-gap upper and lower bounds (Lemmas 4.3 and 4.4) are the quantitative engine that turns per-epoch estimation error into the final bound.

What would settle it

Check whether the martingale property in Lemma 4.1 holds by computing $\mathbb{E}[(\xi_t^j - p)c_t(s_j)\mid\mathcal{F}_{t-1}]$ under the protocol's ordering. If the adversary may choose $c_t$ after seeing the exploration draw, set $c_t(s_j)=-1$ on the pulled basis vector and $0$ otherwise with $C=O(1)$; the conditional mean is nonzero, the estimate is biased by a constant each epoch, and regret grows linearly in $T$, contradicting the claimed $O(C\log T/\Delta)$ bound.

Watch

Extended reading notes

Core claim

The central claim is that an adaptive adversary's bounded reward corruption can be absorbed into stochastic linear bandit regret at a cost linear in the total corruption $C$. The proof route is: run epochs whose lengths grow exponentially; in each epoch explore each principal axis of a Löwner-John ellipsoid just enough to control estimation error, and otherwise exploit the best action according to the previous epoch's estimate. Coordinate-wise estimation on the orthogonal basis makes the exploration indicators nearly independent of the noise and lets the corruption term be bounded by a Freedman-type martingale inequality. Lemmas 4.3 and 4.4 sandwich the estimated gap between upper and lower bounds that decay with past corruption, yielding the linear-in-$C$ regret bound; Section 6 replaces the exact ellipsoid with a polynomial-time weak ellipsoid at the cost of an extra factor $d^{1/2}$ and $d$ in the two terms.

Load-bearing premise

The load-bearing premise is that the adversary chooses each round's corruption before seeing which basis vector the algorithm explores that round; if the adversary could react to the current exploration draw, the martingale step and the whole regret bound collapse.

Editorial extensions

If this is right

This is the first algorithm for stochastic linear optimization with adversarial corruption, answering an open question posed in the finite-arm corruption literature.
Regret grows only linearly in the total corruption $C$ even though the algorithm is agnostic to $C$; when $C = O(1)$ the bound matches known no-corruption problem-dependent regret up to logarithmic factors.
Using the polynomial-time weak Löwner-John ellipsoid, the same guarantee holds computationally efficiently with regret $O(d^{5/2} C \log T / \Delta + d^6 \log(d \log T/\delta) \log T / \Delta^2)$.
Setting $\delta = 1/T$ gives expected regret $O(d^{5/2} C \log T / \Delta + d^6 \log^2 T / \Delta^2)$, asymptotically within one $\log T$ factor of the no-corruption lower bound.

Reading between the lines

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

The proof's martingale step (Lemma 4.1) silently assumes the adversary's corruption for round $t$ is fixed before the algorithm's exploration draw is revealed; if the protocol instead let the adversary condition on the current action, the concentration bound would fail. A timing-robust variant could use private randomness or delayed reward observation to close this gap.
The coordinate-wise basis estimator is not tied to the ellipsoid: any exploration set whose coefficients are bounded (for example, a barycentric spanner of the polytope) could replace the Löwner-John ellipsoid with only constant-factor changes, which suggests the regret bounds are portable to other action sets.
The exponential epoch schedule discounts past corruption by $1/8$ per epoch, so the same schedule could make other optimistic linear bandit algorithms corruption-robust if their estimators are replaced by epoch-local coordinate estimates; running SBE against a confidence-ball variant under the same adversary is a direct test.

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

Read this one. It's the first attempt I know of to get corruption-robust bounds for stochastic linear bandits, and the core idea is respectable: explore along the axes of a Löwner-John ellipsoid, estimate each coordinate independently, and run epochs of increasing length so old corruption is discounted. That is a meaningful combination of Gupta et al. and Dani et al., and the regret target—linear in the total corruption C, without knowing C—is the right one.

The proof has one load-bearing ambiguity. Lemma 4.1 treats X_t = (ξ_t^j − n_e/N_m)c_t(s_j) as a martingale difference, asserting ξ_t^j is independent of c_t(s_j) given the past. That requires the adversary to choose the corruption function before seeing the algorithm's action. Section 2 is not clear on this: it says the adversary chooses a corruption function and the algorithm chooses first x_t, then observes corrupted reward. Under the natural reading where the adversary corrupts after seeing the action, the independence fails. An adversary can then corrupt exactly the pulls of one basis direction; the martingale is not centered, and a single epoch of corruption of size Θ(1/Δ²) leaves a constant bias in the estimate, which the next exploitation epoch converts into Ω(TΔ) regret—larger than the stated bound. So this has to be fixed. The authors probably mean the Lykouris convention (corruption chosen before the current action), in which case Lemma 4.1 is fine, but they have to say so explicitly and reword the protocol.

Two smaller things. Equation (2) writes V as the variance of a single X_t and then sums over t in the same bound; Freedman's inequality needs the total conditional variance, so the notation should be cleaned up. And ζ is set to d^6 in Algorithm 1 but d^5 in Lemma 4.1, with both d^5 and d^6 appearing in the advertised bounds. That needs aligning.

The rest of the argument—Lemmas 4.2–4.4, the epoch-based regret decomposition—looks coherent to me, and there are no fitted constants or circular moves. The gap analysis and the exploration/exploitation trade-off check out.

Bottom line: this is a serious paper that deserves a real referee. I'd send it out, with the expectation of major revision. If the timing assumption is clarified and the small inconsistencies are fixed, I think it will be a solid contribution to the bandit theory literature. As it stands, I wouldn't cite the current version.

Referee Report

2 major / 6 minor

Summary. This paper extends the stochastic linear optimization model of Dani et al. to the setting where an adaptive adversary can corrupt observed rewards by an unknown total amount C. The proposed SBE algorithm separates exploration and exploitation: at each epoch it explores the orthogonal basis given by a Löwner–John ellipsoid and exploits the action estimated from the previous epoch, with epoch lengths growing exponentially. The main result, Theorem 5.1, claims a regret bound of O(d^2 C log T / Delta + d^5 log(4d log T/delta) log T / Delta^2) with probability at least 1 - delta, and Section 6 upgrades the constants when only a weak Löwner–John ellipsoid is available. The proof proceeds by bounding the per-coordinate estimation error (Lemma 4.1), translating it to a uniform reward-estimation error (Lemma 4.2), and then controlling the estimated gap from above and below (Lemmas 4.3 and 4.4) before summing the regret over epochs.

Significance. The result is significant if correct: it would give the first algorithm for stochastic linear optimization with adversarial corruption whose regret grows only linearly in the total corruption C and does not require the algorithm to know C. The proof architecture is a genuinely new analysis rather than a repackaging: the coordinate-wise exploration scheme is designed to make the corruption term amenable to martingale concentration, and the epoch-doubling construction damps the effect of past corruption. The paper's claims are explicit and falsifiable, and the derivation is not circular: it relies on standard external tools such as Hoeffding and Freedman-type inequalities. However, two load-bearing points in the current manuscript need to be repaired: the timing of the adversary's corruption choice relative to the current action must be stated precisely, and the exploration regret analysis in Theorem 5.1 uses the wrong estimated-gap index. Neither issue appears fatal if the intended conventions are made explicit, but both must be fixed before the result can be accepted.

major comments (2)

[Section 2 and Lemma 4.1] The proof of Lemma 4.1 relies on the assertion that xi_t^j is independent of c_t(s_j) conditional on F_{t-1}. This is exactly a timing assumption: the adversary must choose c_t before the algorithm's random exploration decision at time t is realized, so that c_t may depend on past history but not on the current action x_t. The protocol statement in Section 2 only says "The algorithm chooses first x_t, then observes the corrupted reward," which admits the opposite reading. If c_t may be chosen after seeing x_t, the adversary can set c_t(s_j)=1 precisely on exploration pulls of one basis direction; then the centered quantity (xi_t^j - n_e/N_m)c_t(s_j) is not a martingale difference, Lemma 4.1 fails, and the regret bound collapses. For example, an adversary that corrupts every exploration pull of a single basis vector at level 1 in each epoch incurs total corruption O(M zeta Delta^{-2}/d) while inducing a constant bias, leading to Omega(T Delta) regret, which contradicts Theorem 5.1 for large T. The authors should either state explicitly that c_t is chosen before x_t (the standard Lykouris et al. convention) or revise the model and proof.
[Section 5, proof of Theorem 5.1] The proof of the exploration regret R_2 states that "the expected number of time steps in which exploration is conducted is zeta / (Delta-hat^{(m)})^2." According to Algorithm 1, epoch m explores with probability gamma_{m-1} and has expected exploration count zeta (Delta-hat^{(m-1)})^{-2}, not zeta (Delta-hat^{(m)})^{-2}. The subsequent case analysis therefore bounds the wrong sum; as written it does not establish the claimed bound on the actual exploration regret. The argument appears repairable by re-indexing (k = m-1) and adjusting the thresholds by constant factors, but this must be carried out explicitly.

minor comments (6)

[Algorithm 1 and Lemma 4.1] Algorithm 1 and Section 6 set zeta = 2^{14} d^6 log(...), while Lemma 4.1 and Theorem 5.1 use zeta = O(d^5 log(...)); the exact-ellipsoid version should specify d^5 and the weak-ellipsoid version d^6, with the derivation shown.
[Lemma 4.1] In the variance bound, V is introduced as E[X_t^2 | F_{t-1}] but then used as the sum over t of the conditional variances; the notation should be separated to avoid ambiguity.
[Lemma 4.1] The filtration defined in Lemma 4.1 includes eta_{t+1} in F_t; this should be justified or corrected, since it makes F_t depend on a future noise variable.
[Section 2] The statement that uniqueness of x* is without loss of generality by perturbing the action set with random noise is not formalized; either define the perturbation or state the uniqueness as an assumption.
[Section 5, inequality (8)] In the exploitation regret calculation, the chain after Inequality (8) drops the d^2 and zeta factors; the final corruption term should be O(d^2 C), not "512C" as displayed.
[References] The bibliography spells "Grötschel" as "Grtschel" and "Lovász" as "Lovsz" in the first reference; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the regret derivation is self-contained and does not reduce to its inputs or to self-citations.

full rationale

The paper's derivation is an analytical regret bound for a newly proposed algorithm, and the bound is not used to define the algorithm or its parameters. The constants zeta, gamma_m, and epoch lengths are fixed before the proof and are not fitted to data or to the claimed regret expression. The main lemmas (4.1-4.4) are proven in the paper using standard external concentration inequalities (Hoeffding, Freedman/Beygelzimer) and the Lowner-John ellipsoid theorem, none of which encode the target regret bound. The paper cites prior work for the corruption model and the epoch-based idea, but the central argument does not rely on any self-citation or on a uniqueness theorem imported from the authors' own prior work. The only noteworthy assumption is the conditional independence of the exploration indicator and the corruption level in Lemma 4.1; even if that timing assumption were questionable, it is a modeling/correctness issue rather than a circularity, because it does not make the conclusion equivalent to an input by construction. No prediction is a renamed fit, and no known result is merely relabeled. The derivation is therefore self-contained with respect to circularity concerns.

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

The central claim rests on standard probability inequalities, the Lowner-John ellipsoid theorem, and the modeling assumptions of sub-Gaussian noise, bounded corruption, a polytope decision set, and uniqueness of the optimal action. The most fragile premise is the independence of each round's corruption function from the current exploration coin flip: it is asserted without discussion, and the protocol description in Section 2 is ambiguous about whether the adversary chooses c_t before or after seeing x_t. No new physical or mathematical entities are introduced.

assumptions (6)

domain assumption The reward noise eta_t is sub-Gaussian with mean 0 and variance proxy 1.
Stated in Section 2 as the reward model; used by the Hoeffding-type concentration bound in Lemma 4.1.
domain assumption The adversary's corruption function c_t maps D to [-1,1] and the total corruption C is finite but unknown.
Stated in Section 2 and used throughout; the regret bound is linear in C.
domain assumption The decision set D is a d-dimensional polytope and the optimal action x* is unique.
Stated in Section 2 and Preliminaries; used to define the gap Delta and to bound the regret by suboptimality gaps.
domain assumption The corruption function c_t is independent of the current exploration indicators xi_t^j conditional on the past filtration F_{t-1}.
Invoked in Lemma 4.1: 'Since xi_t^j is independent of the corruption level c_t^j conditional on F_{t-1}'. This is the weakest premise and is not derived from the protocol description.
standard math The Lowner-John ellipsoid theorem: for any bounded convex body K there is an ellipsoid E with E subset K subset dE, and a polynomial-time weak version with factor 2d^(3/2).
Theorem 2.1 and Section 6, used to construct the exploration basis S with bounded coordinates (Corollary 2.2).
standard math Standard concentration inequalities: Hoeffding's inequality and the Freedman-type martingale inequality of Beygelzimer et al. 2011.
Used in Lemma 4.1 and Appendix A to control noise and corruption deviations.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Stochastic Linear Optimization with Adversarial Corruption." pith.science (2026). https://pith.science/paper/U36V4QUL

@misc{pith2026190902109,
  author       = {Pith},
  title        = {Pith review of: Stochastic Linear Optimization with Adversarial Corruption},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U36V4QUL}},
  note         = {Machine review of arXiv:1909.02109}
}

read the original abstract

We extend the model of stochastic bandits with adversarial corruption (Lykouriset al., 2018) to the stochastic linear optimization problem (Dani et al., 2008). Our algorithm is agnostic to the amount of corruption chosen by the adaptive adversary. The regret of the algorithm only increases linearly in the amount of corruption. Our algorithm involves using L\"owner-John's ellipsoid for exploration and dividing time horizon into epochs with exponentially increasing size to limit the influence of corruption.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Cascading Bandits Robust to Adversarial Corruptions
cs.LG 2025-02 conditional novelty 6.0 of 10

Cascading bandits can be made robust to adversarial click corruption using multi-instance position-based elimination, with regret logarithmic in time and linear in the corruption budget.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

Abbasi-Yadkori, Y., P \'a l, D., and Szepesv \'a ri, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems , pages 2312--2320

work page 2011
[2]

Auer, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research , 3(Nov):397--422

2002
[3]

Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages 19--26

work page 2011
[4]

and Slivkins, A

Bubeck, S. and Slivkins, A. (2012). The best of both worlds: stochastic and adversarial bandits. In Proceedings of the 25th Conference on Learning Theory (COLT) , pages 42--1

work page 2012
[5]

P., and Kakade, S

Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Conference on Learning Theory (COLT) , pages 355--366

work page 2008
[6]

Grtschel, M., Lovsz, L., and Schrijver, A. (1988). Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics , 2:65--84

work page 1988
[7]

Gupta, A., Koren, T., and Talwar, K. (2019). Better algorithms for stochastic bandits with adversarial corruptions. In Proceedings of the 32nd Conference on Learning Theory, to appear

work page 2019
[8]

Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58(301):13--30

1963

Show all 15 references

[9]

K., and Kar, P

Kapoor, S., Patel, K. K., and Kar, P. (2019). Corruption-tolerant bandit learning. Machine Learning , 108(4):687--715

2019
[10]

and Szepesvari, C

Lattimore, T. and Szepesvari, C. (2017). The end of optimism? A n asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics , pages 728--737

2017
[11]

Li, Y., Wang, Y., and Zhou, Y. (2019). Tight regret bounds for infinite-armed linear contextual bandits. arXiv preprint arXiv:1905.01435

2019 arXiv
[12]

Lov \'a sz, L. (1991). Geometric algorithms and algorithmic geometry. In Satake, I., editor, Proceedings of the International Congress of Mathematicians 1990 , volume 1, pages 139--154. The Mathematical Society of Japan, Springer-Verlag

1991
[13]

Lykouris, T., Mirrokni, V., and Paes Leme, R. (2018). Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 114--122. ACM

2018
[14]

Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society , 58:527--535

1952
[15]

and Seldin, Y

Zimmert, J. and Seldin, Y. (2018). An optimal algorithm for stochastic and adversarial bandits. arXiv preprint arXiv:1807.07623

2018 arXiv

Pith tools

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

[1] [1]

Abbasi-Yadkori, Y., P \'a l, D., and Szepesv \'a ri, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems , pages 2312--2320

work page 2011

[2] [2]

Auer, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research , 3(Nov):397--422

2002

[3] [3]

Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages 19--26

work page 2011

[4] [4]

and Slivkins, A

Bubeck, S. and Slivkins, A. (2012). The best of both worlds: stochastic and adversarial bandits. In Proceedings of the 25th Conference on Learning Theory (COLT) , pages 42--1

work page 2012

[5] [5]

P., and Kakade, S

Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Conference on Learning Theory (COLT) , pages 355--366

work page 2008

[6] [6]

Grtschel, M., Lovsz, L., and Schrijver, A. (1988). Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics , 2:65--84

work page 1988

[7] [7]

Gupta, A., Koren, T., and Talwar, K. (2019). Better algorithms for stochastic bandits with adversarial corruptions. In Proceedings of the 32nd Conference on Learning Theory, to appear

work page 2019

[8] [8]

Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58(301):13--30

1963