Author name cluster

Tamás Linder

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

JMLR Journal 2007 Journal Article

The On-Line Shortest Path Problem Under Partial Monitoring

András György
Tamás Linder
Gábor Lugosi
György Ottucsák

The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defined as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. For this problem, an algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is proportional to 1/√ n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with complexity that is linear in the number of rounds n (i.e., the average complexity per round is constant) and in the number of edges. An extension to the so-called label efficient setting is also given, in which the decision maker is informed about the weights of the edges corresponding to the chosen path at a total of m ≪ n time instances. Another extension is shown where the decision maker competes against a time-varying path, a generalization of the problem of tracking the best expert. A version of the multi-armed bandit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

PDF Details

JMLR Journal 2002 Journal Article

Data-dependent margin-based generalization bounds for classification

András Antos
Balázs Kégl
Tamás Linder
Gábor Lugosi

We derive new margin-based inequalities for the probability of error of classifiers. The main feature of these bounds is that they can be calculated using the training data and therefore may be effectively used for model selection purposes. In particular, the bounds involve empirical complexities measured on the training data (such as the empirical fat-shattering dimension) as opposed to their worst-case counterparts traditionally used in such analyses. Also, our bounds appear to be sharper and more general than recent results involving empirical complexity measures. In addition, we develop an alternative data-based bound for the generalization error of classes of convex combinations of classifiers involving an empirical complexity measure that is easier to compute than the empirical covering number or fat-shattering dimension. We also show examples of efficient computation of the new bounds.

PDF Details

NeurIPS Conference 1998 Conference Paper

A Polygonal Line Algorithm for Constructing Principal Curves

Balázs Kégl
Adam Krzyzak
Tamás Linder
Kenneth Zeger

Principal curves have been defined as "self consistent" smooth curves which pass through the "middle" of a d-dimensional probability distri(cid: 173) bution or data cloud. Recently, we [1] have offered a new approach by defining principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The new definition made it possible to carry out a theoretical analysis of learning principal curves from training data. In this paper we propose a practical construction based on the new definition. Simulation results demonstrate that the new algorithm compares favorably with previous methods both in terms of performance and computational complexity.

PDF Details

NeurIPS Conference 1996 Conference Paper

Radial Basis Function Networks and Complexity Regularization in Function Learning

Adam Krzyzak
Tamás Linder

In this paper we apply the method of complexity regularization to de(cid: 173) rive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from the previous complexity regularization neural network function learning schemes in that we operate with random covering numbers and 11 metric entropy, making it po~sibleto consider much broader families of activa(cid: 173) tion functions, namely functions of bounded variation. Some constraints previously imposed on the network parameters are also eliminated this way. The network is trained by means of complexity regularization in(cid: 173) volving empirical risk minimization. Bounds on the expected risk in tenns of the sample size are obtained for a large class of loss functions. Rates of convergence to the optimal loss are also derived.

PDF Details