Stochastic Frank-Wolfe for Composite Convex Minimization

A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees O(k(-1/3)) convergence rate in expectation on the objective residual and O(k (5/12)) on the feasibility gap.

Stochastic distributed learning with gradient quantization and double-variance reduction

Konstantin Mishchenko, Sebastian Urban Stich

We consider distributed optimization over several devices, each sending incremental model updates to a central server. This setting is considered, for instance, in federated learning. Various schemes have been designed to compress the model updates in order to reduce the overall communication cost. However, existing methods suffer from a significant slowdown due to additional variance omega > 0 coming from the compression operator and as a result, only converge sublinearly. What is needed is a variance reduction technique for taming the variance introduced by compression. We propose the first methods that achieve linear convergence for arbitrary compression operators. For strongly convex functions with condition number kappa, distributed among n machines with a finite-sum structure, each worker having less than in components, we also (i) give analysis for the weakly convex and the non-convex cases and (ii) verify in experiments that our novel variance reduced schemes are more efficient than the baselines. Moreover, we show theoretically that as the number of devices increases, higher compression levels are possible without this affecting the overall number of communications in comparison with methods that do not perform any compression. This leads to a significant reduction in communication cost. Our general analysis allows to pick the most suitable compression for each problem, finding the rig ht balance between additional variance and communication savings. Finally, we also (iii) give analysis for arbitrary quantized updates.

TAYLOR & FRANCIS LTD2022

Dimensionality Reduction in Dynamic Optimization under Uncertainty

Napat Rujeerapaiboon

Dynamic optimization problems affected by uncertainty are ubiquitous in many application domains. Decision makers typically model the uncertainty through random variables governed by a probability distribution. If the distribution is precisely known, then the emerging optimization problems constitute stochastic programs or chance constrained programs. On the other hand, if the distribution is at least partially unknown, then the emanating optimization problems represent robust or distributionally robust optimization problems. In this thesis, we leverage techniques from stochastic and distributionally robust optimization to address complex problems in finance, energy systems management and, more abstractly, applied probability. In particular, we seek to solve uncertain optimization problems where the prior distributional information includes only the first and the second moments (and, sometimes, the support). The main objective of the thesis is to solve large instances of practical optimization problems. For this purpose, we develop complexity reduction and decomposition schemes, which exploit structural symmetries or multiscale properties of the problems at hand in order to break them down into smaller and more tractable components. In the first part of the thesis we study the growth-optimal portfolio, which maximizes the expected log-utility over a single investment period. In a classical stochastic setting, this portfolio is known to outperform any other portfolio with probability 1 in the long run. In the short run, however, it is notoriously volatile. Moreover, its performance suffers in the presence of distributional ambiguity. We design fixed-mix strategies that offer similar performance guarantees as the classical growth-optimal portfolio but for a finite investment horizon. Moreover, the proposed performance guarantee remains valid for any asset return distribution with the same mean and covariance matrix. These results rely on a Taylor approximation of the terminal logarithmic wealth that becomes more accurate as the rebalancing frequency is increased. In the second part of the thesis, we demonstrate that such a Taylor approximation is in fact not necessary. Specifically, we derive sharp probability bounds on the tails of a product of non-negative random variables. These generalized Chebyshev bounds can be computed numerically using semidefinite programming--in some cases even analytically. Similar techniques can also be used to derive multivariate Chebyshev bounds for sums, maxima, and minima of random variables. In the final part of the thesis, we consider a multi-market reservoir management problem. The eroding peak/off-peak spreads on European electricity spot markets imply reduced profitability for the hydropower producers and force them to participate in the balancing markets. This motivates us to propose a two-layer stochastic programming model for the optimal operation of a cascade of hydropower plants selling energy on both spot and balancing markets. The planning problem optimizes the reservoir management over a yearly horizon with weekly granularity, and the trading subproblems optimize the market transactions over a weekly horizon with hourly granularity. We solve both the planning and trading problems in linear decision rules, and we exploit the inherent parallelizability of the trading subproblems to achieve computational tractability.

EPFL2016

Dimensionality Reduction in Dynamic Optimization under Uncertainty

Napat Rujeerapaiboon

EPFL2016