A fresh look into variational analysis of $\mathcal C^2$-partly smooth functions

This paper provides a fresh variational analysis of $\mathcal C^2$-partly smooth functions by establishing their strict twice epi-differentiability and calculating their second subderivatives, while demonstrating that the converse does not hold and applying these results to the stability of generalized equations and the asymptotic analysis of sample average approximations.

The Gist

Imagine you are trying to find the lowest point in a vast, rugged landscape. This is the core problem of optimization: finding the best solution (the bottom of the valley) among millions of possibilities.

In the real world, these landscapes aren't always smooth hills. Sometimes they are jagged, with sharp cliffs, corners, and sudden drops. Mathematically, we call these "nonsmooth" functions. For a long time, mathematicians had a hard time analyzing these jagged terrains because the usual tools (like calculus) only work on smooth, rolling hills.

This paper introduces a fresh way to look at a specific type of "jagged but structured" terrain called $C^2$-partly smooth functions.

Here is the breakdown of what the authors did, using simple analogies:

1. The "Hidden Smooth Road" Analogy

Imagine a mountain range that looks incredibly rough from a distance. However, if you zoom in on a specific path, you realize that along that exact path, the ground is actually perfectly smooth, like a paved highway. The rest of the mountain is jagged, but this specific road is smooth.

• The Math: The authors study functions that behave this way. They are rough overall, but if you restrict your view to a specific "manifold" (a smooth surface or path), the function becomes perfectly smooth ($C^2$).
• The Discovery: They proved that if a function has this "hidden smooth road" structure, it behaves very predictably. You can calculate its "second derivative" (how fast the slope is changing) even though the function looks jagged from the outside.

2. The "Strictly Twice Epi-Differentiable" Superpower

The paper introduces a fancy term: Strictly Twice Epi-Differentiable. Let's translate that.

• The Analogy: Imagine you are trying to predict the future shape of a bumpy road based on a small patch of it.
  • Normal functions: If you zoom in, the road might look different depending on exactly where you stand. It's unpredictable.
  • Strictly Twice Epi-Differentiable functions: No matter how you zoom in or where you stand on the "smooth road," the shape of the road ahead is perfectly consistent and predictable. It's like a machine that always produces the same blueprint when you ask for a close-up.

The Big Finding: The authors proved that all functions with that "hidden smooth road" structure (the $C^2$-partly smooth ones) have this superpower of perfect predictability. However, they also showed the reverse isn't true: you can have a perfectly predictable function that doesn't have a hidden smooth road. This means their new method is actually stronger and covers more ground than just looking for smooth roads.

3. Why Does This Matter? (The Applications)

Why do we care if a mountain is predictable? Because it helps us build better algorithms to solve problems.

A. The "GPS" for Optimization (Stability)

When you use a computer to find the lowest point in a valley, you often have to deal with noise or small errors (like a GPS signal drifting).

• The Result: Because these functions are so predictable, the authors showed that the "solution map" (the GPS that tells you where the bottom is) is Lipschitz continuous.
• In Plain English: If you nudge the problem slightly (a small change in data), the answer doesn't jump wildly to a different valley. It moves smoothly and predictably. This is crucial for engineering and finance, where small errors shouldn't cause catastrophic failures.

B. The "Sample Average Approximation" (SAA)

In the real world, we often don't know the exact shape of the mountain. We only have a bunch of samples (like taking photos of the terrain from different angles). We use these photos to guess the whole shape. This is called the Sample Average Approximation (SAA) method.

• The Problem: As you take more and more photos (more data), does your guess get closer to the real bottom? And how fast?
• The Result: The authors used their new "predictability" tools to prove exactly how fast the solution converges to the true answer. They gave a precise formula for the "error distribution."
• The Metaphor: It's like saying, "If you take 1,000 photos of this jagged mountain, your estimate of the lowest point will be within 1 meter of the truth, and here is the exact mathematical curve that describes how your error shrinks."

Summary

Think of this paper as a new set of goggles for mathematicians and data scientists.

1. Before: They looked at jagged, nonsmooth functions and struggled to calculate how they curve.
2. Now: They put on these goggles, identify the "hidden smooth roads" inside the jagged functions, and realize that these functions are actually highly predictable and stable.
3. The Payoff: This allows them to build faster, more reliable algorithms for solving complex problems in machine learning, finance, and engineering, ensuring that small changes in data don't lead to chaotic results.

The authors essentially said: "We found a way to treat these messy, jagged problems as if they were smooth, predictable machines, and here is exactly how to use that to solve real-world problems."

Technical Summary

Here is a detailed technical summary of the paper "A Fresh Look into Variational Analysis of $C^2$-Partly Smooth Functions" by Nguyen T. V. Hang and Ebrahim Sarabi.

1. Problem Statement and Motivation

The paper addresses the variational analysis of $C^2$-partly smooth functions, a class of nonsmooth functions introduced by Lewis that exhibit smooth structure on a specific manifold (the "active manifold") while remaining nonsmooth elsewhere. These functions are ubiquitous in optimization (e.g., polyhedral functions, spectral functions, and decomposable functions).

While the theoretical properties of $C^2$-partly smooth functions (such as active manifold identification and stability) are well-established, there is a need to deepen the understanding of their second-order variational properties, specifically:

• Strict twice epi-differentiability: A strong form of second-order differentiability crucial for stability analysis and asymptotic convergence rates.
• Strict proto-differentiability: A property of set-valued mappings (like subgradient mappings) that ensures the graphical derivative behaves well under perturbations.

The authors aim to clarify the relationship between $C^2$-partial smoothness and strict twice epi-differentiability, calculate the second subderivative explicitly, and apply these findings to the stability of generalized equations and the asymptotic analysis of Sample Average Approximation (SAA) methods in stochastic programming.

2. Methodology and Tools

The authors employ advanced tools from Variational Analysis and Generalized Differential Calculus, primarily drawing from the framework established by Rockafellar and Wets. Key concepts include:

• $C^2$-Partial Smoothness: Defined via restricted smoothness on a manifold, regularity, normal sharpness, and subgradient continuity.
• Strict Twice Epi-Differentiability: Defined via the epi-convergence of second-order difference quotients as the step size and the point of evaluation converge simultaneously.
• Strict Proto-Differentiability: A property of set-valued mappings where the graphical derivative is the limit of difference quotients in a strict sense (involving limits of both the point and the direction).
• Prox-regularity and Subdifferential Continuity: These are used as auxiliary assumptions to ensure the uniqueness of active manifolds and the stability of subgradient mappings.
• Lagrangian Formulation: The authors utilize a Lagrangian function $L(u, y) = \hat{f}(u) + \langle y, \Phi(u) \rangle$ associated with the manifold representation to derive second-order formulas.
• Implicit Mapping Theorems: Used to analyze the stability of solution mappings to generalized equations under perturbations.

3. Key Contributions and Results

A. Relationship Between Partial Smoothness and Strict Twice Epi-Differentiability

The central theoretical contribution is the establishment of a strong link between $C^2$-partial smoothness and strict twice epi-differentiability.

• Main Theorem (Theorem 3.10): The authors prove that if a function $f$ is $C^2$-partly smooth at $\bar{x}$ relative to a manifold $M$, and satisfies prox-regularity and subdifferential continuity at $\bar{x}$ for a subgradient $\bar{v}$ in the relative interior of the subdifferential ($\bar{v} \in \text{ri } \partial f(\bar{x})$), then:
  1. $f$ is strictly twice epi-differentiable at $\bar{x}$ for $\bar{v}$.
  2. The subgradient mapping $\partial f$ is strictly proto-differentiable at $\bar{x}$ for $\bar{v}$.
• Explicit Formulas: The paper provides closed-form expressions for the second subderivative and the graphical derivative:
  • Second Subderivative: $d^2f(\bar{x}, \bar{v})(w) = \nabla^2_{xx}L(\bar{x}, \bar{\mu})(w, w) + \delta_{T_M(\bar{x})}(w)$, where $\bar{\mu}$ is the Lagrange multiplier.
  • Graphical Derivative: $D(\partial f)(\bar{x}, \bar{v})(w) = \nabla^2_{xx}L(\bar{x}, \bar{\mu})(w) + N_{T_M(\bar{x})}(w)$ for $w \in T_M(\bar{x})$.
• Counterexamples: The authors provide two examples demonstrating that the converse does not hold:
  1. There exist strictly twice epi-differentiable functions that are not $C^2$-partly smooth (e.g., a function constructed from a specific piecewise affine integral).
  2. There exist strictly twice epi-differentiable functions that fail to be $C^2$-partly smooth in a neighborhood (e.g., $f(x_1, x_2) = |x_1^3 x_2^2|$ at the origin).
     Significance: This clarifies that $C^2$-partial smoothness is a sufficient but not necessary condition for strict twice epi-differentiability, expanding the scope of applicable functions.

B. Stability of Generalized Equations

The paper analyzes the generalized equation $\bar{p} \in \psi(x) + \partial f(x)$, where $\psi$ is a $C^1$ perturbation.

• Equivalence of Regularity: Under the derived strict proto-differentiability, the authors show that metric regularity, strong metric regularity, and the existence of a Lipschitz continuous single-valued localization of the solution mapping are equivalent.
• Differentiability of Solution Mapping: They establish that the solution mapping $s(p)$ is not only Lipschitz continuous but $C^1$-smooth (continuously differentiable) in a neighborhood of the solution, provided the second-order condition (involving the projected Hessian) holds.
• Proximal Mapping: As a corollary, they prove that the proximal mapping of a $C^2$-partly smooth function is $C^1$-smooth and eventually identifies the active manifold (i.e., maps points near the solution onto the manifold $M$).

C. Asymptotic Analysis of Stochastic Programs

The final section applies the stability results to the Sample Average Approximation (SAA) method for stochastic programs with $C^2$-partly smooth regularizers:
$$\min_{x} \mathbb{E}[\phi(x; Z)] + \theta(x)$$

• Setup: The authors assume the regularizer $\theta$ is $C^2$-partly smooth and the loss function $\phi$ satisfies standard integrability and smoothness conditions.
• Convergence: They prove that the sequence of SAA solutions $\{x_k\}$ converges almost surely to the true solution $\bar{x}$.
• Asymptotic Distribution: They derive the generalized central limit theorem for the SAA solutions. The scaled error $\sqrt{k}(x_k - \bar{x})$ converges in distribution to a normal random variable determined by the inverse of the projected Hessian of the Lagrangian and the variance of the stochastic gradient.
  $$\sqrt{k}(x_k - \bar{x}) \xrightarrow{d} - \left( P_{T_M(\bar{x})} \circ \nabla^2_{xx}L(\bar{x}, \bar{\mu})|_{T_M(\bar{x})} \right)^{-1} (P_{T_M(\bar{x})}(\varphi(\bar{x})))$$
  where $\varphi$ represents the limiting Gaussian process of the stochastic gradients.

4. Significance and Impact

• Theoretical Advancement: The paper refines the understanding of second-order variational properties by showing that $C^2$-partial smoothness implies strict twice epi-differentiability under mild relative interior conditions. This allows for the calculation of second subderivatives for a broad class of nonsmooth functions.
• Algorithmic Implications: The $C^1$-smoothness of the proximal mapping and the solution mapping to generalized equations justifies the use of Newton-type methods and provides a theoretical basis for the superlinear convergence of algorithms like the proximal gradient method when applied to these problems.
• Statistical Learning: The asymptotic distribution result provides a rigorous foundation for constructing confidence intervals and hypothesis tests for solutions to stochastic optimization problems involving nonsmooth regularizers (e.g., Lasso, nuclear norm minimization).
• Robustness: By distinguishing between $C^2$-partial smoothness and strict twice epi-differentiability, the authors identify a larger class of functions that possess desirable stability properties, broadening the applicability of variational analysis in optimization.

In summary, this work bridges the gap between the structural properties of nonsmooth functions and their second-order variational behavior, offering precise tools for stability analysis and asymptotic statistics in modern optimization.