# American Institute of Mathematical Sciences

April  2017, 4(2): 125-148. doi: 10.3934/jdg.2017008

## A continuous-time approach to online optimization

 1 Centre de mathématiques appliquées, École polytechnique, Université Paris-Saclay, Palaiseau, France 2 CNRS (French National Center for Scientific Research), Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, F-38000, Grenoble, France

Received  January 2017 Revised  February 2017 Published  March 2017

We consider a family of mirror descent strategies for online optimization in continuous-time and we show that they lead to no regret. From a more traditional, discrete-time viewpoint, this continuous-time approach allows us to derive the no-regret properties of a large class of discrete-time algorithms including as special cases the exponential weights algorithm, online mirror descent, smooth fictitious play and vanishingly smooth fictitious play. In so doing, we obtain a unified view of many classical regret bounds, and we show that they can be decomposed into a term stemming from continuous-time considerations and a term which measures the disparity between discrete and continuous time. This generalizes the continuous-time based analysis of the exponential weights algorithm from [29]. As a result, we obtain a general class of infinite horizon learning strategies that guarantee an $\mathcal{O}(n^{-1/2})$ regret bound without having to resort to a doubling trick.

Citation: Joon Kwon, Panayotis Mertikopoulos. A continuous-time approach to online optimization. Journal of Dynamics & Games, 2017, 4 (2) : 125-148. doi: 10.3934/jdg.2017008
##### References:

show all references

##### References:
Graphical illustration of the greedy (dashed) and lazy (solid) branches of the projected subgradient (PSG) method
Greedy and Lazy Mirror Descent with γn = 1
Summary of the algorithms discussed in Section 6.The suffix "L" indicates a "lazy" variant; the INPUT column stands for the stream of payoff vectors which is used as input for the algorithm and the NORM column specifies the norm of the ambient space; finally, $\xi_{n}$ represents a zero-mean stochastic process with values in $\mathbb{R}^{d}$
 ALGORITHM $\mathcal{C}$ $h(x)$ $\eta _{n}$ INPUT NORM EW $\Delta_d$ $\sum_{i} x_{i}\log x_{i}$ CONSTANT $v_{n}$ $\ell^{1}$ EW' $\Delta_{d}$ $\sum_{i} x_{i}\log x_{i}$ $\eta /\sqrt{n}$ $v_{n}$ $\ell^{1}$ SFP $\Delta_d$ ANY $\eta /n$ $v_{n}$ $\ell^{1}$ VSFP $\Delta_d$ ANY $\eta n^{-\alpha} \;\;(0<\alpha<1)$ $v_{n}$ $\ell^{1}$ OGD-L ANY $\frac{1}{2} \left\| x \right\|_2^2$ CONSTANT $-\nabla f_{n}(x_{n})$ $\ell^{2}$ OMD-L ANY ANY CONSTANT $-\nabla f_{n}(x_{n})$ ANY PSG-L ANY $\frac{1}{2} \left\| x \right\|_2^2$ $1$ $-\gamma_{n}\nabla f(x_{n})$ $\ell^{2}$ MD-L ANY ANY $1$ $-\gamma_{n} \nabla f(x_{n})$ ANY RSA-L ANY ANY $1$ $-\gamma_{n} (\nabla f(x_{n})+\xi_n)$ ANY SPSG-L ANY $\frac{1}{2} \left\| x \right\|_2^2$ $1$ $-\gamma_{n}(\nabla f(x_{n})+\xi_n)$ $\ell^{2}$
 ALGORITHM $\mathcal{C}$ $h(x)$ $\eta _{n}$ INPUT NORM EW $\Delta_d$ $\sum_{i} x_{i}\log x_{i}$ CONSTANT $v_{n}$ $\ell^{1}$ EW' $\Delta_{d}$ $\sum_{i} x_{i}\log x_{i}$ $\eta /\sqrt{n}$ $v_{n}$ $\ell^{1}$ SFP $\Delta_d$ ANY $\eta /n$ $v_{n}$ $\ell^{1}$ VSFP $\Delta_d$ ANY $\eta n^{-\alpha} \;\;(0<\alpha<1)$ $v_{n}$ $\ell^{1}$ OGD-L ANY $\frac{1}{2} \left\| x \right\|_2^2$ CONSTANT $-\nabla f_{n}(x_{n})$ $\ell^{2}$ OMD-L ANY ANY CONSTANT $-\nabla f_{n}(x_{n})$ ANY PSG-L ANY $\frac{1}{2} \left\| x \right\|_2^2$ $1$ $-\gamma_{n}\nabla f(x_{n})$ $\ell^{2}$ MD-L ANY ANY $1$ $-\gamma_{n} \nabla f(x_{n})$ ANY RSA-L ANY ANY $1$ $-\gamma_{n} (\nabla f(x_{n})+\xi_n)$ ANY SPSG-L ANY $\frac{1}{2} \left\| x \right\|_2^2$ $1$ $-\gamma_{n}(\nabla f(x_{n})+\xi_n)$ $\ell^{2}$
 [1] Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595 [2] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [3] Xiaming Chen. Kernel-based online gradient descent using distributed approach. Mathematical Foundations of Computing, 2019, 2 (1) : 1-9. doi: 10.3934/mfc.2019001 [4] King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021 [5] Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070 [6] M. S. Lee, B. S. Goh, H. G. Harno, K. H. Lim. On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 315-326. doi: 10.3934/naco.2018020 [7] Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial & Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739 [8] Ying Ji, Shaojian Qu, Yeming Dai. A new approach for worst-case regret portfolio optimization problem. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 761-770. doi: 10.3934/dcdss.2019050 [9] Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189 [10] Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038 [11] Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial & Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565 [12] Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075 [13] Ian D. Morris. Ergodic optimization for generic continuous functions. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 383-388. doi: 10.3934/dcds.2010.27.383 [14] Zhenhuan Yang, Yiming Ying, Qilong Min. Online optimization for residential PV-ESS energy system scheduling. Mathematical Foundations of Computing, 2019, 2 (1) : 55-71. doi: 10.3934/mfc.2019005 [15] Herbert Gajewski, Jens A. Griepentrog. A descent method for the free energy of multicomponent systems. Discrete & Continuous Dynamical Systems - A, 2006, 15 (2) : 505-528. doi: 10.3934/dcds.2006.15.505 [16] Joseph Hundley, Eitan Sayag. Descent construction for GSpin groups: Main results and applications. Electronic Research Announcements, 2009, 16: 30-36. doi: 10.3934/era.2009.16.30 [17] Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415 [18] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [19] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [20] Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

Impact Factor: