Author Archives: Dmitry Ostrovsky

About Dmitry Ostrovsky

PhD student with interests in statistics, optimization, and machine learning.

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: The load is concentrated in Fall terms with the salary spread throughout the year (+340EUR en gros for 64 hrs … Continue reading

Posted in Teaching | Leave a comment

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.

Posted in Course on Convex Optimization | Leave a comment

How closed form conjectures are made

Discovered an interesting discussion on math.stackoverflow.

Posted in Pretty little things | Leave a comment

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 … Continue reading

Posted in Course on Concentration Inequalities | Tagged | Leave a comment

McDiarmid’s inequality

In the previous post of the mini-course, we proved Azuma–Hoeffding inequality. We were able to relax the assumption that    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    (now of independent arguments). … Continue reading

Posted in Course on Concentration Inequalities | Tagged | Leave a comment

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    of    possible alternatives, say, election candidates, and    voters. Each voter organizes its individual preference list over    that is, a linear ordering of    (suppose … Continue reading

Posted in Pretty little things | Leave a comment

Azuma-Hoeffding inequality

In this post we will further expand the setting in which concentration inequalities are stated. Remember that we started from the arithmetical mean where all    were independent. We first showed that if    are sufficiently “light-tailed” (subgaussian), then    concentrates above its mean, with a remarkable special … Continue reading

Posted in Course on Concentration Inequalities | Tagged | 1 Comment