Thanks for all the replies so far!
To confirm, the game I'm working on is a 2D game.
So from what I understand there's really no one perfect solution that is going to fix everything, but combining all these different things to get the performance I need.
So I could implement quad trees, plus this "frustum culling" (which I'm guessing works just as well to 2D games as it does for 3D?)
I could also split my objects into "static" and "dynamic".
I could do as wintertime suggested, and have this sort of "probability" buckets, and not update some objects as much as others depending on how probable it is that they would be in the screen on the next update.
I'm using Lua with Love2D by the way.