Auteur/autrice : Paulo Goncalves

 

Justin Romberg
http://users.ece.gatech.edu/justin/Justin_Romberg.html
School of Electrical and Computer Engineering, Georgia Tech

VENUE

ENS Lyon, Site Jacques Monod.
Room: Amphitheater B – 3rd floor

(local correspondant: Paulo Gonçalves)

PROGRAM and MATERIAL

Basis decompositions and frames (3-4 hours)
[notation, basis, frames, dct-notes, wavelets, sparsity-overview]

• fundamentals of basis and frame decompositions
• the discrete cosine transform and applications to image/video compression
• the lapped orthogonal transform
• wavelets
• thresholding for noise reduction

Sparsest decomposition from a dictionary (3-4 hours)
[lecture-2-1-sparseapprox, lecture-2-2-bp, lecture-2-3-upsparse]

• omp and basis pursuit for selecting atoms
• uncertainty principles and sparsest decomposition
• the « spikes+sines » dictionary
• general unions of orthobases

Introduction to compressive sampling and applications (2 hours)
[csoverview-part1,csoverview-part2,csoverview-part3,csoverview-part4] 

Recovering sparse vectors from linear measurements (6 hours/ 1 day)
[lecture-3-1-invprobs,lecture-3-2-ls,lecture-3-3-l1dual,lecture-3-4-l1cone,lecture-3-5-stable]

• review of classical least-squares theory:
• the svd, pseudo-inverse, stability analysis, regularization
• sparse recovery conditions: l1 duality
• sparsest decomposition revisited (with random support)
• the restricted isometry property and sparse recovery
• l1 for perfect recovery from noise-free measurements
• l1 stability
• l2 stability

Random matrices are restricted isometries (2 hours)
[lecture-4-1-gaussrip] 

Optimization (6 hours / 1 day)
[lecture-5-1-sdcg,lecture-5-2-newtonlog,lecture-5-3-streamingl2,lecture-5-4-streamingl1,lasso-dual-notes]
[siamOptimTalk] 

• conjugate gradients
• newton iterations
• newton iterations
• log-barrier methods
• first-order l1 solvers
• greedy algorithms and iterative thresholding
• recursive least-squares
• the Kalman filter
• dynamic l1 updating

Low-rank recovery (2 hours)

TIMETABLE

Monday 9:  10:00am – 12:00am ; 2:00pm – 5:00pm  (5 hours)
Tuesday 10:  9:30am – 12:00am ;  2:00pm – 5:00pm  (5,5 hours)
Wednesday 11:  9:30am – 12:00am ; 2:00pm – 5:00pm  (5,5 hours)
Thursday 12:  9:30am – 12:30pm ; free afternoon  (3 hours)
Friday 13:  9:00am – 12:00am ; 2:00pm – 4:00pm  (5 hours)

Intervenant : François Baccelli (http://www.di.ens.fr/~baccelli/)

The lecture will be taught in English.

Dates : 10 – 14 janvier 2011 – ENS Lyon

Planning:

lundi : 10h30 : 12h30 – 14h00 : 17h00
mardi : 10h00 : 12h00 – 14h00 : 17h00
mercredi : 10h00 : 12h00 – 14h00 : 17h00
jeudi : 10h00 : 12h00 – 14h00 : 17h00
vendredi : 10h00 : 12h00 – 14h00 : 16h00

Objectif: Introduction à la géométrie stochastique et application à la modélisation des communications dans les réseaux sans fil.

Programme (prévisionnel)

Part I – Classical Stochastic Geometry

1. Poisson Point Process
2. Marked Point Processes and Shot-Noise Fields
3. Boolean Model
4. Voronoi Tessellation

Part II – Signal-to-Interference Ratio Stochastic Geometry

5. Signal-to-Interference Ratio Cells
6. Interacting Signal-to-Interference Ratio Cells
7. Signal-to-Interference Ratio Coverage
8. Signal-to-Interference Ratio Connectivity

Part III – Medium Access Control

9. Spatial Aloha: the Bipole Model
10. Receiver Selection in Spatial Aloha
11. Carrier Sense Multiple Access
12. Code Division Multiple Access in Cellular Networks

Part IV – Multihop Routing in Mobile ad Hoc Networks

13. Optimal Routing
14. Greedy Routing
15. Time-Space Routing

Prérequis : Probabilités (à cet effet, les étudiants de M1 sont vivement invités à suivre le cours de L3 « Probabilités – Statistiques« )

Documents de support : monographie « Stochastic Geometry and Wireless Networks » (2009), by F. Baccelli and B. Blaszczyszyn (available on-line at http://www.di.ens.fr/~baccelli/)

Correspondant local : P. Gonçalves.
Sponsor : Pôle ResCom du GDR CNRS ASR

Intervenants :  Claude Lemaréchal (http://www.inrialpes.fr/bipop/people/lemarechal/) &  Jérôme Malick (http://www.inrialpes.fr/bipop/people/malick/)

Dates : 17 – 21 janvier 2011 – ENS Lyon

Planning (sujet à modifications):

Lundi (3h30) —  Introduction

• 10h30 – 12h — présentation du cours, objectifs
• 13h30 – 15h30 — introduction a l’optimisation, exemples

Mardi (5h15) — Optimisation classique

• 10h30 -12h  — principes algorithmiques
• 13h30 – 15h15 — méthodes classiques, méthodes pour la grande taille
• 15h30 – 17h30 — TP

Mercredi (5h) — Optimisation convexe non-différentiable

• 09h00 – 12h00  — non-différentiabilité naturelle, ou provoquée
• 13h30 – 15h30  — TD

Jeudi (5h15) — Théorie de l’optimisation convexe

• 10h30 – 12h   — analyse convexe
• 13h30 – 15h15  — théorie de la dualité
• 15h30 – 17h30  — TD

Vendredi (5h) — Algorithmique de l’optimisation non-différentiable

• 9h – 10h30 — algorithmes à oracle
• 10h30 – 12h  — algorithmes pour problèmes structurés
• 13h30 – 15h30  — fin + examen

Langue de la présentation : FRANCAIS.

Objectifs:

1. introduction a l’optimisation, applications sur des problèmes réels
2. algorithmique de l’optimisation convexe non-différentiable
3. relaxations convexes de problèmes combinatoires, décomposables ou non-convexes structurés

Programme prévisionnel : (enveloppe supérieure du programme)

———————
Partie 1 : Introduction à l’optimisation
– qu’est ce qu’un problème d’optimisation ? objectifs, classification
– exemples: moindres carrés, gestion de production, allocation
– principes mathématiques, rôle de la convexité
– principes algorithmiques: estimation + correction

———————
Partie 2 : Algorithmes d’optimisation différentiable

2.1 principes des méthodes classiques
– estimation : (quasi- Gauss-) Newton
– correction : recherche linéaire, région de confiance
– exemple : classification supervisée

2.2 méthodes pour la grande taille
– mémoire limitée, Newton tronqué
– exemples : prévision météo, maximisation d’entropie

———————
Partie 3 : Optimisation non-différentiable: théorie et applications

3.1 motivations:
– non-différentiabilité naturelle
– non-différentiabilité provoquée : relaxation, problèmes décomposables, optimisation combinatoire

3.2 éléments d’analyse convexe
– sous-différentiabilité
– conjugaison, dualité (Lagrange, Fenchel)
– analyse de sensibilité, interprétation économique

3.3 applications :
– optimisation de la production électrique
– optimisation des réseaux de communication
– optimisation de valeurs propres, application en théorie des graphes

———————
Partie 4 : Algorithmes d’optimisation convexe non-différentiable

4.1 Problèmes à oracle
– méthodes: sous-gradient, plans sécants, faisceaux
– récupération primale
– identification du second-ordre

4.2 Problèmes à non-différentiabilité structurée
– exploitation de la structure
– méthode de points intérieurs
– optimisation semidéfinie (SDP)
– relaxations SDP et applications (combinatoire, stats)

———————
Partie 5 : Deux applications de l’optimisation

4.1 Apprentissage
– contexte, rôle de l’optimisation, exemples
– applications des algorithmes, nouveaux enjeux numériques, optimisation « huge-scale »
– illustrations en vision par ordinateur, en bio-stats

4.2 Optimisation polynomiale
– optimisation globale, lien avec l’optimisation semidéfinie (SDP)
– approximations successives par SDP, preuve de fermeture
– illustrations en commande de systèmes, en certification de programmes

Correspondants locaux : T. Begin et P. Gonçalves.
Sponsor : Pôle ResCom du GDR CNRS ASR

du 25 au 29 janvier 2010 — ENS Lyon

Intervenants :

• Eitan Altman
• Rachid ElAzouzi
• Corinne Touati

Location and schedule

All the lectures will take place in amphitheater B, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).

Schedule:

• Monday 25/01/2010 Morning: Eitan Altman 11:00 – 13
  Zero-sum Games: these are the most elementary game where there are two players, one playing against the other. These games are useful for modeling malicious users, denial of service attacks, jamming etc.  We introduce the notions of upper and lower values as well as the notion of value of a zero-sum game. We present some minimax theorems which are used to establish the existence of a value. We end with an LP solution for Zero sum matrix games. We present examples of games with and without a value.   Solution of 2 by 2 matrix games.
  Non-zero sum games. We present the notion of Nash equilibrium as   well as epsilon Nash equilibrium. We then introduce    Coordination Games and present their properties. We then study    Lemke’s algorithm for computing the equilibrium in non-zero sum games    with two players. We present examples of channel selection games.   We end this part with the concept of Correlated equilibrium

  Afternoon: Corinne Touati 14h30 – 17h00
  Notions from cooperative game theory: Bargaining and fairness.
  Le but de cette partie est de comprendre comment appréhender les qualités d’une allocation (équilibre de Nash ou valeur optimisant une fonction par exemple). Nous commençons par la définition de la propriété d’optimalité. Parmi l’ensemble des points optimaux, un ensemble de critères permet de choisir un point dit équitable. Nous présentons des techniques numériques permettant d’approcher la frontière de Pareto et de calculer les points équitables. Enfin, nous verrons dans une dernière partie des méthodes d’évaluations des performances d’allocations, en terme à la fois d’équité et d’optimalité.
  1. Optimalité
  a. Définition de Pareto et notions liées
  b. Propriétés des ensembles de Pareto (par ex. compacité)
  c. Epsilon-approximation et méthodes de résolutions
  d. Introduction à l’optimisation multi-critères, exemple d’un problème d’ordonnancement.

• Tuesday 26/01/10  Morning: Corinne Touati 10:30 – 12:30
  2. Fairness and Nash bargaining.
  a. Axiomatic definitions: Thomson, Raiffa-Kalai-Smorodinsky, Nash)
  b. Equivalent optimizations and properties
  c. Alpha fairness
  d. Algorithmic solutions.
  e. Application to flow control and TCP.
  3. Performance evaluation of the resource allocation:
  a. The Gain index,
  b. Price of anarchy
  c. Selfish Degradation Factor
  d. Pareto equilibrium

  Afternoon: Eitan Altman 14:00 – 16:30
  Convex games. These are games with a convex compact space. We shall study Rosen’s theory for the existence of an equilibria,   The strict diagonal concavity property (which extends concavity    to a game context). This notion is used to establish    uniqueness of equilibrium in convex games.
  We then introduce games with coupled constraints    as in Rosen, as well as the related    notion of generalized Equilibrium. These are equilibria in which the space of actions of each player are not independent: the actions available to a player may depend on those already chosen by others (for example, if there are capacity constraints over links then the amount of flow that a player can send over a link depends on how much other players send over that link). In the presence of such constrained there is in general no uniqueness of equilibrium. We thus introduce the problem of equilibrium selection. We introduce in particular the notion of normalized Nash equilibrium which and and relate it to scalable pricing.

• Wednesday 27/01/10Morning Rachid El-Azouzi 9h30 – 12h30
  Energy-efficient power control games Non-cooperative games where terminals want to maximize the number of information bits per joule are analyzed. The solution of this game is shown to be inefficient.
  Medium access games: the aloha game.

  Afternoon Rachid El-Azouzi 14:00 – 17:00
  Super-modular Games and Potential Games. These are two classes of games in which not only do we know that equilibria exists, but we also know that sequence of best responses of players convenrge to the equilibrium. In particular, we show how potential games can be transformed into a global optimization problem whose optimum corresponds to the equilibrium of the original game.
  Routing games Wardrop equilibrium: the players are modeled as infinitesimally small, which means that we have a continuum of players. computation of the equilibrium of the game
  Definitions. Price of anarchy, price of stability, variational inequalities. Link between Nash and Wardrop equilibria.

• Thursday 28/01/10Morning: Corinne Touati 10:30 – 12:30
  Evolutionary game theory and population games. (games are related to infinite number of players). We introduce the concept of equilibrium is Evolutionary Stable Strategy, which is more general than a Nash equilibrium in a given sense.
  Replicator Dynamics and evolutionary dynamics: Methods for convergence to equilibria, cases of non-convergence and oscillations. Based on the idea that higher fitness will be adopted by a growing number of individuals. Other evolutionary dynamics: Brown-von Neumann-Nash, Best response dynamics, Fictitious play, Logit response dynamics. We will discuss about the main difference of those dynamics and present a generalization which is called the revision protocols.

  Afternoon: Corinne Touati 14:00 – 17:00
  Learning in games. All the previous evolutionary dynamics are related to learning process. The theory of learning in games explains the dynamic behavior of each player or agents depending on its own experience. Those learning processes related to the evolutionary dynamics, are used in order to construct distributed algorithms converging to equilibrium (Nash or ESS). We will introduce an example of distributed algorithm proposed in the literature which has been widely used in the networking community for power control, pricing, resource sharing and routing protocol. We will present other reinforcement learning algorithms: the Erev-Roth algorithm, and the Arthur algorithm for a variant of the last one with renormalization. Those distributed algorithms have interesting properties of implementation as they are totally distributed but they suffer from stability problems at the boundary of the state space. We will investigate how feedback delays and errors affect convergence

• Friday 29/01/10Morning: Eitan Altman  11:00  – 13:00
  The Braess paradox. Routing games with finitely many users: Uniqueness of the equilibrium.  Parallel links. Load balancing problems. Relation to Ad-hoc networks.

  Afternoon: Eitan Altman 14:30 – 17:00
  Introduction to Repeated Games. Threats and punishments. Credibility of threats and refinements of equilibria. Stochastic games and Dynamic programming approach for stochastic games. The discouted cost and the average cost games. Product stochastic games. Anonymous sequential games, Markov Decision Evoluationary Games.

Correspondant local

• Paulo Goncalves