PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameter-Free Online Convex Optimization with Sub-Exponential Noise

Kwang-Sung Jun, Francesco Orabona

arXiv:1902.01500v3cs.LGmath.OCstat.ML

TL;DR

Unconstrained parameter-free OCO with sub-exponential noise must contend with a lower bound showing exponential penalties for unbounded subgradients, while existing approaches give suboptimal regret or no nontrivial guarantee. The paper proposes BANCO through noisy coin betting and reports an optimal minimax regret rate matching noise-free OCO in comparator norm and horizon.

  • Problem

    Unconstrained noisy OCO seeks regret scaling optimally with comparator norm and horizon, but unbounded subgradients can incur an exponential penalty and existing approaches are suboptimal or lack nontrivial guarantees.

    Source: §1 · p. 2

  • Method

    BANCO is a parameter-free algorithm for noisy OCO based on the noisy coin betting framework.

    Source: §1 · p. 2, §8 · p. 13

  • Results

    BANCO achieves the same optimal minimax regret rate as noise-free unconstrained OCO with respect to comparator norm and horizon.

    Source: §8 · p. 13

  • Takeaways & Limitations

    The results yield the first parameter-free locally private SGD algorithm and a Banach-valued concentration inequality matching the law of the iterated logarithm rate.

    Source: §1 · p. 3

    The lower-bound construction gives the learner knowledge of the best competitor’s norm, making its problem class easier than the setting where that norm is unknown.

    Source: §6 · p. 10

Abstract

from arXiv · show

We 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.

1 Introduction

The paper studies parameter-free unconstrained OCO with sub-exponential noise, where observed subgradients may be unbounded. It introduces BANCO through noisy coin betting and reports optimal regret dependence, with applications to private SGD and concentration.

1 Introduction

  • Unconstrained OCO with unbounded subgradients can incur an exponential penalty without prior information about the largest subgradient, motivating a stochastic-noise setting.The paper allows observed subgradients to be unbounded through stochasticity, which it says limits adversarial power without bounding the observations.Source: §1 · p. 2
  • Existing approaches to noisy OCO either yield suboptimal regret dependence on the comparator norm or no nontrivial guarantee.The paper identifies this gap as motivation for BANCO.Source: §1 · p. 2
  • BANCO achieves optimal expected regret dependence on the comparator norm and horizon in smooth Banach spaces, despite noisy, unbounded feedback.The paper states that its dependence on variance cannot be improved and its comparator-norm dependence matches up to logarithmic factors.Source: §1 · p. 2
  • BANCO reduces noisy OCO in Banach space to one-dimensional betting on noisy coin flips, using a constrained noisy OCO learner as a black box.The reduction extends the coin-betting framework to noisy observations.Source: §1 · p. 2
  • The results yield a parameter-free locally differentially private stochastic subgradient descent algorithm and a connection to the law of the iterated logarithm.The concentration connection proceeds through a noisy coin-betting potential that implies a supermartingale, followed by Doob’s inequality.Source: §1 · p. 3

2 Problem Definition and Preliminaries

This section formalizes expected-regret OCO with noisy subgradients and introduces coin betting as a route to parameter-free regret guarantees. Its noisy extension preserves a betting inequality in conditional expectation rather than requiring wealth to remain nonnegative on every outcome.

Online convex optimization with noise

  • The learner observes noisy negative subgradients and seeks to minimize expected regret because its iterates depend on past noisy observations.The true subgradients are bounded, while the noise is conditionally zero-mean with finite variance and a sub-exponential tail condition.Source: §2 · p. 3

OCO as betting on noisy coins

  • Coin betting views unconstrained OCO as maximizing wealth through repeated bets on coin outcomes, yielding parameter-free regret guarantees for any competitor.The framework does not require a bounded competitor set or a parameter to tune.Source: §2 · p. 4
  • A lower bound on final wealth is equivalent to an upper bound on linearized regret with respect to a comparator.This equivalence connects the coin-betting wealth process to OCO regret.Source: §2 · p. 4

Noisy coin betting

  • Noisy coin outcomes can make wealth negative, so existing strategies that guarantee nonnegative wealth with probability one do not apply.The paper instead guarantees nonnegativity for expected wealth by imposing the betting relationship in conditional expectation.Source: §2 · p. 4

3 The Devil is in the Details: Failing Approaches

The section tests direct extensions of existing OCO methods and finds that their guarantees do not yield the desired parameter-free regret for unconstrained OCO with unbounded noise. It also distinguishes linear losses, where standard OGD can avoid variance dependence, from generic convex losses.

3 The Devil is in the Details: Failing Approaches

  • The direct OGD analysis relies on a noisy-gradient regret bound that does not provide the desired comparator dependence in this unconstrained setting.The section notes that the analogous assumption would hold for constrained OCO with bounded noise, but not for this setting.Source: §3 · p. 5
  • The dependence on the unknown comparator u is ∥u∥², much larger than the best known rate ∥u∥ log(1 + ∥u∥) (McMahan and Orabona, 2014).Source: §3 · p. 5
  • A high-probability bound on noisy subgradients does not make the resulting parameter-free guarantee an upper bound on actual regret, even on that event.The attempted approach applies standard parameter-free OCO under an event bounding all observed subgradients.Source: §3 · p. 5
  • A direct regret decomposition for high-probability analysis leaves a term involving unbounded iterates, so the authors leave such bounds for future work.The behavior of the iterates in that term is described as nontrivial to analyze.Source: §3 · p. 5
  • For generic convex losses, the lower bound shows that the variance factor σ in expected regret cannot generally be avoided.For linear losses, standard OGD can have expected regret that does not scale with σ.Source: §3 · p. 6

4 One-dimensional Betting Algorithm with Noisy Coins

The one-dimensional algorithm extends coin betting to noisy feedback by controlling expected wealth with a noise-aware potential. A sub-exponential inequality supports the construction, and an expected reward–regret relation converts its wealth guarantee into regret.

4 One-dimensional Betting Algorithm with Noisy Coins

  • The noisy coin-betting potential blends sub-exponential noise into a family of potentials parameterized by a prior, enabling analysis of noisy feedback.The paper identifies this noise-aware blending as its key novelty relative to prior expert-advice potentials.Source: §4 · p. 6
  • The construction uses a sub-exponential moment inequality for noisy gradients with mean bounded by G, restricting β to |β| ≤ min(k1/G, 1/b).The stated constant is k1 = 0.683803....Source: §4 · p. 6
  • BANCO is formed from a prior-supported mixture of potential and prediction functions, with the algorithm requiring (σ²,b), G, and initial money τ.The construction specifies a ≤ min(k1/G, 1/b) and a prior supported on [−a,a].Source: §4 · pp. 6–7
  • A lower bound on expected wealth yields an upper bound on expected linearized regret, extending the standard coin-betting reward–regret relationship.The paper notes that whether the converse direction holds for noisy coin betting remains unclear.Source: §4 · pp. 7–8
  • Applying the potential and reward–regret results gives BANCO an expected regret guarantee under the stated choices of S and a.The passages identify S = T(σ²/2 + G²) and a = min(k1/G,1/b), but do not provide a fully readable bound.Source: §4 · p. 8

5 Banach Online Convex Optimization with Noise

BANCO extends to Banach spaces through a black-box reduction that combines a one-dimensional coin-betting learner with a constrained direction learner. The expected regret separates into the learners’ contributions, and the construction applies with suitable learners in uniformly convex spaces.

5 Banach Online Convex Optimization with Noise

  • A black-box reduction extends BANCO to Banach spaces by combining scalar coin betting with a constrained noisy OCO learner.The reduction avoids an algorithm-specific higher-dimensional analysis.Source: §5 · p. 8
  • The reduction predicts xt = wtyt, sends ⟨ĝt,yt⟩ to coin betting, and sends ĝt to the direction learner.The scalar learner sets the magnitude, while the direction learner predicts within the unit ball.Source: §5 · pp. 8–9
  • The combined algorithm's expected regret decomposes into the expected regrets of coin betting and the direction learner.Requiring the direction learner's regret only against a unit-norm comparator removes the need to tune its parameter for the optimal step size.Source: §5 · p. 9
  • The reduction supports uniformly convex Banach spaces, including Hilbert spaces with the 2-norm and p-norm spaces for p ∈ (1,2].The runtime is dominated by the direction learner; BANCO's runtime does not scale with dimension.Source: §5 · p. 10

6 Lower bound

The lower-bound analysis shows that dependence on noise variance cannot generally be improved. Its comparator-norm dependence is weaker than the upper bound because the constructed problem lets the learner know the comparator norm.

6 Lower bound

  • Theorem 6 establishes that BANCO’s dependence on noise variance is unimprovable in general.The lower bound is proved using a stochastic optimization instance connected to online convex optimization through online-to-batch conversion.Source: §6 · p. 10
  • Theorem 6 considers σ ≥ 2, p ≥ 1, and 1/q = 1 − 1/p, with 1-Lipschitz losses in the p-norm and noise variance bounded by σ^2 in the q-norm.The excerpt states that a universal constant appears in the theorem’s lower bound but does not provide the bound itself.Source: §6 · p. 10
  • The lower-bound comparator dependence differs from the upper bound by a factor of log(1 + ||u||), because the construction gives the learner knowledge of the best comparator’s norm.The construction is therefore an easier optimization problem than the setting where the comparator norm is unknown.Source: §6 · p. 10
  • The analysis argues that noisy OCO regret must include an extra logarithmic factor in ||u||, invoking a lower bound of Ω(G||u||^2).The excerpt begins a contradiction argument based on an algorithm with strictly better regret order, but does not include its full conclusion.Source: §6 · pp. 10–11
  • Adding infinitesimal noise to noise-free observed gradients and applying a noisy-OCO algorithm would yield a regret bound contradicting the noise-free lower bound.This argument is used to motivate the asserted extra logarithmic comparator-norm factor in the noisy setting.Source: §6 · pp. 10–11

7 Applications

The applications section connects noisy OCO to locally private stochastic gradient descent and to concentration results related to the law of the iterated logarithm. It applies BANCO to private SGD without requiring the optimal-solution norm to tune step sizes, and derives concentration results from noisy coin betting.

7.1 Parameter-Free Locally Differentially Private SGD

  • The paper applies BANCO to locally differentially private SGD, where privacy noise is added to subgradients, and reports the first parameter-free locally private SGD algorithm.The Laplace sanitization mechanism is shown to satisfy the paper’s sub-exponential noise assumption.Source: §7.1 · p. 11
  • The private SGD convergence rate matches Wu et al. (2017) up to polylogarithmic terms without requiring knowledge of ||w*|| to tune step sizes.The stated corollary assumes convex losses with subgradients bounded in L2 norm by 1.Source: §7.1 · p. 12

7.2 Noisy Coin Betting Implies the Law of Iterated Logarithms in Banach Spaces

  • Noisy coin betting is linked to the law of the iterated logarithm for sub-Gaussian random variables in Banach spaces; the same reasoning is stated to hold for sub-exponential random variables.The exposition treats the sub-Gaussian case for simplicity.Source: §7.2 · p. 12
  • With zero true gradients, the potential yields a supermartingale, and Doob’s inequality is used to derive a concentration inequality.The derivation requires a prior on the betting fraction that gives the optimal bound; Lemma 8 specifies a prior for the one-dimensional sub-Gaussian case.Source: §7.2 · pp. 12–13
  • The noisy coin-betting reduction also implies a Banach-valued martingale concentration inequality for a Banach space that is (2,λ)-uniformly convex.The supplied passage does not include the inequality’s complete statement.Source: §7.2 · p. 13

8 Conclusion and Future Work

The conclusion presents BANCO as achieving the noise-free unconstrained OCO minimax regret rate in comparator norm and horizon, with optimal dependence on noise up to constants. It also identifies open questions about data dependence, unknown noise parameters, heavier-tailed noise, and high-probability guarantees.

8 Conclusion and Future Work

  • BANCO, built through noisy coin betting, achieves the same optimal minimax regret rate as noise-free unconstrained OCO with respect to comparator norm and horizon.The conclusion states that a lower bound on the noise level makes its regret bound optimal up to constant factors.Source: §8 · p. 13
  • The paper’s result yields the first parameter-free subgradient descent algorithm for differential privacy.The conclusion identifies differential privacy as an application of the results.Source: §8 · p. 13
  • The regret bound is not data-dependent, using (G^2 + σ^2)T rather than a data-dependent quantity.The authors identify whether data-dependent bounds are possible as an open question.Source: §8 · p. 13
  • The method requires knowledge of the noise through (σ^2,b); the authors note that noise is unknown in many noisy-channel applications.They also identify heavy-tailed noise and high-probability regret bounds as directions for future work.Source: §8 · p. 14

Appendices

For deterministic linear losses, the appendix shows that OGD’s expected regret need not depend on the noise level, although the general lower bound requires noise dependence.

A OGD with linear losses

  • For deterministic linear losses chosen before play, OGD has a tuned-step-size regret bound of O((||u||^2 + 1)T) that does not involve σ.The appendix contrasts this special case with its general lower bound, which shows that σ must appear in general.Source: A OGD with linear losses · p. 17

B Proof of Theorem 3

The proof of Theorem 3 uses a potential-function lower bound on expected wealth and Fenchel conjugacy. The proof of Theorem 4 optimizes over a betting parameter, with a separate boundary case when the optimizer exceeds the prior range.

B Proof of Theorem 3

  • Expected wealth is lower-bounded by the potential F, and Fenchel conjugacy completes the proof of Theorem 3.Source: B Proof of Theorem 3 · p. 17

C Proof of Theorem 4

  • For Theorem 4, the proof chooses the maximizing betting parameter β⋆ and uses a uniform prior over [−a,a] to bound the resulting integral.Source: C Proof of Theorem 4 · pp. 17–18
  • When β⋆>a, the proof takes the endpoint interval [a−c,a] and derives f⋆(u)=8/(3a)|u|ln(32|u|/(3eaτ)).Source: C Proof of Theorem 4 · p. 18

E Proof of Theorem 6

This proof reduces an online-learning lower bound to stochastic optimization, then constructs noisy-oracle problems whose observations reveal coin outcomes. It also specializes the geometric parameter to ℓp balls.

E Proof of Theorem 6

  • Online-to-batch conversion makes a stochastic-optimization convergence lower bound imply an online-learning lower bound.Source: E Proof of Theorem 6 · p. 19
  • The stochastic oracle returns noisy function values and subgradients with unbiased subgradients and variance bounded by σ², while the function class remains 1-Lipschitz.Source: E Proof of Theorem 6 · pp. 19–20
  • The hard function class encodes coefficients on separated hypercube vertices, and oracle calls reveal corresponding Bernoulli coin outcomes.Source: E Proof of Theorem 6 · p. 20
  • For q∈[1,2], the oracle reveals one coordinate's coin outcome per call; for q≥2, it reveals independent outcomes across all d coordinates.Source: E Proof of Theorem 6 · pp. 20–22
  • The proof uses an optimization method to estimate the encoded target vertex, then applies a Fano-based identification bound to constrain that estimation.Source: E Proof of Theorem 6 · p. 21
  • For an ℓp ball of radius U, the largest r with B∞(r) contained in the domain is Ud^(-1/p).Source: E Proof of Theorem 6 · p. 22

F Proof of Lemma 7

The proof of Lemma 7 derives a concentration bound for Laplace mechanism noise by expressing its exponential moment through a random direction and an Erlang variable. The proof of Lemma 8 reduces the scale to one and bounds the resulting integral in cases.

F Proof of Lemma 7

  • Laplace mechanism noise is represented as the product of a uniformly drawn vector on the L2 ball and an Erlang variable, which supports the exponential-moment bound.Source: F Proof of Lemma 7 · pp. 22–23
  • In dimensions d≥2, the direction cosine has a distribution whose exponential moment is evaluated using a modified Bessel function, yielding the same result as in one dimension.Source: F Proof of Lemma 7 · pp. 22–23

G Proof of Lemma 8

  • Lemma 8 reduces to σ1D=1 by replacing S with its accumulated scale, then bounds the integral using symmetry and separate cases for S relative to t.Source: G Proof of Lemma 8 · pp. 23–24
Loading 1902.01500v3…