Twice Epi-Differentiability of Orthogonally Invariant Matrix Functions and Application

Jiahuan He, Chao Kan, Wen SongarXiv 2024 · arXiv

TL;DR

This paper advances the second-order variational analysis of matrix functions that depend only on singular values (orthogonally invariant functions). The authors prove that the widely used nuclear norm is "twice epi-differentiable" and provide explicit formulas for its second-order derivatives, enabling more sophisticated optimality conditions for matrix optimization problems.

What Problem Does This Paper Address?

In fields like machine learning, matrix completion, and control theory, we often solve optimization problems of the form $\min \psi(X) + \theta(X)$, where $\theta(X)$ is a nonsmooth function like the nuclear norm (the sum of singular values).

While the first-order properties (gradients and subgradients) of these functions are well-understood, second-order analysis—which describes the "curvature" of the function—is much more challenging because these functions are typically nonsmooth. Second-order information is crucial for developing fast Newton-type optimization algorithms and for understanding the stability of solutions. This paper fills a theoretical gap by extending second-order variational tools (like parabolic regularity and twice epi-differentiability) from symmetric eigenvalue functions to the broader class of rectangular matrix singular value functions.

Methods

The authors employ tools from nonsmooth variational analysis. Their primary strategy involves:

  1. The B-operator: They use a linear operator that maps an $m \times n$ matrix to a larger $(m+n) \times (m+n)$ symmetric matrix. This allows them to translate problems about singular values into problems about eigenvalues, which have a more established theoretical framework.
  2. Parabolic Epi-derivatives: Instead of standard Taylor expansions (which require smoothness), the authors use "parabolic" difference quotients. These quotients look at how the function changes along curved (parabolic) paths rather than just straight lines.
  3. Chain Rules: They establish new chain rules to show how properties of a simple scalar function $f$ (acting on a vector of singular values) "inherit" onto the matrix function $F(X) = f(\sigma(X))$.

Datasets

Not discussed in the paper. This is a theoretical mathematical study; no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • Inheritance of Properties: The paper demonstrates that if an absolutely symmetric function $f$ (the "inner" function) is parabolically regular or twice epi-differentiable, the corresponding matrix function $F = f \circ \sigma$ inherits these properties.
  • The Nuclear Norm is Well-Behaved: A major highlight is the proof that the nuclear norm is twice epi-differentiable. This is significant because the nuclear norm is the most common convex surrogate for matrix rank, and knowing its second-order structure allows for more precise optimization.
  • Explicit Formulas: The authors don't just prove existence; they derive explicit, computable expressions for the second-order epi-derivatives and subderivatives. These formulas involve the singular value decomposition (SVD) and projections onto specific subspaces defined by the matrix's singular values.
  • Metric Subregularity: The authors note that for this class of functions, certain technical "constraint qualifications" (like metric subregularity) are automatically satisfied, simplifying the application of their theory.

Key Results

  • Nuclear Norm Derivative: The paper provides a complete second-order epi-derivative for the nuclear norm (Corollary 3.6). This formula accounts for both the "smooth" parts of the norm and the "kinks" where singular values are zero or tied.
  • Second Subderivatives: For any convex orthogonally invariant function, the authors calculate the second subderivative (Theorem 5.6).
  • Optimality Conditions: The authors establish new second-order necessary and sufficient optimality conditions for matrix optimization (Theorem 5.8). For example, they show that a point $X_0$ is a local minimizer if the sum of the Hessian of the smooth part and the second subderivative of the nonsmooth part is positive definite on a specific "critical cone."

Limitations and Future Work

  • Convexity Assumption: Much of the second-order subderivative analysis assumes the underlying function $f$ is convex. While many applications use convex functions, extending this to non-convex orthogonally invariant functions (like Schatten-$p$ quasi-norms where $p < 1$) remains an open challenge.
  • Computational Implementation: While the paper provides explicit formulas, it does not discuss the numerical efficiency of computing these second-order terms in high-dimensional settings, which would be necessary for practical algorithm design.
  • Application Scope: The paper focuses on the nuclear norm and general convex cases; future work could derive similar explicit second-order expressions for other specific norms, such as the Ky Fan $k$-norm or the spectral norm.

Summary updated

Abstract

In this paper, our focus lies on the study of the second-order variational analysis of orthogonally invariant matrix functions. It is well-known that an orthogonally invariant matrix function is an extended-real-value function defined on ${\mathbb M}_{m,n}\,(n \leqslant m)$ of the form $f \circ \sigma$ for an absolutely symmetric function $f \colon \R^n \rightarrow [-\infty,+\infty]$ and the singular values $\sigma \colon {\mathbb M}_{m,n} \rightarrow \R^{n}$. We establish several second-order properties of orthogonally invariant matrix functions, such as parabolic epi-differentiability, parabolic regularity, and twice epi-differentiability when their associated absolutely symmetric functions enjoy some properties. Specifically, we show that the nuclear norm of a real $m \times n$ matrix is twice epi-differentiable and we derive an explicit expression of its second-order epi-derivative. Moreover, for a convex orthogonally invariant matrix function, we calculate its second subderivative and present sufficient conditions for twice epi-differentiability. This enables us to establish second-order optimality conditions for a class of matrix optimization problems.
BibTeX
@misc{he2024twice,
  author = {Jiahuan He and Chao Kan and Wen Song},
  title = {{Twice Epi-Differentiability of Orthogonally Invariant Matrix Functions and Application}},
  year = {2024},
  eprint = {2412.09898},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.09898},
}
Figure