La Data Science

Convexité avec composition et monotonie

Prouver qu’une fonction est convexe est une problématique récurrente en optimisation convexe, souvent incontournable pour l’entraînement de modèles d’apprentissage automatique.

Par exemple, la validité de la plupart des algorithmes d’optimisation des paramètres d’un modèle de régression logistique dépend du caractère convexe de la log-vraisemblance négative de ce modèle.

Pour montrer qu’une fonction est convexe, une bonne chose serait de disposer d’une « boîte à outils » contenant des propriétés que l’on peut appliquer facilement sur de nouvelles fonctions pour vérifier leur convexité, ou, au contraire, leur non-convexité.

Dans cette « boîte à outils », une question que l’on peut se poser est : est-ce que la composition de fonctions convexes et de fonctions monotones donne nécessairement naissance à des fonctions convexes ?

La question est volontairement posée de manière vague et informelle, car elle peut revêtir différentes formes, que nous allons explorer ici.

Formalisation mathématique

Ici, nous allons considérer deux fonctions : f et g. On s’intéressera à leur composition f \circ g. On ne précise pas là les espaces de départ et d’arrivée de f et g car ils importent peu.

La question que l’on va se poser est : f \circ g est-elle convexe ? Pour cela, on va faire varier les hypothèses sur f et g et l’on va regarder ce qui se passe.

✅Cas favorable : f convexe/croissante et g convexe

Hypothèse :

  • f est convexe et croissante.
  • g est convexe.

Conclusion :

  • f \circ g est convexe.

Ce scénario où f est croissante et où les deux fonctions sont convexes est le seul scénario favorable qui nous permet de conclure sur la convexité de la composée.

La preuve de ce résultat ne devrait pas poser trop de problème et est laissée au lecteur. Indication : il suffit d’appliquer la définition de la convexité et d’appliquer la croissance de f sur l’inégalité de convexité.

Le lecteur curieux pourra aussi imaginer une autre preuve dans le cas où f et g sont deux fois différentiables…

🚩f non croissante

Imaginons maintenant que l’on retire l’hypothèse de croissance de f.

A-t-on toujours f \circ g convexe ?

En fait, ce résultat serait trop beau pour être vrai. Ceci dirait que la composition de deux fonctions convexes est encore convexe. Or, cela n’est malheureusement pas vrai.

Cherchons un contre-exemple pour montrer que cette implication n’est pas valable.

Pour ça, on peut chercher une fonction f convexe, mais pas croissante et qui, quitte à ne pas être croissante, est même décroissante. La plus simple que l’on puisse trouver est sûrement x \mapsto -x.

Prenons maintenant une fonction convexe pour g. À tout hasard, prenons la fonctions carré x \mapsto x^2.

On a alors (f \circ g) (x) = -x^2, qui n’est pas convexe.

🚩f non convexe

Récupérons à présent l’hypothèse « f croissante » et relâchons l’hypothèse « f convexe ».

A-t-on alors f \circ g convexe ?

Là encore, allons à contre-courant et cherchons un contre-exemple en prenant une fonction f croissante, mais non convexe et qui, quitte à être non convexe, soit même concave. Par exemple, prenons f : x \mapsto \ln(x).

Et pour g, prenons tout simplement l’identité, c’est-à-dire g : x \mapsto x.

Alors, la composée f \circ g n’est autre que le logarithme \ln, qui est concave et non convexe.

🚩g croissante et non convexe

Supposons que l’on récupère toutes les hypothèses sur f, mais que l’on troque à présent l’hypothèse « g convexe » contre l’hypothèse « g croissante ».

Alors, de manière analogue au contre-exemple précédent, on va prendre cette fois f(x) = x et g(x) = \ln(x) et, encore une fois, la composée sera le logarithme qui n’est pas convexe.

🚩f non croissante et g croissante

Finalement, imaginons que l’on inverse les hypothèses du tout début, et que l’on prenne f seulement convexe, et g convexe et croissante.

Dans ce cas, en prenant f(x) = -x et g(x) = x^2, on aura (f \circ g)(x) = -x^2, qui donnera là encore un contre-exemple. Le problème, dans cette situation, est que f n’étant pas nécessairement croissante, elle peut renverser le comportement de g au dernier moment. C’est ce qu’illustre ce contre-exemple.

Conclusion

Lorsque l’on compose des fonctions croissantes et des fonctions convexes, la seule configuration minimale qui nous garantit d’avoir une composée f \circ g convexe s’obtient lorsque f est convexe et croissante, et g est convexe.

Jean MP

, ,
, , , ,

Laisser un commentaire