Size and depth of monotone neural networks: interpolation and approximation
We study monotone neural networks with threshold gates where all the weights (other than the biases) are non-negative. We focus on the expressive power and efficiency of representation of such networks. Our first result establishes that every monotone function over $[0,1]^d$ can be approximated within arbitrarily small additive error by a depth-4 monotone network. When $d > 3$, we improve upon the previous best-known construction which has depth $d+1$. Our proof goes by solving the monotone interpolation problem for monotone datasets using a depth-4 monotone threshold network. In our second main result we compare size bounds between monotone and arbitrary neural networks with threshold gates. We find that there are monotone real functions that can be computed efficiently by networks with no restriction on the gates whereas monotone networks approximating these functions need exponential size in the dimension.
Code (1)
Tasks
Inductive BiasMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Efficient Temporal Point Processes via Monotone Alternating Splines
Temporal point processes (TPPs) have widespread applications across various domains. Compared to modeling the conditional intensity of a TPP, modeling its cumulative conditional intensity function (CCIF) improves computa…
Computational EfficiencyPoint ProcessesDeletion Robust Non-Monotone Submodular Maximization over Matroids
Maximizing a submodular function is a fundamental task in machine learning and in this paper we study the deletion robust version of the problem under the classic matroids constraint. Here the goal is to extract a small …
Deletion Robust Submodular Maximization over Matroids
Maximizing a monotone submodular function is a fundamental task in machine learning. In this paper, we study the deletion robust version of the problem under the classic matroids constraint. Here the goal is to extract a…
Stochastic $k$-Submodular Bandits with Full Bandit Feedback
In this paper, we present the first sublinear $\alpha$-regret bounds for online $k$-submodular optimization problems with full-bandit feedback, where $\alpha$ is a corresponding offline approximation ratio. Specifically,…
Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint
The problem of non-monotone $k$-submodular maximization under a knapsack constraint ($\kSMK$) over the ground set size $n$ has been raised in many applications in machine learning, such as data summarization, information…
Data Summarization