Das, Puja2014-07-012014-07-012014-05https://hdl.handle.net/11299/163662University of Minnesota Ph.D. dissertation. May 2014. Major: Computer science. Advisor: Arindam Banerjee. 1 computer file (PDF); xiii, 174 pages, appendices A-D.Today, whether we consider the data from the internet, consumers, financial markets, a common feature emerges: all of them involve huge amounts of dynamic data that arrive sequentially and need to be understood and processed quickly. Online learning is concerned with the task of making decisions on-the-fly as observations are received. Online learning has attracted a lot of attention due to the recent emergence of large-scale applications such as online web advertisement placement, online topic-detection in social communities, online web ranking, finding shortest path for internet packet routing, email spam filtering, portfolio selection and many more. In recent years, tools from convex optimization have influenced the design of many online learning algorithms. As a result, Online Convex Optimization (OCO) has emerged as a unified abstraction, which helps in solving problems efficiently and reliably and also facilitates the theoretical analysis. In this thesis, we contribute to the development of OCO and present solutions to several complex problems motivated by real world applications.Although OCO has been studied widely, one drawback of the existing algorithms is the cost of updating model parameters with every incoming data point, especially when the number of parameters is in the order of millions or billions. An example is online portfolio selection, where changing ones portfolio aggressively everyday will incur huge amount of transaction costs. In the first part of the thesis, we present an algorithm that performs lazy updates to the parameters and show that its performance is competitive with optimal strategies, which have the benefit of hindsight. The resulting convex optimization problem is non-smooth, and we use an efficient primal-dual based alternating direction method of multipliers (ADMM) to carry out lazy updates in every step. We successfully establish the effectiveness of our online lazy updates algorithm for online portfolio selection with transaction costs with experiments on real world datasets.Several machine learning algorithms use iterative optimization methods for learning predictive models. It is difficult to know upfront, which of these routines will converge faster or give the best possible solution. This is a common problem in online portfolio selection, where there could be a number of heuristics or theoretically motivated algorithms, which suggest portfolios for each day. It is not possible for an investor to know which of these portfolio selection algorithms will make the most amount of money in a given market. In the second part of the thesis, we present two Meta Algorithms (MAs), which work by adaptively combining iterates from a pool of base optimization algorithms. We show that the performance of the MAs are competitive with the best convex combination of iterates from the base algorithms. We illustrate the effectiveness of MAs on the problem of portfolio selection in the stock market.OCO has emerged as a powerful large scale optimization approach, but much of the existing literature assumes a simple way to project onto the constraint set. This assumption is often not true, and the projection step can become the key computational bottleneck. Motivated by applications in risk-adjusted portfolio selection, we consider online quadratically constrained convex optimization (QCCO) problems, where the constraint set involves intersection of multiple quadratic and linear constraints. We show that the algorithm for solving online QCCOs has theoretical performance guarantees and can be posed as a quadratically constrained quadratic program (QCQP) in each step. We present an efficient algorithm for solving QCQPs based on ADMM. We show that risk adjusted meta portfolio selection is a special case of our general framework. With extensive experiments on two real world stock datasets, we establish that our algorithm RAMP is either competitive or can achieve significantly greater wealth than existing approaches at any given risk level.A network is often defined as a collection of variables, which are inter-dependent through a complex dependency structure. In many scenarios, the structure of the network is not known beforehand and the problem of interest lies in estimating the structure based on sample data from the network variables. Examples include social networks, communication system between operators, user interaction in social media, etc. Moreover, in many domains, the network structure is not static and can change over time. For example, the relationship structure amongst stocks may change significantly over years depending on the companies' financial developments and international economic policies. In the final part of the thesis, we present an online convex optimization model for estimation of the dependency structure of a time-varying network, when the network variables follow a multivariate Gaussian distribution. Under this assumption, the conditional independence structure of the network is encoded in a sequence of precision matrices. We present an ADMM based algorithm for tracking dynamic networks and we establish theoretical performance guarantees of our method with respect to batch methods, which have the power of hindsight. With experiments over synthetic datasets and a real financial dataset, we establish that our algorithm can identify smoothly varying or abruptly evolving network structures even when the sample size is small.en-USAlternating direction method of multipliersConstrained optimizationMeta optimizationNon-smooth composite objectiveOnline convex optimizationOnline portfolio selectionThesis or Dissertation