PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning Without Prior Information

Ashok Cutkosky, Kwabena Boahen

arXiv:1703.02629v2cs.LGstat.ML

TL;DR

Online optimization without prior bounds can make parameter guessing laborious and theoretically unsound. The paper develops lower bounds and FTRL algorithms that match a regret trade-off frontier, including an alternative to the exponential penalty when gradient growth is bounded.

  • Problem

    When bounds on domain diameter or gradients are unavailable, guessing them is laborious and theoretically unsound.

    Source: §1 · p. 2

  • Method

    The paper uses FTRL and adaptive regularizers to construct algorithms matching the lower-bound frontier, including the information-free FREEREX algorithm.

    Source: §4 · p. 5, §6 · p. 10

  • Results

    The paper establishes a frontier of matching lower bounds and algorithms, and shows that a known bound on gradient-growth rate can avoid the exponential penalty.

    Source: §7 · p. 12

  • Takeaways & Limitations

    The algorithms require only the trade-off parameters k and γ, which users can choose without unknown constraints on those parameters.

    Source: §7 · p. 12

    Although the analysis allows arbitrary norms, the examples focus on L2, leaving adaptive regularizers for other or time-changing norms as future work.

    Source: §7 · p. 12

Abstract

from arXiv · show

The vast majority of optimization and online learning algorithms today require some prior information about the data (often in the form of bounds on gradients or on the optimal parameter value). When this information is not available, these algorithms require laborious manual tuning of various hyperparameters, motivating the search for algorithms that can adapt to the data with no prior information. We describe a frontier of new lower bounds on the performance of such algorithms, reflecting a tradeoff between a term that depends on the optimal parameter value and a term that depends on the gradients' rate of growth. Further, we construct a family of algorithms whose performance matches any desired point on this frontier, which no previous algorithm reaches.

1. Problem Definition and Prior Work

Without prior bounds, online optimization may incur an exponential penalty, while guessing parameters is theoretically unsound and laborious. The paper establishes a trade-off frontier and algorithms that match it across its parameter choices.

1. Problem Definition and Prior Work

  • Online convex optimization requires a bound on the domain diameter or gradients, or incurs an exponential penalty in the gradients’ growth rate.The no-prior-information setting is common in practice, where guessing these bounds is laborious and theoretically unsound.Source: §1 · pp. 1–2
  • The paper proves matching lower and upper bounds without prior information, with a frontier trading off regret terms involving the comparator and gradient growth.The frontier is parameterized by k and γ, with different trade-offs between the exponential penalty and other regret terms.Source: §1 · p. 2
  • The constructed algorithm family matches the lower-bound frontier for any chosen k and γ.Source: §1 · p. 2

2. Notation and Setup

The paper reduces convex losses to linear losses using subgradients and focuses its lower bounds and algorithms on an unconstrained Hilbert space. It defines the notation and assumptions used for that setting.

2. Notation and Setup

  • The setup defines convex sets and functions, subgradients, norms, and dual norms; for the L2 norm, the dual norm is also L2.Source: §2 · p. 2
  • Convex-loss regret is upper-bounded by regret on linear losses formed from subgradients at the algorithm’s chosen points.This reduction makes the algorithms first-order: they access losses only through subgradients.Source: §2 · p. 2
  • The analysis focuses on an entire Hilbert space with infinite diameter and aims for regret depending on ∥u∥, T, and Lmax without prior knowledge of them.Source: §2 · p. 2
  • The authors note that their lower bound improves on Cutkosky and Boahen (2016) by removing a square root from the exponential term.Source: §2 · p. 2
  • Indexed sums with colons denote summation over the indicated indices.Source: §2 · p. 3

3. A Frontier of Lower Bounds

The section constructs adversarial lower bounds that trace a frontier of trade-offs involving the comparator norm, the logarithmic exponent, and penalties for gradient growth. It shows how large gradient jumps constrain regret, while slower growth can leave room for sublinear regret.

3.1. Trade-offs in the multiplicative constant k

  • A sequence of repeated unit gradients followed by a large jump can force exponential regret, with the penalty reflecting the jump in gradient magnitude.The first lower-bound inequality rules out sublinear regret while retaining the stated dependence on Lmax and ∥u∥; making the exponential term sublinear requires k = Ω(√T/log(T)), which makes the non-exponential term O(T).Source: §3.1 · p. 3

3.2. Trade-offs in the Logarithmic exponent γ √

  • Extending the adversary to vary γ yields a frontier in which reducing the logarithmic exponent comes at the cost of a larger exponential penalty.The bound permits regret proportional to ∥u∥Lmax√T log^γ(∥u∥T) for γ > 1/2, with the exponential penalty increasing as γ decreases.Source: §3.2 · pp. 4–5
  • When γ approaches 1/2, the apparent singularity need not make the bound diverge because Lmax = O(k²) regardless of T in the discussed setting.However, algorithms relying on a committed Lmax are fragile: if that bound is incorrect, the adversary can force Lmax exp(O(T/Lmax)) regret for arbitrarily large T.Source: §3.2 · p. 4

4. Regret Analysis without Information

The section develops FTRL conditions and adaptive regularizers for achieving regret guarantees without prior information. Its analysis connects regularizer design to the lower-bound frontier and gives a family of algorithms matching that frontier.

4. Regret Analysis without Information

  • FTRL chooses a regularizer after each loss and uses it to select the next iterate; the paper gives conditions for optimal regret without prior information.The analysis generalizes earlier unconstrained-domain regret proofs and improves the bound of Cutkosky and Boahen (2016).Source: §4 · p. 5

4.1. Generalizing Strong Convexity

  • Strongly convex regularizers cannot match the paper’s lower bounds, motivating a generalized form of strong convexity for the analysis.The generalization is described as similar to a dual version of the local-smoothness condition used by Orabona (2013).Source: §4.1 · p. 5

4.2. Adaptive regularizers

  • Adaptive regularizers must grow super-linearly to ensure a minimum, while avoiding quadratic growth that would yield O(∥u∥^2) regret.The paper formalizes conditions on their shape, including a strong-convexity parameter that decreases with the norm and a growth condition on ψ(x)σ(x).Source: §4.2 · p. 6
  • The construction turns an adaptive regularizer into round-specific FTRL regularizers using gradient-dependent sequences η_t and a_t.The sequences are defined recursively from observed subgradients and the running maximum gradient norm.Source: §4.2 · p. 6
  • Theorem 6 bounds regret with three terms that correspond to the comparator-dependent lower-bound term, a constant term, and the exponential penalty.For ψ(w) = (∥w∥ + 1) log(∥w∥ + 1) − ∥w∥, the first term matches the γ = 1 lower-bound term.Source: §4.2 · p. 7
  • A family of adaptive regularizers lets the resulting algorithms match any desired point on the lower-bound frontier.The regularizer’s form determines γ, while the frontier also includes a tradeoff parameter k.Source: §4 · p. 5, §4.2 · p. 7

5. Optimal Algorithms

The paper constructs adaptive regularizers that make FTRL algorithms match the lower-bound frontier. The construction covers γ values in (1/2, 1], and the resulting family matches the bounds up to constants.

5. Optimal Algorithms

  • The paper’s L2 regularizer ψ(w) = (∥w∥ + 1) log(∥w∥ + 1) − ∥w∥ is 1-optimal and matches the lower bound for any desired k.This is a specific instance of a broader family of γ-optimal adaptive regularizers.Source: §5 · pp. 8–9
  • For γ ∈ (1/2, 1], the paper constructs γ-optimal adaptive regularizers from one-dimensional functions φ, enabling high-dimensional regularizer design.The approach uses the L2 norm and is presented as an alternative to prior reductions based on a worst-case subgradient direction.Source: §5 · pp. 8–9

Proof

  • Applying Theorem 6 to the constructed regularizers yields algorithms whose regret matches the lower-bound family up to constants.The guarantees allow k to be selected using prior knowledge when available; a bound on gradient growth can make the exponentiated quantity constant.Source: Proof · pp. 9–10
  • The algorithms require no bounds on ∥u∥ or Lmax, while using other information to avoid the exponential penalty.The passage describes this as an intermediary regime between having prior bounds and paying the full penalty.Source: Proof · p. 10

6. FREEREX

FREEREX is an information-free online algorithm built with an adaptive regularizer and exponential updates. The paper gives a regret theorem for the algorithm and works through its bound.

6. FREEREX

  • FREEREX uses the L2 adaptive regularizer ψ(w) = (∥w∥ + 1) log(∥w∥ + 1) − ∥w∥ and is designed without requiring information about the losses.The name expands to “Information-free Regret via exponential updates.”Source: §6 · p. 10
  • The algorithm’s updates use a running quantity a_t and an FTRL update based on accumulated gradients.The displayed procedure initializes the algorithm at zero and updates a_t using the current maximum gradient norm and η_t.Source: §6 · p. 10
  • Theorem 11 states a regret bound for FREEREX, and the paper derives it by applying its general FTRL theorem to the chosen regularizer.The proof identifies ψ(w) with a function φ of ∥w∥ and then invokes Theorem 6.Source: §6 · p. 10

7. Conclusions

The paper presents a frontier of lower bounds for online convex optimization without prior information and algorithms that match any chosen point on it. It also identifies known gradient-growth information as another way to avoid an exponential penalty, while noting open extensions and scope limits.

7. Conclusions

  • The frontier expresses a fundamental trade-off in worst-case regret for online convex optimization without prior information.Source: §7 · p. 12
  • The algorithms match the lower-bound frontier for any chosen k and γ, requiring no prior information and only these trade-off parameters.The parameters can be freely chosen under the analysis, with no unknown constraints.Source: §7 · p. 12
  • A known bound on max_t Lt/Lt−1 can avoid the exponential penalty, offering another route alongside known bounds on domain diameter or maximum gradient.Source: §7 · p. 12
  • The lower-bound frontier may extend beyond ∥u∥log(∥u∥), and the conditions for exponential-in-T regret remain to be fully characterized.The paper identifies a large jump in Lt as one such condition and notes that others may exist.Source: §7 · p. 12
  • Although the analysis allows arbitrary norms, the examples focus on L2; diverse or time-changing norm regularizers remain potential extensions.Source: §7 · p. 12

Appendix A. Lower Bound Proof

Appendix A proves a lower-bound result using an adversarial loss sequence. Its argument turns on whether the learner’s expected prediction crosses a threshold.

Appendix A. Lower Bound Proof

  • For any online optimization algorithm and allowed γ, k, and T0, Theorem 2 gives a later horizon, comparator, and bounded-gradient sequence witnessing its lower bound.Source: Appendix A · p. 14
  • The adversary repeats gradient −1 until expected predictions cross a threshold; if they do not, a large comparator incurs regret, and if they do, a large positive gradient forces regret at zero.Source: Appendix A · p. 14
  • For randomized algorithms with a deterministic sequence g_t, the passage says the same result holds in expectation, though this excerpt does not specify what that result is.Source: Appendix A · p. 14

Appendix B. FTRL regret

Appendix B gives a general FTRL regret bound and decomposes it in a way the authors say makes the analysis easier. The bound uses shadow regularizers to characterize regret.

Appendix B. FTRL regret

  • The appendix derives a general FTRL regret bound and uses a new decomposition to make its analysis easier.Source: Appendix B · p. 17
  • Shadow regularizers are used to characterize regret more easily.Source: Appendix B · p. 17
  • The bound is similar in form to adaptive online mirror descent and analyses of FTRL with varying regularizers.Source: Appendix B · p. 17

Appendix C. Facts About Strong Convexity

Appendix C establishes basic facts about the paper’s generalized strong convexity, including conditions based on curvature and how the property behaves under transformations and additions.

Appendix C. Facts About Strong Convexity

  • Scaling the argument of a strongly convex function by c yields c²σ′-strong convexity, with σ′(x,y)=σ(cx,cy).Source: Appendix C · p. 20
  • Adding a convex function to a σ-strongly convex function preserves σ-strong convexity; adding a linear function does as well.Source: Appendix C · p. 20
  • A Hessian lower bound by σ(x) in a norm, with σ concave along line segments as specified, is sufficient for σ-strong convexity.Source: Appendix C · p. 21

Appendix D. Proof of Theorem 8

Appendix D proves that a radial function built from φ can be strongly convex and satisfy the adaptive-regularizer conditions. The proof checks these properties using assumptions on φ and its derivatives.

Appendix D. Proof of Theorem 8

  • Under the stated derivative conditions, ψ(w) = φ(∥w∥) is φ′′(∥w∥)-strongly convex with respect to the norm.The construction is stated for a Hilbert space W.Source: Appendix D · p. 21
  • The proof verifies the adaptive-regularizer conditions by showing ψ(0) = 0, establishing the required monotonicity, and checking a growth condition.The growth check uses the stated limit of φ(x)φ′′(x).Source: Appendix D · p. 22
  • The derivative assumptions imply that φ′(x) − xφ′′(x) is non-negative, supplying an intermediate step in the proof.The passage derives this from φ′′′(x) ≤ 0.Source: Appendix D · p. 22

Appendix E. Proof of Theorem 6

Appendix E proves Theorem 6 for an adaptive regularizer and an arbitrary sequence of subgradients. It combines identities and technical lemmas to establish the theorem’s stated bounds.

Appendix E. Proof of Theorem 6

  • Proposition 19 establishes identities for the regularizer sequences that the proof uses in deriving its bounds.The passage introduces these identities as needed for proving the bounds.Source: Appendix E · p. 22
  • Lemma 24 supplies a bound for non-negative sequences whose terms grow by at least a factor of two.The proof applies it when selected gradient-related quantities increase by that factor.Source: Appendix E · pp. 30, 33
  • The proof establishes Theorem 6’s first and second inequalities for an arbitrary sequence of subgradients and k ≥ 1.The proof identifies L_T = Q_T for the first inequality and uses bounds involving η_T^+ and a_T for the second.Source: Appendix E · pp. 34–35
  • The regret proof combines Theorem 13 with Lemmas 22 and 23, then simplifies the resulting bound.The proof also invokes Lemma 25 in simplifying it.Source: Appendix E · p. 34

Related papers

Loading 1703.02629v2…