Volodya Vovk's work on game theory and finance

Seminar Report on Statistical Online Algorithms


We started with an overview of the field in V.Vovk "Competitive on-line statistics"

This paper introduced the Aggregating Algorithm (AA), which is the main technical tool used in the definition and study of predictive complexity.
V.Vovk "Aggregating strategies"

This paper shows that Aggregating Algorithm is optimal in a natural sense.
V.Vovk "A game of prediction with expert advice"

MK seminar of 10/27/04

Today Ben Packer talked about Kilian and Lawrence's paper in CVPR for unspervised learning of image manifolds and a semi supervised variation of it.
Abstract:
"Can we detect low dimensional structure in high dimensional data sets of images and video? The problem of dimensionality reduction arises often in computer vision and pattern recognition. In this paper, we propose a new solution to this problem based on semidefinite programming. Our algorithm can be used to analyze high dimensional data that lies on or near a low dimensional manifold. It overcomes certain limitations of previous work in manifold learning, such as Isomap and locally linear embedding. We illustrate the algorithm on easily visualized examples of curves and surfaces, as well as on actual images of faces, handwritten digits, and solid objects."

MK seminar of 10/20/04

Spectral methods (i.e., methods that use the eigenvalues and eigenvectors of a matrix representation of a graph) are widely used to compute graph separators. Typically, the Laplacian matrix is used; the Laplacian B of a graph G on n vertices is the n * n matrix with the degrees of the vertices of G on the diagonal and entry b[i,j] = -1 if E(i,j) else 0. The eigenvector (u2) corresponding to the second smallest eigenvalue of B [x is an eigenvector of B iff xB = cx for some constant c which is the eigenvalue coresponding to x] is computed and the vertices are partitioned according to their values in u2. The goal is to compute a small separator which has as few edges crossing it given the partitions are roughly similar.
The measure being optimized here is min(over S \subset of V) { e(S,V-S)/min{|S|,|V - S|} }, which is exactly the sparsest cut. In timothee's paper he was optimizing min(over S \subset of V) { e(S,V-S)( 1/|S| + 1/|V -S| ) }. these are very similar since in timothee's cost function the term which does not have |S| < n/2 is less than a constant and is hence not the deciding factor in the choice of the cut (at least it does not make optimal worse by factor 2).
A simple bisection using spectral partitioning has performance as poor as Omega(n) in case of half cut ladder graphs. Using this cut quotient and the isperimetric number we have another algorithm. We present a class of graphs for which the spectral cut's cut quotient is removed from the min ratio cut by a large factor.

Rob Schapire's work

In this post we will outline the abstracts of the recent work of Robvert Schapire in online learning algorithms

(1)Drifting Games (2001) He introduces and studies a general abstract game played between two players, a shpeherd and the adversary. th game is played in a series of rounds using a finite set of chips. The adversary then moves the chips in any way that need only be weekly correlated with the desired direction assigned by the shepherd. n each round shpeherd assigns a sdesired direction of movement.