arXiv:2605.13692v1 [cs.LG] 13 May 2026
Polyhedral Instability Governs Regret in Online Learning
Yuetai Li♣ Fengqing Jiang♣ Yichen Feng♣ Kaiyuan Zheng♣ Basel Alomair♠♣♡ Luyao Niu♣ Bhaskar Ramasubramanian ♢ Linda Bushnell♣ Radha Poovendran♣ ♣ University of Washington ♢ Western Washington University ♠ King Abdulaziz City for Science and Technology ♡ HUMAIN [email protected]
Abstract Many online decision problems over combinatorial actions are addressed via convex relaxations, leading to online convex optimization with piecewise linear objectives and induced polyhedral structure. We show that regret in such problems is governed by polyhedral instability: the number of changes of the active region. Under full information feedback and fixed partition assumptions, if RST denotes the number of region switchesp and Vmax the maximum number of vertices per region, we prove RegT = Θ( (1 + RST ) T log Vmax ) interpolating between experts-like and dimension-dependent OCO rates. For online submodular–concave games under Lovász convexification, this reduces p to the permutation-switch count SCT , yielding the matching rate RegT = Θ( (1 + SCT ) T log n). Experiments on synthetic and real combinatorial problems (shortest path, influence maximization) validate the predicted scaling and indicate that low-instability regimes can arise in practice without explicit enumeration of actions.
1
Introduction
Many online decision problems require a learner to repeatedly choose a combinatorial action while the environment changes over time. A network operator may need to reroute traffic as link conditions change, a public-health planner may need to reposition sensors as risk patterns shift, and a platform may need to choose seed sets as user behavior evolves. In all of these settings, in each round the learner must act before seeing the next round’s outcome. The learner’s performance is measured by regret: the cumulative gap between the learner’s realized loss and that of an appropriate benchmark policy, such as the best fixed action or the round-wise optimum selected in hindsight. These problems are often computationally challenging because the number of feasible actions can be exponential in the problem size. A widely used solution is to replace the discrete decision set by a continuous convex relaxation, enabling optimization in a space whose dimension grows only polynomial with problem size. In many such relaxations, the resulting objective is piecewise linear: the relaxation domain is partitioned into a fixed collection of polyhedral regions, and the objective is linear within each region. However, it remains unclear which structural property of the induced polyhedral partition can explain when regret exhibits experts-like behavior [8, 14], and when it instead follows the dimension-dependent rates of generic online convex optimization (OCO) [9, 19]. In this paper, we study polyhedral instability: the number of rounds on which the active polyhedral region changes. When the learner remains in a single region, the problem reduces to an experts-like task over a small local set of vertices rather than a generic high-dimensional continuous problem. When the learner frequently crosses region boundaries, the local linear model changes repeatedly, Preprint. Under review.
Unstable regime Pπ2
x2
x2
Pπ2 Pπ1
Pπ1
Average regret
Stable regime
100
C (1+SCT)logn/T C n/T OLMDA CAMW
n
10 1
x1
x1
Long motion, no boundary crossing
Short motion, many crossings
101 100 logn
102 103 1 + SCT
104
Figure 1: The key distinction is not how far the learner moves, but whether it crosses region boundaries. Left: motion inside one region keeps the same local linear model. Center: repeated boundary crossings keep changing the effective local problem. Right: the experiments reflect this transition between stable and unstable regimes (Section 5). and the advantage of the polyhedral structure diminishes. Under fixed-partition and full-information assumptions, we show regret bounds that interpolate between these two regimes: experts-like rates under low instability, and ambient-dimension-dependent rates under high instability. The key message is that the difficulty of polyhedral online learning is not determined by ambient dimension alone. Two instances with the same dimension can have very different regret complexity depending on how often the active region changes. This perspective also helps explain empirical behavior that standard theory does not capture: some large combinatorial problems behave surprisingly like small experts problems, while others do not. Because polyhedral partitions arise in many combinatorial relaxations, this viewpoint applies broadly, including to the Lovász extension for submodular optimization [4, 15, 10] and other relaxations built from polyhedra [16]. As a concrete and practically important instance, we specialize polyhedral instability to online submodular–concave games under Lovász convexification. In this setting, instability corresponds to the number of times the active Lovász cell changes, equivalently the number of equilibrium permutation switches. This viewpoint also leads to a practical algorithm: use multiplicative-weightsstyle learning inside one cell, and only restart or transfer information when the active cell changes. The resulting algorithms are simple, interpretable, and directly tied to the geometry of the problem. To summarize, this paper makes the following contributions. • We identify polyhedral instability as a structural feature that yields instability-parameterized regret bounds for online learning with piecewise-linear objectives under fixed-partition assumptions. We show how this applies both to fixed polyhedral partitions and to the specific case of Lovász convexification for submodular–concave games. • We design region-aware multiplicative-weights algorithms that exploit stable geometric regimes rather than treating the objective as a generic black-box convex loss. • We validate the predicted scaling on controlled synthetic games and provide preliminary evidence on shortest-path and influence-maximization tasks that low-instability regimes can arise beyond designed instances.
2
Problem Setup and Preliminary Background
Online Learning Setup. We study online learning over T rounds for combinatorial problems whose convex relaxation induces a fixed polyhedral partition. At each round t, the learner chooses a decision in the relaxation, the environment reveals the round-t objective, and performance is measured by regret against the appropriate round-wise optimal comparator. Submodular–Concave Games. One can instantiate an online learning problem with the submodular–concave game model. Let [n] = {1, . . . , n}. A submodular-concave game consists of a ground set [n], a compact convex set Y ⊆ Rm , and a payoff function f : 2[n] × Y → R such that f (·, y) is submodular for every y ∈ Y and f (S, ·) is concave for every subset S ⊆ [n]. 2
Lovász Extension.
For x ∈ [0, 1]n sorted as xπ(1) ≥ · · · ≥ xπ(n) , the Lovász extension is fL (x, y) =
n X (xπ(i) − xπ(i+1) ) f (Ci , y),
(1)
i=0
where Ci = {π(1), . . . , π(i)}. If f (·, y) is submodular, then fL (·, y) is convex and minx fL (x, y) = minS f (S, y) [15]. The mixed minimax value equals V ⋆ := minx∈[0,1]n maxy∈Y fL (x, y); optimal mixed strategies are supported on chains of at most n+1 nested subsets (Theorem A.3 in Section A.2). For each permutation π of [n], the corresponding Lovász cell is the region Pπ = {x ∈ [0, 1]n : xπ(1) ≥ · · · ≥ xπ(n) }, so the cube is partitioned into Lovász cells indexed by coordinate orderings, and fL (·, y) is linear on each such cell. Online protocol. At each round t = 1, . . . , T : the learner selects (xt , yt ) ∈ [0, 1]n × Y; nature reveals ft ; the learner incurs the saddle-point regret: RegT =
T X t fL (xt , yt⋆ ) − fLt (x⋆t , yt ) ,
(2)
t=1
where (x⋆t , yt⋆ ) is a saddle point of the round-t game, i.e., fLt (x⋆t , y) ≤ fLt (x⋆t , yt⋆ ) ≤ fLt (x, yt⋆ ) ∀x, y. We call (2) dynamic saddle-point regret, as the comparator (x⋆t , yt⋆ ) varies with t. It measures how much the learner loses relative to the roundwise equilibrium sequence, rather than to one fixed hindsight decision. The stability quantities below are therefore structural assumptions on the game sequence induced by these equilibria, not choices made by the learner after the fact. When the equilibrium sequence changes cells frequently, the bound recovers dimension-dependent behavior; when it remains in few cells, the bound captures the easier dynamic comparator path. Assumption 2.1. Let gtx := ∇x fLt (xt , yt ) and gty := ∇y fLt (xt , yt ) denote the gradients at round t. There exist Lx , Ly , M > 0 with ∥gtx ∥2 ≤ Lx , ∥gty ∥2 ≤ Ly , |f t (S, y)| ≤ M for all t, S, y. Additional structural background and assumption scaling are presented in Appendix A.
3
Permutation Stability Governs Regret
This section instantiates polyhedral instability for submodular–concave games under Lovász convexification. We analyze how the equilibrium cell sequence enters regret bounds for these games. Our analysis follows two stages. We start with an oracle version which knows the equilibrium permutation. Next, we develop a proxy algorithm to remove the oracle by using an observable best-response permutation. Section 4 lifts this principle to arbitrary polyhedral partitions. 3.1
Permutation Switches Drive Regret
The Lovász extension is linear on each Lovász cell [4, 15], with gradient determined by the nested chain Ci = {π(1), . . . , π(i)}. For x ∈ [0, 1]n , let π denote the permutation that sorts x in descending order, so that x ∈ Pπ . If the equilibrium remains in a single cell Pπ throughout the horizon, then the minimizer of minx maxy fLt (x, y) is effectively solving an experts problem over only thep n+1 chain vertices {1Ci }ni=0 of that cell, and multiplicative weights over those vertices attains the O( log n/T ) rate [8, 14]. A challenge arises when equilibrium crosses cell boundaries, since each crossing changes the local linear model, the associated chain, and hence the induced experts problem. We quantify this complexity through the number of equilibrium cell changes. Definition 3.1 (Permutation-switch count). Let x⋆t = arg minx maxy fLt (x, y) be a minimax equilibrium at round t, and let πx⋆t be the permutation that sorts x⋆t . The permutation-switch count is SCT := t ∈ [T −1] : πx⋆t+1 ̸= πx⋆t . (3) SCT is an intrinsic property of the game sequence and does not depend on the learner’s actions. In influence maximization, it corresponds to changes in the ranking of nodes by marginal influence; in sensor placement, it measures changes in the ordering of marginal coverage gains. 3
Relation to Existing Adaptive Measures. Existing adaptive measures emphasize different phenomena. Path length and gradual-variation measures track Euclidean motion or temporal drift in the losses [6, 18], while shifting-expert bounds count changes of the best comparator in a fixed expert class [12]. In contrast, here the relevant expert class itself changes when the equilibrium crosses a Lovász cell boundary. Thus SCT captures a distinct form of combinatorial instability and is incomparable with path length, gradient variation, and classical switching counts. Formal separations and related structural properties are in Appendix E. 3.2
Oracle Reference: Cell-Aware Multiplicative Weights
We next show SCT controls regret. We first analyze an oracle version of Cell-Aware Multiplicative Weights (CAMW) that is revealed the equilibrium permutation πx⋆t at each round. This result should be interpreted as a diagnostic benchmark: SCT is an intrinsic but generally inaccessible property of the comparator sequence. Whenever the equilibrium permutation remains fixed, the minimizer faces a static experts problem over the associated n + 1 chain vertices, for which multiplicative weights is sufficient. When the permutation changes, CAMW restarts on the new chain. Consequently, the horizon decomposes into SCT + 1 epochs, each corresponding to a single Lovász cell. Theorem 3.2 (Cell-stability-adaptive regret). Let DY denote the Bregman diameter of Y. Under Assumption 2.1, CAMW with mirror ascent for the maximizer of minx maxy fLt (x, y) achieves: ! r 1 (1 + SCT ) · log n Ly DY (4) RegT ≤ O + √ . T T T Theorem 3.2 shows that regret scales with the number of Lovász cells visited, not with the full dimension of [0, 1]n . The proof and supporting lemmas are given in Appendix C. p Corollary 3.3 (Extreme regimes). When SCT = 0, Theorem 3.2 recovers O( log n/T ). When SCT = O(n/ log n) p (maximally unstable), it recovers the rate of Online Lovász Mirror DescentAscent (OLMDA) O( n/T ). 3.3
Boundary-Aware Implementation
The oracle reference is typically unavailable to the learner and is not used by the implementable algorithm. To obtain an online method, we replace the inaccessible equilibrium permutation with an observable best-response permutation. This keeps the same high-level logic as the oracle proof while grounding the switches in quantities the learner can compute online. Cold-start CAMW, which restarts MW whenever the observed cell changes, is the core method behind the worst-case rate. We also consider a warm-start refinement motivated by the substantial overlap between adjacent Lovász cells’ chain structures. Under an adjacent transposition, only a local portion of the chain changes, while most chain elements remain unchanged. We develop geometric CAMW (Algorithm 1) that exploits this overlap through chain-overlap transfer: when the observed permutation changes, the algorithm retains weight of shared chain elements and assigns fresh mass only to genuinely new ones. The transfer parameter α acts as a probability floor: every new-chain expert receives at least α/(n+1) mass, which preserves the MW initialization guarantee, while inherited mass improves constants when consecutive chains overlap. Implementation details, the OLMDA baseline, and the chain-overlap transfer guarantee are given in Appendix B. Theorem 3.4 (Geometric WS-CAMW). Under Assumption 2.1, Algorithm 1 achieves: s c T ) · log n 1 (1 + SC y DY + L√ RegT ≤ O , T T T
(5)
c T = |{t : π BR ̸= πtBR }| is the observed best-response switch count. where SC t+1 c T . Recovering the This is an online, parameter-free bound with respect to the observed count SC oracle rate in terms of SCT additionally requires the tracking/gap condition stated in Appendix E.2; c T can be larger than SCT . without such separation, SC 4
Algorithm 1 Geometric CAMW Require: Step sizes ηx , ηy > 0; transfer parameter α ∈ (0, 1); initial y1 ∈ Y 1: Initialize MW: p1 = (1/(n+1), . . . , 1/(n+1)); π0 ← id 2: for t = 1, . . . , T do 3: πt ← πtBR (yt ) 4: if πt ̸= πt−1 then π 5: S ← {j : Cjπt = Cj t−1 } α α 6: Transfer: pt,j ← (1−α) pt−1,j + n+1 for j ∈ S; pt,j ← n+1 for j ∈ /S 7: Normalize: pt ← pt /∥pt ∥1 8: end if P 9: xt,πt (j) = i≥j pt,i ; play (xt , yt ); observe ft 10: MW update: pt+1,i ∝ pt,i exp(−ηx ft (Ciπt , yt )) 11: Mirror ascent: yt+1 = arg maxy∈Y {⟨∇y fLt (xt , yt ), y⟩ − η1y Dφ (y, yt )} 12: end for
4
Lower Bounds and the Polyhedral Principle
This section gives matching lower-bound evidence for the SCT dependence and then states the corresponding fixed-partition polyhedral result. The broader result is limited to the full-information, fixed finite partition model made explicit below. 4.1
Cell Transitions Force Unavoidable Regret
We next show that the SCT term cannot be removed in the worst case. Any prescribed switch count can be encoded by an adversary into a submodular–concave game that forces matching regret. The construction partitions the horizon into SCT + 1 epochs separated by permutation shifts. At a high level, the adversary splits time into s+1 epochs, selects a different Lovász cell for each epoch, and places independent Rademacher expert losses on the chain vertices inside that cell. Each epoch therefore contains a freshp experts lower-bound instance, and summing the epoch lower bounds gives P p Ω( j Tj log n) = Ω( (s+1)T log n) by Cauchy–Schwarz. Theorem 4.1 (SCT -dependent lower bound). For any s ∈ {0, . . . , T −1} and n ≥ 3, there exists a sequence of submodular–concave games with SCT = s such that T1 E[RegT ] ≥ p Ω (1 + s) log n / T . The full lower-bound construction and the proof are given in Appendix D. Corollary 4.2 (Matching p switch-dependent rate). Combining Theorems 3.2 and 4.1: RegT = Θ (1 + SCT ) T log n . Theorem p4.2 shows that stability is both sufficient and necessary for improved rates. The worstcase Ω( n/T ) lower bound is recovered when SCT = Θ(n/ log n), via reduction to online linear optimization with Rademacher losses [1]. 4.2
General Polyhedral Principle
We now state the fixed-partition polyhedral analogue. This setting covers several applications with finite polyhedral cells, but it does not cover time-varying partitions, smooth relaxations, bandit feedback, or cases where the active region cannot be identified under the stated feedback model. Examples include online shortest-path on a DAG with N paths over d edges (each path defines a vertex of the path polytope), online min-cost flow with d arcs and Vmax basic feasible solutions, and structured prediction over label polytopes. In each case, the decision space X ⊂ Rd partitions into polyhedral regions {Rk }K k=1 with losses linear on each region. Define the region-switch count RST := |{t : R(x⋆t ) ̸= R(x⋆t+1 )}| and Vmax := maxk |V (Rk )|. We bound the regret for polyhedral OCO as follows. Theorem 4.3 (Regret for fixed polyhedral partitions). Consider full-information piecewise-linear losses partition. Suppose Assumption 2.1 holds, then RegT = p over a fixed finite polyhedral Θ (1 + RST ) T log Vmax . 5
Phase transition: theory predicts data k = 5 (N = 70) k = 6 (N = 252) k = 8 (N = 3, 432) k = 10 (N = 48, 620)
Average regret 1T RegT
101
k = 12 (N = 705, 432) MW-Restarts OGD-FW C (1+RST)logN/T
100
10 1
101
100
102
1 + RST Figurep 2: Phase transition (Theorem 4.5), validated on shortest-path games. Solid lines: theoretical rate C (1+RST ) log N/T , fitted per grid size. Circles: MW-with-restarts regret tracks the theory across five grid sizes (k = 5 to 12, up to N = 705,432 paths). Crosses: OGD-FW regret. Vertical dotted lines mark the predicted crossover RS⋆T = d/ log N for each k; at high RST , OGD becomes competitive, confirming the phase transition.
Remark 4.4. In the ideal full-information model of Theorem 4.3, the regret analysis runs MW over the vertices of the active region and uses only bounded losses and the number of available local vertices. Facet angles, adjacency graph geometry, and conditioning can affect region detection, computational cost and numerical stability, but they are not needed for the regret bound in Theorem 4.3. Extending the theorem to noisy detection, time-varying partitions, or computationally constrained region identification may require such geometric quantities. 4.3
Unify the Experts and OCO Regimes
We compare the fixed-partition MW rate with the usual dimension-dependent OCO rate. When region switches are rare, MW over active-region vertices can be preferable; when switches are frequent, continuous methods can dominate. Theorem 4.5. For piecewise-linear losses over a fixed polyhedral partition with Vmax vertices per region in Rd : (r r )! (1+RST ) log Vmax d 1 ⋆ RegT (RST ) = Θ min , , (6) T T T with crossover at RS⋆T = d/ log Vmax . √ √ This connects the experts regime ( T log N ) and OCO regime ( dT ) through region-switch complexity under the assumptions of Theorem 4.3. Below the threshold, MW-with-restarts over region vertices is optimal; above it, continuous first-order methods dominate. For Lovász convexification (d = n, Vmax = n+1), the threshold is RS⋆T ≈ n/ log n. Theorem 4.3 applies to the fixed-partition full-information piecewise-linear losses described above, not just Lovász convexifications. We have two immediate corollaries: (a) online shortest-path on a p DAG with d edges and N paths gives tight regret Θ( (1+RS p T ) T log N ); (b) online min-cost flow with d arcs and Vmax basic feasible solutions gives Θ( (1+RST ) T log Vmax ) under RST basis pivots. In both cases RST captures combinatorial instability rather than Euclidean displacement (Appendix E.4). We validate the shortest-path instance experimentally in Section 5. Taken together, the region-switch count gives a concise interpolation parameter in this fixed-partition model.
5
Experiments
We evaluate whether instability measures identified by the theory predict empirical regret in structured online-learning problems. The experiments span Lovász games, online shortest-path on grid DAGs, and influence maximization on SNAP networks. Synthetic sweeps are controlled scaling checks rather than evidence by themselves of universality; real-data experiments are intended as preliminary 6
evidence that low-instability regimes can arise outside designed instances. Additional experiments, ablations, revision-time diagnostics, and implementation details appear in Section F. 5.1
Experimental Setup
Datasets and domains.
We use three experimental domains.
• Lovász games with controlled permutation-switch counts, using a stability sweep at n = 20, T = 10,000, and SCT ∈ {0, 1, 5, 20, 50, 200, 1,000, 5,000, 9,999}, together with a separate dimension-scaling study with n ∈ {10, 20, 50, 100, 200, 500, 1,000} and SCT = 0. Appendix F.2 reports additional Lovász diagnostics for warm starts, baseline comparisons, oracle robustness, and switch detection. • Online shortest-path on k × k grid DAGs with up to N = 705,432 source-to-sink paths and T = 50,000 rounds. • Four SNAP influence-maximization networks: Karate Club, Email-Eu, Wiki-Vote, and Epinions, with n up to 2,744 and T up to 20,000. Baselines. We compare CAMW and geometric WS-CAMW against OLMDA, OGD for Lovász games, OGD-FW for shortest-path, Fixed-Share MW [12], SAOL, and ZO-EG [7]. These baselines cover continuous OCO, structure-agnostic experts-style methods, and a strongly-adaptive regret comparator, while keeping the comparison aligned with each domain’s native optimization geometry. The choice of continuous baseline depends on the geometry of the feasible set. In the Lovász experiments, the minimizer acts directly on the cube [0, 1]n , so Euclidean projection is trivial and √ plain OGD is the natural ambient-dimension baseline for testing the predicted n dependence. In shortest-path, by contrast, the continuous relaxation is the path/flow polytope over graph edges; exact Euclidean projection onto this polytope at every round is substantially more involved. Step sizes follow the choices summarized in Section F.1, unless an appendix ablation states otherwise. Metrics.
We use three metrics to validate polyhedral instability:
• Per-round regret. Our primary performance metric is the per-round saddle-point regret 1 T RegT , where RegT is defined in Eq. (2). • Theory-normalized regret. To test per-round regret rate predicted by Theorems 3.2 and 4.5, we divide R̄T by the appropriate theoretical rate. For structure-aware methods we report R̄T R̄Tstruct := p , (1 + κT ) log Veff /T where κT is the relevant instability count and Veff is the effective vertex count (Veff = n for Lovász games and SNAP, Veff = N for shortest-path). For continuous baselines we report R̄T , R̄Tcont := p deff /T where deff is the ambient dimension of the continuous relaxation (deff = n in Lovász games, deff = d in shortest-path). c T , SCBR , RST } be the structural quantity driving • Instability statistic. Let κT ∈ {SCT , SC T regret, with BR c T = {t ∈ [T −1] : πt+1 SC ̸= πtBR }
SCT = {t ∈ [T −1] : πx⋆t+1 ̸= πx⋆t } , BR SCBR et+1 ̸= π etBR } T = {t ∈ [T − 1] : π
RST = {t ∈ [T −1] : R(x⋆t+1 ) ̸= R(x⋆t )} ,
where π etBR is the offline best-response permutation recomputed from logged iterate yt . 5.2
Experimental Results
Finding 1: regret grows with instability, not withpelapsed time alone. From Figure 3a, the stability sweep over SCT is consistent with the (1 + SCT ) log n/T scaling from Theorem 3.2. CAMW’s absolute regret increases sublinearly with instability, while regret normalized by 7
10 1 101
1 + SCT
103
20 15 10 5 0
C n/T
C (1+SCT)logn/T
(b) Collapse plot
101
1 + SCT
CAMW (ours)
103 102
CAMW (ours) (obs) CAMW (ours) (BR) CAMW-no-restart (ours) (obs) CAMW-no-restart (ours) (BR) y=x
101 100
103
OLMDA
(c) SCT tracking
104
Measured SCT
100
Regret / (1+SCT)logn/T
Average regret
(a) Regret vs SCT
101
103
Designed SCT
OGD
CAMW-no-restart (ours)
p (a) Stability sweep. Left: CAMW interpolates from O( log n/T ) toward the dimension-dependent regime. Center: controlled scaling check under theory normalization. Right: online SCT tracking on designed instances.
(b) Normalized by n/T
20
Min. regret / n/T
Min. regret / logn/T
(a) Normalized by logn/T 15 10 5 0
10
100
n
CAMW (ours)
2.0 1.5 1.0 0.5 0.0
1000
CAMW-no-restart (ours)
10
100
n
OLMDA
1000
OGD
(b) Dimension scaling (SCT = 0, T = 20,000, 5 seeds, n ∈ {10, 20, 50, 100, 200, 500, 1,000}). Synthetic instances are normalized to unit loss range. Left: CAMW’s minimizer regret is flat when normalized by p p √ log n/T (CV = 0.12), confirming log n scaling. Right: OGD is flat when normalized by n/T (CV √ = 0.15); OLMDA grows super-linearly, confirming n scaling for both baselines.
Figure 3: Synthetic experiments confirm the (ours) is shown in blue.
p (1+SCT ) log n/T scaling of Theorem 3.2. CAMW
p
(1 + SCT ) log n/T stays nearly constant in the center panel. The left panel gives a log-log slope of 0.54 for absolute regret against 1 + SCT , close to the theoretical exponent 0.5, and the right panel shows that tracked switch counts match the prescribed instability level. Together these plots identify cell changes, rather than elapsed time alone, as the quantity predicting difficulty in the Lovász setting.
√ √ Finding 2: stable polyhedral structure yields a log n dependence instead of n. As shown in Figure 3b, CAMW’s absolute regret grows much morep slowly than the continuous baselines in the stable regime. The left panel shows CAMW divided by log n/T p staying nearly flat with coefficient of variation 0.12, while the right panel shows OGD divided by n/T staying flat with coefficient of variation 0.15. At n = 1,000, the plotted gap between CAMW and the continuous baselines exceeds an order of magnitude. These curves empirically separate the experts-like and continuous-regret regimes predicted by the theory. Finding 3: fixed-partition instability model is consistent with shortest-path behavior. As shown in Figure 4, online shortest-path on k × k grid DAGs follows the same instability-based pattern. MW-with-restarts has absolute regret that grows with RST , while normalized regret stays stable, with log-log slope 0.44 for the unnormalized curve in Fig. 4. Fig. 4 also shows OGD-FW degrading more rapidly as RST increases, with plotted crossover thresholds following the prediction RS⋆T = d/ log N . The appendix crossover plot, Figure 12 in Section F.10, gives a secondary ratio-based summary of the same shortest-path experiment. Thus the main shortest-path figure provides evidence that the same fixed-partition instability model can be informative beyond Lovász games. Finding 4: the tested SNAP influence-maximization instances show low observed instability. As shown in Figure 13 in Section F.11, the tested SNAP influence-maximization instances remain in 8
Average regret
k = 5 (N = 70) 100
slope=0.45
k = 6 (N = 252) 100
slope=0.44
101
k = 8 (N = 3, 432) slope=0.44
101
k = 10 (N = 48, 620) slope=0.44
k = 12 (N = 705, 432) 101
10 1
100
10 1
100
100
10 2
10 1
10 2
10 1
10 1
10 3
10 2
10 3
10 2
10 2
10 3
10 3
10 4
101
1 + RST
10 4
101
101
1 + RST MW-Restarts
OGD-FW
10 3 101
1 + RST
slope=0.44
1 + RST
101
1 + RST
FixedShare(1/T)
Figure 4: Online shortest-path on grid DAGs (T = 50,000, 10 seeds). Five grid sizes from kp = 5 (N = 70) to k = 12 (N = 705,432). MW-with-restarts (blue) tracks the theoretical C (1+RST ) log N/T rate (light blue band) with log-log slope ≈ 0.44; OGD-FW (green) degrades with RST . Crossover threshold RS⋆T = d/ log N shifts rightward for smaller k (dotted vertical lines).
a low-instability regime. Figure 13 shows the observed best-response switch counts staying small, c T ∈ {4, 5, 6}, which is less than 0.3% of the horizon. The same figure shows that when with SC T /n ≈ 1, OLMDA is often the strongest baseline even though the switch counts remain essentially fixed, indicating that the differences across networks are better explained by the phase transition in T /n than by growing instability. Finding 5: exploiting overlap between nearby cells improves constants in practice. As shown in Figure 14 in Appendix F.11, WS-CAMW achieves 2–3× lower absolute regret than cold-start CAMW on the extended SNAP experiments. The figure therefore supports a constant-factor improvement from transferring weight across adjacent cells, rather than a change in the minimax dependence on SCT . This makes the gain practical rather than asymptotic, consistent with the geometric motivation behind chain-overlap transfer. Finding 6: revision diagnostics support the warm-start and tracking mechanisms. Appendix F.2 reports targeted checks not shown in main-paper figures. In the transfer-floor sweep, cold CAMW has mean regret 0.0633, WS-CAMW improves to 0.0600–0.0610, and Geometric-WS-CAMW improves to 0.0440–0.0528. The SAOL baseline was not competitive in tested Lovász regimes. Noise stress tests show that warm-start variants absorb oracle noise much better than cold CAMW, while deterministic switch-detection validation shows near-perfect event detection in the tested regime. These results are used as mechanism diagnostics rather than new headline empirical claims. Additional results. Appendix F contains additional experimental results, including full hyperparameter and compute details, revision-time diagnostics for warm starts and switch tracking, additional real-data domains for sensor placement and feature selection, ablations of restart rules, tracking variants, step sizes, zeroth-order baselines, and wall-clock scaling, plus extended shortest-path, SNAP, and dimension-scaling plots.
6
Conclusion
This paper studied polyhedral instability: the number of changes of the active polyhedral region as a structural parameter governing regret in online learning with piecewise linear objectives. For fixed finite polyhedral partitions under full-information and bounded-loss assumptions, we established p the rate RegT = Θ( (1+RST ) T log Vmax ) with a phase transition at RS⋆T = d/ log Vmax . For Lovász games, p this reduces to the permutation-switch count SCT , yielding the oracle benchmark RegT = Θ( (1+SCT ) T log n) and an implementable boundary-aware algorithm controlled by the c T . Our results show that regret is governed by active-region instability rather than observable count SC ambient dimension alone: stable instances admit experts-like rates, while frequent region changes recover classical dimension-dependent behavior. Experiments on synthetic and real combinatorial problems support the predicted scaling and suggest that low-instability regimes can arise in practice. 9
Limitations This work studies regret through the lens of polyhedral instability under fixed-partition and fullinformation assumptions. These assumptions make the geometry transparent, but they also limit the direct applicability of the theory to settings with changing partitions, partial feedback, noisy observations, or approximate optimization oracles. The empirical results support the predicted scaling in controlled and preliminary real-data settings, but they should not be interpreted as evidence that low-instability behavior is universal across all combinatorial online-learning problems. A further limitation is that the practical algorithms rely on detecting or approximating active-region changes; in large-scale deployments, this detection step may introduce computational overhead or additional approximation error.
Ethical Statement This paper is primarily theoretical and methodological. It does not introduce a deployed system, collect new human-subject data, or make decisions about individuals that may raise ethical concerns.
Broader Impact By identifying polyhedral instability as a predictor of regret, this work may help make large-scale online combinatorial decision problems more computationally tractable and interpretable. The results suggest that some problems with exponentially many actions can behave like much smaller learning problems when their active geometric structure is stable. This could benefit applications such as network routing, monitoring, resource allocation, and influence modeling. At the same time, improved online decision methods can also be used in high-stakes or manipulative settings, especially when applied to recommendation, targeting, or information-spread problems. The broader impact therefore depends on careful application-specific governance, transparent evaluation, and safeguards against harmful optimization objectives.
LLM Usage We used large language models (LLMs) to support the preparation of this manuscript, including assistance with writing, editing, and improving clarity of presentation. LLMs were also used to support experimental workflows, such as drafting code, checking implementation details, and organizing analysis. All intellectual contributions, methodological decisions, experimental design, results interpretation, and final manuscript content were reviewed and verified by the authors, who take full responsibility for the accuracy and integrity of the work.
10
References [1] Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 415–424, 2008. Available at https://www2. eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-19.pdf. [2] Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimization. Mathematics of Operations Research, 39(1):31–45, 2014. doi: 10.1287/moor. 2013.0598. [3] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 138–158. PMLR, 2019. URL https://proceedings. mlr.press/v99/auer19a.html. [4] Francis Bach. Learning with submodular functions: A convex optimization perspective. In Foundations and Trends in Machine Learning, volume 6, pages 145–373, 2013. [5] Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404–1422, 2012. doi: 10.1016/j.jcss.2012.01.001. [6] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 6.1–6.20. PMLR, 2012. URL https://proceedings.mlr.press/v23/chiang12.html. [7] Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, and Iman Shames. Solving the offline and online min-max problem of non-smooth submodular-concave functions: A zeroth-order approach. arXiv preprint arXiv:2601.21243, 2026. URL https://arxiv.org/ abs/2601.21243. [8] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. doi: 10.1006/jcss.1997.1504. [9] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3–4):157–325, 2016. doi: 10.1561/2400000013. URL https://www.nowpublishers. com/article/Details/OPT-013. [10] Elad Hazan and Satyen Kale. Online submodular minimization. Journal of Machine Learning Research, 13:2903–2922, 2012. [11] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2–3):169–192, 2007. doi: 10.1007/s10994-007-5016-8. [12] Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32(2): 151–178, 1998. doi: 10.1023/A:1007424614876. [13] Anatoli Juditsky and Arkadi Nemirovski. First-order methods for nonsmooth convex large-scale optimization, I: General purpose methods. In Suvrit Sra, Sebastian Nowozin, and Stephen J. Wright, editors, Optimization for Machine Learning, pages 121–148. MIT Press, 2011. doi: 10.7551/mitpress/8996.003.0007. [14] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994. doi: 10.1006/inco.1994.1009. [15] László Lovász. Submodular functions and convexity. In Mathematical Programming: The State of the Art, pages 235–257. Springer, 1983. doi: 10.1007/978-3-642-68874-4_10. [16] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. 11
[17] Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 4300–4354. PMLR, 2021. URL https://proceedings.mlr. press/v134/wei21b.html. [18] Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 5882–5891. PMLR, 2018. URL https://proceedings.mlr.press/v80/zhang18o. html. [19] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Machine Learning (ICML), pages 928–936, 2003.
12
Appendix Table of Contents A. B. C. D. E. F. G.
Background and Structural Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Algorithms and Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Proofs: Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Proofs: Lower Bounds and Tight Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Separations and Structural Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Additional Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Extended Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
A
Background and Structural Foundations
A.1
Landscape of Online Polyhedral Learning
Table 1 summarizes the landscape of online submodular and polyhedral optimization. Our work provides an instability-parameterized characterization for the fixed-partition setting studied in the main text. Table 1: Comparison of online learning approaches for submodular-concave and polyhedral games. Approach OGD / Mirror Descent ZO-EG [7] Naive MW (2n arms) CAMW (this paper)
A.2
Rate p O(pn/T ) O(pnP̄T /T ) O(pn/T ) O( (1+SCT ) log n/T )
Adaptive?
Tight?
No Path-length No Cell stability
Yes (worst case) No Intractable Yes
Background on Structural Properties of the Lovász Extension
We present the following structural results from Lovász [15], Schrijver [16] for completeness. Lemma A.1 (Lovász extension: convexity and tight relaxation). Let f : 2[n] → R be submodular. Then the Lovász extension fL : [0, 1]n → R defined in (1) satisfies: (1) fL is convex and (2) minx∈[0,1]n fL (x) = minS⊆[n] f (S). Lemma A.2 (Mixed minimax value via threshold coupling). Consider a submodular-concave game (f, [n], Y) with f (·, y) submodular and f (S, ·) concave. Define the mixed value V mix := minµ∈∆(2[n] ) maxy∈Y ES∼µ [f (S, y)] and the relaxed value V ⋆ := minx∈[0,1]n maxy∈Y fL (x, y). Then V ⋆ = V mix . Lemma A.3 (Chain support structure). The optimal mixed strategy for the minimizer in a submodularconcave game is supported on a chain of at most n+1 nested subsets: there exist ∅ = C0 ⊂ C1 ⊂ PK · · · ⊂ CK = [n] with K ≤ n and weights w ∈ ∆K+1 such that fL (x⋆ , y) = j=0 wj f (Cj , y) for all y ∈ Y. Corollary A.4 (Mixed equilibrium existence). Every submodular-concave game admits a saddle point (x⋆ , y ⋆ ) ∈ [0, 1]n × Y with fL (x⋆ , y) ≤ V ⋆ ≤ fL (x, y ⋆ ) for all x ∈ [0, 1]n , y ∈ Y. Moreover, the optimal minimizer strategy x⋆ decomposes as a distribution over a chain of at most n+1 nested subsets, and V ⋆ = V mix . A.3
Assumption Scaling Across Domains
Assumption 2.1 requires Lipschitz and boundedness constants (Lx , Ly , M ). Table 2 verifies that these scale√ polynomially in n for all application domains considered in the paper. The key observation n is that the n factor in the OLMDA static √ regret arises from the diameter of [0, 1] , not from these constants; CAMW replaces this with log n by exploiting the chain structure. 13
Table 2: Boundedness constants scale polynomially in n for standard application domains. Domain
Lx
Ly
M
Influence max. (IC model) Sensor placement (coverage) Feature selection (MI)
√ O( n) √ O( n) √ O( n)
O(n) O(n) O(n log n)
O(n) O(n) O(n)
B
Algorithms and Implementation
B.1
OLMDA: Online Lovász Mirror Descent-Ascent
Algorithm 2 OLMDA: Online Lovász Mirror Descent-Ascent Require: Step sizes ηx , ηy > 0; initial (x1 , y1 ) 1: for t = 1, . . . , T do 2: Play (xt , yt ); observe ft 3: xt+1 ← arg minx∈[0,1]n ⟨gtx , x⟩ + η1x Dψ (x, xt ) 4: yt+1 ← arg maxy∈Y ⟨gty , y⟩ − η1y Dφ (y, yt ) 5: end for
[mirror descent] [mirror ascent]
Baseline algorithm OLMDA treats fL as a generic convex-concave function. The Lovász subgradient at xt requires n+1 evaluations of ft and O(n log n) sorting. √ Theorem B.1 (Static regret). Under Assumption 2.1, OLMDA achieves T1 RegT ≤ (Lx n + √ Ly DY )/ T . √ The n factor arises from the diameter of [0, 1]n and treats the polyhedral structure as irrelevant. Theorem B.2 (Dynamic regret). Under Assumption 2.1, Algorithm 2 with step sizes ηx = √ p n(1 + PTx )/(Lx T ) achieves: ! r 1 n(1 + P̄T ) DGT ≤ O , (7) T T PT −1 ⋆ where P̄T = t=1 zt⋆ − zt+1 is the path length of the saddle-point sequence and zt⋆ = (x⋆t , yt⋆ ). Proof. The proof follows the dynamic regret analysis for mirror descent. Using the same decomposition as Theorem B.1 but with time-varying comparators x⋆t , the telescoping Bregman terms yield an additional path-length cost: ! T T −1 X X 1 ηx T L2x x ⋆ ⋆ ⋆ ⋆ ⟨gt , xt − xt ⟩ ≤ Dψ (x1 , x1 ) + Dψ (xt+1 , xt ) + . (8) ηx 2 t=1 t=1 The Bregman divergence terms are bounded by O(n(1 + PTx )) under the Euclidean setup, giving the result after optimizing ηx . B.2
Geometric Chain-Overlap Transfer
Geometric WS-CAMW (Algorithm 1) replaces the uniform restart of cold-start CAMW with a chain-overlap transfer that preserves weights on shared chain elements. We state and prove the initialization guarantee used in Theorem 3.4. Lemma B.3 (Geometric transfer initialization). Let w be the MW weight distribution at the end πj πj+1 πj of epoch j over chain P C , and let S = {k : Ck = Ck } be the shared chain elements with total weight p = k∈S wk . Under geometric transfer with parameter α ∈ (0, 1), the transferred distribution .X (1−α) wk + α/(n+1) if k ∈ S, w̃k = wk′ = w̃k w̃ℓ , (9) α/(n+1) if k ∈ / S, ℓ
satisfies: 14
(a) wk′ ≥ α/(n+1) for every k, so DKL (ei⋆ ∥w′ ) ≤ log((n+1)/α) for any comparator i⋆ . (b) If i⋆ ∈ S with prior weight wi⋆ , then wi′⋆ ≥ (1−α) wi⋆ + α/(n+1), and the initialization KL is DKL (ei⋆ ∥w′ ) ≤ log 1/ (1−α) wi⋆ + α/(n+1) . When wi⋆ is large (the expert performed well in the previous epoch), this can be O(1) rather than O(log n). P Proof. Part (a). The normalization constant is Z = k w̃k = (1−α) p + α ≤ 1, since p ≤ 1. Thus ′ wk = w̃k /Z ≥ w̃k ≥ α/(n+1) for all k. The KL bound follows: DKL (ei⋆ ∥w′ ) = log(1/wi′⋆ ) ≤ log((n+1)/α). Part (b). For i⋆ ∈ S: w̃i⋆ = (1−α) wi⋆ + α/(n+1). Since Z ≤ 1, wi′⋆ = w̃i⋆ /Z ≥ w̃i⋆ , giving the stated bound. When p ≈ 1 (most weight on shared elements, as occurs after small permutation changes), Z ≈ 1 and wi′⋆ ≈ (1−α) wi⋆ , so DKL ≈ log(1/wi⋆ ) + log(1/(1−α)): the inherited divergence from the previous epoch plus a constant. Remark B.4 (Comparison with Jaccard transfer). An alternative transfer uses the Jaccard-overlap P (j+1) (j) (j+1) (j) (j) matrix Tik = |Ci ∩ Ck |/|Ci ∪ Ck | and sets wi′ = (1−α) k Tik wk + α/(n+1). This satisfies the same worst-case bound (Part (a)) but does not exploit the position-based chain structure: the geometric transfer preserves the exact weight of shared elements, while Jaccard diffuses weight through set-overlap coefficients. In experiments, both variants outperform cold restart, with geometric transfer providing slightly sharper gains when consecutive permutations are close. Experiments show 6–67% improvement in regret over cold-start CAMW across domains (Section F), with the largest gains at moderate T /n where burn-in dominates. At larger scale, the improvement is more dramatic: in the extended SNAP experiments (Section F.11), Geometric WS-CAMW achieves 2–3× lower absolute regret than cold-start CAMW throughout the T /n range, with the gap widening as T grows.
C
Proofs: Upper Bound
C.1
Preliminary Results
The following two lemmas encapsulate the key steps of the CAMW analysis. They are used throughout the upper bound proofs (Theorems 3.2, 3.4, C.3)). Lemma C.1 (Within-epoch MW bound). Fix an epoch of length τ during which the minimizer runs Multiplicative Weights over a fixed chain of K ≤ n+1 nested subsets with losses bounded by M . Then the epoch’s contribution to saddle-point regret against the game value V ⋆ satisfies: X √ fL (xt , y ⋆ ) − τ · V ⋆ ≤ 2M τ ln K. (10) t∈epoch
p MW with learning rate η = ln K/τ over K experts with losses in [−M, M ] yields Proof. Standard √ regret ≤ 2M τ ln K against the best expert [8]. Since V ⋆ = minx maxy fL (x, y) ≥ mini f (Ci , y ⋆ ) (the game value exceeds the best chain vertex against any fixed y ⋆ ), the MW regret against the best vertex upper bounds the epoch’s contribution to saddle-point regret. Lemma Suppose E epochs of lengths τ1 , . . . , τE P C.2 (Epoch aggregation via Cauchy–Schwarz). √ with j τj = T each contribute regret a τj for some constant a > 0. Then the total regret satisfies: E X √ √ a τj ≤ a E · T .
(11)
j=1
Proof. By Cauchy–Schwarz:
PE
j=1
√
τj ≤
q
E·
P
15
j τj =
√
E · T.
C.2
Proof of Theorem 3.2
We prove the bound for the oracle version of CAMW, which assumes access to the equilibrium permutation πx⋆t . This characterizes minimax regret as a function of the intrinsic permutation-switch complexity SCT . Proof strategy. The proof proceeds in four steps. First, we decompose the horizon into SCT + 1 epochs separated by permutation switches (epoch decomposition). Second, within each epoch the optimal chain is fixed, so we run MW over its ≤ n+1 vertices and apply Lemma C.1 (within-epoch structure). Third, we aggregate across epochs via Lemma C.2 (Cauchy–Schwarz aggregation). Fourth, we combine with the maximizer’s mirror ascent bound. The key insight is that MW’s log K dependence on the number of chain vertices replaces OGD’s n-dependence on the ambient dimension. Proof. Epoch decomposition. Let {t1 = 1 < t2 < · · · < tS+1 = T +1} denote the time indices at which the equilibrium permutation changes, using the consistent deterministic selection rule from Lemma 3.1. This partitions {1, . . . , T } into S+1 epochs, where S = SCT . Within-epoch structure. Fix an epoch j of length Tj . During this epoch, the equilibrium permutation π (j) is fixed. The Lovász extension restricted to this permutahedron cell reduces to a linear function over the associated chain (j)
(j)
C0 ⊂ C1 ⊂ · · · ⊂ Cn(j) . (j)
Thus the minimizer’s problem reduces to online linear optimization over the n+1 vertices {Ci }ni=0 . Minimizer regret within an epoch. By Lemma C.1 with K = n+1 and losses bounded by M : q X fL (xt , y ⋆ ) − Tj · V ⋆ ≤ 2M Tj ln(n+1). (12) t∈epoch j
Coupling with the maximizer. The above bounds minimizer regret against a fixed comparator within the epoch. To obtain saddle-point regret as defined in (2), we combine this with mirror ascent for the maximizer. √ By standard mirror ascent analysis with step size ηy = 1/ T : T X
fL (xt , yt ) −
T X
t=1
√ fL (xt , yt⋆ ) ≤ O(Ly DY T ).
(13)
t=1
Combining the minimizer and maximizer bounds and using the minimax inequality V ⋆ = minx maxy fL (x, y) ≥ minx fL (x, y) for every fixed y, we obtain total regret RegT ≤
S+1 X
2M
q
√ Tj ln(n+1) + O(Ly DY T ).
(14)
j=1
Aggregation across epochs. By Lemma C.2 with E = S+1 = SCT +1 epochs: p √ RegT ≤ O M (1+SCT ) · T · ln n + Ly DY T .
(15)
Dividing by T : 1 RegT ≤ O T
r
(1+SCT ) · log n T
16
!
Ly DY + √ . T
(16)
C.3
Proof of Theorem 3.4
Proof. The proof mirrors that of Theorem 3.2, with the epoch decomposition now driven by the observed best-response switches and the geometric chain-overlap transfer replacing the uniform restart. c T partition Step 1: Epoch decomposition via best-response switches. The observed switches SC BR b c [T ] into S := SCT + 1 epochs. Within epoch j, the best-response permutation πt is constant, so Algorithm 1 runs MW on a fixed chain C (j) of n+1 elements. Comparator. Within each epoch, we bound the minimizer’s contribution to saddle-point regret (j) against the game value V ⋆ . Since mini f (Ci , y ⋆ ) ≤ V ⋆ for any chain and any y ⋆ , the MW bound against the best fixed chain vertex in hindsight yields a valid upper bound on the epoch’s regret contribution. Step 2: Within-epoch MW regret. At the start of epoch j, the geometric transfer (Lemma B.3(a)) ensures every expert has weight ≥ α/(n+1), so the initialization KL satisfies DKL (ei⋆ ∥wj′ ) ≤ log((n+1)/α). Standard MW analysis [8] then gives per-epoch regret: q X (17) fL (xt , y ⋆ ) − Tj · V ⋆ ≤ 2M Tj ln((n+1)/α). t∈epoch j
Since α is a fixed constant, ln((n+1)/α) = ln(n+1) + ln(1/α) = O(ln n). c T +1: Step 3: Cauchy–Schwarz aggregation. By Lemma C.2 with E = SC q T X ⋆ ⋆ c T +1) · T · ln((n+1)/α). fL (xt , y ) − T · V ≤ 2M (SC
(18)
t=1
√ Step 4: Combining with maximizer. The maximizer’s mirror ascent contributes Ly DY T indepenq √ c T ) · log n/T + Ly DY / T . dently of epoch structure. Combining: T1 RegT ≤ O (1+SC Data-dependent refinement. By Lemma B.3(b), when the epoch-j comparator is a shared chain q element with inherited weight wi⋆ , the per-epoch bound improves to 2M Tj · log(1/wi′⋆ ), which j p can be much smaller than 2M Tj ln(n+1). This does not change the worst-case rate—the adversary can always arrange for the comparator to be a new element with minimal weight—but it explains the consistent empirical gains of geometric transfer on stable instances where consecutive permutations share most of their chain structure. C.4
Chain-Restricted Regret
Theorem C.3 (Chain-restricted regret). If the game admits anp optimal chain of at most K ≤ n + 1 1 sets at each round, MW over the chain achieves T RegT = O( log K/T ). When the optimal chain varies across rounds with pSCT permutation switches, sleeping-experts MW over the union chain pool achieves T1 RegT = O( (1+SCT )(log n + log(1+SCT ))/T ). Proof. We give the full proof for the single-game repeated setting (ft = f for all t) and then discuss the extension to varying games. Step 1: Chain structure of optimal strategies. The optimal mixed strategy x⋆ ∈ [0, 1]n for minx maxy fL (x, y) is a threshold vector supported on an optimal chain C ⋆ = {C0 = ∅ ⊂ C1 ⊂ · · · ⊂ CK } with K ≤ n + 1 nested subsets (Lemma A.3). Concretely, there exist weights w⋆ ∈ ∆K (the probability simplex over K+1 elements) such that fL (x⋆ , y) =
K X
wj⋆ f (Cj , y),
for all y ∈ Y.
(19)
fL (x⋆ , y ⋆ ) denote the game value, where y ⋆
=
j=0
Let V ⋆ = minx maxy fL (x, y) arg maxy fL (x⋆ , y).
=
17
Step 2: Two-player algorithm. We run the following pair of no-regret algorithms: • Minimizer: Multiplicative Weights (MW) over the K+1 experts {C0 , C1 , . . . , CK }. At round t, MW produces a distribution pt ∈ ∆K over the chain. The learner plays the threshold vector xt whose Lovász decomposition on C ⋆ has weights pt , so that fL (xt , y) = PK j=0 pt,j f (Cj , y) for all y. mirror ascent over Y with Bregman divergence Dφ and step size • Maximizer: Online √ ηy = DY /(Ly T ). Step 3: Minimizer’s regret P via MW. The minimizer’s loss at round t against the fixed saddle-point response y ⋆ is fL (xt , y ⋆ ) = j pt,j f (Cj , y ⋆ ). Since |f (Cj , y ⋆ )| ≤ M for all j by Assumption 2.1, the standard MW guarantee [1] yields: T X
fL (xt , y ⋆ ) − T ·
t=1
Since V ⋆ =
min j∈{0,...,K}
f (Cj , y ⋆ ) ≤ 2M
p
T ln(K+1).
(20)
⋆ ⋆ ⋆ ⋆ j wj f (Cj , y ) is a convex combination, we have V ≥ minj f (Cj , y ), so:
P
T X
fL (xt , y ⋆ ) − T · V ⋆ ≤ 2M
p
T ln(K+1).
(21)
t=1
Step 4: Combining with maximizer’s mirror ascent. Mirror ascent gives T V ⋆ − √ PT ⋆ t=1 fL (x , yt ) ≤ Ly DY T . Adding to (21): p √ RegT ≤ 2M T ln(K+1) + Ly DY T , (22) p p so T1 RegT = O( log K/T ), which gives O( log n/T ) for K ≤ n + 1. Step 5: Extension to varying games (ft changes across rounds). When the optimal chain Ct⋆ varies across rounds, we proceed as follows. Let C (1) , . . . , C (SCT +1) be the distinct optimal chains encountered across the SCT +1 epochs (an epoch is a maximal interval during which the optimal chain SSC +1 is fixed). Define the union expert pool E = j=1T C (j) , which contains at most (SCT + 1)(n + 1) nested-set experts. We run MW in sleeping-experts mode [1]: at each round t, only the experts in the current chain Ct⋆ are “awake” (receive loss feedback and participate in the MW update), while experts from other chains “sleep” (their weights are frozen). The sleeping-experts guarantee [1, Theorem 3] ensures that for any fixed comparator expert e ∈ E and any subsequence of rounds Te ⊆ [T ] during which e is awake: X X p ℓt (it ) − ℓt (e) ≤ 2M |Te | · ln |E|, (23) t∈Te
t∈Te
where ℓt (it ) is the loss of the action chosen by MW. Within each epoch j of length Tj , the optimal chain C (j) is fixed, and the best expert on this chain achieves value ≤ Vj⋆ . The sleeping-experts bound restricted to epoch j gives minimizer regret p O(M Tj ln |E|). Aggregating over epochs via Cauchy–Schwarz: s SC q T +1 X X p p M Tj ln |E| ≤ M ln |E| · (SCT + 1) Tj = M (SCT + 1) T ln |E|. (24) j=1
j
Since |E| ≤ (SCT + 1)(n + 1), we have ln |E| ≤ ln(SCT + 1) + ln(n + 1). Combined with the maximizer’s mirror ascent bound (unchanged), this yields: ! r (1+SCT )(ln n + ln(1+SCT )) 1 RegT = O , (25) T T p which is O( (1+SCT ) log n/T ) whenever SCT = poly(n, T ) (the logarithmic ln(1+SCT ) term is absorbed). 18
D
Proofs: Lower Bounds and Tight Characterization
D.1
Structure-Dependent Lower Bound
Lemma D.1. For pany c ∈ [0, 1], there exists a family of submodular-concave games such that 1 E[Reg ] ≥ Ω( (1−c) · n/T ). T T Proof. Fix c ∈ [0, 1] and set m = ⌈(1−c) n⌉. Partition [n] = A ∪ B with |A| = m, |B| = n − m. Take h(T ) = min(|T |, 1) for T ⊆ B (monotone submodular) and Y = [−1, 1]. At each round t, draw i.i.d. εt,i ∼ Unif{−1, +1} for i ∈ A and define X ft (S, y) = y εt,i + h(S ∩ B), S ⊆ [n], y ∈ Y. (26) i∈S∩A
Each ft is submodular in S (sum of modular and submodular) and linear in y. P The Lovász extension separates as ftL (x, y) = y i∈A xi εt,i + hL (xB ), where hL (xB ) is deterministic and y-independent. The B-component cancels in the regret difference, so the problem reduces to online linear optimization over [0, 1]m × [−1, 1] with bilinear payoff ℓt (xA , y) = y ⟨εt , xA ⟩. By the minimax lower bound for Rademacher losses [1] and Yao’s principle: ! r 1 (1−c) · n . (27) sup E[RegT ] ≥ Ω T {ft } T As c increases from p 0 to 1, the effective modular dimension shrinks from n to 0, and the bound interpolates from Ω( n/T ) to 0. The lower bound applies to any curvature notion κ satisfying κ = 0 for modular games and κ → 1 as the modular fraction vanishes. D.2
Proof of Theorem 4.1
We construct an adversarial sequence with prescribed permutation-switch count s such that any algorithm incurs p (1+s) · T · log n . E[RegT ] ≥ Ω Proof. Epoch construction. Partition the horizon into s+1 epochs of equal length Tj = ⌊T /(s+1)⌋. For each epoch j, choose a permutation π (j) such that consecutive permutations differ in their first coordinate (π (j) (1) ̸= π (j+1) (1)), ensuring distinct permutahedron cells. (j)
Loss definition. Within epoch j, let {Ci }ni=0 be the chain corresponding to π (j) . For each round t in epoch j, sample i.i.d. Rademacher variables εt,i ∈ {±1} and define: ft (S, y) = y · εt,k(S) ,
(j)
k(S) = max{i : Ci
⊆ S}.
(28)
This function is modular in S along the chain and hence submodular. We add a deterministic (j) perturbation ε · i/T to the loss of chain element Ci for ε = 1/(nT ), ensuring strict ordering and guaranteeing the equilibrium permutation equals π (j) uniquely within each epoch. Epoch-level lower bound. Within epoch j, the minimizer faces an online learning problem over n+1 experts with i.i.d. Rademacher losses. The learner cannot transfer information across epochs: losses in epoch j are drawn independently of prior epochs, so the experts problem is fresh each epoch. By the standard minimax lower bound for expert advice (via Yao’s principle; 1), for any (possibly history-dependent) algorithm: q E[Regj ] ≥ c Tj log(n+1) (29) for a universal constant c > 0. Crucially, this bound holds even conditioning on prior epochs, since the losses in epoch j are drawn independently. 19
Aggregation across epochs. Summing across epochs: E[RegT ] =
s+1 X
E[Regj ] ≥ c
j=1
s+1 q X
Tj log(n+1).
j=1
Since Tj = ⌊T /(s+1)⌋: s+1 X p p Tj ≥ (s+1) · T . j=1
Thus: p E[RegT ] ≥ Ω (1+s) · T · log n . p Dividing by T yields the stated bound T1 E[RegT ] ≥ Ω( (1+s) log n/T ). D.3
General Polyhedral Lower Bound
Proposition D.2 (General polyhedral lower bound). For any s ∈ {0, . . . , T −1}, there exists a polyhedral partition and piecewise-linear losses with RST = s such that T1 E[RegT ] ≥ p Ω( (1+s) log Vmax /T ). We construct the adversary explicitly. Proof. Partition the horizon into s+1 epochs of lengths T1 , . . . , Ts+1 . During each epoch, fix a region Ra and define losses ℓt (vi ) = M εt,i for vertices vi ∈ V (Ra ), with εt,i i.i.d. Rademacher. Extend ℓt linearly over Ra and assign losses M +1 to all vertices outside Ra , ensuring the equilibrium remains in Ra . Insert O(1/T ) perturbations to guarantee unique region membership. By Yao’s minimax principle, for any (possibly history-dependent) algorithm, q E[Regj ] ≥ c Tj log |V (Ra )| for some constant c > 0. Summing over epochs and applying Cauchy–Schwarz gives p E[RegT ] ≥ Ω (1 + s) T log Vmax . Dividing by T yields the stated bound. Since the comparator class includes the vertex set, the lower bound for expert advice applies to all algorithms over the convex hull — continuous strategies cannot beat the discrete optimum when losses are linear within each region. D.4
Proof of Theorem 4.3
Proof. Upper bound. The argument mirrors Theorem 3.2 with regions replacing permutation cells. Let {t1 = 1 < t2 < · · · < ts+1 = T +1} be the region-switch times, giving s = RST and s+1 epochs. Within epoch j, losses are linear over region Ra(j) , so the learner faces an online linear optimization problem over |V (Ra(j) )| ≤ Vmax vertices. Running MW with learning rate p p ηj = ln Vmax /Tj yields per-epoch regret ≤ 2M Tj ln Vmax . Summing across epochs and applying Cauchy–Schwarz: s+1 X p p Tj ≤ (s+1) · T , j=1
p giving RegT ≤ O( (1+RST ) · T · log Vmax ). p Lower bound. Proposition D.2 provides the matching Ω( (1+RST ) · T · log Vmax ) lower bound via Rademacher epoch constructions. 20
D.5
Proof of Theorem 4.5
Proof. The phase transition follows from comparing the polyhedral rate with the OCO baseline. p Upper bound. By Theorem 4.3,p MW-with-restarts achieves O( (1+RST ) log Vmax /T ). Standard OGD over X ⊆ Rd achieves O( d/T ) regardless of RST . Taking the better algorithm yields (r r )! 1 (1+RST ) log Vmax d ⋆ RegT (RST ) ≤ O min , . T T T The crossover occurs when (1+RST ) log Vmax = d, i.e., RS⋆T = d/ log Vmax − 1 ≈ d/ log Vmax . p Lowerp bound. For RST < RS⋆T : Proposition D.2 gives Ω( (1+RSp T ) log Vmax /T ), which dominates d/T . For RST > RS⋆T : the standard OCO lower bound Ω( d/T ) [1] applies, since the problem contains online linear optimization over Rd as a special case. Thus both branches of the minimum are tight.
E
Separations and Structural Properties
E.1
SCT Is Incomparable with Path Length and Gradient Variation Table 3: SCT captures combinatorial geometry invisible to existing adaptive measures. Measure
Defined on
Captures
Path length P̄T Switching count Variation VT SCT (ours)
Comparator motion in ℓ2 #Pcomparator changes ∥ft − ft−1 ∥ Equilibrium cell changes
Drift of best action Discrete instability Loss non-stationarity Geometric stability
Typical bound p O(√ T P̄T ) O(√S · T log K) O(pVT ) O( (1+SCT )T log n)
Proposition E.1 (SCT vs. switching count). SCT and ST := |{t : a⋆t+1 ̸= a⋆t }| are incomparable: (a) SCT = 0, ST = Θ(T ) is possible; (b) SCT = Θ(T ), ST = 0 is possible. Proof. Part (a): SCT = 0, ST = Θ(T ). Fix a single permutation π = (1, 2, . . . , n) with chain C0 = ∅, C1 = {1}, . . . , Cn = [n]. Define losses so that at odd rounds t, the optimal chain vertex is C1 (the singleton), and at even rounds, the optimal vertex is C2 (the pair). Concretely, set ft (S, y) = |S ∩ At | − β|S| where At alternates between {1} and {1, 2} and β is chosen so the optimizer flips. The permutation π is constant (determined by the same marginal ordering), so SCT = 0. But the best action changes every round, giving ST = T − 1. Part (b): SCT = Θ(T ), ST = 0. Let n = 2 and Y = [0, 1]. At each round, define ft such that the singleton {1} is uniquely optimal: ft ({1}, y) < ft ({2}, y) < ft ({1, 2}, y) < ft (∅, y) for all y. The permutation determining the Lovász cell depends on the ordering of marginals δ1 (yt⋆ ) vs. δ2 (yt⋆ ), which can alternate by choosing ft so that δ1 (yt⋆ ) > δ2 (yt⋆ ) at odd rounds and δ1 (yt⋆ ) < δ2 (yt⋆ ) at even rounds, while keeping {1} optimal in both cases. Then ST = 0 but SCT = T − 1. Example E.2 (SCT = 0 but path length = Θ(T )). Consider a repeated game where ft (·, y) has the same optimal permutation π ⋆ for all t, but the adversary’s equilibrium response yt⋆ oscillates within p Y, causing ℓ2 path length Θ(T ). Since√the cell never changes, p SCT = 0, and CAMW achieves O( log n/T ). Path-length bounds give O( nT )—worse by nT / log n. Example E.3 (Small path length but SCT = Θ(T )). Adjacent marginals separated by a vanishing gap ϵ/T : tiny perturbations flip the ordering every round, giving SCT = Θ(T ) with P̄T = O(ϵ). Proposition E.4 (Formal separation). No monotone Φ satisfies SCT ≤ Φ(P̄T ) for all game sequences, and no monotone Ψ satisfies P̄T ≤ Ψ(SCT ). The same holds with gradient variation VT replacing P̄T . Proof. Example E.2 shows SCT = 0 with P̄T = Θ(T ), violating P̄T ≤ Ψ(0) for large T . Example E.3 shows SCT = Θ(T ) with P̄T = O(ϵ), violating SCT ≤ Φ(O(ϵ)) for large T . 21
SCT is also distinct from switching regret: switching regret measures how often the best fixed action changes within an exogenous expert class, while SCT measures how often the active cell geometry changes through boundary crossings, and is algorithm-independent. E.2
Equilibrium Tracking Under Marginal Gaps
Proposition E.5 (Tracking the equilibrium). Let Lxy be the Lipschitz constant of marginals and c T ≤ SCT + |{t : ∥yt − yt⋆ ∥ > δmin > 0 the minimum marginal gap at equilibrium. Then SC c T = SCT . δmin /(2Lxy )}|. When the maximizer tracks well, SC Proof. Fix round t and suppose ∥yt − yt⋆ ∥ ≤ δmin /(2Lxy ). By the Lipschitz condition on marginals: |δi (yt ) − δi (yt⋆ )| ≤ Lxy ∥yt − yt⋆ ∥ ≤ δmin /2,
∀ i ∈ [n].
(30)
At equilibrium, the sorted marginals have gaps ≥ δmin : δπ⋆ (i+1) (yt⋆ ) − δπ⋆ (i) (yt⋆ ) ≥ δmin for all i. Therefore: δπ⋆ (i+1) (yt ) − δπ⋆ (i) (yt ) ≥ δπ⋆ (i+1) (yt⋆ ) − δπ⋆ (i) (yt⋆ ) − 2 · δmin /2 ≥ δmin − δmin = 0.
(31) (32)
So the ordering at yt agrees with the ordering at yt⋆ : πtBR (yt ) = πtBR (yt⋆ ). Since πtBR (yt⋆ ) = πx⋆t (the best-response permutation at the equilibrium maximizer equals the equilibrium minimizer’s permutation), the observed permutation πtBR (yt ) switches only when πx⋆t switches. For rounds where ∥yt − yt⋆ ∥ > δmin /(2Lxy ), the best-response permutation may differ, contributing c T ≤ SCT + |{t : ∥yt − yt⋆ ∥ > at most one extra observed switch per such round. Thus SC δmin /(2Lxy )}|. For applications with natural marginal gaps (influence: δmin ≥ Ω(1/poly(n)); coverage: δmin ≥ 2 2 1/n), tracking is effective after O(L2xy DY /δmin ) rounds. E.3
A Priori Bound on SCT Under Bounded Drift
Proposition E.6 (A priori bound). Under drift maxS,y |ft+1 (S, y) − ft (S, y)| ≤ ∆ and marginal gap δmin > 0: SCT ≤ 2n∆T /δmin . Proof. Each permutation switch requires adjacent sorted marginals to cross, consuming at least δmin of total marginal shift. Per-round drift shifts at most n marginals by ∆ each, giving budget n∆T . E.4
Region-Switch Incomparability for General Polyhedral Losses
For general polyhedral losses, region-switch complexity RST is strictly incomparable with pathlength PT and gradient variation VT : (a) RST = 0 with PT = Θ(T ) (motion within a region), and (b) RST = Θ(T ) with PT = O(1) (boundary crossings by infinitesimal amounts). MW-with-restarts √ is also projection-free: for piecewise-linear losses with RST = 0, it achieves O( T log Vmax ) regret using only linear optimization oracles, circumventing the classical O(T 3/4 ) barrier [9] for projection-free OCO. E.5
The Dimension Gap
p Proposition p E.7 (Dimension gap). Thepratio of the dimension-dependent rate Θ( n/T ) to the tight rate Θ( (1+SC pT ) log n/T ) is Θ( n/((1+SCT ) log n)). When SCT = 0, the classical rate overestimates by Θ( n/ log n); when SCT = Θ(n/ log n), both rates coincide. p p p Proof. The ratio is n/T (1+SCT ) log n/T = n/((1+SCT ) log n). At SCT = 0, this p equals n/ log n. Setting the ratio to 1 gives n = (1+SCT ) log n, i.e., SCT = n/ log n − 1 = Θ(n/ log n). 22
E.6
Piecewise-Constant Drift Implies Bounded SCT
Proposition E.8 (Piecewise-constant drift bound). Suppose the adversary sequence admits k piecewise-constant regimes, i.e., there exist times 1 = τ1 < τ2 < · · · < τk ≤ T such that the equilibrium permutation πx⋆t is constant within each interval [τj , τj+1 ). Then SCT ≤ k − 1, and the √ minimax regret satisfies RegT = O( k · T · log n). Proof. Each regime boundary τj → τj+1 can cause at most one permutation switch (the permutation is constant within each regime by assumption). p √ Thus SCT ≤ k − 1. Substituting into Theorem 3.2: RegT ≤ O( (1+(k−1)) · T · log n) = O( k · T · log n). This captures the common setting where the environment changes through a small number of phases (e.g., seasonal drift in influence networks, regime changes in optimization landscapes).
F
Additional Experiments
This appendix provides the sensor-placement and feature-selection experiments (deferred from Section 5), five ablation studies that validate individual design choices in CAMW, revision-time diagnostics for warm starts and switch detection, and extended results for the shortest-path, SNAP, and dimension-scaling experiments. Main-text Figures 1–6 are generated in Section 5; Figures 7–16 below provide supplementary results. All shaded regions and error bars represent ±1 standard deviation across the number of random seeds listed in Table 4. Unless stated otherwise, appendix experiments follow the same reporting protocol as the main text: absolute regret, theory-normalized regret, and the relevant instability count are the primary quantities, while ratios or crossover locations are secondary summaries derived from them. F.1
Experimental Setup and Hyperparameters
Table 4 reports the hyperparameters used across all experiments. All step sizes were selected via the theory-prescribed formulas unless otherwise noted. Monte Carlo averaging uses MC = 50 samples per subgradient evaluation. Table 4: Hyperparameters across all experimental domains. Seeds MC ηx p Synthetic stability sweep 20 10,000 10 50 plog n/T Dimension scaling {10, 20, 50, 100, 200, 500, 1,000} 20,000 5 50 plog n/T Shortest-path (k-grid) 2k(k−1) 50,000 10 – plog N/T SNAP (small) 34–1,005 2,000 3 50 plog n/T SNAP (large) 787–2,744 1,000–20,000 3 50 plog n/T Sensor placement 30, 50 2,000 3 50 plog n/T Feature selection 11, 30 2,000 3 50 plog n/T Transfer-floor sweep 50 10,000 10 50 plog n/T SAOL baseline 50, 200 10,000 10 50 plog n/T Noise/margin stress 50 10,000 10 50 log n/T Domain
n
T
ηy √ 1/√T 1/√T 1/√T 1/√T 1/√T 1/√T 1/√T 1/√T 1/√T 1/ T
Compute resources. Synthetic stability sweep (360 configurations), dimension scaling (140 configurations), and shortest-path experiments (1,200 configurations at T = 50,000) were run on 8× NVIDIA H100 80GB GPUs with total wall-clock time approximately 18 GPU-hours. Small SNAP and sensor/feature experiments were run on a single H100 in under 2 GPU-hours. Large-scale SNAP experiments (T up to 20,000, n up to 2,744) required approximately 6 GPU-hours. Total compute: ≈ 26 GPU-hours on H100. F.2
Revision-Time Diagnostics
We ran four targeted diagnostics after the main experimental suite. These experiments are used to check mechanisms that underlie the main claims, so we report them in the appendix rather than as additional main-paper figures. 23
Transfer-floor sweep. We swept the transfer-floor parameter α ∈ {0.001, 0.003, 0.01, 0.03, 0.1, 0.3} for both warm-start variants at paper scale (n = 50, T = 10,000, 10 seeds), with cold-restart CAMW as the α-independent reference. Cold CAMW has mean regret 0.0633. WS-CAMW is insensitive to α over this grid, with mean regret 0.0600–0.0610, corresponding to a 3.6–5.2% improvement over cold CAMW. Geometric-WS-CAMW is more sensitive to α and improves monotonically as α decreases, with mean regret 0.0440–0.0528, corresponding to a 16.6–30.5% improvement. Per-seed regret values agree to 4–5 decimal places across the 10 seeds, indicating low-variance behavior at this scale. We therefore use α = 0.1 as a robust default for WS-CAMW and the smallest numerically stable α for Geometric-WS-CAMW. Strongly-adaptive comparator. SAOL is included as the strongly-adaptive baseline and evaluated on two Lovász slots: a non-stationary synthetic regime (n = 50, T = 10,000, target SCT = 10) and a stationary dimension-scaling regime (n = 200, T = 10,000, target SCT = 0). SAOL did not improve over the CAMW family or OGD in either setting. On the non-stationary slot, SAOL’s mean regret is 0.3038, compared with 0.0547 for CAMW, 0.0517 for WS-CAMW, 0.0378 for Geometric-WS-CAMW, 0.0925 for OLMDA, and 0.0379 for OGD. On the stationary slot, CAMW, WS-CAMW, and Geometric-WS-CAMW are bit-identical to at least 10 decimal places, with mean regret 0.0212897210; SAOL’s mean regret is 0.5082. We interpret this as a baseline result for the tested Lovász regimes, not as evidence that strongly-adaptive methods cannot be competitive after further tuning. Noise and margin stress tests. We ran synthetic Lovász stress tests with n = 50, T = 10,000, target SCT = 10, and 10 seeds per cell. The noise axis adds Gaussian noise to the learner-facing oracle outputs with σ ∈ {0.01, 0.05, 0.1} while holding the margin at 0.5. The margin axis varies the chain margin in {0.05, 0.1, 0.25} with a clean oracle. Regret is evaluated on the underlying clean game, while the learner sees noisy or tight-margin oracle outputs. On the noise axis, mean final-average regret rises sharply for cold CAMW and OGD; CAMW increases by approximately 71% from σ = 0.01 to σ = 0.1 and exceeds 0.35 already at σ = 0.01. In contrast, WS-CAMW, Geometric-WS-CAMW, and OGD all remain below 0.07 over the same noise grid, and the two warm-start variants move by only about 6%. On the margin axis, all 15 unordered margin-pair checks (five algorithms times three pairs) give per-seed regrets identical to 10 decimal places in the post-hoc table. Thus this particular margin sweep does not effectively probe near-degenerate detector behavior at this horizon; we do not treat it as evidence that margin stress is conceptually irrelevant. Under noisy observations, observed permutation switches measure detector flicker in the noisy oracle view and should be distinguished from the clean scheduled SCT . Switch-detection validation. The switch-detection validation run completed cleanly: the manifest passed, all 16 batches were present, and the recorded checksums were verified. Ground-truth switch rounds are deterministic for T = 10,000 and target SCT = 10. In this validate regime, restart-aware methods align their triggers with the true boundaries, so the appropriate interpretation is “perfect event detection; delay distinguishes methods,” with 0-round delay for cold CAMW and 1-round delay for warm-start methods. Permutation-difficulty labels (adjacent, moderate-5, moderate-20, random) did not affect event-detection accuracy at this horizon, switch density, and tolerance. We therefore avoid interpreting those labels as harder detector conditions without additional tests at tighter tolerance, denser switches, or under noisy observations. Post-hoc switch-detection analysis produced 80 rows (4 difficulty levels × 4 methods × 5 seeds, T = 10,000, tolerance 50), and paired-test analysis produced 32 data rows for CAMW-family comparisons. The shortest-path runs contribute no paired-test rows under this script because their algorithm names do not match the CAMW-family pair set. Exploratory SNAP extension not reported as evidence. We also explored a larger SNAP influencemaximization extension on soc-Slashdot0902, but do not report it as a paper result. The exploratory preprocessing produced n = 4349, outside the intended 1500–2000 comparability band used by the Wiki-Vote and Epinions large-network experiments, and the run fell back to the pure-Python influence simulation path when Numba was unavailable. The projected runtime was therefore infeasible within the revision window. Our reported real-network influence-maximization evidence remains the Wiki-Vote and Epinions results in Section F.11; the Slashdot extension is deferred pending a defended preprocessing policy and a Numba-enabled runtime path. 24
F.3
Sensor Placement
We evaluate on two sensor-placement problems: a water-network monitoring task (n = 30 candidate locations) and a temperature-grid task (n = 50 grid cells). Unlike influence maximization, sensor placement is deterministic and noise-free, making it a clean testbed for isolating the effect of permutation stability. The adversary selects failure probabilities y ∈ Y to degrade coverage; the minimizer selects sensor locations to maximize worst-case coverage. Figure 5 shows that CAMW c T of these deterministic games, achieving the largest gains over baselines exploits the low observed SC c T ∈ {0, 1} for among all real-world domains. Across all seeds, the observed switch counts are SC both sensor tasks, consistent with the deterministic structure.
water_network 0.5
Average regret
0.8
Average regret
temperature_grid
OLMDA CAMW (ours) OGD CAMW-no-restart (ours)
0.6 0.4 0.2
0.4 0.3 0.2 0.1
0
50
100
150
Round t
200
0
50
100
Round t
150
200
Figure 5: Sensor placement. Left: water network (n = 30). Right: temperature grid (n = 50). c T , giving CAMW the largest gains over baselines. Deterministic games exhibit very low SC F.4
Feature Selection
We evaluate on two online feature-selection tasks: wine quality (n = 11 features) and breast cancer (n = 30 features). The minimizer selects a feature subset S; the adversary selects regression weights y ∈ Y to maximize prediction error. The objective f (S, y) is submodular in S (mutual information) and concave in y. On wine quality (n = 11), Naive MW over all 2n = 2048 subsets is feasible and serves as an oracle baseline. CAMW matches Naive MW within statistical noise, confirming that the cell decomposition incurs no approximation cost when the problem is small. On breast cancer (n = 30), Naive MW is intractable (230 ≈ 109 arms), while CAMW maintains low c T ∈ {1, 2}. Figure 6 summarizes both datasets. regret by exploiting the low observed SC
Wine Quality
Breast Cancer
OLMDA CAMW (ours) OGD CAMW-no-restart (ours) Naive MW
2.0
4
Average regret
Average regret
2.5
1.5 1.0 0.5 0.0
0
50
100
Round t
150
200
3 2 1 0
0
50
100
Round t
150
200
Figure 6: Online feature selection. Left: wine quality (n = 11); CAMW matches Naive MW. Right: breast cancer (n = 30); Naive MW is intractable, CAMW outperforms structure-agnostic baselines.
25
F.5
Ablation: Restart Mechanism
CAMW uses adaptive restarts triggered by detected permutation switches. We compare four restart strategies: (i) full adaptive (default CAMW), (ii) no restart (single epoch), (iii) periodic restart (fixed interval), and (iv) random restart. Figure 7 shows that adaptive restarts are critical at intermediate SCT levels, where the no-restart variant accumulates stale weights and the periodic variant either restarts too frequently (low SCT ) or too infrequently (high SCT ).
1.2
Average regret
1.0 0.8
Restart mechanism comparison full CAMW no restart periodic restart random restart
0.6 0.4 0.2 0.0
SC=0
SC=10
SC=100
Figure 7: Restart mechanism ablation. Adaptive restarts (default CAMW) outperform fixed and random strategies, especially at intermediate SCT .
F.6
Ablation: Oracle vs. Implementable Tracking
c T . Figure 8 compares three variants: Theorem 3.4 replaces the oracle SCT with the online estimate SC obs BR (i) SCT (observed by CAMW at runtime), (ii) SCT (computed from best-response permutations, oracle), and (iii) SCdesigned (the true designed value). The online estimate SCobs T closely tracks the T oracle value, and the resulting regret is statistically indistinguishable from the oracle variant. F.7
Ablation: Step-Size Sensitivity
We sweep step sizes ηx × ηy on a 10 × 10 log-spaced grid for both OLMDA and CAMW. Figure 9 shows that CAMW exhibits a broad plateau of near-optimal performance, while OLMDA is more sensitive to the step-size choice—particularly the minimizer step size ηx . F.8
Ablation: ZO-EG Smoothing Sensitivity
ZO-EG [7] requires a smoothing parameter µ and d function evaluations per gradient estimate. We sweep µ ∈ [10−4 , 10−1 ] and d ∈ {1, 5, 10, 20} to find ZO-EG’s best operating point. Figure 10 shows that ZO-EG’s performance is sensitive to both parameters, and even at its best configuration, it does not match CAMW (horizontal reference line) on stable games. F.9
Ablation: Wall-Clock Time
Figure 11 reports per-round wall-clock time as a function of ground-set size n. CAMW’s per-round cost is dominated by the O(n log n) sorting step for permutation detection, which is modest compared to ZO-EG’s O(d · n) function evaluations. For n ≤ 100, CAMW’s overhead is < 2× that of OLMDA and < 0.5× that of ZO-EG. 26
Oracle vs implementable tracking
102
Measured SCT
y=x SCobs T SCTBR
101 101
102
Designed SCT
c T (observed online) closely matches oracle-based Figure 8: Tracking ablation. The implementable SC tracking, validating Theorem 3.4.
OLMDA: Step size sensitivity
CAMW: Step size sensitivity 1.1 1.0
0.010
0.010
y
0.8 0.7
0.100
Avg regret
y
Avg regret
0.9
0.100
0.6
00 0.1
0.0
10
0.1 00
0.0 10
0.5 x
0.31550 0.31525 0.31500 0.31475 0.31450 0.31425 0.31400 0.31375
x
(a) OLMDA: sensitive to ηx .
(b) CAMW: broad plateau.
Figure 9: Step-size sensitivity (ηx × ηy heatmaps). CAMW is robust across a wide range of step sizes; OLMDA requires careful tuning.
F.10
Shortest-Path Game (Full Results)
Figure 12 provides a secondary phase-transition summary of the shortest-path results across grid sizes k ∈ {5, 6, 8, 10, 12} with T = 50,000 and region-switch counts RST ∈ {2, 5, 10, 20, 50, 100, 200}. The primary quantities remain the absolute-regret and normalized-regret curves reported in the main text; here we compress them into the ratio MW-with-restarts regret / OGD-FW regret, where values above 1 mean OGD-FW is better. Key observations: (i) For k = 5 (d = 40, N = 70) and k = 6 (d = 60, N = 252), MW-with-restarts dominates across all tested RST values — the small d/ log N ratio keeps the polyhedral rate favourable even at high instability. (ii) For k = 8 (d = 112, N = 3,432), the ratio crosses 1 near RST = 10, consistent with the predicted RS⋆T = d/ log N ≈ 14. (iii) For k = 10 (d = 180, N = 48,620) and k = 12 (d = 264, N = 705,432), OGD-FW wins at low RST — these large-d instances require many region switches before MW-with-restarts becomes 27
(b) ZO-EG: sample count
CAMW
0.450 0.425 0.400 0.375 0.350 0.325
Average regret
Average regret
(a) ZO-EG: sensitivity
10 2
Smoothing
10 1
CAMW
0.7 0.6 0.5 0.4 0.3
4
6
8
Number of samples d
10
Figure 10: ZO-EG smoothing sensitivity. Sweeping µ and sample count d; the CAMW reference line shows that structure-adaptive methods dominate even the best-tuned ZO-EG on stable games.
Time/round (ms)
Wall-clock scaling
101
OLMDA CAMW (ours) OGD ZO-EG
101
2 × 101 3 × 101 4 × 101
n
Figure 11: Wall-clock time vs. ground-set size n. CAMW adds modest overhead over OLMDA and is faster than ZO-EG for all tested n. competitive, confirming that the phase transition threshold scales as d/ log N . (iv) The crossover shifts monotonically to higher RST as d increases relative to log N , exactly as Theorem 4.5 predicts. F.11
Phase-Transition Crossover Analysis: Extended SNAP Results
Figure 14 reports the extended SNAP experiment with T up to 20,000 on Wiki-Vote (n = 787, T /n up to 25) and Epinions (n = 2,744, T /n up to 7.3). As in the main text, we interpret the absoluteregret plots jointly with the observed switch counts, which remain O(1) throughout this range, and use the theory normalization only to distinguish instability effects from horizon-vs.-dimension effects. At all tested T /n ratios,pOLMDA dominates—a predicted p limitation consistent with Theorem 4.5: when T /n is small, the n/T continuous rate beats the (1+SCT ) log n/T experts rate because T has not yet overcome the log n vs. n dimension gap. On Wiki-Vote, OLMDA’s regret decreases from 28
MW-Restarts / OGD regret ratio
Phase transition crossover
3.5
k = 5 (d = 40, NOGD = 70)wins above k = 6 (d = 60, N = 252) k = 8 (d = 112, N = 3, 432) k = 10 (d = 180, N = 48, 620) k = 12 (d = 264, N = 705, 432)
3.0 2.5 2.0 1.5 1.0 0.5 101
102
RST
Figure 12: Phase transition crossover in the shortest-path game (T = 50,000, 10 seeds). The ratio MW-with-restarts / OGD-FW is plotted against RST for five grid sizes; ratio > 1 means OGD wins. For k ≤ 6, MW-with-restarts dominates at all RST ; for k = 8, the crossover occurs near RST ≈ 10; for k = 10, 12, OGD wins at low RST due to the large d/ log N ratio. Dotted vertical lines mark the theoretical thresholds RS⋆T = d/ log N .
(a) Wiki-Vote (n = 1, 979)
102
(b) Epinions (n = 2, 744) 104 103 102
0
1000
Round t
2000
(c) SCBR T trajectory
5
SCBR T =5
Cumulative SCBR T
BR = 5 CAMWSC(ours) T OLMDA OGD
Average regret
Average regret
103
Wiki-Vote Epinions
4 3 2 1 0
0
1000
Round t
2000
0
1000
Round t
2000
Figure 13: Large-scale SNAP (T = 2,000, 3 seeds). (a,b) OLMDA leads at T /n ≈ 1. (c) SCBR T confirms SCT = O(1) ≪ T at scale. 16.0 to 5.1 as T /n grows from 1.3 to 25.4; on Epinions, OLMDA remains roughly flat (≈ 106–111) because T /n ≤ 7.3 is insufficient for convergence at this scale. All MW-based algorithms improve steadily with T /n as each epoch gains more rounds. WS-CAMW consistently achieves 2–3× lower regret than standard CAMW by warm-starting weights across epoch boundaries. F.12
Extended Dimension Scaling (n ≤ 1,000)
Figure 15 extends the normalized dimension-scaling experiment to n = 1,000 with T = 20,000 and p SCT = 0. CAMW’s regret normalized by log n/T remains flat (CV = 0.12) across two p orders of magnitude in n, while OLMDA’s ratio grows to 23× at n = 1,000. OGD normalized by n/T is flat √ √ √ (CV = 0.15), confirming the n baseline rate. The separation between log n and n complexity classes exceeds an order of magnitude at n = 1,000, consistent with the theoretical prediction.
G
Extended Related Work
Online p convex optimization. Standard OCO [19, 9] and online submodular methods [10] yield O( n/T ) rates. These approaches treat polyhedral objectives as generic convex functions, p and thus do not exploit the piecewise-linear structure. Zeroth-order approaches [7] achieve O( pN P̄N ) duality gap but also do not exploit polyhedrality. Convex-concave methods [13] yield O( n/T ) 29
Average regret
(a) Wiki-Vote (n = 787)
(b) Epinions (n = 2, 744) OLMDA WS-CAMW CAMW OGD Fixed-Share
102
OLMDA WS-CAMW CAMW OGD Fixed-Share
103
101 102
T/n
101
100
T/n
Figure 14: Extended SNAP regret vs. T /n (T = 1,000–20,000, 3 seeds). (a) Wiki-Vote (n = 787): OLMDA regret 16 → 5 as T /n grows. (b) Epinions (n = 2,744): OLMDA dominates at all T /n ratios. WS-CAMW achieves 2–3× lower regret than CAMW throughout.
(b) Normalized by n/T
20
Min. regret / n/T
Min. regret / logn/T
(a) Normalized by logn/T 15 10 5 0
10
100
n
CAMW (ours)
2.0 1.5 1.0 0.5 0.0
1000
CAMW-no-restart (ours)
10
100
n
OLMDA
1000
OGD
Figure 15: Extended dimension scaling (T = 20,000, SCT = p0, 5 seeds, n ∈ {10, 20, 50, 100, 200, 500, 1,000}). Left: CAMW’s regret normalized by p log n/T is flat, con√ firming log n scaling; OLMDA diverges. Right: OGD normalized by n/T is flat, confirming √ √ n; CAMW decreases, confirming its sub- n rate. rates that scale We exploit the polyhedral structure of the Lovász extension, √ √ with ambient dimension. replacing n dependence with log n in geometrically stable regimes. Online submodular optimization. Hazan p and Kale [10] studied online submodular minimization via the Lovász extension, achieving Õ( n/T ) regret. Their analysis does not leverage the combinatorial cell structure and yields dimension-dependent guarantees even when equilibria remain stable. Adaptive regret bounds. Path-length and variation bounds [11, 6, 18] adapt to Euclidean motion of the loss sequence. For polyhedral objectives, within-cell motion is benign while infinitesimal boundary crossings change the linear regime entirely—RST is strictly incomparable with both path-length and variation (Section E.4). Tracking and switching experts. Fixed-Share MW [12] handles switching experts but pays mixing p cost during stable epochs and cannot reset learning rates at region boundaries. It achieves O( T (S log N + log T )) regret with S switches by continuously mixing toward uniform. While effective for slowly drifting experts, it cannot exploit sharp region boundaries: it pays mixing cost even 30
during p stable epochs and cannot reset its learning rate. Our MW-with-restarts achieves the tighter O( (1+RST ) T log Vmax ) by restarting at detected boundaries. Non-stationary bandits [3, 17] adapt to distribution changes but measure change through ℓ1 shift or breakpoints, not through combinatorial structure. The distinction from SCT is formalized in Theorem E.1. Combinatorial online learning. Combinatorial bandits [5, 2] measure complexity through dimension or sparsity. Our work identifies a different axis: the stability of the polyhedral cell decomposition.
31