Local Minimizers and Second-Order Conditions in Composite Piecewise Programming via Directional Derivatives

Tsung‐Hui Chang, Mingyi Hong, Jong‐Shi PangarXiv 2017 · arXiv

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:

  1. Locally First-order Convex (LFcvx): Functions that behave like convex functions in a first-order sense near a specific point.
  2. 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

Abstract

Based on elementary one-sided (first-order) directional derivatives and their extensions to second order, we introduce several local properties of non-convex, non-differentiable functions at a given point, and discuss their realizations in piecewise affine statistical estimation problems, with or without sparsity control. These properties provide sufficient conditions under which the following local optimality questions can be positively answered for a constrained optimization problem with first-order, and respectively, second-order directionally differentiable objective functions. When is first-order directional stationarity necessary and sufficient for local minimizing? When is weak second-order directional stationarity necessary and sufficient for local minimizing? We also show that for a twice directionally differentiable objective, the strongly locally minimizing property of a first-order directional stationary solution can be characterized in terms of a strong second-order directional stationarity condition. The introduced properties are of a local pointwise convexity and generalized convexity type, they are shown to be invariant under composition with piecewise affine functions. For a special class of unconstrained problems with a smooth objective function plus the non-differentiable $\ell_1$-function, we show that the task of verifying the second-order directional stationarity condition can be converted to the problem of checking the copositivity of certain Schur complement on the nonnegative
BibTeX
@misc{chang2017local,
  author = {Tsung‐Hui Chang and Mingyi Hong and Jong‐Shi Pang},
  title = {{Local Minimizers and Second-Order Conditions in Composite Piecewise Programming via Directional Derivatives}},
  year = {2017},
  eprint = {1709.05758},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.05758},
}

Loading related content...

Figure