Seminar: Jack Mayo (University of Amsterdam) and Isja Mannens (Utrecht University), 2 PhD talks

Speaker: Jack Mayo (Universiteit van Amsterdam) and Isja Mannens (Universiteit Utrecht), 2 PhD talks

Title:

Jack Mayo: Scale-free Unconstrained Online Learning for Curved Losses

Isja Mannens: The parameterized complexity of the Tutte polynomial

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Scale-free Unconstrained Online Learning for Curved Losses" (Jack Mayo):
A sequence of works in unconstrained online convex optimisation have investigated the possibility of adapting simultaneously to the norm U of the comparator and the maximum norm G of the gradients. In full generality, matching upper and lower bounds are known which show that this comes at the unavoidable cost of an additive GU^3, which is not needed when either G or U is known in advance. Surprisingly, recent results by Kempka et al. (2019) show that no such price for adaptivity is needed in the specific case of 1-Lipschitz losses like the hinge loss. We follow up on this observation by showing that there is in fact never a price to pay for adaptivity if we specialise to any of the other common supervised online learning losses: our results cover log loss, (linear and non-parametric) logistic regression, square loss prediction, and (linear and non-parametric) least-squares regression. We also fill in several gaps in the literature by providing matching lower bounds with an e!
 xplicit dependence on U. In all cases we obtain scale-free algorithms, which are suitably invariant under rescaling of the data. Our general goal is to establish achievable rates without concern for computational efficiency, but for linear logistic regression we also provide an adaptive method that is as efficient as the recent non-adaptive algorithm by Agarwal et al. (2021).

Video of the talk of Jack Mayo:

Slides of the talk of Jack Mayo:  
Slides

Abstract of "The parameterized complexity of the Tutte polynomial" (Isja Mannens):
The Tutte polynomial has been widely studied in various areas of mathematics and theoretical computer science. One of these areas is computational complexity. A classic result is that of Jaeger, Vertigan and Welsh, who give a complete dichotomy for the complexity of evaluating the Tutte polynomial at a given point. With recent developments in the field of parameterized complexity in mind, one might ask what such a dichotomy would look like with respect to certain graph parameters.
In this talk we will discuss unpublished work that seeks to answer this question for the parameters of treewidth, pathwidth and cutwidth. We will discuss parallels with the techniques of Jaeger, Vertigan and Welsh and how they can be adapted to this setting. Using this approach, in conjunction with existing hardness results, we find asymptotically tight bounds for all points on so called special curves H_q, for any integer valued q.
In addition, we will discuss a novel rank-based algorithm for the problem of counting forests, a specific evaluation of the Tutte polynomial. This algorithm runs in O(64^tw) time which results in a surprising asymmetry in the complexity of computing the Tutte polynomial, along the lines 'y=1' and 'x=1'. The former can be reduced to counting forests, while the latter is not solvable in O(ctw^{o(ctw)}) time under ETH.

Video of the talk of Isja Mannens: 

Slides of the talk of Isja Mannens:
Slides