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 seeks objective weights that explain observed optimal actions, but general regret bounds retain a log T gap and existing T-independent methods have limitations. The paper introduces Small-Gradient Skipping, which updates OGD, ONS, and MetaGrad only on mistake rounds under a uniform margin. For ILPs with simplex weights, ONS and growing-grid SGS-MetaGrad achieve O(d^2∥M∥2 log(2∥M∥2)) regret independent of T, while the paper also identifies remaining dimension and noise limitations.

  • Problem

    General online inverse linear optimization has an O(d log T) upper bound versus an Ω(d) lower bound, while existing T-independent guarantees have dimensional, gap, or computational limitations.

  • Method

    The paper introduces Small-Gradient Skipping, which freezes the iterate and internal state on correct rounds under a uniform margin and applies it to OGD, ONS, and MetaGrad.

  • Results

    For ILPs with simplex weights, ONS and growing-grid SGS-MetaGrad achieve O(d^2∥M∥2 log(2∥M∥2)) regret independent of T.

  • Takeaways & Limitations

    Under a uniform margin, the log T dependence is removed with deterministic light updates costing O(d^2) plus one generalized projection per mistake round.

  • Takeaways & Limitations

    The paper is restricted to the noiseless setting, and its ILP regret bound remains separated from the Ω(d) lower bound by a factor d and a coordinate-range factor.

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 addresses the unresolved gap between O(d log T) regret upper bounds and Ω(d) lower bounds in online inverse linear optimization. It proposes SGS-based methods whose guarantees are independent of T and polynomial in dimension for ILPs.

  • 1. Introduction: The open problem is obtaining regret independent of T and polynomial in dimension with light computation for general forward problems, including integer programs.Existing T-independent bounds are exponential in dimension, inverse-square in the gap, or require a center-of-gravity computation every round.
  • 1. Introduction: SGS skips updates at correct rounds under a uniform margin and bounds mistakes and regret in terms of the number of mistakes rather than total rounds.For ILPs, the uniform margin is automatically positive and can be bounded using feasible-set structure.
  • 1. Introduction: The paper applies SGS to OGD, ONS, and MetaGrad, with explicit computational and regret guarantees summarized in Table 1.The table compares decision regret and computational cost for ILPs with simplex weight spaces.
  • 1. Introduction: O(d^2∥M∥2 log(2∥M∥2)) regret removes the log T dependence for ONS and growing-grid SGS-MetaGrad on ILPs with simplex weights.The methods require O(d^2) computation plus one generalized projection per mistake round.

2. Related work

The paper places SGS within prior finite-update and finite-regret work in inverse optimization and online learning. Its distinction is applying skipping to first- and second-order online methods while deriving explicit problem-class bounds from combinatorial structure.

  • 2. Related work: SGS extends prior skipping mechanisms to first- and second-order online convex optimization methods whose internal states would otherwise advance without mistakes.The resulting guarantees are independent of T under a uniform margin.
  • 2. Related work: Earlier work established finite updates or constant regret under separability, gaps, M-convexity, or no margin, but with differing assumptions and computational limitations.The cited M-convexity result requires computing a center of gravity at every round.
  • 2. Related work: Unlike prior T-independent bounds, the paper requires only a uniform margin and uses O(d^2) computation plus one generalized projection per mistake round.It also lower-bounds the margin using the feasible set's combinatorial structure.

3. Problem setting

The problem setting has a learner infer an unknown objective vector from an agent's optimal actions across states. Predictions induce forward-problem proposals, and performance is measured through suboptimality and decision-regret quantities.

  • 3. Problem setting: At each round, the agent chooses an action optimal for the unknown objective θ* while the learner predicts a weight from past state-action observations.The inverse problem seeks a weight that rationalizes the observed actions as optimal.
  • 3. Problem setting: The learner's prediction induces an extreme optimal proposal by solving a linear optimization problem over the feasible action set.For ILPs, the oracle is required to return an extreme optimal solution when multiple optima exist.
  • 3. Problem setting: The paper evaluates predictions using cumulative suboptimality loss, cumulative decision regret, and their sum.The summed criterion is bounded independently of T by the paper's theorems.
  • 3. Problem setting: The model assumes bounded convex weight space, compact feasible action sets with finite extreme points, a unique true optimum, and a uniform positive margin.The margin separates the correct action from every other candidate uniformly across states.

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

Small-Gradient Skipping updates the learner only on mistake rounds, exploiting the zero subgradient produced when the predicted action matches the observed action. The mechanism is incorporated into OGD, ONS, and MetaGrad variants.

  • 4. Proposed method: small-gradient skipping (SGS): SGS leaves both the iterate and internal state unchanged when the proposal is correct, and advances them only after a mistake.At mistake rounds it uses the subgradient g = x̂t − xt and advances the internal-state index.
  • 4. Proposed method: small-gradient skipping (SGS): Correct rounds have zero suboptimality loss and admit the zero subgradient, which is why SGS can skip their updates.The oracle-based subgradient is exactly zero whenever no mistake occurs.
  • 4. Proposed method: small-gradient skipping (SGS): SGS is applied to projected OGD, ONS, and MetaGrad, including a growing-grid variant that refines learning rates according to mistakes.ONS and fixed-grid MetaGrad already keep their iterates unchanged when the subgradient is zero, while SGS changes methods whose updates depend on round indices.

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

Under a uniform margin, SGS-based OGD, ONS, and growing-grid MetaGrad achieve deterministic mistake and regret bounds independent of the total number of rounds T. ONS and SGS-MetaGrad provide polynomial dimension dependence for integer linear programs, while ONS improves margin dependence over SGS-OGD.

  • Growing-grid SGS-MetaGrad removes the prior log log T dependence by refining its learning-rate grid according to the realized number of mistakes K.The ordinary precomputed grid requires an a priori mistake bound and can retain a log log T factor; the growing-grid variant avoids that dependence.
  • All three methods have deterministic upper bounds on mistakes and regret whose right-hand sides do not depend on T.The guarantees hold for every T and arbitrary, possibly adaptive, state sequences.
  • The decision regret has the same upper bound as the regret of the sum for these guarantees.
  • ONS reduces SGS-OGD’s margin dependence from γ^-2 to γ^-1 in the number of mistakes and from γ^-1 to log γ^-1 in cumulative suboptimality regret.This improvement is especially relevant when the uniform margin is small, although ONS has higher dimension and projection costs.

6. Integer programming and lower bounds on the uniform margin

The section derives explicit lower bounds on the uniform margin γ_sub from the combinatorial structure of the forward problem, especially for integer programs. These bounds make mistake and regret guarantees explicit by problem class, with polynomial dependence under M-convexity.

  • 6. Integer programming and lower bounds on the uniform margin: Explicit lower bounds on γ_sub are derived for each combinatorial structure, then substituted into upper bounds to obtain problem-class guarantees.The general ILP case receives an unconditional positive bound, while discrete convex structures yield polynomial bounds.
  • 6. Integer programming and lower bounds on the uniform margin: For general ILPs, the explicit margin lower bound is exponentially small in dimension but remains positive and unconditional for the probability simplex.The unit-ball result instead requires a full-dimensionality assumption, with a separate low-dimensional treatment.
  • 6. Integer programming and lower bounds on the uniform margin: The margin γ_sub is the largest attainable minimum objective-value difference between the correct action and competing candidates.When γ_sub > 0, a maximizing weight satisfies the uniform-margin assumption with γ = γ_sub.
  • 6. Integer programming and lower bounds on the uniform margin: The analysis applies beyond identity features when the feature image is a finite union of polyhedra whose integer-point arguments remain valid.The paper presents the identity-feature formulation for notational simplicity.
  • 6. Integer programming and lower bounds on the uniform margin: Integer programming assumes each feasible action lies in Z^d and measures coordinatewise action spread through the vector M.The resulting bounds depend on combinatorial quantities such as the Graver-basis norm and ||M||_2.

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

Substituting explicit margin bounds yields mistake and regret guarantees by problem class. For general ILPs, ONS and growing-grid SGS-MetaGrad achieve T-independent polynomial regret, while M-convex structures retain logarithmic dependence on dimension.

  • 7. Explicit upper bounds on the number of mistakes and the regret by problem class: The reported bounds are obtained by substituting combinatorial lower bounds on γ into the upper bounds for cumulative suboptimality regret.ONS and growing-grid SGS-MetaGrad share the same order in the summarized comparison.
  • 7. Explicit upper bounds on the number of mistakes and the regret by problem class: O(d^2||M||_2 log(2||M||_2)) regret for ONS and growing-grid SGS-MetaGrad in general ILPs is independent of T and polynomial in dimension.Compared with O(||M||_2 d log T), the factor log T disappears, while the dimension power increases by one.
  • 7. Explicit upper bounds on the number of mistakes and the regret by problem class: Table 4 organizes explicit upper-bound orders by feasible-set structure, weight space, criterion, and method.In ILP rows, the substitution L ≤ ||M||_2 is used.
  • 7. Explicit upper bounds on the number of mistakes and the regret by problem class: For M-convex and M♮-convex structures, the regret is O(Ld log(2dL)), directly comparable with the existing O(d log d) bound under normalization.Without that normalization, the comparable existing bound becomes O(||θ*||_L d log d).

8. Conclusion

SGS makes mistake counts and both cumulative regret criteria independent of T under a uniform margin, while yielding polynomial ILP guarantees and lighter computation on non-mistake rounds.

  • 8. Conclusion: The three SGS variants bound mistakes and both cumulative regret criteria by quantities independent of T under a uniform margin.The guarantees apply to SGS combined with OGD, ONS, and MetaGrad.
  • 8. Conclusion: SGS skips iterate updates, internal-state advancement, and associated computations on rounds without mistakes.ONS retains the same iterate sequence as plain ONS; SGS improves the guarantee and omits matrix updates and projections on non-mistake rounds.
  • 8. Conclusion: For ILPs with the probability simplex, ONS and growing-grid SGS-MetaGrad achieve R^est_T = O(d^2∥M∥_2 log(2∥M∥_2)).This removes the log T dependence while retaining a polynomial dimension dependence.
  • 8. Conclusion: For M-convex structures, the resulting regret is comparable to O(d log d) while avoiding a center-of-gravity computation at every round.The comparison differs mainly in the logarithm’s argument under the stated normalization.
  • 8. Conclusion: The ILP guarantee remains separated from the known lower bound by a factor d and coordinate-range dependence, and the analysis is restricted to noiseless feedback.Improving the dimensional gap and extending SGS to noise or corruption remain open directions.
  • 8. Conclusion: A uniform margin alone simultaneously controls mistakes and regret without requiring integrality of θ* or M-convexity of the action set.The margin also receives explicit lower bounds from the forward problem’s combinatorial structure.

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

The comparison distinguishes which existing methods bound decision regret, suboptimality regret, or their sum, whereas the proposed methods bound the sum and thereby both criteria simultaneously under a uniform margin.

  • B.5. Comparison of the performance criteria with existing methods.: Existing methods differ in whether they claim bounds for decision regret, suboptimality regret, their sum, or only a total error criterion.Table 6 organizes the references according to which performance criterion each one bounds.
  • B.5. Comparison of the performance criteria with existing methods.: For per-round computation, non-mistake rounds cost only O(τsolve), whereas mistake-round costs include the method-specific update operations.Table 5 separates costs incurred every round from those incurred only on mistake rounds.
  • B.5. Comparison of the performance criteria with existing methods.: The proposed methods bound the combined criterion independently of T under a uniform margin, thereby bounding decision and suboptimality regret simultaneously.The combined quantity decomposes into the two nonnegative regret components.
  • B.5. Comparison of the performance criteria with existing methods.: The table marks references that do not claim an upper bound on a criterion as “not claimed,” while proposed-method entries restate the paper’s earlier guarantees.The comparison is made under a general margin γ.

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

The SGS-OGD analysis reindexes updates by mistake rounds because non-mistake rounds have zero loss and leave the iterate unchanged. A uniform margin then bounds mistakes and regret through the mistake-round sequence.

  • Margin lemma: The uniform margin yields ℓ_tk + γ ≤ r_tk ≤ LD at every mistake round.This lower bound is the key link between suboptimality loss and the margin.
  • Theorem C.2: Theorem C.2 applies these estimates to SGS-OGD and establishes bounds that hold for every horizon T.The cumulative decision regret has the corresponding bound from Equation (3.8).
  • Reindexing by SGS: Non-mistake rounds contribute zero loss and leave the prediction unchanged, so the analysis reduces to the K mistake rounds.The distinct iterates are therefore at most K + 1.
  • Potential estimate: The potential argument applies at each mistake round and sums the resulting bounds using decreasing step sizes and Abel summation.Projection nonexpansiveness and the bounded diameter of Θ control the potential terms.
  • Regret bounds: The same analysis handles both the reference weight θ̄ and the comparator θ*, but only θ̄ inherits the margin lower bound.For θ*, the analysis uses only 0 ≤ e_r_tk ≤ LD.

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

The ONS analysis controls mistake-round regret through logarithmic potential growth, using determinant identities and a scalar logarithmic inequality. It then derives mistake, suboptimality-regret, and decision-regret guarantees under the uniform margin.

  • Potential analysis: ONS controls cumulative r_tk through a logarithmic potential bound involving d log(1 + K/d).The determinant telescoping argument and eigenvalue bound produce the dimension-dependent logarithm.
  • Theorem D.6: Theorem D.6 applies ONS under the margin assumption and gives deterministic bounds for every horizon T.The cumulative decision regret inherits the theorem’s suboptimality-regret bound.
  • Mistake bound: The margin converts the cumulative r_tk bound into a finite mistake bound because r_tk ≥ γ at every mistake.The resulting bound is summarized as K ≤ K_ONS.
  • Suboptimality regret: The suboptimality-regret bound follows by subtracting γ from each mistake-round r_tk and optimizing the resulting logarithmic expression.The analysis distinguishes γ ≥ LD from γ < LD.
  • MetaGrad comparison: Fixed-grid MetaGrad retains an O(log log T) dependence through its prescribed grid upper bound K̄ when K̄ = T.The growing-grid variant is introduced to remove this residual dependence.

E.2. Proof.

The fixed-grid MetaGrad proof bounds linearized regret for each learning-rate expert, combines the experts through a potential argument, and applies the result to the mistake-round sequence. This yields bounds for mistakes and both regret notions.

  • Expert and master bounds: MetaGrad’s expert-level regret bound is combined with a monotone master potential to control the aggregate linearized regret.The result holds for every comparator u in the convex domain.
  • Comparison: Fixed-grid MetaGrad matches ONS in dependence on γ and d but has worse constants and a doubly logarithmic dependence on K̄.Taking K̄ = T leaves an O(log log T) horizon dependence.
  • Reduction to mistake rounds: The proof applies MetaGrad to the K mistake-round losses, with K bounded in advance by the grid upper bound K̄.Non-mistake rounds do not change the internal state or prediction.
  • Mistake bound: The uniform margin supplies γK ≤ R, which converts the aggregate regret inequality into a finite bound on the number of mistakes.A scalar inequality of the form y ≤ c1 + c2 log(1 + y) is then solved explicitly.
  • Decision regret: The same MetaGrad bound is applied with u = θ* to control cumulative decision regret without using the margin lower bound for θ*.The proof uses 0 ≤ e_r_tk ≤ LD and substitutes the mistake bound afterward.

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

Growing-grid MetaGrad creates learning-rate experts during execution and analyzes only the realized mistake rounds. This removes the fixed-grid upper-bound dependence on T while preserving finite mistake and regret guarantees.

  • Growing-grid construction: Growing-grid SGS-MetaGrad creates η_i-experts on a schedule and treats not-yet-created experts as virtual experts outputting the master point.The resulting potential remains controlled over the countable learning-rate grid.
  • Potential analysis: The growing-grid potential bound replaces the fixed horizon-based grid term with a quantity depending on the realized number of mistake rounds K.The proof reduces the algorithm to growing-grid MetaGrad on the K mistake-round losses.
  • Theorem F.3: Theorem F.3 gives finite mistake and regret bounds whose right-hand sides are independent of the total number of rounds T.The remaining doubly logarithmic factor depends on d rather than T.
  • Mistake bound: The mistake bound follows by combining γK ≤ R with the growing-grid aggregate regret estimate and solving the resulting scalar inequality.The proof bounds the grid term using logarithms of d and K before applying the elementary inequality.
  • Decision regret: Applying the same result with θ* yields a cumulative decision-regret bound after substituting the mistake bound into the increasing grid expression.Rounds without mistakes contribute zero to this comparator regret.

Appendix G. Lower bounds on the margin by structure

Appendix G derives lower bounds on the uniform margin from lattice geometry and discrete structure, including general ILPs, M-convex sets, and Graver-basis complexity.

  • General ILPs: For general ILPs, the unit-ball margin has explicit bounds depending on the feature-range norm, with a low-dimensional refinement when the affine hull excludes the origin.The low-dimensional bound is (2∥M∥2)^−k for k = dim aff Z∗.
  • General ILPs: For probability-simplex weights, the lower-bound construction does not require full-dimensionality of the relevant convex hull.The simplex analysis instead uses a full-dimensional polyhedron obtained by adding the nonnegative orthant.
  • Test sets: Test sets provide a uniform route to lower bounds on the margin by decomposing any feasible point toward an optimum through improving test-set directions.For M-convex sets, single exchange vectors form a test set; analogous finite test sets exist for M♮-convex sets.
  • Discrete convex structures: M-convex and M♮-convex feasible sets yield polynomial margin lower bounds through their exchange-based test sets.The corresponding test sets use {e_i − e_j} for M-convex sets and {e_i − e_j, ±e_i} for M♮-convex sets.
  • Linear inequalities: For linear inequality systems, the margin lower bound depends only on the ℓ∞ norm of the Graver basis, not on the right-hand side or feature range.For totally unimodular matrices, the relevant Graver-basis norm satisfies C_g = 1.

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

Appendix I establishes the geometric and arithmetic ingredients behind the margin bounds: separation from the origin and control of integer normal vectors.

  • Separating hyperplanes: A bounded full-dimensional polytope separated from a point admits a supporting halfspace whose boundary contains d affinely independent vertices.The separating hyperplane is chosen so the polytope lies in the halfspace while the excluded point lies outside it.
  • General ILP proof: The general-ILP proof reduces the margin bound to separating the convex hull of integer action differences from the origin.The uniform margin implies all relevant difference vectors lie strictly on one side of the origin.
  • Integer normal vectors: For integer vertices, the separating hyperplane can be represented with an integer normal vector constructed from determinants of vertex-difference matrices.The determinant construction supplies an integer normal whose norm can then be bounded using coordinate ranges.
  • Norm estimates: Hadamard-type estimates bound the separating normal through the coordinate ranges of the lattice points, producing the full-dimensional and low-dimensional margin bounds.The low-dimensional argument uses the distance from the origin to the affine hull and yields (2∥M∥2)^−k when 0 is not in that affine hull.
  • Probability simplex: For the probability simplex, adding the nonnegative orthant creates a full-dimensional polyhedron with nonnegative facet normals that separates the origin.This construction removes the need for a full-dimensionality assumption on Conv Z∗.

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

Appendix N substitutes the structural margin bounds into the three SGS guarantees to obtain explicit mistake and regret bounds for each problem class.

  • General derivation: The three SGS guarantees are expressed in terms of the margin γ, then specialized by substituting lower bounds for γ and problem-specific diameter and Lipschitz estimates.The resulting bounds are monotone in γ, so stronger margin lower bounds directly improve the guarantees.
  • General ILPs: For general ILPs, the substitutions use bounds involving the feature-range norm ∥M∥2, with separate expressions for the unit ball and probability simplex.The derivation applies to SGS-OGD, ONS, and growing-grid SGS-MetaGrad.
  • Linear inequalities: For linear inequalities, the analogous bounds replace the feature-range dependence with the Graver-basis quantity C_g.The appendix explicitly uses log(1/γ) = O(d log(C_g)) in these substitutions.
  • Discrete convex structures: For M-convex and M♮-convex structures, the orders of the resulting guarantees coincide up to the different structural bounds on 1/γ.The stated bounds use d for M-convex and d^(3/2) or d(d + 1)/2 for M♮-convex cases, depending on the weight domain.
  • Discrete convex structures: When L = O(d), the appendix reports O(d^4) to O(d^5) mistakes for SGS-OGD and O(d^3 log d) to O(d^(7/2) log d) for ONS.These ranges summarize the stated unit-ball and probability-simplex cases.
Loading 2609.09809v1…