Pith Number

pith:VWHAPZQE

pith:2026:VWHAPZQEUJIFUGXY3J2ZRWPDL3

not attested not anchored not stored refs resolved

Polyhedral Instability Governs Regret in Online Learning

Basel Alomair, Bhaskar Ramasubramanian, Fengqing Jiang, Kaiyuan Zheng, Linda Bushnell, Luyao Niu, Radha Poovendran, Yichen Feng, Yuetai Li

Regret in online learning over combinatorial actions scales with the square root of the number of polyhedral region switches.

arxiv:2605.13692 v1 · 2026-05-13 · cs.LG · cs.CC

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{VWHAPZQEUJIFUGXY3J2ZRWPDL3}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

Under full information feedback and fixed partition assumptions, Regret_T = Θ(√((1+RS_T) T log V_max)) where RS_T is the number of region switches and V_max the maximum vertices per region.

C2weakest assumption

The fixed partition assumptions together with full information feedback that keep the polyhedral structure stable enough for the region-switch counting argument to apply.

C3one line summary

Regret in polyhedral online convex optimization equals Θ(√((1+RS_T) T log V_max)) where RS_T counts active region switches.

References

19 extracted · 19 resolved · 0 Pith anchors

[1] Bartlett, Alexander Rakhlin, and Ambuj Tewari 2008

[2] Regret in online combinatorial optimization.Mathematics of Operations Research, 39(1):31–45, 2014 2014 · doi:10.1287/moor

[3] Adaptively tracking the best bandit arm with an unknown number of distribution changes 2019

[4] Learning with submodular functions: A convex optimization perspective 2013

[5] Combinatorial bandits.Journal of Computer and System Sciences, 78(5):1404–1422, 2012 2012 · doi:10.1016/j.jcss.2012.01.001

Receipt and verification

First computed	2026-05-18T02:44:16.937093Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

ad8e07e604a2505a1af8da7598d9e35ee93b46a005f80a9820847bae41e2582a

Aliases

arxiv: 2605.13692 · arxiv_version: 2605.13692v1 · doi: 10.48550/arxiv.2605.13692 · pith_short_12: VWHAPZQEUJIF · pith_short_16: VWHAPZQEUJIFUGXY · pith_short_8: VWHAPZQE

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/VWHAPZQEUJIFUGXY3J2ZRWPDL3 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: ad8e07e604a2505a1af8da7598d9e35ee93b46a005f80a9820847bae41e2582a

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "2bd5c554aaed882da16bc7c405b6f38fcf0fe19e6f5d38538647c457e94923a4",
    "cross_cats_sorted": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.LG",
    "submitted_at": "2026-05-13T15:45:44Z",
    "title_canon_sha256": "2512ee722e47d0a2da1d88542986a6fd89094c0a96bcc67bf7ebed7486cd980c"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13692",
    "kind": "arxiv",
    "version": 1
  }
}