S.V.N. Vishwanathan
Regularized Risk Minimization by Nesterov's Accelerated Gradient Methods: Algorithmic Extensions and Empirical Studies.
Wed, 11/03/2010 - 16:01 — SomNambulAuthors: Ankan Saha, S.V.N. Vishwanathan, Xinhua Zhang
Subjects: Learning
AbstractNesterov's accelerated gradient methods (AGM) have been successfully applied
in many machine learning areas. However, their empirical performance on
training max-margin models has been inferior to existing specialized solvers.
In this paper, we first extend AGM to strongly convex and composite objective
functions with Bregman style prox-functions. Our unifying framework covers both
the $\infty$-memory and 1-memory styles of AGM, tunes the Lipschiz constant
adaptively, and bounds the duality gap.A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning.
Tue, 02/23/2010 - 16:01 — SomNambulAuthors: S.V.N. Vishwanathan, Jin Yu, Simon Guenter, Nicol N. Schraudolph
Subjects: Machine Learning
AbstractWe extend the well-known BFGS quasi-Newton method and its memory-limited
variant LBFGS to the optimization of nonsmooth convex objectives. This is done
in a rigorous fashion by generalizing three components of BFGS to
subdifferentials: the local quadratic model, the identification of a descent
direction, and the Wolfe line search conditions. We prove that under some
technical conditions, the resulting subBFGS algorithm is globally convergent in
objective function value. We apply its memory-limited variant (subLBFGS) to
L_2-regularized risk minimization with the binary hinge loss.Lower Bounds for BMRM and Faster Rates for Training SVMs.
Thu, 09/10/2009 - 10:12 — SomNambulAuthors: Ankan Saha, S.V.N. Vishwanathan, Xinhua Zhang
Subjects: Learning
AbstractRegularized risk minimization with the binary hinge loss and its variants
lies at the heart of many machine learning problems. Bundle methods for
regularized risk minimization (BMRM) and the closely related SVMStruct are
considered the best general purpose solvers to tackle this problem. It was
recently shown that BMRM requires $O(1/\epsilon)$ iterations to converge to an
$\epsilon$ accurate solution. In the first part of the paper we use the
Hadamard matrix to construct a regularized risk minimization problem and show
that these rates cannot be improved.Efficient Approximation Algorithms for Minimum Enclosing Convex Shapes.
Tue, 09/08/2009 - 12:16 — SomNambulAuthors: Ankan Saha, S.V.N. Vishwanathan
Subjects: Computational Geometry
AbstractWe address the problem of Minimum Enclosing Ball (MEB) and its generalization
to Minimum Enclosing Convex Polytope (MECP). Given $n$ points in a $d$
dimensional Euclidean space, we give a $O(nd/\sqrt{\epsilon})$ algorithm for
producing an enclosing ball whose radius is at most $\epsilon$ away from the
optimum. In the case of MECP our algorithm takes $O(1/\epsilon)$ iterations to
converge.
User login
