Abstract
Based on elementary one-sided (first-order) directional derivatives and their extensions to the second order, this research introduces several local properties of non-convex, non-differentiable functions. We discuss their realizations in piecewise affine statistical estimation problems, with and without sparsity control. These properties provide sufficient conditions under which local optimality questions can be positively answered for constrained optimization problems with directionally differentiable objective functions. Specifically, we characterize when first-order and second-order directional stationarity are necessary and sufficient for local minimizing. For twice directionally differentiable objectives, we show that the strongly locally minimizing property can be characterized via a strong second-order directional stationarity condition. These properties, categorized as local pointwise convexity and generalized convexity, are shown to be invariant under composition with piecewise affine functions. Finally, for unconstrained problems involving smooth objectives plus an $\ell_1$-penalty, we demonstrate that verifying second-order directional stationarity can be reduced to checking the copositivity of a specific Schur complement on the nonnegative orthant.
Introduction
In modern machine learning and statistical modeling, optimization landscapes are rarely smooth or globally convex. Many popular models rely on "non-smooth" components—such as $\ell_1$ sparsity penalties (Lasso), Huber loss functions, or Rectified Linear Units (ReLU) in neural networks. These components introduce sharp ridges and "corners" where traditional gradient-based calculus fails because the gradient is undefined.
While variational analysis offers a high-level mathematical framework for these problems, its abstraction can often obscure practical application in engineering and statistics. This research bridges that gap by developing a concrete set of tools based on directional derivatives to identify and verify local minimizers in piecewise programming environments.
The Framework: Directional Derivatives and Local Convexity
Rather than relying on a single global gradient, this framework utilizes directional derivatives—measuring how a function changes as one moves in a specific direction from a point. This approach allows for a granular analysis of the function's behavior even at non-differentiable points.
Functional Classes: LFcvx and LScvx
The core of the proposed theory lies in two new functional properties:
- Locally First-order Convex (LFcvx): Functions that behave like convex functions in a first-order sense near a specific point.
- Locally Second-order Convex (LScvx): Functions that maintain convex-like curvature properties in a second-order sense near a point.
These properties are significant because they allow researchers to treat non-convex functions as if they were convex within a local neighborhood. Crucially, the authors prove that these properties are invariant under composition with Piecewise Affine (PA) functions. Since many complex models are built by layering simple piecewise components (like ReLUs), this invariance ensures the theory remains applicable as models grow in complexity.
Stationarity and Optimality Conditions
A central question in optimization is: When is a stationary point actually a local minimum? In smooth optimization, we look for a zero gradient and a positive semi-definite Hessian. In the non-smooth, non-convex regime, the answers are more complex.
First-Order and Second-Order Stationarity
The research establishes necessary and sufficient conditions for local optimality:
- First-Order: For LFcvx functions, first-order directional stationarity is shown to be both necessary and sufficient for a point to be a local minimizer.
- Second-Order: For LScvx functions, the authors prove that a weak second-order directional stationary point is a local minimizer. Furthermore, for twice directionally differentiable objectives, a strong second-order directional stationarity condition characterizes a "strong" local minimizer.
Applications in Statistical Estimation
The theoretical framework is applied to several common statistical "building blocks," demonstrating its practical utility:
- Sparsity Control: For unconstrained problems featuring a smooth objective combined with an $\ell_1$-function, the task of verifying second-order optimality is converted into a matrix-theoretic problem. Specifically, it involves checking the copositivity of a Schur complement on the nonnegative orthant.
- Piecewise Structures: The paper demonstrates how these properties manifest in Huber loss, SCAD/MCP penalties, and truncated hinge loss. It also shows that the ratio of two Piecewise Affine functions—a structure found in certain specialized neural architectures—maintains these favorable local properties.
Discussion and Limitations
While this framework provides a rigorous path to identifying local minimizers, it faces computational hurdles. Verifying the "copositivity" of a matrix is known to be an NP-hard problem in the general case, meaning that while the mathematical condition is clear and finite-dimensional, it may be difficult to compute for very large-scale problems.
Additionally, while the current results are robust for piecewise affine and piecewise quadratic functions, extending these findings to more general "piecewise $C^k$" functions remains an open question. Future work may focus on relaxing these structural assumptions to encompass an even broader class of non-smooth objective functions used in deep learning and high-dimensional statistics.
Summary updated