Ankan Saha
Smoothing Multivariate Performance Measures.
Mon, 02/20/2012 - 15:01 — SomNambulAuthors: Ankan Saha, Xinhua Zhang, S. V.N. Vishwanatan
Subjects: Learning
AbstractA Support Vector Method for multivariate performance measures was recently
introduced by Joachims (2005). The underlying optimization problem is currently
solved using cutting plane methods such as SVM-Perf and BMRM. One can show that
these algorithms converge to an eta accurate solution in O(1/Lambda*e)
iterations, where lambda is the trade-off parameter between the regularizer and
the loss function. We present a smoothing strategy for multivariate performance
scores, in particular precision/recall break-even point and ROCArea.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.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
