Post Your Answer
1 year ago in Computational Geometry , Mathematical Analysis By Srajan
How can the complexity of a function be measured?
Reading papers on machine learning and high-dimensional analysis, I constantly see references to function complexity affecting model behavior and computational cost. Beyond vague intuition, what are the concrete, measurable properties we're actually referring to?
Â
All Answers (1 Answers In All)
By Rani Answered 1 year ago
In my research on approximation algorithms, we measure complexity to predict how hard a function is to learn, optimize, or integrate. It's not one number. Practically, I look at several axes: smoothness, via bounds on derivatives or the Lipschitz constant (how wildly it can oscillate); intrinsic dimensionality, meaning it might live in a high-dimensional space but actually vary along only a few key directions; and geometric complexity, like the number of local minima or the curvature of its level sets. For learning theory, we use Vapnik-Chervonenkis dimension to measure its "flexibility." Each metric informs different computational strategies.
Reply to Rani
Related Questions