Projected Stochastic Primal-Dual Method for Constrained Online Learning with Kernels

Kaiqing Zhang, Hao Zhu, Tamer Basar, Alec Koppel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of stochastic optimization with nonlinear constraints, where the decision variable is not vector-valued but instead a function belonging to a reproducing Kernel Hilbert Space (RKHS). Currently, there exist solutions to only special cases of this problem. To solve this constrained problem with kernels, we first generalize the Representer Theorem to a class of saddle-point problems defined over RKHS. Furthermore, we develop a primal-dual method which executes alternating projected primal/dual stochastic descent/ascent on the dual-augmented Lagrangian of this problem. The primal projection sets are low-dimensional subspaces of the ambient function space which are greedily constructed using matching pursuit. By tuning the projection-induced error to the algorithm step-size, we are able to establish mean convergence both in primal objective sub-optimality and constraint violation, respectively to the \mathcal{O}(\sqrt{T}) and \mathcal{O}(T^{3/4}) neighborhoods, where T is the total number of iterations. We evaluate the proposed method through numerical tests for the application of risk-aware supervised learning.

Original languageEnglish (US)
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4224-4231
Number of pages8
ISBN (Electronic)9781538613955
DOIs
StatePublished - Jan 18 2019
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: Dec 17 2018Dec 19 2018

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2018-December
ISSN (Print)0743-1546

Conference

Conference57th IEEE Conference on Decision and Control, CDC 2018
CountryUnited States
CityMiami
Period12/17/1812/19/18

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Projected Stochastic Primal-Dual Method for Constrained Online Learning with Kernels'. Together they form a unique fingerprint.

Cite this