The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings David Martı́nez-Rubio
IMDEA Software Institute, Madrid, Spain
Brian Bullins*
arXiv:2609.20687v1 [math.OC] 17 Sep 2026
Purdue University, West Lafayette, IN, USA
Cristóbal Guzmán*
[email protected] Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile
Mathieu Molina*
Tel Aviv University, Israel
Abstract We study first-order black-box convex optimization over an ℓp -ball for objectives Lipschitz in the ℓq -norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set (p < q) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. e Our rates include O(1/T √ ) for convex Euclidean-Lipschitz optimization over the ℓ1 -ball, improving on the O(1/ T ) classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far. We bound the value of this game above and below in terms of a combinatorial online learning quantity: the sequential fat-shattering dimension, which we characterize for the ℓp /ℓq case. Our results generally apply when the feasible set X and the set of possible subgradients H are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel’s theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.
1. Introduction First-order optimization methods arise in high-dimensional settings as a basic computational primitive of continuous optimization across the sciences, engineering, statistics, and machine learning. The first-order oracle complexity model is the main framework to investigate optimal rates of convergence in high-dimensional convex optimization (NY83), with the Lipschitz setting being one of the most fundamental and natural regimes, widely satisfied across problems where local-search methods work (NY83; Nes04). *. Authors marked with an asterisk are listed alphabetically. . Most non-local notation in this work links to its definition, using this code; for example, X links to the definition of the feasible set of the optimization problem we consider in this work.
1
Martı́nez-Rubio Bullins* Guzmán* Molina*
The framework asks an algorithm ALG to minimize a convex Lipschitz function f accessed only via a local first-order oracle, which on a point x returns the value f (x) and a subgradient g ∈ ∂f (x), cf. 3. The minimax rate of the output x bT of ALG after T steps for a class of functions F, namely EX ,H (T ) := inf ALG supf ∈F (f (b xT ) − minx f (x)), is dictated by the geometry of the feasible set X and of the set H where subgradients of f can lie on. In the so-called dual setting, X is bounded in a given norm ∥ · ∥, and H is bounded in the dual norm ∥ · ∥∗ , that is, the objective is Lipschitz in ∥ · ∥ with a uniformly bounded Lipschitz constant. Dual settings were settled optimally in ℓp -norms using the Mirror Descent (MD) algorithm (NY83), that is, X = Bpd and H = Bpd∗ , where Brd denotes the unit ℓr -ball in d dimensions and p∗ satisfies 1/p + 1/p∗ = 1. More generally, it was shown that MD is universally optimal in a fairly broad family of dual problems (SST11). A vast majority of developed algorithms in this and other optimization problems work in dual settings. Nondual settings. The nondual problem is far less understood. A combinatorial quantity from learning theory, known as the fat-shattering dimension 1 for a class of linear functions depending on X and H, provides a lower bound even in nondual settings (SS12), and Sridharan [Sri12, Section 10.1.2, Q3] conjectures the possibility that this quantity determines the minimax complexity in general, up to constants. Guzmán [Guz15a] studies specifically the high-dimensional (p, q)-norm case, p, q ∈ [1, ∞], where X = Bpd , H = Bqd∗ , d ≥ T . The corresponding lower bounds, which are also fat-shattering lower bounds in hindsight, turn out to exhibit polynomial gaps with the best-known MD-based algorithm when p ≤ q (up to logarithmic factors). This gap motivates the open problem (Guz15b).2 The question is whether the geometry of the smaller feasible set Bpd ⊊ Bqd than in the dual setting, would allow for new algorithms that match the lower bound, or whether better lower-bound techniques are needed to establish the optimality of current algorithms. The question was also posed for smooth settings where new lower bounds were provided, which nonetheless presented a similarly gap. With the (1, 2) case as an example, if we optimize a Euclidean convex Lipschitz function f (x) with x in an ℓ1 -ball or√a subset of it, the currently best known high-dimensional rate does not improve over O(1/ T ), which is what is also achieved over the much larger ℓ2 -ball domain, whereas the lower bound only prevents a much faster decay of O(1/T ). It is worth noting that despite the remaining gaps in these nondual settings in the literature, they naturally appear in several applications. Any problem with a probability distribution as variable and Lipschitzness in an ℓq -norm q > 1, such as the natural Euclidean Lipschitzness condition, is a nondual problem. In inverse problems, mixed-geometries result from the discrepancy between a signal structure and measurement device. For block MIR sampling, there are optimization formulations whose feasible domain is a high-dimensional ℓ∞ box, and provably faster algorithms can be obtained by considering Lipschitzness measured in ℓp -norms, where 1 ≤ p ≤ 2 (BWB14). Another example is convex relaxations of sparse PCA 1. This quantity, introduced by Kearns and Schapire [KS94], is a continuous scale-sensitive analog of the VC dimension, cf. Definition 1. 2. The case p ≥ 2 when p < q, that was also stated as an open question (Guz15b) is in fact also solved optimally with mirror descent: a Gq -Lipschitz function in ℓq is also Gq -Lipschitz in ℓp , so running mirror descent over the RBpd and using the ℓp geometry gives rates of O(RGq /T 1/p ) for p ≥ 2, which nearly √ matches the lower bound. The hard question is p < min{q, 2}, where rates would be faster than O(1/ T ). Similarly, regular acceleration in the p-norm works near optimally when 2 < p < q.
2
(DMM+17), where the objective is a quadratic form given by the directional covariance, for which it is natural to regard the objective as Lipschitz in the ℓ2 -norm, and the feasible set is given by an intersection of ℓ2 - and ℓ1 -balls of different radii. In infinite dimensions, the Rudin-Osher-Fatemi model for total variation regularization in imaging leads to L2 constraints with an objective given by a total variation seminorm (ROF92). Main results. In this work, we identify a new high-dimensional phenomenon in convex optimization and achieve the O(1/T ) rate mentioned in the (1, 2) example above, up to log factors. More generally, for the (p, q)-norm case our rates are 1 ep,q , O 1 1 − − 12 p q + T which nearly match the mentioned lower bounds up to logarithmic factors, where (x)+ = max{x, 0}, 1/∞ = 0, solving the nonsmooth part of the COLT 2015 open question in (Guz15b), providing a polynomial improvement over the rate of Mirror Descent algorithms O(T −1/ max{q,2} ) = O(1/T 1/q−(1/q−1/2)+ ), when p < min{q, 2}. Additionally, we obtain an upper bound in the general setting where the feasible set X and the set of possible subgradients H are convex and centrally symmetric, showing that the minimax complexity is upper bounded by a combinatorial quantity known as the sequential fat-shattering dimension (sfat) which is no less than the fat-shattering dimension (fat), and we show they are the same up to log factors in the (p, q)-case. This general result provides the first positive contribution towards understanding the question posed by Sridharan [Sri12]. We achieve our results by defining and studying a new online learning game, of independent interest, which we explain in the following. Regret limitations, bundle methods, and our new max-regret. To put our solution into context, we first note that the question of Guzmán [Guz15b] is especially puzzling if one takes into account that, despite decades of research, the MD algorithm in Nemirovski and Yudin [NY83] is essentially the best known method for this problem, defaulting to the dual geometry when one could instead exploit the smaller geometry of the feasible set. Other families of algorithms have been devised under different names, like Dual Averaging or Follow-the-Regularized-Leader (FTRL) (Gor99; SS07; Nes09), or Follow-the-PerturbedLeader (KV03), but all can be viewed through the common template and analysis of optimizing summed-up linearizations together with a regularizer (ALS+14; McM17) and do not yield faster minimax rates. Most of the best known bounds in convex Lipschitz optimization are, in hindsight, regret bounds for the more general problem of online convex optimization (War98; Gor99; Zin03; BT03; Sha07). In this setting, a different convex function ℓt is chosen adversarially at every round even with knowledge of the Pcompeting algorithm, P and the performance after T steps is measured by the regret RT := Tt=1 ℓt (xt ) − inf u∈X Tt=1 ℓt (u). If we set all ℓt to f and output the average query, we obtain convex optimization rates of RT /T . However, any analysis that first reduces the optimization problem to worst-case regret for convex Lipschitz losses is formally limited to a Ω(T −1/2 ) guarantee as per dual (ST10; JMP+25) and nondual (RST15a, Proposition 9), (CDL25, Lemma 3 and Theorem 5) regret lower bounds, and can be worse for several geometries, which provides some evidence that MD algorithms may not be able to match the nondual lower bounds we achieve in 3
Martı́nez-Rubio Bullins* Guzmán* Molina*
this work, although a MD optimization analysis would not necessarily have to come from a reduction to regret. Our nearly-optimal rates are achieved via introducing a new paradigm: a new online learning game, where the metric is what we call the max-regret, where the comparator is measured via T times the maximum of previous losses, rather than the sum: max RX ,T :=
T X
ℓt (xt ) − inf T max ℓt (u), u∈X
t=1
t≤T
(1)
or RTmax , if X is clear from context. This regret is compatible with convex optimization P in the sense that the average query x̄T := T −1 Tt=1 xt can similarly be used to obtain optimization rates of RTmax /T , cf. Lemma 4, by setting all ℓt to f , or alternatively to its first-order Taylor approximation f (xt ) + ⟨gt , · − xt ⟩ at the query xt using subgradient gt ∈ ∂f (xt ). Note that by the nature of the max, we have RTmax ≤ RT . In the settings we study, RTmax will be significantly lower. We lower and upper bound the minimax value of the Lipschitz convex game by expressions depending on sequential fat-shattering, that we show they nearly match in several settings. In particular, they match for the (p, q)-norm case, where we characterize these quantities, up to log factors. Given the widespread applications of regret across areas of computer science, we believe the max-regret and its analysis to be of independent interest. Our results go in the direction of finding oracle-efficient algorithms using informationtheoretic arguments (ABR+08; AAB+09; RST10; ST10; RST11; RSS12). We establish the existence of a strategy minimizing the max-regret that leads to near-optimal firstorder oracle optimization complexity. This strategy can be turned into an exponential time algorithm by dynamic programming and standard discretization arguments, leading to an algorithm with runtime exponential in T and d. We leave the study of an algorithm that simultaneously achieves near-optimal first-order oracle rates and computational efficiency for a forthcoming paper. The latter property should be understood as the required number of real operations being polynomial in the number of optimal first-order oracle queries and the dimension. Finally, the minimization of the max-regret above should remind the reader of bundle methods (Kel60; LNN95; BN05; Lan15; DT16; DG23), which keep a maximum of affine minorants of the objective to compute their next query. Bundle methods have been reported to perform well in practice in terms of oracle queries (BN05; Lan15) but to the best of our knowledge, our algorithm is the first bundle method that provides an advantage in worstcase oracle optimization rates with respect to regret-based algorithms for convex Lipschitz optimization. In fact, we are not aware of any other problem class where bundle methods improve over other techniques. We refer to Appendix A for further related work. The iid case. An intermediate expression to bound the max-regret minimax value in the (p, q)-norm case, if specialized to the case where the losses are linear and iid, results in a problem of independent interest about how fast the convex hull of samples of a fixed distribution supported on Bq∗ , approaches its mean in ℓp∗ distance, cf. Lemma 6 and (9). Or a more general statement when working with general sets X , H. Our techniques also yield upper and lower bounds for this problem, see Theorem 7 and Corollary 8, which match in 4
the (p, q)-norm case. This result can be viewed as an early-time, quantitative analogue of Wendel-type convex-hull containment theorems (Wen62): the latter gives the exact probability that the convex hull of iid points from a centrally symmetric distribution in general position contains the origin, and gives a sharp transition at around the dimension. We instead measure the distance of the convex hull to the mean in the ℓp∗ norm and we use general bounded distributions, rather than symmetric ones. Previous quantitative variants have been obtained in very specific cases, including Euclidean distance for the uniform distribution (LY14) and distribution-dependent Euclidean-distance settings (HLO23). We note however that allowing general distributions changes the problem and answer substantially. Our results show a decay as fast as 1/T for the more benign geometries, but no faster. The 1D case already illustrates this phenomenon: if we have a symmetric distribution, we only need one sample on each side of the mean in order for the convex hull to contain it, and the probability of this not happening decreases as exp(−Ω(T )). However, for arbitrary distributions bounded in [−1, 1] and T steps, we have the distribution with atoms at −1 and 1/T with probabilities 1/(T + 1) and T /(T + 1), respectively, which is bounded but e would yield a decay in the expected distance of Θ(1/T ). We next give a technical overview of our main results in the concrete mixed ℓp /ℓq geometry and beyond, outlining the proof strategy and highlighting the core novel technical results that make the argument possible. 1.1. Technical Overview The upper bound proof proceeds in four steps. First, we show that max-regret controls the optimization error when applied to the supporting affine minorants returned by the firstorder oracle. Second, a minimax reduction turns the max-regret game into a sequential convex-hull approximation problem. Third, we bound the value of this game above and below using sequential fat-shattering, a scale-sensitive complexity measure for adaptive function classes. Finally, we characterize this combinatorial dimension for the associated linear class up to logarithmic factors and show that it nearly matches its non-sequential counterpart, the ordinary fat-shattering dimension. Combined with the known oracle lower bounds based on ordinary fat-shattering, this yields the main theorem. We sketch some of the arguments of these steps for the (p, q)-norm case for p < q. That is, the feasible set is Bpd and the subgradients live in Bqd∗ . Max-regret online-to-batch. We normalize f (0) = 0 without loss of generality. The max first-order oracle returns affine minorants ℓt (u) = f (xt ) + ⟨gt , u − xt ⟩ ≤ f (u). Let Vp,q ∗ ,T denote the minimax value of the max-regret attainable against adaptive affine losses with these slopes and also intercepts in [−1, 1], which is a consequence of Lipschitzness and normalizing f (0) = 0, as formalized in (7). The max-regret online-to-batch reduction in Lemma 4 therefore gives the following for the minimax optimization error. EBpd ,B d∗ (T ) ≤ q
max Vp,q ∗ ,T
T
,
so it is enough to study the minimax value of the max regret. Online reduction and stochastic processes. The minimax reduction in Proposition 5 removes the player’s decisions by choosing actions that minimize the conditional expected 5
Martı́nez-Rubio Bullins* Guzmán* Molina*
loss in the minimax-swapped game. Write π for an adversarial strategy that chooses predictable distributions (rt )t≤T from the previously sampled losses, draws ℓt ∼ rt , and has conditional mean mt (u) = E[ℓt (u) | ℓ1:t−1 ]. Then, we show in Proposition 5 that max Vp,q ∗ ,T
T
( ≤ sup Eπ sup π
u∈Bpd
) T 1X mt (u) − max ℓt (u) . t≤T T t=1
P P Here maxt ℓt (u) = maxλ∈∆T t λt ℓt (u), where ∆T = {λ ∈ [0, 1]T : t λt = 1}. For linear losses, these weights form convex combinations of the sampled gradients. We first provide bounds for the case where the losses are linear and iid, in which case duality identifies the inner supremum with the ℓp∗ -distance from their common mean to their convex hull (Lemma 6), a problem of independent interest. That is, for a probability distribution P supported on Bqd∗ , let µP := EG∼P [G], and let G1 , . . . , GT be independent samples from P . The expression above in this case becomes the worst-case expected distance from the mean to the convex hull of the samples, which is sup
E [distp∗ (µP , conv{G1 , . . . , GT })] ,
(2)
supp(P )⊆Bqd∗
where distp (x, S) is the p-norm distance from point x to set S.3 We show that the quantity 1 1 1 e p,q 1/T p − q − 2 + and in general it depends on the (nonsequential) above is of the order of Θ fat-shattering dimension. The bound is obtained using arguments from stochastic processes, that gracefully generalize to the adaptive non-iid case. One key idea consists of restricting (2) the convex-hull weights λt to a capped simplex ∆T = {λ ∈ ∆T : λt ≤ 2/T }. This can only increase the approximation error we must bound and allows for the use of stochastic processes tools. The intuition is that we have a scalar empirical-process problem in each direction u, and just uniform weights would provide strong averaging but only recover the usual T −1/2 fluctuation scale, whereas the full simplex can adapt completely to the realized sample but may concentrate all its mass on a single observation, destroying the averaging structure needed for concentration. The capped simplex interpolates between these two extremes: imposing λi ≤ κ/T forces every admissible combination to use at least T /κ samples, while still allowing the weights to adapt to the realization. Crucially, the approximation error over the capped simplex can be upper bounded by an P offset empirical process of the form E[ϕ(⟨u, G⟩)] − κT −1 i ϕ(⟨u, Gi ⟩) for some non-negative function ϕ. The extra factor κ > 1 creates a negative drift, so overcoming this drift requires a constant fraction of the samples to deviate coherently in the same unfavorable direction. Such collective deviations have exponentially decaying tails, yielding finite-class bounds of p order log N/T rather than the usual log N/T . The (sequential) fat-shattering dimension then enters by controlling the sizes of the covers used to pass from finite classes to the full function class, which is approximated at successively finer scales in a chaining argument. 3. We note by passing that the quantity (2) has some history in convex optimization. For example, (NY83) (page 163 therein) prove their ℓ1 -dual setting lower bound by building a distribution P that lower bounds the convex-hull distance problem.
6
Bounding the rate via sfat. After generalizing the stochastic processes argument to the sequential case, the relevant class whose complexity we study for the (p, q)-norm case is Ldp,q∗ = {Bqd∗ ∋ g 7→ ⟨u, g⟩ : u ∈ Bpd }. The final expression for the upper bound involves the so-called sequential covering numbers (RST15b) which are known to be bounded by sfatα (Ldp,q∗ ). A similar analysis in the iid case yields expressions depending on nonsequential covering numbers which are bounded by fatα (Ldp,q∗ ). Lower bounds on the max-regret value depending on these quantities also arise naturally leading to Theorem 10. Finally, we compute bounds for sfatα (Ldp,q∗ ) Set θp,q = 1/p − (1/q − 1/2)+ . For p < q and 0 < α ≲p,q 1, Theorem 12 establishes e p,q fatα (Ld ∗ ) . e p,q min α−1/θp,q , d 1 + log+ 1 = Θ sfatα (Ldp,q∗ ) = Θ p,q αdθp,q The upper bound covers the feasible ball by smaller uniformly convex balls, bounds the complexity within each ball, and combines the classes using a sequential union bound, cf. Lemma 27. For the lower bound, ordinary fat-shattering provides a cube of possible evaluation vectors; binary search along each coordinate turns this cube into an adaptively shattered tree. This also explains why sequential shattering can continue growing logarithmically after ordinary shattering saturates at dimension d. When T ≤ d, the scale α ≍p,q T −θp,q lies in the first regime. Substitution into the game bound yields the optimizaep,q (T −θp,q ) (Corollary 11); the ordinary-fat oracle lower bound of Srebro tion upper bound O and Sridharan [SS12, Theorem 1] matches this rate up to logarithmic factors. In particular, e (p, q) = (1, 2) gives O(1/T ). 1.2. A general Banach-space optimization bound via sfat, and consequences. The max-regret and sequential-fat shattering arguments are not specific to finite-dimensional mixed-norm geometry. Consider E a real reflexive Banach space, and X ⊆ E being a nonempty closed, bounded, convex feasible set containing 0, and H ⊆ E ∗ being a bounded set of admissible subgradients, along with the constant ΛX ,H := supg∈H,u∈X |⟨g, u⟩|, assumed to be finite. Our main result, Theorem 10, implies that if sfatα of the linear class LX ,H := {H ∋ g 7→ ⟨g, u⟩ : u ∈ X } , has a polynomial growth ΛX ,H r e sfatα (LX ,H ) = O , α for some r ≥ 1 and all α ∈ (0, ΛX ,H ], then the minimax optimization error satisfies e ΛX ,H T − min{1,1/r} . EX ,H (T ) = O The same conclusion holds when reflexivity is replaced by norm-compactness of the feasible set. We apply the general result to three infinite-dimensional function-space problems in Section 5, showing how faster rates can arise from the geometry of the feasible set and admissible subgradients even in more general settings. First, Proposition 13 considers the Sobolev unit ball of H s ([0, 1]m ) with L2 -bounded subgradients and proves the following bounds for fat, sfat and the minimax optimization rate for 0 < s ≤ m/2: 2m e s,m T −( 12 + ms ) , EX ,H (T ) = Θ fatα (LX ,H ) ≍s,m sfatα (LX ,H ) ≍s,m α− m+2s , 7
Martı́nez-Rubio Bullins* Guzmán* Molina*
By comparison, ignoring the Sobolev structure and viewing X only as a subset of the L2 unit ball gives the standard T −1/2 nonsmooth Hilbert-space rate via the sub-gradient algorithm (Sho64). Thus any positive Sobolev smoothness yields a polynomial improvement, reaching the 1/T scale at the critical smoothness level s = m/2. Second, Proposition 14 considers an optimization problem over normalized 1-Lipschitz functions on [0, 1]m with point-evaluation subgradients. By Arzelà-Ascoli the feasible set is compact, and fatα (LX ,H ) ≍m sfatα (LX ,H ) ≍m α−m ,
e m (T −1/m ). EX ,H (T ) = Θ
The one-dimensional case yields a 1/T rate. And third, Proposition 15 considers an ℓp -ball of coefficients in an orthonormal basis, for 1 < p < 2, with coordinate-evaluation subgradients. The ambient space is reflexive, although the feasible ball is not norm compact, and fatα (LX ,H ) ≍p sfatα (LX ,H ) ≍p α−p ,
e p (T −1/p ). EX ,H (T ) = Θ
The generic dual problem with the full ℓp∗ unit ball of subgradients instead has the standard T −1/2 nonsmooth rate (NY83) through mirror-descent. , so the faster T −1/p rate exploits the restricted coordinate-observation geometry. We also give concrete interpretations of these examples in terms of functional regression, individual fairness, and low-complexity wavelet representations for image compression and denoising. Together, they show that faster rates from nondual geometry are neither specific to the ℓp /ℓq setting nor to finite dimension, but are governed more generally by the pairing between feasible points and admissible subgradients.
2. Notation, Preliminaries and Groundwork For r ∈ [1, ∞], let r∗ ∈ [1, ∞] satisfy 1/r + 1/r∗ = 1, with the usual endpoint conventions, d d and denote the unit r-ball as r := {x ∈ R : ∥x∥r ≤ 1}. For T ≥ 1, we denote the PB T T simplex by ∆T = {λ ∈ R+ : t=1 λt = 1}. For a ∈ R, we use a+ := max{a, 0}, and write log+ t := (log t)+ . For a condition E, we write 1E for its 0/1 indicator. We write Oϑ (·) e when the omitted constant may depend on the parameter or tuple of parameters ϑ, and O(·) iid
to omit logarithmic factors. We denote G1:T ∼ P when G1 , . . . , GT are sampled iid from P . For a sequentially nested expression like the following, we use the compact notation: (sup EZt ∼rt )bt=a F (Za:b ) := sup EZa ∼ra · · · sup EZb ∼rb F (Za:b ), rt
ra
rb
where rt is allowed to be a predictable kernel depending on the past Za:t−1 . Given a nonempty decision set X , actions xt ∈ X , and losses ℓt : X → R in some class, we define the max-regret as in (1) without explicitly writing the losses class. Recall that the max-regret, despite its name, it is always no greater than the regular regret, due to the max appearing with a minus sign in its definition. Let X , H ⊆ Rd be origin-symmetric convex bodies. For the polar body and its associated norm, we write X ◦ := z ∈ Rd : supu∈X |⟨u, z⟩| ≤ 1 , ∥z∥X ◦ := supu∈X |⟨u, z⟩|. We define dist∥·∥ (x, S) = inf y∈S ∥y − x∥, and we use the shorthand notations distp = dist∥·∥p , and distX ◦ = dist∥·∥X ◦ . Analogous terminology will be used for infinite-dimensional settings. 8
Let X be a convex subset of a real normed space E. A function f : X → R is convex and subdifferentiable in X if for every x ∈ X there is a functional g ∈ E ∗ , such that: f (y) ≥ f (x) + ⟨g, y − x⟩
for every y ∈ X .
(3)
Then g is called a subgradient and the set of all such subgradients is the subdifferential ∂f (x). Throughout, our objectives are real-valued convex subdifferentiable functions on their feasible sets. In online learning, learnability is characterized in terms of combinatorial parameters. The following introduces the ones that are relevant to our results. Definition 1 (Fat-shattering and sequential fat-shattering dimensions) For a set Z, let G ⊆ RZ and α > 0. A set z1 , . . . , zm ∈ Z is α-shattered by G if there are thresholds s1 , . . . , sm ∈ R such that, for every ε ∈ {±1}m , some hε ∈ G satisfies α εi hε (zi ) − si ≥ , i = 1, . . . , m. 2 A depth-T predictable tree over Z is a sequence z = (zt )Tt=1 , with zt : {±1}t−1 → Z. It is sequentially α-shattered by G if there is a real-valued predictable tree s = (st )Tt=1 such that, for every ε ∈ {±1}T , some hε ∈ G satisfies α εt hε (zt (ε<t )) − st (ε<t ) ≥ , t = 1, . . . , T. 2 The fat-shattering dimension fatα (G) and its sequential version sfatα (G) are the largest possible such m and T , respectively. Note that using the definition with a predictable tree that is constant across each level yields fatα (G) ≤ sfatα (G); see also (RST15a, Section 2). Our upper bounds make use of the following ℓ∞ covering numbers, which in turn are controlled by fat for fixed designs (ABC+93) and by sfat for predictable trees (RST10, Corollary 4). Definition 2 (Sequential covers) For a fixed depth-T Z-valued tree z, an ℓ∞ sequential α-cover Vz of G is a set of depth-T trees over R such that ∀h ∈ G, ∀ε ∈ {±1}T , ∃v ∈ Vz such that max h zt (ε<t ) − vt (ε<t ) ≤ α. 1≤t≤T
Note that above v may depend on both h and ε, so it is a pathwise cover. The size of a seq worst-case optimal cover over depth-T trees is denoted by N∞ (α, G, T ):= supz minVz |Vz | We denote the nonsequential covering number by N∞ (α, G, z1:T ), which is the size of the worst-case optimal cover over trees where each level is constant. On a first read, the reader may just consider the following spaces to be finite-dimensional and the sets X and H being compact. We present our results in more generality and provide some infinite-dimensional examples, under mild assumptions. Let E be a real Banach space, let X ⊆ E be our feasible set: a nonempty closed, bounded, convex set containing 0. Let H ⊆ E ∗ be a nonempty bounded centrally symmetric set containing 0.4 We write 4. We tacitly equip all spaces below with the natural σ-algebras making the relevant evaluation maps and probability kernels measurable.
9
Martı́nez-Rubio Bullins* Guzmán* Molina*
⟨g, u⟩ := g(u) for the duality pairing between E ∗ and E. We equip X with the weak topology. Since E is reflexive and X is closed, bounded, and convex, X is weakly compact, while every map u 7→ ⟨g, u⟩, g ∈ E ∗ , is weakly continuous. Define the cross-duality constant and the affine sample space by ΛX ,H :=
sup
|⟨g, u⟩|,
ZX ,H := H × [−ΛX ,H , ΛX ,H ].
(4)
g∈H, u∈X
The boundedness assumptions imply ΛX ,H < ∞. Define the associated linear and affine pairing classes by LX ,H := {H ∋ g 7→ ⟨g, u⟩ : u ∈ X } , AX ,H := {ZX ,H ∋ (g, b) 7→ ⟨g, u⟩ + b : u ∈ X } .
(5)
Every function in LX ,H takes values in [−ΛX ,H , ΛX ,H ]. Note that the linear class LX ,H , which we will use in shattering constants fat and sfat, is about shattering the space of subgradients in X using linear functions whose gradients are points in the domain X . That is, the roles of X and H are dualized in the shattering reduction, with respect to how we think about them in optimization. We consider convex subdifferentiable functions f : X → R, normalized by f (0) = 0, accessed through a first-order oracle. At every query x ∈ X , the oracle returns the value f (x) and a subgradient g ∈ ∂f (x) ∩ H in the sense of (3). For a query xt ∈ X with oracle output gt ∈ H, let ℓt (u) := ⟨gt , u⟩ + bt , where bt := f (xt ) − ⟨gt , xt ⟩. Since f (0) = 0 and f admits an H-valued supporting functional at 0, we have bt ∈ [−2ΛX ,H , 0]. Thus Yt := (gt , bt +ΛX ,H ) belongs to ZX ,H , and, for every u ∈ X , the function au (g, b) := ⟨g, u⟩+b in AX ,H satisfies au (Yt ) = ℓt (u) + ΛX ,H . This common shift leaves max-regret unchanged. We define the minimax error after T adaptive first-order oracle queries as EX ,H (T ) := inf
sup f (b xT ) − inf f (u),
ALG f,Oracle
u∈X
(6)
where ALG outputs x bT ∈ X after T queries, and the supremum ranges over admissible convex objectives f and valid adaptive first-order oracles. We often use r ∈ [1, ∞] in a subscript to denote Brd , so for instance Ldp,q∗ and Adp,q∗ correspond to (5) when (X , H) = (Bpd , Bqd∗ ), where we made d explicit to remove ambiguity. As a running concrete example, on a first read, the reader may simply keep in mind E = Rd , X = Bpd , and H = Bqd∗ , which is the setting of the optimization open question. In particular, if p ≤ q, then Λp,q∗ = 1, since |⟨g, u⟩| ≤ ∥u∥p ∥g∥p∗ ≤ ∥g∥q∗ ≤ 1. Next, we state our general setting. We work in spaces where a minimax theorem works for the value of the max-regret game VXmax ,H,T , defined below. Assumption 3 Let X ⊆ E, H ⊆ E ∗ be nonempty, convex and symmetric with respect to 0, with H bounded and ΛX ,H < ∞, and such that the minimax theorem consequence 1 applies, where rt and st are distributions over the affine loss class F := {x 7→ ⟨g, x⟩ + b : (g, b) ∈ ZX ,H } and over X , chosen by the adversary and the player, respectively. The 10
minimax value of the game is defined as: ) T (X T VXmax inf sup ℓt (xt ) − inf T max ℓt (u) ,H,T := xt ∈X ℓt ∈F
1 =
t=1
( T X
T sup inf Ext ∼st rt
st
ℓt ∼rt
u∈X
t=1
t=1
t=1
(7)
t∈[T ]
) ℓt (xt ) − inf T max ℓt (u) u∈X
t∈[T ]
We further assume that for every η > 0, an η-minimizing action exists for the conditional expectation of an announced loss distribution inf x∈X Eℓt ∼rt (·|x1:t−1 ,ℓ1:t−1 ) ℓt (x). The assumption above is mild, and in particular it holds for finite-dimensional compact sets X , H symmetric with respect to 0. Indeed, see Abernethy et al. [AAB+09] that made this connection for the regular regret, between minmax regret and its analogous form after 1 by taking randomized strategies and applying the minmax theorem. The minimax assumption 1 holds more generally whenever there exists a Hausdorff locally convex topology τ for which X is compact and convex and every admissible affine loss u 7→ ⟨g, u⟩ + b is τ -continuous. In this case, the required minimax interchange follows from Sion’s minimax theorem (Sio58). This covers the standard settings used throughout the paper: closed and bounded feasible sets in finite-dimensional spaces, which are compact in the usual Euclidean topology (AAB+09; RST11); norm-compact feasible sets in arbitrary Banach spaces, such as closed uniformly bounded equicontinuous classes of continuous functions by the ArzelàAscoli theorem; and closed bounded convex feasible sets in reflexive Banach spaces, which are weakly compact, while continuous linear functionals, and hence admissible affine losses, are weakly continuous. The η-optimal selection condition holds whenever X is separable in norm: conditional expected affine losses are norm-continuous, so one may choose the first η-optimal point in a fixed countable dense subset. Some of the hypotheses in Assumption 3 are imposed only for simplicity and can be weakened. In particular, the set X could be symmetric with respect to an arbitrary center. Or H need not be centrally symmetric or contain 0 for the upper-bound argument: it is enough for H to be bounded. In finite-dimensional settings, more general loss classes may also be treated whenever the corresponding minimax interchange and existence of η-minimizing strategies is valid. In fact, Proposition 5 does not use convexity of the losses. The following lemma makes explicit how max-regret allows for a simple reduction to minimizing a convex function, by repeatedly using it or surrogates of it like its linearizations at queried points ℓt (x) = f (xt ) + ⟨gt , x − xt ⟩, gt ∈ ∂f (xt ). It works since the first-order information observed along the optimization trajectory must be consistent with affine minorants of a single convex function. The lemma is analogous to the classical online-to-batch conversion for regular regret. Lemma 4 (Max-regret online-to-batch) For a convex set X , let f : X → R be a convex function and for an max-regret game (1) with query xP t , t ∈ [T ], let ℓt (x) : X → R satisfy ℓt (x) ≤ f (x) and ℓt (xt ) = f (xt ). Then for x̄T = T −1 Tt=1 xt and any u ∈ X , we have max RX ,T f (x̄T ) − f (u) ≤ . T 11
Martı́nez-Rubio Bullins* Guzmán* Molina*
For instance, u can be a minimizer x∗ of f , if it exists. Proof We use Jensen’s inequality in 1 , the assumption about ℓt in 2 . For 3 , we use the definition of max-regret that compares with the best fixed action versus the fixed action u: T T max 1 X 2 X 3 RX f (xt ) ℓt (xt ) ,T f (x̄T ) − f (u) ≤ − f (u) ≤ − max ℓt (u) ≤ . t≤T T T T t=1
t=1
3. Reduction to convex-hull approximation problem, and the iid case We upper bound the value of the game by an expression involving only the sampled losses and their conditional means along the realized history. Motivated by the triplex framework of Rakhlin, Sridharan, and Tewari [RST11], we remove the player’s choices directly by minimizing conditional expected losses in the minimax-swapped game. Proposition 5 (Online reduction) [↓] Under Assumption 3, let rtR(· | ℓ1:t−1 ) range over predictable distributions for admissible losses, and define mt (u) := ℓ(u) rt (dℓ | ℓ1:t−1 ). Then ( T ) X T sup VXmax mt (u) − T max ℓt (u) . (8) ,H,T ≤ sup Eℓt ∼rt rt
t=1 u∈X
t=1
t≤T
Recall that the losses are ⟨gt , ·⟩ + bt , with (gt , bt ) ∈ ZX ,H . The mixed-norm case with p ≤ q is recovered using gt ∈ Bqd∗ and bt ∈ [−1, 1]. The offsets are important for the reduction from optimization but, as Theorem 10 shows, they only create a lower-order term. Before bounding the right-hand side of Proposition 5 in the fully adaptive affine setting, it is illustrative to look at the simpler iid linear case. This already gives the aforementioned version of a classical convex-hull problem (Wen62) but quantitative and for general nonsymmetric distributions instead. We start from the simplification in which all the losses are iid and linear, rather than adaptive affine losses with arbitrary predictable means. Let X , H ⊆ Rd be origin-symmetric convex bodies. In this iid linear case, bounding the online-reduction term is exactly the problem of approximating the mean of a distribution by the convex hull of its samples in the polar norm ∥ · ∥X ◦ , as we show next. The iid property allows the bound to depend on fat, rather the sfat that will appear in the adaptive case. R Lemma 6 (iid specialization) [↓] Let P be supported on H, with mean µP := g dP (g). If the losses in the right-hand side of (8) are the iid linear losses ℓt (x) = ⟨Gt , x⟩, with iid
G1:T ∼ P and mt (u) = Eℓt (u), then the corresponding term, divided by T , satisfies ( T ) X 1 E sup mt (u) − T max⟨Gt , u⟩ = E iid iid distX ◦ (µP , conv{G1:T }) . G1:T ∼ P t≤T T G1:T ∼ P u∈X t=1
Note that above mt (u) = ⟨µP , u⟩. We now study worst-case bounds in this iid setting. Define the worst-case expected X ◦ -distance from the convex hull of T samples to their common mean: ConvDistwc X ,H,T :=
sup supp(P )⊆H
E
iid
G1:T ∼ P
12
distX ◦ (µP , conv{G1:T }) .
(9)
In this case, we can obtain upper and lower bounds depending on fat. Theorem 7 (iid convex-hull approximation) [↓] Let T ≥ 2, set Λ := ΛX ,H , and write ,H fatX := fatη (LX ,H ). There are universal constants C, c, γ > 0 such that η " ( #) Z Λ ,H eT Λ α fatX C ,H α γ sup fatX Λ+ dβ . ∧ 1 ≤ ConvDistwc Cα + X ,H,T ≤ inf cβ log 0<α≤Λ T T β α>0 8 α Using the known values of fat for the (p, q)-norm case, cf. (11) and (12), we obtain that our previous bounds nearly match in this case. Corollary 8 [↓] Let 1 ≤ p, q ≤ ∞ and T ≥ 2. If d ≥ T , then ( 1 − 1 )+ d q p 1 e ≲p,q ConvDistwc 1 1 1 p,q ∗ ,T = Op,q −( − ) + T Tp q 2
! ( 1 − 1 )+ d q p 1 . 1 −( 1 − 1 ) T Tp q 2 +
If d ≤ T , then e ConvDistwc p,q ∗ ,T = Θp,q
1− p1 +( 1q − 12 )+
d
T
! .
Observe that, as we advanced earlier, when d ≤ T , the decay is not exponential. We now provide another lower bound, based on a coupon-collector argument. It is useful for p = 1, q ≥ 2 in the high-dimensional regime d ≥ T and regimes trivially close to it, where the corresponding lower bound in Corollary 8 is Ω(1/T ). In that case, it contains an additional logarithmic factor. In other cases the fat-shattering lower bound in Corollary 8 dominates for T greater than some constant. Proposition 9 (Coupon-collector lower bound for the iid case) [↓] There exists a universal constant c > 0 such that, for every p, q ∈ [1, ∞] and T ≥ 3, and every dimension d ≥ T , we have log T ConvDistwc . p,q ∗ ,T ≥ c T The lower bound is witnessed by a mean-zero distribution supported on Bqd∗ . For any law P supported on Bqd∗ , the law of (G − µP )/2 is centered and supported on the same ball. Against its iid linear losses, with G1:T ∼ P , every player has 0 expected loss. Thus the duality calculation in Lemma 6, followed by taking the supremum over P , gives max Vp,q ∗ ,T
T
≥
1 E distp∗ (0, conv{(Gt − µP )/2 : t ∈ [T ]}) = ConvDistwc p,q ∗ ,T . 2 supp(P )⊆B d∗ sup
q
The factor 1/2 ensures (Gt − µP )/2 ∈ Bqd∗ , since ∥Gt − µP ∥q∗ ≤ 2; translation invariance and homogeneity of distance give the equality. The purpose of the current section is noting that a special case of our problem yields many interesting results, adjacent to already studied probability questions, like Wendel’s theorem (Wen62). In the next section, we study the case in which losses are adaptively 13
Martı́nez-Rubio Bullins* Guzmán* Molina*
chosen by an adversary, which yields the optimization rates. The iid case is a special case of the latter and the proofs are essentially the same, except that at the end of the upper bounds proofs and for the lower bounds, we have to distinguish between using predictable trees and sequential coverings, leading to a sfat dependence, versus fixed settings and nonsequential covering numbers leading to a fat dependence.
4. Adaptive rate and sequential convex-hull approximation We prove a fully sequential version in which the distributions are chosen adaptively. Although the game itself involves affine losses, the associated linear class captures the order of the upper bound, and the offset coordinate will be shown to contribute only a low order term. Consequently, the final upper bound is expressed in terms of the sequential fat-shattering dimension of the underlying linear class. Our final result can be compared in spirit to the one in (RST15a, Proposition 9), where the authors obtained some bounds for the minimax value of regular online learning via Rademacher complexities and sequential fat-shattering expressions. However, the symmetrizations leading to the Rademacher complexity are possible in online learning due to all expressions involving sums. Treating max-regret requires a substantially different treatment. We now introduce some notation. At each time t = 1, . . . , T , after observing the history y1:t−1 = ((g1 , b1 ), . . . , (gt−1 , bt−1 )), the adversary chooses a probability distribution Pt (· | y1:t−1 ) supported on ZX ,H . We write Yt = (Gt , Bt ) ∼ Pt (· | Y1:t−1 ). For a function f : ZX ,H → R, set Z (Pt f )(y1:t−1 ) := f (g, b) dPt (g, b | y1:t−1 ), ZX ,H
and abbreviate this quantity as Pt f along a realized path. The predictable means of the two coordinates are5 Z Z g dPt (g, b | y1:t−1 ), βt (y1:t−1 ) := b dPt (g, b | y1:t−1 ). µt (y1:t−1 ) := ZX ,H
ZX ,H
Each sample Yt = (Gt , Bt ) defines the affine score u 7→ ⟨Gt , u⟩ + Bt . Define the normalized one-sided approximation functional (* + ) T T T X 1X 1X GX ,H,T (Y1:T ) := sup µt , u + βt − max λt (⟨Gt , u⟩ + Bt ) . λ∈∆T T T u∈X t=1
t=1
t=1
For these affine losses, the conditional mean in Proposition 5 is mt (u) = ⟨µt , u⟩ + βt . Thus that proposition gives T max VX ,H,T ≤ T sup EYt ∼rt GX ,H,T (Y1:T ), t=1
rt
where each rt is supported on ZX ,H . Every function in LX ,H is bounded in [−ΛX ,H , ΛX ,H ]. When p ≤ q, (X , H) = (Bpd , Bqd∗ ) recovers the preceding Bqd∗ × [−1, 1] setup. 5. In the general Banach-space setting, E ∗ -valued integrals are understood weakly: µt ∈ E ∗ is defined by R ⟨µt , u⟩ = ⟨g, u⟩ dPt (g, b | y1:t−1 ) for every u ∈ E. We only use µt through such duality pairings.
14
We now present our main theorem. In order to show the conclusion for the (p, q)-norm case, we make use of sfat bounds the linear classes between finite-dimensional p-norm spaces Ldp,q∗ , where E = Rd , X = Bpd , H = Bqd∗ , which we prove in the next subsection. ,H Theorem 10 [↓] Under Assumption 3, let T ≥ 1, set Λ := ΛX ,H , and write sfatX := η sfatη (LX ,H ). There are universal constants C, c, γ > 0 such that
α sup α>0 2
,H sfatX α ∧1 T
≤
VXmax ,H,T T (
≤ inf
0<α≤Λ
" Z Λ #) eT Λ C eΛ X ,H γ sfatcβ log Cα + Λ 1 + log + dβ . T α β α
Thus, if p ≤ q and T ≤ d, then 1 1
Tp
−( 1q − 21 )+
≲p,q
max Vp,q ∗ ,T
T
ep,q =O
1 1
Tp
−( 1q − 12 )+
.
r e More generally, if sfatα (LX ,H ) = Θ((Λ X ,H /α) ) for some r ≥ 1 and all α ≤ ΛX ,H , then
VXmax ,H,T T
e X ,H T −1/r ). = Θ(Λ
(10)
For p > q, the last statement, along with the max-regret online-to-batch conversion in Lemma 4, recovers the known matching upper and lower bounds up to log factors from classical constructions and mirror descent (Guz15b; Guz15a). Moreover, for p ≤ q and T ≤ d, we obtain our main optimization result, nearly matching the lower bounds in citet(Guz15b; Guz15a). Corollary 11 (First-order optimization bound) [↓] Let 1 ≤ p ≤ q ≤ ∞, d, T ∈ N, and F be the class of convex 1-Lipschitz functions Rd → R in ∥ · ∥q . There is a deterministic algorithm that for any f ∈ F, after making T queries to a first-order oracle, computes x bT such that 1 ep,q f (b xT ) − min f (u) = O . 1 −( 1 − 1 ) u∈Bpd Tp q 2 + Similarly, the general optimization oracle complexity upper bound derived from the last part of Theorem 10 and Lemma 4 gives a partial answer to Sridharan [Sri12, Section 10.1.2, Q3], which conjectured a similar upper bound depending on fatα (LX ,H ) instead of sfatα (LX ,H ), for any general value of fatα , instead of our polynomial decay; see Appendix A. 4.1. Sequential Fat-Shattering of Linear Classes between Bpd and Bqd∗ Set Lα := 1 + log+ (ed/α). Since every function in Ldp,q∗ takes values in [−Λp,q∗ , Λp,q∗ ], we have sfatα (Ldp,q∗ ) = 0 whenever α > 2Λp,q∗ since we cannot have function value separation greater than the range of the function class. Thus the next theorem is stated on the nontrivial scale 0 < α ≤ 2Λp,q∗ . At p = q = ∞, we interpret its second line as sfatα (Ld∞,1 ) ≍ d(1 + log+ (1/α)) on this same scale. 15
Martı́nez-Rubio Bullins* Guzmán* Molina*
Theorem 12 (Near-optimal sfat bounds) [↓] Assume 0 < α ≤ 2Λp,q∗ . Then, sfatα (Ldp,q∗ ) lies, up to constants depending only on p, q, between the following quantity and Lα times it: −1 1 − p1 −( 1q − 21 )+ , p < q, , d 1 + log+ min α 1 −( 1q − 12 )+ p αd ! ! d1/q−1/p max{q,2} 1/q−1/p d min , d 1 + log+ 1/ max{q,2} , p ≥ q. α αd
5. Optimization over Infinite-Dimensional Function Spaces In this section, we exploit the generality of our results and elaborate on three applications on infinite-dimensional spaces, in which the decision variable is a function on Ω := [0, 1]m , by providing the optimization minmax rate via bounds on the corresponding fat-shattering dimension. The first application considers a Sobolev ball with L2 -bounded subgradients, the second a ball of Lipschitz functions with point-evaluation subgradients, and the third functions whose coefficients lie in an orthogonal-series representation belonging to an ℓp ball. The Sobolev example fits the reflexive Banach-space setting and is in fact norm compact in L2 , the Lipschitz example uses norm compactness in the nonreflexive space C(Ω), and the coefficient example has a norm-noncompact feasible ball whose weak compactness follows from reflexivity. To keep notation light, we reuse X and H for the feasible set and admissible subgradient set in each subsection. We repeatedly use the last part of Theorem 10 and its implication of an optimization rate, after using Lemma 4, and the lower bound of Srebro and Sridharan [SS12] in terms of fat. That is, the minimax rates are r e ΛX ,H T −1/r , if sfatα (LX ,H ) ≍p,q fatα (LX ,H ) = Θ((Λ e EX ,H (T ) = Θ X ,H /α) ) for r ≥ 1 and all α ≤ ΛX ,H . In each example below, it suffices to identify the sequential fat-shattering profile of the corresponding pairing class. We will use examples for which ΛX ,H ≤ 1. A natural application of our results is constrained regression over infinite-dimensional function classes. The decision variable is a function u, while X encodes structural assumptions on the regression function (such as Sobolev smoothness, Lipschitz regularity, or sparse like representation) and H specifies the linear measurements through which the loss accesses u. Equivalently, H induces the observable metric supg∈H |⟨g, u − v⟩| which measures how distinguishable two candidate functions are under the available measurements. Thus the resulting optimization complexity depends jointly on the regularity class X and on the observation model H. 5.1. Optimization over Sobolev balls Fix 0 < s ≤ m/2 and let X := u ∈ H s (Ω) : ∥u∥H s (Ω) ≤ 1 ⊆ L2 (Ω),
H := BL2 (Ω) .
Here H s (Ω) denotes the usual L2 -Sobolev space of smoothness s. For integer s, its norm controls the L2 norms of the weak derivatives of u up to order s.6 We normalize the norm so that ∥u∥L2 ≤ ∥u∥H s . The Rellich-Kondrachov theorem implies that X is compact as 6. For noninteger s, we can use the standard fractional Sobolev definition.
16
a subset of L2 (Ω), while Cauchy-Schwarz gives ΛX ,H ≤ 1. Hence the result for a norm compact space applies. Functional linear regression. A natural statistical application is functional linear regression with a smooth coefficient function, see (RS05; CKS09). Given functional covariates Zi ∈ L2 (Ω) and responses Yi ∈ R, the goal is to find the best function u ∈ X that minimizes N 1 X ℓ Yi − ⟨Zi , u⟩L2 . N i=1
When ∥Zi ∥L2 ≤ 1 and ℓ is convex and 1-Lipschitz, every subgradient of this functional belongs to BL2 (Ω) , so the present result applies directly. This includes nonsmooth losses such as absolute-deviation and quantile regression. We now prove the shattering bounds that yields the tight minimax rate. Proposition 13 [↓] For every m ≥ 1 and 0 < s ≤ m/2, for all sufficiently small α > 0, 2m
fatα (LX ,H ) ≍s,m sfatα (LX ,H ) ≍s,m α− m+2s . Consequently, e s,m T −( 21 + ms ) . EX ,H (T ) = Θ Thus every positive amount of Sobolev smoothness in this regime yields a polynomial improvement over the natural T −1/2 rate obtained by the classical subgradient method. At the critical smoothness s = m/2, the rate reaches the 1/T scale. As can be seen by the exponent s/m, what matters for this class, is the amount of smoothness relative to the ambient dimension. 5.2. Optimization over Lipschitz balls Work in C(Ω) endowed with the supremum norm, ∥u∥∞ = supx∈Ω |u(x)|, and let X := {u ∈ C(Ω) : u(0) = 0,
|u(x) − u(y)| ≤ ∥x − y∥∞ for all x, y ∈ Ω} .
For each x ∈ Ω, let δx (u) := u(x) and let the point evaluations be H := {0} ∪ {±δx : x ∈ Ω}. Thus LX ,H is simply the class of 0-normalized 1-Lipschitz functions on Ω. Moreover, X is compact in the supremum norm by the Arzelà-Ascoli theorem and ΛX ,H ≤ 1. Individual fairness. We give an example application from fairness in machine learning. We consider a point x ∈ [0, 1]m as the feature vector of an individual, and let u(x) denote the score or decision assigned to that individual, such as the salary, credit score, or some priority score. A Lipschitz constraint then requires individuals with similar features to receive similar scores, this is a standard formulation that is called individual fairness (DHP+12). Given a baseline score v, solving minu∈X ∥u − v∥∞ corresponds to finding an individually fair score with minimum worst-case deviation. Proposition 14 [↓] For all sufficiently small α > 0, fatα (LX ,H ) ≍m sfatα (LX ,H ) ≍m α−m . Consequently, e m (T −1/m ). EX ,H (T ) = Θ 17
Martı́nez-Rubio Bullins* Guzmán* Molina*
In particular, when m = 1, the minimax rate is 1/T . When m = 2, it is the T −1/2 scale, while for m > 2 this grows slower than the usual T −1/2 rate. Relation to the Sobolev example. The two preceding examples encode different forms of regularity. The Sobolev constraint of H s controls smoothness through square-integrable derivatives and is paired above with the full L2 unit ball of subgradients. The Lipschitz constraint instead controls pointwise variation and is paired with point evaluations. Sobolev embedding relates these classes for sufficiently large s, but using that embedding to control the Sobolev example would be lossy. 5.3. Optimization over an ℓp Coefficients Ball Let (ϕj )j≥1 be a real orthonormal basis of L2 (Ω) and fix 1 < p < 2. Let X :=
u=
X
θj ϕ j :
j≥1
X
|θj | ≤ 1 , p
j≥1
P p 1/p . For where the ambient space is equipped with the coefficient norm ∥u∥ := j≥1 |θj | each j ≥ 1, define the coordinate functional ⟨gj , u⟩ := ⟨u, ϕj ⟩L2 (Ω) = θj , and let H := {gj : j ≥ 1}. Since ℓp ⊆ ℓ2 , these series converge in L2 (Ω). Under the coefficient map, the ambient space is isometric to ℓp , and is therefore reflexive. Notice also that X is not compact for the norm-topology as the functions ϕj belong to X and satisfy ∥ϕj − ϕk ∥ = 21/p for j ̸= k which means that this sequence does not have a convergent sub-sequence. Wavelet reconstruction. For Ω = [0, 1]2 , we may take (ϕj ) to be an orthonormal wavelet basis. Sparse or ℓp -structured wavelet representations are classical models for lowcomplexity signal and image representations, with applications to compression and denoising, see for instance Mallat [Mal09]. Suppose that v ∈ L2 (Ω) is an observed image and that we seek a low-complexity approximation u ∈ X . For a finite collection of wavelet coefficients, one natural criterion is to minimize max1≤j≤M |⟨u, ϕj ⟩L2 − ⟨v, ϕj ⟩L2 |, the maximum discrepancy between the wavelet coefficients of the reconstruction and those of the observed image, subject to the ℓp constraint on the coefficients of u. Proposition 15 [↓] For all sufficiently small α > 0, fatα (LX ,H ) ≍p sfatα (LX ,H ) ≍p α−p . Consequently, after symmetrizing the coefficient functionals, e p (T −1/p ). EX ,H (T ) = Θ Unlike the Sobolev ball, which after diagonalization is a weighted ℓ2 ball with coefficients penalized by weights wj ≍ j s/m , this X is an unweighted ℓp ball, so it controls sparsity or compressibility of the coefficient sequence rather than imposing increasing decay with frequency. 18
6. Conclusion We have solved the nonsmooth regime of the COLT open question (Guz15b) by showing that the optimal minmax rate coincides, up to polylog factors, with the rate of the previously known lower bounds. The new substantial improvement occurs when p < min{q, 2}, while we point that 2 < p < q can be in fact solved by mirror descent. We expect that the techniques and results developed in this work will reach other applications. To the best of our knowledge, no previous general quantitative results for average convex-hull approximation to the mean were devised previously. An important open question for future work is that of finding efficient algorithms that realize the bounds found in this work, as well as extending the speed advantage to Hölder-smooth settings. We also gave a partial answer to the open question in Sridharan [Sri12, Section 10.1.2, Q3] about whether the complexity of convex Lipschitz optimization could be upper bounded in terms of fat-shattering dimension. We upper bounded it in terms of sequential fatshattering dimension instead. These two quantities were only logarithmic factors away in our (p, q)-norm case, as well as in the Lipschitz, Sobolev, and L2 orthonormal basis examples.
Acknowledgments Cristóbal Guzmán was partially funded by ANID FONDECYT 1251029 grant, and ANID Basal FB210017 National Center for Artificial Intelligence CENIA. David Martı́nez-Rubio was funded by grant La Caixa Junior Leader Fellowship 2025. He thanks OpenAI for free access to their models. Mathieu Molina received funding from the European Research Council (ERC) under the European Union’s Horizon Europe program (grant agreement No. 101170373), as a postdoctoral fellow at Tel Aviv University. This work was elaborated in combination with ChatGPT/Codex, that helped in a few places after a highly interactive workflow. Many of the main ideas (definition of the maxregret as a tool for solving the problem, online reduction removing player’s actions, use of the capped simplex for the stochastic processes bound, iid simplified case, structure of lower bounds, among others) were from the authors, while AI was used to accelerate computations, checks and elaboration of some proofs. The computation of sequential fat-shattering bounds was mostly done by AI, and then checked and rewritten. The majority of this AI use, except for minor later refinements, was done with GPT 5.5 and earlier models (the newest models when we worked on the main results), except for the infinite-dimensional results. For the bounds of the latter results, many of the ingredients were classical but dispersed in the literature. We used GPT 5.6 and 6 to identify and synthesize these ingredients and derive short self-contained proofs tailored to our setting. The authors checked and rewrote the proofs that were automated, simplifying the presentation and making the main ideas more transparent. In particular, they are solely responsible for the contents of this manuscript.
19
Martı́nez-Rubio Bullins* Guzmán* Molina*
References [AAB+09]
Jacob Abernethy, Alekh Agarwal, Peter L Bartlett, and Alexander Rakhlin. A stochastic view of optimal regret through minimax duality. In: Proceedings of the 22nd Annual Conference on Learning Theory. 2009 (cit. on pp. 4, 11).
[AB99]
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge: Cambridge University Press, 1999. isbn: 9780521573535 (cit. on pp. 27, 40, 41).
[ABC+93]
Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. ScaleSensitive Dimensions, Uniform Convergence, and Learnability. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science. IEEE, 1993, pp. 292–301 (cit. on p. 9).
[ABM+20]
Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure Properties for Private Classification and Online Prediction. In: Proceedings of the Thirty Third Conference on Learning Theory. Ed. by Jacob Abernethy and Shivani Agarwal. Vol. 125. Proceedings of Machine Learning Research. PMLR, 2020, pp. 119–152 (cit. on p. 45).
[ABR+08]
Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal Strategies and Minimax Lower Bounds for Online Convex Games. In: Proceedings of the 21st Annual Conference on Learning Theory. 2008, pp. 415– 424 (cit. on p. 4).
[ALS+14]
Jacob D. Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online Linear Optimization via Smoothing. In: Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014. Ed. by Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári. Vol. 35. JMLR Workshop and Conference Proceedings. JMLR.org, 2014, pp. 807–823 (cit. on p. 3).
[BCL94]
Keith Ball, Eric A. Carlen, and Elliott H. Lieb. Sharp Uniform Convexity and Smoothness Inequalities for Trace Norms. In: Inventiones Mathematicae 115.3 (1994), pp. 463–482 (cit. on p. 48).
[BN05]
Aharon Ben-Tal and Arkadi Nemirovski. Non-Euclidean Restricted Memory Level Method for Large-Scale Convex Optimization. In: Mathematical Programming 102.3 (2005), pp. 407–456 (cit. on pp. 4, 28).
[BT03]
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. In: Oper. Res. Lett. 31.3 (May 2003), pp. 167–175. issn: 0167-6377 (cit. on p. 3).
[BWB14]
Claire Boyer, Pierre Weiss, and Jérémie Bigot. An Algorithm for Variable Density Sampling with Block-Constrained Acquisition. In: SIAM Journal on Imaging Sciences 7.2 (2014), pp. 1080–1107 (cit. on p. 2).
[CDL25]
Chen Cheng, John C. Duchi, and Daniel Levy. Geometry, Computation, and Optimality in Stochastic Optimization. An earlier version appeared at NeurIPS 2019 as “Necessary and Sufficient Geometries for Gradient Methods”. 2025 (cit. on pp. 3, 26). 20
[CKS09]
Christophe Crambes, Alois Kneip, and Pascal Sarda. Smoothing splines estimators for functional linear regression. In: The Annals of Statistics 37.1 (2009), pp. 35–72 (cit. on p. 17).
[Cla36]
James A. Clarkson. Uniformly Convex Spaces. In: Transactions of the American Mathematical Society 40.3 (1936), pp. 396–414 (cit. on p. 53).
[Cov65]
Thomas M. Cover. Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition. In: IEEE Transactions on Electronic Computers EC-14.3 (1965), pp. 326–334 (cit. on p. 28).
[DG23]
Mateo Dı́az and Benjamin Grimmer. Optimal Convergence Rates for the Proximal Bundle Method. In: SIAM Journal on Optimization 33.2 (2023), pp. 424– 454 (cit. on pp. 4, 28).
[DHP+12]
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In: ITCS ’12. 2012 (cit. on p. 17).
[DMM+17]
Santanu S Dey, Rahul Mazumder, Marco Molinaro, and Guanyi Wang. Sparse principal component analysis and its l 1-relaxation. In: arXiv preprint arXiv:1712.00800 (2017) (cit. on p. 3).
[DT09]
David L. Donoho and Jared Tanner. Counting the Faces of RandomlyProjected Hypercubes and Orthants, with Applications. In: Discrete & Computational Geometry 43.3 (2009), pp. 522–541 (cit. on p. 28).
[DT16]
Yoel Drori and Marc Teboulle. An Optimal Variant of Kelley’s Cutting-Plane Method. In: Mathematical Programming 160.1–2 (2016), pp. 321–351 (cit. on pp. 4, 27).
[ET96]
David E. Edmunds and Hans Triebel. Function Spaces, Entropy Numbers, Differential Operators. Vol. 120. Cambridge Tracts in Mathematics. Cambridge University Press, 1996 (cit. on p. 53).
[Gar88]
E. Gardner. The space of interactions in neural network models. In: Journal of Physics A 21 (1988), pp. 257–270 (cit. on p. 28).
[Gor99]
Geoffrey J. Gordon. Regret Bounds for Prediction Problems. In: Proceedings of the Twelfth Annual Conference on Computational Learning Theory. ACM, 1999, pp. 29–40 (cit. on p. 3).
[Guz15a]
Cristóbal Guzmán. “Information, Complexity and Structure in Convex Optimization”. PhD thesis. Georgia Institute of Technology, 2015 (cit. on pp. 2, 15, 27, 44).
[Guz15b]
Cristóbal Guzmán. Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings. In: Proceedings of The 28th Conference on Learning Theory. Ed. by Peter Grünwald, Elad Hazan, and Satyen Kale. Vol. 40. Proceedings of Machine Learning Research. Paris, France: PMLR, July 2015, pp. 1761–1763 (cit. on pp. 1–3, 15, 19, 26).
[HLO23]
Satoshi Hayakawa, Terry Lyons, and Harald Oberhauser. Estimating the Probability That a Given Vector Is in the Convex Hull of a Random Sample. In: Probability Theory and Related Fields (2023) (cit. on pp. 5, 28). 21
Martı́nez-Rubio Bullins* Guzmán* Molina*
[JMP+25]
Emmeran Johnson, David Martı́nez-Rubio, Ciara Pike-Burke, and Patrick Rebeschini. On the Necessity of Adaptive Regularisation: Optimal Anytime Online Learning on ℓp -Balls. In: Advances in Neural Information Processing Systems. Vol. 38. 2025 (cit. on p. 3).
[Kas77]
Boris S. Kashin. Diameters of Some Finite-Dimensional Sets and Classes of Smooth Functions. In: Mathematics of the USSR-Izvestiya 11.2 (1977), pp. 317–333 (cit. on p. 52).
[Kel60]
Jr. Kelley James E. The Cutting-Plane Method for Solving Convex Programs. In: Journal of the Society for Industrial and Applied Mathematics 8.4 (1960), pp. 703–712 (cit. on pp. 4, 27).
[KS94]
Michael J. Kearns and Robert E. Schapire. Efficient Distribution-Free Learning of Probabilistic Concepts. In: Journal of Computer and System Sciences 48.3 (1994), pp. 464–497 (cit. on pp. 2, 26).
[KV03]
Adam Kalai and Santosh S. Vempala. Efficient Algorithms for Online Decision Problems. In: Learning Theory and Kernel Machines. Vol. 2777. Lecture Notes in Computer Science. Springer, 2003, pp. 26–40 (cit. on p. 3).
[KV20]
Marta Kossaczká and Jan Vybı́ral. Entropy numbers of finite-dimensional embeddings. In: Expositiones Mathematicae 38.3 (2020), pp. 319–336 (cit. on pp. 26, 47).
[KZ20]
Zakhar Kabluchko and Dmitry Zaporozhets. Absorption Probabilities for Gaussian Polytopes and Regular Spherical Simplices. In: Advances in Applied Probability 52.2 (2020), pp. 588–616 (cit. on p. 28).
[Lan15]
Guanghui Lan. Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization. In: Mathematical Programming 149.1– 2 (2015), pp. 1–45 (cit. on pp. 4, 27).
[Lit87]
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. In: 28th Annual Symposium on Foundations of Computer Science (sfcs 1987). 1987, pp. 68–77 (cit. on pp. 27, 28).
[LNN95]
Claude Lemaréchal, Arkadii Nemirovskii, and Yurii E. Nesterov. New variants of bundle methods. In: Math. Program. 69 (1995), pp. 111–147 (cit. on p. 4).
[LY14]
Zhenxia Liu and Xiangfeng Yang. Probabilities of Hitting a Convex Hull. In: Comptes Rendus. Mathématique 352.11 (2014), pp. 935–940 (cit. on pp. 5, 28).
[Mal09]
Stéphane Mallat. A Wavelet Tour of Signal Processing (Third Edition). In: Academic Press, 2009 (cit. on p. 18).
[McM17]
H. Brendan McMahan. A Survey of Algorithms and Analysis for Adaptive Online Learning. In: Journal of Machine Learning Research 18.90 (2017), pp. 1– 50 (cit. on p. 3).
[MPR05]
Shahar Mendelson, Alain Pajor, and Mark Rudelson. The Geometry of Random {−1, 1}-Polytopes. In: Discrete & Computational Geometry 34.3 (2005), pp. 365–379 (cit. on p. 27). 22
[MS04]
Shahar Mendelson and Gideon Schechtman. The Shattering Dimension of Sets of Linear Functionals. In: The Annals of Probability 32.3A (2004), pp. 1746– 1770 (cit. on pp. 27, 44, 49).
[Nes04]
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Vol. 87. Applied Optimization. Springer, 2004 (cit. on p. 1).
[Nes09]
Yurii Nesterov. Primal-Dual Subgradient Methods for Convex Problems. In: Mathematical Programming 120.1 (2009), pp. 221–259 (cit. on p. 3).
[NY83]
Arkadi S. Nemirovski and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. New York: Wiley, 1983 (cit. on pp. 1–3, 6, 8, 26, 27).
[Pis89]
Gilles Pisier. The Volume of Convex Bodies and Banach Space Geometry. Vol. 94. Cambridge Tracts in Mathematics. Cambridge University Press, 1989 (cit. on p. 47).
[ROF92]
L I Rudin, S Osher, and E Fatemi. Nonlinear total variation based noise removal algorithms. In: Physica D: Nonlinear Phenomena 60.1-4 (1992), pp. 259–268 (cit. on p. 3).
[RS05]
James O. Ramsay and Bernard Walter Silverman. Functional Data Analysis. In: Springer Series in Statistics. 2005 (cit. on p. 17).
[RSS12]
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Relax and Localize: From Value to Algorithms. In: CoRR abs/1204.0870 (2012) (cit. on p. 4).
[RST10]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. In: Advances in neural information processing systems 23 (2010) (cit. on pp. 4, 9, 26).
[RST11]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Beyond regret. In: Proceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 2011, pp. 559–594 (cit. on pp. 4, 11, 12, 26, 29).
[RST15a]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. In: The Journal of Machine Learning Research 16.1 (2015), pp. 155–186 (cit. on pp. 3, 9, 14, 26, 31).
[RST15b]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential Complexities and Uniform Martingale Laws of Large Numbers. In: Probability Theory and Related Fields 161.1–2 (2015), pp. 111–153 (cit. on pp. 7, 26, 27, 36, 45).
[SAH20]
Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The Performance Analysis of Generalized Margin Maximizers on Separable Data. In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, July 2020, pp. 8417–8426 (cit. on p. 28).
[Sch84]
Carsten Schütt. Entropy numbers of diagonal operators between symmetric Banach spaces. In: Journal of Approximation Theory 40.2 (1984), pp. 121–128 (cit. on p. 47). 23
Martı́nez-Rubio Bullins* Guzmán* Molina*
[Sha07]
Shai Shalev-Shwartz. “Online Learning: Theory, Algorithms and Applications”. PhD thesis. Hebrew University of Jerusalem, Israel, 2007 (cit. on p. 3).
[Sho64]
Naum Z. Shor. “On the structure of algorithms for numerical solution of problems of optimal planning and design”. Doctoral Dissertation (Doctor of Philosophy). PhD thesis. Kiev: Cybernetics Institute, Academy of Sciences of the Ukrainian SSR, 1964 (cit. on p. 8).
[Sio58]
Maurice Sion. On general minimax theorems. en. In: Pacific Journal of Mathematics 8.1 (Mar. 1958), pp. 171–176. issn: 0030-8730, 0030-8730 (cit. on p. 11).
[Sri12]
Karthik Sridharan. “Learning From An Optimization Viewpoint”. PhD thesis. Toyota Technological Institute at Chicago, 2012 (cit. on pp. 1–3, 15, 19, 26).
[SS07]
Shai Shalev-Shwartz and Yoram Singer. A Primal-Dual Perspective of Online Learning Algorithms. In: Machine Learning 69.2–3 (2007), pp. 115–142 (cit. on p. 3).
[SS12]
Nathan Srebro and Karthik Sridharan. On Convex Optimization, Fat Shattering and Learning. 2012 (cit. on pp. 2, 7, 16, 26, 27).
[SST11]
Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the Universality of Online Mirror Descent. In: Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain. Ed. by John Shawe-Taylor, Richard S. Zemel, Peter L. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger. 2011, pp. 2645–2653 (cit. on p. 2).
[ST02]
Maria Shcherbina and Brunello Tirozzi. On the volume of the intersection of a sphere with random half spaces. en. In: Comptes Rendus. Mathématique 334.9 (2002), pp. 803–806 (cit. on p. 28).
[ST03]
Mariya Shcherbina and Brunello Tirozzi. Rigorous solution of the Gardner problem. In: Communications in mathematical physics 234.3 (2003), pp. 383– 422 (cit. on p. 28).
[ST10]
Karthik Sridharan and Ambuj Tewari. Convex Games in Banach Spaces. In: Proceedings of the 23rd Annual Conference on Learning Theory. 2010, pp. 1– 13 (cit. on pp. 3, 4).
[Sto13]
Mihailo Stojnic. Another look at the Gardner problem. 2013 (cit. on p. 28).
[Tik23]
Konstantin Tikhomirov. On the probability that convex hull of random points contains the origin. 2023 (cit. on p. 28).
[vdVW96]
A. W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. In: Springer Series in Statistics. 1996 (cit. on p. 54).
[War98]
Manfred K Warmuth. Continuous and discrete time nonlinear gradient descent: relative loss bounds and convergence. In: Electronic Proceedings of Fifth International Symposium on Artificial Intelligence and Mathematics, 1998. 1998 (cit. on p. 3). 24
[Wen62]
James G. Wendel. A Problem in Geometric Probability. In: Mathematica Scandinavica 11 (1962), pp. 109–112 (cit. on pp. 1, 5, 12, 13, 28).
[WHG+22]
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Sequential vs. Fixed Design Regrets in Online Learning. In: 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 438–443 (cit. on p. 27).
[WW01]
Uli Wagner and Emo Welzl. A Continuous Analogue of the Upper Bound Theorem. In: Discrete & Computational Geometry 26.2 (2001), pp. 205–219 (cit. on p. 28).
[Zin03]
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the Twentieth International Conference on International Conference on Machine Learning. ICML’03. Washington, DC, USA: AAAI Press, 2003, pp. 928–935. isbn: 1577351894 (cit. on p. 3).
25
Martı́nez-Rubio Bullins* Guzmán* Molina*
Appendix A. Further Related Work Prior open questions. Guzmán [Guz15b] asked for the large-scale minimax risk of blackbox convex minimization over ℓp -balls when regularity is measured in a different ℓq -norm, and whether the rate of the standard ℓq /ℓq method can be improved by exploiting the geometry of the smaller feasible set. Our results answer this question at the κ = 1 endpoint. The case κ → 1 is identified there with the nonsmooth Lipschitz limit. Our first reduction in Proposition 5 uses a direct conditional-mean argument, motivated by the triplex framework of Rakhlin, Sridharan, and Tewari [RST11], who give a general framework for non-standard notions of regret in which the learner’s losses and the benchmark may be aggregated in ways other than addition. In our setting, the benchmark is a maximum over losses. Ordinary √ online convex optimization, with regret against the sum of losses, is already pinned to the T cumulative scale in worst case. This is visible through the online convex optimization reduction of RST15; a, Lemma 13, the sequential-Rademacher upper bound of RST15; b, Proposition 16, and the matching lower-bound phenomena in Cheng, Duchi, and Levy [CDL25, Lemma 3 and Theorem 5]. The sequential entropy step uses the sequential covering and fat-shattering machinery of Rakhlin, Sridharan, and Tewari [RST15a]. In particular, their Proposition 9 gives a lower bound in terms of sequential fatshattering for supervised absolute loss. Our lower bound in terms of fat-shattering is for the value of the max-regret game and although its analysis differs from any prior work, the final result should be viewed as an analog of (RST15a, Proposition 9) for our setting, in terms of its shape. The relationship between convex optimization and fat-shattering goes back to the lowerbound construction of Nemirovski and Yudin [NY83, Section 4.4.2]. Srebro and Sridharan [SS12] observed that this construction yields an oracle-complexity lower bound controlled by the fat-shattering dimension of the associated linear class. The open question in Sridharan [Sri12, Section 10.1.2] asks, in this spirit, whether the offline oracle complexity can always be upper bounded by the fat-shattering dimension of the associated linear class, and whether such a bound can be achieved by an optimization algorithm. That is, in our notation, whether there is c such that if T is the minimum iteration count such that EX ,H (T ) ≤ ε then T ≤ fatcε (LX ,H ). Taken literally, such a bound cannot work in low dimensions, as oracle lower bounds of order d log(1/ε) are known (NY83, Chapter 4) while fat-shattering contributes only the d-scale. One may instead ask for the right statement up to logarithmic factors. Our contribution to the question is to show exactly that bound when using the sequential fat-shattering dimension instead, in cases where it decays according to the polynomial rate in Theorem 10. Upper bounds and sequential fat-shattering As explained before the Triplex inequality of (RST11) was a source of inspiration for our upper bounds, after realizing the max-regret would be a useful object of study for this problem. In the nondual settings, upper bounds depended on sequential fat-shattering bounds for classes of linear functions in mixed geometries, which were not know before to the best of our knowledge. The geometric part about characterizing sequential fat-shattering up to log factors in the (p, q)-norm case is close in spirit to classical entropy estimates for ℓdp → ℓds embeddings, including Schütt’s bounds and the sparse-vector proofs surveyed in Kossaczká and Vybı́ral [KV20, Theorem 2(a), Section 3]. Fat-shattering was introduced by Kearns and Schapire [KS94], whereas Rakhlin, 26
Sridharan, and Tewari [RST10] introduced the sequential fat-shattering dimension. The martingale complexity framework of RST15; b, Proposition 16 gives sfatα (Ls,s∗ ) for s ≥ 2. To the best of our knowledge, the general p, q case was not previously known. In general, sfat and fat can be very far apart: in the binary case this is the familiar gap between Littlestone and VC dimensions (Lit87), and Wu et al. [WHG+22] exhibit corresponding separations between fat and sfat for specific hypothesis classes; namely, for sequential prediction of linear threshold functions under log-loss. For the linear classes studied in this work, by contrast, our bounds show that fat and sfat are the same up to logarithmic factors. Lower bounds and fat shattering The systematic study of lower bounds in first-order oracle models begins with Nemirovski and Yudin (NY83), who formalized local oracles and developed resisting-oracle constructions for the dual case. A later observation of Srebro and Sridharan [SS12, Theorem 1] was that the same construction gives a lower bound of fat2ε (LX ,H ) for the oracle complexity over X for convex functions with subgradients in H. The values of fat-shattering dimension were studied up to constants in Mendelson and Schechtman [MS04], which gave tight upper and lower bounds in several regimes and partial estimates in others. Guzmán [Guz15a] provided lower bounds for convex Lipschitz optimization for all p, q and although it was not noted in that work, the construction automatically serves for showing tight lower bounds for fat-shattering for all p, q, up to constants when (p, q) ̸= (1, 1), and logarithmic factors at (1, 1), improving over Mendelson and Schechtman [MS04] in their missing case. In fact, the tightness is implied by matching oracle complexity upper bounds from mirror descent for this case q < 2 < p, which provides a proof that the lower bound on fat-shattering is tight. Thus, even though the pieces were not previously put together, for (p, q) ∈ / {(1, 1), (∞, ∞)} and on the nontrivial scales it is known that 1 − min α p1 −( 1q − 12 )+ , d , p < q, fatα (Ldp,q∗ ) ≍p,q (11) n o min d1/q−1/p /α max{q,2} , d , p ≥ q, (p, q) ∈ / {(1, 1), (∞, ∞)}. At (p, q) = (1, 1), the results of Mendelson, Pajor, and Rudelson [MPR05, Corollary 2.3 and Theorem 3.1] give the sharp characterization log(2 + dα2 ) d fatα (L1,∞ ) ≍ min d, , 0 < α ≤ 1. (12) α2 And finally, it is fatα (Ld∞,1 ) = d if 0 < α ≤ 2 and 0 otherwise. In all cases, the minimum with d is the finite-dimensional cutoff, cf. Anthony and Bartlett [AB99, Section 11]. Note that a simple consequence of the definition of fatα for any class, is that it increases when alpha decreases and it tends to the pseudodimension of the class (AB99, Section 11.3) when α → 0, which is a real-valued function generalization of the VC-dimension. Bundle methods The following is a non exhaustive discussion on the bundle-method literature. To the best of our knowledge, the first bundle method is from Kelley [Kel60]. Drori and Teboulle [DT16] concerns a modified version of it, rather than the unstabilized method original method. Bundle-level methods attain the same optimal nonsmooth rate (Lan15) and can adapt to smoothness and be universal. The proximal-bundle analysis of 27
Martı́nez-Rubio Bullins* Guzmán* Molina*
Dı́az and Grimmer [DG23] recovers this rate and adapts to additional smoothness or growth assumptions. Ben-Tal and Nemirovski [BN05] designed bundle methods for non-Euclidean geometries, matching the rates of mirror descent methods. Approximation of a convex hull of samples to its mean The classical Wendel Theorem (Wen62) provides an exact formula for the probability that the origin lies in the convex-hull of n vectors drawn i.i.d. from a centrally symmetric distribution in general position and in particular there is a sharp transition at Θ(d) samples. We study a more quantitative margin version guarantee, in the different setting of considering general distributions. A few, but limited, quantitative variants of the Wendel’s theorem have been studied in a specific cases, such as Liu and Yang [LY14], who treat the uniform distribution and Euclidean distance. Hayakawa, Lyons, and Oberhauser [HLO23] obtain distributiondependent quantitative extensions of Wendel’s theorem, controlling the probability that a point lies within distance ε of the convex hull of iid samples. Their results concern Euclidean geometries and primarily the post-dimensional regime. Notable applications of the Wendel Theorem include learning theory, as we discuss below, and compressed sensing: Donoho and Tanner [DT09] use it to show sharp transitions on the recovery of sparse vectors under random linear measurements. There is a broad literature on Wendel-type containment and absorption probabilities (WW01; KZ20; HLO23; Tik23). To the best of our knowledge, these works mostly concern the regime in which the number of samples is at least the ambient dimension, whereas our bounds are most informative in the early-time regime T < d and provide a more robust margin guarantee depending on a norm of choice. The ideas behind Wendel’s Theorem have been systematically applied to the study of linear (and nonlinear) data separability, starting from the work of Cover [Cov65]. In this regard, quantitative versions of Wendel’s theorem as studied in our work are directly related to margin conditions, which are relevant for machine learning and statistical physics. For example, the Gardner problem in statistical physics asks precisely for margin conditions on randomly drawn (Gaussian) vectors (Gar88; ST02; ST03; Sto13). There are also well known connections between margin conditions in different norms and guarantees for offline and online learning (Lit87; SAH20).
Appendix B. Proofs for the Online-Learning Reduction Proof of Proposition 5. For each realized past, write E′t for the conditional expectation over independent draws x′t ∼ st and ℓ′t ∼ rt : E′t F (x′t , ℓ′t ) := Ex′t ∼st F (x′t , ℓ′t ) | x1:t−1 , ℓ1:t−1 . ℓ′t ∼rt
These draws are used only inside the conditional expectation; future distributions depend on the realized, unprimed history. 28
Using Assumption 3 gives 1 . Adding and subtracting the conditional expectations and splitting supu gives 2 : VXmax ,H,T
T
1 =
sup
sup inf Ext ∼st rt
st
ℓt ∼rt
t=1 u∈X
st
+ sup
ℓt ∼rt
( T X
u∈X
) ℓt (xt ) − T max ℓt (u) t∈[T ]
t=1
" T X
T 2 ≤ sup inf Ext ∼st rt
( T X
(ℓt (xt ) − E′t ℓ′t (x′t )) + sup u∈X t=1
t=1
( T X
) E′t (ℓ′t (x′t ) − ℓ′t (u))
t=1
)# E′t ℓ′t (u) − T max ℓt (u)
.
t∈[T ]
t=1
We break this expression into three terms in the spirit of the Triplex Inequality (RST11, Theorem 1), allowing different loss aggregations for the player and comparator. Using linearity of expectation and, at each infimum, inf [C1 (a) + C2 (a) + C3 (a)] ≤ sup C1 (a) + inf C2 (a) + sup C3 (a), a
a
a
a
we obtain VXmax ,H,T ≤
( T X
T
sup sup Ext ∼st rt
ℓt ∼rt
st
t=1
T + sup inf Ext ∼st rt
st
ℓt ∼rt
st
ℓt ∼rt
t=1
sup
( T X
t=1 u∈X
T + sup sup Ext ∼st rt
) (ℓt (xt ) − E′t ℓ′t (x′t ))
sup
t=1 u∈X
) E′t (ℓ′t (x′t ) − ℓ′t (u))
t=1
( T X t=1
) E′t ℓ′t (u) − T max ℓt (u) t∈[T ]
.
The first term is zero by the tower property, since E′t ℓ′t (x′t ) = E[ℓt (xt ) | x1:t−1 , ℓ1:t−1 ]. For the second term, fix η > 0. Since rt is announced before st in the minimax-swapped game, choose st as the pure strategy of playing a measurable η-optimal point of inf Eℓ′t ∼rt (·|x1:t−1 ,ℓ1:t−1 ) ℓ′t (x).
x∈X
Then E′t (ℓ′t (x′t ) − ℓ′t (u)) ≤ η for every u ∈ X along every realized path, so the second term is at most T η. In the third term, the payoff depends only on the chosen loss kernels and sampled losses. Player actions only provide auxiliary randomness for choosing future kernels. By backward induction, averaging over these actions cannot exceed the best continuation, so their distributions can be replaced by deterministic choices. For any fixed resulting strategy, those choices can be reconstructed from the loss history. Hence R the kernels may be written as rt (· | ℓ1:t−1 ). Finally, substituting the notation E′t ℓ′t (u) = ℓ(u) rt (dℓ | ℓ1:t−1 ) = mt (u) and letting η ↓ 0 proves the claim.
Appendix C. Proof of Theorem 10: Sequential Bounds It will be useful for a tight characterization of the max-regret to establish lower bounds in terms of the sequential fat-shattering dimension, as we show next. 29
Martı́nez-Rubio Bullins* Guzmán* Molina*
Proposition 16 (Lower bound)
Under Assumption 3, for every α > 0, VXmax α sfatα (LX ,H ) ,H,T ≥ ∧1 . T 2 T
Proof Fix α > 0 and set m := min{sfatα (LX ,H ), T }. If m = 0, the right-hand side is zero, and the identically zero adversarial strategy shows m that VXmax ,H,T ≥ 0. Hence, suppose m ≥ 1. Fix a depth-m predictable tree (gt )t=1 over H and m a threshold tree (st )t=1 that are sequentially α-shattered by LX ,H . This class is bounded in [−ΛX ,H , ΛX ,H ]. Since both children of every shattered node are realizable, −ΛX ,H +
α α ≤ st ≤ ΛX ,H − . 2 2
In particular, α/2 ≤ ΛX ,H . Let ε1 , . . . , εm be iid Rademacher signs and set ( −εt gt (ε<t ), εt st (ε<t ) , t ≤ m, (Gt , Bt ) := (0, −α/2), m < t ≤ T,
Yt = (Gt , Bt ).
The symmetry assumption H = −H ensures that Gt ∈ H for t ≤ m, and convexity and symmetry give 0 ∈ H on the padded rounds. The bounds above give Bt ∈ [−ΛX ,H , ΛX ,H ] in both cases. Hence Yt ∈ ZX ,H , so this is an admissible adaptive adversarial strategy. For t ≤ m, the sign εt is independent of the past and has mean zero; for t > m, Yt is deterministic. Therefore ( 0, t ≤ m, µt = E[Gt | Y1:t−1 ] = 0, βt = E[Bt | Y1:t−1 ] = −α/2, m < t ≤ T. Using the witnesses uε from Definition 1, for t ≤ m we have −⟨Gt , uε ⟩ − Bt = εt (⟨gt (ε<t ), uε ⟩ − st (ε<t )) ≥
α . 2
For t > m, the left-hand side equals α/2. Moreover, P against this fixed adversarial strategy, every player strategy has expected cumulative loss Tt=1 βt = −(T − m)α/2. Therefore, after using Assumption 3, we lower bounding the minimax value by the one for our specific adversarial strategy and obtain: VXmax (T − m)α ,H,T ≥ E sup − + min −⟨Gt , u⟩ − Bt T 2T t∈[T ] u∈X (T − m)α ≥− + E min −⟨Gt , uε ⟩ − Bt 2T t∈[T ] (T − m)α α mα ≥− + = . 2T 2 2T Substituting the definition of m proves the claim. 30
The proof of Theorem 10 will use several lemmas that can be found after the proof. Proof of Theorem 10. The lower bound is Proposition 16. For the upper bound, write e := Λ−1 H. Scaling every affine loss by 1/Λ gives Λ := ΛX ,H and H max VXmax = ΛV , sfat L α e = sfatΛα (LX ,H ) . ,H,T e X ,H X ,H,T It therefore suffices to prove the normalized upper bound when Λ = 1, which we assume below. In this normalization, recall the body-indexed version of the offset envelope class from Definition 21: ⟨g, u⟩ + b Φ ◦ ( 21 AX ,H ) := (g, b) 7→ ϕ : u ∈ X, ϕ ∈ Φ . 2 Fix 0 < α ≤ 1. We obtain, for every adaptive adversarial strategy π: " # T T 1 1X 2X Eπ [GX ,H,T (Y1:T )] ≤ 2 Eπ sup Pt f − f (Yt ) T T 1 f ∈Φ◦( 2 AX ,H )
t=1
t=1
Z 1 2 C seq 1 ≤ Cα + 1+ log N∞ (coff β, Φ ◦ ( 2 AX ,H ), 2T ) dβ T α Z 1 Z 3 C 17 log 5 1 dβ seq ≤ Cα + 1+ log N∞ (coff β/4, LX ,H , 2T ) dβ + T coff α α β Z 1 4 C eT e ≤ Cα + 1 + log + sfatcβ (LX ,H ) logγ dβ . T α β α Where above, 1 uses Lemma 18, and 2 uses Proposition 20 with Z = ZX ,H and C = Φ ◦ ( 21 AX ,H ), writing coff for the scale constant in that proposition. We obtain 3 using Lemma 22 to make sfat of the linear class LX ,H appear as opposed to the one of the affine R1 class, decreasing coff if necessary so it is in (0, 1]. Finally, in 4 , we used α β −1 dβ ≤ log(e/α), the bound of sequential covering numbers by sfatcβ from (RST15a, Corollary 1), and we renamed coff /4 as the universal scale constant c. The deterministic-domination and affine-entropy proofs use only the normalized range bound and therefore apply verbatim to (X , H). The right-hand side does not depend on the adversarial strategy π. Hence, for every ε > 0, choosing an ε-optimal history-dependent adversarial strategy π ε for the nested problem yields VXmax ,H,T ≤ Eπε GX ,H,T (Y1:T ) + ε. T Letting ε ↓ 0 and then taking the infimum over 0 < α ≤ 1 proves the normalized upper bound. Multiplying it by Λ, substituting α′ = Λα and β ′ = Λβ, and then dropping the primes gives the stated upper bound for (X , H). High-dimensional instantiation in the (p, q) case. When T ≤ d, the endpoint p = q = ∞ follows by choosing α = 1 in the inf of the upper bound, combining the endpoint case of Theorem 12 with Proposition 16. For proving the remaining regimes, we study the general case where sfatα decays like α−r for r ≥ 1. 31
Martı́nez-Rubio Bullins* Guzmán* Molina*
In particular, for the remaining regimes with p ≤ q, write r :=
1 p −
−1
1 1 q − 2 +
, so
that T −1/r = T −(1/p−(1/q−1/2)+ ) . The class Ldp,q∗ is exactly the linear class whose sequential fat-shattering dimension is characterized in Theorem 12. The upper side of that result gives ed d −r 1 + log+ , 0 < β ≤ 1. sfatβ (Lp,q∗ ) ≤ Cp,q β β Substituting this estimate into the upper bound proved above gives ( ) Z max Vp,q ∗ ,T Cp,q 1 −r ed eT C e C β 1 + log+ logγ dβ . ≤ inf Cα + log + + 0<α≤1 T T α T T α β β First suppose r = 1. Choose α = T −1 . Then ed eT 1 + log+ ≤ C log(edT ), log ≤ C log(eT ) β β
(T −1 ≤ β ≤ 1),
and therefore for a constant Cp,q,γ : max Vp,q ∗ ,T
T
Z 1 Cp,q,γ C C 1 γ eT ≤ + log(eT ) + log(edT ) log dβ T T T β T −1 β Cp,q,γ C C 1 γ+1 e ≤ + log(eT ) + log(edT ) log (eT ) = O . T T T T 1/r
This is the asserted bound when r = 1. Now suppose r > 1. If T = 1, the claim is trivial after increasing the constant, so assume T ≥ 2. For every α ≥ T −1 , Z 1 ed −r γ eT β 1 + log+ log dβ ≤ Cr,γ α1−r log(edT ) logγ (eT /α). β β α Thus max Vp,q ∗ ,T
Cp,q,r,γ 1−r C e C Cα + log + + α log(edT ) logγ (eT /α) T T α T T T −1 <α≤1 1 log(edT ) logγ (eT ) 1/r C ≤ Cp,q,r,γ + log(eT ) T T 1 e =O . T 1/r 1/r log(edT ) logγ (eT ) where 1 uses α = min 1, > T1 , since if the minimum is attained at T ≤
inf
1, the displayed claim is trivial after increasing the constant. Otherwise, this choice satisfies log(eT /α) ≤ Cr log(eT ). For the lower bound, it is enough that the first term in Theorem 12 be active, up to constants, at some scale α ≍ T −1/r ; thus T ≤ d is sufficient but not necessary. Indeed, set 32
αT := T −1/r . At this scale, the first term in that corollary equals T , while its saturated term equals d when T ≤ d, because αT d1/r = (d/T )1/r ≥ 1. Hence, for some cp,q > 0, sfatαT (Ldp,q∗ ) ≥ cp,q T. By Proposition 16, max Vp,q ∗ ,T
T
αT ≥ 2
sfatαT (Ldp,q∗ ) ∧1 T
! ≥
cp,q ∧ 1 , 2T 1/r
which is the stated lower bound after renaming the constant. Now we prove the remaining lemmas needed in the proof of Theorem 10. In order to do that, we only require the next lemma to apply conditional pushforwards along a fixed realized adaptive path. However, we show something more general without assuming any joint sampling or coupling of the measures. Let Q1 , . . . , QT Rbe probability measures on [−1, 1], with distribution functions F1 , . . . , FT and means mt := z dQt (z). Let z1 , . . . , zT ∈ [−1, 1] be arbitrary points. Define T
m̄ :=
T
1X mt , T
F̄ (a) :=
t=1
1X Ft (a), T
2 Fb(a) := T
t=1
T X
1{zt ≤a} .
t=1
Also define the capped simplex (2) ∆T :=
2 λ ∈ ∆T : λt ≤ for every t . T
Lemma 17 (One-dimensional capped domination) With the notation above and Φ as in Definition 21, " # T T Z T X 1X 2X m̄ − max λt zt ≤ sup ϕ dQt − ϕ(zt ) . (2) T ϕ∈Φ T λ∈∆ T
t=1
t=1
t=1
P ν has total mass 2. Maximizing Tt=1 λt zt Proof Let ν := 2T t=1 δzt . The measure R (2) over λ ∈ ∆T is equivalent to maximizing z dθ(z) over all submeasures θ ≤ ν with total mass 1, where θ being a submeasure of ν means that θ(A) ≤ ν(A) for every measurable set A. The maximizing submeasure fills mass from the largest observed points downward. If G denotes its distribution function, then G(a) = Fb(a) − 1 + . P Let Q̄ := T −1 Tt=1 Qt . Then Q̄ has distribution function F̄ and mean m̄. For any probabilR R1 ity measure γ on [−1, 1] with distribution function Gγ , we have z dγ(z) = 1− −1 Gγ (a) da. Therefore Z Z 1 Z 1 T X m̄ − max λt zt = m̄ − z dθ(z) = 1 − F̄ (a) da − 1 − G(a) da PT −1
(2)
λ∈∆T
−1
t=1
Z 1 =
G(a) − F̄ (a) da ≤
−1
Z 1 −1
33
−1
Fb(a) − F̄ (a) − 1 + ,
Martı́nez-Rubio Bullins* Guzmán* Molina*
where the inequality follows from G(a) = (Fb(a) − 1)+ and F̄ (a) ≥ 0.R It remains to idenz tify the last integral. Every ϕ ∈ Φ admits a representation ϕ(z) = −1 h(a) da for some measurable h : [−1, 1] → [0, 1]. Conversely, every such h defines a function in Φ. Hence Z 1
Z ϕ dQt =
Z 1
h(a) 1 − Ft (a) da,
and
−1
ϕ(zt ) = −1
h(a)1{a≤zt } da.
Therefore T
1X T t=1
Z
T
2X ϕ(zt ) = ϕ dQt − T
Z 1
h(a) Fb(a) − F̄ (a) − 1 da.
−1
t=1
Taking the supremum over measurable h : [−1, 1] → [0, 1] gives the positive part integral, and therefore the claim. Now fix a realized path yt = (gt , bt ) ∈ ZX ,H , t = 1, . . . , T , and the corresponding kernels Pt (· | y1:t−1 ). Lemma 18 (Convex hull-distance bound by capped-simplex process) Suppose that ΛX ,H = 1. For every realized path, " GX ,H,T (y1:T ) ≤ 2
sup 1 f ∈Φ◦( 2 AX ,H )
# T T 1X 2X Pt f − f (yt ) . T T t=1
t=1
Above, the function class in the supremum is defined in Definition 21. Proof Fix u ∈ X and define ztu := ⟨gt , u⟩ + bt . Its predictable mean is Z (⟨g, u⟩ + b) dPt (g, b | y1:t−1 ) = ⟨µt , u⟩ + βt , mut := ZX ,H
where we abbreviate µt = µt (y1:t−1 ) and βt = βt (y1:t−1 ). Since ΛX ,H = 1, we have |⟨gt , u⟩| ≤ 1. Together with bt ∈ [−1, 1], this gives ztu ∈ [−2, 2]. Let Qut be the pushforward of Pt (· | y1:t−1 ) under ⟨g, u⟩ + b (g, b) 7→ . 2 Then Qut is supported on [−1, 1] and has mean mut /2. Therefore, T T T T X X 1X u 1X u mt − max λt ztu ≤ mt − max λt ztu (2) λ∈∆T T T λ∈∆T t=1 t=1 t=1 t=1 " # T T X 1 X mut ztu =2 − max λt (2) T 2 2 λ∈∆T t=1 t=1 " # T T 1 ⟨·, u⟩ + · ⟨gt , u⟩ + bt 1X 2X ≤ 2 sup Pt ϕ − ϕ . 2 T 2 ϕ∈Φ T t=1
t=1
34
Here 1 applies Lemma 17 to Qu1 , . . . , QuT and z1u /2, . . . , zTu /2. Taking the supremum over u ∈ X proves the claim. We first control the offset process for a finite class of pair-trees (trees that have a pair of numbers at each node), and then apply this estimate scale by scale to sequential covers in the chaining argument. Lemma 19 (Finite-class offset estimate) Let b > 0, and let A be a finite nonempty + family of nonnegative pair-trees a = at (ε1:t−1 ), a− t (ε1:t−1 ) t≤T with values in [0, b]. For Ma (ε) :=
T X −εt at (ε1:t−1 ) − 2aεt t (ε1:t−1 )
we have
t=1
1 4b Eε sup Ma (ε) ≤ 1+log |A| . T a∈A T + (13)
Proof Indeed, fix a ∈ A. Conditionally on ε1:t−1 , write r = r, s ∈ [0, 1]. For a sufficiently small universal λ > 0,
a− a+ t (ε1:t−1 ) t (ε1:t−1 ) , s = . Then b b
1 λ(s−2r) 1 λ(r−2s) e + e ≤ 1. 2 2 Indeed, for fixed s, the left-hand side is convex in r, so its maximum over r ∈ [0, 1] is attained at r = 0 or r = 1. For each of these two choices, the resulting function of s is again convex, so it is enough to check the four corners of [0, 1]2 . The claim holds, for example, for λ = 1/4. Therefore Eε exp(λMa (ε)/b) ≤ 1. Hence Pε (Ma (ε) > u) ≤ e−λu/b . By a union bound, Pε sup Ma (ε) > u
≤ min{1, |A|e−λu/b }.
a∈A
Writing N = |A| and integrating at the cutoff u0 = 4b log N gives Z ∞ Eε sup Ma (ε) ≤ u0 + N e−u/(4b) du = 4b(1 + log N ). a∈A
+
u0
Dividing by T proves the lemma. Assume that every h ∈ C is measurable and that C is pointwise measurable: there is a countable C0 ⊆ C such that every h ∈ C is the pointwise limit of a sequence in C0 . Thus the supremum below equals a countable supremum and is measurable. Since 0 ≤ h ≤ 2, the quantity inside the supremum lies in [−4, 2], so it is integrable without any further assumption. Proposition 20 (Sequential one-sided offset bound) Let Z be any measurable space and let C be a nonempty pointwise-measurable class of measurable functions Z → [0, 2]. For every adaptive strategy of kernels Pt (· | X1:t−1 ) supported on Z, and every 0 < δ ≤ 1, # Z T T 2X 16 48 1 1X seq E sup Pt h − h(Xt ) ≤ 4δ + + log N∞ (α/4, C, 2T ) dα, T T T δ h∈C T "
t=1
t=1
35
Martı́nez-Rubio Bullins* Guzmán* Molina*
Proof We use are going to use a sequential symmetrization technique, at the level of predictable trees. The inspiration is (RST15b) that also consider symmetrization for different adaptive processes. At every node of the adaptive process, draw two independent children from the distribution chosen at that node, obtaining a random pair-tree Z = Zt+ (ε1:t−1 ), Zt− (ε1:t−1 ) t≤T . For a sign path ε ∈ {±1}T , the selected point at time t is Ztεt (ε1:t−1 ), and the tangent ghost point is Zt−εt (ε1:t−1 ). Let Ft−1 be the sigma-field generated by the past signs and the sampled pairs along the selected path up to time t − 1, and write Pt for the kernel evaluated at the selected history. Then Pt h = E[h(Ztεt ) | Ft−1 ] = E[h(Zt−εt ) | Ft−1 ]. Conditionally on the entire selected path and the signs, each ghost point still has law Pt , since future selected points depend only on the selected history, not on the ghosts. The selected path has the law of X1:T , so conditional Jensen’s inequality gives: T T X X E sup (Pt h − 2h(Xt )) ≤ EZ,ε sup h(Zt−εt (ε1:t−1 )) − 2h(Ztεt (ε1:t−1 )) . h∈C t=1
h∈C t=1
We average over the random sign and the two terms always use different children of the same node. It remains to bound the right-hand side conditionally on Z for which we perform a chaining argument. The left-hand side of the proposition is at most 2. Hence the result is immediate when δ ≥ 1/2, and we assume below that 0 < δ < 1/2. Fix the pair-tree Z and fix 0 < δ ≤ 1. Let S := max{s ≥ 0 : 2−s ≥ δ},
αs := 2−s .
(14)
At scale αs , take a pair-tree sequential cover Vs of C at accuracy αs /2. A pair-tree of depth T can be encoded as an ordinary tree of depth 2T by listing, at each time t, first the “+” child and then the “−” child. Therefore we may choose Vs with seq log |Vs | ≤ log N∞ (αs /2, C, 2T ).
(15)
We also clip the cover trees to [0, 2], which does not increase the covering error. By Definition 2, the approximation guarantee is pathwise. Fix h ∈ C and a sign path ε. For each scale s, choose vs ∈ Vs approximating h along the path on both children. Define + the notation vs,t for the cover value approximating h(Zt+ (ε<t )), that is, the plus child of vs − at time t. Similarly vs,t for h(Zt− (ε<t )). We now bound both quantities at once using the ± notation vs,t . By definition of the covers at scales αr /2, along the chosen path we have the approximations ± ± ± 0 ≤ c± for all s. (16) s,t := max vr,t − αr /2 + ≤ h(Zt ) ≤ cs,t + αs 0≤r≤s
Define increments by ± g0,t := c± 0,t ∈ [0, 2],
n o ± ± and, for s ≥ 1, gs,t := min c± − c , α ∈ [0, αs−1 ]. s−1 s,t s−1,t 36
(17)
The truncation is needed only off the chosen path: it gives every possible increment tree the uniform envelope αs−1 required by the finite-class estimate in Lemma 19. Along the chosen path it is harmless, since ± ± ± c± s,t − cs−1,t ≤ h(Zt ) − cs−1,t ≤ αs−1
and so
c± S,t =
S X
± gs,t .
(18)
s=0
Using that by (14) we have δ ≤ αS < 2δ and using (16), we have ± ± c± S,t ≤ h(Zt ) ≤ cS,t + 2δ,
which along with (18), yields 1 below: " # T S T 1 X X 1 1 X h(Zt−εt ) − 2h(Ztεt ) ≤ 2δ + gt−εt (ε<t ) − 2gtεt (ε<t ) Eε sup Eε sup T g∈G h∈C T t=1 s s=0 t=1 + ! S s 2 X 8X ≤ 2δ + αs 1 + log |Vr | T s=0 r=0 " # S 3 X 16 ≤ 2δ + 1+ αs log |Vs | T s=0
Z 4 16 48 1 seq ≤ 2δ + + log N∞ (α/4, C, 2T ) dα. T T δ where in 2 , we used the envelopes in (17) and Lemma 19. For s = 0, the envelope 2 gives the factor 8/T = 8α0 /T . For s ≥ 1, the envelope αs−1 = 2αs gives 8αs /T P.s The possible increment pair-trees at level s form a finite class Gs satisfying log |Gs | ≤ r=0 log |Vr |. In P 3 we used that Ss=0 αs ≤ 2 and that with Ar = log |Vr |, we have S X s=0
αs
s X r=0
Ar =
S X r=0
Ar
S X
αs ≤
s=r
S X r=0
Ar
∞ X s=r
2−s = 2
S X
αr Ar .
r=0
Finally, in 4 we used the cover-size bound (15) and monotonicity of the covering numbers. Indeed, the term s = 0 is at most twice the integral over [1/2, 1] with covering scale α/4, while each term s ≥ 1 is at most the corresponding integral over [αs , αs−1 ]. Since S ≥ 1 and δ ≤ αS , their sum is at most three times the integral over [δ, 1]. Averaging over Z proves the proposition. Proof of Corollary 11. Finite-dimensional compact balls satisfy Assumption 3. Apply Lemma 4 to a minimax strategy for the max-regret game and output its average query. The rate is a consequence of Theorem 10. We do not seek a computationally efficient strategy in this paper, but a valid deterministic strategy can be obtained by taking sufficiently fine discretizations of the iterated decision spaces Bpd and Bqd∗ , using the Lipschitz continuity of max-regret, and solving the resulting max by enumeration. This discrete problem coming from the deterministic definition of Vp,q establishes first-order oracle efficiency, but the resulting computational time is exponential in d and T .
37
Martı́nez-Rubio Bullins* Guzmán* Molina*
C.1. Reducing the affine class to the linear one Here, we show that the covering number for the affine class is not much larger than the one for the linear class. Throughout this section, for simplicity, we assume that ΛX ,H = 1. Definition 21 (Offset envelope class) Define Φ := {ϕ : [−1, 1] → [0, 2] : ϕ(−1) = 0, ϕ ≥ 0, ϕ is nondecreasing and 1-Lipschitz} . The affine-composed class appearing in our analysis is defined as: ⟨g, u⟩ + b 1 : u ∈ X, ϕ ∈ Φ . Φ ◦ ( 2 AX ,H ) := (g, b) 7→ ϕ 2 Since |⟨g, u⟩| ≤ 1 and b ∈ [−1, 1], every argument of ϕ belongs to [−1, 1]. Therefore, every function in Φ ◦ ( 12 AX ,H ) is well-defined and bounded in [0, 2]. Lemma 22 (Affine offsets do not increase the sequential entropy) With Φ and Φ◦ ( 12 AX ,H ) as in Definition 21, for every n ≥ 1 and every 0 < α ≤ 1, 17 log 5 seq seq log N∞ α, Φ ◦ ( 12 AX ,H ), n ≤ log N∞ (α/4, LX ,H , n) + . α Proof Fix a depth-n tree z = (g, b),
zt (ε<t ) = (gt (ε<t ), bt (ε<t )) ∈ H × [−1, 1].
Let V be a sequential α/4-cover of the linear class LX ,H on the H-valued tree g. Clip every value of every tree in V to [−1, 1]; since the true linear evaluations lie in [−1, 1], this does not increase the covering error. We also use a uniform α/4-cover U of Φ in ℓ∞ ([−1, 1]), by real-valued functions on [−1, 1]. The construction is elementary. Put η = α/8, choose a grid 17 2 ≤ . −1 = t0 < t1 < · · · < tM = 1, tj − tj−1 ≤ η, M≤ η α For a given ϕ ∈ Φ, quantize each ϕ(tj ) to a nearest point aj ∈ ηZ, set ψ(−1) = a0 , and let ψ be constant equal to aj on (tj−1 , tj ] for 1 ≤ j ≤ M . Then ∥ϕ − ψ∥∞ ≤ η/2 + η ≤ α/4. Moreover a0 = 0, because ϕ(−1) = 0, and the 1-Lipschitz property gives |aj − aj−1 | ≤ |ϕ(tj ) − ϕ(tj−1 )| + η ≤ 2η. Thus, after aj−1 is fixed, aj has at most five possible successors, namely the admissible grid values in aj−1 + {−2η, −η, 0, η, 2η}. Since a0 = 0 is fixed, only a1 , . . . , aM contribute choices. Hence one may choose U with log |U| ≤ M log 5 ≤
17 log 5 . α
For each v ∈ V and ψ ∈ U, define a real-valued tree on z by vt (ε<t ) + bt (ε<t ) v,ψ wt (ε<t ) := ψ . 2 38
The collection of all such trees has cardinality at most |V||U|. Since vt ∈ [−1, 1] and bt ∈ [−1, 1], the argument of ψ belongs to [−1, 1]. Now fix u ∈ X , ϕ ∈ Φ, and the corresponding function ⟨g, u⟩ + b fu,ϕ (g, b) := ϕ ∈ Φ ◦ ( 12 AX ,H ). 2 Fix a root-to-leaf path ε. Since V covers the linear class, choose a tree v ∈ Vwhich approximates the linear function g 7→ ⟨g, u⟩ along this path: max |⟨gt (ε<t ), u⟩ − vt (ε<t )| ≤ α/4. t≤n
Choose ψ ∈ U with ∥ϕ − ψ∥∞ ≤ α/4. Along this path, abbreviating gt = gt (ε<t ), bt = bt (ε<t ), and vt = vt (ε<t ), ⟨gt , u⟩ + bt vt + b t ⟨gt , u⟩ + bt vt + b t ϕ −ψ ≤ ϕ −ϕ + ∥ϕ − ψ∥∞ 2 2 2 2 1 α 3α ≤ |⟨gt , u⟩ − vt | + ≤ ≤ α. 2 4 8 for every t ≤ n. Hence seq seq (α/4, LX ,H , g) |U |. N∞ α, Φ ◦ ( 12 AX ,H ), z ≤ N∞ Taking logarithms and then the supremum over z proves the claim.
Appendix D. Proofs for the iid case Proof of Lemma 6. Since the gradients are iid, the conditional means in (8) satisfy mt (u) = ⟨µP , u⟩. Consequently, the corresponding term divided by T is + * T X 1 E sup ⟨µP , u⟩ − max⟨Gt , u⟩ = E sup inf λt Gt − µP , u u∈X
2 = E inf sup λ∈∆T u∈X
= E dist
X◦
t≤T
u∈X λ∈∆T
* T X
+ λt Gt − µP , u
t=1
3 = E inf
t=1
λ∈∆T
T X t=1
λt Gt − µP X◦
µP , conv{G1 , . . . , GT } .
Here 1 renames u as −u (recall that X is symmetric) and writes the minimum as an infimum over the simplex, 2 is von Neumann’s minimax theorem, and 3 is the definition of the polar norm. The following proof is essentially the same as the one for Theorem 10, except that we exploit the iid case for obtaining bounds depending on fat instead of sfat. We are using the same structure of proof for simplicity, although the usage of the class Φ could likely be avoided. 39
Martı́nez-Rubio Bullins* Guzmán* Molina*
Proof of Theorem 7. The lower bound follows by taking the supremum over α > 0 in Proposition 24. For the upper bound, we may focus on zero-mean distributions. Indeed, for an arbitrary distribution P supported on H, convexity gives µP ∈ H, and hence (Gi − µP )/2 ∈ H. The law of these centered random vectors has mean zero, and distX ◦ (µP , conv{G1:T }) = 2 distX ◦ (0, conv{(Gi − µP )/2 : i ∈ [T ]}) . Thus a uniform bound for mean-zero distributions implies the desired bound after absorbing the factor of 2 into C and taking the supremum over P . e := Λ−1 H. Homogeneity gives Now let H wc ConvDistwc X ,H,T = ΛConvDistX ,H,T e ,
and
fatβ (LX ,H e ) = fatΛβ (LX ,H ).
It therefore suffices to prove the claim when Λ = 1. Assume this for the remainder of the argument. Accordingly, fix a distribution P supported on H with µP = 0. By Lemma 6, it remains to prove the centered estimate. Using the linear class in (5), write ℓ(g) 1 Φ ◦ 2 LX ,H := g 7→ ϕ : ℓ ∈ LX ,H , ϕ ∈ Φ , 2 P and set PbT f = T −1 Tt=1 f (Gt ). Fix 0 < α ≤ 1, let η = max{α, T −1 }, and write coff for the scale constant in the fixed-design chaining bound. Then E distX ◦ 0, conv{G1 , . . . , GT } 1 ≤ 2E
sup 1 f ∈Φ◦( 2 LX ,H )
P f − 2PbT f
Z 1 2 C 1 ≤ Cη + 1+ log N∞ coff β, Φ ◦ ( 2 LX ,H ), 2T dβ T η Z 1 Z 3 C 17 log 5 1 dβ ≤ Cη + 1+ log N∞ coff β/4, LX ,H , 2T dβ + T coff η η β Z 1 4 eT C ≤ Cα + 1+ fatcβ (LX ,H ) logγ dβ . T β α Here 1 applies Lemma 18 with bt = 0 and Pt = P . The fixed-design chaining argument in the proof of Proposition 23, before bounding covering numbers by fat-shattering dimension, gives 2 . Note these are non-sequential covering numbers. For 3 , the construction in the proof of Lemma 22, using ordinary fixed-design covers and setting the offset coordinate to zero, gives 17 log 5 log N∞ β, Φ ◦ ( 21 LX ,H ), n ≤ log N∞ β/4, LX ,H , n + . β Finally, 4 uses Anthony and Bartlett [AB99, Theorem 12.8], which bounds fixed-design ℓ∞ covering numbers by fat-shattering dimension up to logarithmic factors, together with η ≤ α+T −1 and monotonicity of the integral. We may take c ≤ 1 and γ ≥ 1. Choose g0 ∈ H 40
and u0 ∈ X that attain ΛX ,H = 1. By symmetry, g0 is β-shattered by LX ,H for 0 < β ≤ 2. Thus, when α ≤ 1/2, the integral over [1/2, 1] absorbs the term T −1 log(e/η) from the last integral in 3 . When α > 1/2, that term is absorbed by Cα. The deterministic and entropy arguments cited above use only convexity, symmetry, and the normalized range bound, so their proofs apply verbatim to LX ,H . Taking the infimum over α proves the normalized upper bound. Finally, multiply that bound by Λ, set α′ = Λα and β ′ = Λβ, and use the two homogeneity identities above. Dropping the primes gives the stated bound for (X , H).
The following proposition is an analogous result to Proposition 20 for the iid case, which is the only part where the analysis of the iid and the adaptive cases slightly differ, which makes fat appear in the former case as opposed to sfat in the latter. Proposition 23 (iid centered one-sided offset bound) Let Z ⊆ Rd be measurable, iid
let P be a probability distribution supported on Z with mean 0, and let G1 , . . . , GT ∼ P . Let C be a nonempty pointwise-measurable class of measurable functions Z → [0, 2], and R PT −1 b write P h := h dP and PT h := T t=1 h(Gt ). There are universal constants C, c, γ > 0 such that, for every 0 < δ ≤ 1, Z 1 C γ eT b E sup P h − 2PT h ≤ Cδ + 1+ fatcα (C) log dα . T α h∈C δ iid
Proof For each t, draw an independent pair Zt+ , Zt− ∼ P , and let ε1 , . . . , εT be independent Rademacher signs. Ghost-sample symmetrization and a random swap within each pair give E sup
T X
h∈C t=1
T X P h − 2h(Gt ) ≤ EZ,ε sup h(Zt−εt ) − 2h(Ztεt ) . h∈C t=1
− + . Unlike in the adaptive case, these points do not , Z1:T Condition on the 2T points Z1:T depend on the sign history, so the dyadic lower-approximation argument in the proof of Proposition 20 uses ordinary fixed-design ℓ∞ covers. That argument and Lemma 19 yield
Z 1 T 1 X C −εt εt Eε sup log N∞ (cα, C, Z1:2T ) dα . h(Zt ) − 2h(Zt ) ≤ Cδ + 1+ T h∈C T δ t=1
Applying AB99, Theorem 12.8 with sample size 2T and range bound 2 gives, we have the following bound: γ eT ′ log N∞ (cα, C, 2T ) ≤ Cfatc α (C) log . α Averaging over the pairs and renaming the universal scale constant proves the claim. Proposition 24 (iid convex-hull lower bounds) Let X , H be centrally symmetric convex bodies, and let T ≥ 2 and α > 0. There is a distribution P over H satisfying α fatα (LX ,H ) wc ConvDistX ,H,T ≥ E ∧1 . iid distX ◦ (µP , conv{G1:T }) ≥ G1:T ∼ P 8 T 41
Martı́nez-Rubio Bullins* Guzmán* Molina*
Proof Set m := min {fatα (LX ,H ), T } . If m = 0, take P to be the point mass at 0. Hence, suppose m ≥ 1. By Fact 31, there are g1 , . . . , gm ∈ H whose evaluation image contains m . Set η := (2T )−1 , and let P assign mass η to every g and the remaining mass to (α/2)B∞ i 0. This is a probability distribution because m ≤ T . Given a sample from P , let S ⊆ [m] contain the indices that appear and set M := m−|S|. m gives u ∈ X such that ⟨u , g ⟩ = 0 for i ∈ S The fact that the image contains (α/2)B∞ S S i and ⟨uS , gi ⟩ = α/2 otherwise. Thus every point in the sampled convex hull has pairing zero with uS , whereas αηM ⟨uS , µP ⟩ = . 2 Consequently, the distance from µP to the sampled convex hull is at least αηM/2. Since EM = m(1 − η)T ≥ m/2, taking expectations gives αm α fatα (LX ,H ) E distX ◦ (µP , conv{G1:T }) ≥ = ∧1 . 8T 8 T The definition of ConvDistwc X ,H,T now gives the final claim. Proof of Proposition 9. Fix p, q ∈ [1, ∞] and T ≥ 3. After decreasing the universal constant, if necessary, it is enough to consider large T . Let k ≥ 2 be the largest integer satisfying k log k ≤ T , and set d = T . Then k ≤ d and k ≍ T / log T . In the first k coordinates of Rd , consider the centered simplex vertices 1 1 vi := ei − 1 , i = 1, . . . , k, 2 k where ei is the i-th standard basis vector in Rk andP1 = (1, . . . , 1). Let P be the uniform distribution on {v1 , . . . , vk }. P has mean 0, since k1 ki=1 vi = 12 k1 1 − k1 1 = 0. Moreover, the distribution P is supported on Bqd∗ , because ∥vi ∥q∗ ≤ ∥vi ∥1 = 1 − k1 < 1. iid
Draw G1 , . . . , GT ∼ P , and write S := {i ∈ [k] : vi appears among G1 , . . . , GT }. 1 If some index j is missing, then every y ∈ conv{vi : i ∈ S} has j-th coordinate yj = − 2k , since (vi )j = −1/(2k) for all i ̸= j. Consequently, for every p ∈ [1, ∞],
distp∗ 0, conv{G1 , . . . , GT } =
inf
y∈conv{G1 ,...,GT }
∥y∥p∗ ≥
1 2k
on the event {S ̸= [k]}.
It remains to show that this event has probability bounded below by a universal constant. Let M := k − |S| be the P number of missing support points. If Xi is the indicator that vi is not sampled, then M = i Xi , and the standard second-moment computation gives 1 T EM = k 1 − , k
2 T EM 2 = EM + k(k − 1) 1 − . k
The maximality of k gives k log k ≤ T < (k + 1) log(k + 1). Hence (1 − k1 )T ≍ k −1 and (1 − k2 )T ≲ k −2 , with universal constants. Therefore there are universal constants 42
0 < c1 < c2 < ∞ such that c1 ≤ EM ≤ c2 , EM 2 ≤ c2 , Combining the geometric observation above with the Paley-Zygmund inequality, and using k ≍ T / log T , yields 2 (EM )2 1 1 c0 c log T E distp∗ 0, conv{G1 , . . . , GT } ≥ P(M > 0) ≥ ≥ ≥ . 2 2k 2kEM k T Here 1 is the geometric observation above and 2 is the Paley-Zygmund inequality. The constants c0 , c > 0 are universal. Proof of Corollary 8. Set 1 1 a := − , q p +
1 s := a + − p
1 1 − q 2
. +
Then Λp,q∗ = da . If p = q = ∞, the endpoint ordinary fat-shattering profile, Theorem 7 and Proposition 24, and the trivial diameter bound give d wc e ∧1 , ConvDist∞,1,T = Θ T which proves both claims at this endpoint. Hence, assume (p, q) ̸= (∞, ∞), so s > 0. First suppose d ≥ T . The ordinary fat-shattering bounds (11) and (12) give, uniformly in the remaining (p, q), Λp,q∗ 1/s d (0 < β ≤ Λp,q∗ ). fatβ (Lp,q∗ ) ≲p,q Lβ β For the upper bound, choose α = Λp,q∗ T −s in Theorem 7. Integrating the preceding estimate gives (the exponent γ+2 allows for Lcβ ≲p,q log(eT d) on this interval and the extra logarithm when s = 1) Z Λp,q∗ d γ eT Λp,q ∗ dβ ≲p,q Λp,q∗ T 1−s logγ+2 (eT d), fatcβ (Lp,q∗ ) log β α −s ). For the lower bound, choose α ≍ −s e and hence ConvDistwc p,q Λp,q ∗ T p,q ∗ ,T = Op,q (Λp,q ∗ T sufficiently small that (11) and (12) give fatα (Ldp,q∗ ) ≥ cp,q T , with 0 < cp,q ≤ 1. We only need a constant fraction of T , including when d = T . Applying Proposition 24 therefore yields ! d ) fat (L ∗ cp,q α α α p,q ∧1 ≥ ≳p,q Λp,q∗ T −s . ConvDistwc p,q ∗ ,T ≥ 8 T 8
Finally, Λp,q∗ T
−s
a d 1 = , 1 1 −( −1) T Tp q 2 +
which proves the first claim. Suppose now that d ≤ T . Write ρ := ρp,q,d (d), with ρp,q,d as in (19). We first prove dρ wc e ConvDistp,q∗ ,T = Θp,q . T 43
Martı́nez-Rubio Bullins* Guzmán* Molina*
For the upper bound, the ordinary fat-shattering estimates of Mendelson and Schechtman [MS04] and Guzmán [Guz15a], summarized in the related-work discussion and supplemented by (12) at (1, 1), give ( 1/s ) ∗ Λ p,q , fatβ (Ldp,q∗ ) ≲p,q min d, Lβ β and ρ = Λp,q∗ d−s . Apply Theorem 7 with α = ρ/T . Splitting its integral at ρ gives Z Λp,q∗
fatcβ (Ldp,q∗ ) logγ
α
eT Λp,q∗ β
dβ ≲p,q dρ logγ+2 (eT d).
Indeed, on [α, ρ] use fatcβ ≤ d, which contributes at most dρ times the logarithmic factor. On 1/s [ρ, Λp,q∗ ], use Lcβ ≲p,q log(eT d). Integrating (Λp,q∗ /β)1/s gives Op,q (Λp,q∗ ρ1−1/s ) = Op,q (dρ) when s < 1 and one additional logarithm when s = 1. Since 0 < s ≤ 1 and ρ = Λp,q∗ d−s , we also have Λp,q∗ ≤ dρ, so the theorem yields the claimed upper bound. For the lower bound, for all sufficiently large d, choose an integer m ≍p,q d with m ≤ cp,q d in Fact 32. Since ρp,q,d (m) is nonincreasing in m, cf. (19), the resulting cube has radius R ≳p,q ρp,q,d (d) = ρ. For the finitely many remaining dimensions, the one-coordinate cube gives the same conclusion after decreasing the (p, q)-dependent constant. By Fact 31, this gives fat2R (Ldp,q∗ ) ≥ m. Since m ≤ d ≤ T , Proposition 24 with α = 2R gives α ConvDistwc p,q ∗ ,T ≥ 8
fatα (Ldp,q∗ ) ∧1 T
! ≥
Rm dρ ≳p,q . 4T T
Finally, substituting m ≍p,q d into (19) and using 1 1 1 1 − = − q max{q, 2} q 2 + gives the expression in the statement in both regimes.
Appendix E. Proof of the Sequential Fat-Shattering Bounds Proof of Theorem 12. The p < q and p ≥ q cases follow by combining the corresponding upper bound in Theorem 30 and lower bound in Theorem 34, both proved below. Recall the linear class Ldp,q∗ in (5). For 1 ≤ m ≤ d, define ρp,q,d (m) :=
( m−(1/p−(1/q−1/2)+ ) , d1/q−1/p m−1/ max{q,2} ,
p < q, p ≥ q.
(19)
Set Lα := 1 + log+ ed α. The proof of the upper bound consists of several parts. First, we recall that uniform convexity controls sfat for uniformly convex balls. For balls like Bqd∗ that do not induced a 44
uniformly convex norm, we cover them with other balls and compute sfat with Lemma 27 that allows to compute sfat for a union of sets of functions. Trading off radius of the covering balls vs their sfat, we can compute upper bounds that are near optimal. For the lower bound, a classical technique for fat shattering is amplified by sequential binary search. The latter turns each of m ordinary shattering directions into log(1 + ρp,q,d (m)/α) adaptive levels and explains the logarithmic growth after the ordinary dimension has saturated at d. E.1. Upper bound We first introduce a few classical notions. Definition 25 (Uniform convexity and function range) Let (E, ∥ · ∥) be a normed space, and K ⊆ E be convex. For c > 0 and κ ≥ 2, a function Φ : K → R is (c, κ)uniformly convex on K with respect to ∥ · ∥ if Φ(u) + Φ(v) u+v ≥Φ + c∥u − v∥κ , u, v ∈ K. 2 2 Its range on K is rangeK (Φ) := supu∈K Φ(u) − inf u∈K Φ(u). The next lemma says sfat can be bounded in terms of the constants of a uniformly convex potential in our set, if it exists. We note below the lemma, that this result is essentially known, since it is a consequence of concatenating two known results. For convenience, however, we instead provide a direct simple proof of the lemma in Section E.3. Lemma 26 (Uniformly convex localization) [↓] Let ∥ · ∥ and suppose ∥g∥∗ ≤ L for every g ∈ H. Let K ⊆ Rd be convex, and let Φ : K → R be (c, κ)-uniformly convex on K with respect to ∥ · ∥ and range D. Then D L κ sfatα (LK,H ) ≤ . c α For 1 < r < ∞, the classical uniform-convexity inequalities for ℓr show that RBrd admits a potential as in Lemma 26 with κ = max{2, r} and D/c ≲r Rmax{2,r} . The result in Lemma 26 directly follows by concatenating the sequential Rademacher comparison and uniformly convex potential bound of Rakhlin, Sridharan, and Tewari [RST15b, Lemma 8 and Proposition 16]. Note that in their notation, fatα denotes the sequential dimension: Lemma 8 shows that sfatα (G) ≥ n implies α ≤ 2Rn (G), and Proposition 16 bounds this sequential Rademacher complexity Rn using a uniformly convex potential. For convenience, we instead provide a direct simple proof of the lemma in Section E.3. We next combine localized classes. The statement is the real-valued, scale-sensitive analogue of the multiple-union bound for Littlestone dimension in Alon et al. [ABM+20, Appendix A.1, Proposition 23]. We retain the short multiplicative-weights proof because it also fixes the margin and tree conventions used below. Lemma 27 (Sequential union bound) SN [↓] Let G1 , . . . , GN be real-valued function classes on the same domain, and set G := i=1 Gi . If sfatα (Gi ) ≤ m for every i ∈ [N ], then sfatα (G) ≤ C m + log N , for a universal constant C. 45
Martı́nez-Rubio Bullins* Guzmán* Molina*
Proof of Lemma 27. For a subset of functions V ⊆ Gi , write rk(V) := sfatα (V), with rk(∅) = −1. We will have an expert predicting on each subset, and once the subset is empty the corresponding expert predicts arbitrarily. At a node with instance-threshold pair (x, s), define V+ := {f ∈ V : f (x) ≥ s + α/2},
V− := {f ∈ V : f (x) ≤ s − α/2}.
If rk(V) = R, the two children cannot both have rank at least R, since otherwise attaching their depth-R shattered trees below (x, s) would give a depth-(R + 1) tree shattered by V. Hence min{rk(V+ ), rk(V− )} ≤ R − 1. The rank algorithm predicts the sign of the child with larger rank, breaking ties arbitrarily, and updates to the child selected by the observed sign. On an α-realizable path, every mistaken prediction therefore decreases the rank by at least one, and thus the rank algorithm for Gi makes at most sfatα (Gi ) ≤ m mistakes. Now run the N rank algorithms as experts. Give every expert initial weight 1, predict by weighted majority, and after each round multiply the weight of each mistaken expert by 1/2. If the master makes a mistake, then at least half of the current total weight is on mistaken experts, and hence the total weight Zt is multiplied by at most 3/4. After M master mistakes, we have 2 below, where 1 holds if the sequence is α-realizable by Gi , since expert i makes at most m mistakes and thus its final weight is at least 2−m :
2
−m
M 1 2 3 , ≤ ZT ≤ N 4
and hence
M≤
m + log2 N ≤ 4(m + log2 N ). − log2 (3/4)
Finally, let n be the depth of an arbitrary tree shattered by G, and run the N rank algorithms and their weighted-majority master at its nodes. The two edges below each node represent the two possible signs of the margin constraint at that node. After the master predicts one sign, the adversary selects the edge with the other sign. Repeating this rule constructs a root-to-leaf path on which the master makes exactly n mistakes. Since the tree is shattered, thisScomplete path is witnessed by some function f ∈ G, and the union representation G = N i=1 Gi places that function in some Gi . The mistake bound above therefore applies to the constructed path and yields n ≤ 4(m + log2 N ), proving the lemma.
Covering the parameter body by local balls now costs only the logarithm of the covering number. This is the key argument for computing near optimal upper bounds on sfatα (Ldp,q∗ ), as we simply take the infimum over R over covering a ball with another type of ball of radius R, the latter coming from a uniformly convex geometry. Corollary 28 (Uniform convexity vs covering) [↓] Let 1 < r < ∞ and suppose Bqd∗ ⊆ LBrd∗ . Then " # LR max{2,r} d d d sfatα (Lp,q∗ ) ≲r inf + log N (Bp , RBr ) . R>0 α 46
Proof of Corollary 28. Fix R > 0, and cover Bpd by Bpd ⊆
N [
(ai + RBrd ),
N = N (Bpd , RBrd ).
i=1
Set Ci := Bpd ∩ (ai + RBrd ),
Fi := {Bqd∗ ∋ g 7→ ⟨w, g⟩ : w ∈ Ci }.
Since Ci ⊆ ai +RBrd , the class Fi is contained in the corresponding local SN ball class. Moreover, d shifting the ball by ai does not change sfat. Thus, using Lp,q∗ ⊆ i=1 Fi , Lemma 26 and Lemma 27, we have sfatα (Ldp,q∗ ) ≲r
LR α
max{2,r}
+ log N (Bpd , RBrd )
for all R > 0.
The next estimate is classical. The first one is the packing-volume bound for finitedimensional norm balls (Pis89, Chapter 5) and the second is the intermediate entropy regime of Schütt [Sch84]. An explicit modern formulation is Kossaczká and Vybı́ral [KV20, Theorem 2(a)]. Fact 29 (Covering numbers) For 1 ≤ p, s ≤ ∞ and R > 0, ! 1/s−1/p d log N (Bpd , RBsd ) ≲p,s d 1 + log+ , R log N (Bpd , RBsd ) ≲p,s R−1/(1/p−1/s) log
Ced , R
1 ≤ p < s ≤ 2,
(20) 0 < R < 1.
(21)
Theorem 30 (sfat upper bound) [↓] For every 1 ≤ p, q ≤ ∞, (p, q) ̸= (∞, ∞), and α > 0, −1 1 − p1 −( 1q − 12 )+ min α , d 1 + log+ , p < q, 1 −( 1q − 12 )+ p αd !max{q,2} ! sfatα (Ldp,q∗ ) ≲p,q Lα 1/q−1/p 1/q−1/p d d min , d 1 + log , p ≥ q. + α αd1/ max{q,2} At p = q = ∞, sfatα (Ld∞,1 ) ≲ d 1 + log+ α1 . Proof of Theorem 30. When p < q, every function in the class takes values in [−1, 1]. We can restrict to 0 < α ≤ 1. Indeed, since sfatα is nonincreasing in α, we can map the case 1 < α ≤ 2 to the case α = 1, which just changes the constant. If α > 2, even a depth-one shattered tree would require two function values separated by at least α, which is impossible for a class taking values in [−1, 1], so sfatα would be 0. 47
Martı́nez-Rubio Bullins* Guzmán* Molina*
The case p < q and p ≥ 2. Apply Corollary 28 with r = p and L = 1. Taking R = 1, for which N (Bpd , Bpd ) = 1, gives sfatα (Ldp,q∗ ) ≲p α−p . Using (20) instead and taking R = αd1/p gives 1 sfatα (Ldp,q∗ ) ≲p d 1 + log+ 1/p . αd The case p < q and p < 2.
Set s := min{2, q},
b :=
1 1 − . p s
Then p < s ≤ 2, Bqd∗ ⊆ Bsd∗ , and θ = b + 1/2. Applying Corollary 28 with r = s and L = 1, followed by (21), gives for every 0 < R < 1 sfatα (Ldp,q∗ ) ≲p,q
Ced R2 + R−1/b log . 2 α R
For 0 < α < 1, take R = α2b/(2b+1) . Since log(Ced/R) ≲p,q Lα , we obtain sfatα (Ldp,q∗ ) ≲p,q Lα α−1/θ . The case α = 1 follows by monotonicity. For the d-dependent term, use (20) in Corollary 28 √ with r = s, L = 1, and R = α d. Since θ = 1/p − 1/s + 1/2, this gives 1 d sfatα (Lp,q∗ ) ≲p,q d 1 + log+ θ . αd Since θ = b + 1/2 = 1/p − (1/q − 1/2)+ , we have the result. The case p ≥ q and q < ∞. Set r := max{q, 2} and A := d1/q−1/p . If q ≥ 2, use r = q, L = 1, and R = A, the inclusion Bpd ⊆ ABqd makes the covering q number equal to one and gives sfatα (Ldp,q∗ ) ≲q A . α If q < 2 and p > 1, set u = min{p, 2}. The inclusions Bpd ⊆ d1/u−1/p Bud ,
Bqd∗ ⊆ d1/q−1/u Bud∗
have product distortion A. Applying the same covering bound with r = u and a one-element 2 cover therefore gives sfatα (Ldp,q∗ ) ≲p,q A . α For p = q = 1, it suffices to consider the nontrivial range α ≤ 2. Take u = 1 + 1/Lα . d ⊆ eB d , and the quadratic modulus constant from Ball, Carlen, and Then B1d ⊆ Bud , B∞ u∗ Lieb [BCL94] is of order u − 1. Thus the same argument gives sfatα (Ld1,∞ ) ≲ Lα α−2 . ∗ ∗ For the dimension dependent term, set λ := d1/r −1/q = d1/q−1/r . Then Bqd∗ ⊆ λBrd∗ . Hence Corollary 28 and (20) give " !# λR r d1/r−1/p sfatα ≲p,q inf + d 1 + log+ . R>0 α R Taking R = αλ−1 d1/r makes the first term equal to d, and λd−1/p = Ad−1/r . Thus A sfatα ≲p,q d 1 + log+ 1/r . αd 48
d in ℓ . Let V be such a net. The case p = q = ∞. Apply (20) to an α/4-net of B∞ ∞ d For every w ∈ B∞ , choose v ∈ V with ∥w − v∥∞ ≤ α/4. Uniformly over g ∈ B1d , the corresponding linear functions then differ by at most α/4. Replacing the witnesses of an α-shattered tree by their nearest net points therefore gives an (α/2)-shattered tree for the finite class indexed by V. A depth-n shattered tree requires a distinct function for each of its 2n root-to-leaf paths, so n ≤ log2 |V|. Finally, (20) bounds this logarithm by O d(1 + log+ (1/α)) . Thus
sfatα (Ld∞,1 ) ≲ d
1 1 + log+ . α
E.2. Lower bound We start by providing a proof of the following fact from Mendelson and Schechtman [MS04, Corollary 3.2] for completeness and the reader’s convenience. It involves the equivalence between fat shattering and a certain cube containment in some cases. Let X , H ⊆ Rd be centrally symmetric convex bodies and, for g1 , . . . , gm ∈ H, define the evaluation image CX ,H (g1:m ) := {(⟨u, g1 ⟩, . . . , ⟨u, gm ⟩) : u ∈ X } . Fact 31 (Fat-shattering and evaluation cubes) [↓] Let X , H ⊆ Rd be centrally symmetric convex bodies, let m ∈ N, and let g1 , . . . , gm ∈ H. For every α > 0, {g1 , . . . , gm } is α-shattered by LX ,H
⇐⇒
α m B ⊆ CX ,H (g1:m ). 2 ∞
(22)
As explained in the introduction, sharp fat-shattering lower bounds were known for (X , H) = (Bpd , Bqd∗ ). Through Fact 31, they give the following evaluation cubes. We include a direct proof for completeness. Fact 32 (Evaluation cubes in ℓp /ℓq cases) [↓] There is a constant cp,q > 0 such that, for every 1 ≤ m ≤ cp,q d, there exist g1 , . . . , gm ∈ Bqd∗ satisfying n o (⟨w, g1 ⟩, . . . , ⟨w, gm ⟩) : w ∈ Bpd ⊇ cp,q ρp,q,d (m)[−1, 1]m . The new sequential step is to query each coordinate of such a cube repeatedly by binary search. Lemma 33 (Cube-to-tree amplification) [↓] Let X , H ⊆ Rd be centrally symmetric convex bodies and let g1 , . . . , gm ∈ H. We have 2R m . RB∞ ⊆ CX ,H (g1:m ) =⇒ sfatα (LX ,H ) ≥ m log2 1 + α 49
Martı́nez-Rubio Bullins* Guzmán* Molina*
Proof of Lemma 33. A single interval [−R, R] supports the usual binary-search tree. For a current interval [a, b], use the midpoint s = (a+b)/2 as threshold. The minus child retains [a, s − α/2], and the plus child retains [s + α/2, b]. After t levels, every survivinginterval has length 2−t (2R + α) − α. It is therefore nonempty through h := log2 1 + 2R levels. α Every point in a terminal interval satisfies the margin inequalities along the corresponding branch. Concatenate this construction in m blocks. In block j, label every node by gj and use the binary-search thresholds for coordinate j. A branch of depth mh determines terminal intervals I1 , . . . , Im ⊆ [−R, R]. Choose zj ∈ Ij , j ∈ [m]. By the cube containment, for a u ∈ X , we have ⟨u, gj ⟩ = zj , j ∈ [m]. This witness satisfies every margin constraint on the branch, so the concatenated tree is α-shattered to depth mh. Theorem 34 (sfat lower bound) [↓] Let 1 ≤ p, q ≤ ∞, (p, q) ̸= (∞, ∞), and assume 0 < α ≤ 2Λp,q∗ . Then −1 1 − p1 −( 1q − 12 )+ , d 1 + log+ , p < q, min α 1 −( 1q − 12 )+ p αd ! ! sfatα (Ldp,q∗ ) ≳p,q d1/q−1/p max{q,2} 1/q−1/p d 1 + log , d , p ≥ q. min + α αd1/ max{q,2} For p = q = ∞ and 0 < α ≤ 2, sfatα (Ld∞,1 ) ≳ d 1 + log+ α1 . Proof of Theorem 34. First assume 0 < α ≤ cp,q Λp,q∗ for a sufficiently small constant 0 < cp,q ≤ 1. Fix 1 ≤ m ≤ cp,q d. By Fact 32, there are g1 , . . . , gm ∈ Bqd∗ whose evaluation image contains a cube of radius cp,q ρp,q,d (m). Applying Lemma 33 with (X , H) = (Bpd , Bqd∗ ), and then taking the supremum over such m, gives the profile bound below with the supremum restricted to m ≤ cp,q d. For m > cp,q d, choose m′ ≤ cp,q d with m′ ≍p,q m. Since ρp,q,d is nonincreasing, the profile term at m′ is at least a constant multiple of the term at m. The finitely many dimensions for which such an m′ does not exist are absorbed into the constants. Consequently, cp,q ρp,q,d (m) d sfatα (Lp,q∗ ) ≳p,q sup m log2 1 + . α 1≤m≤d We evaluate this profile directly. Fix K > 0, A > 0, and 0 < β ≤ 1, and write x = A/α. On the nontrivial range 0 < α ≲K A, choosing m comparable to min{x1/β , d} gives j k n x o sup m log2 1 + Kxm−β ≳β,K min x1/β , d 1 + log+ β . d 1≤m≤d Indeed, if x < dβ , choose m ≍β,K x1/β , so the logarithm is bounded below by a positive constant. If x ≥ dβ , choose m to be a sufficiently small fixed multiple of d, depending on 50
β, K. This yields the second term. Adjusting the comparison constants absorbs the floor. First consider p = q = ∞. Then ρ∞,∞,d (m) = 1, and taking m = d gives d(1 + log+ (1/α)) up to universal constants. Otherwise, apply the estimate with K = cp,q to the two cases in (19). We obtain the result with: 1 1 1 1 1 − p1 q (A, β) = 1, − for p < q, and (A, β) = d , for p ≥ q. − p q 2 + max{q, 2} For cp,q Λp,q∗ < α ≤ 2Λp,q∗ and (p, q) ̸= (∞, ∞), the claimed lower bound is Op,q (1), whereas sfatα ≥ 1: choose g ∈ Bqd∗ and u ∈ Bpd attaining ⟨u, g⟩ = Λp,q∗ , and use ±u with threshold d give sfat ≥ d for every 0 < α ≤ 2, zero. At p = q = ∞, coordinate evaluations of B∞ α which also covers the remaining scales.
E.3. Proofs of essentially-known facts provided for completeness or elegance Proof of Lemma 26. Suppose the class α-shatters a depth-n tree, and choose a witness wε ∈ K for every leaf ε. For a node u, let L(u) be the leaves below it and set mu :=
X 1 wε . |L(u)| ε∈L(u)
Convexity of K gives mu ∈ K. If gu ∈ H and su are the instance and threshold at an internal node, averaging the shattering inequalities over its two child subtrees gives ⟨mu+ , gu ⟩ ≥ su +
α , 2
⟨mu− , gu ⟩ ≤ su −
α . 2
Consequently, ∥mu+ − mu− ∥ ≥
⟨mu+ − mu− , gu ⟩ α ≥ . ∥gu ∥∗ L
For each level t, define Φt := 2−t
X
Φ(mu ).
|u|=t
Since mu = (mu+ + mu− )/2, uniform convexity yields Φt+1 ≥ Φt + c
α κ L
.
Thus nc(α/L)κ ≤ Φn − Φ0 ≤ D, which proves the lemma. m ⊆ C m Proof of Fact 31. First suppose that α2 B∞ X ,H (g1:m ). For every ε ∈ {±1} , choose uε ∈ X whose evaluation vector is (α/2)ε. The corresponding functions shatter g1 , . . . , gm with all thresholds equal to zero. Conversely, suppose that g1 , . . . , gm are α-shattered with threshold vector s ∈ Rm , and write C = CX ,H (g1:m ). Fix a ∈ Rm , and choose the two shattering functions corresponding
51
Martı́nez-Rubio Bullins* Guzmán* Molina*
to the sign patterns of a and −a, with arbitrary signs in the zero coordinates. Their evaluation vectors y + , y − ∈ C satisfy α α ⟨a, y + ⟩ ≥ ⟨a, s⟩ + ∥a∥1 , ⟨−a, y − ⟩ ≥ ⟨−a, s⟩ + ∥a∥1 . 2 2 Since C is centrally symmetric, its support function satisfies α α hC (a) = hC (−a) ≥ ∥a∥1 + |⟨a, s⟩| ≥ ∥a∥1 . 2 2 m . Both sets are closed and The rightmost expression is the support function of (α/2)B∞ m convex, so support-function duality gives (α/2)B∞ ⊆ C. This cube spans Rm , so the evaluation map u 7→ (⟨u, gi ⟩)m i=1 has rank m, which also proves that the gi are linearly independent. P Proof of Fact 32. Given g1 , . . . , gm , define T : Rm → Rd by T a = m i=1 ai gi , and let C be the evaluation image in the statement. Its support function is
sup⟨a, y⟩ = sup ⟨w, T a⟩ = ∥T a∥p∗ . y∈C
w∈Bpd
Thus it suffices in every case to prove ∥T a∥p∗ ≳p,q ρp,q,d (m)∥a∥1 . The range p ≤ q.
If q ≥ 2, take gi = ei . Then ∥T a∥p∗ = ∥a∥p∗ ≥ m−1/p ∥a∥1 = ρp,q,d (m)∥a∥1 .
If q < 2, choose an orthonormal basis u1 , . . . , um ∈ Rm with ∥ui ∥∞ ≲ m−1/2 and embed it in the first m coordinates of Rd . Set gi := cq m1/q−1/2 ui . Then gi ∈ Bqd∗ , and, since p∗ ≥ q ∗ > 2, ∗
∥T a∥p∗ ≳p,q m1/q−1/2 m1/p −1/2 ∥a∥2 ≥ m−(1/p+1/2−1/q) ∥a∥1 = ρp,q,d (m)∥a∥1 . The range q < p. If q > 2, partition a subset of [d] into m disjoint blocks B1 , . . . , Bm of ∗ common size b ≍ d/m, and set gi := b−1/q 1Bi . Then ∥gi ∥q∗ = 1, and the disjoint supports give ∥T a∥p∗ = b1/q−1/p ∥a∥p∗ ≥ b1/q−1/p m−1/p ∥a∥1 ≍ d1/q−1/p m−1/q ∥a∥1 . Finally, suppose q ≤ 2. Kashin’s random-sign construction (Kas77) gives, for m ≤ cp d, a matrix G ∈ {±1}d×m such that ∗
∥Ga∥p∗ ≳p d1/p ∥a∥2 ,
a ∈ Rm .
For p∗ ≤ 2, this is the Kashin ℓ1 -estimate followed by norm comparison. For p∗ ≥ 2, it follows from the smallest singular-value bound and the comparison of ℓp∗ with ℓ2 . If Gi is ∗ column i, define gi := d−1/q Gi . Then ∥gi ∥q∗ = 1, and ∗
∥T a∥p∗ = d−1/q ∥Ga∥p∗ ≳p,q d1/q−1/p m−1/2 ∥a∥1 . In each case the support-function criterion gives the asserted cube.
52
Appendix F. Proofs of minimax rate for some infinite-dimensional cases Proof of Proposition 13. We first prove the fat-shattering lower bound. By the RellichKondrachov compact embedding theorem, the inclusion J : H s (Ω) ,→ L2 (Ω) is compact. Since both spaces are Hilbert and J is injective, the singular-value decomposition for compact Hilbert-space operators gives an orthonormal basis (ej )j≥1 of H s (Ω), an orthonormal basis (ϕj )j≥1 of L2 (Ω), and positive weights (wj )j≥1 satisfying Jej = wj−1 ϕj . Thus, if P P u = j≥1 aj ej ∈ H s (Ω), then, viewing u as an element of L2 (Ω), u = Ju = j≥1 aj wj−1 ϕj . P P 2 2 2 Writing θj = aj wj−1 gives us ∥u∥2H s (Ω) = j≥1 aj = j≥1 wj θj . Hence, we have the following representation X X 2 2 wj θ j ≤ 1 . X = θj ϕ j : j≥1
j≥1
The classical spectral estimate for the Sobolev embedding gives wj ≍s,m j s/m , see Edmunds 2 Pn 2 and Triebel [ET96, Section 3.3.4].7 Let n satisfy α4 j=1 wj ≤ 1, and take P gj = ϕj ∈ H, n j = 1, . . . , n, with zero thresholds. For every ε ∈ {±1} , define uε := α2 nj=1 εj ϕj . Then P α α2 Pn 2 2 2 j≥1 wj ⟨uε , ϕj ⟩L2 = 4 j=1 wj ≤ 1, so uε ∈ X , while for every j ≤ n, εj ⟨gj , uε ⟩ = 2 . Thus g1 , . . . , gn are α-fat-shattered. Since wj ≍s,m j s/m , the standard integral comparison for sums of powers gives n X j=1
wj2 ≍s,m
n X j=1
j
2s/m
Z n ≍s,m
x2s/m dx =
0
1 n1+2s/m ≍s,m n1+2s/m . 1 + 2s/m
Therefore the condition on n, and the fact that we can have a set of size n that is fat2m shattered, implies fatα (LX ,H ) ≳s,m α− m+2s . For the sequential upper bound, it is sufficient to construct a uniform cover of the linear class, since every uniform cover induces a sequential cover on any input tree. For fu (g) = ⟨g, u⟩ and fv (g) = ⟨g, v⟩, since H = BL2 (Ω) , we have ∥fu − fv ∥∞ = supg∈H |⟨g, u − v⟩| = ∥u − v∥L2 . Thus a uniform cover of LX ,H is equivalent to an L2 -cover of X . Let N2 (X , R) denote the covering number of X by radius-R balls in L2 (Ω). The Sobolev entropy estimate of ET96, Sections 3.3.2 and 3.5 gives log N2 (X , R) ≲s,m R−m/s ,
0 < R < 1.
Cover X by these balls. Note that the squared L2 distance to the center of each ball is (1/4, 2)-uniformly convex with range at most R2 (see Definition 25 for the notions of uniform convexity and range) (Cla36). Hence, for any R ∈ (0, 1), Lemma 26 and 27 gives 2 2 2m R R −m/s sfatα (LX ,H ) ≲s,m inf + log N2 (X , R) ≲s,m inf +R ≲s,m α− m+2s , 2 2 R∈(0,1) α R∈(0,1) α 7. In the notation of ET96, take A = F , p1 = p2 = q1 = q2 = 2, s1 = s, s2 = 0, and dimension m. Their approximation-number estimate then gives aj ≍s,m j −s/m . For compact operators between Hilbert spaces, approximation numbers coincide with singular values, while in our decomposition the corresponding singular value is wj−1 .
53
Martı́nez-Rubio Bullins* Guzmán* Molina*
where the last inequality follows by taking R = α2s/(m+2s) for 0 < α < 1, so both terms equal α−2m/(m+2s) . Proof of Proposition 14. For the ordinary fat-shattering lower bound, take a grid x1 , . . . , xn ∈ [1/2, 1]m (this is basically the elements of H) with spacing α in each coordinate. Then n ≍m α−m and, for every i ̸= j, ∥xi − xj ∥∞ ≥ α. For every ε ∈ {±1}n , let uε (0) = 0 and uε (xi ) = εi α/2. These values are 1-Lipschitz on {0, x1 , . . . , xn }, since for i ̸= j, |uε (xi ) − uε (xj )| ≤ α ≤ ∥xi − xj ∥∞ , while |uε (xi ) − uε (0)| = α/2 ≤ ∥xi ∥∞ . By the McShane extension theorem, uε extends to a 1-Lipschitz function on Ω. Since gi = δxi , εi ⟨δxi , uε ⟩ = εi uε (xi ) = α2 . Hence x1 , . . . , xn are α-fat-shattered with zero thresholds, and therefore fatα (LX ,H ) ≳m α−m . For the sequential upper bound, the entropy estimate for Lipschitz functions gives log N∞ (X , α) ≲m α−m , see van der Vaart and Wellner [vdVW96, Theorem 2.7.1.]. Since H = {0} ∪ {±δx : x ∈ Ω}, the uniform metric on LX ,H is exactly the uniform metric on X , as supg∈H |⟨g, u − v⟩| = supx∈Ω |u(x) − v(x)| = ∥u − v∥∞ . Now suppose a tree of depth n is α-shattered, and let uε ∈ X be a witness for each path ε ∈ {±1}n . If two distinct paths ε, ε′ first differ at level t, they encounter the same point xt and threshold rt . Assuming without loss of generality that εt = 1 and ε′t = −1, the shattering inequalities give uε (xt ) ≥ rt + α2 , uε′ (xt ) ≤ rt − α2 , and hence ∥uε − uε′ ∥∞ ≥ α. Thus the 2n witnesses are pairwise α-separated, so by triangle inequality any uniform α/4cover of X contains at least 2n elements. Therefore n log 2 ≤ log N∞ (X , α/4) ≲m α−m . Hence sfatα (LX ,H ) ≲m α−m . Proof of Proposition 15. For the ordinary lower bound, let n ≤ (2/α)p and consider the fixed functionals g1 , . . . , gn with zero thresholds. For every (ε1 , . . . , εn ) ∈ {±1}n , let p α Pn u = 2 j=1 εj ϕj . Since n ≤ (2/α)p , ∥u∥p = n α2 ≤ 1, so u ∈ X . Moreover, for α each j ≤ n, εj ⟨gj , u⟩ = 2 . Thus g1 , . . . , gn are α-fat-shattered with zero thresholds, and fatα (LX ,H ) ≳p α−p . For the sequential upper bound, consider an α-shattered tree of depth n. We construct one root-to-leaf path ε = (ε1 , . . . , εn ) greedily. Fix a coordinate gj . We prove by induction that, after its k-th occurrence along the constructed path, we have |⟨gj , u⟩| ≥ k − 12 α for every u ∈ X realizing the current partial path, i.e., satisfying all the shattering inequalities corresponding to the branches chosen so far (there is at least one because the tree is αshattered). For k = 1, choose the branch whose constraint lies away from zero, which gives |⟨gj , u⟩| ≥ α/2. For the induction step, suppose for instance that after the kth occurrence we have ⟨gj , u⟩ ≥ (k − 21 )α. At the next occurrence, let r be the threshold. Since the tree is shattered, the negative child is realizable, so there exists some u− ∈ X satisfying the previous constraints together with ⟨gj , u− ⟩ ≤ r − α/2. By the induction hypothesis, the same u− satisfies ⟨gj , u− ⟩ ≥ (k − 21 )α. Hence α r − ≥ ⟨gj , u− ⟩ ≥ 2 54
1 k− α, 2
so r ≥ kα. Choosing the positive child then gives ⟨gj , u⟩ ≥ r +α/2 ≥ (k + 12 )α. The negative case is symmetric. Thus, if kj denotes the number of occurrences of gj along the resulting path, P any witness u ∈ X for that path satisfies |⟨gj , u⟩| ≥ (kj − 12 )α whenever kj > 0. Since j kj = n, p
1 ≥ ∥u∥ =
X j
p
|⟨gj , u⟩| ≥ α
p
α p X 1 p α p X kj − ≥ n. kj = 2 2 2 j
j:kj >0
Hence n ≤ (2/α)p , so sfatα (LX ,H ) ≲p α−p . For the optimization consequence, replace H by {0} ∪ {±gj : j ≥ 1}. This does not change either shattering dimension.
55