PHD Discussions Logo

Ask, Learn and Accelerate in your PhD Research

Question Icon Post Your Answer

Question Icon

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.

Your Answer