How do I approach Machine Learning interview questions?

Machine Learning questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master machine learning interviews.

What difficulty level is this interview question?

This is a medium difficulty Machine Learning question, commonly asked during Technical Screen rounds at Rippling.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Rippling during technical interviews.

Find minimum of unknown convex function | Rippling Interview Question

Q: Find minimum of unknown convex function

This question evaluates a candidate's understanding of convex optimization and zeroth-order (query-based) algorithm design, including reasoning about sample complexity, interval-reduction strategies, and robustness to noisy function evaluations.

You are given access to an unknown univariate convex function $f(x)$ defined on a closed interval $[L, R]$ on the real line.

You cannot see the analytical form of $f(x)$ .
You are allowed to query the function at any point $x \in [L, R]$ and obtain the value $f(x)$ .
You are told that $f(x)$ is convex and has a unique global minimum within $[L, R]$ .
You have a strict budget of at most $K$ function evaluations (queries) and want to find the location of the minimum as accurately as possible.

Tasks:

Describe an algorithm that uses only function evaluations (no gradient information) to find the point where $f(x)$ attains its minimum on $[L, R]$ , under the convexity assumption.
Explain why gradient descent is not directly applicable when gradients or subgradients are not available, and why your proposed algorithm is suitable.
Analyze the time complexity in terms of the number of function evaluations needed to achieve an interval of uncertainty of length at most $\varepsilon$ containing the minimum.
Discuss how noise in the function evaluations (i.e., you observe $f(x) + \epsilon$ where $\epsilon$ is small random noise) would affect your method and what modifications, if any, you would make.

Clearly explain the intuition, the step-by-step procedure (including how you shrink the search interval each iteration), and provide pseudocode.

You are given access to an unknown univariate convex function $f(x)$ defined on a closed interval $[L, R]$ on the real line.

You cannot see the analytical form of $f(x)$ .
You are allowed to query the function at any point $x \in [L, R]$ and obtain the value $f(x)$ .
You are told that $f(x)$ is convex and has a unique global minimum within $[L, R]$ .
You have a strict budget of at most $K$ function evaluations (queries) and want to find the location of the minimum as accurately as possible.

Tasks:

Describe an algorithm that uses only function evaluations (no gradient information) to find the point where $f(x)$ attains its minimum on $[L, R]$ , under the convexity assumption.
Explain why gradient descent is not directly applicable when gradients or subgradients are not available, and why your proposed algorithm is suitable.
Analyze the time complexity in terms of the number of function evaluations needed to achieve an interval of uncertainty of length at most $\varepsilon$ containing the minimum.
Discuss how noise in the function evaluations (i.e., you observe $f(x) + \epsilon$ where $\epsilon$ is small random noise) would affect your method and what modifications, if any, you would make.

Clearly explain the intuition, the step-by-step procedure (including how you shrink the search interval each iteration), and provide pseudocode.

Find minimum of unknown convex function

Quick Overview

Solution

Comments (0)

Find minimum of unknown convex function

Quick Overview

Solution

Comments (0)