acceptodds
Under review as a conference paper at ICLR 2027

Finding Second-Order Stationary Points of Nonconvex—Strongly-Concave Minimax Problems under Weaker Smoothness Assumption

Abstract

Most existing studies on computing second-order stationary points of minimax problems focus on the nonconvex–-strongly-concave setting under higher-order smoothness assumptions. We adopt the notion of Goldstein approximate second-order stationarity and, for the first time, extend the study of second-order stationarity to the weaker setting where the objective is only continuously differentiable with a Lipschitz continuous gradient. Specifically, we propose a first-order method, called Smoothed Minimax Cubic Newton (SMCN), for finding an -Goldstein approximate second-order stationary point of the primal function. We show that with high probability, SMCN requires at most outer iterations and first-order oracle calls, where denotes the Lipschitz constant of the gradient, is the condition number, and is the primal dimension. We conduct numerical experiments to further demonstrate the effectiveness of the proposed method.

Primary area:
optimization
Keywords:
Second-Order Stationary Points, Nonconvex---Strongly-Concave Minimax Problems, First-Order Method

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_255DOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. 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.
  3. 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.
Reviewer_e6QNOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies second-order stationarity in nonconvex strongly convex minimax optimization under the weaker assumption that the objective has a Lipschitz-continuous gradient, without requiring a Lipschitz-continuous Hessian or even twice continuous differentiability. Since the primal function may not be twice differentiable, the authors adopt Goldstein approximate second-order stationarity as the convergence criterion.

The authors propose a Smoothed Minimax Cubic Newton which combines randomized smoothing, accelerated gd for approximate inner maximization, and cubic-regularized Newton updates using gradient and Hessian estimators constructed entirely from first-order information. They establish high-probability convergence to an ε\varepsilon-Goldstein approximate second-order stationary point with an outer iteration complexity provided and first-order oracle complexity provided as well. Numerical experiments on a synthetic nonconvex strongly convex minimax problem demonstrate improved escape from non-minimizing stationary regions compared with gradient descent ascent.

Critical strengths
  • The main contribution is extending second-order stationarity guarantees for nonconvex strongly convex minimax optimization to objectives with only Lipschitz-continuous gradients. Previous approaches generally require higher-order differentiability or Hessian regularity. Establishing high-probability convergence to a Goldstein approximate second order stationary point under this weaker setting addresses a meaningful gap in the existing optimization literature

  • The convergence analysis carefully accounts for two distinct sources of error: stochastic estimation of the smoothed primal gradient and Hessian, and approximation error introduced by solving the inner maximization problem. The warm-start accelerated gradient procedure, estimator concentration bounds, and oracle complexity guarantees provide a clean framework for extending smoothing based second-order methods to minimax problems where exact primal gradients are unavailable which is an interesting setting.

Critical weaknesses
  • the proposed approach is largely built upon existing randomized smoothing and cubic Newton techniques particularly the framework of Guan and So (2026), together with established smoothness properties of nonconvex strongly convex minimax primal objectives. Although accommodating inexact inner maximization requires additional analysis, the paper does not appear to sufficiently distinguish the conceptual novelty of this extension from a relatively direct combination of existing results.

  • the first-order oracle complexity has unfavorable dependencies on the condition number, dimension, and target accuracy, particularly the ε−9\varepsilon^{-9} term. Each outer iteration also requires many inner optimization solves, construction of a dense Hessian estimator, and solution of a cubic subproblem which are all costly in their own right. The paper does not establish whether the resulting approach is computationally competitive with simpler alternatives.

  • the numerical evaluation is restricted to a single low-dimensional synthetic problem with two carefully selected initializations, comparing the proposed method only against standard GDA. Since the initializations are deliberately chosen near stationary regions where unperturbed gradient methods progress slowly, the observed advantage is not enough to establish robust or general improvements.

  • comparisons against perturbation-based first-order methods, experiments across different dimensions and condition numbers, and evaluations from more diverse initializations are absent. the empirical results also don't directly evaluate the attained Goldstein stationarity conditions or investigate how the theoretical oracle complexity translates into actual computational costs which restricts the implications for practitioners

Guan and So 2026: https://arxiv.org/abs/2607.24122

Questions for authors
  • To what extent can the main convergence guarantee be obtained by directly applying the randomized smoothing framework of Guan and So (2026) to the primal function using approximate inner maximization to construct inexact gradient evaluations? Could the authors explain which parts of the analysis cannot be recovered through a direct application of existing results?
  • The theoretical guarantees rely on parameter choices involving quantities that may not be available in practice - Can these parameters be replaced by computable bounds or adaptive procedures while preserving the stated guarantees?
  • Do the observed improvements persist across higher-dimensional problems, different condition numbers, and randomized initializations?
Reviewer_YKyQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studied NC-SC minimax problem, aiming to find second-order stationary points with only first-oracle oracle when the objective function is not twice continuously differentiable. This work proposed SMCN method based on randomized smoothing to compute the approximate Goldstein SOSP of the primal function. It also derives the sample complexity of the proposed methods. Numerical experiment results are also provided to validate the performance of the proposed algorithm.

Critical strengths
  1. Extend existing study by relaxing the differentiablity assumption to that the objective function is not twice continuously differentiable.
  2. Explicit complexity results are provided to quantify the convergence rate of the proposed algorithm in the high-probability regime.
Critical weaknesses
  1. One of the closest related work should be Guan and So (2026a) as authors cited, the present complexity results in the current submission should be able to derive from Guan and So (2026a, Theorem 4.2 therein), by substituting L=(κ+1)ℓL=(\kappa+1)\ell and adding an accelerated inner-solve cost of O~(κ)\widetilde O(\sqrt{\kappa}) reproduces the submitted exponents. So I will concern the novelty of the current results appears to be a bit incremental.
  2. The numerical experiment appears to be a bit weak. First the problem is only synthetic, especially regarding the separable structure on the nonconvex component ω(x3)\omega(x_3). Second, the experiments report only the primal optimality gap and the trajectory of one coordinate, without evaluating the Goldstein SOSP studied in the theory (or a suitable alternative). Also the experiment only applied GDA as the baseline, making it difficult to isolate the benefits of the proposed method's different components.
Questions for authors
  1. As mentioned in #1 above, I fear that the main theoretical results may be a bit incremental, so it may be better to add more clarification on the technical difficulty to distinguish the current work from existing results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.