# Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions

arXiv: https://arxiv.org/abs/2010.11450 · HTML: https://mlsanity.com/paper/2010.11450/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 10 of 10)

- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Long-Term Fairness with Unknown Dynamics](https://mlsanity.com/paper/2304.09362/) (2023)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Breaking Correlation Shift via Conditional Invariant Regularizer](https://mlsanity.com/paper/2207.06687/) (2022)
- [A Statistical Framework for Data-dependent Retrieval-Augmented Models](https://mlsanity.com/paper/2408.15399/) (2024)
- [Convergence of Policy Mirror Descent Beyond Compatible Function Approximation](https://mlsanity.com/paper/2502.11033/) (2025)
- [Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation](https://mlsanity.com/paper/2211.15792/) (2022)
- [Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization](https://mlsanity.com/paper/2504.02833/) (2025)
- [An Elementary Proof of the Near Optimality of LogSumExp Smoothing](https://mlsanity.com/paper/2512.10825/) (2025)

## Abstract (arXiv)

A soft-max function has two main efficiency measures: (1) approximation - which corresponds to how well it approximates the maximum function, (2) smoothness - which shows how sensitive it is to changes of its input. Our goal is to identify the optimal approximation-smoothness tradeoffs for different measures of approximation and smoothness. This leads to novel soft-max functions, each of which is optimal for a different application. The most commonly used soft-max function, called exponential mechanism, has optimal tradeoff between approximation measured in terms of expected additive approximation and smoothness measured with respect to R'enyi Divergence. We introduce a soft-max function, called "piecewise linear soft-max", with optimal tradeoff between approximation, measured in terms of worst-case additive approximation and smoothness, measured with respect to ℓq-norm. The worst-case approximation guarantee of the piecewise linear mechanism enforces sparsity in the output of our soft-max function, a property that is known to be important in Machine Learning applications [Martins et al. '16, Laha et al. '18] and is not satisfied by the exponential mechanism. Moreover, the ℓq-smoothness is suitable for applications in Mechanism Design and Game Theory where the piecewise linear mechanism outperforms the exponential mechanism. Finally, we investigate another soft-max function, called power mechanism, with optimal tradeoff between expected textitmultiplicative approximation and smoothness with respect to the R'enyi Divergence, which provides improved theoretical and practical results in differentially private submodular optimization.