Browsing by Subject "convex optimization"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A Modern Treatise on Variational Inequality Problems: Structures, Algorithms, and Iteration Complexities
    (2023-05) Huang, Kevin
    In this thesis, we study the variational inequality (VI) problem with the methodology of designing efficient (or optimal) algorithms and analyzing their (sample/gradient) iteration complexities. In particular, we aim to explore the hidden structures in VI that have not been (fully) studied before and use them as insights to guide the development of new optimal algorithms that align with the modern research trends in both VI and optimization. We start from the first-order methods, where acceleration has been established in algorithms such as extra-gradient method, optimistic gradient descent ascent method, and dual extrapolation method. These methods are known as optimal in the sense that they match the lower iteration complexity bounds established for first-order methods in (strongly) monotone VI. We observe that these acceleration schemes in VI, together with the acceleration schemes used in optimization such as Nesterov's acceleration, share a common structure: using additional sequence(s), which we refer to it as ``extra points'', to help improve the convergence of the main sequence. We then propose a general guideline, called the extra-point approach, to construct optimal first-order methods via a more systematic way, which provides flexibility in adopting a variety of extra points/sequences such that the lower bounds take effect. Moving towards high-order methods, research before has relied on using high-order Taylor approximation and an iterative binary-search in solving the subproblems. We show that both of them are not necessary in developing high-order methods, and the key lies in satisfying a high-order Lipschitz bound for any approximation operator used in the subroutine, as well as an appropriate order of regularization to eliminate the needs of binary-search. The proposed unifying framework largely relieves the demand on the complicated analysis derived for different methods and allows us to focus more on the problem structure to design a suitable approximation operator in the algorithm. We also investigate stochastic algorithms for VI, mainly focusing on the stochastic approximation (SA) approach. We propose stochastic extensions of two new first-order methods, which could be viewed as special instances following the aforementioned extra-point approach, and show that optimal iteration complexities can be established for them, in both situations where the stochastic errors are bounded separately or they are reduced together with the deterministic terms. Application is discussed using the example of black-box saddle point problem where even the function values can only be estimated with noises. Using a smoothing technique, we show that by constructing the stochastic zeroth-order gradients, the previous schemes can be readily applied with the guarantee on sample iteration complexities. Another aspect of stochasticity is discussed following the similar line of research, where we study the VI problems with the finite-sum structure. In addition, such finite-sum structure consists of both general vector mappings and gradient mappings. Developments in variance reduced algorithms for both finite-sum optimization and finite-sum VI have been found recently, but none has focused on finite-sum VI with optimization structures. We propose two algorithms for both monotone and strongly monotone VI that explicitly make use of such optimization structure and demonstrate that they indeed serve as a bridge between these two problem classes and are able to perform better than general variance reduced VI algorithms when such structure is actually present. We show that the saddle point reformulation of a finite-sum optimization with finite-sum constraints immediately take the aforementioned forms in VI, where applications are commonly seen in Neyman-Pearson classification in machine learning. Finally, the research in this thesis is extended to non-monotone VI and the solution methods for solving it. Without the monotonicity, another (weaker) global property of the VI problem, the existence of Minty solution, comes to play a central role in the convergence of accelerated projection-type methods. With a slightly worse iteration complexity than the monotone VI, we show that how a general high-order extra-gradient-type method using the concept of the aforementioned approximation can converge. Furthermore, when the existence of Minty solution is no longer assumed, very little can be said in general about the convergence of these projection-type methods. Alternatively, we use these methods as starting points and derive sufficient conditions that characterize various structures of VI where they can converge with guaranteed iteration complexity bounds. This approach allows us to extend our study to potentially broader VI problem classes that have no monotonicity nor Minty solutions.
  • Thumbnail Image
    Item
    Online Convex Optimization in Changing Environments and its Application to Resource Allocation
    (2019-12) Yuan, Jianjun
    In the era of the big data, we create and collect lots of data from all different kinds of sources: the Internet, the sensors, the consumer market, and so on. Many of the data are coming sequentially, and would like to be processed and understood quickly. One classic way of analyzing data is based on batch processing, in which the data is stored and analyzed in an offline fashion. However, when the volume of the data is too large, it is much more difficult and time-consuming to do batch processing than sequential processing. What’s more, sequential data is usually changing dynamically, and needs to be understood on-the-fly in order to capture the changes. Online Convex Optimization (OCO) is a popular framework that matches the above sequential data processing requirement. Applications using OCO include online routing, online auctions, online classification and regression, as well as online resource allocation. Due to the general applicability of OCO to the sequential data and the rigorous theoretical guarantee, it has attracted lots of researchers to develop useful algorithms to fulfill different needs. In this thesis, we show our contributions to OCO’s development by designing algorithms to adapt to changing environments. In the first part of the thesis, we propose algorithms to have better adaptivity by examining the notion of dynamic regret, which compares the algorithm’s cumulative loss against that incurred by a comparison sequence. Dynamic regret extends a common performance measure known as static regret. Since it may not be known whether the environment is dynamic or not, it is desirable to take advantage of both regrets by having a trade-off between them. To achieve that, we discuss recursive least-squares algorithms and show how forgetting factors can be used to develop new OCO algorithms that have such a regret trade-off. More specifically, we rigorously characterize the effect of forgetting factors for a class of online Newton algorithms. For exp-concave or strongly convex objective, the improved dynamic regret of max{O(log T),O(\sqrt{TV })} is achieved, where V is a bound on the path length of the comparison sequence. In particular, we show how classic recursive least-squares with a forgetting factor achieves this dynamic regret bound. By varying V , we obtain the regret trade-off. In order to obtain more computationally efficient algorithm, we also propose a novel gradient descent step size rule for strongly convex functions, which recovers the dynamic regret bounds described above. For smooth problems, we can obtain static regret of O(T^{1−\beta}) and dynamic regret of O(T^{\beta}V^*), where \beta\in(0,1) and V^* is the path length of the sequence of minimizers. By varying \beta, we obtain the regret trade-off. The second part of the thesis describes how to design efficient algorithms to adapt to the changing environments. Previous literature runs a pool of algorithms in parallel to gain better adaptivity, which increases both the running time and the online implementation complexity. Instead, we propose a new algorithm requiring only one update per time step, while with the same adaptive regret performance guarantee as the current state-of-the-art result. We then apply the algorithm to online Principal Component Analysis (online PCA) and variance minimization under changing environments, since the previous literature on online PCA has focused on performance guarantee under stationary environment. We demonstrate both theoretically and experimentally that the proposed algorithms can adapt to the changing environments. The third part of the thesis starts from the observation that the projection operator used in constrained OCO algorithms cannot really achieve true online implementation due to the high time-consumption. To accelerate the OCO algorithms’ update, previous literature is proposed to approximate the true desired projection with a simpler closed-form one at the cost of constraint violation (g(\theta) >0) for some time steps. Nevertheless, it can guarantee sub-linearity for both the static regret and the long-term constraint, \sum_{t=1}^T g(\theta_t), having constraint satisfaction on average. However, the sub-linear long-term constraint does not enforce small constraint violation for every time step, because a strictly feasible solution can cancel out the effects of violated constraints. To resolve it, we propose algorithms to have the cumulative constraint of the form \sum_{t=1}^T(max{g(\theta_t), 0})^2 upper bounded sub-linearly. This new form heavily penalizes large constraint violations while the cancellation effects cannot occur. Furthermore, useful bounds on the single step constraint violation are derived. For convex objectives, our result generalizes existing bounds, and for strongly convex objectives we give improved regret bounds. In numerical experiments, we show that our algorithm closely follows the constraint boundary leading to low cumulative violation. Furthermore, we extend the proposed algorithms’ idea to the more general time-dependent online resource allocation problems with performance guarantee by a variant of dynamic regret.
  • Thumbnail Image
    Item
    Quantifying Political Leaning from Tweets, Retweets, and Retweeters
    (IEEE Transactions on Knowledge and Data Engineering, 2016) Wong, Felix MFW; Tan, Chee Wei; Sen, Soumya; Chiang, Mung
    The widespread use of online social networks (OSNs) to disseminate information and exchange opinions, by the general public, news media and political actors alike, has enabled new avenues of research in computational political science. In this paper, we study the problem of quantifying and inferring the political leaning of Twitter users. We formulate political leaning inference as a convex optimization problem that incorporates two ideas: (a) users are consistent in their actions of tweeting and retweeting about political issues, and (b) similar users tend to be retweeted by similar audience. Then for evaluation and a numerical study, we apply our inference technique to 119 million election-related tweets collected in seven months during the 2012 U.S. presidential election campaign. Our technique achieves 94% accuracy and high rank correlation as compared with manually created labels. By studying the political leaning of 1,000 frequently retweeted sources, 230,000 ordinary users who retweeted them, and the hashtags used by these sources, our numerical study sheds light on the political demographics of the Twitter population, and the temporal dynamics of political polarization as events unfold.