Paper deep dive
Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs
Akira Kitaoka
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/2/2026, 1:20:36 PM
Summary
This paper addresses the Data-Driven Inverse Optimization Problem (DDIOP) for Integer Linear Programs (ILPs). It derives explicit iteration complexity bounds for projected subgradient descent applied to the suboptimality loss, providing a lower bound for the geometric constant gamma(l_sub) as a function of problem size (sample size N, feature dimension d, feature ranges, and constraint matrix structure). The results quantify the number of iterations required to achieve exact consistency with observed data, distinguishing between general ILPs (exponential dependence on dimension) and structured cases like M-convex sets or totally unimodular matrices (polynomial dependence).
Entities (8)
Relation Signals (6)
Data-Driven Inverse Optimization Problem → appliesto → Integer Linear Program
confidence 95% · A data-driven inverse optimization problem (DDIOP) ... arises in many applications, including integer linear programming (ILP).
Projected Subgradient Descent → minimizes → Suboptimality Loss
confidence 95% · projected subgradient descent applied to the suboptimality loss to achieve exact consistency
Geometric Constant → bounds → Iteration Complexity
confidence 93% · the required number of iterations is bounded as T=O(1/gamma(l_sub)^2) in terms of a problem-dependent geometric constant
M-convex Set → yields → Polynomial Iteration Bound
confidence 92% · for M-convex and M♮-convex sets, the lower bound on gamma(l_sub) is a polynomial in the dimension
Graver Basis → determines → Geometric Constant
confidence 90% · we derive explicit lower bounds on gamma(l_sub) from the structure of integer programming ... Graver bases
Total Unimodularity → simplifies → Graver Basis Norm
confidence 90% · in particular C=1 for totally unimodular matrices
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:A data-driven inverse optimization problem (DDIOP) is the problem of estimating the objective-function parameters (weights) that explain observed optimal-solution data, and it arises in many applications, including integer linear programming (ILP). It is known that, by applying gradient-based optimization methods to the suboptimality loss, the inverse optimization of ILPs can be solved exactly within finitely many oracle iterations, and that the required number of iterations is bounded as $T=O(1/\gamma(\ell_{\mathrm{sub}})^2)$ in terms of a problem-dependent geometric constant $\gamma(\ell_{\mathrm{sub}})$. However, no means of bounding $\gamma(\ell_{\mathrm{sub}})$ from below as a function of the problem size has been available, and hence the number of iterations could not be given as an explicit function of the problem size. We therefore give, when the forward problem is an integer linear program (ILP), the number of iterations sufficient for projected subgradient descent applied to the suboptimality loss to achieve exact consistency with the observed data, as a fully explicit function of the number of samples, the dimension of the features, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set, the step-size parameter, and the Lipschitz constant of the suboptimality loss).
Tags
Links
- Source: https://arxiv.org/abs/2607.22263v1
- Canonical: https://arxiv.org/abs/2607.22263v1
Trouble viewing inline? Open PDF directly →
Full Text
126,168 characters extracted from source content.
Expand or collapse full text
Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs Akira Kitaoka NEC Corporation, 1753 Shimonumabe, Nakahara-ku, Kawasaki, Kanagawa, Japan akira-kitaoka@nec.com Abstract. A data-driven inverse optimization problem (DDIOP) is the problem of estimating the objective-function parameters (weights) that explain observed optimal-solution data, and it arises in many applications, including integer linear programming (ILP). It is known that, by applying gradient-based optimization methods to the suboptimality loss, the inverse optimization of ILPs can be solved exactly within finitely many oracle iterations, and that the required number of iterations is bounded as T=O(1/γ(ℓsub)2)T=O(1/γ( _sub)^2) in terms of a problem-dependent geometric constant γ(ℓsub)γ( _sub). However, no means of bounding γ(ℓsub)γ( _sub) from below as a function of the problem size has been available, and hence the number of iterations could not be given as an explicit function of the problem size. We therefore give, when the forward problem is an integer linear program (ILP), the number of iterations sufficient for projected subgradient descent applied to the suboptimality loss to achieve exact consistency with the observed data, as a fully explicit function of the number of samples, the dimension of the features, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set, the step-size parameter, and the Lipschitz constant of the suboptimality loss). Key words and phrases: inverse optimization problem, mathematical programming, integer linear programming, projected subgradient method, Graver basis, M-convexity, total unimodularity AMS subject classifications 2020: 90C90(primary), 90C25, 90C52, 90C11, 90C05, 68Q25 (secondary) 1. Introduction Inverse optimization is the problem of estimating an objective function or its parameters from observed optimal solutions (Ahuja and Orlin, 2001; Heuberger, 2004; Chan et al., 2019, 2023), with a wide range of applications including transportation (Bertsimas et al., 2015), power systems (Birge et al., 2017), healthcare (Chan et al., 2022), advertisement scheduling (Suzuki et al., 2019), and inverse reinforcement learning (Ng et al., 2000). In this paper, we treat the case where the objective function of the forward problem is given as a linear combination of known features: for each state s∈s , given a feasible region X(s)⊂X(s) , a feature map f=(f1,…,fd):×→ℝdf=(f_1,…,f_d) ×S ^d, and weights θ∈Θ⊂ℝdθ∈ ^d, the forward problem is x∗(θ,s)∈argmaxx∈X(s)θ⊤f(x,s)x^*(θ,s)∈ *arg\,max_x∈ X(s)θ f(x,s). Given observed data =(s(n),x(n))n=1ND=\(s^(n),x^(n))\_n=1^N, x(n)=x∗(θ∗,s(n))x^(n)=x^*(θ^*,s^(n)), generated by unknown true weights θ∗θ^*, the data-driven inverse optimization problem (DDIOP) asks for weights θ that explain every observed solution as an optimal solution (see ˜3 for the precise formulation). In particular, setting f(x,s)=xf(x,s)=x, this framework includes mixed integer linear programs (MILPs). To measure consistency with the observed data, we compare the observed features a(n):=f(x(n),s(n))a^(n):=f(x^(n),s^(n)) with the predicted features a∗(θ,s(n)):=f(x∗(θ,s(n)),s(n))a^*(θ,s^(n)):=f(x^*(θ,s^(n)),s^(n)). A representative loss, the prediction loss of features (PLF) ℓplf(θ):=1N∑n=1N∥a∗(θ,s(n))−a(n)∥22 _plf(θ):= 1N _n=1^N a^*(θ,s^(n))-a^(n) _2^2 (Aswani et al., 2018; Chan et al., 2019; Babier et al., 2021; Chan et al., 2023; Ferber et al., 2023; Liang and Dvorkin, 2023), is in general discontinuous in inverse optimization for MILPs because a∗(θ,s(n))a^*(θ,s^(n)) can vary discontinuously with respect to θ, which makes direct gradient-based minimization difficult (cf. Beck, 2017; Hazan, 2019; Garrigos and Gower, 2023). In contrast, the suboptimality loss ℓsub(θ):=1N∑n=1N(θ⊤a∗(θ,s(n))−θ⊤a(n)) _sub(θ):= 1N _n=1^N(θ a^*(θ,s^(n))-θ a^(n)), introduced by Mohajerin Esfahani et al. (2018), is convex and Lipschitz continuous in our setting (Mohajerin Esfahani et al., 2018; Bärmann et al., 2018; Kitaoka and Eto, 2023a), and ℓsub(θ)=0 _sub(θ)=0 is equivalent to every observed solution x(n)x^(n) being optimal under the weights θ, that is, to exact consistency with the observed data. Consequently, first-order and online optimization methods—projected subgradient descent, multiplicative weights update, online Newton step, MetaGrad, and others—have been applied to the suboptimality loss, and regret and best-iterate analyses provide asymptotic guarantees that the loss decreases as the number of iterations T grows (Bärmann et al., 2018; Besbes et al., 2021, 2025; Gollapudi et al., 2021; Sakaue et al., 2025). Moreover, Kitaoka (2024) strengthened these asymptotic guarantees, using the geometric structure that the suboptimality loss is convex and piecewise linear and that its minimizer set has a relative interior point: gradient-based optimization methods reach ℓsub=0 _sub=0—that is, exact consistency with the observed data—within finitely many iterations, and the number of iterations is bounded from above via a problem-dependent geometric constant γ(ℓsub)>0γ( _sub)>0 (e.g., T=O(1/γ(ℓsub)2)T=O(1/γ( _sub)^2) for projected subgradient descent). However, γ(ℓsub)γ( _sub) is an abstract constant determined by the geometry of the problem, and no means of bounding it from below as a function of the problem size was known. Consequently, the number of iterations sufficient for exact consistency could not be given as an explicit function of the problem size, such as the sample size N and the feature dimension d. In this paper, when the forward problem is an integer linear program (ILP), we derive explicit lower bounds on γ(ℓsub)γ( _sub) from the structure of integer programming (total unimodularity, Graver bases, and M-convexity/M♮-convexity). Substituting them into the iteration upper bounds of Kitaoka (2024), we give the number of iterations sufficient to achieve exact consistency with the observed data as a fully explicit function of the sample size N, the feature dimension d, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set diam(Θ)diam( ), the step-size parameter β, and the Lipschitz constant of the suboptimality loss L(ℓsub)L( _sub)). The obtained lower bounds are polynomial in the dimension and independent of the ranges of the features for M-convex and M♮-convex sets, whereas for general ILPs they can become exponentially small in the dimension d. The latter is consistent with the NP-hardness of inverse optimization (Aswani et al., 2018), and shows that, in our bounds, the exponential dependence is confined to the dimension d (˜4.4). Contributions The contributions of this paper are as follows. • For data-driven inverse optimization whose forward problem is an integer linear program (ILP), under Θ=Δd−1 = ^d-1 (Theorem˜6.6), we give an explicit lower bound γ(ℓsub)≥1Ndmax(d−1,2)∥m∥2d−1γ( _sub)≥ 1N^d (d-1, 2)\, m _2^d-1 on the constant γ(ℓsub)γ( _sub), where m=(mi)im=(m_i)_i collects the ranges of the features and N is the sample size. • When the constraints form a linear inequality system Ax≤bAx≤ b, we give a lower bound γ(ℓsub)=Ω(1/(Nd(d+1)/2(2C)d−1))γ( _sub)= (1/(N\,d^(d+1)/2(2C)^d-1) ) that is independent of the ranges of the features and determined solely by the ℓ∞ _∞ norm C=g∞(A~)C=g_∞( A) of the Graver basis of the slack-augmented matrix A~=[A∣I] A=[A I] (in particular C=1C=1 for totally unimodular matrices). • When the feasible region is an M-convex or M♮-convex set, we give a polynomial-in-dimension lower bound Ω(1/(Nd2)) (1/(Nd^2) ) that is independent of the ranges of the features. • Substituting these lower bounds into the iteration upper bounds for gradient-based optimization methods (Kitaoka, 2024), we give the number of iterations sufficient to solve the data-driven inverse optimization of ILPs exactly as an explicit function of the problem size. The same substitution also yields an explicit bound on the number of iterations required to attain the minimum of the prediction loss of features (PLF). • We show that the general-ILP lower bounds above are essentially tight: we construct an explicit family of ILP instances on which γ(ℓsub)=‖m‖∞−Ω(d)γ( _sub)=\|m\|_∞^- (d) (with ‖m‖∞=maximi\|m\|_∞= _im_i) is exponentially small in the dimension d (˜6.9). Hence the exponential dependence of the resulting iteration bound on d is genuine rather than an artifact of a loose lower bound. The remainder of this paper is organized as follows. In ˜2, we review related work. In ˜3, we describe the DDIOP setting and the algorithm, which applies gradient-based optimization to the suboptimality loss. In ˜4, we state the main results. In ˜5, we compare our bounds with existing methods; in ˜6, we give the lower bounds on the constant γ(ℓsub)γ( _sub) together with their proofs; and in ˜7, we derive the iteration upper bounds. 2. Related Work Research on inverse optimization has classically developed for combinatorial and network optimization (Ahuja and Orlin, 2001; Heuberger, 2004), and more recently the data-driven framework—which estimates an objective function or its parameters from observed data—has been actively studied from both theoretical and applied perspectives (Chan et al., 2019, 2023) (the applications and loss functions were reviewed in the introduction; for systematic surveys see Chan et al. (2019, 2023), and for a detailed account of related work in the same setting as ours see Kitaoka (2024)). In this section, we focus on the work directly related to the contributions of this paper: explicit lower bounds on γ(ℓsub)γ( _sub) and explicit evaluations of the number of iterations. Existing guarantees for the suboptimality loss. For the convex suboptimality loss, regret and best-iterate analyses based on first-order and online optimization methods—projected subgradient descent, multiplicative weights update, online Newton step, and MetaGrad—have been carried out (Bärmann et al., 2018; Besbes et al., 2021, 2025; Gollapudi et al., 2021; Kitaoka and Eto, 2023a; Sakaue et al., 2025) (for details of existing regret analyses see Appendix˜A, and for the offline implications see Table˜2); however, these guarantees remain asymptotic, of the form ℓsub(θt)→0 _sub(θ^t)→ 0 or min1≤t≤Tℓsub(θt)→0 _1≤ t≤ T _sub(θ^t)→ 0. Kitaoka (2024) strengthened these asymptotic guarantees into finite-step exact attainment, with an iteration upper bound via the constant γ(ℓsub)γ( _sub), under the structure that the suboptimality loss is convex and piecewise linear and its minimizer set has a relative interior point. Inverse optimization with discrete structure. The work most closely sharing our motivation is Oki and Sakaue (2026), which treats online inverse linear optimization where the feasible region is an M-convex set (a fundamental class in discrete convex analysis that includes matroids (cf. Murota, 1996, 1998, 2003)) and gives a regret bound O(dlogd)O(d d) independent of the number of iterations T; it lies on the same complexity axis as ours in that it obtains a polynomial-in-dimension complexity by exploiting discrete structure. This paper extends this axis: by deriving lower bounds on γ(ℓsub)γ( _sub) from the structure of integer programming, such as total unimodularity and Graver bases (Sturmfels, 1996; Onn, 2010), we broaden the scope to general ILPs, which contain M-convex and M♮-convex sets as special cases, and we guarantee finite-step attainment of exact consistency with the observed data (ℓsub=0 _sub=0), together with explicit iteration upper bounds, rather than the finiteness of the cumulative regret. To avoid the discontinuity of the PLF or of the discrete optimal-solution map, approaches that smooth the problem by adding noise (Berthet et al., 2020) or regularization (Wilder et al., 2019), or by using cutting planes and LP relaxations for MILPs (Ferber et al., 2020, 2023), have also been proposed; however, these generally solve an approximate problem and do not guarantee exact consistency for the original discrete problem in finitely many iterations (for an examination of the approximation errors and solution uniqueness of these methods, see Kitaoka, 2024). Our framework does not use smoothing and is based on the geometric structure of the suboptimality loss itself. Computational complexity and evaluation of the number of iterations. This paper sharpens the qualitative guarantee of attaining exact consistency in finitely many iterations into an explicit evaluation that quantifies the required number of iterations in accordance with the problem structure. Our iteration upper bound is described via the problem-dependent geometric constant γ(ℓsub)γ( _sub), and for PSGD (SRSS, SRSL; defined in ˜3) it takes the form T=O(1/γ(ℓsub)2)T=O(1/γ( _sub)^2) up to polynomial factors. Whereas existing first-order/online studies rarely give the number of iterations required for exact consistency as an explicit function of the problem size, this paper, when the forward problem is an integer linear program (ILP), derives an explicit lower bound on γ(ℓsub)γ( _sub) from the structure of integer programming (total unimodularity, the Graver basis (Sturmfels, 1996; Onn, 2010), and M-convexity / M♮-convexity), and thereby evaluates the required number of iterations as an explicit function of the problem size. As a result, it is shown quantitatively that for a broad range of cases in which the structure can be exploited, or for a fixed dimension d (including the totally unimodular case), the number of iterations is bounded by a polynomial in the problem size. In particular, for M-convex and M♮-convex sets, the lower bound on γ(ℓsub)γ( _sub) is a polynomial in the dimension, Ω(1/(Nd2)) (1/(Nd^2)), independent of the ranges of the features, and the number of iterations is bounded by O(N2d4)O(N^2d^4) times poly(diam(Θ),β,L(ℓsub))poly(diam( ),β,L( _sub)) (˜7). We also note that γ(ℓsub)γ( _sub) can be upper-bounded via the SPO loss (Mohajerin Esfahani et al., 2018; Elmachtoub and Grigas, 2022) (Kitaoka, 2024, Section 13.4); however, what is needed to evaluate the number of iterations is a lower bound on γ(ℓsub)γ( _sub), which this paper provides, and the two are complementary. Moreover, our explicit evaluation makes the possible worst-case behavior of the resulting bounds visible. In the worst case for general ILPs without structural assumptions, or for linear inequality constraints including the totally unimodular case, the lower bound on γ(ℓsub)γ( _sub) that we give can become exponentially small in the dimension d, so the corresponding iteration upper bounds can grow exponentially in d. This dependence is consistent with the computational hardness of inverse optimization—Aswani et al. (2018, Theorem 1) show NP-hardness of inverse optimization with noisy data. In this way, rather than claiming polynomial-time solvability in the general sense, this paper quantitatively separates the two regimes: it guarantees polynomial iteration bounds when the structure can be exploited, while in the general case our bounds leave room for exponential growth in the dimension d (˜4.4). Implications enabled by the explicit lower bounds on γ(ℓsub)γ( _sub). Previously, γ(ℓsub)γ( _sub) was an abstract constant guaranteed only to be positive (˜4.1), so the iteration upper bounds of Kitaoka (2024) remained qualitative statements of finite termination. Having lower bounds on γ(ℓsub)γ( _sub) computable from the problem size newly enables the following considerations. First, an iteration budget can be determined before running the algorithm. For instance, when the coefficient matrix is totally unimodular, the coefficient C=g∞(A~)C=g_∞( A) determined by the linear-inequality constraint matrix (the ℓ∞ _∞ norm of the Graver basis of the slack-augmented matrix A~=[A∣I] A=[A I]) equals 11, so under the assumptions of ˜7 the upper bounds in Table˜4 are determined solely by the sample size N, the dimension d, and the basic constants diam(Θ)diam( ), β, and L(ℓsub)L( _sub); they thus serve as an a priori stopping criterion—running this many iterations guarantees exact consistency—and as an estimate of the computational budget. Second, comparisons with asymptotic guarantees become comparisons between explicit functions of the problem size. The finite-step guarantee “0 if T≥⋯T≥·s” in Table˜2 could not previously be compared with regret-type guarantees on the same footing because γ(ℓsub)γ( _sub) was unknown; substituting the lower bounds places both on the same problem-size scale. Third, the computational value of discrete structure can be quantified. An M♮-convex set can also be described by a system of linear inequalities, but the lower bound Ω(1/(Nd2)) (1/(Nd^2)) obtained directly from M♮-convexity is far better than the bound Ω(1/(Nd(d+1)/2(2C)d−1)) (1/(N\,d^(d+1)/2(2C)^d-1) ) obtained by treating the same set via the general theory for linear inequality constraints (˜6.5.2). That is, for one and the same feasible region, which structural information is used to evaluate γ(ℓsub)γ( _sub) can make the resulting iteration estimate polynomial or exponential in the dimension, and this distinction becomes visible as a comparison of the lower bounds. Relation to weak sharp minima. The structure that is key to the finite-step attainment (Theorem˜4.5)—that the set of minimizers has a relative interior point—is closely related to the notion of weak sharp minima (Burke and Ferris, 1993), and finite termination of optimization algorithms under weak sharp minima has been studied classically (Polyak, 1987; Ferris, 1991; Burke and Ferris, 1993). For a detailed comparison between these finite-termination theories and the finite-step attainment of gradient-based methods for the nonsmooth suboptimality loss, see Kitaoka (2024). The difference of the present paper lies not in whether finite termination occurs but in its quantification: whereas the classical finite-termination theory of weak sharp minima does not provide the number of iterations until termination as a function of the problem size, this paper derives explicit lower bounds on γ(ℓsub)γ( _sub) from the structure of integer programming (Graver bases, total unimodularity, and M-convexity/M♮-convexity; ˜6 and 7), thereby giving the required number of iterations as an explicit function of the problem size. Positioning of this paper. In light of the above, this paper is positioned at the intersection of two streams of work: the asymptotic analysis of first-order/online optimization for the suboptimality loss, and the problem awareness of achieving exact consistency with the observed data in discrete inverse optimization including ILPs. The finite-time exact solvability of gradient-based methods for the suboptimality loss, together with the general iteration upper bound T=O(1/γ(ℓsub)2)T=O(1/γ( _sub)^2) via the constant γ(ℓsub)γ( _sub), was established by Kitaoka (2024); this paper is responsible for bounding γ(ℓsub)γ( _sub) from below in terms of the structure of ILPs. Its novelty is to derive explicit lower bounds on the constant γ(ℓsub)γ( _sub) from the structure of integer programming (total unimodularity, Graver bases, and M-convexity/M♮-convexity), and thereby to give the number of iterations required for exact consistency as an explicit function of the problem size. 3. Problem Setup and Algorithms For each state s∈s , we define the optimal solution to the forward problem and its associated feature vector as follows: x∗(θ,s)∈argmaxx∈X(s)θ⊤f(x,s)=∑i=1dθifi(x,s),a∗(θ,s)=f(x∗(θ,s),s).x^*(θ,s)∈ *arg\,max_x∈ X(s)θ f(x,s)= _i=1^d _if_i(x,s), a^*(θ,s)=f(x^*(θ,s),s). (3.1) Given the observed data =(s(n),x(n))n=1ND=\(s^(n),x^(n))\_n=1^N, the data-driven inverse optimization problem associated with the forward problem Equation˜3.1 is the problem of finding θ∈Θθ∈ satisfying the following condition for all n=1,…,Nn=1,…,N: x(n)∈argmaxx∈X(s(n))θ⊤f(x,s(n))=∑i=1dθifi(x,s(n)).x^(n)∈ *arg\,max_x∈ X(s^(n))θ f(x,s^(n))= _i=1^d _if_i(x,s^(n)). (3.2) We impose the following assumptions to specify the problem setting studied in this paper. Assumption 3.1. Let the nonempty set S be the state space, and let the nonempty set ⊂ℝdX ^d_X be the decision space. Let f=(f1,…,fd):×→ℝdf=(f_1,…,f_d) ×S ^d be a mapping such that each component fif_i is a piecewise linear function. Let the weight space Θ⊂ℝd ^d be a bounded, closed, and convex set. For each state s∈s , let the feasible region X(s)X(s) be a finite union of bounded, closed, and convex polytopes that are subsets of X. Let :=(s(n),x(n))n=1ND:= \ (s^(n),x^(n) ) \_n=1^N be a set of training data such that the samples s(n)∈s^(n) are generated from an unknown distribution ℙP_S, and there exists an unknown θ∗∈Θθ^*∈ satisfying, for each n=1,…,Nn=1,…,N, x(n)=x∗(θ∗,s(n))x^(n)=x^*(θ^*,s^(n)). As a technical condition, we further assume the following. Assumption 3.2. For each n=1,…,Nn=1,…,N, the feature a∗(θ∗,s(n))a^*(θ^*,s^(n)) is uniquely determined. ˜3 is a natural assumption, in view of the following statement. Lemma 3.3 (Kitaoka, 2024, Lemma 3.3). Suppose ˜3 holds and let Θ=Δd−1⊂ℝd = ^d-1 ^d. Then, for θ∈Δd−1θ∈ ^d-1 almost everywhere (with respect to the measure on Δd−1 ^d-1 induced by the Lebesgue measure), the feature a∗(θ,s(n))a^*(θ,s^(n)) is uniquely determined for every n=1,…,Nn=1,…,N. In this paper, based on the following proposition, we apply a gradient-based optimization method to the suboptimality loss ℓsub _sub and minimize it. Proposition 3.4 (Bärmann et al. 2018, Proposition 3.1; Kitaoka and Eto 2023a, Lemma 4.8). Suppose that ˜3 holds. Then the following statements hold: (A) the suboptimality loss ℓsub _sub is convex; (B) the suboptimality loss ℓsub _sub is Lipschitz continuous; and (C) a subgradient of the suboptimality loss ℓsub _sub at θ∈Θθ∈ is given by g(θ):=∑n=1N(a∗(θ,s(n))−a(n))/Ng(θ):= _n=1^N (a^*(θ,s^(n))-a^(n) )/N. Algorithm 1 Minimization of the suboptimality loss (Kitaoka, 2024) 1: Initialize θ1∈Θθ^1∈ 2: for t=1,…,T−1t=1,…,T-1 do 3: For each n=1,…,Nn=1,…,N, solve for x∗(θt,s(n))x^*(θ^t,s^(n)) 4: θt+1←updatet(θt′t′=1t∣ℓsub,g)θ^t+1 _t\! (\θ^t \_t =1^t _sub,g ) 5: end for 6: return θbestT∈argminθ∈θtt=1Tℓsub(θ) _best^T∈ *arg\,min_θ∈\θ^t\_t=1^T _sub(θ) Hereafter, when it is clear from the context, minΘℓ=minθ∈Θℓ(θ) _ = _θ∈ (θ) and argminΘℓ=argminθ∈Θℓ(θ) *arg\,min_ = *arg\,min_θ∈ (θ) are used as abbreviations. Let ℓ:Θ→ℝ be a Lipschitz-continuous convex function, and let ∂ℓ∂ denote the subdifferential of ℓ . Let ∇ℓ:Θ→ℝd∇ ^d be any (sub)gradient selection satisfying, for every θ, ∇ℓ(θ)∈∂ℓ(θ)∇ (θ)∈∂ (θ). For t∈ℤ≥1t _≥ 1, let the update map be updatet:Θt×ℝt×(ℝd)t→Θupdate_t ^t×R^t×(R^d)^t→ . Moreover, define updatet(θt′t′=1t∣ℓ,∇ℓ):=updatet(θt′t′=1t,ℓ(θt′)t′=1t,∇ℓ(θt′)t′=1t) split&update_t (\θ^t \_t =1^t ,∇ ):=update_t(\θ^t \_t =1^t,\ (θ^t )\_t =1^t,\∇ (θ^t )\_t =1^t) split The resulting procedure is described in Algorithm˜1. Example 3.5 (Projected subgradient descent). Let αt:ℝd×ℝ×ℝd→ℝ≥0 _t ^d×R×R^d _≥ 0 be a mapping, and refer to αtt∈ℤ≥1\ _t\_t _≥ 1 as the learning rate. Let ProjΘProj_ denote the projection onto Θ . We identify the mapping αt _t with its value αt(θt,ℓ(θt),∇ℓ(θt)) _t(θ^t, (θ^t),∇ (θ^t)) when no confusion arises. We define projected subgradient descent (PSGD) (cf. Boyd et al., 2003; Beck, 2017) as the update rule updatett\update_t\_t in Algorithm˜1 by updatet(θt′t′=1t|ℓ,∇ℓ)=ProjΘ(θt−αt∇ℓ(θt)).update_t (\θ^t \_t =1^t| ,∇ )=Proj_ (θ^t- _t∇ (θ^t) ). The learning rate αt _t is said to be a nonsummable step size (NSS) if there exists a sequence βtt⊂ℝ\ _t\_t such that βt>0,limT→∞∑t=1Tβt2∑t=1Tβt=0 _t>0, _T→∞ _t=1^T _t^2 _t=1^T _t=0 (3.3) and αt=βt _t= _t. The learning rate αt _t is said to be a square root step size (SRSS) if, for some β>0β>0, it is an NSS learning rate with βt=βt−1/2 _t=β t^-1/2. The learning rate αt _t is said to be a nonsummable step length (NSL) if, for some sequence βtt⊂ℝ\ _t\_t satisfying Equation˜3.3, we set αt=βt‖∇ℓ(θt)‖−1 _t= _t\|∇ (θ^t)\|^-1 when ∇ℓ(θt)≠0∇ (θ^t) =0, and αt=0 _t=0 when ∇ℓ(θt)=0∇ (θ^t)=0. The learning rate αt _t is said to be a square root step length (SRSL) if, for some β>0β>0, it is an NSL learning rate with βt=βt−1/2 _t=β t^-1/2. The learning rate αt _t is said to be Polyak if the minimum value minΘℓ _ is known and αt=(ℓ(θt)−minΘℓ)‖∇ℓ(θt)‖−2 _t= ( (θ^t)- _ )\|∇ (θ^t)\|^-2 holds. We present below an example satisfying ˜3, together with an implementation example of Algorithm˜1. Example 3.6. In ˜3, let f(x,s)=xf(x,s)=x (i.e., the features are the decision variables themselves). Under this setting, Equation˜3.1 becomes an MILP. Let the sequence updatett\update_t\_t be PSGD, and implement the projection ProjΔd−1Proj_ ^d-1 onto Θ=Δd−1 = ^d-1 as in Wang and Carreira-Perpinán (2013). Then one can implement Algorithm˜1. This implementation is identical to Kitaoka and Eto (2023a, Algorithm 1). Remark 3.7. In ˜3, it is more natural to require that the weight space Θ does not contain 0; see Appendix˜C for the rationale. 4. Main Results 4.1. Finite-time exact solvability of DDIOP for MILP (gradient based optimization method) For gradient-based optimization methods, we make the following assumptions: namely, that the update rule depends only on the past sequence of iterates and (sub)gradients, and that a convergence rate in terms of the best iterate is guaranteed, respectively. Assumption 4.1. For any t∈ℤ≥1t _≥ 1, we assume that updatet:Θt×ℝt×(ℝd)t→Θupdate_t ^t×R^t×(R^d)^t→ does not depend on the second component space ℝtR^t. Assumption 4.2. For any L-Lipschitz-continuous convex function ℓ:Θ→ℝ , any initial point θ1∈Θθ^1∈ , and any t∈ℤ≥1t _≥ 1, define the iterates inductively by θt+1=updatet(θt′t′=1t∣ℓ,∇ℓ)θ^t+1=update_t (\θ^t \_t =1^t ,∇ ). Then there exists a nonincreasing function QL,θ1:ℝ>0→ℝQ_L,θ^1 _>0 such that, for every ε>0 >0, if T≥QL,θ1(ε)T≥ Q_L,θ^1( ), then for any L-Lipschitz-continuous convex function ℓ:Θ→ℝ , the best iterate is ε -accurate, that is, mint=1,…,Tℓ(θt)−minΘℓ≤ε _t=1,…,T (θ^t)- _ ≤ . Among PSGD methods, those with NSS or NSL learning rates satisfy ˜4.1, and explicit convergence rates for the best iterate are available (Kitaoka, 2024, Propositions 9.2 and 9.8). In contrast, for PSGD with the Polyak learning rate, updatetupdate_t depends on the second argument, i.e., the sequence of objective values ℓ(θt′)t′=1t\ (θ^t )\_t =1^t, and hence it does not satisfy ˜4.1. Since X(s(n))X(s^(n)) is a finite union of polyhedra and f is such that each component function fif_i is piecewise affine, it follows that f(X(s(n)),s(n))f\! (X(s^(n)),s^(n) ) is also a finite union of polyhedra (Kitaoka, 2024, Propositions 10.5 and 10.14). Let Y(n)Y^(n) denote the set of vertices of the finite union of polyhedra f(X(s(n)),s(n))f\! (X(s^(n)),s^(n) ) (˜4.1). Definition 4.3 (Kitaoka, 2024, Definition 10.15). Let X be a finite union of polyhedra. A set Y is said to be the vertex set of X if Y is the vertex set of the convex hull ConvXConvX. Under ˜3, by the maximum principle, a∗(θ∗,s(n))∈Y(n)a^*(θ^*,s^(n))∈ Y^(n) (4.1) holds. We define the Lipschitz constant L(ℓsub)L( _sub) and a positive constant γ(ℓsub)γ( _sub) as follows: L(ℓsub) L( _sub) :=supan∈f(X(s(n)),s(n)),n=1,…,N‖1N∑n=1N(an−a(n))‖(≤L(f)diam()), := _ subarrayca^n∈ f(X(s^(n)),s^(n)),\\ n=1,…,N subarray \| 1N _n=1^N(a^n-a^(n)) \| (≤ L(f)diam(X) ), (4.2) γ(ℓsub) γ( _sub) :=maxθ∈Θmin(an)n∈∏n=1NY(n)∖(a(n))n1N∑n=1Nθ⊤(a(n)−an). := _θ∈ _(a^n)_n∈ _n=1^NY^(n) \(a^(n))_n\ 1N _n=1^Nθ (a^(n)-a^n ). (4.3) Here, L(f)L(f) denotes the Lipschitz constant of f, and diam()=supx,x′∈‖x−x′‖diam(X)= _x,x \|x-x \| denotes the diameter of X. For an intuitive explanation of the constant γ(ℓsub)γ( _sub), see Kitaoka (2024, Section 6). The positivity of γ(ℓsub)γ( _sub) follows from the following proposition. Proposition 4.4 (Kitaoka, 2024, Proposition 7.4). Under ˜3 and 3, the constant γ(ℓsub)γ( _sub) defined in Equation˜4.3 is positive. The theorem established by Kitaoka (2024), on which the arguments of this paper rest, is the following. Theorem 4.5 (Kitaoka, 2024, Theorem 4.3). Suppose that ˜3, 4.1, 4.1 and 3 hold. Then, if T≥QL(ℓsub),θ1(γ(ℓsub))T≥ Q_L( _sub),θ^1(γ( _sub)), we have mint=1,…,Tℓsub(θt)=minΘℓsub=0 _t=1,…,T _sub(θ^t)= _ _sub=0. From ˜3 and Theorem˜4.5, we obtain the following corollary. Corollary 4.6 (Kitaoka, 2024, Corollary 4.4). Suppose that ˜3, 4.1 and 4.1 hold. Let Θ=Δd−1 = ^d-1. Then, for Lebesgue-almost every θ∗∈Δd−1θ^*∈ ^d-1 (with respect to the measure on Δd−1 ^d-1 induced by Lebesgue measure), the following holds: if T≥QL(ℓsub),θ1(γ(ℓsub))T≥ Q_L( _sub),θ^1(γ( _sub)), then mint=1,…,Tℓsub(θt)=minΘℓsub=0 _t=1,…,T _sub(θ^t)= _ _sub=0. Remark 4.7. By strengthening the result of Theorem˜4.5, one can, in the case Θ=Δd−1 = ^d-1, replace the constant γ(ℓsub)γ( _sub) by a constant depending only on X(s(n))n\X(s^(n))\_n, f, and Θ (Kitaoka, 2024, Theorem 12.3). 4.2. Concrete complexity bounds for PSGD In this section, by applying Theorem˜4.5, we bound the number of iterations required to solve the DDIOP associated with an MILP when incorporating a concrete gradient-based optimization method into the update rule of Algorithm˜1. Let diam(Θ)diam( ) denote the diameter of Θ . In what follows, we use the fact that each variant of PSGD satisfies ˜4.1 and admits an error bound for the best iterate (Kitaoka, 2024, Propositions 9.2 and 9.8). Then, by Theorem˜4.5, the following results hold. PSGD (SRSS) When the learning rate is SRSS, one can explicitly construct the function QL,θ1Q_L,θ^1 (see Kitaoka, 2024, Proposition 9.2); hence, one can bound the number of iterations required to solve the DDIOP associated with an MILP as follows: Corollary 4.8 (Kitaoka, 2024, Corollary 4.7). Under ˜3 and 3, Algorithm˜1 with PSGD (SRSS) solves Equation˜3.2 exactly within at most max(1,(diam(Θ)2+(1+log2)β2L(ℓsub)2βγ(ℓsub))2−2) (1, ( diam( )^2+(1+ 2)β^2L( _sub)^2βγ( _sub) )^2-2 ) iterations. PSGD (SRSL) When the learning rate is SRSL, one can explicitly construct the function QL,θ1Q_L,θ^1 (see Kitaoka, 2024, Proposition 9.8); hence, one can bound the number of iterations required to solve the DDIOP associated with an MILP as follows: Corollary 4.9 (Kitaoka, 2024, Corollary 4.9). Under ˜3 and 3, Algorithm˜1 with PSGD (SRSL) solves Equation˜3.2 exactly within at most max(1,(L(ℓsub)(diam(Θ)2+(1+log2)β2)βγ(ℓsub))2−2) (1, ( L( _sub)(diam( )^2+(1+ 2)β^2)βγ( _sub) )^2-2 ) iterations. 4.3. Extension: finite-time attainment of the PLF minimum As with the suboptimality loss, the number of iterations required to attain the minimum value 0 of the PLF can also be bounded in terms of the constant γ(ℓsub)γ( _sub) (Kitaoka, 2024, Theorems 4.10 and 4.11). Theorem 4.10 (Kitaoka, 2024, Theorem 4.10(B)). Suppose that ˜3 and 3 hold. Let θtt\θ^t\_t be the sequence obtained by implementing the update rule updatett\update_t\_t in Algorithm˜1 via PSGD (SRSS). Then the condition ℓplf(θT)=0 _plf(θ^T)=0 is attained within at most max(4(1+log2)2L(ℓsub)4β2γ(ℓsub)2−2,(1+diam(Θ)2(2−2)βγ(ℓsub))2) ( 4(1+ 2)^2L( _sub)^4β^2γ( _sub)^2-2, (1+ diam( )^2(2- 2)βγ( _sub) )^2 ) iterations. Theorem 4.11 (Kitaoka, 2024, Theorem 4.11(B)). Suppose that ˜3 and 3 hold. Let θtt\θ^t\_t be the sequence obtained by implementing the update rule updatett\update_t\_t in Algorithm˜1 via PSGD (SRSL). Then the condition ℓplf(θT)=0 _plf(θ^T)=0 holds within at most max(4(1+log2)2L(ℓsub)2β2γ(ℓsub)2−2,(1+diam(Θ)2L(ℓsub)(2−2)βγ(ℓsub))2) ( 4(1+ 2)^2L( _sub)^2β^2γ( _sub)^2-2, (1+ diam( )^2L( _sub)(2- 2)βγ( _sub) )^2 ) iterations. Since these upper bounds are also of the form O(γ(ℓsub)−2)O\! (γ( _sub)^-2 ) in γ(ℓsub)γ( _sub), substituting the lower bounds on γ(ℓsub)γ( _sub) given in ˜4.4 yields the number of iterations required to attain the PLF minimum as an explicit function of the problem size as well (˜7). 4.4. Lower bounds on γ(ℓsub)γ( _sub) for ILPs The iteration-complexity upper bounds given by Theorem˜4.5, ˜4.2 and 4.2, and Theorems˜4.10 and 4.11 all depend on the constant γ(ℓsub)γ( _sub). Although γ(ℓsub)>0γ( _sub)>0 by ˜4.1, estimating the number of iterations as a function of the problem size requires a lower bound on γ(ℓsub)γ( _sub). In this subsection, we provide explicit lower bounds on γ(ℓsub)γ( _sub) when the forward problem is an integer linear program (ILP, ˜6.1). Proofs and details are given in ˜6. In what follows, when the feasible region is given by a linear inequality system X(s)=x∈ℤd∣Ax≤b(s)X(s)=\x ^d Ax≤ b(s)\, we use the ℓ∞ _∞ norm of the Graver basis (A~)G( A) (˜6.5) of the slack-augmented matrix A~=[A∣Ip] A=[A I_p], C:=g∞(A~)=max‖g‖∞∣g∈(A~)∈ℤ≥1,C:=g_∞( A)= \\|g\|_∞ g ( A)\ _≥ 1, to describe the bounds. The main lower bounds are summarized in Table˜1 (see ˜6 for details). Table 1. Lower bounds on the constant γ(ℓsub)γ( _sub) for ILPs (˜6). Here m=(mi)im=(m_i)_i collects the per-coordinate ranges of the features, and C=g∞(A~)C=g_∞( A) is the ℓ∞ _∞ norm of the Graver basis of A~=[A∣Ip] A=[A I_p]. Whereas the bound for general ILPs depends on ∥m∥2 m _2 and NdN^d, the bound for linear inequality constraints is determined solely by C and is independent of the right-hand side, the feature range, and the dimension-dependent exponent of the sample size. Setting Θ=Δd−1 = ^d-1 Reference General ILP 1Ndmax(d−1,2)∥m∥2d−1 1N^d (d-1, 2)\, m _2^d-1 Theorem˜6.6 M-convex Ω(1Nd2) \! ( 1Nd^2 ) Theorem˜6.14 M♮-convex Ω(1Nd2) \! ( 1Nd^2 ) Theorem˜6.19 Linear inequalities (constant C) Ω(1Nd(d+1)/2(2C)d−1) \! ( 1N\,d^(d+1)/2(2C)^d-1 ) Theorem˜6.24 Totally unimodular (C=1C=1) Ω(1Nd(d+1)/22d−1) \! ( 1N\,d^(d+1)/22^d-1 ) ˜6.5.2 Here mi=sups∈(maxx∈X(s)fi(x,s)−minx∈X(s)fi(x,s))m_i= _s ( _x∈ X(s)f_i(x,s)- _x∈ X(s)f_i(x,s) ). For M-convex and M♮-convex sets (˜6.3 and 6.4), one obtains polynomial-in-dimension bounds that are independent of ∥m∥2 m _2. These bounds are obtained directly by constructing explicit test sets, without going through properties of the coefficient matrices of the describing inequality systems (such as total unimodularity), and they are far better than the bound for general linear inequality constraints (˜6.5.2). Substituting these lower bounds into the iteration-complexity upper bounds of ˜4.2 and 4.2, one can evaluate the number of iterations required to solve the DDIOP for MILPs Equation˜3.2 exactly as an explicit function of the problem size. For example, when the constraints form a totally unimodular linear inequality system, PSGD (SRSS) solves Equation˜3.2 exactly within at most O(N2d+1 4d−1poly(diam(Θ),β,L(ℓsub)))O\! (N^2\,d^d+1\,4^d-1\,poly(diam( ),β,L( _sub)) ) iterations. Iteration upper bounds for the other cases are summarized in ˜7. Remark 4.12. The lower bounds in Table˜1 can be exponentially small in the dimension d (e.g., (2C)−(d−1)(2C)^-(d-1)). Hence they imply that the corresponding iteration-complexity upper bounds can be exponentially large, which is consistent with the computational hardness of inverse optimization; for instance, Aswani et al. (2018, Theorem 1) establish NP-hardness for a formulation with noisy data (see also ˜2). The aim of this subsection is not to improve the worst-case complexity, but to quantify γ(ℓsub)γ( _sub) in terms of the problem structure (the ℓ∞ _∞ norm C of the Graver basis of the constraint matrix). 5. Comparison tables 5.1. DDIOP for MILPs A performance comparison of methods for solving the DDIOP for MILPs (Equation˜3.2) is provided in Table˜2. Table 2. Performance comparison of methods for solving the DDIOP for MILPs (Equation˜3.2). The integer T denotes the number of iterations or the number of optimization calls. The integer t denotes the iteration index or the optimization-call index. Method Suboptimality loss UPA O(diam(Θ)L(ℓsub)T−1/(d−1))O\! (diam( )\,L( _sub)\,T^- 1(d-1) ) (cf. Flatto and Newman, 1977, Theorem 2.1) RPA Oℙ(diam(Θ)L(ℓsub)(logT/T)1/(d−1))O_P\! (diam( )\,L( _sub)\, ( T/T ) 1(d-1) ) (cf. Reznikov and Saff, 2015, Corollary 2.3) MWU (Arora et al., 2012) O(L(ℓsub)logd/T)O (L( _sub) d/ T ), provided that Θ=Δd−1 = ^d-1 (Bärmann et al., 2018, Theorem 3.5) Besbes et al. (2021, 2025) O(d4logT/T)O (d^4 T/T ), provided that Θ is the unit sphere and L(ℓsub)≤1L( _sub)≤ 1 Gollapudi et al. (2021) O(dlogT/T)O (d T/T ), O(d2(d+1)/T)O (d^2(d+1)/T ) provided that Θ is the unit ball and L(ℓsub)≤1L( _sub)≤ 1 ONS (Hazan et al., 2007) O(diam(Θ)L(ℓsub)dlog(T/d)/T)O (diam( )\,L( _sub)\,d (T/d)/T ) (Sakaue et al., 2025, Theorem 3.1) MetaGrad (van Erven and Koolen, 2016; van Erven et al., 2021) O(diam(Θ)L(ℓsub)dlog(T/d)/T)O (diam( )\,L( _sub)\,d (T/d)/T ) (Sakaue et al., 2025, Theorem 4.1) PSGD O(diam(Θ)L(ℓsub)/T)O (diam( )\,L( _sub)/ T ) (Bärmann et al., 2018, Theorem 3.11) (with step size diam(Θ)L(ℓsub)−1t−1/2diam( )L( _sub)^-1t^-1/2) PSGD 0 if T≥max(1,(diam(Θ)2+(1+log2)β2L(ℓsub)2βγ(ℓsub))2−2)T≥ (1, ( diam( )^2+(1+ 2)β^2L( _sub)^2βγ( _sub) )^2-2 ) (with step size βt−1/2β t^-1/2) (Kitaoka, 2024, Corollary 4.7) PSGD 0 if T≥max(1,(L(ℓsub)(diam(Θ)2+(1+log2)β2)βγ(ℓsub))2−2)T≥ (1, ( L( _sub)\,(diam( )^2+(1+ 2)β^2)βγ( _sub) )^2-2 ) (with step length βt−1/2β t^-1/2) (Kitaoka, 2024, Corollary 4.9) 5.2. PLF minimization A performance comparison of methods for solving the minimum value of the PLF for MILPs is provided in Table˜3. Table 3. Performance comparison of methods for minimizing the PLF for MILPs. The notation is the same as in Table˜2. Method Distance between the set where the PLF equals 0 and the learned weight θTθ^T (when the PLF is nonzero) UPA O(diam(Θ)T−1/(d−1))O\! (diam( )\,T^- 1(d-1) ) RPA Oℙ(diam(Θ)(logT/T)1/(d−1))O_P\! (diam( )\, ( T/T ) 1(d-1) ) PSGD diam(Θ)2−β(2−2)(T−1)(2γ(ℓsub)−βL(ℓsub)22(1+log2)T+2)diam( )^2-β(2- 2) ( T-1 ) (2γ( _sub)-β L( _sub)^2 2(1+ 2) T+2 ) (with step size βt−1/2β t^-1/2) (Kitaoka, 2024, Theorem 4.10) PSGD diam(Θ)2−β(2−2)(T−1)(2γ(ℓsub)L(ℓsub)−β2(1+log2)T+2)diam( )^2-β(2- 2) ( T-1 ) (2 γ( _sub)L( _sub)-β 2(1+ 2) T+2 ) (with step length βt−1/2β t^-1/2) (Kitaoka, 2024, Theorem 4.11) 6. Lower bounds on the constant γ(ℓsub)γ( _sub) for ILPs In this section, we lower-bound the constant γ(ℓsub)γ( _sub) defined in Equation˜4.3. In particular, when the forward problem has structure—such as being an integer linear program (ILP)—we give explicit lower bounds on γ(ℓsub)γ( _sub), which make the iteration-complexity upper bound QL(ℓsub),θ1(γ(ℓsub))Q_L( _sub),θ^1(γ( _sub)) of Theorem˜4.5 concrete. Throughout this section, we use that Equation˜4.1 holds under ˜3 and 3. 6.1. A min-max representation of the constant γ(ℓsub)γ( _sub) We consider the following assumption, modeling the case where the forward problem is an integer linear program. Assumption 6.1 (Integer linear program). Let the decision space satisfy ⊂ℤdX ^d_X, and let the feature map satisfy f(×)⊂ℤdf(X×S) ^d. Proposition 6.2. Let Θ be a bounded closed convex set, and let A⊂ℝdA ^d be a finite set. Then maxθ∈Θmina∈Aθ⊤a=mina∈ConvAmaxθ∈Θθ⊤a. _θ∈ _a∈ Aθ a= _a _θ∈ θ a. proof. By the maximum principle, maxθ∈Θmina∈Aθ⊤a=maxθ∈Θmina∈ConvAθ⊤a. _θ∈ _a∈ Aθ a= _θ∈ _a θ a. By the minimax theorem, maxθ∈Θmina∈ConvAθ⊤a=mina∈ConvAmaxθ∈Θθ⊤a. _θ∈ _a θ a= _a _θ∈ θ a. ∎ Proposition 6.3. Suppose that ˜3 and 3 hold. Then γ(ℓsub)=1Nmin(an)n∈Conv(∏n=1NY(n)∖(a(n))n)maxθ∈Θ∑n=1Nθ⊤(a(n)−an).γ( _sub)= 1N _(a^n)_n ( _n=1^NY^(n) \(a^(n))_n\ ) _θ∈ _n=1^Nθ (a^(n)-a^n ). proof. This follows from ˜6.1. ∎ 6.1.1. The case where Θ is the unit ball By ˜6.1, γ(ℓsub)=1Nmin(an)n∈Conv(∏n=1NY(n)∖(a(n))n)‖∑n=1Na(n)−∑n=1Nan‖.γ( _sub)= 1N _(a^n)_n ( _n=1^NY^(n) \(a^(n))_n\ ) \| _n=1^Na^(n)- _n=1^Na^n \|. (6.1) From this expression, the following theorem follows. Theorem 6.4. Suppose that ˜3, 3 and 6.1 hold, and let Θ=Bd =B^d with d≥2d≥ 2. In addition, assume that the convex hull of the set of sums W:=∑n=1Nbn∣(bn)n∈∏n=1NY(n)∖(a(n))nW:=\ _n=1^Nb^n (b^n)_n∈ _n=1^NY^(n) \(a^(n))_n\\ is full-dimensional, that is, dimConv(W)=d (W)=d. Here W is the set obtained by collecting, for each choice of points bnb^n from the vertex sets Y(n)Y^(n), the total sums ∑n=1Nbn _n=1^Nb^n, excluding the sum P:=∑n=1Na(n)P:= _n=1^Na^(n) corresponding to the observed solution. The condition dimConv(W)=d (W)=d is equivalent to W not being contained in any hyperplane of ℝdR^d. Then γ(ℓsub)≥1Ndd−1‖m‖2d−1.γ( _sub)≥ 1N^d d-1\|m\|_2^d-1. For the proof, see ˜6.7. Remark 6.5. As a sufficient condition for the full-dimensionality condition dimConv(W)=d (W)=d, the following holds: if there exists a sample index n0∈1,…,Nn_0∈\1,…,N\ such that the convex hull of the vertex set with the vertex a(n0)a^(n_0) corresponding to the observed solution removed is full-dimensional, that is, dimConv(Y(n0)∖a(n0))=d \! (Y^(n_0) \a^(n_0)\ )=d holds, then dimConv(W)=d (W)=d holds. Indeed, fixing bn=a(n)b^n=a^(n) for n≠n0n≠ n_0 and letting bn0∈Y(n0)∖a(n0)b^n_0∈ Y^(n_0) \a^(n_0)\ vary, the corresponding tuple differs from (a(n))n(a^(n))_n since bn0≠a(n0)b^n_0≠ a^(n_0), so its sum ∑n=1Nbn=(P−a(n0))+bn0 _n=1^Nb^n= (P-a^(n_0) )+b^n_0 belongs to W. Therefore W⊇(P−a(n0))+(Y(n0)∖a(n0)),W (P-a^(n_0) )+ (Y^(n_0) \a^(n_0)\ ), and since translation preserves dimension, dimConv(W)≥dimConv(Y(n0)∖a(n0))=d, (W)\ ≥\ \! (Y^(n_0) \a^(n_0)\ )=d, that is, we obtain dimConv(W)=d (W)=d. Intuitively, this sufficient condition requires the natural non-degeneracy, for a single sample, that “for some single sample s(n0)s^(n_0), the image of the features f(X(s(n0)),s(n0))f(X(s^(n_0)),s^(n_0)) (even after removing the observed vertex a(n0)a^(n_0)) is not contained in any hyperplane of ℝdR^d and spreads out in all directions.” 6.1.2. The case where Θ is the probability simplex By ˜6.1, γ(ℓsub)=1Nmin(an)n∈Conv(∏n=1NY(n)∖(a(n))n)maxi=1,…,d(∑n=1Nai(n)−∑n=1Nain).γ( _sub)= 1N _(a^n)_n ( _n=1^NY^(n) \(a^(n))_n\ ) _i=1,…,d ( _n=1^Na_i^(n)- _n=1^Na_i^n ). (6.2) From this expression, the following theorem follows. Theorem 6.6. Suppose that ˜3, 3 and 6.1 hold, and let Θ=Δd−1 = ^d-1 with d≥2d≥ 2. In addition, assume that Y(n0)Y^(n_0) is not a singleton for some n0∈1,…,Nn_0∈\1,…,N\, that is, that the index set ∏n=1NY(n)∖(a(n))n _n=1^NY^(n) \(a^(n))_n\ of the minimum in Equation˜4.3 is nonempty (nondegeneracy). Then γ(ℓsub)≥1Ndmax(d−1,2)‖m‖2d−1.γ( _sub)≥ 1N^d (d-1, 2)\|m\|_2^d-1. For the proof, see ˜6.8. Remark 6.7. If the nondegeneracy assumption fails, that is, if Y(n)Y^(n) is a singleton for every n, then the index set of the minimum in Equation˜4.3 is empty, so under the convention that the minimum over the empty set is +∞+∞ we have γ(ℓsub)=+∞γ( _sub)=+∞, and the lower bound above holds trivially (in this case f(⋅,s(n))f(·,s^(n)) is constant on X(s(n))X(s^(n)) for each n, so ℓsub≡0 _sub≡ 0 and every θ∈Θθ∈ solves Equation˜3.2). We also note that, in the present theorem, the full-dimensionality assumption dimConv(W)=d (W)=d imposed in the unit-ball case (Theorem˜6.4) can be replaced by nondegeneracy alone: the downward closure Q=Conv(W)−ℝ≥0dQ=Conv(W)-R_≥ 0^d used in the proof (˜6.8) is automatically full-dimensional as soon as Conv(W)≠∅Conv(W)≠ . 6.2. γ(ℓsub)γ( _sub) for discrete feasible regions For a bounded discrete set X⊂ℤdX ^d, a set T is a test set of X if the following holds: for any x1∈Xx^1∈ X, θ∈Θθ∈ with θ⊤x1<maxx∈Xθ⊤xθ x^1< _x∈ Xθ x, there exists g∈g such that x1+g∈X,θ⊤g>0.x^1+g∈ X, θ g>0. Proposition 6.8. Take a bounded discrete set X⊂ℤdX ^d (which is finite since it is bounded) and a test set T of X. Then, for any x1∈Xx^1∈ X and θ∈Θθ∈ , there exist some x∗∈argmaxx∈Xθ⊤x^*∈ *arg\,max_x∈ Xθ x and some g1,…,gr∈g^1,…,g^r such that x∗−x1=∑i=1rgi,θ⊤gi>0.x^*-x^1= _i=1^rg^i, θ g^i>0. proof. The set X⊂ℤdX ^d is bounded, hence finite. We construct a sequence x(k)k≥0\x^(k)\_k≥ 0 inductively. Set x(0):=x1x^(0):=x^1. As long as x(k)∈Xx^(k)∈ X satisfies θ⊤x(k)<maxx∈Xθ⊤xθ x^(k)< _x∈ Xθ x, the definition of a test set yields some g(k+1)∈g^(k+1) with x(k+1):=x(k)+g(k+1)∈X,θ⊤g(k+1)>0.x^(k+1):=x^(k)+g^(k+1)∈ X, θ g^(k+1)>0. Then θ⊤x(k+1)=θ⊤x(k)+θ⊤g(k+1)>θ⊤x(k)θ x^(k+1)=θ x^(k)+θ g^(k+1)>θ x^(k), so θ⊤x(k)k\θ x^(k)\_k is strictly increasing; in particular x(0),x(1),…x^(0),x^(1),… are pairwise distinct points of X. Since X is finite, this construction stops after finitely many steps r≥0r≥ 0. The stopping point x(r)x^(r) does not satisfy the continuation condition θ⊤x(r)<maxx∈Xθ⊤xθ x^(r)< _x∈ Xθ x, i.e., θ⊤x(r)=maxx∈Xθ⊤xθ x^(r)= _x∈ Xθ x, so x(r)∈argmaxx∈Xθ⊤x^(r)∈ *arg\,max_x∈ Xθ x. Setting x∗:=x(r)x^*:=x^(r) and gi:=g(i)g^i:=g^(i) (i=1,…,ri=1,…,r), telescoping gives x∗−x1=∑i=1r(x(i)−x(i−1))=∑i=1rgi,θ⊤gi>0(i=1,…,r)x^*-x^1= _i=1^r (x^(i)-x^(i-1) )= _i=1^rg^i, θ g^i>0 (i=1,…,r) (if x1x^1 is already optimal, then r=0r=0 and the sum is empty). ∎ Lemma 6.9 (Reduction of the lower bound via a test set). Suppose that ˜3 and 3 hold, and assume in addition that, for each n, f(x,s(n))=xf(x,s^(n))=x, Y(n)⊆X(s(n))Y^(n) X(s^(n)) and that ⊂ℤdT ^d is a test set of X(s(n))X(s^(n)). Let θ∗θ^* be the true weight. Then, for any θ†∈Θθ ∈ , γ(ℓsub)≥1Nming∈,θ∗⊤g>0θ†⊤g.γ( _sub)\ ≥\ 1N _g ,\,θ^* g>0θ g. proof. If the right-hand side is nonpositive, the claim is trivial since γ(ℓsub)≥0γ( _sub)≥ 0; hence we may assume μ:=ming∈,θ∗⊤g>0θ†⊤g>0μ:= _g ,\,θ^* g>0θ g>0. Choosing θ=θ†θ=θ in the maxθ _θ of (4.3) gives γ(ℓsub)≥1Nmin(an)n≠(a(n))n∑n=1Nθ†⊤(a(n)−an).γ( _sub)\ ≥\ 1N _(a^n)_n≠(a^(n))_n\ _n=1^Nθ (a^(n)-a^n). Fix any (an)n≠(a(n))n(a^n)_n≠(a^(n))_n. By ˜3, each a(n)=a∗(θ∗,s(n))a^(n)=a^*(θ^*,s^(n)) is the unique θ∗θ^*-maximizer over Y(n)Y^(n), so θ∗⊤(a(n)−an)≥0θ^* (a^(n)-a^n)≥ 0. Moreover a(n)=a∗(θ∗,s(n))a^(n)=a^*(θ^*,s^(n)) is the (by ˜3, unique) maximizer of θ∗θ^* over X(s(n))X(s^(n)), and an∈X(s(n))a^n∈ X(s^(n)). Applying ˜6.2 with X=X(s(n))X=X(s^(n)), θ=θ∗θ=θ^*, and x1=anx^1=a^n, we obtain a decomposition toward the maximizer a(n)a^(n), namely a(n)−an=∑ign,ia^(n)-a^n= _ig^n,i with gn,i∈g^n,i and θ∗⊤gn,i>0θ^* g^n,i>0. Therefore a(n)−an=∑kαkngn,k,αkn∈ℤ≥0,gn,k∈,θ∗⊤gn,k>0.a^(n)-a^n= _kα^n_kg^n,k, α^n_k _≥ 0,\ g^n,k ,\ θ^* g^n,k>0. Hence θ†⊤gn,k≥μθ g^n,k≥μ, so ∑nθ†⊤(a(n)−an)=∑n∑kαknθ†⊤gn,k≥μ∑n∑kαkn. _nθ (a^(n)-a^n)= _n _kα^n_k\,θ g^n,k\ ≥\ μ _n _kα^n_k. Since the tuple differs from (a(n))n(a^(n))_n, there is some n0n_0 with an0≠a(n0)a^n_0≠ a^(n_0), hence ∑n∑kαkn≥1 _n _kα^n_k≥ 1. Therefore ∑nθ†⊤(a(n)−an)≥μ _nθ (a^(n)-a^n)≥μ. Since (an)n(a^n)_n was arbitrary, the claim follows. ∎ 6.3. M-convex sets and linear programming Definition 6.10 (M-convex set, Murota, 2003, cf.). A nonempty set X⊆ℤdX ^d is an M-convex set if it satisfies the following exchange axiom: for all x,y∈Xx,y∈ X and every index i with xi>yix_i>y_i, there exists an index j with xj<yjx_j<y_j such that x−ei+ej∈Xx-e_i+e_j∈ X and y+ei−ej∈Xy+e_i-e_j∈ X (where eie_i is the i-th unit vector). Every element of an M-convex set has the same coordinate sum ∑ixi _ix_i, and M-convex sets coincide with the sets of integer points of integral base polytopes. Assumption 6.11 (M-convex action set with identity features). Let d=d_X=d. For each s∈s , let X(s)⊆ℤdX(s) ^d be an M-convex set in ℤdZ^d, and let the feature map be the identity, i.e., fi(x,s)=xif_i(x,s)=x_i (i=1,…,di=1,…,d). The indicator function of an M-convex set X, δX(x):=0, if x∈X,∞, if x∉X, _X(x):=0, if x∈ X,\,∞, if x ∈ X, is an M-convex function. The following is known. Proposition 6.12 (Murota, 1996, 1998, 2003). A test set of an M-convex set can be taken to be the set of single-exchange vectors =ei−ej∣i≠jT=\e_i-e_j i≠ j\. 6.3.1. The case where Θ is the unit ball Theorem 6.13. Suppose that ˜3, 3 and 6.3 hold, and let Θ=Bd=θ∈ℝd∣‖θ‖2≤1 =B^d=\θ ^d \|θ\|_2≤ 1\ with d≥2d≥ 2. Then γ(ℓsub)≥1N⋅23d(d2−1)=Ω(1Nd3/2).γ( _sub)≥ 1N· 2 3 d(d^2-1)= \! ( 1N\,d^3/2 ). proof. By ˜6.3, =ei−ejT=\e_i-e_j\ is a test set. Reordering coordinates so that θ1∗≥⋯≥θd∗θ^*_1≥·s≥θ^*_d, we have θ∗⊤(ei−ej)=θi∗−θj∗>0θ^* (e_i-e_j)=θ^*_i-θ^*_j>0 only for i<ji<j. Set θi†:=α((d+1)/2−i)θ _i:=α ((d+1)/2-i ) with α:=23/d(d2−1)α:=2 3/ d(d^2-1); then ‖θ†‖2=1\|θ \|_2=1, i.e., θ†∈Bdθ ∈ B^d. For each g=ei−ejg=e_i-e_j (i<ji<j) with θ∗⊤g>0θ^* g>0, θ†⊤g=θi†−θj†=(j−i)α≥α.θ g=θ _i-θ _j=(j-i)α≥α. Hence, by ˜6.2, γ(ℓsub)≥α/Nγ( _sub)≥α/N. ∎ 6.3.2. The case where Θ is the probability simplex Theorem 6.14. Suppose that ˜3, 3 and 6.3 hold, and let Θ=Δd−1=θ∈ℝ≥0d∣∑i=1dθi=1 = ^d-1=\θ _≥ 0^d _i=1^d _i=1\ with d≥2d≥ 2. Then γ(ℓsub)≥1N⋅2d(d−1)=Ω(1Nd2).γ( _sub)≥ 1N· 2d(d-1)= \! ( 1N\,d^2 ). proof. By ˜6.3, =ei−ejT=\e_i-e_j\ is a test set. Reordering coordinates so that θ1∗≥⋯≥θd∗θ^*_1≥·s≥θ^*_d, we have θ∗⊤(ei−ej)>0θ^* (e_i-e_j)>0 only for i<ji<j. Set θi†:=(d−i)⋅2d(d−1)θ _i:=(d-i)· 2d(d-1) (i=1,…,di=1,…,d); then θ†≥0θ ≥ 0 and ∑iθi†=2d(d−1)∑i=1d(d−i)=1 _iθ _i= 2d(d-1) _i=1^d(d-i)=1, so θ†∈Δd−1θ ∈ ^d-1. For each g=ei−ejg=e_i-e_j (i<ji<j) with θ∗⊤g>0θ^* g>0, θ†⊤g=θi†−θj†=(j−i)⋅2d(d−1)≥2d(d−1).θ g=θ _i-θ _j=(j-i)· 2d(d-1)≥ 2d(d-1). Hence, by ˜6.2, γ(ℓsub)≥1N⋅2d(d−1)γ( _sub)≥ 1N· 2d(d-1). ∎ 6.4. M♮-convex sets and linear programming Definition 6.15 (M♮-convex set, Murota, 2003, cf.). A nonempty set X⊆ℤdX ^d is an M♮-convex set if it satisfies the following exchange axiom: for all x,y∈Xx,y∈ X and every index i with xi>yix_i>y_i, either (i) x−ei∈Xx-e_i∈ X and y+ei∈Xy+e_i∈ X, or (i) there exists an index j with xj<yjx_j<y_j such that x−ei+ej∈Xx-e_i+e_j∈ X and y+ei−ej∈Xy+e_i-e_j∈ X. M♮-convex sets are obtained as coordinate projections of M-convex sets and coincide with the sets of integer points of generalized base polytopes. Assumption 6.16 (M♮-convex action set with identity features). Let d=d_X=d. For each s∈s , let X(s)⊆ℤdX(s) ^d be an M♮-convex set in ℤdZ^d, and let the feature map be the identity, i.e., fi(x,s)=xif_i(x,s)=x_i (i=1,…,di=1,…,d). The indicator function of an M♮-convex set X, δX(x) _X(x) is an M♮-convex function. The following is known. Proposition 6.17 (Murota and Shioura, 1999; Murota, 2003). A test set of an M♮-convex set can be taken to be the set of single-exchange vectors =ei−ej,±ei∣i≠jT=\e_i-e_j,± e_i i≠ j\. 6.4.1. The case where Θ is the unit ball Theorem 6.18. Suppose that ˜3, 3 and 6.4 hold, and let Θ=Bd=θ∈ℝd∣‖θ‖2≤1 =B^d=\θ ^d \|θ\|_2≤ 1\ with d≥2d≥ 2. Then γ(ℓsub)≥1N6d(d+1)(2d+1)≥1Nd3/2=Ω(1Nd3/2).γ( _sub)≥ 1N 6d(d+1)(2d+1)≥ 1N\,d^3/2= \! ( 1N\,d^3/2 ). proof. By ˜6.4, =ei−ej,±eiT=\e_i-e_j,\,± e_i\ is a test set. Reorder coordinates so that θ1∗≥⋯≥θd∗θ^*_1≥·s≥θ^*_d, and let p,z,np,z,n be the numbers of positive, zero, and negative components (p+z+n=dp+z+n=d, with positive components first, zero components in the middle, and negative components last). Define an integer vector s∈ℤds ^d by s=(p,p−1,…,1,0,…,0⏟z,−1,…,−n),s=(\,p,p-1,…,1,\ 0,…,0_z,\ -1,…,-n\,), and set θ†:=csθ :=c\,s with c:=(∑isi2)−1/2c:=( _is_i^2)^-1/2 (so ‖θ†‖2=1\|θ \|_2=1, i.e., θ†∈Bdθ ∈ B^d). If θ∗=0θ^*=0, then by Appendix˜C ˜3 fails unless every X(s(n))X(s^(n)) is a singleton, in which case the index set of the minimum in Equation˜4.3 is empty and the bound holds trivially; hence θ∗≠0θ^*≠ 0, so s≠0s≠ 0 and c is well-defined. The vectors g∈g with θ∗⊤g>0θ^* g>0 are of the following three types, each satisfying θ†⊤g≥cθ g≥ c: • g=ei−ejg=e_i-e_j (with θi∗>θj∗θ^*_i>θ^*_j): since si−sj≥1s_i-s_j≥ 1, θ†⊤g=c(si−sj)≥cθ g=c(s_i-s_j)≥ c; • g=+eig=+e_i (with θi∗>0θ^*_i>0): since si≥1s_i≥ 1, θ†⊤g=csi≥cθ g=cs_i≥ c; • g=−eig=-e_i (with θi∗<0θ^*_i<0): since −si≥1-s_i≥ 1, θ†⊤g=c(−si)≥cθ g=c(-s_i)≥ c. Hence, by ˜6.2, γ(ℓsub)≥c/Nγ( _sub)≥ c/N. Finally, from ∑isi2=∑k=1pk2+∑k=1nk2≤∑k=1dk2=d(d+1)(2d+1)6 _is_i^2= _k=1^pk^2+ _k=1^nk^2≤ _k=1^dk^2= d(d+1)(2d+1)6 (as p+n≤dp+n≤ d), together with d(d+1)(2d+1)≤6d3d(d+1)(2d+1)≤ 6d^3, we obtain c≥6d(d+1)(2d+1)≥d−3/2.c≥ 6d(d+1)(2d+1)≥ d^-3/2. ∎ 6.4.2. The case where Θ is the probability simplex Theorem 6.19. Suppose that ˜3, 3 and 6.4 hold, and let Θ=Δd−1=θ∈ℝ≥0d∣∑i=1dθi=1 = ^d-1=\θ _≥ 0^d _i=1^d _i=1\ with d≥2d≥ 2. Then γ(ℓsub)≥1N⋅2d(d+1)=Ω(1Nd2).γ( _sub)≥ 1N· 2d(d+1)= \! ( 1N\,d^2 ). proof. By ˜6.4, =ei−ej,±eiT=\e_i-e_j,\,± e_i\ is a test set. On Θ=Δd−1 = ^d-1 we have θ∗≥0θ^*≥ 0, so θ∗⊤(−ei)=−θi∗≤0θ^* (-e_i)=-θ^*_i≤ 0, i.e., g=−eig=-e_i does not satisfy θ∗⊤g>0θ^* g>0. Reorder coordinates so that θ1∗≥⋯≥θd∗θ^*_1≥·s≥θ^*_d, and set θi†:=2(d−i+1)d(d+1)(i=1,…,d).θ _i:= 2(d-i+1)d(d+1) (i=1,…,d). These are positive and decreasing, with ∑iθi†=2d(d+1)∑i=1d(d−i+1)=1 _iθ _i= 2d(d+1) _i=1^d(d-i+1)=1, so θ†∈Δd−1θ ∈ ^d-1. The vectors g∈g with θ∗⊤g>0θ^* g>0 are of the following two types, each satisfying θ†⊤g≥2d(d+1)θ g≥ 2d(d+1): • g=ei−ejg=e_i-e_j (with θi∗>θj∗θ^*_i>θ^*_j, hence i<ji<j): θ†⊤g=(j−i)2d(d+1)≥2d(d+1)θ g=(j-i) 2d(d+1)≥ 2d(d+1); • g=+eig=+e_i (with θi∗>0θ^*_i>0): θ†⊤g=θi†≥θd†=2d(d+1)θ g=θ _i≥θ _d= 2d(d+1). Hence, by ˜6.2, γ(ℓsub)≥1N⋅2d(d+1)γ( _sub)≥ 1N· 2d(d+1). ∎ 6.5. Linear inequality constraints and the Graver basis The individual examples so far (M-convex and M♮-convex) share the property that X(s)X(s) can be represented by an integer linear inequality system over ℤdZ^d and that a test set can be taken to be a Graver basis. In this subsection, we give a lower bound determined solely by the ℓ∞ _∞ norm of the Graver basis of the constraint matrix A. In particular, the bound is independent of the right-hand side b(s)b(s), the feature range ‖m‖2\|m\|_2, and the factor Nd−1N^d-1 in the sample size. This is an essential improvement over the general ILP lower bounds of Theorems˜6.4 and 6.6. Assumption 6.20 (Linear inequality constraints with identity features). Let d=d_X=d. For a constraint matrix A∈ℤp×dA ^p× d and a right-hand side b(s)∈ℤpb(s) ^p, let X(s)=x∈ℤd∣Ax≤b(s).X(s)=\x ^d Ax≤ b(s)\. Let the feature map be the identity, i.e., fi(x,s)=xif_i(x,s)=x_i (i=1,…,di=1,…,d). Definition 6.21 (Graver basis, Onn, 2010; Sturmfels, 1996, cf.). For an integer matrix B∈ℤq×nB ^q× n, let its integer kernel be kerℤ(B):=z∈ℤn∣Bz=0 _Z(B):=\z ^n Bz=0\. For vectors u,v∈ℝnu,v ^n, we say that u is conformal to v, written u⊑vu v, if uivi≥0u_iv_i≥ 0 (same sign) and |ui|≤|vi||u_i|≤|v_i| for every coordinate i. The Graver basis (B)G(B) of B is the (finite) set of ⊑ -minimal elements of kerℤ(B)∖ _Z(B) \0\. Introducing slack variables converts the system into an equality system A~x~=b(s) A x=b(s) (with A~=[A∣Ip]∈ℤp×(d+p) A=[A I_p] ^p×(d+p), x~=(x,y) x=(x,y), y≥0y≥ 0). We define the ℓ∞ _∞ norm of the Graver basis (A~)G( A) (˜6.5) by g∞(A~):=max‖g‖∞∣g∈(A~)∈ℤ≥1.g_∞( A):= \\|g\|_∞ g ( A)\ _≥ 1. This is determined by A~ A (and hence by A) alone, and does not depend on b(s)b(s), ‖m‖2\|m\|_2, or N. Proposition 6.22 (Test set via the Graver basis). Under ˜3 and 6.5, let πx:ℤd+p→ℤd _x ^d+p ^d be the projection onto the x-coordinates and set x:=πx((A~))T_x:= _x(G( A)). Then xT_x is a test set of X(s)X(s) for every s∈s , and ‖g‖∞≤g∞(A~)\|g\|_∞≤ g_∞( A) for all g∈xg _x. proof. Take any s∈s , x1∈X(s)x^1∈ X(s), and θ∈Θθ∈ with θ⊤x1<maxx∈X(s)θ⊤xθ x^1< _x∈ X(s)θ x. By ˜3, X(s)X(s) is bounded, hence finite as a subset of the integer lattice, so a maximizer x2∈argmaxx∈X(s)θ⊤x^2∈ *arg\,max_x∈ X(s)θ x exists. Lifting by slacks, set x~j:=(xj,b(s)−Axj)∈ℤd+p x^j:=(x^j,\,b(s)-Ax^j) ^d+p for j=1,2j=1,2; then A~x~j=b(s) A x^j=b(s) and the last p components (the slack components) of x~j x^j are nonnegative. For the difference z~:=x~2−x~1∈kerℤ(A~)∖0 z:= x^2- x^1∈ _Z( A) \0\, the conformal decomposition property of Graver bases (every 0≠z∈kerℤ(B)0≠ z∈ _Z(B) decomposes as a sum z=∑kgkz= _kg^k of elements of (B)G(B) with gk⊑zg^k z; Sturmfels, 1996; Onn, 2010, cf.) yields z~=∑k=1rg~k,g~k∈(A~),g~k⊑z~. z= _k=1^r g^k, g^k ( A), g^k z. Each g~k g^k is conformal to z~ z, i.e., componentwise it has the same sign as z~ z and its absolute value does not exceed |z~|| z|; hence, for every subset K⊆1,…,rK \1,…,r\, each component of the partial sum x~1+∑k∈Kg~k x^1+ _k∈ K g^k lies between the corresponding components of x~1 x^1 and x~2 x^2. In particular the slack components remain nonnegative and the equality system for A~ A is preserved, so the first d components of the partial sum belong to X(s)X(s). Now set θ~:=(θ,0)∈ℝd+p θ:=(θ,0) ^d+p; then θ~⊤z~=θ⊤(x2−x1)>0 θ z=θ (x^2-x^1)>0, so there is some k0k_0 with θ~⊤g~k0>0 θ g^k_0>0. Setting g:=πx(g~k0)∈xg:= _x( g^k_0) _x and considering the partial sum with K=k0K=\k_0\, we obtain x1+g∈X(s)x^1+g∈ X(s) and θ⊤g=θ~⊤g~k0>0θ g= θ g^k_0>0. Therefore xT_x is a test set of X(s)X(s). Finally, since the projection does not increase the ℓ∞ _∞ norm, ‖πx(g~)‖∞≤‖g~‖∞≤g∞(A~)\| _x( g)\|_∞≤\| g\|_∞≤ g_∞( A) for every g~∈(A~) g ( A). ∎ 6.5.1. The case where Θ is the unit ball Theorem 6.23. Suppose that ˜3, 3 and 6.5 hold, and let Θ=Bd=θ∈ℝd∣‖θ‖2≤1 =B^d=\θ ^d \|θ\|_2≤ 1\ with d≥2d≥ 2. Set C:=g∞(A~)C:=g_∞( A), and assume that the convex hull of S+:=g∈x∣θ∗⊤g>0S^+:=\g _x θ^* g>0\ is full-dimensional (dimConv(S+)=d (S^+)=d). Then γ(ℓsub)≥1Nd−1(2Cd)d−1=Ω(1Nd(d+1)/2(2C)d−1).γ( _sub)≥ 1N\, d-1\,(2C d)^d-1= \! ( 1N\,d^(d+1)/2\,(2C)^d-1 ). proof. By ˜6.5, xT_x is a test set with ‖g‖∞≤C\|g\|_∞≤ C for all g∈xg _x. Set S+:=g∈x∣θ∗⊤g>0⊂ℤdS^+:=\g _x θ^* g>0\ ^d. Step 1 (reduction to a distance via minimax). ˜6.2 gives γ(ℓsub)≥1Nming∈S+θ†⊤gγ( _sub)≥ 1N _g∈ S^+θ g for any θ†∈Θθ ∈ . Maximizing the right-hand side over θ†∈Bdθ ∈ B^d and applying ˜6.1 (BdB^d is compact convex and S+S^+ is finite), we obtain γ(ℓsub) γ( _sub) ≥1Nmaxθ†∈Bdming∈S+θ†⊤g=1Nminq∈Conv(S+)max‖θ†‖2≤1θ†⊤q ≥ 1N _θ ∈ B^d _g∈ S^+θ g= 1N _q (S^+) _\|θ \|_2≤ 1θ q =1Nminq∈Conv(S+)‖q‖2=1Ndist(0,Conv(S+)). = 1N _q (S^+)\|q\|_2= 1N\,dist (0,Conv(S^+) ). Since θ∗⊤g>0θ^* g>0 for each g∈S+g∈ S^+, we have θ∗⊤q>0θ^* q>0 for every q∈Conv(S+)q (S^+); in particular 0∉Conv(S+)0 (S^+). Step 2 (an integral separating hyperplane). Conv(S+)Conv(S^+) is a lattice polytope whose vertices lie in S+⊂g∈ℤd∣‖g‖∞≤CS^+⊂\g ^d \|g\|_∞≤ C\, and by assumption it is full-dimensional with 0∉Conv(S+)0 (S^+). Applying ˜6.6 with A=Conv(S+)A=Conv(S^+) and the lattice point P=0P=0 yields affinely independent vertices y1,…,yd∈S+y^1,…,y^d∈ S^+ and an integral normal a∈ℤda ^d, c∈ℤc such that Conv(S+)⊆x∣a⋅x≤cConv(S^+) \x a· x≤ c\ and a⋅0>ca· 0>c (i.e., c≤−1c≤-1). Here a is given by the cofactors of the difference vectors vk:=yk+1−y1v_k:=y^k+1-y^1 (k=1,…,d−1k=1,…,d-1; since both endpoints satisfy ∥⋅∥∞≤C\|·\|_∞≤ C, we have |(vk)j|≤2C|(v_k)_j|≤ 2C), and c=a⋅y1c=a· y^1. Step 3 (estimate). For every q∈Conv(S+)⊆x∣a⋅x≤cq (S^+) \x a· x≤ c\, the Cauchy–Schwarz inequality gives ‖q‖2=‖0−q‖2≥a⋅(0−q)‖a‖=−a⋅q‖a‖≥−c‖a‖≥1‖a‖\|q\|_2=\|0-q\|_2≥ a·(0-q)\|a\|= -a· q\|a\|≥ -c\|a\|≥ 1\|a\| (using −c≥1-c≥ 1). Hence dist(0,Conv(S+))≥1/‖a‖dist(0,Conv(S^+))≥ 1/\|a\|. Since each component of the difference vectors has width 2C2C, applying ˜6.7 with m=(2C,…,2C)m=(2C,…,2C) (‖m‖2=2Cd\|m\|_2=2C d) gives ‖a‖≤d−1(2Cd)d−1\|a\|≤ d-1\,(2C d)^d-1. Combining these, γ(ℓsub)≥1N⋅1‖a‖≥1Nd−1(2Cd)d−1.γ( _sub)≥ 1N· 1\|a\|≥ 1N\, d-1\,(2C d)^d-1. ∎ 6.5.2. The case where Θ is the probability simplex Theorem 6.24. Suppose that ˜3, 3 and 6.5 hold, and let Θ=Δd−1 = ^d-1 with d≥2d≥ 2. Set C:=g∞(A~)C:=g_∞( A). In addition, assume that Y(n0)Y^(n_0) is not a singleton for some n0∈1,…,Nn_0∈\1,…,N\ (nondegeneracy). Then γ(ℓsub)≥1Nmax(d−1,2)(2Cd)d−1=Ω(1Nd(d+1)/2(2C)d−1).γ( _sub)≥ 1N\, (d-1, 2)\,(2C d)^d-1= \! ( 1N\,d^(d+1)/2\,(2C)^d-1 ). proof. By ˜6.5, xT_x is a test set with ‖g‖∞≤C\|g\|_∞≤ C. Set S+:=g∈x∣θ∗⊤g>0⊂ℤdS^+:=\g _x θ^* g>0\ ^d. By the nondegeneracy assumption we can take an∈Y(n0)∖a(n0)a^n∈ Y^(n_0) \a^(n_0)\ (note that Y(n0)Y^(n_0) is the vertex set of Conv(X(s(n0)))Conv(X(s^(n_0))) since f is the identity map, and that Y(n0)⊆X(s(n0))Y^(n_0) X(s^(n_0))). By ˜3, a(n0)a^(n_0) is the unique maximizer of θ∗θ^* over X(s(n0))X(s^(n_0)); hence, applying ˜6.2 with X=X(s(n0))X=X(s^(n_0)), θ=θ∗θ=θ^*, and x1=anx^1=a^n, the resulting decomposition is a nonempty sum because an≠a(n0)a^n≠ a^(n_0), and so there exists g∈xg _x with θ∗⊤g>0θ^* g>0; that is, S+≠∅S^+≠ . Step 1 (reduction via minimax). Maximizing ˜6.2 (which holds for any θ†∈Θθ ∈ ) over θ†∈Δd−1θ ∈ ^d-1 and applying ˜6.1 (Δd−1 ^d-1 is compact convex, S+S^+ finite), since maxθ†∈Δd−1θ†⊤q=maxiqi _θ ∈ ^d-1θ q= _iq_i we obtain γ(ℓsub)≥1Nmaxθ†∈Δd−1ming∈S+θ†⊤g=1Nminq∈Conv(S+)maxi=1,…,dqi.γ( _sub)≥ 1N _θ ∈ ^d-1 _g∈ S^+θ g= 1N _q (S^+) _i=1,…,dq_i. From θ∗∈Δd−1θ^*∈ ^d-1 (θ∗≥0θ^*≥ 0) and θ∗⊤q>0θ^* q>0, we have maxiqi>0 _iq_i>0 for each q∈Conv(S+)q (S^+), that is, Conv(S+)∩(−ℝ≥0d)=∅Conv(S^+)∩(-R_≥ 0^d)= . Step 2 (an integral separating hyperplane with a nonnegative normal). Consider the upward closure Q′:=Conv(S+)+ℝ≥0dQ :=Conv(S^+)+R_≥ 0^d. Being the Minkowski sum of a bounded convex polytope and a convex cone, Q′Q is a polyhedron (an intersection of finitely many closed half-spaces), and since it contains the full d-dimensional set q0+ℝ≥0dq_0+R_≥ 0^d for any q0∈Conv(S+)q_0 (S^+), Q′Q is full d-dimensional. Moreover Q′Q is upward closed, that is, x∈Q′x∈ Q and x′≥x ≥ x (componentwise) imply x′∈Q′x ∈ Q . Hence each facet inequality defining Q′Q can be taken in the form a⋅x≥ca· x≥ c with a≥0a≥ 0: indeed, writing a facet inequality as a⋅x≥ca· x≥ c and supposing ai<0a_i<0 for some i, upward closedness gives x+tei∈Q′x+te_i∈ Q for all t≥0t≥ 0 and x∈Q′x∈ Q , so a⋅x+tai≥ca· x+ta_i≥ c would have to hold for all t≥0t≥ 0, while the left-hand side tends to −∞-∞ as t→∞t→∞, a contradiction (this mirrors the argument for the downward closure in Step 3 of the proof of Theorem˜6.6). As Conv(S+)∩(−ℝ≥0d)=∅Conv(S^+)∩(-R_≥ 0^d)= is equivalent to 0∉Q′0∉ Q , the point 0 violates some facet inequality: there exist an integral normal a∈ℤ≥0d∖0a _≥ 0^d \0\ and c∈ℤc with Conv(S+)⊆Q′⊆x∣a⋅x≥cConv(S^+) Q \x a· x≥ c\ and a⋅0<ca· 0<c (i.e., c≥1c≥ 1). This facet is spanned by vertices of S+S^+ (lattice points with ∥⋅∥∞≤C\|·\|_∞≤ C) and recession directions eie_i (where ai=0a_i=0); a can be constructed from the cofactors of affinely independent lattice points y1,…,ydy^1,…,y^d (choosing the sign so that a≥0a≥ 0), and the difference vectors vk=yk+1−y1v_k=y^k+1-y^1 satisfy |(vk)j|≤2C|(v_k)_j|≤ 2C. Step 3 (estimate). For every q∈Conv(S+)q (S^+), since a≥0a≥ 0 the weights λi:=ai/∑jaj _i:=a_i/ _ja_j form a convex combination, so maxiqi≥∑iλiqi=a⋅q∑jaj≥c∑jaj≥1∑jaj. _iq_i≥ _i _iq_i= a· q _ja_j≥ c _ja_j≥ 1 _ja_j. Applying the same Hadamard estimate as in the proof of Theorem˜6.6 (˜6.7) with m=(2C,…,2C)m=(2C,…,2C) gives ∑jaj≤max(d−1,2)(2Cd)d−1 _ja_j≤ (d-1, 2)(2C d)^d-1. Therefore, γ(ℓsub)≥1N⋅1∑jaj≥1Nmax(d−1,2)(2Cd)d−1.γ( _sub)≥ 1N· 1 _ja_j≥ 1N\, (d-1, 2)(2C d)^d-1. ∎ Remark 6.25. If A is totally unimodular (i.e., every square submatrix of A has determinant in 0,±1\0,± 1\), then C=1C=1 (cf. Onn, 2010, Lemmas 3.18, 3.19). For Θ=Δd−1 = ^d-1, by Theorem˜6.24, the lower bound on γ(ℓsub)γ( _sub) is Ω(1/(Nd(d+1)/2 2d−1)) (1/(N\,d^(d+1)/2\,2^d-1) ). Remark 6.26. An M♮-convex set (˜6.4) is the set of integer points of a generalized integral base polyhedron, which is described by lower and upper bound constraints over a family of subsets (submodular and supermodular inequalities). We caution that the corresponding coefficient matrix (whose rows are indicator vectors of subsets) is in general not totally unimodular: for instance, the rows (1,1,0)(1,1,0), (0,1,1)(0,1,1), (1,0,1)(1,0,1) form a square submatrix of determinant ±2± 2 (total unimodularity holds only for special families of subsets such as laminar families). Hence the lower bound for the M♮-convex case cannot, in general, be derived as a corollary of ˜6.5.2 (C=1C=1). On the other hand, Theorems˜6.18 and 6.19, which exploit the explicit test set ei−ej,±ei\e_i-e_j,± e_i\, hold regardless of the structure of the coefficient matrix of the describing inequality system, and give much sharper lower bounds, namely Ω(1/(Nd3/2)) (1/(Nd^3/2)) and Ω(1/(Nd2)) (1/(Nd^2)). Proposition 6.27 (An explicit upper bound on g∞(A~)g_∞( A), cf. Onn, 2010, Section 3.4). For the constraint matrix A∈ℤp×dA ^p× d of ˜6.5 with A≠0A≠ 0, let A~=[A∣Ip] A=[A I_p]. Let Δ(A) (A) be the largest absolute value of the square subdeterminants of A. Then C=g∞(A~)≤dΔ(A).C=g_∞( A)\ ≤\ d\, (A). proof. The matrix A~=[A∣Ip] A=[A I_p] has n=d+pn=d+p columns and p rows, and contains the submatrix IpI_p, so its rank is r=pr=p. Applying Onn (2010, Lemma 3.20) to A~ A, every g∈(A~)g ( A) satisfies ‖g‖∞≤(n−r)Δ(A~)=dΔ(A~)\|g\|_∞≤(n-r) ( A)=d\, ( A). Adjoining unit columns gives Δ(A~)=max(Δ(A),1) ( A)= ( (A),1), and since A≠0A≠ 0 we have Δ(A)≥1 (A)≥ 1, so Δ(A~)=Δ(A) ( A)= (A). ∎ 6.6. A separating hyperplane theorem Definition 6.28. For a vector ∈ℝdb ^d (≠b 0) and a scalar c∈ℝc , H=∈ℝd∣T≤cH=\x ^d ^Tx≤ c\ is called a closed half-space. Its boundary hyperplane is ∂H=∈ℝd∣T=c∂ H=\x ^d ^Tx=c\. Definition 6.29. The affine hull aff(S)aff(S) of a set S⊆ℝdS ^d is the smallest affine subspace containing S (equivalently, the intersection of all affine subspaces containing S); for a finite list of points y1,…,yk∈ℝdy^1,…,y^k ^d we write aff(y1,…,yk):=aff(y1,…,yk)aff(y^1,…,y^k):=aff(\y^1,…,y^k\). Consider a polyhedron A in ℝdR^d (a convex set expressed as the intersection of finitely many closed half-spaces) together with an inequality ⊤≤cb x≤ c that holds on A (that is, A⊆∣⊤≤cA \x x≤ c\ with ≠b 0). Then the set F:=A∩∣⊤=cF:=A∩\x x=c\ is called a face of A. The dimension of the affine hull aff(F)aff(F) of a face F is called the dimension of that face, and a face whose dimension equals dimA−1 A-1 is called a facet of A. Moreover, when a face F is a facet of A, the inequality ⊤≤cb x≤ c that gives it (that is, an inequality holding on A such that F=A∩∣⊤=cF=A∩\x x=c\) is called a facet-defining inequality of F. Proposition 6.30. In Euclidean space ℝdR^d, let A be a bounded convex polytope all of whose vertices are lattice points (points of ℤdZ^d) and that satisfies dimA=d A=d (full-dimensional), and let P∈ℤdP ^d be a lattice point not belonging to A (P∉AP∉ A). Then there exist a closed half-space H=∈ℝd∣⊤≤cH=\x ^d x≤ c\ and affinely independent vertices y1,…,ydy^1,…,y^d of A (which, being vertices of A, are lattice points) such that: A⊂HA⊂ H; P∉HP∉ H (i.e., ⊤P>cb P>c); and ∂H=aff(y1,…,yd)∂ H=aff(y^1,…,y^d). proof. Since A is a d-dimensional bounded convex polytope, it admits an irredundant facet representation A=⋂i=1M∈ℝd∣i⊤≤ciA= _i=1^M\x ^d _i x≤ c_i\, where each i⊤=ci\n_i x=c_i\ is a hyperplane defining a facet of A. Since P∉AP∉ A, there is an index i0i_0 with i0⊤P>ci0n_i_0 P>c_i_0. The corresponding facet G:=A∩∣i0⊤=ci0G:=A∩\x _i_0 x=c_i_0\ is a (d−1)(d-1)-dimensional face, so it has d affinely independent vertices y1,…,yd∈Gy^1,…,y^d∈ G. Being vertices of A, these are lattice points, and aff(y1,…,yd)=aff(G)=i0⊤=ci0aff(y^1,…,y^d)=aff(G)=\n_i_0 x=c_i_0\ holds. Setting :=i0b:=n_i_0, c:=ci0c:=c_i_0, and H:=∣⊤≤cH:=\x x≤ c\, we obtain A⊂HA⊂ H, ⊤P=i0⊤P>ci0=cb P=n_i_0 P>c_i_0=c, and ∂H=aff(y1,…,yd)∂ H=aff(y^1,…,y^d). ∎ 6.7. Proof of Theorem 6.4 The proof consists of three steps. Proof of Theorem˜6.4. Step 1: Reduction to the space of sums. The map φ:(ℝd)N→ℝd (R^d)^N ^d, (b1,…,bN)↦∑n=1Nbn(b^1,…,b^N) _n=1^Nb^n is linear, so it maps convex sets to convex sets, and φ(Conv(∏n=1NY(n)∖(a(n))n))=Conv(φ(∏n=1NY(n)∖(a(n))n))=Conv(W). \! (Conv\! ( _n=1^NY^(n) \(a^(n))_n\ ) )=Conv\! ( \! ( _n=1^NY^(n) \(a^(n))_n\ ) )=Conv(W). Hence (6.1) can be rewritten as γ(ℓsub)=1Nminq∈Conv(W)‖P−q‖γ( _sub)= 1N _q (W)\|P-q\| (6.3) Next we show P∉Conv(W)P (W). By ˜3, for each n, a(n)=a∗(θ∗,s(n))a^(n)=a^*(θ^*,s^(n)) is the unique optimal solution under θ∗θ^*; that is, for any bn∈Y(n)b^n∈ Y^(n), θ∗⊤bn≤θ∗⊤a(n),θ^* b^n≤θ^* a^(n), with equality if and only if bn=a(n)b^n=a^(n). If (bn)n∈∏n=1NY(n)∖(a(n))n(b^n)_n∈ _n=1^NY^(n) \(a^(n))_n\, then there is some n0n_0 with bn0≠a(n0)b^n_0≠ a^(n_0), so θ∗⊤∑n=1Nbn=∑n=1Nθ∗⊤bn<∑n=1Nθ∗⊤a(n)=θ∗⊤P.θ^* _n=1^Nb^n= _n=1^Nθ^* b^n< _n=1^Nθ^* a^(n)=θ^* P. This strict inequality holds for all elements of ∏n=1NY(n)∖(a(n))n _n=1^NY^(n) \(a^(n))_n\, and is preserved under convex combinations. Thus θ∗⊤q<θ∗⊤Pθ^* q<θ^* P for all q∈Conv(W)q (W), and in particular P∉Conv(W)P (W). Step 2: Reduction to a separating hyperplane through lattice points. By ˜6.1, f(×)⊂ℤdf(X×S) ^d. For each s∈s , by translating the range of f, we may assume that for all x∈X(s)x∈ X(s), f(x,s)∈∏i=1d0,1,…,mi.f(x,s)∈ _i=1^d\0,1,…,m_i\. Then P=∑n=1Na(n)∈∏i=1d0,1,…,Nmi,W⊂Λ′:=∏i=1d0,1,…,Nmi.P= _n=1^Na^(n)∈ _i=1^d\0,1,…,Nm_i\, W⊂ := _i=1^d\0,1,…,Nm_i\. (6.4) By Step 1, P∉Conv(W)P (W), and since Conv(W)Conv(W) is compact and convex, the distance between P and Conv(W)Conv(W) is positive. As Conv(W)Conv(W) is the convex hull of the finite set W, it is a convex polytope, and P∩Conv(W)=∅\P\ (W)= . The vertices of Conv(W)Conv(W) are all lattice points of W⊂Λ′W⊂ . By the assumption of the theorem, Conv(W)Conv(W) is full-dimensional (dimConv(W)=d (W)=d), and by Step 1 we have P∉Conv(W)P (W). Hence we may apply ˜6.6 to the d-dimensional polytope A=Conv(W)A=Conv(W) and the lattice point P. This yields a closed half-space H−=x∈ℝd∣a⋅x≤cH^-=\x ^d a· x≤ c\ and d affinely independent points y1,…,yd∈W⊂Λ′y^1,…,y^d∈ W⊂ that are vertices of Conv(W)Conv(W) (hence lattice points of Λ′ ) such that: Conv(W)⊂H−Conv(W)⊂ H^-, P∉H−P∉ H^- (i.e., a⋅P>ca· P>c), and ∂H−=aff(y1,…,yd)∂ H^-=aff(y^1,…,y^d). Since the boundary hyperplane ∂H−=x∈ℝd∣a⋅x=c∂ H^-=\x ^d a· x=c\ is the affine hull of the lattice points y1,…,yd∈ℤdy^1,…,y^d ^d, the normal a can be given as the cofactors of the difference vectors vk:=yk+1−y1∈ℤdv_k:=y^k+1-y^1 ^d (k=1,…,d−1k=1,…,d-1): ai=(−1)idet(V(i))∈ℤa_i=(-1)^i (V^(i)) (i=1,…,d),(i=1,…,d), where V(i)V^(i) is the matrix obtained by deleting the i-th column of the (d−1)×d(d-1)× d matrix V whose rows are the difference vectors. Also c=a⋅y1∈ℤc=a· y^1 . Since P∈ℤdP ^d, we have a⋅P−c∈ℤa· P-c , which combined with a⋅P>ca· P>c gives a⋅P−c≥1.a· P-c≥ 1. (6.5) For any q∈Conv(W)⊂H−q (W)⊂ H^- we have a⋅q≤ca· q≤ c, so by the Cauchy–Schwarz inequality, ‖P−q‖≥a⋅(P−q)‖a‖=a⋅P−a⋅q‖a‖≥a⋅P−c‖a‖≥1‖a‖.\|P-q\|≥ a·(P-q)\|a\|= a· P-a· q\|a\|≥ a· P-c\|a\|≥ 1\|a\|. Taking the minimum over q∈Conv(W)q (W), minq∈Conv(W)‖P−q‖≥1‖a‖. _q (W)\|P-q\|≥ 1\|a\|. (6.6) Step 3: Bounding the norm of the normal vector. Proposition 6.31. Let α>0α>0 and set Fα(z):=∑i=1d(1−zi)α, for z∈Δd−1.F_α(z):= _i=1^d(1-z_i)^α, for z∈ ^d-1. Then: (1) if α≥1α≥ 1, then FαF_α is convex on Δd−1 ^d-1 and its maximum is attained at a vertex; in particular Fα(z)≤d−1F_α(z)≤ d-1; (2) if 0<α<10<α<1, then FαF_α is strictly concave on Δd−1 ^d-1 and its maximum is attained at the barycenter z=(1/d,…,1/d)z=(1/d,…,1/d); in particular Fα(z)≤d(1−1/d)αF_α(z)≤ d(1-1/d)^α. proof. The second derivative of each term g(t)=(1−t)αg(t)=(1-t)^α is g′(t)=α(α−1)(1−t)α−2g (t)=α(α-1)(1-t)^α-2. Let t∈[0,1)t∈[0,1). • if α≥1α≥ 1, then g′≥0g ≥ 0, so g is convex. Hence FαF_α is convex on Δd−1 ^d-1 and its maximum is attained at a vertex i=(δij)je_i=( _ij)_j, where δij _ij is the Kronecker delta. Then Fα(i)=(1−1)α+(d−1)(1−0)α=d−1F_α(e_i)=(1-1)^α+(d-1)(1-0)^α=d-1, which proves the claim; • if 0<α<10<α<1, then g′<0g <0, so g is strictly concave. Hence FαF_α is strictly concave on Δd−1 ^d-1, and by Jensen’s inequality the maximizer is the barycenter z=(1/d,…,1/d)z=(1/d,…,1/d), with Fα(1/d,…,1/d)=d(1−1/d)αF_α(1/d,…,1/d)=d(1-1/d)^α. ∎ Proposition 6.32. Let d≥2d≥ 2 and m=(m1,…,md)∈ℝdm=(m_1,…,m_d) ^d. Then ∑i=1d(∑j≠imj2)d−1≤(d−1)‖m‖22(d−1). _i=1^d ( _j≠ im_j^2 )^d-1≤(d-1)\|m\|_2^2(d-1). proof. If m=0m=0 the claim holds, so we may assume m≠0m≠ 0. The left-hand side equals ∑i=1d(∑j≠imj2)d−1=∑i=1d(‖m‖22−mi2)d−1=‖m‖22(d−1)∑i=1d(1−mi2‖m‖22)d−1. _i=1^d ( _j≠ im_j^2 )^d-1= _i=1^d (\|m\|_2^2-m_i^2 )^d-1=\|m\|_2^2(d-1) _i=1^d (1- m_i^2\|m\|_2^2 )^d-1. Setting zi=mi2‖m‖22z_i= m_i^2\|m\|_2^2 and z=(z1,…,zd)z=(z_1,…,z_d), we have z∈Δd−1z∈ ^d-1. By ˜6.7, ‖m‖22(d−1)∑i=1d(1−mi2‖m‖22)d−1≤(d−1)‖m‖22(d−1),\|m\|_2^2(d-1) _i=1^d (1- m_i^2\|m\|_2^2 )^d-1≤(d-1)\|m\|_2^2(d-1), which proves the claim. ∎ Proposition 6.33. Let d≥2d≥ 2, and let y1,…,yd∈ℝdy^1,…,y^d ^d be affinely independent points whose difference vectors vk:=yk+1−y1v_k:=y^k+1-y^1 (k=1,…,d−1k=1,…,d-1) satisfy |(vk)j|≤mj|(v_k)_j|≤ m_j for all j. Let V be the (d−1)×d(d-1)× d matrix whose rows are v1,…,vd−1v_1,…,v_d-1, let V(i)V^(i) be the matrix obtained by deleting the i-th column of V, and set ai:=(−1)idet(V(i))a_i:=(-1)^i (V^(i)) (i=1,…,di=1,…,d). Then ‖a‖2≤∑i=1d(∑j≠imj2)d−1≤(d−1)‖m‖22(d−1).\|a\|^2≤ _i=1^d ( _j≠ im_j^2 )^d-1≤(d-1)\|m\|_2^2(d-1). proof. By Hadamard’s inequality, |ai|=|det(V(i))|≤∏k=1d−1‖vk(i)‖.|a_i|=| (V^(i))|≤ _k=1^d-1\|v_k^(i)\|. For the norm of each vk(i)v_k^(i), since |(vk)j|≤mj|(v_k)_j|≤ m_j, ‖vk(i)‖2=∑j≠i(vk)j2≤∑j≠imj2.\|v_k^(i)\|^2= _j≠ i(v_k)_j^2≤ _j≠ im_j^2. This bound is independent of k, so |ai|≤∏k=1d−1∑j≠imj2=(∑j≠imj2)(d−1)/2.|a_i|≤ _k=1^d-1 _j≠ im_j^2= ( _j≠ im_j^2 )^(d-1)/2. By ˜6.7, ‖a‖2=∑i=1dai2≤∑i=1d(∑j≠imj2)d−1≤(d−1)‖m‖22(d−1).\|a\|^2= _i=1^da_i^2≤ _i=1^d ( _j≠ im_j^2 )^d-1≤(d-1)\|m\|_2^2(d-1). ∎ With the above preparations, we complete Step 3 of the proof of Theorem˜6.4. The hyperplane ∂H−∂ H^- passes through d affinely independent lattice points y1,…,ydy^1,…,y^d in Λ′=∏i=1d0,1,…,Nmi = _i=1^d\0,1,…,Nm_i\, and the difference vectors vk=yk+1−y1v_k=y^k+1-y^1 satisfy |(vk)j|≤Nmj|(v_k)_j|≤ Nm_j. By ˜6.7 (applied with m replaced by NmNm), ‖a‖2≤(d−1)‖Nm‖22(d−1)=(d−1)N2(d−1)‖m‖22(d−1), i.e., ‖a‖≤d−1Nd−1‖m‖2d−1.\|a\|^2≤(d-1)\,\|Nm\|_2^2(d-1)=(d-1)\,N^2(d-1)\,\|m\|_2^2(d-1), i.e., \|a\|≤ d-1\,N^d-1\,\|m\|_2^d-1. (6.7) Combining (6.3), (6.6), and (6.7), γ(ℓsub) γ( _sub) =1Nminq∈Conv(W)‖P−q‖≥1N⋅1‖a‖≥1N⋅1d−1Nd−1‖m‖2d−1=1Ndd−1‖m‖2d−1. = 1N _q (W)\|P-q\|≥ 1N· 1\|a\|≥ 1N· 1 d-1\,N^d-1\,\|m\|_2^d-1= 1N^d\, d-1\,\|m\|_2^d-1. ∎ 6.8. Proof of Theorem 6.6 The proof consists of three steps. Steps 1 and 2 are common to the proof of Theorem˜6.4, while Step 3 is specific to the probability-simplex case. Proof of Theorem˜6.6. Step 1: Reduction to the space of sums. By the linearity of φ:(ℝd)N→ℝd (R^d)^N ^d, (b1,…,bN)↦∑n=1Nbn(b^1,…,b^N) _n=1^Nb^n, (6.2) can be rewritten as γ(ℓsub)=1Nminq∈Conv(W)maxi=1,…,d(Pi−qi).γ( _sub)= 1N _q (W) _i=1,…,d(P_i-q_i). (6.8) By the same argument as in Step 1 of the proof of Theorem˜6.4 (uniqueness via ˜3), P∉Conv(W)P (W). Moreover, by ˜4.1 (γ(ℓsub)>0γ( _sub)>0) and Equation˜6.8, for any q∈Conv(W)q (W), maxi=1,…,d(Pi−qi)>0. _i=1,…,d(P_i-q_i)>0. (6.9) Rewriting (6.9) in set-theoretic terms, Conv(W)∩(P+ℝ≥0d)=∅,Conv(W)∩(P+R_≥ 0^d)= , (6.10) where P+ℝ≥0d=x∈ℝd∣xi≥Pi,∀iP+R_≥ 0^d=\x ^d x_i≥ P_i,\ ∀\,i\ is the translate of the nonnegative orthant with vertex P. Step 2: Reduction to the lattice structure.As in Step 2 of the proof of Theorem˜6.4, by ˜6.1 and a translation, P∈∏i=1d0,1,…,Nmi,W⊂Λ′:=∏i=1d0,1,…,Nmi.P∈ _i=1^d\0,1,…,Nm_i\, W⊂ := _i=1^d\0,1,…,Nm_i\. (6.11) Step 3: Reduction to a lattice hyperplane with nonnegative normal. We first verify that we may assume mi≥1m_i≥ 1 for each i. By ˜6.1, each mim_i is a nonnegative integer. For a coordinate i with mi=0m_i=0, the feature fif_i is constant on X(s)X(s) for every s, so bin=ai(n)b^n_i=a^(n)_i for every n and every bn∈Y(n)b^n∈ Y^(n); that is, Pi−qi=0P_i-q_i=0 for every q∈Conv(W)q (W), and the coordinate i does not contribute to maxi(Pi−qi) _i(P_i-q_i) in Equation˜6.8 (by Equation˜6.9, the positive maximum is attained at a coordinate with mi≥1m_i≥ 1). Hence, applying the argument below to the d′d -dimensional problem obtained by removing all coordinates with mi=0m_i=0 (1≤d′≤d1≤ d ≤ d; the case d′=0d =0 is excluded, since then every Y(n)Y^(n) would be a singleton and the index set of the min in Equation˜6.2 would be empty), and writing m′m for the vector of the nonzero components of m, we obtain γ(ℓsub)≥1Nd′max(d′−1,2)‖m′‖2d′−1≥1Ndmax(d−1,2)‖m‖2d−1γ( _sub)\ ≥\ 1N^d (d -1, 2)\,\|m \|_2^d -1\ ≥\ 1N^d (d-1, 2)\,\|m\|_2^d-1 (the last inequality uses N≥1N≥ 1, d′≤d ≤ d, and ‖m′‖2=‖m‖2≥1\|m \|_2=\|m\|_2≥ 1). In what follows we assume mi≥1m_i≥ 1 for each i. The estimate below (˜6.7 and 6.7) requires the reduced dimension to satisfy d′≥2d ≥ 2; if d′=1d =1, then Δ0 ^0 is a single point and, since W⊂ℤW and P∈ℤP with P−q>0P-q>0 for all q∈Conv(W)q (W) by Equation˜6.9, integrality gives minq∈Conv(W)(P−q)≥1 _q (W)(P-q)≥ 1, whence γ(ℓsub)≥1/N≥1/(N2)γ( _sub)≥ 1/N≥ 1/(N 2) and the bound already holds. We may therefore assume d′≥2d ≥ 2. Consider the downward closure Q:=Conv(W)−ℝ≥0d=q−v∣q∈Conv(W),v∈ℝ≥0d.Q:=Conv(W)-R_≥ 0^d=\q-v q (W),\ v _≥ 0^d\. Since Conv(W)Conv(W) is a bounded convex polytope and ℝ≥0dR_≥ 0^d is a convex cone, Q is a polyhedron (an intersection of finitely many closed half-spaces); and since for any q0∈Conv(W)q_0 (W) it contains Q⊇q0−ℝ≥0dQ q_0-R_≥ 0^d (which is full d-dimensional), Q is also full d-dimensional. Moreover Q is downward closed, that is, x∈Qx∈ Q and x′≤x ≤ x (componentwise) imply x′∈Qx ∈ Q. Hence the normal a of each facet inequality a⋅x≤ca· x≤ c defining Q can be taken to satisfy a≥0a≥ 0 (if ai<0a_i<0, then for x∈Qx∈ Q downward closedness gives x−tei∈Qx-te_i∈ Q for all t≥0t≥ 0, so a⋅x−tai≤ca· x-ta_i≤ c holds for all t≥0t≥ 0, a contradiction as t→∞t→∞). (6.10) (Conv(W)∩(P+ℝ≥0d)=∅Conv(W)∩(P+R_≥ 0^d)= ) is equivalent to P∉QP∉ Q, and since the full d-dimensional Q equals the intersection of the finitely many closed half-spaces defining its facets (˜6.6), P violates some facet inequality. That is, there exist a∘∈ℝ≥0d∖0a _≥ 0^d \0\ and c∘∈ℝc such that Conv(W)⊆Q⊆x∣a∘⋅x≤c∘,a∘⋅P>c∘.Conv(W) Q \x a · x≤ c \, a · P>c . The facet F:=Q∩x∣a∘⋅x=c∘F:=Q∩\x a · x=c \ is (d−1)(d-1)-dimensional (the vertices of Q coincide with vertices of Conv(W)Conv(W), hence are lattice points of Λ′ ), and its edge directions are either (i) difference vectors between vertices of Conv(W)Conv(W), or (i) coordinate directions −ei-e_i (for i with ai∘=0a _i=0; by downward closedness F may extend as a ray in this direction). Since aff(F)=x∣a∘⋅x=c∘aff(F)=\x a · x=c \ is (d−1)(d-1)-dimensional, a vertex y1∈Wy^1∈ W of F together with d−1d-1 affinely independent vectors taken from these edge directions yields affinely independent lattice points y1,…,yd∈ℤdy^1,…,y^d ^d with aff(y1,…,yd)=x∣a∘⋅x=c∘aff(y^1,…,y^d)=\x a · x=c \. The difference vectors vk:=yk+1−y1v_k:=y^k+1-y^1 satisfy, in case (i), |(vk)j|≤Nmj|(v_k)_j|≤ Nm_j (both endpoints are lattice points of Λ′ ), and in case (i), vk=−eiv_k=-e_i, hence |(vk)j|=δij≤1≤Nmj|(v_k)_j|= _ij≤ 1≤ Nm_j. Moreover, since a∘≥0a ≥ 0 and a∘⋅P>c∘a · P>c , for any x∈a∘⋅x=c∘x∈\a · x=c \ we have ∑iai∘(Pi−xi)=a∘⋅P−c∘>0 _ia _i(P_i-x_i)=a · P-c >0, so there is some j with aj∘>0a _j>0 and Pj−xj>0P_j-x_j>0, whence maxi(Pi−xi)>0 _i(P_i-x_i)>0. Therefore, we obtain a hyperplane H:=aff(y1,…,yd)H:=aff(y^1,…,y^d) (=x∣a∘⋅x=c∘=\x a · x=c \) containing d affinely independent lattice points y1,…,ydy^1,…,y^d with difference vectors in Λ′=∏i=1d0,1,…,Nmi = _i=1^d\0,1,…,Nm_i\ such that: • Conv(W)Conv(W) is contained in the closed half-space H−=x∣a⋅x≤cH^-=\x a· x≤ c\ defined by H (with a⋅P>ca· P>c); • ∀x∈H,maxi=1,…,d(Pi−xi)>0∀\,x∈ H,\ _i=1,…,d(P_i-x_i)>0. Construct the normal vector a as the cofactors of the (d−1)×d(d-1)× d integer matrix V whose rows are the difference vectors vk:=yk+1−y1∈ℤdv_k:=y^k+1-y^1 ^d (k=1,…,d−1k=1,…,d-1): ai=(−1)idet(V(i))∈ℤ(i=1,…,d).a_i=(-1)^i (V^(i)) (i=1,…,d). Then c=a⋅y1∈ℤc=a· y^1 . This a is an integer normal of the hyperplane aff(y1,…,yd)=x∣a∘⋅x=c∘aff(y^1,…,y^d)=\x a · x=c \, and is parallel to a∘a . Since H∩(P+ℝ≥0d)=∅H∩(P+R_≥ 0^d)= , choosing the sign of a appropriately yields ai≥0(∀i),a⋅P−c≥1.a_i≥ 0 (∀\,i), a· P-c≥ 1. (6.12) For any q∈Conv(W)⊂H−q (W)⊂ H^-, setting λi:=ai∑j=1daj≥0 _i:= a_i _j=1^da_j≥ 0 (so ∑i=1dλi=1 _i=1^d _i=1), maxi=1,…,d(Pi−qi)≥∑i=1dλi(Pi−qi)=a⋅(P−q)∑j=1daj≥a⋅P−c∑j=1daj≥1∑j=1daj. _i=1,…,d(P_i-q_i)≥ _i=1^d _i(P_i-q_i)= a·(P-q) _j=1^da_j≥ a· P-c _j=1^da_j≥ 1 _j=1^da_j. (6.13) We bound ∑j=1daj _j=1^da_j. The difference vectors satisfy |(vk)j|≤Nmj|(v_k)_j|≤ Nm_j, so by Hadamard’s inequality, ai≤|ai|≤(∑j≠i(Nmj)2)(d−1)/2.a_i≤|a_i|≤ ( _j≠ i(Nm_j)^2 )^(d-1)/2. Since ai≥0a_i≥ 0, ∑i=1dai≤∑i=1d(∑j≠i(Nmj)2)(d−1)/2=Nd−1‖m‖2d−1∑i=1d(1−mi2‖m‖22)(d−1)/2. _i=1^da_i≤ _i=1^d ( _j≠ i(Nm_j)^2 )^(d-1)/2=N^d-1\|m\|_2^d-1 _i=1^d (1- m_i^2\|m\|_2^2 )^(d-1)/2. By ˜6.7, ∑i=1dai≤max(d−1,2)Nd−1‖m‖2d−1. _i=1^da_i≤ (d-1, 2)\,N^d-1\,\|m\|_2^d-1. (6.14) Combining (6.8), (6.13), and (6.14), γ(ℓsub) γ( _sub) =1Nminq∈Conv(W)maxi=1,…,d(Pi−qi)≥1N⋅1∑j=1daj = 1N _q (W) _i=1,…,d(P_i-q_i)≥ 1N· 1 _j=1^da_j ≥1N⋅1max(d−1,2)Nd−1‖m‖2d−1=1Ndmax(d−1,2)‖m‖2d−1. ≥ 1N· 1 (d-1, 2)\,N^d-1\,\|m\|_2^d-1= 1N^d\, (d-1, 2)\,\|m\|_2^d-1. ∎ 6.9. Tightness of the general-ILP lower bounds The lower bounds of Theorems˜6.4 and 6.6 decay exponentially in the dimension d. The following explicit family shows that γ(ℓsub)γ( _sub) itself can be exponentially small in d, so that the iteration upper bound T=O(1/γ(ℓsub)2)T=O(1/γ( _sub)^2) can be exponentially large in d. Proposition 6.34. Fix an integer K≥2K≥ 2 and a dimension d≥2d≥ 2, and set a=(1,K,K2,…,Kd−1)∈ℤda=(1,K,K^2,…,K^d-1) ^d. Consider the single-sample DDIOP (N=1N=1) with identity features f(x,s)=xf(x,s)=x and feasible region X=p0,p1,…,pd−1,pd,a∗⊂ℤd, X=\p_0,p_1,…,p_d-1,p_d,\,a^*\ ^d, p0=0,pi=Kei−ei+1(i=1,…,d−1),pd=−ed,a∗=e1, p_0=0, p_i=Ke_i-e_i+1\ (i=1,…,d-1), p_d=-e_d, a^*=e_1, whose feature ranges satisfy mi≤K+1m_i≤ K+1 for every i, and let the true weight be θ∗=a/‖a‖θ^*=a/\|a\| (normalized in ∥⋅∥1\|·\|_1 for Θ=Δd−1 = ^d-1 and in ∥⋅∥2\|·\|_2 for Θ=Bd =B^d). Then a∗a^* is the unique maximizer of θ∗⊤xθ^* x over X, and, with ‖a‖1=Kd−1K−1\|a\|_1= K^d-1K-1 and ‖a‖2=K2d−1K2−1\|a\|_2= K^2d-1K^2-1, 1‖a‖1≤γ(ℓsub)≤1Kd−1(Θ=Δd−1),1‖a‖2≤γ(ℓsub)≤1Kd−1(Θ=Bd). 1\|a\|_1≤γ( _sub)≤ 1K^d-1 ( = ^d-1), 1\|a\|_2≤γ( _sub)≤ 1K^d-1 ( =B^d). In particular γ(ℓsub)=Θ(K−(d−1))γ( _sub)= (K^-(d-1)) in both cases. proof. Since a⋅p0=0a· p_0=0, a⋅pi=K⋅Ki−1−Ki=0a· p_i=K· K^i-1-K^i=0 (i=1,…,d−1i=1,…,d-1), a⋅pd=−Kd−1a· p_d=-K^d-1, and a⋅a∗=1a· a^*=1, we have θ∗⊤a∗=1/‖a‖>0≥θ∗⊤pθ^* a^*=1/\|a\|>0≥θ^* p for every p∈p0,…,pd−1,pdp∈\p_0,…,p_d-1,p_d\, so a∗a^* is the unique maximizer; thus a(1)=a∗a^(1)=a^* and ˜3 holds. Put W=X∖a∗=p0,…,pd−1,pdW=X \a^*\=\p_0,…,p_d-1,p_d\. Since p0,…,pd−1p_0,…,p_d-1 span the hyperplane a⋅x=0\a· x=0\ and pd=−ed∉a⋅x=0p_d=-e_d∉\a· x=0\, Conv(W)Conv(W) is full-dimensional, so Theorem˜6.4 applies to this family. By ˜6.1, γ(ℓsub)=minq∈Conv(W)maxθ∈Θθ⊤(a∗−q)γ( _sub)= _q (W) _θ∈ θ (a^*-q). Every q∈Conv(W)q (W) satisfies a⋅q≤0a· q≤ 0, whereas a⋅a∗=1a· a^*=1. Lower bounds. If Θ=Δd−1 = ^d-1, then maxθθ⊤(a∗−q)=maxi(ai∗−qi) _θ (a^*-q)= _i(a^*_i-q_i), and from ∑iai(ai∗−qi)=a⋅(a∗−q)=1−a⋅q≥1 _ia_i(a^*_i-q_i)=a·(a^*-q)=1-a· q≥ 1 with ai>0a_i>0 we get maxi(ai∗−qi)≥1/∑iai=1/‖a‖1 _i(a^*_i-q_i)≥ 1/ _ia_i=1/\|a\|_1. If Θ=Bd =B^d, then maxθθ⊤(a∗−q)=‖a∗−q‖2≥|a⋅(a∗−q)|/‖a‖2≥1/‖a‖2 _θ (a^*-q)=\|a^*-q\|_2≥|a·(a^*-q)|/\|a\|_2≥ 1/\|a\|_2. Upper bound. Take q∘=λ0p0+∑i=1d−1K−ipiq = _0p_0+ _i=1^d-1K^-ip_i with λ0=1−∑i=1d−1K−i≥0 _0=1- _i=1^d-1K^-i≥ 0. A direct computation gives q∘=e1−K−(d−1)ed∈Conv(W)q =e_1-K^-(d-1)e_d (W), so a∗−q∘=K−(d−1)eda^*-q =K^-(d-1)e_d, whence maxi(ai∗−qi∘)=K−(d−1) _i(a^*_i-q _i)=K^-(d-1) and ‖a∗−q∘‖2=K−(d−1)\|a^*-q \|_2=K^-(d-1); thus γ(ℓsub)≤K−(d−1)γ( _sub)≤ K^-(d-1) in both cases. Finally ‖a‖1=Kd−1K−1≤2Kd−1\|a\|_1= K^d-1K-1≤ 2K^d-1 and ‖a‖2=K2d−1K2−1≤K2−1Kd−1≤23Kd−1\|a\|_2= K^2d-1K^2-1≤ K K^2-1\,K^d-1≤ 2 3\,K^d-1 (both using K≥2K≥ 2), so γ(ℓsub)=Θ(K−(d−1))γ( _sub)= (K^-(d-1)) with constants independent of d. ∎ 7. Iteration upper bounds for integer linear programs The iteration upper bound of PSGD (SRSS) (˜4.2) and that of PSGD (SRSL) (˜4.2) are both of the form O(γ(ℓsub)−2)×poly(diam(Θ),β,L(ℓsub))O\! (γ( _sub)^-2 )×poly(diam( ),β,L( _sub)). Hence, substituting each lower bound on γ(ℓsub)γ( _sub) from Table˜1 (obtained in ˜6), the SRSS and SRSL iteration upper bounds for solving Equation˜3.2 exactly are obtained as explicit functions of the problem size (both share the same O order). We summarize the results in Table˜4 (for the probability simplex Θ=Δd−1 = ^d-1; we abbreviate poly=poly(diam(Θ),β,L(ℓsub))poly=poly(diam( ),β,L( _sub))). The totally unimodular case (O(N2d+14d−1poly)O(N^2\,d^d+14^d-1\,poly)) illustrated in ˜4.4 corresponds to the last row of this table. Table 4. Iteration upper bounds of PSGD (SRSS) and PSGD (SRSL), obtained by substituting each lower bound on γ(ℓsub)γ( _sub) from Table˜1 into ˜4.2 and 4.2 (Θ=Δd−1 = ^d-1, poly=poly(diam(Θ),β,L(ℓsub))poly=poly(diam( ),β,L( _sub)); both share the same O order). Setting Iteration upper bound (SRSS, SRSL) ILP O(N2dd2∥m∥22(d−1)poly)O\! (N^2d\,d^2\, m _2^2(d-1)\,poly ) M-convex O(N2d4poly)O\! (N^2d^4\,poly ) M♮-convex O(N2d4poly)O\! (N^2d^4\,poly ) Linear inequality (C=g∞(A~)C=g_∞( A)) O(N2d+1(2C)2(d−1)poly)O\! (N^2\,d^d+1(2C)^2(d-1)\,poly ) Totally unimodular (C=1C=1) O(N2d+14d−1poly)O\! (N^2\,d^d+14^d-1\,poly ) For M-convex and M♮-convex sets the iteration count is bounded by a polynomial in the dimension d, whereas for general ILPs and linear inequality constraints it can grow exponentially in d (˜4.4). The iteration upper bounds for attaining the PLF minimum (Theorems˜4.10 and 4.11) are also of the form O(γ(ℓsub)−2)×poly(diam(Θ),β,L(ℓsub))O\! (γ( _sub)^-2 )×poly(diam( ),β,L( _sub)). Hence, substituting each lower bound on γ(ℓsub)γ( _sub) from Table˜1 yields the iteration upper bound for attaining the PLF minimum as an explicit function of the problem size as well, whose O order coincides with that in Table˜4. 8. Conclusion In this paper, for data-driven inverse optimization whose forward problem is an integer linear program (ILP), we gave explicit lower bounds on the geometric constant γ(ℓsub)γ( _sub) of the suboptimality loss in terms of the structure of integer programming (total unimodularity, Graver bases, and M-convexity/M♮-convexity). Substituting them into the iteration upper bounds for gradient-based optimization methods (Kitaoka, 2024), we evaluated the number of iterations sufficient to achieve exact consistency with the observed data as an explicit function of the sample size, the dimension, the feature ranges, and the structure of the constraint matrix, up to polynomial factors in basic constants. Similarly, we gave an explicit bound on the number of iterations required to attain the minimum of the prediction loss of features (PLF). The obtained lower bounds show that the number of iterations is bounded by a polynomial in the problem size when structure can be exploited, while for general ILPs they can become exponentially small in the dimension; the latter is consistent with the NP-hardness of inverse optimization with noisy data established by Aswani et al. (2018). In fact ˜6.9 exhibits an explicit family of ILP instances on which γ(ℓsub)γ( _sub) is exponentially small in d; hence no lower bound on γ(ℓsub)γ( _sub) polynomial in the problem size can hold for general ILPs, and the exponential dependence of the iteration bound on d is genuine. Sharpening the general ILP lower bound and improving its NdN^d dependence are left for future work. Acknowledgement We also thank GPT-5.2, GPT-5.4, Opus 4.7, and Opus 4.8, Fable 5 for their assistance with proofreading the manuscript. References R. K. Ahuja and J. B. Orlin (2001) Inverse optimization. Operations Research 49 (5), p. 771–783. External Links: Document Cited by: §1, §2. S. Arora, E. Hazan, and S. Kale (2012) The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing 8 (1), p. 121–164. External Links: Document Cited by: Table 5, Table 2. A. Aswani, Z. Shen, and A. Siddiq (2018) Inverse optimization with noisy data. Operations Research 66 (3), p. 870–892. External Links: Document Cited by: §1, §1, §2, Remark 4.12, §8. A. Babier, T. C. Chan, T. Lee, R. Mahmood, and D. Terekhov (2021) An ensemble learning framework for model fitting and evaluation in inverse linear optimization. INFORMS Journal on Optimization 3 (2), p. 119–138. External Links: Document Cited by: §1. A. Bärmann, A. Martin, S. Pokutta, and O. Schneider (2018) An online-learning approach to inverse optimization. Note: Available at arXiv:1810.12997 Cited by: Table 5, Table 5, Remark C.1, §1, §2, Proposition 3.4, Table 2, Table 2. A. Beck (2017) First-order methods in optimization. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania. External Links: Document Cited by: §1, Example 3.5. Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J. Vert, and F. Bach (2020) Learning with differentiable perturbed optimizers. Advances in Neural Information Processing Systems 33, p. 9508–9519. Cited by: §2. D. Bertsimas, V. Gupta, and I. C. Paschalidis (2015) Data-driven estimation in equilibrium using inverse optimization. Mathematical Programming 153, p. 595–633. External Links: Document Cited by: Remark C.1, §1. O. Besbes, Y. Fonseca, and I. Lobel (2021) Online learning from optimal actions. In The 34th Conference on Learning Theory, p. 586–586. Cited by: Table 5, §1, §2, Table 2. O. Besbes, Y. Fonseca, and I. Lobel (2025) Contextual inverse optimization: offline and online learning. Operations Research 73 (1), p. 424–443. External Links: Document Cited by: Table 5, §1, §2, Table 2. J. R. Birge, A. Hortaçsu, and J. M. Pavlin (2017) Inverse optimization for the recovery of market structure from market outcomes: an application to the miso electricity market. Operations Research 65 (4), p. 837–855. External Links: Document Cited by: §1. S. Boyd, L. Xiao, and A. Mutapcic (2003) Subgradient methods. Vol. 2004. External Links: Link Cited by: Example 3.5. J. V. Burke and M. C. Ferris (1993) Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization 31 (5), p. 1340–1359. External Links: Document Cited by: §2. T. C. Chan, M. Eberg, K. Forster, C. Holloway, L. Ieraci, Y. Shalaby, and N. Yousefi (2022) An inverse optimization approach to measuring clinical pathway concordance. Management Science 68 (3), p. 1882–1903. External Links: Document Cited by: §1. T. C. Chan, T. Lee, and D. Terekhov (2019) Inverse optimization: closed-form solutions, geometry, and goodness of fit. Management Science 65 (3), p. 1115–1135. External Links: Document Cited by: §1, §1, §2. T. C. Chan, R. Mahmood, and I. Y. Zhu (2023) Inverse optimization: theory and applications. Operations Research. External Links: Document Cited by: §1, §1, §2. V. X. Chen and F. Kılınç-Karzan (2020) Online convex optimization perspective for learning from dynamically revealed preferences. Note: Available at arXiv:2008.10460 Cited by: Remark C.1. A. N. Elmachtoub and P. Grigas (2022) Smart “predict, then optimize”. Management Science 68 (1), p. 9–26. External Links: Document Cited by: §2. A. M. Ferber, T. Huang, D. Zha, M. Schubert, B. Steiner, B. Dilkina, and Y. Tian (2023) Surco: learning linear surrogates for combinatorial nonlinear optimization problems. In The 40th International Conference on Machine Learning, p. 10034–10052. Cited by: §1, §2. A. Ferber, B. Wilder, B. Dilkina, and M. Tambe (2020) Mipaal: mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, p. 1504–1511. External Links: Document Cited by: §2. M. C. Ferris (1991) Finite termination of the proximal point algorithm. Mathematical Programming 50, p. 359–366. External Links: Document Cited by: §2. L. Flatto and D. J. Newman (1977) Random coverings. Acta Math. 138, p. 241–264. External Links: Document Cited by: Table 2. G. Garrigos and R. M. Gower (2023) Handbook of convergence theorems for (stochastic) gradient methods. Note: Available at arXiv:2301.11235 Cited by: §1. S. Gollapudi, G. Guruganesh, K. Kollias, P. Manurangsi, R. Leme, and J. Schneider (2021) Contextual recommendations and low-regret cutting-plane algorithms. Advances in Neural Information Processing Systems 34, p. 22498–22508. Cited by: Table 5, §1, §2, Table 2. E. Hazan, A. Agarwal, and S. Kale (2007) Logarithmic regret algorithms for online convex optimization. Machine Learning 69 (2), p. 169–192. External Links: Document Cited by: Table 5, Table 2. E. Hazan (2019) Introduction to online convex optimization. Note: Available at arXiv:1909.05207 Cited by: §1. C. Heuberger (2004) Inverse combinatorial optimization: a survey on problems, methods, and results. Journal of Combinatorial Optimization 8, p. 329–361. External Links: Document Cited by: §1, §2. A. Kitaoka and R. Eto (2023a) A proof of convergence of inverse reinforcement learning for multi-objective optimization. Note: Available at arXiv:2305.06137v3 Cited by: Remark C.1, §1, §2, Proposition 3.4, Example 3.6. A. Kitaoka and R. Eto (2023b) A proof of imitation of Wasserstein inverse reinforcement learning for multi-objective optimization. Note: Available at arXiv:2305.10089 Cited by: Remark C.1. A. Kitaoka (2024) Exact solution to data-driven inverse optimization of milps in finite time via gradient-based methods. Note: Companion paper, arXiv:2405.14273v8 External Links: 2405.14273 Cited by: Remark C.1, 4th item, §1, §1, §2, §2, §2, §2, §2, §2, §2, Lemma 3.3, Definition 4.3, Proposition 4.4, Corollary 4.6, Remark 4.7, §4.1, §4.1, §4.1, §4.1, Corollary 4.8, §4.2, Corollary 4.9, §4.2, §4.2, §4.3, Theorem 4.10, Theorem 4.11, Theorem 4.5, Table 2, Table 2, Table 3, Table 3, §8, Algorithm 1. Z. Liang and Y. Dvorkin (2023) Data-driven inverse optimization for marginal offer price recovery in electricity markets. In Proceedings of the 14th ACM International Conference on Future Energy Systems, p. 497–509. External Links: Document Cited by: §1. P. Mohajerin Esfahani, S. Shafieezadeh-Abadeh, G. A. Hanasusanto, and D. Kuhn (2018) Data-driven inverse optimization with imperfect information. Mathematical Programming 167, p. 191–234. External Links: Document Cited by: Remark C.1, §1, §2. K. Murota and A. Shioura (1999) M-convex function on generalized polymatroid. Mathematics of Operations Research 24 (1), p. 95–105. External Links: Document Cited by: Proposition 6.17. K. Murota (1996) Convexity and Steinitz’s exchange property. Advances in Mathematics 124 (2), p. 272–311. External Links: Document Cited by: §2, Proposition 6.12. K. Murota (1998) Discrete convex analysis. Mathematical Programming 83, p. 313–371. External Links: Document Cited by: §2, Proposition 6.12. K. Murota (2003) Discrete convex analysis. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania. External Links: Document Cited by: §2, Definition 6.10, Proposition 6.12, Definition 6.15, Proposition 6.17. A. Y. Ng, S. Russell, et al. (2000) Algorithms for inverse reinforcement learning. In 7th International Conference on Machine Learning, Vol. 1, p. 2. Cited by: §1. T. Oki and S. Sakaue (2026) Finite and corruption-robust regret bounds in online inverse linear optimization under M-convex action sets. Note: Available at arXiv:2602.01682v2 Cited by: §2. S. Onn (2010) Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society, Berlin. External Links: Document Cited by: §2, §2, Definition 6.21, §6.5, Proposition 6.27, §6.5.2, Remark 6.25. B. T. Polyak (1987) Introduction to optimization. Optimization Software, Inc., New York, New York. External Links: Document Cited by: §2. A. Reznikov and E. B. Saff (2015) The Covering Radius of Randomly Distributed Points on a Manifold. International Mathematics Research Notices 2016 (19), p. 6065–6094. External Links: ISSN 1073-7928, Document Cited by: Table 2. S. Sakaue, T. Tsuchiya, H. Bao, and T. Oki (2025) Online inverse linear optimization: improved regret bound, robustness to suboptimality, and toward tight regret analysis. Note: Available at arXiv:2501.14349v6, and to appear in The Thirty-Ninth Annual Conference on Neural Information Processing Systems Cited by: Table 5, Table 5, Table 5, §1, §2, Table 2, Table 2. B. Sturmfels (1996) Gröbner bases and convex polytopes. University Lecture Series, Vol. 8, American Mathematical Society, Providence, Rhode Island. External Links: Document Cited by: §2, §2, Definition 6.21, §6.5. C. Sun, S. Liu, and X. Li (2023) Maximum optimality margin: a unified approach for contextual linear programming and inverse linear programming. In The 40th International Conference on Machine Learning, Vol. 202, p. 32886–32912. Cited by: Remark C.1. Y. Suzuki, W. M. Wee, and I. Nishioka (2019) TV advertisement scheduling by learning expert intentions. In The 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, p. 3071–3081. External Links: Document Cited by: §1. T. van Erven, W. M. Koolen, and D. van der Hoeven (2021) Metagrad: adaptation using multiple learning rates in online learning. Journal of Machine Learning Research 22 (161), p. 1–61. Cited by: Table 5, Table 2. T. van Erven and W. M. Koolen (2016) Metagrad: multiple learning rates in online learning. Advances in Neural Information Processing Systems 29. Cited by: Table 5, Table 2. W. Wang and M. A. Carreira-Perpinán (2013) Projection onto the probability simplex: an efficient algorithm with a simple proof, and an application. Note: Available at arXiv:1309.1541 Cited by: Example 3.6. B. Wilder, B. Dilkina, and M. Tambe (2019) Melding the data-decisions pipeline: decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, p. 1658–1665. External Links: Document Cited by: §2. Appendix A Regret analysis for the suboptimality loss Let Θ be a nonempty subset of ℝdR^d. Let ℓ:Θ→ℝ be a loss function. Consider a sequence θtt=1T⊂Θ\θ^t\_t=1^T⊂ . We define the regret by Regret(T)=∑t=1T(ℓ(θt)−minθ∈Θℓ(θ)).Regret(T)= _t=1^T ( (θ^t)- _θ∈ (θ) )\,. In what follows, we review existing work on regret analyses for the suboptimality loss. The results are summarized in Table˜5. Table 5. Performance comparison of methods for solving the DDIOP for MILPs (Equation˜3.2). The integer T denotes the number of iterations or the number of optimization calls. The integer t denotes the iteration index or the optimization-call index. Method Regret for the suboptimality loss MWU (Arora et al., 2012) O(L(ℓsub)logdT)O (L( _sub) d T ), provided that Θ=Δd−1 = ^d-1 (Bärmann et al., 2018, Theorem 3.5) PSGD (online gradient descent) O(diam(Θ)L(ℓsub)T)O (diam( )L( _sub) T ) (Bärmann et al., 2018, Theorem 3.11) (with step size diam(Θ)L(ℓsub)−1t−1/2diam( )L( _sub)^-1t^-1/2) Besbes et al. (2021, 2025) O(d4logT)O (d^4 T ), provided that Θ is the unit sphere and L(ℓsub)≤1L( _sub)≤ 1 Gollapudi et al. (2021) O(dlogT)O (d T ), provided that Θ is the unit ball and L(ℓsub)≤1L( _sub)≤ 1 O(d2(d+1))O (d^2(d+1) ), provided that Θ is the unit ball and L(ℓsub)≤1L( _sub)≤ 1 ONS (Hazan et al., 2007) O(diam(Θ)L(ℓsub)dlog(T/d))O (diam( )L( _sub)d (T/d) ) (Sakaue et al., 2025, Theorem 3.1) MetaGrad (van Erven and Koolen, 2016; van Erven et al., 2021) O(diam(Θ)L(ℓsub)dlog(T/d))O (diam( )L( _sub)d (T/d) ) (Sakaue et al., 2025, Theorem 4.1) Cf. lower bound Ω(d) (d) (Sakaue et al., 2025, §5) Appendix B Online and offline optimization Let Θ be a nonempty subset of ℝdR^d. Let ℓ:Θ→ℝ be a function. Consider a sequence θtt=1T⊂Θ\θ^t\_t=1^T⊂ . Then, the following holds: mint=1,…,T(ℓ(θt)−minΘℓ)≤1T∑t=1T(ℓ(θt)−minΘℓ)≤Regret(T)T. _t=1,…,T ( (θ^t)- _ )≤ 1T _t=1^T ( (θ^t)- _ )≤ Regret(T)T\,. (B.1) By applying the existing regret bounds reviewed in Appendix˜A to Equation˜B.1, one can upper-bound the best-iterate performance for the suboptimality loss. For the resulting bounds, see Table˜2. Appendix C Additional remarks on Assumption 3 Remark C.1. We explain why it is preferable to exclude 0 from the weight space Θ . At the origin 0, one has ℓsub(0)=0 _sub(0)=0, and thus 0 attains the minimum value of the suboptimality loss. Consequently, for the DDIOP for MILPs (Equation˜3.2), θ=0θ=0 is a solution. However, the optimizer x∗(0,s(n))x^*(0,s^(n)) may be any point in X(s(n))X(s^(n)); hence, unless X(s(n))X(s^(n)) is a singleton, the optimizer is not uniquely determined. Therefore, even if the true weight were θ∗=0θ^*=0, Assumption 3 would not be satisfied. That is, even if learning returns θ=0θ=0, such a θ does not coincide with the true weight θ∗θ^*. This issue is common to many IOPs for LPs, regardless of whether the setting is online or offline (Bertsimas et al., 2015; Mohajerin Esfahani et al., 2018; Bärmann et al., 2018; Chen and Kılınç-Karzan, 2020; Sun et al., 2023; Kitaoka and Eto, 2023a, b; Kitaoka, 2024).