Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

• URL: http://arxiv.org/abs/2605.10219v1
• Date: Mon, 11 May 2026 08:59:57 GMT
• Title: Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
• Abstract summary: We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine functions.<n>Recent work by Tian and So shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case.<n>We extend our hardness results to a family of shallow ReLU CNN training losses, with stationarity tested in the trainable weight space.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral geometry that appears in ReLU-type training losses. Recent work by Tian and So (SODA 2025) shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case, and identifies fixed-dimensional tractability as an open direction. We address this direction from the viewpoint of parameterized complexity, with the ambient dimension $d$ as the parameter. In this paper, we give XP algorithms in fixed dimension for the tractable sides, and prove W[1]-hardness for the complementary sides. Moreover, lower bounds under the Exponential Time Hypothesis rule out algorithms running in time $ρ(d)\size^{o(d)}$ for any computable function $ρ$, where $\size$ denotes the total binary encoding length of the stationarity-testing instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We further extend our hardness results to a family of shallow ReLU CNN training losses, with stationarity tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses.

Related papers

• Parallel Diffusion Solver via Residual Dirichlet Policy Optimization [88.7827307535107]
  Diffusion models (DMs) have achieved state-of-the-art generative performance but suffer from high sampling latency due to their sequential denoising nature.<n>Existing solver-based acceleration methods often face significant image quality degradation under a low-dimensional budget.<n>We propose the Ensemble Parallel Direction solver (dubbed as EPD-EPr), a novel ODE solver that mitigates these errors by incorporating multiple gradient parallel evaluations in each step.
  arXiv  Detail & Related papers  (2025-12-28T05:48:55Z)
• Adaptive Probability Flow Residual Minimization for High-Dimensional Fokker-Planck Equations [14.22534820071447]
  Solving high-dimensional Fokker-Planck equations is a challenge in computational physics and dynamics.<n>Existing deep learning approaches, such as Physics-Informed Neural Networks, face computational challenges as dimensionality increases.<n>We propose the Adaptive Probability Flow Residual Minimization (A-PFRM) method.
  arXiv  Detail & Related papers  (2025-12-22T09:31:31Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• A parametric algorithm is optimal for non-parametric regression of smooth functions [44.32603181895527]
  PADUA is the first parametric algorithm with optimal sample complexity for this setting.<n>We show that PADUA shows comparable performance to state-of-the-art methods, while requiring only a fraction of the computational time.
  arXiv  Detail & Related papers  (2024-12-19T11:22:52Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  We study the type of solutions to which gradient descent converges when used to train a single hidden-layer multivariate ReLU network with the quadratic loss. We prove that although shallow ReLU networks are universal approximators, stable shallow networks are not.
  arXiv  Detail & Related papers  (2023-06-30T09:17:39Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
  We derive nonasymptotic complexity of exact and inexact PPA to minimize convex functions under $gamma-$Holderian growth. Our numerical tests show improvements over existing restarting versions of the Subgradient Method.
  arXiv  Detail & Related papers  (2021-08-10T07:15:07Z)
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality [8.940054309023525]
  We analyze the influence of the dimension $d$ of the training data on the computational complexity. We prove that known brute-force strategies are essentially optimal. In particular, we extend a known-time algorithm for constant $d$ and convex loss functions to a more general class of loss functions.
  arXiv  Detail & Related papers  (2021-05-18T17:05:26Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.