UC Berkeley

In the last couple of decades, focus on speed and personalization has been a topic of major importance for optimization systems. The internet and big data have made users expect results immediately or with an unperceivable delay. For example, in online advertising a user is shown an ad a few milliseconds after entering a website, app, or other media. This new online environment has force optimization systems to evolve from operating in an offline fashion, i.e., assuming all the information is available a priori, to an online one. In an online setting, information arrives sequentially, and systems need to make decisions as information arrives. This thesis is composed of three main chapters. The first studies an online advertising problem that serves as a motivation for the thesis as a whole. Though motivated by the leading online advertising problem, the second and third chapters make broad contributions to optimization theory and machine learning, respectively.

In the first chapter of this thesis, we develop an optimization model and corresponding algorithm to manage a demand-side platform (DSP), whereby the DSP acquires valuable ad space for its advertiser clients in a real-time bidding environment. In particular, we focus on how a DSP should bid in real-time auctions to acquire valuable ad space to allocate between its advertiser's clients. We propose a highly flexible model for the DSP to maximize its profit while maintaining acceptable budget spending levels for its advertisers' clients. We prove that a dual formulation attains a zero-duality gap under practical settings for DSPs. Using a primal-dual scheme, we derive a bidding and allocation policy that DSPs can apply in practice.

In the second chapter of this thesis, we propose a joint online optimization and learning algorithm through dual mirror descent. Part of the motivation for this topic comes from developing an online solution/policy to solve the DSP problem mentioned above. An online policy in the sense that it gets updated using simple steps after each user arrival. We achieved this goal for DSPs who buy ad space in real-time bidding environments which use second-price auction mechanisms. No complicated optimization problem needs to be solved in advance. The contribution of this chapter of the thesis extends broadly beyond its original motivation on online advertising, making contributions in the online optimization field. In particular, we propose a new algorithm that mixes an online dual mirror descent scheme with a generic parameter learning process and a novel offline benchmark for this setup. Bounds on regret and worst possible constraints violation are studied.

In the third chapter of this thesis, we propose training neural networks jointly using subgradient-descent, Frank-Wolfe, and Frank-Wolfe variants called in-face directions. An important motivation for this chapter is how to add structure to neural networks in a principled manner. In particular, if we can promote sparsity in some layers of a neural network, we can make the overall inference step faster/cheaper. The latter is a major concern in production systems in online advertising in which the inference step of a neural network may be called billions of times per day.