## Vocabulaire d’enseignement

It finally happened. Both this and next year I will be teaching in French. Trying to be optimistic here so here are the good points:

1. The load is concentrated in Fall terms with the salary spread throughout the year (+340EUR en gros for 64 hrs of classes a year).
2. It’s the final opportunity to learn French (yep, first you begin teaching and then you learn the language).
3. This is the way to deal with “common” and “professional” ETC credits. Yes, that was an occurence of RAS syndrome.

Courses are MAT116 (Calculus for Engineers, lectures and seminars combined) and STA230 (Applied Statistics, seminars). Taking into account my level of French, a cheat sheet with some corresponding vocabulary will be useful I guess. Here we go.

## Projected Gradient Descent III — Strong convexity

Strong convexity provides an improved lower bound for a convex function; therefore are in our right to expect the improvement of the rate of convergence of PGD. In this post we will find out how much we actually gain.

## How closed form conjectures are made

Discovered an interesting discussion on math.stackoverflow.

## Information theory background I

This is the first of a series of two posts with a goal of providing a background on information theory. For today, the itinerary is as follows: we will start with introducing basic information quantities, proceed with proving  tensorization  statements for them — i.e. that they behave well under the product measure. The tensorization, in turn, will allow us to prove a much stronger counterpart of McDiarmid’s inequality in the next post.

## McDiarmid’s inequality

In the previous post of the mini-course, we proved Azuma–Hoeffding inequality. We were able to relax the assumption that  $X_i$  were independent but we were dealing only with their sum. Now we are to demonstrate that martingale method lets also to control more general functions  $F$  (now of independent arguments). The idea is to apply Azuma–Hoeffding inequality to the generic random sequence called Doob martingale. Continue reading

## Arrow’s impossibility theorem

There is an amazing result in the theory of social choice called Arrow’s impossibility theorem. Suppose we have a set  $A$  of  $n$  possible alternatives, say, election candidates, and  $N$  voters. Each voter organizes its individual preference list over  $A,$  that is, a linear ordering of  $A$  (suppose for simplicity that ties are not allowed). A voting system is a map of $N$-tuple of individual preference lists (also called profile) into a single ordering of  $A$ — a social preference list. A  dictatorship  is a voting system that has the following property: there is a fixed voter — a “dictator” — such that its individual preference coincides with the social preference for any possible profile. As Arrow’s theorem states,

Any consistent (in some sense) voting system turns out to be a dictatorship.

Here one may find the precise statement as well as several short proofs. Of course, it turns out that consistency, in the sense required by Arrow’s theorem, is not met in real-life voting systems as explained in this notice.

$\displaystyle F(X) = \frac{1}{n}\sum_{\i=1}^n X_i,$
where all  $X_i$  were independent. We first showed that if  $X_i$  are sufficiently “light-tailed” (subgaussian), then  $F(X)$  concentrates above its mean, with a remarkable special case when  $X_i$  are bounded. We then obtained another result (concentration of quadratic forms) for Gaussian  $X$  when  $F(X)$  is a quadratic form of a Gaussian vector (actually they can also be expanded to subgaussian case); again we by no means relaxed the independency of  $X.$  The goal of this post is to relax this assumption in some extent.