REVIEW 3 major objections 4 minor 35 references
Sliding Methods for H\"older-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read For Hölder-smooth bilinear minimax problems, a recursive sliding method separates oracle costs: each function's gradient budget is set by its own smoothness exponent, and coupling products keep the smooth rate.
desk verdict Solid Hölder-extension of Borodich et al.'s sliding method with honest per-oracle rates, but the headline strongly-convex table quietly depends on zero-normal-vector boundary conditions that fail on plain box-constrained examples. 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 a recursive sliding scheme for finite-sum monotone variational inequalities (Algorithm 1), specialized to a three-component decomposition: p1 = f, p2 = g, and a coupling-induced regularizer p3 = (βx/2)||Bx − g′(y_in)||² + (βy/2)||B^T y + f′(x_in)||² whose anchor gradients are drawn once per restart, with Q3 the skew-symmetric bilinear operator. Three reductions make it run: a Hölder-to-inexact-oracle conversion (Lemma E.1) that turns every (ν, H) function into a (δ, L(δ)) oracle and balances the tolerance against the recursion depth; effective curvatures δx = μx + 4βx μxy², δy = μy + 4βy μyx², condition numbers κx = Lx/δx, κy = Ly/δy, κxy = Lxy²/(δxδy) and scaled const
What would settle it
Run the method on a strongly convex instance with νx = 1 whose unique saddle point lies on the boundary of X, for example f(x) = ½(x−c)² − t·x on X = [0,1] with the tilt t chosen so x* = 0, paired with any Hölder g, and measure the per-restart Lyapunov contraction Ψ(z_out)/Ψ(z_in). Theorem 4.4 claims a factor of 3/4 whenever the stated normal-vector condition holds; if the boundary instance does not produce the Table 1 rates, or the contraction fails, the boundary condition is genuinely load-bearing rather than cosmetic.
Extended reading notes
Core claim
The paper claims that when f and g have (νx, Hx)- and (νy, Hy)-Hölder gradients, a restarted three-level sliding method on the associated monotone variational inequality reaches accuracy ε with N_f = O(H̃x^{2/(1+3νx)} ε^{(νx−1)/(1+3νx)}) evaluations of f′ for νx < 1 (Õ(√κx) at νx = 1), the analogue for g′, and N_B = Õ(√κxy) products with B and B^T, independent of the Hölder exponents. So the f-budget is set by f's own smoothness and the coupling spectrum, not by g's; at (νx, νy) = (1,1) the trio collapses to the known optimal smooth separated rates, at ν = 0 to nonsmooth O(ε^{−2})-type scaling, and between them each component interpolates with exponent 2/(1+3ν). The route: convert each Hölde
Load-bearing premise
The strongly convex rates rest on the optimality conditions' normal vectors vanishing at the saddle point whenever a smooth anchor term is active, which is automatic at interior saddle points but not at boundary saddle points, together with the requirement that any smooth component's Lipschitz-gradient constant hold on the whole ambient space rather than only on the feasible set.
Editorial extensions
If this is right
- When one component is smooth (ν = 1) and the other is genuinely Hölder (ν < 1), the smooth component keeps its logarithmic √κ rate while the other pays only its own ε^{−(1−ν)/(1+3ν)} cost, so the overall rate is not the worse of the two.
- In the fully nonsmooth limit νx = νy = 0, the gradient budgets become O(1/ε²)-type nonsmooth rates while the coupling budget remains O(Lxy Ω/ε), matching the optimal rates for first-order convex optimization and for monotone Lipschitz variational inequalities respectively.
- For δx = δy = 0 (no effective strong convexity), the regularizer term is dropped and componentwise budgets follow directly from the general VI theorem, so the results cover the nonstrongly convex-concave regime.
- In the stochastic setting with bounded-variance gradient estimators, the method gives a uniform expected-gap bound in the degenerate regime, and under positive effective curvature it converges to within an explicit noise floor that mini-batching the anchors reduces to O(ε).
- The synthetic experiments reproduce the predicted per-function exponents, with fitted slopes within 4% of 2/(1+3νx), and a tomography benchmark shows runtime gains when the expensive oracle is the genuinely Hölder one.
Reading between the lines
- If the separation is robust, the practical scheduling rule in composite applications with heterogeneous oracle costs becomes immediate: allocate recursion depth to the cheapest component and gradient budget to each function by its own Hölder exponent; the paper's own crossover-cost analysis (sliding wins when one gradient call costs more than roughly 20–40 matrix-vector products) suggests where th
- The machinery suggests an untested extension the paper only lists as future work: estimating ν and H online and making the (δ, L(δ)) conversion adaptive, which would remove the assumption that the Hölder constants are known to the algorithm.
- The boundary normal-vector condition (ζ = 0, ξ = 0 at active smooth anchors) limits the strongly-convex table to saddle points that are interior relative to the anchors; a constraint that binds at the solution would need a correction term, so the most informative next experiment is a boundary-saddle instance.
- The coupling budget being independent of νx and νy hints that the bilinear term is always 'as smooth as the smoothest object in the problem'; if that survives a lower-bound analysis, the separation is structural rather than an artifact of the method.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the bilinearly coupled convex-concave minimax problem min_{x∈X} max_{y∈Y} f(x)+⟨y,Bx⟩−g(y), where f and g have Hölder-continuous (sub)gradients. It develops a recursive sliding method for monotone variational inequalities with finite-sum structure, and specializes it to the bilinear saddle-point problem. The claimed outcome is a componentwise oracle complexity: the numbers of f′-evaluations, g′-evaluations, and B/B^T products are governed separately by the Hölder exponents and constants of f and g and by the spectrum of B, interpolating from nonsmooth O(ε^{-2}) rates to smooth accelerated rates. The paper also treats nonstrongly convex, mixed, and stochastic regimes, and reports synthetic and tomographic experiments supporting the separation of oracle counts across Hölder exponents.
Significance. If the stated results hold, they extend the smooth separated-complexity framework of Borodich et al. (2025) to Hölder-smooth components and provide the first per-oracle separation across the Hölder spectrum for bilinearly coupled minimax problems. The VI-level analysis in Section 3 is self-contained, derives explicit constants without fitted parameters, and correctly recovers known smooth rates at ν=1. The numerical section gives reproducible-seeming experiments and separates the f′ and g′ budgets as predicted. However, the most prominent strongly convex results rest on restrictive boundary conditions that are not reflected in the abstract or Table 1, and the stochastic positive-curvature row is proven only in a narrower setting than the table states. The headline contribution is therefore narrower than presented, though the underlying recursive-sliding idea appears sound under the stated theorem-level assumptions.
major comments (3)
- [§4, Theorem 4.4, Remark 2, Appendix H; Corollary 4.5 / Table 1] The zero-normal condition ζ=0 when βx>0 and ξ=0 when βy>0 is load-bearing and cannot be removed. In the proof of Theorem 4.4, after defining E, the lower bound on the p3 quadratic is converted to a useful term only through the step 'For active coefficients, the normal conditions ... and (28) give Bx*=g′(y*) and B^Ty*=−f′(x*)'. Without this step the bound retains the uncontrolled residual −βx∥Bx*−g′(yin)∥²−βy∥B^Ty*+f′(xin)∥², which at zin=z* equals −βx∥ζ∥²−βy∥ξ∥² and cannot be absorbed into Ψ(zin). This is not a corner case: take X=Y=[−1,1], f(x)=−10x, g(y)=0, B=1, νx=νy=1, Hx=10, Hy=1, Lxy=2, µxy=µyx=1. Then all numerical hypotheses of Theorem 4.4 except the zero-normal condition hold (δx=1, δy=0.1, βx=1/4, βy=1/40, range and ambient-smoothness conditions are satisfied), yet the unique saddle point (1,1) has ξ=9 and ζ=1. Thus Theorem 4.4 does not apply to this valid smooth, strongly-curv
- [§K.3 and Table 3] The stochastic strongly convex row of Table 3 is not proven for the generality that the table suggests. The proof in K.3 assumes X=R^{dx}, Y=R^{dy}, µx>0, µy>0, and explicitly sets µxy=µyx=0, so δx=µx and δy=µy. The table, however, states the δx>0, δy>0 rates without restricting the source of the effective curvature. When the positive curvature comes solely from the coupling, i.e. µxy>0 or µyx>0, the contraction argument in K.3 does not go through: the lower bound used there relies on ambient strong convexity of f and g, not on the coupling-induced regularizer, and the range/normal-cone machinery needed for the coupling-curvature case is not developed for the stochastic setting. The table should be restricted to the case actually proved, or the stochastic proof must be extended to cover coupling-induced effective curvature.
- [§4, 'Ambient smoothness for active anchor terms' and Assumptions 4.1–4.2] The ambient-smoothness requirement is another load-bearing restriction. Assumptions 4.1 and 4.2 only impose Hölder smoothness on the restriction of f to X and g to Y, but the proof of Theorem 4.4 uses equation (20), which requires the full-space Lipschitz-gradient inequality for every active smooth anchor. The paper does state this in an unnumbered paragraph after Assumption 4.3, and the abstract mentions that a smooth component used in the coupling regularizer must be smooth in the ambient space. Nevertheless, this means the strongly convex smooth rates O(√κx), O(√κy) do not apply to functions that are merely smooth on the feasible set, which is a common situation for constrained problems. This restriction should be promoted into Assumptions 4.1–4.2 (or a single named standing assumption) and should be repeated in the statements of Table 1 and the abstract, since the current presentatio
minor comments (4)
- [Section 5 / Appendix L.1] The synthetic experiments set µx=µy=µxy=µyx=0 and thus δx=δy=0, so they validate the degenerate rates of Corollary 3.6/Table 4, not the strongly convex rates of Table 1. The abstract's phrase 'numerical experiments reproduce the predicted Hölder exponents' should be qualified to state that the strongly convex regime is not tested.
- [§K.3, paragraph after Eq. (32)] The statement 'Thus the strongly convex block of Table 3 gives ε-accuracy when Δanc=O(ε)' is accurate only for the full-space, ambiently smooth, µx,µy>0 setting; in the printed text this paragraph appears before the full set of K.3 assumptions and could be misread as applying to the general δx,δy>0 case.
- [Appendix F, proof of Corollary 3.6] The relabeling step says 'performing no more than CnRi evaluations' but the construction of the nested budgets uses Ri≥1; this is fine, but the constants κn=2^{2n+2} and Cn=2^{2n+4} differ from the experimental choice κn=1. Appendix L notes this and reports one nonsmooth row 6% above target; the relation between the theorem's sufficient constants and the experimental implementation should be stated explicitly in the main text.
- [Section 4, Eq. (21)–(22)] The definitions βx=1{νy=1}/(4Ly) and βy=1{νx=1}/(4Lx) are asymmetric relative to the notation 'βx' and 'βy'; a reader could expect βx to be associated with the x-block. A sentence explaining that βx scales the x-block quadratic term and uses the smoothness of g (via Ly) would help.
Circularity Check
No circularity: the Hölder sliding bounds are derived from stated assumptions with self-contained proofs.
full rationale
The derivation chain is self-contained. Theorem 3.3 is proved in Appendix D for the inexact-oracle finite-sum VI, and Theorem 3.5/Corollary 3.6 follow by Lemma E.1 (Hölder-to-inexact oracle) and standard balancing, with no fitted parameter renamed as a prediction. The bilinear specialization (Theorem 4.4, Appendix H) starts from Assumptions 4.1–4.3, constructs the anchor-regularized p3, and applies Theorem 3.3 with comparator z*; the resulting N_f, N_g, N_B bounds are obtained by balancing κx/Nf^2, κy/Ng^2, κxy/NB^2 and √κxy/NB against oracle tolerances, not by assuming the conclusion. Restarting in Corollary 4.5 is standard. The cited Borodich et al. (2025) work supplies the recursive sliding template and the smooth-case comparison, but the convergence theorem used here is reproved in the appendix, so the self-citation is not load-bearing. The ζ=0/ξ=0 boundary condition is an explicit hypothesis, not a circular reduction: the proof uses it to activate the anchor identities, and Table 1 inherits it through Corollary 4.5's reference to Theorem 4.4. Experiments fit empirical exponents and compare them to the theoretical formula, which is a validation, not a circular re-derivation. No equation in the paper defines a predicted quantity in terms of itself or of a fitted parameter.
Assumptions & free parameters
assumptions (6)
- domain assumption Hölder continuity and strong convexity of f and g on X and Y (Assumptions 4.1-4.2).
- domain assumption Spectral bounds and range conditions of Assumption 4.3: ∂f(x) ⊆ range(B^T), ∂g(y) ⊆ range(B), X+ker B = X, Y+ker B^T = Y, with bounds on μxy, μyx, Lxy.
- domain assumption Ambient-space smoothness for active anchor terms: if νx=1 then ∇f is Hx-Lipschitz on R^dx; if νy=1 then ∇g is Hy-Lipschitz on R^dy.
- domain assumption Zero normal-vector conditions at the saddle point: ζ=0 when βx>0 and ξ=0 when βy>0.
- domain assumption Exact projections and exact solution of proximal subproblems (Assumption C.1).
- domain assumption For stochastic results: unbiased bounded-variance gradient oracles (Assumption K.1); in the positive-curvature regime, full-space domains and μxy=μyx=0.
Cite this review
Pith. "Pith review of Sliding Methods for H\"older-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling." pith.science (2026). https://pith.science/paper/2L6AFKDB
@misc{pith2026260803846,
author = {Pith},
title = {Pith review of: Sliding Methods for H\"older-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling},
year = {2026},
howpublished = {\url{https://pith.science/paper/2L6AFKDB}},
note = {Machine review of arXiv:2608.03846}
}
abstract
We study convex-concave minimax optimization problems with bilinear coupling of the form $\min_{x\in \mathcal X}\max_{y\in \mathcal Y} \; f(x)+\langle y,\mathbf{B}x\rangle-g(y),$ where the functions $f$ and $g$ have H\"older continuous (sub)gradients. This setting covers a broad range of regimes, from nonsmooth problems with bounded subgradient variation to smooth problems with Lipschitz continuous gradients; for a smooth component used in the coupling-induced regularizer, its Lipschitz-gradient constant is assumed to hold in the ambient space. We propose a sliding method that exploits the composite structure of the problem by querying the oracles associated with $f$, $g$, and the bilinear coupling operator at prescribed frequencies determined by their individual properties. The method is based on a recursive sliding scheme for monotone variational inequalities. We establish convergence guarantees under H\"older continuity and show how the resulting complexity bounds depend explicitly on the H\"older exponents, H\"older constants, strong convexity parameters, and spectral properties of the coupling matrix. Our analysis covers nonstrongly convex and partially strongly convex regimes. For stochastic problems, we prove a uniform expected-gap bound in the degenerate regime and, under ambient smoothness and positive effective curvature, convergence up to an explicit noise floor. Numerical experiments reproduce the predicted H\"older exponents and confirm that the number of gradient evaluations required for each function separates according to its own smoothness level rather than the worse of the two. A tomographic benchmark shows runtime gains when gradient evaluations are more expensive than the additional matrix-vector products.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Forty-second International Conference on Machine Learning , year =
On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms , author =. Forty-second International Conference on Machine Learning , year =
-
[2]
international conference on machine learning , pages =
Optimal algorithms for smooth and strongly convex distributed optimization in networks , author =. international conference on machine learning , pages =. 2017 , organization =
work page 2017
-
[3]
Mathematical Programming , volume =
Communication-efficient algorithms for decentralized and stochastic optimization , author =. Mathematical Programming , volume =. 2020 , publisher =
work page 2020
-
[4]
Advances in Neural Information Processing Systems , volume =
Optimal algorithms for non-smooth distributed optimization in networks , author =. Advances in Neural Information Processing Systems , volume =
-
[5]
The extragradient method for finding saddle points and other problems , author =. Matecon , volume =
-
[6]
SIAM Journal on Optimization , volume =
Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems , author =. SIAM Journal on Optimization , volume =. 2004 , publisher =
work page 2004
-
[7]
Journal of Optimization Theory and Applications , volume =
Generalized Mirror Prox Algorithm for Monotone Variational Inequalities: Universality and Inexact Oracle , author =. Journal of Optimization Theory and Applications , volume =. 2022 , publisher =
work page 2022
-
[8]
Journal of mathematical imaging and vision , volume =
A first-order primal-dual algorithm for convex problems with applications to imaging , author =. Journal of mathematical imaging and vision , volume =. 2011 , publisher =
work page 2011
Show all 35 references
-
[9]
submitted to SIAM Journal on Optimization , volume =
On accelerated proximal gradient methods for convex-concave optimization , author =. submitted to SIAM Journal on Optimization , volume =
-
[10]
Mathematical Programming , volume =
On lower iteration complexity bounds for the convex concave saddle point problems , author =. Mathematical Programming , volume =. 2022 , publisher =
2022
-
[11]
International conference on machine learning , pages =
Linear lower bounds and conditioning of differentiable games , author =. International conference on machine learning , pages =. 2020 , organization =
2020
-
[12]
The 22nd International Conference on Artificial Intelligence and Statistics , pages =
Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity , author =. The 22nd International Conference on Artificial Intelligence and Statistics , pages =. 2019 , organization =
2019
-
[13]
2003 , publisher =
Finite-dimensional variational inequalities and complementarity problems , author =. 2003 , publisher =
2003
-
[14]
Mathematical Programming , volume =
Dual extrapolation and its applications to solving variational inequalities and related problems , author =. Mathematical Programming , volume =. 2007 , publisher =
2007
-
[15]
Mathematical Programming , volume =
Solving variational inequalities with monotone operators on domains given by linear minimization oracles , author =. Mathematical Programming , volume =. 2016 , publisher =
2016
-
[16]
Mathematical Programming , volume =
Accelerated schemes for a class of variational inequalities , author =. Mathematical Programming , volume =. 2017 , publisher =
2017
-
[17]
Mathematical Programming , volume =
Gradient sliding for composite optimization , author =. Mathematical Programming , volume =. 2016 , publisher =
2016
-
[18]
Computational Optimization and Applications , volume =
Accelerated gradient sliding for structured convex optimization , author =. Computational Optimization and Applications , volume =. 2022 , publisher =
2022
-
[19]
Mathematical programming , volume =
An optimal randomized incremental gradient method , author =. Mathematical programming , volume =. 2018 , publisher =
2018
-
[20]
Journal of Inverse and Ill-posed Problems , volume =
Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems , author =. Journal of Inverse and Ill-posed Problems , volume =
-
[21]
Advances in Neural Information Processing Systems , volume =
Optimal and practical algorithms for smooth and strongly convex decentralized optimization , author =. Advances in Neural Information Processing Systems , volume =
-
[22]
Mathematical Programming , volume =
Universal gradient methods for convex optimization problems , author =. Mathematical Programming , volume =. 2015 , publisher =
2015
-
[23]
Mathematical programming , volume =
Smooth minimization of non-smooth functions , author =. Mathematical programming , volume =. 2005 , publisher =
2005
-
[24]
Advances in Neural Information Processing Systems , volume =
A Universal Primal-Dual Convex Optimization Framework , author =. Advances in Neural Information Processing Systems , volume =
-
[25]
Journal of Optimization Theory and Applications , volume=
A universal accelerated primal--dual method for convex optimization problems , author=. Journal of Optimization Theory and Applications , volume=. 2024 , publisher=
2024
-
[26]
arXiv preprint arXiv:2603.23492 , year =
Universal and Parameter-free Gradient Sliding for Composite Optimization , author =. arXiv preprint arXiv:2603.23492 , year =
-
[27]
Mathematical Programming , volume =
First-order methods of smooth convex optimization with inexact oracle , author =. Mathematical Programming , volume =. 2014 , publisher =
2014
-
[28]
Computational Mathematics and Mathematical Physics , volume =
Universal method for stochastic composite optimization problems , author =. Computational Mathematics and Mathematical Physics , volume =. 2018 , publisher =
2018
-
[29]
International conference on machine learning , pages =
Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's algorithm , author =. International conference on machine learning , pages =. 2018 , organization =
2018
-
[30]
1983 , publisher =
Problem complexity and method efficiency in optimization , author =. 1983 , publisher =
1983
-
[31]
2013 , publisher =
Introductory lectures on convex optimization: A basic course , author =. 2013 , publisher =
2013
-
[32]
arXiv preprint arXiv:2111.00996 , year =
Mirror-prox sliding methods for solving a class of monotone variational inequalities , author =. arXiv preprint arXiv:2111.00996 , year =
-
[33]
Stochastic Systems , volume=
Solving variational inequalities with stochastic mirror-prox algorithm , author=. Stochastic Systems , volume=. 2011 , publisher=
2011
-
[34]
Advances in Neural Information Processing Systems , volume=
Accelerated primal-dual gradient method for smooth and convex-concave saddle-point problems with bilinear coupling , author=. Advances in Neural Information Processing Systems , volume=
-
[35]
arXiv preprint arXiv:2103.09344 , year =
On accelerated methods for saddle-point problems with composite structure , author =. arXiv preprint arXiv:2103.09344 , year =
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.