PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

Akira Kitaoka

arXiv:2609.09809v1cs.LGcs.DSmath.OC

TL;DR

Online inverse linear optimization still has an open question: can regret be bounded independently of the number of rounds, polynomially in dimension, and with light computation for general forward problems? This paper introduces Small-Gradient Skipping under a uniform margin and shows that its algorithms have mistake bounds independent of the number of rounds, with a log T-free regret bound for specified integer programs.

  • Problem

    Whether a regret guarantee independent of T, polynomial in dimension, and lightweight for general forward problems including integer programs was open.

    Source: §1 · p. 2

  • Method

    Under a uniform margin, Small-Gradient Skipping skips updates on mistake-free rounds and is applied to online gradient descent, the online Newton step, and MetaGrad.

    Source: §1 · p. 2

  • Results

    For simplex ILPs, ONS and growing-grid SGS-MetaGrad attain regret O(d^2||M||^2 log(2||M||^2)), removing log T dependence; all three methods bound mistakes independently of T.

    Source: §8 · p. 12

  • Takeaways & Limitations

    Under a uniform margin, the results provide a deterministic, light-update regret bound with polynomial dimension dependence for integer programs.

    Source: §8 · p. 12

    The analysis is restricted to noiseless feedback, leaving extensions to suboptimal or corrupted feedback for future work.

    Source: §8 · p. 12

Abstract

from arXiv · show

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of $\log T$ between the regret upper bound $O(d \log T)$ and the lower bound $Ω(d)$ is unresolved (here $T$ is the total number of rounds and $d$ is the dimension). When the action set is M-convex, the regret is known to be bounded by $O(d \log d)$, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake in the case where the correct action is uniformly separated from the other candidates, and applies it to online gradient descent, the online Newton step, and MetaGrad. The number of mistakes is then bounded, for all three, by a quantity independent of $T$; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes $O(d^2)$ when the forward problem is an integer linear program, that is, the factor $\log T$ is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

1. Introduction

The paper introduces Small-Gradient Skipping (SGS), which skips updates on correct rounds under a uniform margin, and applies it to obtain mistake and regret guarantees independent of T. For ILPs with simplex weights, ONS and growing-grid SGS-MetaGrad achieve regret bounds polynomial in the dimension without a log T factor.

Introduction

  • The work addresses the unresolved gap between the O(d log T) regret upper bound and Ω(d) lower bound, as existing T-independent guarantees have exponential dimension dependence, gap dependence, or costly center-of-gravity computation.The cited limitations are respectively exp(O(d log d)), dependence proportional to the inverse square of the gap, and center-of-gravity computation at every round.Source: §1 · pp. 1–2

Contributions

  • Under a uniform margin γ > 0, SGS leaves both the iterate and internal state unchanged whenever the proposal is correct, yielding finitely many mistakes.For an integer linear program, the margin is automatically positive and can be bounded below using the feasible set’s combinatorial structure.Source: §1 · p. 2
  • Applied to OGD, ONS, and MetaGrad, SGS yields mistake and regret bounds independent of T, with explicit problem-class bounds obtained from structural lower bounds on the margin.The guarantees are stated in terms of mistakes rather than total rounds.Source: §1 · p. 2
  • For ILPs with simplex weights, ONS and growing-grid SGS-MetaGrad achieve regret O(d^2||M||^2 log(2||M||^2)), with O(d^2) computation plus one generalized projection per mistake round.The bound is independent of T; growing-grid SGS-MetaGrad incurs an additional log K factor in total computational cost, where K is the number of mistakes.Source: §1 · pp. 2–3

2. Related work

Prior work establishes finite updates under margin or gap conditions and constant regret in online inverse optimization, but this paper formulates skipping for first- and second-order online convex optimization methods. Its guarantees require only a uniform margin and include explicit bounds derived from feasible-set structure.

Finitely many updates under a margin condition: the classical line

  • Margin-based finite updates trace from the Perceptron and ALMA to inverse optimization (Sun et al., 2023), but those classification results do not directly apply to suboptimality loss.Skipping correct or nearly optimal rounds also appears in Gollapudi et al. (2021) and Besbes et al. (2021, 2025); this paper formulates it for first- and second-order online convex optimization methods.Source: §2 · p. 3

Finite regret in online inverse optimization

  • Under a uniform margin alone, the algorithms give T-independent guarantees, with each mistake round costing O(d^2) plus one generalized projection onto Θ.The paper also derives explicit lower bounds on the uniform margin from feasible-set combinatorial structure and reduces them to explicit upper bounds by problem class.Source: §2 · p. 4
  • Earlier T-independent regret bounds assume a gap (Sakaue et al., 2025a), M-convexity (Oki and Sakaue, 2026), or neither margin nor gap (Gollapudi et al., 2021, Theorem 4.2).Unlike those works, this paper requires no structure beyond a uniform margin.Source: §2 · p. 4

3. Problem setting

The section formulates online inverse linear optimization: an agent with an unknown weight chooses optimal actions, and a learner predicts that weight from observed states and actions. It defines the learner’s proposals and performance criteria, with the paper’s guarantees bounding cumulative suboptimality and decision regret together independently of T.

3. Problem setting

  • At each round, the agent selects an action optimal for its unknown weight in the given state, and the learner predicts that weight from past state-action observations.The inverse problem is to find a weight whose optimal actions explain the agent’s observed choices.Source: §3 · pp. 4–5
  • The learner’s proposal is an extreme optimal solution for its predicted weight, chosen from the extreme points of the convex hull of feasible actions.The linear objective has the same optimal value over the convex hull as over the original action set.Source: §3 · p. 5
  • The paper bounds the sum of cumulative suboptimality and decision regret independently of T, thereby bounding both criteria simultaneously.Suboptimality loss measures how poorly the learner’s weight explains the agent’s action; decision regret measures how suboptimal the learner’s proposal is under the true weight.Source: §3 · pp. 5–6
  • The setting assumes bounded, closed, convex prediction weights, compact feasible-action sets with finitely many extreme points, and a unique agent-optimal action for every state.Assumption 3.1 also includes a uniform-margin condition.Source: §3 · p. 6

4. Proposed method: small-gradient skipping (SGS)

Small-gradient skipping (SGS) updates the learner only after mistakes, leaving its iterate and internal state unchanged on correct predictions. The paper applies SGS to online gradient descent, ONS, and MetaGrad.

Definition and mechanism

  • On a no-mistake round, SGS leaves the iterate and internal state unchanged; on a mistake, it updates with g = ˆxt − xt and advances the state index.The iterate is updated only at mistake rounds.Source: §4 · pp. 6–7
  • At a no-mistake round, the oracle-based subgradient is zero, which is a minimum-loss subgradient that SGS skips.The loss is zero and 0 ∈ ∂θℓsub(ˆθt, st).Source: §4 · p. 6

Algorithm effects

  • For ONS and fixed-grid MetaGrad, SGS does not change the algorithm; for round-index-dependent updates, it can change the algorithm and base learning-rate-grid refinement on mistakes.The passage contrasts SGS-OGD's αk^-1/2 with αt^-1/2 and says growing-grid SGS-MetaGrad refines its grid by mistake count.Source: §4 · pp. 6–7

Instances of SGS

  • SGS is applied to projected online gradient descent, ONS, and MetaGrad, including a variant that grows its learning-rate grid with the number of mistakes.The passage identifies ONS as second-order and MetaGrad as universal.Source: §4 · p. 7

5. Main results: finitely many mistakes and regret independent of T

Under Assumption 3.1, SGS-OGD, ONS, and growing-grid SGS-MetaGrad have deterministic mistake and regret guarantees whose bounds do not depend on T. Their updates or analyses use mistake rounds, while growing-grid SGS-MetaGrad removes the fixed-grid dependence on an a priori mistake bound.

Methods

  • SGS-OGD takes a projected subgradient step only on mistake rounds, while ONS’s iterate and information matrix stay unchanged on rounds without mistakes.SGS-OGD uses step size αk^-1/2, where k counts mistakes; both methods’ only parameters are L and D.Source: §5 · p. 7
  • Growing-grid SGS-MetaGrad refines its learning-rate grid as mistakes accrue, replacing the fixed-grid a priori bound with the realized mistake count and making its guarantee independent of T.With a grid fixed before execution, the bound retains a c0(K̄) factor that is O(log log T) when K̄ = T; growing the grid removes that dependence.Source: §5 · p. 7

Main results

  • For arbitrary, possibly adaptive state sequences, all three methods have deterministic bounds on mistakes, cumulative suboptimality regret, and the sum that are independent of T.The cumulative decision regret has the same upper bound as the regret of the sum.Source: §5 · p. 8, Table 2 · p. 8

Comparison of the methods

  • ONS improves SGS-OGD’s margin dependence from γ^-2 to γ^-1 for mistakes and from γ^-1 to log γ^-1 for cumulative suboptimality regret, at the price of linear dependence on d.Growing-grid SGS-MetaGrad achieves the same order as ONS with worse constants; its Lipschitz-adaptive version does not require L.Source: §5 · p. 8

6. Integer programming and lower bounds on the uniform margin

The section turns combinatorial lower bounds on the uniform margin γ into explicit mistake and regret bounds: general ILPs have finite bounds, while M-convexity yields polynomial dimension dependence.

6. Integer programming and lower bounds on the uniform margin

  • General ILPs admit an unconditional finite upper bound using an explicit, positive but exponentially small lower bound on γ; M-convexity improves the lower bound to polynomial in the dimension.Substituting the margin bounds into the closed-form upper bounds makes the mistake and cumulative regret bounds explicit.Source: §6 · pp. 8–9

6.1. The largest attainable margin.

  • Under (1), (2), and (3) of Assumption 3.1 and 0 < L_sub < ∞, the maximum defining γ_sub is attained; if γ_sub > 0, a maximizer gives a valid margin γ = γ_sub with L = L_sub.Source: §6.1 · p. 9

6.2. Explicit lower bounds for general ILPs.

  • Explicit lower bounds on γ_sub are derived by feasible-set combinatorial structure and summarized for the probability simplex and unit ball in Table 3 for d ≥ 2.The unit-ball bound requires full dimensionality; the simplex bound is unconditional.Source: §6.2 · pp. 9–10, Table 3 · p. 10

7. Explicit upper bounds on the number of mistakes and the regret by problem class

The section gives explicit regret bounds by problem class, showing that ONS and growing-grid SGS-MetaGrad achieve T-independent regret for general ILPs and efficient bounds for M-convex structures.

7. Explicit upper bounds on the number of mistakes and the regret by problem class

  • For general ILPs, ONS and growing-grid SGS-MetaGrad achieve regret O(d^2 ||M||_2 log(2||M||_2)), independent of T.The bounds are polynomial in dimension and depend linearly on ||M||_2.Source: §7 · p. 10
  • Compared with Sakaue et al. (2025b), the general-ILP bound removes log T while increasing the dimension power by one.Compared with Gollapudi et al. (2021, Theorem 4.2), it replaces exp(O(d log d)) with a polynomial-in-d bound, assuming a uniform margin and depending linearly on ||M||_2.Source: §7 · p. 10
  • For M-convex and M♮-convex structures, regret is O(Ld log(2dL)), versus O(d log d) for Oki and Sakaue (2026) under their normalization.Without that normalization, their bound becomes O(||θ*|| L d log d); the bounds differ only in the logarithm's argument.Source: §7 · p. 11
  • For M-convex and M♮-convex structures, updates require O(d^2) computation plus one generalized projection per mistake round, while Oki and Sakaue (2026) compute a center of gravity every round.Their number-of-mistake-rounds bound does not depend on the normalization.Source: §7 · p. 11

8. Conclusion … B.4. Growing-grid SGS-MetaGrad.

This section presents small-gradient skipping (SGS) guarantees and implementations, including T-independent mistake and regret bounds under margin conditions and explicit ILP guarantees. It also develops fixed- and growing-grid MetaGrad variants, relates the guarantees to prior work, and identifies open problems.

8. Conclusion

  • O(d^2∥M∥^2 log(2∥M∥^2)): for probability-simplex ILPs, ONS and growing-grid SGS-MetaGrad attain this decision-regret bound, while all three SGS methods bound mistakes and both regret measures independently of T under a uniform margin.The three measures are the number of mistakes, cumulative suboptimality regret, and cumulative decision regret.Source: §8 · p. 12
  • A factor d and coordinatewise-range terms separate the ILP decision-regret upper bound from the known Ω(d) lower bound; extending SGS to noise or corruption remains future work.The analysis is restricted to noiseless feedback; under corruption, the uniform-margin progress weakens and the ONS quadratic-term analysis would need a per-round corruption-dependent inequality.Source: §8 · p. 12

Appendix A. Related work in detail

  • A single witness with a uniform margin simultaneously bounds mistakes and suboptimality regret independently of T, without requiring integral θ* or M-convex actions; combinatorial structure gives explicit margin lower bounds.Source: Appendix A · p. 16

B.2. ONS.

  • O(d^2) matrix updates and generalized projections are skipped on no-mistake rounds; SGS-ONS retains plain ONS iterates while its analysis gives T-independent mistake and suboptimality-regret bounds.Source: §B.2 · p. 18

B.3. MetaGrad.

  • In SGS-MetaGrad, experts, weights, and the index advance only on mistake rounds; building the learning-rate grid from mistakes enables a T-independent guarantee, and growing the grid removes the need for an upper bound on K.Source: §B.3 · p. 19
  • Under a uniform margin, fixed-grid SGS analysis gives MetaGrad a T-independent guarantee without changing its sequence of iterates.At mistake-free rounds, the gradients and expert updates are zero; SGS can also omit expert updates then, and a known mistake upper bound can reduce the grid size.Source: §B.3 · p. 21

B.4. Growing-grid SGS-MetaGrad.

  • The growing-grid SGS-MetaGrad bounds both mistakes and cumulative suboptimality regret by constants independent of T.Its grid grows with the realized mistake count K, replacing the fixed upper bound on mistakes in the analysis.Source: §B.4 · p. 21
  • Refining the grid by mistake count preserves freezing, whereas refinement by round would change state on mistake-free rounds and leave an O(log log T) factor.The growing-grid algorithm generally differs from round-refined anytime MetaGrad because earlier-created experts receive subsequent mistake-round updates.Source: §B.4 · pp. 21–22
  • The logarithmic-term coefficient changes from 152/3 ≈ 50.7 to 52, while per-mistake-round cost scales with 1 + ⌈1/2 log2 K⌉ created experts, independent of T.The algorithm’s parameters are L and D.Source: §B.4 · p. 22
  • With Lipschitz adaptation, the guarantee keeps the same order but changes the logarithm’s argument from K/d to DLK/d, requiring only prior knowledge of D.The explicit constants are not tracked in this O(·)-form result.Source: §B.4 · p. 23

B.5. Comparison of the performance criteria with existing methods.

The section distinguishes cumulative decision regret from cumulative suboptimality regret and shows that, under a uniform margin, the proposed methods bound both criteria simultaneously and independently of T.

B.5. Comparison of the performance criteria with existing methods.

  • Prior work on online inverse linear optimization evaluates cumulative decision regret and does not necessarily claim a bound on cumulative suboptimality regret.Source: §B.5 · p. 23
  • An upper bound on either solution regret or suboptimality regret alone does not imply a bound on the other; bounding their sum controls both.Source: §B.5 · p. 23
  • Bärmann et al. (2018) use total error, which decomposes into objective-function error and solution error.Source: §B.5 · p. 23
  • Under uniform margin (Assumption 3.1), all three proposed methods bound the total error independently of T, thereby bounding both criteria simultaneously.Source: §B.5 · p. 24
  • Table 6 distinguishes existing methods without a uniform-margin assumption from proposed methods under Assumption 3.1, and marks criteria without a claimed upper bound.The ‡ mark denotes bounds on the sum that control both criteria, while † applies only when the feasible set is M-convex.Source: §B.5 · p. 24, Table 6 · p. 25

Appendix C. Analysis of SGS-OGD (proof of Theorem C.2)

Appendix C analyzes SGS-OGD using only mistake rounds, where the uniform margin separates the mistake-round loss from the quantity driving the update. It also treats the comparator-relative regret separately because the comparator need not satisfy that margin.

Lemma C.1

  • At every mistake round, ℓ_tk + γ ≤ r_tk ≤ LD, so r_tk is strictly positive.The lower bound follows from the uniform margin; the upper bound uses the gradient and diameter bounds.Source: Appendix C · p. 26

Theorem C.2 proof

  • No-mistake rounds have zero suboptimality loss and leave the iterate unchanged, so SGS-OGD has at most K + 1 distinct iterates.The analysis reindexes the sequence by its K mistake rounds.Source: Appendix C · pp. 25, 26, 28

Theorem C.2 proof: potential estimate

  • For arbitrary u ∈ Θ, the proof bounds a projected-distance potential using nonexpansiveness, the decreasing step sizes, and Abel summation.The potential argument uses only u ∈ Θ, including the bound on its squared distance to the iterates.Source: Appendix C · p. 27

Theorem C.2 proof: comparator case

  • For θ*, the comparator-relative cumulative term sums only over mistake rounds and each term is at most LD; the margin lower bound is unavailable because θ* need not satisfy the margin.The proof therefore handles this case separately, using monotonicity of the square root and a bound on K.Source: Appendix C · pp. 26, 28

Appendix D. Analysis of ONS (proof of Theorem D.6) · Appendix E. Analysis of MetaGrad (proof of Theorem E.1) · E.1. The guarantee of the fixed-grid version.

The ONS analysis bounds cumulative regret on mistake rounds and uses that bound to establish finite-mistake and regret guarantees. The fixed-grid MetaGrad guarantee has the same dependence on dimension and separation but carries grid-related costs.

Appendix D. Analysis of ONS (proof of Theorem D.6)

  • The ONS proof bounds the sum of mistake-round regrets by 1 + d log(1 + K/d), using a log-determinant bound that telescopes over updates.The argument sums log det Σ_k terms and bounds the final determinant using the eigenvalues of Σ_K.Source: Appendix D · pp. 28, 30
  • Under Assumption 3.1, Theorem D.6 gives bounds for ONS’s mistake count and cumulative suboptimality and decision regret for every T.The supplied theorem statement identifies these guarantees, though its displayed bound expressions are fragmented.Source: Appendix D · p. 30
  • The ONS proof gives K ≤ KONS := d + β(1 + d log max(β, 1)) and substitutes this mistake-round cutoff into its cumulative-regret bound.The displayed passage defines the bound in terms of β but does not provide its definition in the supplied text.Source: Appendix D · p. 31

E.1. The guarantee of the fixed-grid version.

  • Fixed-grid MetaGrad has the same dependence on γ and d as ONS: O(dLD/γ) mistakes and O(LD d log max(LD/γ, 1)) cumulative suboptimality regret.The comparison passage also notes worse constants for MetaGrad.Source: §E.1 · p. 31
  • The fixed-grid guarantee depends doubly logarithmically on the grid upper bound; setting K̄ = T introduces O(log log T) dependence, so strict T-independence is lost.The passage says this dependence is removed by the growing-grid version of MetaGrad.Source: §E.1 · p. 31
  • At each mistake round, fixed-grid MetaGrad incurs per-round computational cost multiplied by the grid size, and its parameters L, D, K̄ require no knowledge of γ.The passage describes 1 + ⌈(1/2) log² K̄⌉ experts, each using O(d²) computation plus a generalized projection.Source: §E.1 · p. 32

E.2. Proof. · 3 LD, Equation (E.12) gives

The proof establishes a grid-based MetaGrad regret bound and applies it to the sequence of mistake rounds, then derives the stated mistake and regret bounds. It handles the unknown number of mistakes by fixing the grid using an upper bound in advance.

E.2. Proof.

  • Proposition E.3 bounds MetaGrad’s linearized regret for convex losses when the domain diameter, subgradient norm, and subgradient inner-product range are bounded.Its grid can be fixed using an upper bound on the number of rounds; this is needed because the realized mistake count is unknown before execution.Source: §E.2 · pp. 32, 34
  • The proof combines a fixed-grid potential bound with the regret bound for a single η-expert to control regret at each grid scale.Lemma E.5 gives Φ_m ≤ 1 and a term bounded by 2 log(i + 2); Proposition E.4 bounds the expert’s contribution by B_m.Source: §E.2 · pp. 32–33
  • On mistake rounds, Algorithm 5 is MetaGrad on the loss sequence of length K, with G = L and H = LD.The proof verifies the subgradient and bounded-gradient assumptions and uses K ≤ K̄ to apply Proposition E.3.Source: §E.2 · p. 34
  • The mistake-bound derivation converts Equation (E.12) into an inequality in K/d and solves it to obtain Equation (E.1).It uses γK ≤ R and the auxiliary inequality y ≤ c1 + c2 log(1 + y).Source: §E.2 · p. 35

3 LD, Equation (E.12) gives

  • The proof bounds the maximized function ψ by ρd log max(ρ/γ, 1), yielding Equation (E.2).When γ ≥ ρ, ψ is nonincreasing; otherwise the proof evaluates it at its stationary point.Source: §3 · p. 35
  • For comparator θ*, the proof replaces mistake-round regret r_tk with excess regret er_tk because rounds without mistakes contribute zero.It applies Proposition E.3 with u = θ* and uses the resulting bound to derive Equation (E.3).Source: §3 · p. 35
  • Substituting K ≤ Kmax into the increasing right-hand side gives Equation (E.3).The substitution uses the mistake bound established in part (i).Source: §3 · p. 35

Appendix F. Analysis of growing-grid MetaGrad (proof of Theorem F.3) · 5. From the elementary inequality

Appendix F proves bounds for growing-grid MetaGrad by treating not-yet-created experts as virtual experts that output the master’s point. The resulting SGS-MetaGrad bounds have no dependence on the total number of rounds T.

Appendix F. Analysis of growing-grid MetaGrad (proof of Theorem F.3)

  • The analysis treats each not-yet-created η_i-expert as a virtual expert that outputs the master’s point, enabling a monotonicity argument for the potential.The potential remains at most its initial value, Φ_0 = 1, yielding −L_i_m ≤ log((i + 1)(i + 2)) for every grid index i.Source: Appendix F · p. 36
  • Growing-grid MetaGrad assigns prior weights π_i = 1/((i + 1)(i + 2)) to a countable η_i grid and creates experts on a schedule, running ONS after creation.The master point sums over already-created experts without normalizing their weights.Source: Appendix F · p. 36

5. From the elementary inequality

  • Proposition F.1 provides a deterministic upper bound on linearized regret for every comparator u in W, which the proof applies to the sequence of mistake-round losses.The theorem proof instantiates the proposition with n = d, W = Θ = D, G = L, and H = LD.Source: Appendix F · p. 36, §5 · p. 38
  • Theorem F.3’s proof derives bounds by controlling the potential-related terms with an elementary inequality and splitting the analysis into cases for the comparator’s optimal learning rate.It bounds the first term using log((i + 1)(i + 2)) and the expert’s regret using Proposition E.4.Source: §5 · pp. 36–37
  • Theorem F.3 bounds mistakes and cumulative decision regret independently of T, with a doubly logarithmic factor depending on d rather than T.The bounds are stated in terms of the theorem’s right-hand sides; the supplied passages do not expose all their formulas.Source: §5 · p. 38
  • Applying Proposition F.1 to a comparator θ* also bounds cumulative regret on all rounds, since rounds without a mistake contribute zero to that comparison.The proof uses the bound on mistake-round regret to obtain the explicit bound for total cumulative regret.Source: §5 · p. 39

Appendix G. Lower bounds on the margin by structure … Appendix H. Proofs for §6, I: general theory

These appendices develop margin lower bounds for integer optimization using structural properties of feasible sets and test sets, and provide proofs for the general theory. The bounds depend on the setting, with some unresolved low-dimensional cases.

Appendix G. Lower bounds on the margin by structure.

  • For general ILPs, the appendices give explicit margin lower-bound results for the unit ball and probability simplex; the simplex result needs no full-dimensionality assumption.For the unit ball, the stated full-dimensional case is supplemented by a bound when 0 is outside aff Z*, while the case 0 ∈ aff Z* with lower dimension remains unresolved.Source: Appendix G · pp. 40–41

G.1. General theory of lower bounds via test sets.

  • A test set lets any nonoptimal feasible point reach an optimal point through finitely many improving directions, yielding a lower bound on the margin from sign-consistent directions.The margin bound applies when the same test set works for every feasible set X(s).Source: §G.1 · p. 41

G.2. Definitions from discrete convex analysis and Graver bases.

  • The appendix defines M-convex and M♮-convex sets through exchange axioms and defines a Graver basis as the sign-minimal nonzero integer kernel vectors.M-convex sets are integer points of integral base polyhedra; M♮-convex sets are integer points of generalized integral base polyhedra.Source: §G.2 · pp. 41–42

G.3. Polynomial lower bounds for M-convex and M♮-convex structures.

  • M-convex and M♮-convex feasible sets have polynomial margin lower bounds, with test sets given by single exchanges and exchanges plus signed unit vectors, respectively.The cited theorems specify the unit-ball setting; the M♮-convex result assumes d ≥ 2.Source: §G.3 · p. 42, §G.4 · p. 44

G.4. General lower bounds for linear inequality constraints: independence of ∥M∥2.

  • For linear inequality constraints, the margin lower bounds depend on the coefficient matrix’s Graver-basis norm, not on the right-hand side or feature range; for totally unimodular A, Cg = 1.The unit-ball result assumes the convex hull of improving test directions is full-dimensional; the probability-simplex result does not state that condition.Source: §G.4 · p. 43

Appendix H. Proofs for §6, I: general theory.

  • The proofs establish finite improvement sequences for test sets and use compactness and minimax to relate margin bounds to the convex hull of feasible-point differences.The proof of the test-set margin bound applies the improvement sequence to each nonoptimal feasible point and takes the infimum over states and candidates.Source: Appendix H · pp. 44–45

Appendix I. The separating hyperplane theorem and a lemma on the norm of the normal vector … Appendix M. Proofs of the lower bounds via Graver bases

These appendices establish separation and lattice-normal results and derive lower bounds for submodularity margins and M-convex structures, including positive separation bounds from bounded Graver-basis test directions.

Appendix I. The separating hyperplane theorem and a lemma on the norm of the normal vector

  • A bounded convex polytope can be separated from an outside point by a halfspace whose boundary spans d affinely independent vertices; the proof also constructs an integral separating normal for the lattice setting.The lattice argument uses determinant-based normals and norm estimates to establish the claimed bound.Source: Appendix I · pp. 46–47

Appendix K. Proof of Theorem G.4

  • Theorem G.4’s proof constructs a nonnegative integral normal separating the origin from a polyhedron built from the lattice set, then combines estimates to establish its claim.The normal is constructed from cofactors of an integer matrix formed using facet vertices and coordinate directions.Source: Appendix K · pp. 48–49

2. Hence

  • The Appendix K proof concludes by combining bounds (K.1), (K.3), and (K.4) to establish its claim.Source: §2 · p. 50

Appendix L. Proofs of the lower bounds for M-convex and M♮-convex structures

  • For σ(i) = (d − i) · 2/(d(d − 1)) for i = 1, …, d, θ† ∈ ∆d−1; the adjacent-rank difference is 2/(d(d − 1)), yielding γsub ≥ 2/(d(d − 1)) by Proposition G.7.Source: Appendix L · p. 51
  • γ_sub ≥ 2d(d+1) for the M-convex and M♮-convex lower-bound construction.Source: Appendix L · p. 51

Appendix M. Proofs of the lower bounds via Graver bases

  • Graver-basis decomposition yields a feasible improving direction whose infinity norm is bounded by the Graver bound C_g.Source: Appendix M · pp. 51–52
  • For the Euclidean-norm bound, γ_sub is at least the distance from 0 to Conv(S+).Source: Appendix M · p. 52
  • γ_sub ≥ min_{q∈Conv(S+)} max_i q_i > 0 for the Graver-basis lower bound.Source: Appendix M · p. 52

Appendix N. Derivation of the explicit upper bounds by problem class · Appendix O. Derivation of the entry of Sakaue et al. (2025a) in Table 1

Appendix N derives explicit bounds by substituting problem-class separation guarantees into general bounds, while Appendix O derives the Sakaue et al. (2025a) entry in Table 1. The derivations specify their assumptions and parameter choices, including a caveat about the comparison bound’s constant and dependence on regularizer and norms.

Appendix N. Derivation of the explicit upper bounds by problem class

  • The class-specific bounds follow by substituting lower bounds on γ into Corollary N.1, whose bounds are nonincreasing in γ.For ILPs and linear inequalities, the derivation also uses L ≤ ∥M∥2; the simplified logarithms are log(2∥M∥2), log(2CgdL), and log(2dL) for ILPs, linear inequalities, and M-convex and M♮-convex cases, respectively, assuming L ≥ 1 and Cg ≥ 1.Source: Appendix N · pp. 53–54
  • For the M-convex case, eRT = O(Ld log(2dL)).The passage states that the M♮-convex case has changed constants in the separation bound but coincides in order.Source: Appendix N · p. 55
  • When L = O(d), the mistake count is O(d^4) to O(d^5) for SGS-OGD and O(d^3 log d) to O(d^(7/2) log d) for ONS.The passage does not give a corresponding mistake-count range for growing-grid SGS-MetaGrad.Source: Appendix N · p. 55

Appendix O. Derivation of the entry of Sakaue et al. (2025a) in Table 1

  • Sakaue et al. (2025a, Theorem 5.2) assumes a ∆-gap condition and bounds cumulative regret using L∞, a strongly convex regularizer, and an admissible constant B.L∞ upper-bounds the distance between the agent’s optimal action and an action induced by a prediction; the regularizer is λ-strongly convex with respect to the dual norm.Source: Appendix O · p. 55
  • On the probability simplex, Sakaue et al. (2025a) use the ℓ∞ action norm, ℓ1 weight norm, and entropic regularizer, yielding λ = 1 and B = Θ(√log d).The derivation uses that the simplex has ℓ1 diameter 2, the regularizer ranges over an interval of length log d, and L∞ is at most ∥M∥∞.Source: Appendix O · pp. 55–56
  • The numerical constant in the derived Sakaue et al. (2025a) bound is loose, and its form depends on the regularizer and norm pair.The entropic choice recovers the probability-simplex guarantee of Bärmann et al. (2018).Source: Appendix O · p. 56

Related papers

Loading 2609.09809v1…