Pith. sign in

REVIEW 3 major objections 5 minor 49 references

Unconstrained Robust Online Convex Optimization

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Adversarial gradient corruption in unconstrained online learning can be absorbed at the optimal rate, with a matching lower bound.

desk verdict First unconstrained OCO with adversarial corruptions, optimal known-G rate; main proof has a repairable gap in the error bound, not a structural failure. read the letter →

arxiv 2506.12781 v1 pith:3GIY2XGO submitted 2025-06-15 cs.LG math.OC

Jiujia Zhang , Ashok Cutkosky This is my paper
classification cs.LGmath.OC
keywords onlineconvexoptimizationunconstrainedlearningadversarialgradientcorruptionregretboundsparameter-freeclippingHuberregularizationlower
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

Online convex optimization normally assumes the learner sees true gradients, but in practice gradients can be corrupted by outliers, mislabeled data, or tampering. This paper treats the hardest version of that problem: the decision variable can range over all of $\mathbb{R}^d$, so a learner cannot rely on a bounded domain to keep mistakes from growing exponentially. Its central claim is that, given a known corruption budget $k$ and Lipschitz bound $G$, a clipped and regularized online update keeps regret against any comparator $u$ at $\widetilde{O}(\|u\| G(\sqrt{T}+k))$, and that no algorithm can improve on this. When $G$ is unknown, the paper still obtains a regret bound, with an extra additive penalty of order $(\|u\|^2+G^2)k$. These rates mean corruption up to $k = O(\sqrt{T})$ rounds costs nothing in asymptotics, which is what makes the result worth knowing.

What carries the argument

The load-bearing object is the regret decomposition $R_T(u) = R^A_T(u) + \mathrm{ERROR} - \mathrm{CORRECTION} + \mathrm{BIAS}$, built over clipped gradients $\tilde{g}^c_t = \tilde{g}_t \min(h_t, \|\tilde{g}_t\|)/\|\tilde{g}_t\|$ and a regularizer $r_t$. The regularizer is a Huber-type loss $f_t(w;c,p,\alpha)= c\,\sigma_t(w;p,\alpha)/S_t^{1-1/p}$ with $S_t = \sum_{i\le t} \|w_i\|^p + \alpha^p$, which grows polynomially near $\|w_t\|$ and linearly farther out; scaled with $c=kG$ it cancels the corruption error and keeps bias at $O(kG\|u\|)$. The base learner is a centered mirror descent that guarantees composite regret $O(\|u\|G\sqrt{T})$ even with the nonstandard regularizer. For unknown $G$, a filter doubles a clipping threshold only after $k+1$ excess-gradient events, so the threshold stays $O(G)$ and truncation happens few times, while a tracker marks epochs of $\|w_t\|$ growth so a sparse quadratic regularizer can absorb corruption error without adding $T\|u\|^2$ bias; epigraph-based regularization in $\mathbb{R}^{d+1}$ handles the quadratic term whose coefficient is unknown in advance.

What would settle it

Run the known-$G$ algorithm on the 1-D losses $\ell_t(w)=|w-1|$ with $T=k^2$, corrupting $k$ consecutive gradients by negation (as in the paper's Figure 1), and compare regret against $D(\sqrt{T}+k)$. The theorem predicts regret $\Theta(Dk)$ along $T=k^2$; if regret grows exponentially in $k$, as an unregularized learner does in the same experiment, the bound is false. Conversely, checking several $k \in \{20,\dots,70\}$ confirms the linear-in-$k$ rate.

Watch

Extended reading notes

Core claim

The paper's claim is that adversarial gradient corruption has a bounded, additive effect on unconstrained online convex optimization, not a destabilizing one. Under the corruption model where $k$ bounds both the number of rounds with large deviation and the total capped deviation, Theorem 5.1 gives regret $\widetilde{O}(\|u\|G(\sqrt{T}+k))$ when $G \ge \max_t \|g_t\|$ is known, Theorem 5.2 shows any algorithm must suffer $\Omega(\|u\|(\sqrt{T}+k))$ for some comparator of any chosen norm, and Corollary 6.2 removes the need to know $G$ at the price of an extra $(k+1)(\|u\|^2+[G]_{\tau_G}^2)$ term, where $[G]_{\tau_G}=\max(\tau_G,G)$. The key conceptual move is that regularization can be made to cancel the corruption error almost perfectly: a Huber-type regularizer scaled by $kG$ converts the worst-case corruption damage $kG \max_t \|w_t\|$ into an $O(\epsilon G)$ offset, while the composite-loss learner keeps the clean $O(\|u\|G\sqrt{T})$ term. When $G$ is unknown, a $k$-lag threshold filter and a tracker-epoch mechanism control clipping error and corruption error separately, yielding the same leading term with the additional quadratic penalty.

Load-bearing premise

The load-bearing premise is that the learner is handed an accurate upper bound $k$ on the total corruption before the game starts; all thresholds and regularizer scales are built from $k$, so a missing or wrong $k$ collapses the guarantees.

Editorial extensions

If this is right

  • Corruption is free up to $k = O(\sqrt{T})$: the regret bound remains $\widetilde{O}(\|u\|G\sqrt{T})$, the same order as the uncorrupted benchmark, for any corruption budget up to that size.
  • The known-$G$ guarantee is tight: the matching lower bound rules out any algorithm with regret $o(\|u\|(\sqrt{T}+k))$ on the hard instances constructed in Theorem 5.2.
  • At the comparator $u=0$ the known-$G$ regret is constant regardless of $k$, so the learner can always fall back to a default action without catastrophic loss.
  • An online-to-batch conversion turns the regret bound into a stochastic convex optimization guarantee with error $\widetilde{O}(\|u\|G(\sqrt{T}+k)/T)$ when $k$ of the $T$ gradient evaluations are arbitrarily corrupted.
  • The same machinery covers an online distributionally robust optimization objective under total-variation and KL uncertainty sets.

Reading between the lines

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

  • Beyond the paper: because $k$ is an input, a practical deployment needs an estimate of $k$; the paper does not give a data-driven way to set it, and a wrong estimate breaks the threshold and regularizer scales.
  • Beyond the paper: the lower bound's hard instances corrupt gradients by flipping their sign, so the count of flipped rounds rather than the magnitude of deviation appears to be what drives the $k$ penalty; this could guide cheaper defenses.
  • Beyond the paper: the constant-regret-at-zero property suggests a safety interpretation: if the learner treats the origin as a default, heavy corruption cannot force it much above the default's loss, which is testable in real optimization pipelines.
  • Beyond the paper: a direct empirical check on deterministic convex problems, such as logistic regression with a handful of sign-flipped gradient evaluations, should show excess error scaling like $(\sqrt{T}+k)/T$ once $k$ is supplied; the paper itself gives no experiments.
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.

Referee Report

3 major / 5 minor

Summary. The paper studies unconstrained online convex optimization where the learner observes adversarially corrupted gradients instead of true gradients, with corruption measured by a budget k through Equations (3) and (4). The main claims are: (i) when a Lipschitz bound G is known, Algorithm 1 with a specific Huber regularizer and the centered mirror-descent base of Jacobsen and Cutkosky achieves regret O~(||u||G(√T+k)); (ii) a matching lower bound Ω(||u||(√T+k)) is claimed in Theorem 5.2; (iii) when G is unknown, a FILTER/TRACKER mechanism with epigraph regularization gives O~(||u||[G]_tauG(√T+k) plus an additive penalty in ||u||² and [G]²). The paper also provides two applications, to stochastic convex optimization and an online distributionally robust optimization formulation. The development is organized around a four-term regret decomposition (RA, ERROR, CORRECTION, BIAS) and uses previously published machinery, mostly from the same authors, for the regularizer, the base learner, and the unknown-G epigraph construction.

Significance. If the main theorems are correct, this is the first optimal-rate treatment of unconstrained online convex optimization under adversarial gradient corruption, and the paper gives a coherent and reasonably modular design: clipping, a specifically scaled regularizer, and a composite-regret base learner. The unknown-G section is technically ambitious and the FILTER/TRACKER devices are natural contributions. The paper is also honest about relying on prior published proofs rather than reproducing them. However, two load-bearing proof steps are currently defective: the known-G ERROR bound in Section 5.1 does not follow from the corruption model, and the lower-bound proof in Theorem 5.2 drops an expectation term that is not zero. Both issues appear repairable without changing the stated rates, but they must be fixed before the central claims are established.

major comments (3)
  1. [Theorem 5.2] The displayed bound ERROR ≤ (Σ_{t∈B}||g_t−g̃_t|| + G|B̄|) max_t||w_t|| ≤ kG max_t||w_t|| is not implied by Equation (4). Equation (4) gives G|B| + Σ_{t∈B̄} min(||g_t−g̃_t||, G) ≤ kG, which bounds G|B| + Σ_{t∈B̄}||g_t−g̃_t||, whereas the manuscript's sum has Σ_{t∈B}||g_t−g̃_t||, and on B the deviations are unbounded. With clipping at ht=G the valid bound is ERROR ≤ (2G|B| + Σ_{t∈B̄}||g_t−g̃_t||)·max_t||w_t|| ≤ 2kG·max_t||w_t||. Since the proof sets c=kG, Lemma B.1 cancels only kG max_t||w_t||, leaving an uncontrolled kG max_t||w_t|| residual; Lemma E.3 shows that max_t||w_t|| can be exponential, so the residual is not absorbed elsewhere. The theorem is repairable by taking c=Θ(kG) (e.g., c=2kG), and the rest of the argument is unchanged, but the proof as written fails.
  2. [Corollary 6.2] The proof of Theorem 5.2 drops the first expectation term Σ_t E[⟨E_t[z_t]q, w_t⟩]. For t≤k this term is not zero: z_1,...,z_k are defined as sign(Σ_{t=k+1}^T z_t), so they depend on future signs, and with the sign convention needed to keep z_t in {−1,+1} the expectation E_t[z_t] is positive. An algorithm that sets w_t = −Mq for t≤k makes this term negative and can overpower the Dk term, so the claimed Ω(||u*||(√T+k)) lower bound is not established for all algorithms as stated. The construction may be salvageable by choosing q adaptively after seeing the algorithm's early iterates or by adding a condition on the algorithm, but the current proof is incomplete.
  3. [Theorem E.5] As typeset, Corollary 6.2 states an extra additive penalty of (k+1)(||u||² + [G]²_τG/τG), but substituting c=kτG, γβ=k, γα=1, τD=ϵ/k into Theorem J.1 yields O~(k||u||² + k max(τG,G)²) after absorbing log factors, not an expression with [G]²/τG. The displayed form also conflicts with the abstract's claim of an additive (||u||²+G²)k penalty. Please correct the display or reconcile the derivation; if the printed [G]²/τG is intentional, the unknown-G rate depends on τG in a way that is not stated in the abstract.
minor comments (5)
  1. [Algorithm 3] Algorithm 3 doubles the threshold when the counter n reaches k, but Lemma F.2's proof repeatedly refers to k+1 clipped gradients; please check the off-by-one and state the resulting bound on h_T consistently.
  2. [Theorem E.5] The proof describes the corruption step as 'reversing the direction' of k gradients, but the actual construction sets g_t = 0 on S; please rephrase to match the algebra.
  3. [Abstract and Corollary 6.2] The abstract promises an extra additive penalty of (||u||²+G²)k, while the theorem's bound uses max(τG,G) and thus depends on the initial guess τG; please state explicitly how τG is chosen or why the displayed corollary should be read with τG=O(G).
  4. [Notation] Equation (7) defines σ_t with an p-norm while the rest of the paper uses the Euclidean norm; please clarify the norm notation, and also check the typesetting of Equation (6) and of the lower-bound display in Theorem 5.2.
  5. [Presentation] There are several typos and formatting issues: 'the the corrupted gradient', 'difficutly', '42 st' in the proceedings line, and Figure 1's caption should define what is plotted. These do not affect the substance but should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof chain uses cited published lemmas and in-appendix verifications; the regret bound is not equivalent to a fitted input or to the corruption model by construction.

full rationale

The derivation chain is largely self-contained or backed by published prior results whose assumptions do not include the target corruption regret. The Huber regularizer bounds (Lemma B.1) are re-stated and partly re-proved from Zhang & Cutkosky (2022) with parameters c, p, alpha that are set after the fact but not fit to the comparator or regret; the centered mirror-descent composite-regret bound (Theorem C.2) is verified in Appendix C from Jacobsen & Cutkosky (2022)'s Lemma 1; the unknown-G epigraph bound (Theorem I.3) is explicitly built on Cutkosky & Mhammedi (2024)'s Theorem 10. These are parameter-free technical theorems with stated assumptions that do not include the corruption regret being proved, so they are independent support rather than circular self-citation. The corruption parameter k is an input budget satisfying Equations (3)-(4), not a quantity fitted from the regret, and Equation (6) is an algebraic decomposition rather than a definition of the result. The lower bound constructs a hard instance and is not derived from the upper bound. The conclusion's caveat about unknown-G k-dependence is a limitation, not a circularity. The skeptic's factor-two concern about the ERROR inequality in Section 5.1 is a possible proof-correctness issue (an apparent B/Bbar set-index slip), not a reduction of the theorem to its inputs, so it does not change the circularity score.

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

The central claim rests on the corruption-model assumptions and on several mathematical lemmas from prior work. No physically invented entities are introduced. The main free choices are algorithm hyperparameters epsilon, tauG, tauD, c, gamma_alpha, and gamma_beta, which are set by hand in the corollaries rather than fitted to data.

free parameters (5)
  • epsilon = user-specified positive constant
    Appears as additive epsilon G or epsilon [G]_tauG in the regret bounds and as alpha = epsilon/k in the known-G regularizer. It is chosen by hand to control the origin regret and does not affect the asymptotic rate.
  • tauG = user-specified initial Lipschitz guess
    Initial threshold in FILTER for the unknown-G case. The regret depends on [G]_tauG = max(tauG, G), and a poor guess changes the leading constant or the additive term.
  • tauD = user-specified initial magnitude guess
    Initial threshold in TRACKER for the unknown-G case; set to epsilon/k in Corollary 6.2. It controls the epoch partition of ||w_t|| and appears in the k tauD G term.
  • c = kG in known-G case, k tauG in Corollary 6.2
    Scale of the Huber regularizer. It must be large enough to cancel the corruption error and appears explicitly in the OFFSET and BIAS bounds.
  • gamma_alpha and gamma_beta = gamma_alpha=1, gamma_beta=k in Corollary 6.2
    Weights of the sparse quadratic regularizers. They set the tradeoff between truncation-error control and the (||u||^2) bias.
assumptions (4)
  • domain assumption The learner is given a scalar k satisfying |B| <= k and (1/G) sum min(||g_t - g_tilde_t||, G) <= k, as in Equations (3) and (4).
    This is the formal corruption model from Section 2. All regret bounds are stated in terms of k, and Algorithm 1 receives k as input.
  • domain assumption Each loss l_t is convex and the true gradients satisfy max_t ||g_t|| <= G when G is known; in the unknown-G setting G exists but is not revealed.
    This is the standard OCO setup used in Sections 1 and 2. Convexity gives the standard regret identity, and the Lipschitz bound controls the clipping threshold.
  • standard math Standard convex-analysis facts are used without proof: convexity of Bregman divergences, Fenchel-Moreau, properties of the Lambert W function, and the online-to-batch conversion.
    These are cited from Orabona (2019), Bertsekas (2009), and other standard sources, and are used in the appendix proofs.
  • standard math The Huber regularizer bounds in Lemma B.1, restated from Zhang and Cutkosky 2022, are valid.
    The paper reproduces the lemma and gives a proof sketch, referring to the prior paper for details. It is a mathematical inequality, not a fitted quantity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Unconstrained Robust Online Convex Optimization." pith.science (2026). https://pith.science/paper/3GIY2XGO

@misc{pith2026250612781,
  author       = {Pith},
  title        = {Pith review of: Unconstrained Robust Online Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3GIY2XGO}},
  note         = {Machine review of arXiv:2506.12781}
}
abstract

This paper addresses online learning with ``corrupted'' feedback. Our learner is provided with potentially corrupted gradients $\tilde g_t$ instead of the ``true'' gradients $g_t$. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult ``unconstrained'' setting in which our algorithm must maintain low regret with respect to any comparison point $u \in \mathbb{R}^d$. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret $ \|u\|G (\sqrt{T} + k) $ when $G \ge \max_t \|g_t\|$ is known, where $k$ is a measure of the total amount of corruption. When $G$ is unknown we incur an extra additive penalty of $(\|u\|^2+G^2) k$.

Figures

Figures reproduced from arXiv: 2506.12781 by the authors.

Figure 1
Figure 1. KT-bettor with ℓ(w) = |w − 1| and comparator u = 1. (a)-(b): T = 400 and corruption happens during t ∈ [300, 319]. (c): Ratio between regrets with and without corruptions with various total corrupted rounds k ∈ [20, 30, 40, 50, 60, 70] and T = k 2 . and also: 1 G X T t=1 min (∥gt − g˜t∥, G) ≤ k (4) Intuitively, B denotes the rounds with a “large” amount of corruption. Notice that |B| ≤ min (kcount, kdeviation) and 1… view at source ↗
Figure 2
Figure 2. Comparison of Huber loss ft without scaling factor σt with p = 3, |wt| = 1, and |w| 2 . |w| 2 always grow faster than σt(w) far away from the origin. iterations in which ∥g˜t∥ ≥ ht. This mechanism is named as FILTER and is displayed as Algorithm 3 in Appendix F. Notice that ht only doubles if it is guaranteed that some gt satisfies ht ≤ ∥gt∥, so that ht ≤ O(G) always. Denote rounds where gradients are clipped as P¯ … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

49 extracted references · 44 canonical work pages

  1. [1]

    L., Rakhlin, A., and Tewari, A

    Abernethy, J., Bartlett, P. L., Rakhlin, A., and Tewari, A. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the nineteenth annual conference on computational learning theory, pp.\ 415--424, 2008

    work page 2008

  2. [2]

    Stochastic dueling bandits with adversarial corruption

    Agarwal, A., Agarwal, S., and Patil, P. Stochastic dueling bandits with adversarial corruption. In Algorithmic Learning Theory, pp.\ 217--248. PMLR, 2021

    work page 2021

  3. [3]

    Robust optimization, volume 28

    Ben-Tal, A., El Ghaoui, L., and Nemirovski, A. Robust optimization, volume 28. Princeton university press, 2009

    work page 2009

  4. [4]

    Oracle-based robust optimization via online learning

    Ben-Tal, A., Hazan, E., Koren, T., and Mannor, S. Oracle-based robust optimization via online learning. Operations Research, 63 0 (3): 0 628--638, 2015

    work page 2015

  5. [5]

    Convex optimization theory, volume 1

    Bertsekas, D. Convex optimization theory, volume 1. Athena Scientific, 2009

    work page 2009

  6. [6]

    J., Li, X., Ma, Y., and Wright, J

    Cand \`e s, E. J., Li, X., Ma, Y., and Wright, J. Robust principal component analysis? Journal of the ACM (JACM), 58 0 (3): 0 1--37, 2011

    work page 2011

  7. [7]

    Gradient descent: Robustness to adversarial corruption

    Chang, F.-C., Nabiei, F., Wu, P.-Y., Cioba, A., Vakili, S., and Bernacchia, A. Gradient descent: Robustness to adversarial corruption. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022

    work page 2022

  8. [8]

    Online and distribution-free robustness: Regression and contextual bandits with huber contamination

    Chen, S., Koehler, F., Moitra, A., and Yau, M. Online and distribution-free robustness: Regression and contextual bandits with huber contamination. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 684--695. IEEE, 2022

    work page 2021

Show all 49 references
  1. [9]

    I., Flammarion, N., and Bartlett, P

    Cherapanamjeri, Y., Aras, E., Tripuraneni, N., Jordan, M. I., Flammarion, N., and Bartlett, P. L. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.08137, 2020

    2007 arXiv

  2. [10]

    Cook, R. D. Detection of influential observation in linear regression. Technometrics, 42 0 (1): 0 65--68, 2000

    2000

  3. [11]

    Algorithms and Lower Bounds for Parameter-free Online Learning

    Cutkosky, A. Algorithms and Lower Bounds for Parameter-free Online Learning. PhD thesis, Stanford University, 2018

    2018

  4. [12]

    Artificial constraints and hints for unbounded online learning

    Cutkosky, A. Artificial constraints and hints for unbounded online learning. In Proceedings of the Thirty-Second Conference on Learning Theory, pp.\ 874--894, 2019

    2019

  5. [13]

    and Mhammedi, Z

    Cutkosky, A. and Mhammedi, Z. Fully unconstrained online learning. Advances in Neural Information Processing Systems, 2024

    2024

  6. [14]

    and Orabona, F

    Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pp.\ 1493--1529, 2018

    2018

  7. [15]

    Delibalta, I., Gokcesu, K., Simsek, M., Baruh, L., and Kozat, S. S. Online anomaly detection with nested trees. IEEE Signal Processing Letters, 23 0 (12): 0 1867--1871, 2016

    2016

  8. [16]

    and Kane, D

    Diakonikolas, I. and Kane, D. M. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911, 2019

    1911 arXiv

  9. [17]

    C., Shalev-Shwartz, S., Singer, Y., and Tewari, A

    Duchi, J. C., Shalev-Shwartz, S., Singer, Y., and Tewari, A. Composite objective mirror descent. In COLT, volume 10, pp.\ 14--26. Citeseer, 2010

    2010

  10. [18]

    Better algorithms for stochastic bandits with adversarial corruptions

    Gupta, A., Koren, T., and Talwar, K. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp.\ 1562--1578. PMLR, 2019

    2019

  11. [19]

    Huber, P. J. Robust statistics, volume 523. John Wiley & Sons, 2004

    2004

  12. [20]

    On optimal robustness to adversarial corruption in online decision problems

    Ito, S. On optimal robustness to adversarial corruption in online decision problems. Advances in Neural Information Processing Systems, 34: 0 7409--7420, 2021

    2021

  13. [21]

    and Cutkosky, A

    Jacobsen, A. and Cutkosky, A. Parameter-free mirror descent. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp.\ 4160--4211. PMLR, 2022. URL https://proceedings.mlr.press...

    2022

  14. [22]

    and Orabona, F

    Jun, K.-S. and Orabona, F. Parameter-free online convex optimization with sub-exponential noise. In Conference on Learning Theory, pp.\ 1802--1823. PMLR, 2019

    2019

  15. [23]

    K., and Meka, R

    Klivans, A., Kothari, P. K., and Meka, R. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pp.\ 1420--1430. PMLR, 2018

    2018

  16. [24]

    C., and Sidford, A

    Levy, D., Carmon, Y., Duchi, J. C., and Sidford, A. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33: 0 8847--8860, 2020

    2020

  17. [25]

    and Mendelson, S

    Lugosi, G. and Mendelson, S. Robust multivariate mean estimation: the optimality of trimmed mean. 2021

    2021

  18. [26]

    Stochastic bandits robust to adversarial corruptions

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

    2018

  19. [27]

    and Streeter, M

    Mcmahan, B. and Streeter, M. No-regret algorithms for unconstrained online convex optimization. In Advances in neural information processing systems, pp.\ 2402--2410, 2012

    2012

  20. [28]

    McMahan, H. B. and Orabona, F. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In COLT, pp.\ 1020--1039, 2014

    2014

  21. [29]

    and Koolen, W

    Mhammedi, Z. and Koolen, W. M. Lipschitz and comparator-norm adaptivity in online learning. Conference on Learning Theory, pp.\ 2858--2887, 2020

    2020

  22. [30]

    and Duchi, J

    Namkoong, H. and Duchi, J. C. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems, 29, 2016

    2016

  23. [31]

    Simultaneous model selection and optimization through parameter-free stochastic learning

    Orabona, F. Simultaneous model selection and optimization through parameter-free stochastic learning. In Advances in Neural Information Processing Systems, pp.\ 1116--1124, 2014

    2014

  24. [32]

    A modern introduction to online learning

    Orabona, F. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019

    1912 arXiv

  25. [33]

    and P \'a l, D

    Orabona, F. and P \'a l, D. Coin betting and parameter-free online learning. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29, pp.\ 577--585. Curran Associates, Inc., 2016

    2016

  26. [34]

    B., and Liang, P

    Oren, Y., Sagawa, S., Hashimoto, T. B., and Liang, P. Distributionally robust language modeling. arXiv preprint arXiv:1909.02060, 2019

    1909 arXiv

  27. [35]

    An online method for a class of distributionally robust optimization with non-convex objectives

    Qi, Q., Guo, Z., Xu, Y., Jin, R., and Yang, T. An online method for a class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34: 0 10067--10080, 2021

    2021

  28. [36]

    M., Horn, C., Silva, J., and Marcia, R

    Raginsky, M., Willett, R. M., Horn, C., Silva, J., and Marcia, R. F. Sequential anomaly detection in the presence of noise and limited feedback. IEEE Transactions on Information Theory, 58 0 (8): 0 5544--5562, 2012

    2012

  29. [37]

    W., Hashimoto, T

    Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911.08731, 2019

    1911 arXiv

  30. [38]

    and Narayanaswamy, B

    Sankararaman, A. and Narayanaswamy, B. Online robust non-stationary estimation. Advances in Neural Information Processing Systems, 36, 2024

    2024

  31. [39]

    Y., and Song, Z

    Sankararaman, A., Narayanaswamy, B., Singh, V. Y., and Song, Z. Fitness:(fine tune on new and similar samples) to detect anomalies in streams with drift and outliers. In International Conference on Machine Learning, pp.\ 19153--19177. PMLR, 2022

    2022

  32. [40]

    Thode, H. C. Testing for normality. CRC press, 2002

    2002

  33. [41]

    User-specified local differential privacy in unconstrained adaptive online learning

    van der Hoeven, D. User-specified local differential privacy in unconstrained adaptive online learning. In Advances in Neural Information Processing Systems, pp.\ 14103--14112, 2019

    2019

  34. [42]

    M., and Kotlowski, W

    van Erven, T., Sachs, S., Koolen, W. M., and Kotlowski, W. Robust online convex optimization in the presence of outliers. In Conference on Learning Theory, pp.\ 4174--4194. PMLR, 2021

    2021

  35. [43]

    M., Pham, H., Dong, X., Du, N., Liu, H., Lu, Y., Liang, P

    Xie, S. M., Pham, H., Dong, X., Du, N., Liu, H., Lu, Y., Liang, P. S., Le, Q. V., Ma, T., and Yu, A. W. Doremi: Optimizing data mixtures speeds up language model pretraining. Advances in Neural Information Processing Systems, 36, 2023

    2023

  36. [44]

    and Cutkosky, A

    Zhang, J. and Cutkosky, A. Parameter-free regret in high probability with heavy tails. Advances in Neural Information Processing Systems, 35: 0 8000--8012, 2022

    2022

  37. [45]

    Pde-based optimal strategy for unconstrained online learning

    Zhang, Z., Cutkosky, A., and Paschalidis, I. Pde-based optimal strategy for unconstrained online learning. In International Conference on Machine Learning, pp.\ 26085--26115. PMLR, 2022

    2022

  38. [46]

    Zhang, Z., Yang, H., Cutkosky, A., and Paschalidis, I. C. Improving adaptive online learning using refined discretization. In International Conference on Algorithmic Learning Theory, pp.\ 1208--1233. PMLR, 2024

    2024

  39. [47]

    and Paffenroth, R

    Zhou, C. and Paffenroth, R. C. Anomaly detection with robust deep autoencoders. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp.\ 665--674, 2017

    2017

  40. [48]

    Online convex programming and generalized infinitesimal gradient ascent

    Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp.\ 928--936, 2003

    2003

  41. [49]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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