On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles

Abstract:Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Their known lower bounds cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. They leave open the power of exact component proximal steps, whose responses are global saddle points of regularized component problems and can expose directions that gradients do not reveal. We show that neither unrestricted adaptivity nor exact proximal access improves the polynomial complexity. We consider $n$ components with joint mean-squared smoothness $L$ and condition number $\kappa$, started from a point with primal gap at most $\Delta$ and joint gradient norm at most $\sqrt{2L\Delta}$. For $\varepsilon^2/(L\Delta)$ below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses needs $\Omega(n+\min\{\sqrt n\,\kappa,n^{3/4}\sqrt\kappa\}L\Delta/\varepsilon^2)$ component queries in the worst case to find an $\varepsilon$-stationary point of the value function. A method using only component gradients attains this rate up to a factor $\log^2(2+\kappa)$, including initialization. Zhou (arXiv:2610.04944) concurrently proves the same rate for zero-respecting first-order methods. In our hard instances, every component admits proximal steps with the same step sizes, and a response for a component reveals hidden directions only up to the first one assigned to another component.

50 pages, including appendices and references. Lean 4 formalization of the lower bounds in the ancillary files

Machine Learning (cs.LG)

arXiv:2611.04806 [cs.LG]

(or arXiv:2611.04806v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2611.04806 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

lean_formalization/Audit.lean

lean_formalization/CLAIMS.md

lean_formalization/DependencyAudit.lean

lean_formalization/Minimax/ActualAngles.lean

lean_formalization/Minimax/ActualClass.lean

lean_formalization/Minimax/ActualClassFormula.lean

lean_formalization/Minimax/ActualClassProperties.lean

lean_formalization/Minimax/ActualDual.lean

lean_formalization/Minimax/ActualEndpoint.lean

lean_formalization/Minimax/ActualForcing.lean

lean_formalization/Minimax/ActualPrimalCurvature.lean

lean_formalization/Minimax/ActualSourceNormalization.lean

lean_formalization/Minimax/AdaptiveSearch.lean

lean_formalization/Minimax/AllKappaCalibration.lean

lean_formalization/Minimax/AllKappaConfidence.lean

lean_formalization/Minimax/AllKappaExpected.lean

lean_formalization/Minimax/AllKappaRates.lean

lean_formalization/Minimax/BaselineCanonicalConfidence.lean

lean_formalization/Minimax/BaselineCanonicalExpected.lean

lean_formalization/Minimax/BaselineCanonicalLoss.lean

lean_formalization/Minimax/BaselineCanonicalMain.lean

lean_formalization/Minimax/BaselineCanonicalReply.lean

lean_formalization/Minimax/BlockDifferential.lean

lean_formalization/Minimax/BlockProduct.lean

lean_formalization/Minimax/CalibratedLowerBarrier.lean

lean_formalization/Minimax/CalibratedLowerCapped.lean

lean_formalization/Minimax/CalibratedLowerSigned.lean

lean_formalization/Minimax/CensoredLocalization.lean

lean_formalization/Minimax/CensoredLocalizationCenters.lean

lean_formalization/Minimax/CensoredLocalizationComponent.lean

lean_formalization/Minimax/CensoredLocalizationFlat.lean

lean_formalization/Minimax/CensoredLocalizationFrontier.lean

lean_formalization/Minimax/CensoredLocalizationMask.lean

lean_formalization/Minimax/CensoredLocalizationOwners.lean

lean_formalization/Minimax/CensoredLocalizationSubspace.lean

lean_formalization/Minimax/CensoredProx.lean

lean_formalization/Minimax/CensoredProxAuxiliary.lean

lean_formalization/Minimax/CensoredProxChoice.lean

lean_formalization/Minimax/CensoredProxCoupling.lean

lean_formalization/Minimax/CensoredProxExistence.lean

lean_formalization/Minimax/CensoredProxLocal.lean

lean_formalization/Minimax/CensoredProxPrefix.lean

lean_formalization/Minimax/CensoredProxReflection.lean

lean_formalization/Minimax/CensoredProxStationary.lean

lean_formalization/Minimax/CensoredProxSymmetry.lean

lean_formalization/Minimax/CutoffNorms.lean

lean_formalization/Minimax/CutoffScalar.lean

lean_formalization/Minimax/CutoffSharp.lean

lean_formalization/Minimax/EndpointCorrected.lean

lean_formalization/Minimax/EndpointDamping.lean

lean_formalization/Minimax/EndpointDual.lean

lean_formalization/Minimax/EndpointJoint.lean

lean_formalization/Minimax/EuclideanFamily.lean

lean_formalization/Minimax/EuclideanLowerInstance.lean

lean_formalization/Minimax/EuclideanProx.lean

lean_formalization/Minimax/EuclideanTransport.lean

lean_formalization/Minimax/EuclideanValue.lean

lean_formalization/Minimax/FiniteExceptionalMVT.lean

lean_formalization/Minimax/FiniteIID.lean

lean_formalization/Minimax/FiniteJointPrior.lean

lean_formalization/Minimax/FinitePriorConfidence.lean

lean_formalization/Minimax/FinitePriorCost.lean

lean_formalization/Minimax/FiniteTree.lean

lean_formalization/Minimax/FlatCrossBlocks.lean

lean_formalization/Minimax/FlatCrossComposition.lean

lean_formalization/Minimax/FlatCrossOwned.lean

lean_formalization/Minimax/FlatCrossScalar.lean

lean_formalization/Minimax/FlatPrimalAuxiliary.lean

lean_formalization/Minimax/FlatPrimalClass.lean

lean_formalization/Minimax/FlatPrimalComponent.lean

lean_formalization/Minimax/FlatPrimalConfiguration.lean

lean_formalization/Minimax/FlatPrimalDimension.lean

lean_formalization/Minimax/FlatPrimalGeometry.lean

lean_formalization/Minimax/FlatPrimalLocalization.lean

lean_formalization/Minimax/FlatPrimalMain.lean

lean_formalization/Minimax/FlatPrimalMean.lean

lean_formalization/Minimax/FlatPrimalParameters.lean

lean_formalization/Minimax/FlatPrimalPolynomial.lean

lean_formalization/Minimax/FlatPrimalPrefix.lean

lean_formalization/Minimax/FlatPrimalProjection.lean

lean_formalization/Minimax/FlatPrimalProx.lean

lean_formalization/Minimax/FlatPrimalRotations.lean

lean_formalization/Minimax/FlatPrimalSmooth.lean

lean_formalization/Minimax/FlatPrimalSpaces.lean

lean_formalization/Minimax/FlatPrimalValue.lean

lean_formalization/Minimax/ForcingCompensation.lean

lean_formalization/Minimax/GateBounds.lean

lean_formalization/Minimax/GradientSecond.lean

lean_formalization/Minimax/GraphConcavity.lean

lean_formalization/Minimax/GraphGradient.lean

lean_formalization/Minimax/GraphGradientRMS.lean

lean_formalization/Minimax/GraphNode.lean

lean_formalization/Minimax/GraphRMS.lean

lean_formalization/Minimax/HilbertPair.lean

lean_formalization/Minimax/InitialGap.lean

lean_formalization/Minimax/InitialGradientMean.lean

lean_formalization/Minimax/InitialGradientSource.lean

lean_formalization/Minimax/InnerSecond.lean

lean_formalization/Minimax/LineExceptionalSets.lean

lean_formalization/Minimax/LinearPrecomp.lean

lean_formalization/Minimax/Linewise.lean

lean_formalization/Minimax/LowerCoreAssumptions.lean

lean_formalization/Minimax/LowerCoreComplete.lean

lean_formalization/Minimax/LowerCoreGeometry.lean

lean_formalization/Minimax/LowerCoreMain.lean

lean_formalization/Minimax/LowerCoreTheorem.lean

lean_formalization/Minimax/LowerDimensionCounts.lean

lean_formalization/Minimax/LowerDimensionGeometry.lean

lean_formalization/Minimax/LowerDimensionPolynomial.lean

lean_formalization/Minimax/LowerDimensionSpaces.lean

lean_formalization/Minimax/LowerDimensionTail.lean

lean_formalization/Minimax/LowerDimensionWidth.lean

lean_formalization/Minimax/LowerEuclideanProperties.lean

lean_formalization/Minimax/LowerInstanceFamily.lean

lean_formalization/Minimax/LowerInstanceInitialization.lean

lean_formalization/Minimax/LowerInstanceParameters.lean

lean_formalization/Minimax/LowerOracleExecution.lean

lean_formalization/Minimax/LowerOracleMain.lean

lean_formalization/Minimax/LowerOraclePrefix.lean

lean_formalization/Minimax/LowerOracleProbability.lean

lean_formalization/Minimax/LowerOracleProgram.lean

lean_formalization/Minimax/LowerOracleResponse.lean

lean_formalization/Minimax/LowerParameters.lean

lean_formalization/Minimax/LowerParametersNormalization.lean

lean_formalization/Minimax/LowerParametersPath.lean

lean_formalization/Minimax/LowerParametersRMS.lean

lean_formalization/Minimax/LowerParametersRate.lean

lean_formalization/Minimax/LowerParametersWidth.lean

lean_formalization/Minimax/MiddleActualClass.lean

lean_formalization/Minimax/MiddleActualValue.lean

lean_formalization/Minimax/MiddleCensoredCoupling.lean

lean_formalization/Minimax/MiddleCensoredExistence.lean

lean_formalization/Minimax/MiddleClassComplete.lean

lean_formalization/Minimax/MiddleCoreGeometry.lean

lean_formalization/Minimax/MiddleCoreMain.lean

lean_formalization/Minimax/MiddleCoreSigned.lean

lean_formalization/Minimax/MiddleCoreTheorem.lean

lean_formalization/Minimax/MiddleCostArithmetic.lean

lean_formalization/Minimax/MiddleDimensionCounts.lean

lean_formalization/Minimax/MiddleDimensionGeometry.lean

lean_formalization/Minimax/MiddleDimensionOrder.lean

lean_formalization/Minimax/MiddleDimensionPolynomial.lean

lean_formalization/Minimax/MiddleDimensionSpaces.lean

lean_formalization/Minimax/MiddleDimensionTail.lean

lean_formalization/Minimax/MiddleDimensionWidth.lean

lean_formalization/Minimax/MiddleEuclideanInstance.lean

lean_formalization/Minimax/MiddleEuclideanProperties.lean

lean_formalization/Minimax/MiddleEuclideanProx.lean

lean_formalization/Minimax/MiddleInstanceCapped.lean

lean_formalization/Minimax/MiddleInstanceFamily.lean

lean_formalization/Minimax/MiddleInstanceParameters.lean

lean_formalization/Minimax/MiddleInstanceSigned.lean

lean_formalization/Minimax/MiddleOracleExecution.lean

lean_formalization/Minimax/MiddleOracleMain.lean

lean_formalization/Minimax/MiddleOraclePrefix.lean

lean_formalization/Minimax/MiddleOracleProbability.lean

lean_formalization/Minimax/MiddleOracleProgram.lean

lean_formalization/Minimax/MiddleOracleResponse.lean

lean_formalization/Minimax/MiddleParameters.lean

lean_formalization/Minimax/MiddlePositiveWidth.lean

lean_formalization/Minimax/MiddleValueBarrier.lean

lean_formalization/Minimax/MiddleValueDerivative.lean

lean_formalization/Minimax/MiddleValueInitialization.lean

lean_formalization/Minimax/MiddleZeroValue.lean

lean_formalization/Minimax/ModifiedMeanLocalization.lean

lean_formalization/Minimax/NodeBase.lean

lean_formalization/Minimax/NodeCurvature.lean

lean_formalization/Minimax/NodeCutoff.lean

lean_formalization/Minimax/NodeGlobal.lean

lean_formalization/Minimax/OracleCanonical.lean

lean_formalization/Minimax/OracleModel.lean

lean_formalization/Minimax/OracleTranscript.lean

lean_formalization/Minimax/OwnedEdge.lean

lean_formalization/Minimax/OwnedEdgeCurvature.lean

lean_formalization/Minimax/OwnedEdgeGlobal.lean

lean_formalization/Minimax/OwnedEdgeHessian.lean

lean_formalization/Minimax/OwnerCost.lean

lean_formalization/Minimax/OwnerRun.lean

lean_formalization/Minimax/OwnerRunPrefix.lean

lean_formalization/Minimax/PathCoordinates.lean

lean_formalization/Minimax/PathGraph.lean

lean_formalization/Minimax/PathGreenBounds.lean

lean_formalization/Minimax/PathGreenColumn.lean

lean_formalization/Minimax/PathGreenHyperbolic.lean

lean_formalization/Minimax/PathGreenLinear.lean

lean_formalization/Minimax/PathGreenParameters.lean

lean_formalization/Minimax/PathGreenReflection.lean

lean_formalization/Minimax/PathOwnedRMS.lean

lean_formalization/Minimax/PathSchur.lean

lean_formalization/Minimax/PathSharedBarrier.lean

lean_formalization/Minimax/PositiveWidthActual.lean

lean_formalization/Minimax/PositiveWidthConjugate.lean

lean_formalization/Minimax/PositiveWidthGradient.lean

lean_formalization/Minimax/PositiveWidthOptimizer.lean

lean_formalization/Minimax/PositiveWidthRadius.lean

lean_formalization/Minimax/PositiveWidthTransfer.lean

lean_formalization/Minimax/PositiveWidthValue.lean

lean_formalization/Minimax/PosteriorOwnerCompletion.lean

lean_formalization/Minimax/PosteriorOwnerExecution.lean

lean_formalization/Minimax/PosteriorOwnerPotential.lean

lean_formalization/Minimax/PosteriorOwnerTape.lean

lean_formalization/Minimax/PrefixExposure.lean

lean_formalization/Minimax/PrefixExposureHiding.lean

lean_formalization/Minimax/PrefixOracle.lean

lean_formalization/Minimax/PrefixOracleCoupling.lean

lean_formalization/Minimax/PrefixOracleHiding.lean

lean_formalization/Minimax/PrefixOracleOwners.lean

lean_formalization/Minimax/PrefixOwnerCharging.lean

lean_formalization/Minimax/PrefixOwnerCoupling.lean

lean_formalization/Minimax/PrefixOwnerPosterior.lean

lean_formalization/Minimax/PrefixOwnerRanks.lean

lean_formalization/Minimax/PrefixOwnerSimulation.lean

lean_formalization/Minimax/PrefixOwnerTail.lean

lean_formalization/Minimax/PrefixOwnerTests.lean

lean_formalization/Minimax/PrimalSourceGlobal.lean

lean_formalization/Minimax/PrimalSourceGraph.lean

lean_formalization/Minimax/PrimalSourcePair.lean

lean_formalization/Minimax/PrimalSourcePaper.lean

lean_formalization/Minimax/PrimalSourcePenalty.lean

lean_formalization/Minimax/PrimalSourceScalar.lean

lean_formalization/Minimax/ProxActualExpression.lean

lean_formalization/Minimax/ProxActualGate.lean

lean_formalization/Minimax/ProxAnalyticPrimitive.lean

lean_formalization/Minimax/ProxAnalyticSource.lean

lean_formalization/Minimax/ProxBoundedAtoms.lean

lean_formalization/Minimax/ProxContinuation.lean

lean_formalization/Minimax/ProxDual.lean

lean_formalization/Minimax/ProxExistence.lean

lean_formalization/Minimax/ProxExistenceActual.lean

lean_formalization/Minimax/ProxExistenceComplete.lean

lean_formalization/Minimax/ProxExistenceCore.lean

lean_formalization/Minimax/ProxExistenceGeometry.lean

lean_formalization/Minimax/ProxExistenceLegal.lean

lean_formalization/Minimax/ProxExistencePaper.lean

lean_formalization/Minimax/ProxExistenceQuadratic.lean

lean_formalization/Minimax/ProxExistenceSet.lean

lean_formalization/Minimax/ProxExistenceSmooth.lean

lean_formalization/Minimax/ProxExistenceSubspace.lean

lean_formalization/Minimax/ProxExpressionStrict.lean

lean_formalization/Minimax/ProxFiniteBranches.lean

lean_formalization/Minimax/ProxFlatGates.lean

lean_formalization/Minimax/ProxFlatRemoval.lean

lean_formalization/Minimax/ProxGateBranches.lean

lean_formalization/Minimax/ProxGateExpression.lean

lean_formalization/Minimax/ProxLineRepresentation.lean

lean_formalization/Minimax/ProxMaximizer.lean

lean_formalization/Minimax/ProxObjective.lean

lean_formalization/Minimax/ProxRadialBranch.lean

lean_formalization/Minimax/ProxRegularLine.lean

lean_formalization/Minimax/ProxRestrictedUniqueness.lean

lean_formalization/Minimax/ProxRotations.lean

lean_formalization/Minimax/ProxStrictConvex.lean

lean_formalization/Minimax/ProxUniqueness.lean

lean_formalization/Minimax/PublicCosine.lean

lean_formalization/Minimax/PublicCosineClass.lean

lean_formalization/Minimax/PublicCosineCoordinates.lean

lean_formalization/Minimax/PublicCosineDifferential.lean

lean_formalization/Minimax/PublicCosineDimensions.lean

lean_formalization/Minimax/PublicCosineExecution.lean

lean_formalization/Minimax/PublicCosineFamily.lean

lean_formalization/Minimax/PublicCosineLoss.lean

lean_formalization/Minimax/PublicCosineOracle.lean

lean_formalization/Minimax/PublicCosineProduct.lean

lean_formalization/Minimax/PublicCosineProx.lean

lean_formalization/Minimax/PublicCosineValue.lean

lean_formalization/Minimax/PublicDomination.lean

lean_formalization/Minimax/PublicExtra.lean

lean_formalization/Minimax/PublicPenaltyGradient.lean

lean_formalization/Minimax/PublicPenaltyScalar.lean

lean_formalization/Minimax/PublicRadialHessian.lean

lean_formalization/Minimax/PublicRadialMaps.lean

lean_formalization/Minimax/QuadraticBaseline.lean

lean_formalization/Minimax/QuadraticEmbedded.lean

lean_formalization/Minimax/RMSAssembly.lean

lean_formalization/Minimax/RademacherAxis.lean

lean_formalization/Minimax/RademacherDimension.lean

lean_formalization/Minimax/RademacherProduct.lean

lean_formalization/Minimax/RademacherProjection.lean

lean_formalization/Minimax/RademacherTail.lean

lean_formalization/Minimax/RadialCap.lean

lean_formalization/Minimax/RadialHessian.lean

lean_formalization/Minimax/RadialHinge.lean

lean_formalization/Minimax/RadialHingeHessian.lean

lean_formalization/Minimax/RadialLipschitz.lean

lean_formalization/Minimax/RadialProfiles.lean

lean_formalization/Minimax/RadialThreshold.lean

lean_formalization/Minimax/RankMoments.lean

lean_formalization/Minimax/SVRG.lean

lean_formalization/Minimax/ScalarBounds.lean

lean_formalization/Minimax/ScalarDeadzone.lean

lean_formalization/Minimax/ScalarGate.lean

lean_formalization/Minimax/ScalarSecond.lean

lean_formalization/Minimax/ScalarSource.lean

lean_formalization/Minimax/SearchLaw.lean

lean_formalization/Minimax/SearchTail.lean

lean_formalization/Minimax/SecondDerivative.lean

lean_formalization/Minimax/SerialGeometry.lean

lean_formalization/Minimax/SerialGeometryEvent.lean

lean_formalization/Minimax/SmoothAssembly.lean

lean_formalization/Minimax/SmoothGluing.lean

lean_formalization/Minimax/SparseBlocks.lean

lean_formalization/Minimax/SphericalCoordinates.lean

lean_formalization/Minimax/StoppingMeasure.lean

lean_formalization/Minimax/StrongGradient.lean

lean_formalization/Minimax/SymmetricNorm.lean

lean_formalization/Minimax/TerminalBarrier.lean

lean_formalization/Minimax/TerminalBarrierChain.lean

lean_formalization/Minimax/TerminalBarrierCompact.lean

lean_formalization/Minimax/TerminalBarrierExclusions.lean

lean_formalization/Minimax/TerminalBarrierInverse.lean

lean_formalization/Minimax/TerminalBarrierLocal.lean

lean_formalization/Minimax/TerminalBarrierScalars.lean

lean_formalization/Minimax/ThresholdHessian.lean

lean_formalization/Minimax/TwoNodeCompensation.lean

lean_formalization/Minimax/TwoNodeGreen.lean

lean_formalization/Minimax/TwoNodeOptimizer.lean

lean_formalization/Minimax/TwoNodePaths.lean

lean_formalization/Minimax/TwoNodeRadius.lean

lean_formalization/Minimax/UncutAxes.lean

lean_formalization/Minimax/UncutCompensation.lean

lean_formalization/Minimax/UncutEndpoint.lean

lean_formalization/Minimax/UncutEnergy.lean

lean_formalization/Minimax/UncutOptimizer.lean

lean_formalization/Minimax/UncutPaths.lean

lean_formalization/Minimax/UncutRadius.lean

lean_formalization/Minimax/UncutValue.lean

lean_formalization/Minimax/UnifiedHighParameters.lean

lean_formalization/Minimax/UnifiedPrimalCurvature.lean

lean_formalization/Minimax/ValueCapBounds.lean

lean_formalization/Minimax/ValueCapNormalization.lean

lean_formalization/Minimax/ValueChain.lean

lean_formalization/Minimax/ValueChainFinite.lean

lean_formalization/Minimax/ValueChainPenalty.lean

lean_formalization/Minimax/ValueChainResidual.lean

lean_formalization/Minimax/ValueChainSource.lean

lean_formalization/Minimax/ValueCoreBound.lean

lean_formalization/Minimax/ValueNormalization.lean

lean_formalization/Minimax/ValueNormalizedBlock.lean

lean_formalization/Minimax/ValuePaperRadius.lean

lean_formalization/Minimax/ValuePositiveBarrier.lean

lean_formalization/Minimax/ValueRadiusControl.lean

lean_formalization/Minimax/ValueRawCurve.lean

lean_formalization/Minimax/ValueRawGradient.lean

lean_formalization/Minimax/ValueUniformBarrier.lean

lean_formalization/Minimax/ValueVectorBlock.lean

lean_formalization/Minimax/ValueVectorDerivative.lean

lean_formalization/Minimax/ValueVectorResidual.lean

lean_formalization/MinimaxLower.lean

lean_formalization/README.md

lean_formalization/TRUSTED_DEFINITIONS.md

lean_formalization/lake-manifest.json

lean_formalization/lakefile.toml

(384 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.