REVIEW 4 major objections 6 minor 18 references
Mirror Descent on Reproducing Kernel Banach Spaces
T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Mirror descent on reproducing kernel Banach spaces converges linearly only in the near-Hilbert case; elsewhere a sublinear rate is the provable best.
desk verdict Useful RKBS construction and a clean constrained-rate proof, but the headline linear-rate theorem is not proven as written and the Hilbertizability assumption undercuts the non-Hilbertian pitch. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the functional mirror descent update $g_t\leftarrow g_{t-1}-\eta\,\partial_{f_{t-1}}L$, $f_t\leftarrow(\partial\Phi)^{-1}(g_t)$, where $\Phi$ is a strictly convex mirror potential and its Gâteaux derivative $\partial\Phi$ maps the primal RKBS onto its dual; the reproducing kernel supplies the concrete dual-space gradient $2\sum_i(f_{t-1}(x_i)-y_i)K(x_i,\cdot)$, so the iteration runs on coefficient vectors. The linear-rate proof is driven by a convex-conjugate lemma (from Zălinescu) that converts $\rho$-smoothness of $\Phi$ into a lower bound $\kappa$ on the dual norm of its differential, together with strong convexity of $L$ to sandwich the loss decrease. The negative result Lemma 19 uses second-order Taylor expansion points (Borwein–Noll) and Kwapień's generalized parallelogram-law characterization to conclude that simultaneous strong convexity and smoothness forces the Banach norm to be equivalent to a Hilbert norm.
What would settle it
Take the paper's own $p$-norm RKBS with $p\neq 2$ (which is not Hilbertizable) and try to construct, or numerically locate, a functional that is both $\mu$-strongly convex and $\gamma$-smooth with respect to its norm; Lemma 19 predicts none exists, so exhibiting one would refute the negative result and reopen the possibility of linear rates beyond Hilbertizable spaces.
Extended reading notes
Core claim
On its own terms, the paper's discovery is Theorem 20: on a reflexive reproducing kernel Banach space (RKBS, a Banach space of functions whose point evaluations are continuous, so a kernel exists) that is Hilbertizable—isomorphic, not necessarily isometrically, to a Hilbert space—and admits a functional that is both $\mu$-strongly convex and $\gamma$-smooth with respect to the Banach norm, mirror descent with learning rate $\eta=\min\{\nu/\gamma,1/(2\mu\nu\kappa^2)\}$ converges linearly at rate $e^{-k\mu\nu^2\kappa^2/\gamma}$, where $\nu$ and $\rho$ are the strong-convexity and smoothness constants of the mirror map and $\kappa$ depends on $\rho$. The companion Lemma 19 states that no Banach space not isomorphic to a Hilbert space admits any such functional, which means the linear-rate assumptions cannot hold in genuinely non-Hilbertian RKBS; the same rate is shown under the Polyak–Łojasiewicz inequality, and a $O(1/\sqrt{t})$ rate for constrained problems under convexity and Lipschitzness. To make the method concrete, the paper introduces a family of $p$-norm RKBSs ($p\neq 2$) with an explicitly given reproducing kernel and a dual map whose inverse is the standard $\ell^q$ gradient, reducing each iteration to vector updates of coefficients in $\mathbb{R}^n$.
Load-bearing premise
The load-bearing premise is Assumption 2, that the RKBS admits a functional that is both $\mu$-strongly convex and $\gamma$-smooth with respect to the Banach norm—which, by the paper's own Lemma 19, forces the space to be isomorphic to a Hilbert space, so the headline linear rate applies only in a near-Hilbert setting.
Editorial extensions
If this is right
- If the theorem is right, first-order optimization on RKBS can match the Euclidean linear-rate guarantee $e^{-k\mu\nu^2\kappa^2/\gamma}$ whenever the space is Hilbertizable and the loss and mirror map satisfy the smoothness/strong-convexity pair.
- Because Lemma 19 forces Hilbertizability whenever both assumptions hold, the analysis draws a clean boundary: genuinely non-Hilbertian RKBS admit no fast-rate regime of this type, and existing representer theorems for such spaces come with no corresponding fast optimization guarantee.
- The linear rate survives when the loss's strong convexity is relaxed to the Polyak–Łojasiewicz inequality, so the same algorithm is fast for losses that are not convex in the classical sense.
- In the constrained setting, projected mirror descent converges at $O(1/\sqrt{t})$ under only convexity and Lipschitzness of the loss plus strong convexity of the mirror map, with no smoothness or Hilbertizability required.
- The explicit $p$-norm RKBS family turns each mirror step into $\beta^{(t)}\leftarrow \beta^{(t-1)}-\eta\,\hat{H}^\top(\hat{H}\alpha^{(t-1)}-Y)$ and a dual-map normalization, meaning the method ports directly to similarity-matrix-based kernel code.
Reading between the lines
- Extension: the negative Lemma 19 suggests that the practical gains of $p\neq 2$ RKBS must come from approximation or sparsity, not from faster optimization; any claim of linear rates on genuinely non-Hilbertian spaces would need a different smoothness/strong-convexity notion than the paper's Banach-norm definitions.
- Extension: the concrete $p$-norm construction invites a testable study in which small $p$ produces sparser coefficients and possibly better generalization on high-dimensional data, at the cost of leaving the linear-rate (near-Hilbert) regime for the constrained $O(1/\sqrt{t})$ regime; the paper's step-function experiments show error decreasing with smaller $p$ but do not measure this trade-off.
- Extension: the rate's constant $\kappa$ is only said to 'depend on $\rho$' via Proposition 21; an explicit expression for $\kappa$ in terms of $\rho$ and the isomorphism constants would let practitioners predict the actual contraction factor, and a numerical check on a Hilbertizable RKBS with known constants could test whether the bound is tight.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies mirror descent on reproducing kernel Banach spaces (RKBS). It proposes a functional mirror descent algorithm whose dual updates are expressed through the reproducing kernel, and it analyzes convergence. The main theoretical claims are: (i) a linear convergence rate for unconstrained mirror descent when the RKBS is reflexive and Hilbertizable and the loss and mirror map are strongly convex and smooth (Theorem 20), with an extension under the Polyak–Łojasiewicz condition (Theorem 22); (ii) a negative result (Lemma 19) stating that a functional that is both strongly convex and smooth exists only on spaces isomorphic to Hilbert spaces; and (iii) an O(1/√t) rate for projected mirror descent in a constrained setting (Theorem 25). The paper also constructs a finite-center p-norm RKBS with an explicit reproducing kernel and ℓp mirror map, and reports numerical experiments.
Significance. The contribution is potentially useful: it brings the mirror-descent framework to RKBS optimization, gives a concrete finite-dimensional p-norm RKBS with an explicit kernel and dual map, and provides a standard constrained O(1/√t) analysis. The explicit updates in Algorithm 1 and the connection to representer theorems are strengths. However, the headline linear-rate theorem is narrower than the abstract suggests: by the paper's own Lemma 19, the smooth-and-strongly-convex assumptions force the space to be isomorphic to a Hilbert space, so the linear-rate result does not cover genuinely non-Hilbertian RKBS. Moreover, the proof of Theorem 20 has a repairable but load-bearing gap around Eq. (30). With those points fixed, the paper would make a solid contribution to the optimization side of RKBS.
major comments (4)
- [§3.2, Eq. (30)] The contraction step in the proof of Theorem 20 is misindexed. Strong convexity at f_{k-1} gives L(f*) ≥ L(f_{k-1}) − (1/(2µ))||∂f_{k-1}L||²_{B*}, while strong convexity at f_k gives L(f*) ≥ L(f_k) − (1/(2µ))||∂f_k L||²_{B*}. The displayed equation instead writes an infimum around f_k and then uses ∂f_{k-1}L; with that subgradient the inequality does not follow, and with ∂f_kL it belongs to iteration k+1 and cannot be combined with Eq. (29). The displayed contraction factor is therefore not established as written, and Theorem 22 inherits this gap.
- [§3.2, after Proposition 21] The constant κ is undefined. The proof states 'there exists a scalar κ > 0 such that κ := 1/L3' but L3 never appears in Proposition 21 or elsewhere. Proposition 21 has constants L2 and L5; the proof needs to define κ explicitly (for p = 2, presumably κ = 1/L5) and show that κ depends only on ρ, since the rate e^{−k·µν²κ²/γ} is otherwise not quantitative.
- [§3.2, Theorem 20] The final rate is obtained by setting (2ν−γη)η = ν²/γ, which requires η = ν/γ, but the theorem states η = min{ν/γ, 1/(2µνκ²)}. The second branch is never analyzed, and one must also verify that η < 2ν/γ so that the coefficient in Eq. (28) is positive. A complete proof needs a branch analysis and, if necessary, a different contraction factor for the second branch.
- [§3.1–3.2, Lemma 19 and Assumption 2] The scope of the linear-rate result is narrower than the abstract suggests. Lemma 19 implies that any space satisfying Assumption 2 is isomorphic to a Hilbert space, so Assumption 2 already implies Assumption 1; moreover, since Theorem 20 independently assumes that L and Φ are strongly convex and smooth, Assumption 2 is redundant as stated. The authors should state explicitly that the linear-rate guarantee applies only to Hilbertizable RKBS and does not cover genuinely non-Hilbertian RKBS, and they should restructure the assumptions accordingly.
minor comments (6)
- [§2.1, Definition 6] The convexity definition has a typo: 'F(λf + (1 + λ)f′)' should read 'F(λf + (1−λ)f′)'.
- [§3.3, Theorem 25 proof] The Jensen inequality direction is reversed in the line 'using convexity 1/t ∑ L(f_t) − L(f*) ≤ L(1/t ∑ f_t) − L(f*)'; it should be '≥'. The desired bound follows from L(1/t∑f_t) − L(f*) ≤ (1/t)∑(L(f_t) − L(f*)) together with the averaged regret bound.
- [§A.2, Lemma 19 proof] In Eqs. (61)–(62) the argument of F in the second-order expansion and in the smoothness/strong-convexity inequalities is written inconsistently as f′; these should be 'F(f + λf′)' and '⟨λf′, g*⟩' with the subgradient taken at f.
- [§4] The text 'for q = 1 + q/p' is incorrect; the intended relation is 1/p + 1/q = 1, equivalently q = p/(p−1).
- [§4, Algorithm 1] The initial values α(0) and β(0) are listed in the Data line but never specified; the algorithm should state an initialization, for example β(0) = 0 and α(0) = 0.
- [§4, Figure 5] The text says the training error is plotted over 500,000 iterations while the caption mentions up to 100,000 steps; the numbers should be made consistent.
Circularity Check
No significant circularity: the convergence theorems are conditional on explicit strong-convexity/smoothness assumptions, and the RKBS construction is a genuine derivation rather than a fitted input relabeled as a prediction.
full rationale
The paper's main theoretical claim (Theorem 20) is a conditional statement: given a reflexive RKBS, a loss functional L that is µ-strongly convex and γ-smooth, and a mirror map Φ that is ν-strongly convex and ρ-smooth, mirror descent converges linearly. The rate is derived from those constants through the descent estimate and the duality result quoted from Zălinescu (Proposition 21). Hilbertizability (Assumption 1) and smooth-convexity (Assumption 2) are used as sufficient conditions for the existence of such functionals, not as assumptions that directly encode the linear-rate conclusion. Lemma 19 shows Assumption 2 implies Assumption 1, making Assumption 1 redundant, but redundancy is not circularity. The p-norm RKBS construction in Section 4 is self-contained: the space, norm, dual space, reproducing kernel, and mirror map are all explicitly defined, and the reproducing property and the mirror-descent updates are verified rather than assumed. No parameter is fitted to data and then renamed as a prediction; the numerical experiments validate convergence behavior but do not masquerade as theoretical predictions. The paper contains no self-citations by the current authors; the cited external results (Borwein-Noll, Kwapień, Zălinescu, Bubeck) are independent mathematical facts. The proof issues identified by the skeptic—the index mismatch in Eq. (30) and the equality of the contraction exponent only holding on the η = ν/γ branch of the min—are correctness or repair concerns, not circular reductions of the conclusion to the inputs. Similarly, any gap in the non-separable case of Lemma 19 is a completeness issue, not a circularity. Overall, the derivation chain does not reduce any claimed prediction to its own assumptions.
Assumptions & free parameters
free parameters (3)
- learning rate η (experiments) =
not reported
- LAB kernel bandwidths θ_i =
computed by 10 gradient steps on loss
- Gaussian baseline bandwidth σ² =
best across trials
assumptions (7)
- domain assumption B is a reflexive RKBS
- domain assumption Assumption 1: B is Hilbertizable (isomorphic to a Hilbert space)
- domain assumption Assumption 2: B admits a µ-strongly convex and γ-smooth functional
- domain assumption Loss functional L is µ-strongly convex and γ-smooth (Theorem 20) or convex and L-Lipschitz (Theorem 25)
- domain assumption Mirror map Φ is ν-strongly convex and ρ-smooth (Theorem 20) or µ-strongly convex (Theorem 25)
- domain assumption Linear independence of {H(·, c_i)} over the field
- standard math Known theorems: Kwapień (1972), Borwein-Noll (1994), Zălinescu (2002) are correct
Cite this review
Pith. "Pith review of Mirror Descent on Reproducing Kernel Banach Spaces." pith.science (2026). https://pith.science/paper/IRG4FLTV
@misc{pith2026241111242,
author = {Pith},
title = {Pith review of: Mirror Descent on Reproducing Kernel Banach Spaces},
year = {2026},
howpublished = {\url{https://pith.science/paper/IRG4FLTV}},
note = {Machine review of arXiv:2411.11242}
}
abstract
Recent advances in machine learning have led to increased interest in reproducing kernel Banach spaces (RKBS) as a more general framework that extends beyond reproducing kernel Hilbert spaces (RKHS). These works have resulted in the formulation of representer theorems under several regularized learning schemes. However, little is known about an optimization method that encompasses these results in this setting. This paper addresses a learning problem on Banach spaces endowed with a reproducing kernel, focusing on efficient optimization within RKBS. To tackle this challenge, we propose an algorithm based on mirror descent (MDA). Our approach involves an iterative method that employs gradient steps in the dual space of the Banach space using the reproducing kernel. We analyze the convergence properties of our algorithm under various assumptions and establish two types of results: first, we identify conditions under which a linear convergence rate is achievable, akin to optimization in the Euclidean setting, and provide a proof of the linear rate; second, we demonstrate a standard convergence rate in a constrained setting. Moreover, to instantiate this algorithm in practice, we introduce a novel family of RKBSs with $p$-norm ($p \neq 2$), characterized by both an explicit dual map and a kernel.
Figures
Reference graph
Works this paper leans on
-
[8]
doi: 10.1007/s10994-006-0679-0
ISSN 0885-6125. doi: 10.1007/s10994-006-0679-0. URL https://doi.org/10.1007/s10994-006-0679-0. Arkadii Nemirovski and David Borisovich Yudin.Problem Complexity and Method Efficiency in Optimization
-
[10]
doi: https://doi.org/10.1016/j.acha.2011.01.001
ISSN 1063-5203. doi: https://doi.org/10.1016/j.acha.2011.01.001. URL https://www.sciencedirect.com/science/article/pii/S1063520311000157. Alistair Shilton, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Gradient descent in neural networks as sequential learning in reproducing kernel banach space. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara E...
-
[12]
Haoyuan Sun, Khashayar Gatmiry, Kwangjun Ahn, and Navid Azizan
URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ c9694bf4f9bf3626f7d21158bab74f8e-Paper-Conference.pdf. Haoyuan Sun, Khashayar Gatmiry, Kwangjun Ahn, and Navid Azizan. A unified approach to controlling implicit regularization via mirror descent.ArXiv, abs/2306.13853,
arXiv 2022
-
[16]
A simple proof of the Baillon-Haddad theorem on open subsets of Hilbert spaces
URLhttps://arxiv.org/abs/2204.00282. Rui Wang, Yuesheng Xu, and Mingsong Yan. Sparse representer theorems for learning in reproducing kernel banach spaces.ArXiv, abs/2305.12584, 2023a. Rui Wang, Yuesheng Xu, and Mingsong Yan. Sparse representer theorems for learning in reproducing kernel banach spaces, 2023b. Matthew A. Wright and Joseph Gonzalez. Transfo...
-
[18]
doi: https://doi.org/10.1016/j.acha.2010.09.007
ISSN 1063-5203. doi: https://doi.org/10.1016/j.acha.2010.09.007. URL https://www.sciencedirect. com/science/article/pii/S1063520310001120. Haizhang Zhang and Jun Zhang. Regularized learning in banach spaces as an optimization problem: representer theorems. Journal of Global Optimization, 54:235–250,
-
[1963]
Random Fourier Features for Asymmetric Kernels
ISSN 0041-5553. doi: https://doi.org/ 10.1016/0041-5553(63)90382-3. URL https://www.sciencedirect.com/science/article/pii/ 0041555363903823. Ming qian He, Fan He, Fanghui Liu, and Xiaolin Huang. Random fourier features for asymmetric kernels. ArXiv, abs/2209.08461,
-
[1996]
ISSN 00359246. URLhttp://www.jstor. org/stable/2346178. Hongzhi Tong, Di-Rong Chen, and Fenghong Yang. Least square regression with lp-coefficient regularization. Neural Computation, 22(12):3221–3235,
-
[2007]
Stephen Boyd and Lieven Vandenberghe
URL https://proceedings.neurips.cc/paper_files/paper/ 2007/file/0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge,
work page 2007
Show all 18 references
-
[2010]
41 Mirror Descent on RKBS Michael Unser, Julien Fageot, and Harshit Gupta
doi: 10.1162/NECO_a_00044. 41 Mirror Descent on RKBS Michael Unser, Julien Fageot, and Harshit Gupta. Representer theorems for sparsity-promotingℓ1 regularization. IEEE Transactions on Information Theory, 62(9):5167–5180,
-
[2011]
Rémi Gribonval, Gitta Kutyniok, Morten Nielsen, and Felix Voigtländer
URL https://proceedings.neurips.cc/paper_files/paper/ 2011/file/7b13b2203029ed80337f27127a9f1d28-Paper.pdf. Rémi Gribonval, Gitta Kutyniok, Morten Nielsen, and Felix Voigtländer. Approximation spaces of deep neural networks.Constructive Approximation, 55:259–367,
2011
-
[2012]
Yingyi Chen, Qinghua Tao, Francesco Tonin, and Johan A
Curran Associates Inc. Yingyi Chen, Qinghua Tao, Francesco Tonin, and Johan A. K. Suykens. Primal-attention: Self- attention through asymmetric kernel svd in primal representation.ArXiv, abs/2305.19798,
-
[2013]
doi: https://doi.org/10.1016/j.acha.2012.03.009
ISSN 1063-5203. doi: https://doi.org/10.1016/j.acha.2012.03.009. URL https://www.sciencedirect.com/science/ article/pii/S1063520312000486. Len Spek, Tjeerd Jan Heeringa, and Christoph Brune. Duality for neural networks through reproducing kernel banach spaces.ArXiv, abs/2211.05020,
2012 arXiv
-
[2015]
doi: https://doi.org/10.1016/j.acha.2014.03.007
ISSN 1063-5203. doi: https://doi.org/10.1016/j.acha.2014.03.007. URL https://www.sciencedirect.com/science/article/pii/S1063520314000475. Kenji Fukumizu, Gert Lanckriet, and Bharath K. Sriperumbudur. Learning in hilbert vs. banach spaces: A measure embedding viewpoint. In J. S...
2014 doi
-
[2016]
Daniel Wachsmuth and Gerd Wachsmuth
doi: 10.1109/ TIT.2016.2590421. Daniel Wachsmuth and Gerd Wachsmuth. A simple proof of the baillon-haddad theorem on open subsets of hilbert spaces,
2016
-
[2019]
Support vector machines in reproducing kernel hilbert spaces versus banach spaces
Qi Ye. Support vector machines in reproducing kernel hilbert spaces versus banach spaces. In Gregory E. Fasshauer and Larry L. Schumaker, editors,Approximation Theory XIV: San Antonio 2013, pages 377–395, Cham,
2013
-
[2021]
Francis R. Bach. Breaking the curse of dimensionality with convex neural networks. ArXiv, abs/1412.8690,
-
[2022]
doi: 10.1007/s10114-022-1397-7
ISSN 1439-7617. doi: 10.1007/s10114-022-1397-7. URLhttps: //doi.org/10.1007/s10114-022-1397-7. David G. Luenberger.Optimization by Vector Space Methods. John Wiley & Sons, Inc., USA, 1st edition,
-
[2023]
doi: https://doi.org/10.1016/j.acha.2022.08.006
ISSN 1063-5203. doi: https://doi.org/10.1016/j.acha.2022.08.006. URL https://www.sciencedirect.com/science/article/pii/S1063520322000768. Heinz H. Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: First-order methods revisited and...
2022 doi
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.