Well, I'm not sure what you mean by "concave part of a Pareto curve." (Perhaps you meant convex?) Usually, the Pareto curve is the epigraph of the individual function evaluations at the optimal points, so, unless your problem is highly nonconvex, the Pareto curve is likely to be convex.
More specifically, the tradeoff curve is defined as the following: letting θ(λ) be the optimal solution of the first optimization problem at fixed λ, the Pareto optimal curve/frontier is the epigraph of the set of of all (l(θ(λ)), r(θ(λ))). I.e.,
{(x, y) | x ≥ l(θ(λ)), y ≥ r(θ(λ)), λ ∈ ℝ}
If l and r are convex functions, then this curve is guaranteed to be convex. A similar curve can be defined for the second problem (over M instead of λ), and both curves are equal (in the sense that they both include the same points).
Note that this equivalency between both problems doesn't require convexity; for example, lower semi-continuity of l and r with r bounded from below [0], are sufficient conditions that would include essentially all functions used in ML.
-----
[0] Boundedness is needed in this case since, otherwise, we could just have r(θ) = -∞ for a bunch of points, in which case we would always choose this θ, no matter how large or small λ is (except at λ = 0) in problem (1), whereas it would have a different effect in problem (2).
More specifically, the tradeoff curve is defined as the following: letting θ(λ) be the optimal solution of the first optimization problem at fixed λ, the Pareto optimal curve/frontier is the epigraph of the set of of all (l(θ(λ)), r(θ(λ))). I.e.,
If l and r are convex functions, then this curve is guaranteed to be convex. A similar curve can be defined for the second problem (over M instead of λ), and both curves are equal (in the sense that they both include the same points).Note that this equivalency between both problems doesn't require convexity; for example, lower semi-continuity of l and r with r bounded from below [0], are sufficient conditions that would include essentially all functions used in ML.
-----
[0] Boundedness is needed in this case since, otherwise, we could just have r(θ) = -∞ for a bunch of points, in which case we would always choose this θ, no matter how large or small λ is (except at λ = 0) in problem (1), whereas it would have a different effect in problem (2).