Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities