Whitney-type estimates for convex functions

Basic Information

• Paper ID: 2311.00912
• Title: Whitney-type estimates for convex functions
• Authors: Jaskaran Singh Kaire, Andriy Prymak (University of Manitoba)
• Classification: math.CA cs.NA math.NA
• Publication Date: November 2023 (arXiv preprint, latest version August 2025)
• Paper Link: https://arxiv.org/abs/2311.00912

Abstract

This paper investigates Whitney-type estimates for approximating convex functions in the uniform norm on various convex multivariate domains, with particular focus on the dependence of relevant constants on dimension and domain geometry.

Research Background and Motivation

Research Problem

This paper studies the application of Whitney-type inequalities in convex function approximation. Traditional Whitney inequalities establish relationships between function approximation error and smoothness moduli, but existing theory remains incomplete for the special class of convex functions.

Significance

1. Theoretical importance: Whitney-type estimates are fundamental tools in approximation theory, used for constructing piecewise polynomial approximations and bounding local approximation errors
2. Practical applications: When processing high-dimensional data in data science, understanding the dependence of constants on dimension is crucial
3. Geometric insights: Understanding how domain geometry affects approximation properties

Limitations of Existing Methods

1. Whitney constants for general functions grow rapidly with dimension
2. Insufficient exploitation of special properties of convex functions
3. Incomplete theory for shape-preserving approximation (requiring approximating polynomials to also be convex)

Research Motivation

By exploiting convexity constraints, the authors aim to obtain better approximation rates and smaller Whitney constants, particularly in high-dimensional settings.

Core Contributions

1. Established precise asymptotic behavior of Whitney constants for convex functions: Proved that $\lim_{n→∞} \frac{\widehat{w}_{2,n}}{\log_2 n} = \frac{1}{4}$, which is half that of general functions ($\frac{1}{2}$)
2. Provided exact results on centrally symmetric domains: For any centrally symmetric convex domain $K$, $\widehat{w}_2(K) = \frac{1}{2}$
3. Proved equivalence in higher-order cases: When $m ≥ 3$, $\widehat{w}_m(K) = w_m(K)$
4. Established theoretical framework for convex-preserving approximation: Provided upper bounds for convex-preserving approximation constants, depending on the Banach-Mazur distance of the domain
5. Provided negative results for convex-preserving approximation: Proved that for $m ≥ 4$, convex-preserving Whitney constants are infinite

Detailed Methodology

Problem Definition

Let $K \subset \mathbb{R}^n$ be a convex body. Define three classes of Whitney constants:

• General Whitney constant: $w_m(K) := \sup\{E_{m-1}(f;K) : f \in C(K), \omega_m(f;K) \leq 1\}$
• Convex function Whitney constant: $\widehat{w}_m(K) := \sup\{E_{m-1}(f;K) : f \in \widehat{C}(K), \omega_m(f;K) \leq 1\}$
• Convex-preserving Whitney constant: $\widehat{\widehat{w}}_m(K) := \sup\{\widehat{E}_{m-1}(f;K) : f \in \widehat{C}(K), \omega_m(f;K) \leq 1\}$

where $E_m(f;K)$ denotes the $m$-degree polynomial approximation error and $\omega_m(f;K)$ denotes the $m$-th order smoothness modulus.

Core Theoretical Results

1. Linear Approximation Case (m=2)

Theorem 1.2: $\frac{1}{4}\log_2(n+1) \leq \widehat{w}_{2,n} \leq \frac{1}{4}[\log_2 n] + \frac{3}{4}$

Theorem 1.3: For any centrally symmetric convex domain $K$, $\widehat{w}_2(K) = \frac{1}{2}$

2. Higher-Order Approximation Case (m≥3)

Theorem 1.4: For any $K \in \mathcal{K}_n$ and $m ≥ 3$, $\widehat{w}_m(K) = w_m(K)$

3. Convex-Preserving Approximation

Theorem 1.5: For any $K \in \mathcal{K}_n$ and $m ≥ 4$, $\widehat{\widehat{w}}_m(K) = ∞$

Theorem 1.6: For any convex function $f$ and quadratic polynomial $P$, there exists a convex quadratic polynomial $Q$ such that $\|f-Q\|_K \leq a(K)\|f-P\|_K$ where $a(K) = 2(d(K))^2$ and $d(K)$ is the Banach-Mazur distance between $K$ and the unit ball.

Technical Innovations

1. Utilization of supporting hyperplanes: For centrally symmetric domains, exploiting the property that convex functions possess supporting hyperplanes at the center of symmetry
2. Convexification technique: Making smooth functions convex by adding appropriate quadratic terms
3. Geometric analysis: Connecting approximation problems to domain geometric properties (Banach-Mazur distance)

Main Proof Strategies

Proof of Theorem 1.2

• Upper bound: Utilizing Brudnyi-Kalton recursive techniques and Jensen's inequality for convex functions
• Lower bound: Constructing a specific convex function $f_n(x) = \frac{1}{2}\sum_{k=1}^{n+1} x_k \log_2 x_k$ on the standard simplex

Proof of Theorem 1.3

• Upper bound: Exploiting supporting properties of convex functions at the origin, reducing the problem to approximation of non-negative convex functions
• Lower bound: Constructing a one-dimensional convex function $g_δ(x_1) = \max\{0, \frac{x_1-1+δ}{δ}\}$

Proof of Theorem 1.4

The core idea is "convexification": for any smooth function $g$, adding a sufficiently large quadratic term $L\|x\|^2$ makes it convex while preserving higher-order approximation properties.

Experimental Results

Theoretical Result Verification

This paper is primarily theoretical, verifying the tightness of theoretical bounds through construction of specific function examples:

1. Proposition 1.8: Constructed a specific convex function $f(x,y) = 2\max\{1-y, |x|\}$, proving that the set of best quadratic polynomial approximations may contain non-convex polynomials

Numerical Examples

• On $[−1,1] × [0,1]$, the function $f(x,y) = 2\max\{1-y, |x|\}$ has best quadratic approximation error of $\frac{1}{2}$
• Non-convex best approximation polynomial: $P(x,y) = \frac{3}{2} + x^2 - y^2$
• Convex best approximation polynomial: $Q(x,y) = \frac{3}{2} + x^2 + y^2 - 2y$

Related Work

Classical Whitney Theory

• Whitney (1957): Established fundamental inequalities for the one-dimensional case
• Gilewicz, Kryakin, Shevchuk: Obtained the best known Whitney constant upper bounds $w(m) ≤ 2 + e^{-2}$

Multivariate Extensions

• Brudnyi-Kalton (2000): Systematically studied multivariate Whitney constants, establishing dimension dependence
• Dekel-Leviatan: Proved that Whitney constants do not depend on specific geometry of convex domains
• Dai-Prymak: Studied directional Whitney inequalities on non-convex domains

Shape-Preserving Approximation

• Shvedov: Made important contributions to convex-preserving multivariate polynomial approximation
• One-dimensional shape-preserving approximation theory is relatively mature, but multivariate cases have been less studied

Conclusions and Discussion

Main Conclusions

1. Halved dimensional effect: The growth rate of Whitney constants for convex functions with respect to dimension is half that of general functions
2. Importance of symmetry: Whitney constants for convex functions on centrally symmetric domains equal the constant $\frac{1}{2}$
3. Higher-order equivalence: For third-order and higher approximations, convexity constraints provide no additional advantage
4. Difficulty of convex-preserving approximation: For fourth-order and higher approximations, convex-preserving Whitney constants are infinite

Limitations

1. Quadratic convex-preserving approximation: Only upper bounds depending on Banach-Mazur distance are provided, which may not be optimal
2. Constructive aspects: Theoretical results are primarily existence results, lacking concrete construction algorithms
3. Computational complexity: Computational complexity of computing Whitney constants is not discussed

Future Directions

1. Open problems: Can one always select a convex best approximation quadratic polynomial?
2. Algorithm development: Design efficient algorithms for computing convex-preserving approximations
3. Application extensions: Apply theoretical results to convex optimization problems in machine learning

In-Depth Evaluation

Strengths

1. Theoretical depth: Established a complete theoretical framework for Whitney estimates of convex functions
2. Technical innovation: Cleverly combined convex analysis, approximation theory, and geometric analysis
3. Precise results: Provided asymptotically exact bounds, particularly exact values in the centrally symmetric case
4. Systematicity: Comprehensively studied different approximation degrees and constraint conditions

Weaknesses

1. Limited practical utility: Primarily theoretical results with limited consideration of practical applications
2. Computational aspects: No effective methods provided for computing Whitney constants
3. Special cases: Constants in some results (e.g., Theorem 1.6) may not be optimal

Impact

1. Theoretical contribution: Provided new perspectives for approximation theory, particularly in high-dimensional settings
2. Methodological value: Demonstrated how to exploit special properties of functions to improve general estimates
3. Future research: Laid foundation for convex-preserving approximation and high-dimensional approximation theory

Applicable Scenarios

1. Theoretical research: Interdisciplinary research in approximation theory, harmonic analysis, and convex analysis
2. Numerical analysis: Polynomial approximation of high-dimensional data
3. Optimization theory: Function approximation problems in convex optimization

References

This paper primarily references the following key works:

1. Brudnyi, Y.A. and Kalton, N.J. (2000): Systematic study of multivariate Whitney constants
2. Whitney, H. (1957): Classical one-dimensional Whitney inequalities
3. Shvedov, A.S. (1981): Pioneering work on convex-preserving polynomial approximation
4. DeVore, R.A. and Lorentz, G.G. (1993): Standard textbook on constructive approximation theory

This paper makes important theoretical contributions to approximation theory, particularly in understanding how convexity constraints improve approximation estimates. While primarily theoretical, it establishes a solid mathematical foundation for future applied research.