We propose a stochastic gradient framework for solving stochastic composite convex optimization problems with (possibly) infinite number of linear inclusion constraints that need to be satisfied almost surely. We use smoothing and homotopy techniques to handle constraints without the need for matrix-valued projections. We show for our stochastic gradient algorithm @math convergence rate for general convex objectives and @math convergence rate for restricted strongly convex objectives. These rates are known to be optimal up to logarithmic factors, even without constraints. We demonstrate the performance of our algorithm with numerical experiments on basis pursuit, a hard margin support vector machines and a portfolio optimization and show that our algorithm achieves state-of-the-art practical performance.
A stochastic Forward-Backward algorithm with a constant step is studied. At each time step, this algorithm involves an independent copy of a couple of random maximal monotone operators. Defining a mean operator as a selection integral, the differential inclusion built from the sum of the two mean operators is considered. As a first result, it is shown that the interpolated process obtained from the iterates converges narrowly in the small step regime to the solution of this differential inclusion. In order to control the long term behavior of the iterates, a stability result is needed in addition. To this end, the sequence of the iterates is seen as a homogeneous Feller Markov chain whose transition kernel is parameterized by the algorithm step size. The cluster points of the Markov chains invariant measures in the small step regime are invariant for the semiflow induced by the differential inclusion. Conclusions regarding the long run behavior of the iterates for small steps are drawn. It is shown that when the sum of the mean operators is demipositive, the probabilities that the iterates are away from the set of zeros of this sum are small in Ces aro mean. The ergodic behavior of these iterates is studied as well. Applications of the proposed algorithm are considered. In particular, a detailed analysis of the random proximal gradient algorithm with constant step is performed. Maximal monotone operators are set-valued mappings which extend (but are not limited to) the notion of subdifferential of a convex function. The proximal point algorithm is a method for finding a zero of a maximal monotone operator. The algorithm consists in fixed point iterations of a mapping called the resolvent which depends on the maximal monotone operator of interest. The paper investigates a stochastic version of the algorithm where the resolvent used at iteration k is associated to one realization of a random maximal monotone operator. We establish the almost sure ergodic convergence of the iterates to a zero of the expectation (in the Aumann sense) of the latter random operator. Application to constrained stochastic optimization is considered. Consider convex optimization problems subject to a large number of constraints. We focus on stochastic problems in which the objective takes the form of expected values and the feasible set is the intersection of a large number of convex sets. We propose a class of algorithms that perform both stochastic gradient descent and random feasibility updates simultaneously. At every iteration, the algorithms sample a number of projection points onto a randomly selected small subsets of all constraints. Three feasibility update schemes are considered: averaging over random projected points, projecting onto the most distant sample, projecting onto a special polyhedral set constructed based on sample points. We prove the almost sure convergence of these algorithms, and analyze the iterates' feasibility error and optimality error, respectively. We provide new convergence rate benchmarks for stochastic first-order optimization with many constraints. The rate analysis and numerical experiments reveal that the algorithm using the polyhedral-set projection scheme is the most efficient one within known algorithms. In this paper, we are interested in the development of efficient algorithms for convex optimization problems in the simultaneous presence of multiple objectives and stochasticity in the first-order information. We cast the stochastic multiple objective optimization problem into a constrained optimization problem by choosing one function as the objective and try to bound other objectives by appropriate thresholds. We first examine a two stages exploration-exploitation based algorithm which first approximates the stochastic objectives by sampling and then solves a constrained stochastic optimization problem by projected gradient method. This method attains a suboptimal convergence rate even under strong assumption on the objectives. Our second approach is an efficient primal-dual stochastic algorithm. It leverages on the theory of Lagrangian method in constrained optimization and attains the optimal convergence rate of O(1 √T) in high probability for general Lipschitz continuous objectives. This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special cases, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves @math expected regret and constraint violations and @math high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm. Cette these porte essentiellement sur l'etude d'algorithmes d'optimisation. Les problemes de programmation intervenant en apprentissage automatique ou en traitement du signal sont dans beaucoup de cas composites, c'est-a-dire qu'ils sont contraints ou regularises par des termes non lisses. Les methodes proximales sont une classe d'algorithmes tres efficaces pour resoudre de tels problemes. Cependant, dans les applications modernes de sciences des donnees, les fonctions a minimiser se representent souvent comme une esperance mathematique, difficile ou impossible a evaluer. C'est le cas dans les problemes d'apprentissage en ligne, dans les problemes mettant en jeu un grand nombre de donnees ou dans les problemes de calcul distribue. Pour resoudre ceux-ci, nous etudions dans cette these des methodes proximales stochastiques, qui adaptent les algorithmes proximaux aux cas de fonctions ecrites comme une esperance. Les methodes proximales stochastiques sont d'abord etudiees a pas constant, en utilisant des techniques d'approximation stochastique. Plus precisement, la methode de l'Equation Differentielle Ordinaire est adaptee au cas d'inclusions differentielles. Afin d'etablir le comportement asymptotique des algorithmes, la stabilite des suites d'iteres (vues comme des chaines de Markov) est etudiee. Ensuite, des generalisations de l'algorithme du gradient proximal stochastique a pas decroissant sont mises au point pour resoudre des problemes composites. Toutes les grandeurs qui permettent de decrire les problemes a resoudre s'ecrivent comme une esperance. Cela inclut un algorithme primal dual pour des problemes regularises et lineairement contraints ainsi qu'un algorithme d'optimisation sur les grands graphes.