Kolmogorov Neural Networks can represent discontinuous functions
arxiv.org
arxiv.org
During the forward pass you sample a discrete outcome given your NN weights to get an error for backprop. During the backward pass you directly propogate through the weights.
This GradTree paper[1] does a good job covering how to do discrete gradient-based optimization (i.e. NNs w/ discrete representations).
Another option is to use a GFlowNet[2]. Then you have a NN policy that takes discrete actions like you're playing an RL game. You're not back-propogating through something that isn't continuous, but you're utilizing a NN to make informed decisions about a problem with a discrete representation.
[1] GradTree (https://arxiv.org/pdf/2305.03515.pdf) [2] GFlowNet (https://arxiv.org/abs/2111.09266)
I'm baffled why Mert Pilanci's work in this area hasn't received more attention. His proofs of a zero duality gap for neural networks are impressive.
The paper only gives an existence result for the general case, and may require an arbitrarily complex activation function to represent arbitrarily complex multivariate functions, so it's unlikely to be useful for machine-learning applications.
Even a result like f(x) = nice(x) + evil(x) with |evil| < epsilon should be "happy enough" right?
Edit: I may have been misremembering the Lebesgue decomposition theorem which is not quite so nice, as the singular part doesn't just go away.
It may turn out that the correct representation can be constructed using an alternate method than backpropagation. But this is still an open question.
I was thinking about some weird activation function like say
0 for x < 0.5
0.5 for x in [0.5, 1]
0.1x + 1 for x > 1
My probably silly thought was, what if you used a smoothed version for computing the differentials for the backpropagation step, while keeping the discontinuous function for actual evaluation? My thought was this would make backprop sensitive to the step changes in the function, while allowing for discontinuous activation.
Of course this example function is just something random without any further thought, so probably not a useful one in actual usage.
That being said, if it's only discontinuous in a few number of places you could extend the derivative everywhere by taking either the left or the right derivative, and then you'd end up with a gradient being defined everywhere, but not continuous. But then does gradient descent work if the gradient isn't continuous?