Cette thèse aborde le problème de l’apprentissage avec des fonctions de perte nonmodulaires. Pour les problèmes de prédiction, où plusieurs sorties sont prédites simultanément, l’affichage du résultat comme un ensemble commun de prédiction est essentiel afin de mieux incorporer les circonstances du monde réel. Dans la minimisation du risque empirique, nous visons à réduire au minimum une somme empirique sur les pertes encourues sur l’échantillon fini avec une certaine perte fonction qui pénalise sur la prévision compte tenu de la réalité du terrain. Dans cette thèse, nous proposons des méthodes analytiques et algorithmiquement efficaces pour traiter les fonctions de perte non-modulaires. L’exactitude et l’évolutivité sont validées par des résultats empiriques. D’abord, nous avons introduit une méthode pour les fonctions de perte supermodulaires, qui est basé sur la méthode d’orientation alternée des multiplicateurs, qui ne dépend que de deux problémes individuels pour la fonction de perte et pour l’infèrence. Deuxièmement, nous proposons une nouvelle fonction de substitution pour les fonctions de perte submodulaires, la Lovász hinge, qui conduit à une compléxité en O(p log p) avec O(p) oracle pour la fonction de perte pour calculer un gradient ou méthode de coupe. Enfin, nous introduisons un opérateur de fonction de substitution convexe pour des fonctions de perte nonmodulaire, qui fournit pour la première fois une solution facile pour les pertes qui ne sont ni supermodular ni submodular. Cet opérateur est basé sur une décomposition canonique submodulairesupermodulaire. / This thesis addresses the problem of learning with non-modular losses. In a prediction problem where multiple outputs are predicted simultaneously, viewing the outcome as a joint set prediction is essential so as to better incorporate real-world circumstances. In empirical risk minimization, we aim at minimizing an empirical sum over losses incurred on the finite sample with some loss function that penalizes on the prediction given the ground truth. In this thesis, we propose tractable and efficient methods for dealing with non-modular loss functions with correctness and scalability validated by empirical results. First, we present the hardness of incorporating supermodular loss functions into the inference term when they have different graphical structures. We then introduce an alternating direction method of multipliers (ADMM) based decomposition method for loss augmented inference, that only depends on two individual solvers for the loss function term and for the inference term as two independent subproblems. Second, we propose a novel surrogate loss function for submodular losses, the Lovász hinge, which leads to O(p log p) complexity with O(p) oracle accesses to the loss function to compute a subgradient or cutting-plane. Finally, we introduce a novel convex surrogate operator for general non-modular loss functions, which provides for the first time a tractable solution for loss functions that are neither supermodular nor submodular. This surrogate is based on a canonical submodular-supermodular decomposition.

Fictitious Play is the oldest and most studied learning process for games. Since the already classical result for zero-sum games, convergence of beliefs to the set of Nash equilibria has been established for several classes of games, including weighted potential games, supermodular games with diminishing returns, and 3×3 supermodular games. Extending these results, we establish convergence of Continuous-time Fictitious Play for ordinal potential games and quasi-supermodular games with diminishing returns. As a by-product we obtain convergence for 3×m and 4×4 quasi-supermodular games.

The reliability and quality of suppliers' components are inevitably two factors that impact the performance of the supply chain. Stochastic reliability affects the final production quantity and hence makes it more difficult to predict the manufacturer's best ordering quantity as opposed to the simpler traditional news vendor model. In addition, the quality of suppliers' products directly influence the potential demand in the market. Hence every firm in the supply chain system faces the needs to invest time, money and effort to improve the product quality even though it may bring a higher production and investment cost. Thus our dissertation is divided into two parts. In the first part, we build a model for a two echelon supply chain system in which a single manufacturer sells his product to a market with stochastic demand. A group of suppliers provide essential components for the manufacturer. They may be: 1) homogeneous component suppliers, 2) complementary component suppliers or 3) divided into subgroups, suppliers in the same subgroup provide the same component while the components from different subgroups are assembled in the final product. The fraction of effective component ordered from each supplier is a random variable. We first analyze the manufacturer's optimal ordering quantity decision. We identify several important properties of the optimal decision. Then based on those properties, we devise optimal solution procedures and heuristic methods for the above three systems. Finally, in the case of Bernoulli reliability, we investigate the suppliers' price competition by non-cooperative game theory. In the second part, we model a two echelon assembly system which faces deterministic demand affected by the market price and quality of the product. Therefore, the decisions of the firms are divided into two stages: in the first stage, they decide on how much effort to invest in the quality of the components or the final product to stimulate the market. They may make decisions simultaneously or sequentially. Then after the efforts are invested, in the second stage, the component suppliers first decide on their components' wholesale price and then the manufacture decides on the market price given the wholesale price. We identify the existence of Nash equilibrium in each stage through potential functions. Moreover, in the first stage decision, we find that the competition with a leader can always benefit the whole system compared with simultaneous competition. / Ph. D.