Show simple item record

dc.contributor.authorJun, Kwang-Sungen_US
dc.contributor.authorOrabona, Francescoen_US
dc.date.accessioned2020-05-15T14:34:42Z
dc.date.available2020-05-15T14:34:42Z
dc.date.issued2019-12-05
dc.identifier.citationKwang-Sung Jun, Francesco Orabona. 2019. "Parameter-free Online Convex Optimization with Sub-Exponential Noise." Annual Conference on Learning Theory
dc.identifier.urihttps://hdl.handle.net/2144/40898
dc.description.abstractWe consider the problem of unconstrained online convex optimization (OCO) with sub-exponential noise, a strictly more general problem than the standard OCO. In this setting, the learner receives a subgradient of the loss functions corrupted by sub-exponential noise and strives to achieve optimal regret guarantee, without knowledge of the competitor norm, i.e., in a parameter-free way. Recently, Cutkosky and Boahen (COLT 2017) proved that, given unbounded subgradients, it is impossible to guarantee a sublinear regret due to an exponential penalty. This paper shows that it is possible to go around the lower bound by allowing the observed subgradients to be unbounded via stochastic noise. However, the presence of unbounded noise in unconstrained OCO is challenging; existing algorithms do not provide near-optimal regret bounds or fail to have a guarantee. So, we design a novel parameter-free OCO algorithm for Banach space, which we call BANCO, via a reduction to betting on noisy coins. We show that BANCO achieves the optimal regret rate in our problem. Finally, we show the application of our results to obtain a parameter-free locally private stochastic subgradient descent algorithm, and the connection to the law of iterated logarithms.en_US
dc.description.urihttp://proceedings.mlr.press/v99/jun19a/jun19a.pdf
dc.language.isoen_US
dc.rights© 2019 K.-S. Jun & F. Orabona.en_US
dc.subjectParameter-freeen_US
dc.subjectOnline convex optimizationen_US
dc.subjectUnconstraineden_US
dc.subjectDifferentially-private stochastic subgradient descenten_US
dc.titleParameter-free online convex optimization with sub-exponential noiseen_US
dc.typeConference materialsen_US
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Engineeringen_US
pubs.organisational-groupBoston University, College of Engineering, Department of Electrical & Computer Engineeringen_US
pubs.publication-statusPublisheden_US
dc.description.oaversionPublished version
dc.identifier.mycv546354


This item appears in the following Collection(s)

Show simple item record