Timezone: »
Poster
Online Optimization with Memory and Competitive Control
Guanya Shi · Yiheng Lin · Soon-Jo Chung · Yisong Yue · Adam Wierman
This paper presents competitive algorithms for a novel class of online optimization problems with memory. We consider a setting where the learner seeks to minimize the sum of a hitting cost and a switching cost that depends on the previous $p$ decisions. This setting generalizes Smoothed Online Convex Optimization. The proposed approach, Optimistic Regularized Online Balanced Descent, achieves a constant, dimension-free competitive ratio. Further, we show a connection between online optimization with memory and online control with adversarial disturbances. This connection, in turn, leads to a new constant-competitive policy for a rich class of online control problems.
Author Information
Guanya Shi (Caltech)
PhD student in machine learning and robotics
Yiheng Lin (California Institute of Technology)
Soon-Jo Chung (Caltech)
Yisong Yue (Caltech)
Adam Wierman (California Institute of Technology)
More from the Same Authors
-
2021 : The Multi-Agent Behavior Dataset: Mouse Dyadic Social Interactions »
Jennifer J Sun · Tomomi Karigo · Dipam Chakraborty · Sharada Mohanty · Benjamin Wild · Quan Sun · Chen Chen · David Anderson · Pietro Perona · Yisong Yue · Ann Kennedy -
2021 : Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning »
Cameron Voloshin · Hoang Le · Nan Jiang · Yisong Yue -
2021 Spotlight: Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems »
Yiheng Lin · Yang Hu · Guanya Shi · Haoyuan Sun · Guannan Qu · Adam Wierman -
2022 : Neurosymbolic Programming for Science »
Jennifer J Sun · Megan Tjandrasuwita · Atharva Sehgal · Armando Solar-Lezama · Swarat Chaudhuri · Yisong Yue · Omar Costilla Reyes -
2022 : Robustifying machine-learned algorithms for efficient grid operation »
Nicolas Christianson · Christopher Yeh · Tongxin Li · Mahdi Torabi Rad · Azarang Golmohammadi · Adam Wierman -
2022 : Stability Constrained Reinforcement Learning for Real-Time Voltage Control »
Jie Feng · Yuanyuan Shi · Guannan Qu · Steven Low · Anima Anandkumar · Adam Wierman -
2022 : SustainGym: A Benchmark Suite of Reinforcement Learning for Sustainability Applications »
Christopher Yeh · Victor Li · Rajeev Datta · Yisong Yue · Adam Wierman -
2023 Poster: Robust Learning for Smoothed Online Convex Optimization with Feedback Delay »
Pengfei Li · Jianyi Yang · Adam Wierman · Shaolei Ren -
2023 Poster: A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games »
Zaiwei Chen · Kaiqing Zhang · Eric Mazumdar · Asuman Ozdaglar · Adam Wierman -
2023 Poster: Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations »
Yiheng Lin · James Preiss · Emile Anand · Yingying Li · Yisong Yue · Adam Wierman -
2023 Poster: Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions »
Tongxin Li · Yiheng Lin · Shaolei Ren · Adam Wierman -
2023 Poster: Adversarial Attacks on Online Learning to Rank with Click Feedback »
Jinhang Zuo · Zhiyao Zhang · Zhiyong Wang · Shuai Li · Mohammad Hajiesmaili · Adam Wierman -
2023 Poster: Anytime-Constrained Reinforcement Learning with Policy Prior »
Jianyi Yang · Pengfei Li · Tongxin Li · Adam Wierman · Shaolei Ren -
2023 Poster: SustainGym: Reinforcement Learning Environments for Sustainable Energy Systems »
Christopher Yeh · Victor Li · Rajeev Datta · Julio Arroyo · Nicolas Christianson · Chi Zhang · Yize Chen · Mohammad Mehdi Hosseini · Azarang Golmohammadi · Yuanyuan Shi · Yisong Yue · Adam Wierman -
2022 : Panel »
Jeevana Priya Inala · Pushmeet Kohli · Ann Kennedy · Sriram Rajamani · Yisong Yue -
2022 : Deep Neural Imputation: A Framework for Recovering Incomplete Brain Recordings »
Sabera Talukder · Jennifer J Sun · Matthew Leonard · Bingni Brunton · Yisong Yue -
2022 Poster: On the Sample Complexity of Stabilizing LTI Systems on a Single Trajectory »
Yang Hu · Adam Wierman · Guannan Qu -
2022 Poster: Policy Optimization with Linear Temporal Logic Constraints »
Cameron Voloshin · Hoang Le · Swarat Chaudhuri · Yisong Yue -
2022 Poster: Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity »
Yiheng Lin · Yang Hu · Guannan Qu · Tongxin Li · Adam Wierman -
2021 : Panel B: Safe Learning and Decision Making in Uncertain and Unstructured Environments »
Yisong Yue · J. Zico Kolter · Ivan Dario D Jimenez Rodriguez · Dragos Margineantu · Animesh Garg · Melissa Greeff -
2021 : Learning for Agile Control in the Real World: Challenges and Opportunities »
Yisong Yue · Ivan Dario D Jimenez Rodriguez -
2021 Poster: Meta-Adaptive Nonlinear Control: Theory and Algorithms »
Guanya Shi · Kamyar Azizzadenesheli · Michael O'Connell · Soon-Jo Chung · Yisong Yue -
2021 Poster: Multi-Agent Reinforcement Learning in Stochastic Networked Systems »
Yiheng Lin · Guannan Qu · Longbo Huang · Adam Wierman -
2021 Poster: DeepGEM: Generalized Expectation-Maximization for Blind Inversion »
Angela Gao · Jorge Castellanos · Yisong Yue · Zachary Ross · Katherine Bouman -
2021 Poster: Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems »
Bo Sun · Russell Lee · Mohammad Hajiesmaili · Adam Wierman · Danny Tsang -
2021 Poster: Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems »
Yiheng Lin · Yang Hu · Guanya Shi · Haoyuan Sun · Guannan Qu · Adam Wierman -
2021 Poster: Iterative Amortized Policy Optimization »
Joseph Marino · Alexandre Piche · Alessandro Davide Ialongo · Yisong Yue -
2020 Workshop: Learning Meets Combinatorial Algorithms »
Marin Vlastelica · Jialin Song · Aaron Ferber · Brandon Amos · Georg Martius · Bistra Dilkina · Yisong Yue -
2020 Poster: A General Large Neighborhood Search Framework for Solving Integer Linear Programs »
Jialin Song · ravi lanka · Yisong Yue · Bistra Dilkina -
2020 Poster: Learning compositional functions via multiplicative weight updates »
Jeremy Bernstein · Jiawei Zhao · Markus Meister · Ming-Yu Liu · Anima Anandkumar · Yisong Yue -
2020 Poster: Learning Differentiable Programs with Admissible Neural Heuristics »
Ameesh Shah · Eric Zhan · Jennifer J Sun · Abhinav Verma · Yisong Yue · Swarat Chaudhuri -
2020 Poster: Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward »
Guannan Qu · Yiheng Lin · Adam Wierman · Na Li -
2020 Poster: On the distance between two neural networks and the stability of learning »
Jeremy Bernstein · Arash Vahdat · Yisong Yue · Ming-Yu Liu -
2020 Poster: The Power of Predictions in Online Control »
Chenkai Yu · Guanya Shi · Soon-Jo Chung · Yisong Yue · Adam Wierman -
2019 : Poster Session »
Ahana Ghosh · Javad Shafiee · Akhilan Boopathy · Alex Tamkin · Theodoros Vasiloudis · Vedant Nanda · Ali Baheri · Paul Fieguth · Andrew Bennett · Guanya Shi · Hao Liu · Arushi Jain · Jacob Tyo · Benjie Wang · Boxiao Chen · Carroll Wainwright · Chandramouli Shama Sastry · Chao Tang · Daniel S. Brown · David Inouye · David Venuto · Dhruv Ramani · Dimitrios Diochnos · Divyam Madaan · Dmitrii Krashenikov · Joel Oren · Doyup Lee · Eleanor Quint · elmira amirloo · Matteo Pirotta · Gavin Hartnett · Geoffroy Dubourg-Felonneau · Gokul Swamy · Pin-Yu Chen · Ilija Bogunovic · Jason Carter · Javier Garcia-Barcos · Jeet Mohapatra · Jesse Zhang · Jian Qian · John Martin · Oliver Richter · Federico Zaiter · Tsui-Wei Weng · Karthik Abinav Sankararaman · Kyriakos Polymenakos · Lan Hoang · mahdieh abbasi · Marco Gallieri · Mathieu Seurin · Matteo Papini · Matteo Turchetta · Matthew Sotoudeh · Mehrdad Hosseinzadeh · Nathan Fulton · Masatoshi Uehara · Niranjani Prasad · Oana-Maria Camburu · Patrik Kolaric · Philipp Renz · Prateek Jaiswal · Reazul Hasan Russel · Riashat Islam · Rishabh Agarwal · Alexander Aldrick · Sachin Vernekar · Sahin Lale · Sai Kiran Narayanaswami · Samuel Daulton · Sanjam Garg · Sebastian East · Shun Zhang · Soheil Dsidbari · Justin Goodwin · Victoria Krakovna · Wenhao Luo · Wesley Chung · Yuanyuan Shi · Yuh-Shyang Wang · Hongwei Jin · Ziping Xu -
2019 Workshop: Safety and Robustness in Decision-making »
Mohammad Ghavamzadeh · Shie Mannor · Yisong Yue · Marek Petrik · Yinlam Chow -
2019 Poster: Imitation-Projected Programmatic Reinforcement Learning »
Abhinav Verma · Hoang Le · Yisong Yue · Swarat Chaudhuri -
2019 Poster: NAOMI: Non-Autoregressive Multiresolution Sequence Imputation »
Yukai Liu · Rose Yu · Stephan Zheng · Eric Zhan · Yisong Yue -
2019 Poster: Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization »
Gautam Goel · Yiheng Lin · Haoyuan Sun · Adam Wierman -
2019 Spotlight: Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization »
Gautam Goel · Yiheng Lin · Haoyuan Sun · Adam Wierman -
2019 Poster: Teaching Multiple Concepts to a Forgetful Learner »
Anette Hunziker · Yuxin Chen · Oisin Mac Aodha · Manuel Gomez Rodriguez · Andreas Krause · Pietro Perona · Yisong Yue · Adish Singla -
2019 Poster: Landmark Ordinal Embedding »
Nikhil Ghosh · Yuxin Chen · Yisong Yue -
2018 : Yisong Yue »
Yisong Yue -
2018 : Coffee Break 1 (Posters) »
Ananya Kumar · Siyu Huang · Huazhe Xu · Michael Janner · Parth Chadha · Nils Thuerey · Peter Lu · Maria Bauza · Anthony Tompkins · Guanya Shi · Thomas Baumeister · André Ofner · Zhi-Qi Cheng · Yuping Luo · Deepika Bablani · Jeroen Vanbaar · Kartic Subr · Tatiana López-Guevara · Devesh Jha · Fabian Fuchs · Stefano Rosa · Alison Pouplin · Alex Ray · Qi Liu · Eric Crawford -
2018 Poster: Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners »
Yuxin Chen · Adish Singla · Oisin Mac Aodha · Pietro Perona · Yisong Yue -
2018 Poster: A General Method for Amortizing Variational Filtering »
Joseph Marino · Milan Cvitkovic · Yisong Yue -
2017 : Coffee break and Poster Session II »
Mohamed Kane · Albert Haque · Vagelis Papalexakis · John Guibas · Peter Li · Carlos Arias · Eric Nalisnick · Padhraic Smyth · Frank Rudzicz · Xia Zhu · Theodore Willke · Noemie Elhadad · Hans Raffauf · Harini Suresh · Paroma Varma · Yisong Yue · Ognjen (Oggi) Rudovic · Luca Foschini · Syed Rameel Ahmad · Hasham ul Haq · Valerio Maggio · Giuseppe Jurman · Sonali Parbhoo · Pouya Bashivan · Jyoti Islam · Mirco Musolesi · Chris Wu · Alexander Ratner · Jared Dunnmon · Cristóbal Esteban · Aram Galstyan · Greg Ver Steeg · Hrant Khachatrian · Marc Górriz · Mihaela van der Schaar · Anton Nemchenko · Manasi Patwardhan · Tanay Tandon -
2016 Poster: Generating Long-term Trajectories Using Deep Hierarchical Networks »
Stephan Zheng · Yisong Yue · Patrick Lucey -
2015 Poster: Smooth Interactive Submodular Set Cover »
Bryan He · Yisong Yue -
2015 Demonstration: Data-Driven Speech Animation »
Yisong Yue · Iain Matthews