2023/01/04 by Geneson, Jesse, Zhou, Ethan · 1 citation
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2301.01434
In this paper, we study the online learning of real-valued functions where the hidden function is known to have certain smoothness properties. Specifically, for q ≥ 1, let \mathcal Fq be the class of absolutely continuous functions f: [0,1] → \mathbb R such that ‖f'‖q ≤ 1. For q ≥ 1 and d ∈ \mathbb Z+, let \mathcal Fq,d be the class of functions f: [0,1]d → \mathbb R such that any function g: [0,1] → \mathbb R formed by fixing all but one parameter of f is in \mathcal Fq. For any class of real-valued functions \mathcal F and p>0, let optp(\mathcal F) be the best upper bound on the sum of pth powers of absolute prediction errors that a learner can guarantee in the worst case. In the single-variable setup, we find new bounds for optp(\mathcal Fq) that are sharp up to a constant factor. We show for all ε ∈ (0, 1) that opt1+ε(F∞) = Θ(ε-(1)/(2)) and opt1+ε(Fq) = Θ(ε-(1)/(2)) for all q ≥ 2. We also show for ε ∈ (0,1) that opt2(\mathcal F1+ε)=Θ(ε-1). In addition, we obtain new exact results by proving that optp(\mathcal Fq)=1 for q ∈ (1,2) and p ≥ 2+(1)/(q-1). In the multi-variable setup, we establish inequalities relating optp(\mathcal Fq,d) to optp(\mathcal Fq) and show that optp(\mathcal F∞,d) is infinite when pd. We also obtain sharp bounds on learning \mathcal F∞,d for p < d when the number of trials is bounded.