Optimizing penalized and constrained loss functions with applications to large-scale internet media selection

The use of penalized loss functions in optimization procedures is prevalent throughout the statistical literature. However, penalized loss function methodology is less familiar outside the areas of mathematics and statistics, and even within statistics loss functions are typically studied on a problem-by-problem basis. In this thesis I present general loss function approaches for both penalized as well as penalized and constrained loss functions and apply these approaches to a problem outside statistics, namely the optimization of a large-scale Internet advertising campaign. ❧ Recent work in penalized loss functions has focused largely on linear regression methods with excellent results. Methods like the LASSO (Tibshirani 1996a) have demonstrated that penalization can yield gains in both prediction accuracy and algorithmic efficiency. In cases where linearity is not appropriate, however, the best approaches can be unclear. To this end I propose a generalized methodology, applicable to many loss function for which the first and second derivatives can be readily computed. This leverages the efficiency benefits seen in penalized linear regression approaches and applies them to problems of general nonlinear objectives. ❧ Unfortunately, as useful as penalization is in optimization, many problems require another step: constraints. Problems like portfolio optimization or monotone curve estimation have very natural constraints which need to be taken into account directly during the optimization. Because of this, I propose a further advance in the penalized methodology: PAC, or penalized and constrained regression. PAC is capable of incorporating constraints directly into the optimization, allowing for better parameter estimation when compared to unconstrained methods. Again, the use of penalization allows for efficient algorithms applicable to a wide variety of problems. ❧ One such problem comes from the field of marketing: the optimization of large-scale Internet advertising campaigns. I apply both approaches to the real-world problem encountered by firms and advertising agencies when attempting to select a set of websites to use for advertising and then allocating an advertising budget over those websites. Due to the sheer number of websites available for advertising, all of which represent a unique advertising opportunity with varying cost, traffic, etc., these selection and allocation questions can present daunting challenges to anyone wanting to advertise online. At the same time, online advertising is becoming increasingly necessary to businesses of all industries. To address this, I show how the efficient penalized approaches developed in the general case can be specifically applied to this problem. I carry out two case studies using real data from comScore, Inc., which exemplify campaign considerations faced by companies today. Further, I show how these methods significantly improve on the methods currently available. ❧ I also discuss future directions for the research in this thesis, particularly in the real-world application of Internet media campaigns. Though this research could be extended in a wide variety of directions, I focus on furthering the marketing application to extend to the most current advertising procedure, bidding on ad impressions in real time, as well as extending the penalized and constrained approach to include time-varying objective functions (for problems in which the behavior of one time period affects the optimization of a second time period).惩罚损失函数（penalized loss function）在优化流程中的应用在统计研究文献中已十分普及。然而，该类方法在数学与统计学以外的领域中认知度较低；即便在统计学范畴内，损失函数的研究通常也多以单个问题为导向，逐个展开。在本论文中，笔者提出了适用于惩罚损失函数，以及惩罚与约束结合损失函数的通用研究框架，并将该框架应用于统计学以外的一个实际问题：大规模互联网广告活动优化。 近年来针对惩罚损失函数的研究多聚焦于线性回归方法，并已取得优异成果。诸如套索回归（LASSO, Tibshirani 1996a）这类方法已证实，惩罚机制可同时提升预测精度与算法运行效率。然而在线性假设不再适用的场景中，最优解决方案往往尚不明确。为此，笔者提出了一种通用方法论，可适用于多数可便捷计算一阶与二阶导数的损失函数。该方法借鉴了惩罚线性回归方案中的效率优势，并将其推广至通用非线性目标优化问题。 尽管惩罚机制在优化中极具价值，但诸多实际问题还需引入约束条件。诸如投资组合优化、单调曲线估计等问题，均存在极为自然的约束条件，需在优化过程中直接纳入考量。有鉴于此，笔者在惩罚方法的基础上提出了进一步改进方案：PAC（惩罚约束回归，penalized and constrained regression）。相较于无约束方法，PAC可直接将约束条件融入优化流程，从而实现更优质的参数估计效果。同样，惩罚机制的应用使得该方法可适配各类问题的高效求解算法。 此类问题的一个典型案例来自营销领域：大规模互联网广告活动的优化。笔者将上述两种方法应用于企业与广告代理商在实际运营中遇到的问题：即选定用于投放广告的网站集合，并在这些网站间分配广告预算。由于可用于广告投放的网站数量极其庞大，且每个网站均具备独特的广告投放机会，其成本、流量等指标各不相同，此类选择与分配问题会为在线广告投放者带来极具挑战性的难题。与此同时，在线广告已成为各行业企业愈发不可或缺的营销手段。为解决该问题，笔者展示了如何将通用场景下开发的高效惩罚方法具体应用于此问题。笔者采用comScore公司的真实数据开展了两项案例研究，以此展现当前企业在广告活动中面临的实际考量。进一步地，笔者证实了该方法相较现有方法可实现显著提升。 笔者还探讨了本论文研究的未来方向，尤其是互联网媒体广告活动的实际应用场景。尽管该研究可在诸多方向上进行拓展，笔者将重点聚焦于两方面的延伸：一是将营销应用场景拓展至当前最前沿的广告投放流程——实时广告展示竞价；二是将惩罚约束方法推广至含时变目标函数的问题（即某一时间段的优化行为会影响下一时间段优化过程的场景）。