In this talk we consider a new class of convex optimization problems,
which admit faster black-box optimization schemes. For analyzing
their rate of convergence, we introduce a notion of mixed accuracy of an
approximate solution, which is a convenient generalization of
the absolute and relative accuracies. We show that for our problem
class, a natural Quasi-Newton method is always faster than the standard
gradient method. At the same time, after an appropriate normalization,
our results can be extended onto the general convex unconstrained
minimization problems.
Copyright. All Rights Reserved.