Niangjun  Chen

Research Scientist, Computer Science
Institute for High Performance Computing (IHPC)
Email: niangjun [AT] gmail.com


I am a research scientist working at Institute for High Performance Computing (IHPC) in Singapore. During my doctoral studies at Caltech, I was with the Computing and Mathematical Sciences (CMS) department under the supervision of Professor Adam Wierman and Professor Steven Low. My research interests lie in online algorithms, optimization and mechanism design and their applications to the future energy systems. [CV] [Google Scholar profile].

Publications


  1. J. Comden, S. Yao, N. Chen, H. Xing, Z. Liu "Online Optimization in Cloud Resource Provisioning: Predictions, Regrets, and Algorithms" , Sigmetrics, 2019 [show/hide abstract]
    Due to mainstream adoption of cloud computing and its rapidly increasing usage of energy, the efficient management of cloud computing resources has become an important issue. A key challenge in managing the resources lies in the volatility of their demand. While there have been a wide variety of online algorithms (e.g. Receding Horizon Control, Online Balanced Descent) designed, it is hard for cloud operators to pick the right algorithm. In particular, these algorithms vary greatly on their usage of predictions and performance guarantees. This paper aims at studying an automatic algorithm selection scheme in real time. To do this, we empirically study the prediction errors from real-world cloud computing traces. Results show that prediction errors are distinct from different prediction algorithms, across virtual machines, and over the time horizon. Based on these observations, we propose a simple prediction error model and prove upper bounds on the dynamic regret of several online algorithms. We then apply the empirical and theoretical results to create a simple online meta-algorithm that chooses the best algorithm on the fly. Numerical simulations demonstrate that the performance of the designed policy is close to that of the best algorithm in hindsight.

  2. N. Chen*, G. Goel*, A. Wierman, "Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent" , Conference on Learning Theory (COLT), 2018 *Equal contribution [show/hide abstract]
    We study Smoothed Online Convex Optimization, a version of online convex optimization where the learner incurs a penalty for changing her actions between rounds. Given a known Ω(\sqrt{d}) lower bound on the competitive ratio of any online algorithm, where d is the dimension of the action space, we ask under what conditions this bound can be beaten. We introduce a novel algorithmic framework for this problem, Online Balanced Descent (OBD), which works by iteratively projecting the previous point onto a carefully chosen level set of the current cost function so as to balance the switching costs and hitting costs. We demonstrate the generality of the OBD framework by showing how, with different choices of "balance," OBD can improve upon state-of-the-art performance guarantees for both competitive ratio and regret; in particular, OBD is the first algorithm to achieve a dimension-free competitive ratio, 3+O(1/α), for locally polyhedral costs, where α measures the "steepness" of the costs. We also prove bounds on the dynamic regret of OBD when the balance is performed in the dual space that are dimension-free and imply that OBD has sublinear static regret.

  3. G. Goel, N. Chen, A. Wierman, "Thinking Fast and Slow: Optimization Decomposition Across Timescales" , IEEE Conference on Decision and Control (CDC), 2017. [show/hide abstract]
    Many real-world control systems, such as the smart grid and human sensorimotor control systems, have decentralized components that react quickly using local infor- mation and centralized components that react slowly using a more global view. This paper seeks to provide a theoretical framework for how to design controllers that are decomposed across timescales in this way. The framework is analogous to how the network utility maximization framework uses opti- mization decomposition to distribute a global control problem across independent controllers, each of which solves a local problem; except our goal is to decompose a global problem temporally, extracting a timescale separation. Our results highlight that decomposition of a multi-timescale controller into a fast timescale, reactive controller and a slow timescale, predictive controller can be near-optimal in a strong sense. In particular, we exhibit such a design, named Multi-timescale Reflexive Predictive Control (MRPC), which maintains a per- timestep cost within a constant factor of the offline optimal in an adversarial setting.

  4. Y. Nakahira, N. Chen, L. Chen, S. H. Low, "Smoothed Least-laxity-first Algorithm for EV Charging," ACM e-Energy 2017. [show/hide abstract]
    We formulate EV charging as a feasibility problem that meets all EVs’ energy demands before departure under charging rate con- straints and total power constraint. We propose an online algorithm, the smoothed least-laxity- rst (sLLF) algorithm, that decides on the current charging rates based on only the information up to the current time. We characterize the performance of the sLLF algorithm analytically and numerically. Numerical experiments with real-world data show that it has signi cantly higher rate of generating feasible EV charging than several other common EV charging algorithms.

  5. N. Chen, J. Comden, Z. Liu, A. Gandhi, A. Wierman, "Using predictions in online optimization: looking forward with an eye on the past," ACM Sigmetrics 2016. [show/hide abstract]
    We consider online convex optimization (OCO) problems with switching costs and noisy predictions. While the design of online algorithms for OCO problems has received considerable attention, the design of algorithms in the context of noisy predictions is largely open. To this point, two promising algorithms have been proposed: Receding Horizon Control (RHC) and Averaging Fixed Horizon Control (AFHC). The comparison of these policies is largely open. AFHC has been shown to provide better worst-case performance, while RHC outperforms AFHC in many realistic settings. In this paper, we introduce a new class of policies, Committed Horizon Control (CHC), that generalizes both RHC and AFHC. We provide average-case analysis and concentration results for CHC policies, yielding the first analysis of RHC for OCO problems with noisy predictions. Further, we provide explicit results characterizing the optimal CHC policy as a function of properties of the prediction noise, e.g., variance and correlation structure. Our results provide a characterization of when AFHC outperforms RHC and vice versa, as well as when other CHC policies outperform both RHC and AFHC.

  6. N. Ruhi, N. Chen, K. Dvijotham, A. Wierman "Opportunities for Price Manipulations for Aggregators in Electricity Markets," ACM Greenmetrics 2016. Best student paper [show/hide abstract]
    Aggregators are playing an increasingly crucial role for integrating renewable generation into power systems. However, the intermittent nature of renewable generation makes market interactions of aggregators difficult to monitor and regulate, raising concerns about potential market manipulations. In this paper, we address this issue by quantifying the profit an aggregator can obtain through strategic curtailment of generation in an electricity market. We show that, while the problem of maximizing the benefit from curtailment is hard in general, efficient algorithms exist when the topology of the network is radial (acyclic). Further, we highlight that significant increases in profit can be obtained through strategic curtailment in practical settings.
    • Journal version has been accepted for publication in IEEE Trans. on Smart Grid.

  7. N. Chen, X. Ren, S. Ren, A. Wierman, "Greening multi-tenant data center demand response, " IFIP WG7.3 Performance 2015. [show/hide abstract]
    Data centers have emerged as promising resources for demand response, particularly for emergency demand response (EDR), which saves the power grid from incurring blackouts during emergency situations. However, currently, data centers typically participate in EDR by turning on backup (diesel) generators, which is both expensive and environmentally unfriendly. In this paper, we focus on ‘‘greening’’ demand response in multi-tenant data centers, i.e., colocation data centers, by designing a pricing mechanism through which the data center operator can efficiently extract load reductions from tenants during emergency periods for EDR. In particular, we propose a pricing mechanism for both mandatory and voluntary EDR programs, ColoEDR, that is based on parameterized supply function bidding and provides provably near-optimal efficiency guarantees, both when tenants are pricetaking and when they are price-anticipating. In addition to analytic results, we extend the literature on supply function mechanism design, and evaluate ColoEDR using trace-based simulation studies. These validate the efficiency analysis and conclude that the pricing mechanism is both beneficial to the environment and to the data center operator (by decreasing the need for backup diesel generation), while also aiding tenants (by providing payments for load reductions).

    • Extended abstract appears at the Workshop on MAthematical performance Modeling and Analysis (MAMA), 2015.

  8. N. Chen, A. Agarwal, A. Wierman, S. Barman, L. L. H. Andrew, "Online Convex Optimization Using Predictions," ACM SIGMETRICS 2015. [show/hide abstract]
    Making use of predictions is a crucial, but under-explored, area of online algorithms. This paper studies a class of online optimization problems where we have external noisy predictions available. We propose a stochastic prediction error model that generalizes prior models in the learning and stochastic control communities, incorporates correlation among prediction errors, and captures the fact that predictions improve as time passes. We prove that achieving sublinear regret and constant competitive ratio for online algorithms requires the use of an unbounded prediction window in adversarial settings, but that under more realistic stochastic prediction error models it is possible to use Averaging Fixed Horizon Control (AFHC) to simultaneously achieve sublinear regret and constant competitive ratio in expectation using only a constant-sized prediction window. Furthermore, we show that the performance of AFHC is tightly concentrated around its mean.

  9. N. Chen, L. Gan, S. H. Low, A. Wierman "Distributional Analysis for Model Predictive Deferrable Load Control," IEEE Conference on Decision and Control (CDC) 2014. [show/hide abstract]
    Deferrable load control is essential for handling the uncertainties associated with the increasing penetration of renewable generation. Model predictive control has emerged as an effective approach for deferrable load control, and has received considerable attention. Though the average-case performance of model predictive deferrable load control has been analyzed in prior works, the distribution of the performance has been elusive. In this paper, we prove strong concentration results on the load variation obtained by model predictive deferrable load control. These results highlight that the typical performance of model predictive deferrable load control is tightly concentrated around the average-case performance.

  10. N. Chen, T. Q. S. Quek, C. W. Tan, "Electric Vehicle Charging in Smart Grid: Optimality and Valley-Filling Algorithms," IEEE Trans. on Selected Topics in Signal Processing 2014. [show/hide abstract]
    Electric vehicles (EVs) offer an attractive long-term solution to reduce the dependence on fossil fuel and greenhouse gas emission. At the same time, charging a large fleet of EVs distributed across the residential area poses a challenge for the distribution network. In this paper, we formulate this problem by building on the optimal power flow (OPF) framework to model the network constraints that arises from charging EVs at different locations. To overcome the computational challenge when the control horizon is long, we study a nested optimization approach to decompose the joint OPF and EV charging problem. We characterize the optimal EV charging schedule to be a valley- filling profile, which allows us to develop an efficient offline algorithm with significantly lower computational complexity compared to centralized interior point solvers. Furthermore, we propose a decentralized online algorithm that dynamically tracks the valley-filling profile. Our algorithms are evaluated on the IEEE 14 bus system with real residential load profiles, and the simulations show that our online algorithm performs almost optimally under different settings.

  11. Z. Liu, A. Wierman, Y. Chen, B. Razon, N. Chen, "Data Center Demand Response: Avoiding the Coincident Peak via Workload Shifting and Local Generation," IFIP Performance 2013. [show/hide abstract]
    Demand response is a crucial aspect of the future smart grid. It has the potential to provide significant peak demand reduction and to ease the incorporation of renewable energy into the grid. Data centers’ participation in demand response is becoming increasingly important given their high and increasing energy consumption and their flexibility in demand management compared to conventional industrial facilities. In this paper, we study two demand response schemes to reduce a data center’s peak loads and energy expenditure: workload shifting and the use of local power generation. We conduct a detailed characterization study of coincident peak data over two decades from Fort Collins Utilities, Colorado and then develop two algorithms for data centers by combining workload scheduling and local power generation to avoid the coincident peak and reduce the energy expenditure. The first algorithm optimizes the expected cost and the second one provides a good worst-case guarantee for any coincident peak pattern, workload demand and renewable generation prediction error distributions. We evaluate these algorithms via numerical simulations based on real world traces from production systems. The results show that using workload shifting in combination with local generation can provide significant cost savings (up to 40% under the Fort Collins Utilities charging scheme) compared to either alone.

  12. L. Gan, A. Wierman, U. Topcu, N. Chen, S. Low "Real-Time Deferrable Load Control: Handling Uncertainties of Renewable Generation," ACM e-Energy 2013. [show/hide abstract]
    Real-time demand response is an essential tool for handling the uncertainties associated with the increasing penetration of renewable generation. Traditionally, demand response has been focused on large industrial and commercial loads, however it is expected that a large number of small residential loads such as air conditioners, dish washers, and electric vehicles will also participate in the coming years. The electricity consumption of these smaller loads, which we call deferrable loads, can be shifted over time, and can thus be used (in aggregate) to compensate for the random fluctuations in renewable generation. In this paper, we propose a real-time distributed deferrable load control algorithm to reduce the variance of aggregate load (load minus renewable generation) by shifting the power consumption of deferrable loads to periods with high renewable generation. At every time step, the algorithm minimizes the expected aggregate load variance with updated predictions. We prove that the suboptimality of the algorithm vanishes quickly as time horizon expands. Further, we evaluate the algorithm via trace-based simulations.

  13. N. Chen, T. Q. S. Quek, C. W. Tan "Optimal Charging of Electric Vehicles in Smart Grid: Characterization and Valley-Filling Algorithms," IEEE SmartGridComm 2012. [show/hide abstract]
    Electric vehicles (EVs) offer an attractive long-term solution to reduce the dependence on fossil fuel and greenhouse gas emission. However, a fleet of EVs with different EV battery charging rate constraints, that is distributed across a smart power grid network requires a coordinated charging schedule to minimize the power generation and EV charging costs. In this paper, we study a joint optimal power flow (OPF) and EV charging problem that augments the OPF problem with charging EVs over time. While the OPF problem is generally nonconvex and nonsmooth, it is shown recently that the OPF problem can be solved optimally for most practical power grid networks using its convex dual problem. Building on this strong duality result, we study a nested optimization approach to decompose the joint OPF and EV charging problem. We characterize the optimal offline EV charging schedule to be a valley-filling profile, which allows us to develop an optimal offline algorithm with computational complexity that is significantly lower than centralized interior point solvers. Furthermore, we propose a decentralized online algorithm that dynamically tracks the valley-filling profile. Our algorithms are evaluated on the IEEE 14 bus system, and the simulations show that the online algorithm performs almost near optimality (< 1% relative difference from the offline optimal solution) under different settings.


Thesis

  1. Online Algorithms: From Predictions to Decisions. Ph.D Thesis. California Institute of Technology, 2017

  2. Model Predictive Control for Deferrable Loads Scheduling. Master Thesis. California Institute of Technology, 2014

Presentations

  1. "Using Predictions in Online Optimziation: Looking Forward with an Eye on the Past"[pptx] [pdf] at ACM Sigmetrics, 2016

  2. "Online Convex Optimization Using Predictions"[pptx] [pdf] at ACM Sigmetrics, 2015

  3. "Greening Multi-Tenant Data Center Demand Response"[pptx] [pdf] at IFIP Performance, 2015

  4. "Greening Multi-Tenant Data Center Demand Response with Supply Function Bidding"[pptx] [pdf] at INFORMS 2015