pith. sign in

arxiv: 2604.19462 · v1 · submitted 2026-04-21 · 🧮 math.OC

Solving Convex-Concave Problems with tilde{mathcal{O}}(ε^(-4/(3p+1))) pth-Order Oracle Complexity

Lesi Chen , Xinliang Zhang , Chengchang Liu , Junru Li , Luo Luo , Jingzhao Zhang This is my paper

Pith reviewed 2026-05-10 01:59 UTC · model grok-4.3

classification 🧮 math.OC
keywords convex-concave minimax problemshigher-order oracle complexityMonteiro-Svaiter accelerationminimax optimizationp-th order smoothnessacceleration techniques
0
0 comments X

The pith

Monteiro-Svaiter acceleration achieves Õ(ε^{-4/(3p+1)}) p-th order oracle complexity for convex-concave minimax problems

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that convex-concave minimax problems whose objective has Lipschitz continuous p-th order derivatives can be solved with Õ(ε^{-4/(3p+1)}) p-th order oracle calls. This improves on the previously known O(ε^{-2/(p+1)}) bound that came from generalizing optimal first-order methods. The authors also prove a matching-style lower bound of Ω(ε^{-2/(3p-1)}), which shows the new upper bound is not yet tight when p is at least 2. Readers care because the result gives a concrete, faster way to solve smooth minimax problems that appear in game theory, robust optimization, and machine learning whenever higher-order derivatives can be evaluated.

Core claim

When the objective has Lipschitz continuous p-th order derivatives, convex-concave minimax problems can be solved with Õ(ε^{-4/(3p+1)}) p-th order oracle calls by applying the Monteiro-Svaiter acceleration. This improves upon the prior O(ε^{-2/(p+1)}) bound. The authors also establish a lower complexity bound of Ω(ε^{-2/(3p-1)}), leaving a gap for p ≥ 2.

What carries the argument

Monteiro-Svaiter acceleration, which accelerates higher-order methods by solving an auxiliary optimization problem at each iteration to select the extrapolation parameter or step.

Load-bearing premise

The objective has p-th order derivatives that are Lipschitz continuous, and the Monteiro-Svaiter acceleration extends directly to the convex-concave minimax setting.

What would settle it

A specific convex-concave problem with Lipschitz p-th derivatives on which the accelerated method requires Ω(ε^{-2/(p+1)}) oracle calls instead of the claimed Õ(ε^{-4/(3p+1)}).

read the original abstract

When the objective has Lipschitz continuous $p$th-order derivatives, it is known that convex-concave minimax problems can be solved with $\mathcal{O}(\epsilon^{-2/(p+1)})$ $p$th-order oracle calls. This complexity upper bound was speculated to be optimal as it is achieved by a natural generalization of the optimal first-order method. In this work, we show an improved upper bound of $\tilde{\mathcal{O}}(\epsilon^{-4/(3p+1)})$ by applying the Monteiro-Svaiter acceleration. We also establish a lower complexity bound of $\Omega(\epsilon^{-2/(3p-1)})$, suggesting a gap still exists for $p \ge 2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that convex-concave minimax problems with Lipschitz continuous p-th order derivatives can be solved with an improved p-th-order oracle complexity of Õ(ε^{-4/(3p+1)}) by applying the Monteiro-Svaiter acceleration framework, improving on the prior O(ε^{-2/(p+1)}) bound. It also establishes a lower bound of Ω(ε^{-2/(3p-1)}), leaving a gap for p ≥ 2.

Significance. If the central extension holds, the result would meaningfully advance higher-order methods for saddle-point problems by showing that acceleration from the convex minimization setting can be adapted to monotone operators arising from convex-concave objectives. The explicit provision of both improved upper and lower bounds is a strength, as is the parameter-free nature of the derived rates.

major comments (2)
  1. [§3] §3 (Main acceleration result): The claim that Monteiro-Svaiter acceleration extends directly to the convex-concave setting without additional structural assumptions is load-bearing for the improved upper bound. The manuscript must explicitly show that the p-th-order regularized model of the monotone operator preserves the necessary monotonicity and that the potential function decreases at the claimed rate; the abstract's statement that this occurs 'without additional structural assumptions' requires a self-contained verification step that is not visible from the high-level description.
  2. [Theorem 4.1] Theorem 4.1 (upper bound): The Õ(ε^{-4/(3p+1)}) rate is obtained by invoking the Monteiro-Svaiter framework, but the analysis should include a precise statement of how the p-th-order oracle is used to solve the regularized subproblem and confirm that no hidden Lipschitz assumption on the (p+1)-th derivative is implicitly required for the potential decrease.
minor comments (2)
  1. [Introduction] The notation for the Õ and Ω bounds should be defined explicitly in the introduction or preliminaries section for readers unfamiliar with the tilde notation in complexity analysis.
  2. [Table 1] Table 1 (complexity comparison): Ensure the rows for different p values include the exact exponents for both the new upper bound and the lower bound to facilitate direct comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We believe the points raised can be fully addressed by adding explicit verifications and clarifications, and we will revise the paper accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (Main acceleration result): The claim that Monteiro-Svaiter acceleration extends directly to the convex-concave setting without additional structural assumptions is load-bearing for the improved upper bound. The manuscript must explicitly show that the p-th-order regularized model of the monotone operator preserves the necessary monotonicity and that the potential function decreases at the claimed rate; the abstract's statement that this occurs 'without additional structural assumptions' requires a self-contained verification step that is not visible from the high-level description.

    Authors: We agree that the extension of the Monteiro-Svaiter framework requires explicit verification to be fully rigorous. In the revised manuscript, we will insert a self-contained lemma in §3 that directly verifies monotonicity preservation for the p-th-order regularized model of the monotone operator arising from the convex-concave saddle-point problem. We will also expand the potential-function analysis with a complete step-by-step derivation of the decrease rate, relying exclusively on p-th-order Lipschitz continuity of the operator. This will substantiate the claim of no additional structural assumptions. revision: yes

  2. Referee: [Theorem 4.1] Theorem 4.1 (upper bound): The Õ(ε^{-4/(3p+1)}) rate is obtained by invoking the Monteiro-Svaiter framework, but the analysis should include a precise statement of how the p-th-order oracle is used to solve the regularized subproblem and confirm that no hidden Lipschitz assumption on the (p+1)-th derivative is implicitly required for the potential decrease.

    Authors: We will revise the proof of Theorem 4.1 to include an explicit description of the approximate solution procedure for the regularized subproblem using the p-th-order oracle. The analysis will be updated to state clearly that the potential decrease relies only on the given p-th-order Lipschitz assumption; no Lipschitz continuity of the (p+1)-th derivative is invoked or needed at any step. We will add a short remark confirming the absence of such hidden assumptions. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation; bounds obtained by external acceleration technique and separate lower-bound construction

full rationale

The paper's upper bound is obtained by adapting the Monteiro-Svaiter acceleration (an external prior technique) to the p-th-order convex-concave setting under the stated Lipschitz assumption on derivatives; this is an application rather than a self-referential fit or redefinition. The lower bound Ω(ε^{-2/(3p-1)}) is derived independently via a standard information-based complexity argument. No equations reduce to their own inputs by construction, no load-bearing self-citations appear, and no ansatz or uniqueness claim is smuggled via prior author work. The derivation chain is self-contained against the given assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard assumption of p-th order Lipschitz continuity and the applicability of Monteiro-Svaiter acceleration to the minimax setting. No free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The objective function has Lipschitz continuous p-th order derivatives.
    Stated in the first sentence of the abstract as the setting under which the complexity bounds hold.

pith-pipeline@v0.9.0 · 5441 in / 1280 out tokens · 27419 ms · 2026-05-10T01:59:49.756802+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

67 extracted references · 4 canonical work pages

  1. [1]

    Optimal methods for higher-order smooth monotone variational inequalities.arXiv preprint arXiv:2205.06167, 2022

    Deeksha Adil, Brian Bullins, Arun Jambulapati, and Sushant Sachdeva. Optimal methods for higher-order smooth monotone variational inequalities.arXiv preprint arXiv:2205.06167, 2022

    work page arXiv 2022

  2. [2]

    Convex optimization withp-norm oracles.arXiv preprint arXiv:2410.24158, 2024

    Deeksha Adil, Brian Bullins, Arun Jambulapati, and Aaron Sidford. Convex optimization withp-norm oracles.arXiv preprint arXiv:2410.24158, 2024

    work page arXiv 2024

  3. [3]

    Oracle complexity of second-order methods for smooth convex optimization.Mathematical Programming, 178(1):327–360, 2019

    Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization.Mathematical Programming, 178(1):327–360, 2019

    2019

  4. [4]

    Complexity of highly parallel non-smooth convex optimization

    Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. InNeurIPS, 2019

    2019

  5. [5]

    Near-optimal method for highly smooth convex optimization

    Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. InCOLT, 2019

    2019

  6. [6]

    Brian Bullins and Kevin A. Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities.SIAM Journal on Optimization, 32(3):2208–2229, 2022

    2022

  7. [7]

    Finite-time last-iterate convergence for learning in multi-player games

    Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. InNeurIPS, 2022

    2022

  8. [8]

    Distributionally robust optimization via ball oracle acceleration

    Yair Carmon and Danielle Hausler. Distributionally robust optimization via ball oracle acceleration. In NeurIPS, 2022

    2022

  9. [9]

    Acceleration with a ball optimization oracle

    Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. InNeurIPS, 2020

    2020

  10. [10]

    Thinking inside the ball: Near-optimal minimization of the maximal loss

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. InCOLT, 2021

    2021

  11. [11]

    Optimal and adaptive monteiro-svaiter acceleration

    Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. InNeurIPS, 2022

    2022

  12. [12]

    RECAPP: Crafting a more efficient catalyst for convex optimization

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. RECAPP: Crafting a more efficient catalyst for convex optimization. InICML, 2022

    2022

  13. [13]

    A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions. InSODA, 2024

    2024

  14. [14]

    Solving convex-concave problems with O(ϵ−4/7)second-order oracle complexity

    Lesi Chen, Chengchang Liu, Luo Luo, and Jingzhao Zhang. Solving convex-concave problems with O(ϵ−4/7)second-order oracle complexity. InCOLT, 2025

    2025

  15. [15]

    Second-order min-max optimization with lazy hessians

    Lesi Chen, Chengchang Liu, and Jingzhao Zhang. Second-order min-max optimization with lazy hessians. InICLR, 2025

    2025

  16. [16]

    Optimal tensor methods in smooth convex and uniformly convexoptimization

    Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, and César A Uribe. Optimal tensor methods in smooth convex and uniformly convexoptimization. In COLT, 2019

    2019

  17. [17]

    Near optimal methods for minimizing convex functions with lipschitzp-th derivatives

    Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, César A Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, et al. Near optimal methods for minimizing convex functions with lipschitzp-th derivatives. InCOLT, 2019. 16

    2019

  18. [18]

    An approximation-based regularized extra-gradient method for monotone variational inequalities.SIAM Journal on Optimization, 35(3):1469–1497, 2025

    Kevin Huang and Shuzhong Zhang. An approximation-based regularized extra-gradient method for monotone variational inequalities.SIAM Journal on Optimization, 35(3):1469–1497, 2025

    2025

  19. [19]

    An optimal high-order tensor method for convex optimization

    Bo Jiang, Haoyue Wang, and Shuzhong Zhang. An optimal high-order tensor method for convex optimization. InCOLT, 2019

    2019

  20. [20]

    An improved cutting plane method for convex optimization, convex-concave games, and its applications

    Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. InSIGACT, 2020

    2020

  21. [21]

    Generalized optimistic methods for convex-concave saddle point problems.arXiv preprint arXiv:2202.09674, 2022

    Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave saddle point problems.arXiv preprint arXiv:2202.09674, 2022

    work page arXiv 2022

  22. [22]

    Online learning guided curvature approximation: A quasi-newton method with global non-asymptotic superlinear convergence

    Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approximation: A quasi-newton method with global non-asymptotic superlinear convergence. InCOLT, 2023

    2023

  23. [23]

    Adaptive and optimal second-order optimistic methods for minimax optimization

    Ruichen Jiang, Ali Kavis, Qiujiang Jin, Sujay Sanghavi, and Aryan Mokhtari. Adaptive and optimal second-order optimistic methods for minimax optimization. InNeurIPS, 2024

    2024

  24. [24]

    Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback.Operations Research, 73(3):1675–1702, 2025

    Michael Jordan, Tianyi Lin, and Zhengyuan Zhou. Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback.Operations Research, 73(3):1675–1702, 2025

    2025

  25. [25]

    The extragradient method for finding saddle points and other problems.Matecon, 12:747–756, 1976

    Galina M Korpelevich. The extragradient method for finding saddle points and other problems.Matecon, 12:747–756, 1976

    1976

  26. [26]

    The first optimal acceleration of high-order methods in smooth convex optimization

    Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. InNeurIPS, 2022

    2022

  27. [27]

    The first optimal algorithm for smooth and strongly-convex- strongly-concave minimax optimization

    Dmitry Kovalev and Alexander Gasnikov. The first optimal algorithm for smooth and strongly-convex- strongly-concave minimax optimization. InNeurIPS, 2022

    2022

  28. [28]

    Monotone inclusions, acceleration, and closed-loop control.Mathematics of Operations Research, 48(4):2353–2382, 2023

    Tianyi Lin and Michael I Jordan. Monotone inclusions, acceleration, and closed-loop control.Mathematics of Operations Research, 48(4):2353–2382, 2023

    2023

  29. [29]

    Tianyi Lin and Michael I. Jordan. Perseus: A simple high-order regularization method for variational inequalities.Mathematical Programming, pages 1–42, 2024

    2024

  30. [30]

    Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In COLT, 2020

    2020

  31. [31]

    Iteration-complexity of a newton proximal extragradient method for monotone variational inequalities and inclusion problems.SIAM Journal on Optimization, 22(3):914–935, 2012

    Renato DC Monteiro and Benar Fux Svaiter. Iteration-complexity of a newton proximal extragradient method for monotone variational inequalities and inclusion problems.SIAM Journal on Optimization, 22(3):914–935, 2012

    2012

  32. [32]

    An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.SIAM Journal on Optimization, 23 (2):1092–1125, 2013

    Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.SIAM Journal on Optimization, 23 (2):1092–1125, 2013

    2013

  33. [33]

    Equilibrium points in n-person games.Proceedings of the national academy of sciences, 36(1):48–49, 1950

    John F Nash Jr. Equilibrium points in n-person games.Proceedings of the national academy of sciences, 36(1):48–49, 1950

    1950

  34. [34]

    Arkadi Nemirovski. Prox-method with rate of convergenceO(1/t)for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems.SIAM Journal on Optimization, 15(1):229–251, 2004

    2004

  35. [35]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  36. [36]

    Dual extrapolation and its applications to solving variational inequalities and related problems.Mathematical Programming, 109(2-3):319–344, 2007

    Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems.Mathematical Programming, 109(2-3):319–344, 2007. 17

    2007

  37. [37]

    Accelerating the cubic regularization of newton’s method on convex problems.Mathe- matical Programming, 112(1):159–181, 2008

    Yurii Nesterov. Accelerating the cubic regularization of newton’s method on convex problems.Mathe- matical Programming, 112(1):159–181, 2008

    2008

  38. [38]

    Lectures on convex optimization

    Yurii Nesterov. Lectures on convex optimization. 137, 2018

    2018

  39. [39]

    Implementable tensor methods in unconstrained convex optimization.Mathematical Programming, 186(1):157–183, 2021

    Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization.Mathematical Programming, 186(1):157–183, 2021

    2021

  40. [40]

    Inexact high-order proximal-point methods with auxiliary search procedure.SIAM Journal on Optimization, 31(4):2807–2828, 2021

    Yurii Nesterov. Inexact high-order proximal-point methods with auxiliary search procedure.SIAM Journal on Optimization, 31(4):2807–2828, 2021

    2021

  41. [41]

    Superfast second-order methods for unconstrained convex optimization.Journal of Optimization Theory and Applications, 191:1–30, 2021

    Yurii Nesterov. Superfast second-order methods for unconstrained convex optimization.Journal of Optimization Theory and Applications, 191:1–30, 2021

    2021

  42. [42]

    arXiv preprint arXiv:2311.15154 , year=

    Yurii Nesterov. High-order reduced-gradient methods for composite variational inequalities.arXiv preprint arXiv:2311.15154, 2023

    work page arXiv 2023

  43. [43]

    Inexact accelerated high-order proximal-point methods.Mathematical Programming, pages 1–26, 2023

    Yurii Nesterov. Inexact accelerated high-order proximal-point methods.Mathematical Programming, pages 1–26, 2023

    2023

  44. [44]

    Cubic regularization of newton method and its global performance

    Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006

    2006

  45. [45]

    Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.Mathematical Programming, 185(1):1–35, 2021

    Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.Mathematical Programming, 185(1):1–35, 2021

    2021

  46. [46]

    A modification of the arrow-hurwicz method for search of saddle points

    Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845–848, 1980

    1980

  47. [47]

    Smoothing functions and smoothing newton method for complementarity and variational inequality problems.Journal of Optimization Theory and Applications, 113:121–147, 2002

    Liqun Qi and Defeng Sun. Smoothing functions and smoothing newton method for complementarity and variational inequality problems.Journal of Optimization Theory and Applications, 113:121–147, 2002

    2002

  48. [48]

    Superlinear convergence of an interior-point method despite dependent constraints.Mathematics of Operations Research, 25(2):179–194, 2000

    Daniel Ralph and Stephen J Wright. Superlinear convergence of an interior-point method despite dependent constraints.Mathematics of Operations Research, 25(2):179–194, 2000

    2000

  49. [49]

    Smoothness parameter of power of euclidean norm.Journal of Optimization Theory and Applications, 185(2):303–326, 2020

    Anton Rodomanov and Yurii Nesterov. Smoothness parameter of power of euclidean norm.Journal of Optimization Theory and Applications, 185(2):303–326, 2020

    2020

  50. [50]

    Optimal algorithms for smooth and strongly convex distributed optimization in networks

    Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. InICML, 2017

    2017

  51. [51]

    On general minimax theorems.Pacific J

    Maurice Sion. On general minimax theorems.Pacific J. Math., 8(4):171–176, 1958

    1958

  52. [52]

    Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I. Jordan. Stochastic cubic regularization for fast nonconvex optimization. InNeurIPS, 2018

    2018

  53. [53]

    Zur hilbertschen beweistheorie.Mathematische Zeitschrift, 26(1):1–46, 1927

    John Von Neumann. Zur hilbertschen beweistheorie.Mathematische Zeitschrift, 26(1):1–46, 1927

    1927

  54. [54]

    Stochastic variance-reduced cubic regularization for nonconvex optimization

    Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan. Stochastic variance-reduced cubic regularization for nonconvex optimization. InAISTATS, 2019

    2019

  55. [55]

    Stochastic online auc maximization

    Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. InNeurIPS, 2016

    2016

  56. [56]

    Mitigating unwanted biases with adversarial learning

    Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. InProceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335–340, 2018

    2018

  57. [57]

    On lower iteration complexity bounds for the convex concave saddle point problems.Mathematical Programming, 194(1-2):901–935, 2022

    Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems.Mathematical Programming, 194(1-2):901–935, 2022

    2022

  58. [58]

    Stochastic variance-reduced cubic regularization methods

    Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularization methods. JMLR, 2019. 18 A Proof of Theorem 3.2 Proof. Let Gaph(z) = h(z) −h (z∗). We prove that the parameter settingT = O (γ/µ)2/(3p+1) ensures that, for alls= 0,· · ·, S−1, each epoch of the algorithm satisfies Gaph(z(s+1))≤ 1 2Gaph(z(s))≤ · · · ≤ 1 2s+1 ∆ =ϵ (s+1),(...

    2019

  59. [59]

    finds a pointˆy∈ Ysuch thatf ϵ(x, ˆy)−Φ(x)≤δwith complexity O Lp +p!µ y µy 2/(3p+1) log D2 Y(L1 +pµ yDp−1 Y ) δ !! .(36)

  60. [60]

    finds a pointˆy∈ Ysuch that∥∇f ϵ(x, ˆy)− ∇Φ(x)∥ ≤δwith complexity O   Lp +p!µ y µy 2/(3p+1) log   D2 Y L1 +pµ yDp−1 Y p+2 µyδp+1     .(37)

  61. [61]

    finds a pointˆx∈ Xsuch thatΨ(y; ¯x)−g ϵ(ˆx,y; ¯x)≤δwith complexity O Lp +p!(γ+µ x) γ+µ x 2/(3p+1) log D2 X (L1 +p(γ+µ x)Dp−1 X ) δ !! .(38)

  62. [62]

    The uniform convexity (concavity) and Lipschitz constants of the objectivesfϵ(x,· )and gϵ( ·,y ; ¯x) are given in Lemma B.1

    finds a pointˆx∈ Xsuch that∥∇ ygϵ(ˆx,y; ¯x)− ∇Ψ(y; ¯x)∥ ≤δwith complexity O   Lp +p!(γ+µ x) γ+µ x log   D2 X L1 +p(γ+µ x)Dp−1 X p+2 µxδp+1     .(39) Proof. The uniform convexity (concavity) and Lipschitz constants of the objectivesfϵ(x,· )and gϵ( ·,y ; ¯x) are given in Lemma B.1. Given these quantities, we can apply Theorem 3.1 to prove all th...

  63. [63]

    We then obtain Eq

    According to Theorem 3.1, the complexity of finding a pointˆy∈ Y such that fϵ(x, ˆy) − Φ(x) ≤δ using OptMS-restart is upper bounded by O Lp +p!µ y µy 2/(3p+1) log fϵ(x,y 0)−Φ(x) δ ! , wherey 0 is the initialization point for the algorithm. We then obtain Eq. (36) by using fϵ(x,y 0)−Φ(x)≤(L 1 +pµ yDp−1 Y )∥y0 −y ∗(x)∥2

  64. [64]

    Therefore, to obtain aδ-first-order oracle ofΦ(x)under Assumption 2.3, it suffices to findˆy∈ Y such that ∥ˆy−y ∗(x)∥ ≤ δ L1 +pµ yDp−1 Y

    By Danskin’s theorem, we have that∇Φ(x) = ∇xfϵ(x,y ∗(x)), where y∗(x) = arg maxy∈Y fϵ(x,y ). Therefore, to obtain aδ-first-order oracle ofΦ(x)under Assumption 2.3, it suffices to findˆy∈ Y such that ∥ˆy−y ∗(x)∥ ≤ δ L1 +pµ yDp−1 Y . Further, by Lemma 2.3 (the second inequality) and Lemma 4.1 (item 1), it only needs to find a point ˆy∈ Ysuch that fϵ(x, ˆy)−...

  65. [65]

    We only need to show that¯f(x,y )is convex- concave in ¯X × ¯Y

    It is apparent that both the sets¯X and ¯Y are convex. We only need to show that¯f(x,y )is convex- concave in ¯X × ¯Y. Let B=   −1 1−1 ... ... 1−1   (53) and e1 = (1, 0,· · ·, 0)⊤. Let ¯g(x,y ) =PT+1 i=1 y[i]xp [i]. This function is convex-concave on the domain RT+1 + ×R T+1 + . Since ¯f(x,y ) = ( Lp/(2p+1p!))¯g(Bx + e1,y )and the affine mapping...

  66. [66]

    (15) by induction

    We prove the property in Eq. (15) by induction. We let RT+1 t ={x∈R T+1 :x [i] = 0, i=t+ 1,· · ·, T+ 1}. Suppose( xt,y t) ∈R T+1 t ×R T+1 t , our goal is to show that(xt+1,y t+1) ∈ (RT+1 t+1 ∩ ¯X ) ×(RT+1 t+1 ∩ ¯Y)when the algorithm lies in the class of Definition 5.1. Note that our hard instance in Eq. (14) is constructed such that for anyq∈ {1,· · ·, p}...

  67. [67]

    For anyz = (x,y ) ∈ ¯X × ¯Y with x[T+1] = y[T+1] = 0, we can use Lemma 2.1 to give a lower bound of the tangent residual via duality gap as follows: DZ rtan ¯F (z)≥ Lp 2p+1p! max y′∈Y ¯f(x,y ′)−min x′∈X ¯f(x ′,y) ≥ Lp 2p+1p! ¯f(x,1)− ¯f(1,y) = Lp 2p+1p! ¯f(x T ,1) = Lp 2p+1p! 1−x [1] p + T−1X i=1 x[i] −x [i+1] p + x[T] p ! ≥ Lp(T+ 1) 2p+1p! 1 T+ 1 1−x [1]...