- N. Chen, C. Kurniawan, Y. Nakahira, L. Chen, S.H. Low, “A learning and control perspective for microfinance”, arXiv preprint
arXiv:2207.12631
[show/hide abstract]
Microfinance, despite its significant potential for poverty reduction, is facing sustainability hardships due to high default rates. Although many methods in regular finance
can estimate credit scores and default probabilities, these methods are not directly applicable to microfinance due to the following unique characteristics: a) under-explored (developing) areas
such as rural Africa do not have sufficient prior loan data for microfinance institutions (MFIs) to establish a credit scoring system; b) microfinance applicants may have difficulty providing
sufficient information for MFIs to accurately predict default probabilities; and c) many MFIs use group liability (instead of collateral) to secure repayment. Here, we present a novel
control-theoretic model of microfinance that accounts for these characteristics. We construct an algorithm to learn microfinance decision policies that achieve financial inclusion, fairness,
social welfare, and sustainability. We characterize the convergence conditions to Pareto-optimum and the convergence speeds. We demonstrate, in numerous real and synthetic datasets, that the
proposed method accounts for the complexities induced by group liability to produce robust decisions before sufficient loans are given to establish credit scoring systems and for applicants whose
default probability cannot be accurately estimated due to missing information. To the best of our knowledge, this paper is the first to connect microfinance and control theory. We envision that
the connection will enable safe learning and control techniques to help modernize microfinance and alleviate poverty.
- N. Chen, C. Kurniawan, Y. Nakahira, L. Chen, S.H. Low, “Smoothed Least-Laxity-First Algorithm for EV Charging”, IEEE Transactions on Smart
Grid 13 (3), 2209-2217, 2022
[show/hide abstract]
Adaptive charging can charge electric vehicles (EVs) at scale cost effectively, despite of the uncertainty in EV arrivals. We formulate adaptive EV charging as a
feasibility problem that meets all EVs’ energy demands before their deadlines while satisfying constraints in charging rate and total charging power. We propose an online algorithm, smoothed
least-laxity- first (sLLF), that decides the current charging rates without the knowledge of future arrivals and demands. We characterize the performance of the sLLF algorithm analytically and
numerically. Numerical experiments with real-world data show that it has a significantly higher rate of feasible EV charging than several other existing EV charging algorithms. Resource
augmentation framework is employed to assess the feasibility condition of the algorithm. The assessment shows that the sLLF algorithm achieves perfect feasibility with only a 7% increase in the
maximal power supply of the charging station.
- Y. Liu, N. Chen, Z. Liu, Y. Yang “Online Cloud Resource Provisioning Under Cost Budget for QoS Maximization”, IEEE/ACM International Symposium on
Quality of Service, 2021
[show/hide abstract]
Cloud computing is becoming one of the ubiquitous
computing paradigms for enterprises and organizations in recent
years. Due to the volatility of system states such as cloud resource
price and workload demand, it is challenging to provision cloud
resources efficiently. This paper studies online cloud resource
provisioning problems under cost budget where no accurate or
distributional future information is available. We develop an
algorithmic framework and design online algorithms based on
the framework. We prove the competitive ratio of the proposed
algorithms. We further show the proposed algorithms have better
performance than a prominent existing algorithm named CRPursuit.
While prior works on the problem require the objective
functions to be concave, the proposed algorithms work for nonconvex
and non-concave objective functions. We conduct realworld
trace-driven simulations. Results highlight the proposed
algorithms outperform baselines significantly over a wide range
of settings.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.