- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies nonconvex-strongly-concave minimax optimization when the joint objective has a Lipschitz continuous gradient but need not be twice continuously differentiable. The authors propose Smoothed Minimax Cubic Newton (SMCN), which approximately solves the inner maximization by accelerated gradient descent, applies randomized smoothing to the primal function, constructs gradient and Hessian estimators from first-order evaluations of the minimax objective, and takes cubic-regularized outer steps. The analysis controls both sampling error and the error caused by inexact inner solutions. With high probability, the method returns an epsilon-Goldstein approximate second-order stationary point of the primal function. For equal stationarity and smoothing tolerances, the stated bounds are O-tilde(kappa^4 ell^4 n epsilon^-5) outer iterations and O-tilde(kappa^8.5 ell^8 n^2 epsilon^-9 + kappa^6.5 ell^6 n^3 epsilon^-7) first-order oracle calls. A synthetic example illustrates escape from a strict local maximum and from a nonsmooth boundary of a flat stationary region.
Critical strengths
- The paper addresses a meaningful gap between first-order NC-SC minimax theory and second-order guarantees that normally require twice differentiability or Hessian regularity. The resulting guarantee uses only first-order oracle evaluations of the original minimax objective.
- The analysis explicitly couples two nontrivial error sources: randomized estimation of the smoothed primal derivatives and inexact solution of the inner maximization problems. The two-stage warm start and high-probability error control provide a coherent minimax realization of the smoothing-based cubic framework.
Critical weaknesses
- Several theoretical parameter choices are not directly implementable from the stated assumptions. In particular, T_0 requires ||y*(x_0)|| and the prescribed batch sizes require K* and hence an unknown optimal-value gap. The use of such quantities is common in nonadaptive complexity statements, but the paper should clarify whether known upper bounds are assumed, whether the result is only an a priori guarantee, or whether an adaptive or residual-based implementation can be provided and analyzed.
- The paper builds directly on the smoothing and cubic-regularization framework of Guan and So (2026a). The minimax-specific contribution is the construction of approximate primal gradient and Hessian estimators through inexact inner maximization and the associated error analysis. The stated oracle complexity has high polynomial dependence on kappa, ell, n, and epsilon^{-1}, while Table 1 compares assumptions and stationarity notions but does not isolate the minimax-specific overhead. A decomposition that separates the inherited exact-primal-oracle cost from the additional cost of the inner maximization would make the novelty and scope easier to assess. The numerical example is useful as an illustration, but it is not evidence of broad practical competitiveness; I do not regard this as a central weakness for a primarily theoretical paper.
Questions for authors
- Can Theorem 4.2 be stated with inf_x P_sigma(x), and can the complexity corollary explicitly identify the dependence on Delta_sigma = P_sigma(x_0) - inf_x P_sigma(x), or give a uniform epsilon-independent upper bound for this quantity?
- Can the authors discuss how the method could be implemented without knowing ||y*(x_0)|| and K*? In particular, would a residual-based stopping rule or an adaptive batch-size schedule preserve the stated high-probability complexity up to logarithmic factors? Please also clarify whether the current theorem is intended as an a priori nonadaptive guarantee or as a directly implementable procedure.
- Relative to the exact-primal-oracle framework of Guan and So (2026a), which factors in the final oracle complexity are specifically introduced by the inner maximization and its inexactness? A decomposition or comparison that isolates this overhead would materially clarify the technical contribution.