  This paper studies a class of simple bilevel optimization problems where we
minimize a composite convex function at the upper-level subject to a composite
convex lower-level problem. Existing methods either provide asymptotic
guarantees for the upper-level objective or attain slow sublinear convergence
rates. We propose a bisection algorithm to find a solution that is
$\epsilon_f$-optimal for the upper-level objective and $\epsilon_g$-optimal for
the lower-level objective. In each iteration, the binary search narrows the
interval by assessing inequality system feasibility. Under mild conditions, the
total operation complexity of our method is ${\tilde
{\mathcal{O}}}\left(\max\{\sqrt{L_{f_1}/\epsilon_f},\sqrt{L_{g_1}/\epsilon_g}
\} \right)$. Here, a unit operation can be a function evaluation, gradient
evaluation, or the invocation of the proximal mapping, $L_{f_1}$ and $L_{g_1}$
are the Lipschitz constants of the upper- and lower-level objectives' smooth
components, and ${\tilde {\mathcal{O}}}$ hides logarithmic terms. Our approach
achieves a near-optimal rate, matching the optimal rate in unconstrained smooth
or composite convex optimization when disregarding logarithmic terms. Numerical
experiments demonstrate the effectiveness of our method.
