Source-linked AI summary
Adaptive Bound Optimization for Online Convex Optimization
H. Brendan McMahan, Matthew Streeter
TL;DR
The paper addresses the gap between worst-case-optimal online convex optimization bounds and better bounds available on structured problem instances. It introduces an adaptive FTRL algorithm that selects regularization functions from observed losses, and shows competitive guarantees against the best hindsight choice. The resulting bounds can be dramatically better on hyperrectangles and related structures while retaining worst-case guarantees.
Problem
Worst-case-optimal regret bounds can still be unnecessarily large on structured feasible sets, while useful problem structure is not known in advance.
Method
The paper analyzes FTPRL, which adaptively selects positive semidefinite regularization matrices using previously observed loss functions.
Results
The algorithm retains worst-case-optimal bounds and can provide substantially better bounds on hyperrectangles and other structured feasible sets.
Takeaways & Limitations
Adaptive regularization exploits structure typical of large-scale learning problems without requiring that structure to be specified beforehand.
Takeaways & Limitations
For arbitrary feasible sets, guarantee quality and competitive ratios depend on how tightly the set can be approximated by a suitable transformed norm ball, and richer regularization families remain open.
Abstract
from arXiv · showhide
We introduce a new online convex optimization algorithm that adaptively chooses its regularization function based on the loss functions observed so far. This is in contrast to previous algorithms that use a fixed regularization function such as L2-squared, and modify it only via a single time-dependent parameter. Our algorithm's regret bounds are worst-case optimal, and for certain realistic classes of loss functions they are much better than existing bounds. These bounds are problem-dependent, which means they can exploit the structure of the actual problem instance. Critically, however, our algorithm does not need to know this structure in advance. Rather, we prove competitive guarantees that show the algorithm provides a bound within a constant factor of the best possible bound (of a certain functional form) in hindsight.
1 Introduction
The paper develops adaptive regularization for online convex optimization, targeting problem-dependent regret without knowing loss structure in advance. It establishes competitive guarantees and identifies feasible-set geometries where coordinate adaptation yields substantial gains.
- 1 Introduction: Worst-case-optimal regret can remain unnecessarily large on easy instances, such as hypercubes where better algorithms exist than the standard L2-based guarantee.The conventional bound depends on feasible-set diameter and gradient norms and is minimax optimal for hyperspheres, but not necessarily practically optimal.
- 1 Introduction: Adaptive schemes choose regularization parameters from previously observed losses and achieve regret within a constant factor of the best bound of the same functional form in hindsight.The method first constructs functional regret bounds depending on losses and algorithm parameters, then selects those parameters online.
- 1.1 Follow the proximally-regularized leader: FTPRL centers additional regularization at the current feasible point and uses the sum of previous gradients, yielding a global rather than local optimization each round.This distinguishes it from dual averaging, which centers regularization at the origin.
- 1.2 The practical importance of adaptive regularization: Adaptive regularization has practical relevance for sparse, heavy-tailed feature distributions in text classification and click-through-rate prediction, where ordinary gradient descent can have vacuous bounds.For heavy-tailed gradients, the adaptive bound can be sublinear for α > 1, while ordinary gradient descent may scale as O(nT).
- 1.3 Adaptive algorithms and competitive ratios: 2-competitive guarantees are obtained for coordinate-constant matrices on Lp balls with p ∈[1, 2], relative to the best post-hoc positive semidefinite choice.The result is stated for the full family of positive semidefinite matrices.
- 1.3 Adaptive algorithms and competitive ratios: For p > 2, coordinate-independent regularization is not generally post-hoc optimal, so per-coordinate adaptation can improve bounds, especially on the L∞ ball.FTPRL-Diag selects diagonal matrices using coordinate widths of the feasible set.
- 1.3 Adaptive algorithms and competitive ratios: 2-competitive guarantees extend to transformed hyperellipsoids and certain transformed Lp balls, while arbitrary feasible sets inherit guarantees dependent on norm-ball approximation quality.For arbitrary sets, the guarantee relates to the widths of the smallest containing hyperrectangle and largest contained hyperrectangle.
2 Analysis of FTPRL
The analysis bounds FTPRL regret for arbitrary regularization matrices by combining an FTRL regret lemma with a projection-based characterization of the algorithm. It relates successive iterates through the matrix-induced geometry and subgradients.
- Regret bound: Theorem 2 gives a regret bound for FTPRL on a closed, bounded convex feasible set containing the origin, using arbitrary regularization matrices.The bound applies to a sequence of convex losses with subgradients at the played points.
- Regret bound: Lemma 1 bounds FTPRL regret using non-negative regularization functions and the post-hoc optimal feasible point.This lemma provides the general FTRL-style bound used to prove Theorem 2.
- Algorithm characterization: The algorithm is equivalently characterized as unconstrained optimization followed by projection onto the feasible set.This reformulation makes the unconstrained solutions depend on cumulative linear terms and quadratic regularization.
- Algorithm characterization: The unconstrained update has a closed form determined by cumulative regularization matrices, cumulative gradients, and the proximal-centering terms.The optimality condition yields the update relation for the next unconstrained point.
- Geometric analysis: Projection makes successive unconstrained points no farther apart under the matrix-induced norm, enabling a per-round regret bound in terms of A_t^-1g_t.The analysis combines this contraction property with the relation between consecutive unconstrained solutions and the current subgradient.
3 Specific Adaptive Algorithms and Competitive Ratios
The paper develops adaptive regularization schemes whose parameters are chosen from observed losses and whose regret is competitive with the best post-hoc bound. Guarantees depend on the feasible set, with diagonal adaptation especially effective for hyperrectangles and broader approximation settings.
- The post-hoc optimization can be reduced to a sequence using Q_1 = Q and Q_t = 0 thereafter.This reduction follows from the monotonicity of cumulative regularization matrices.
- Adaptive coordinate-constant regularization: 2-competitive guarantees are obtained for coordinate-constant regularization, including the standard O(DM√T) scale when gradient norms are bounded by M.The coordinate-constant scheme matches the best possible bound in terms of diameter and gradient-norm parameters.
- Adaptive diagonal regularization: 2-competitive guarantees are obtained for FTPRL-Diag against the best post-hoc diagonal bound on hyperrectangles.The algorithm sets cumulative diagonal entries using coordinate widths and observed gradient information.
- Adaptive diagonal regularization: For arbitrary feasible sets bounded between inner and outer hyperrectangles, FTPRL-Diag is 2β-competitive, where β is the largest outer-to-inner width ratio.The regret guarantee itself holds on arbitrary feasible sets, while this competitive comparison uses the hyperrectangle approximation.
- Full matrix regularization on Lp balls: For Lp balls, coordinate-constant regularization is always optimal when p ≤ 2, whereas per-coordinate adaptation can improve the post-hoc bound when p > 2.The non-constant optimum for p > 2 excludes only the degenerate case of identical cumulative coordinate quantities.
- Full matrix regularization on hyperspheres and hyperellipsoids: For hyperspheres, the optimal regularization is coordinate-constant, while transformations extend the corresponding result to hyperellipsoids.The transformed algorithm retains the same competitive guarantees, and the resulting bound can be arbitrarily better when some scaling factors are much smaller than 1.
4 Related work
The paper situates adaptive regularization among preconditioning, online learning, and prior competitive-bound analyses. It distinguishes its general online convex optimization setting and feasible-set guarantees from more specialized preceding methods.
- The work extends the preconditioning idea from batch convex optimization to online convex optimization and regret bounds.The proposed change of coordinates accounts for both feasible-set shape and loss structure.
- Confidence-weighted classification and AROW also adapt across coordinates, but they target classification and provide mistake bounds rather than general regret bounds.The comparison highlights a difference in problem scope and guarantee type.
- FTPRL differs from lazily-projected gradient descent by centering additional regularization at the current feasible point rather than outside the feasible region.The cited comparison links this centering choice to how low regret is achieved.
- Prior general online-learning methods include extensions of online subgradient descent, while few general follow-the-regularized-leader algorithms had been analyzed.The paper places FTPRL within this relatively limited general FTRL literature.
- Competitive ratios for regret bounds depending on regularization parameters had been proved previously, but for different algorithms and parameter classes.The paper identifies Bartlett et al. and Do et al. as examples of this earlier line of work.
- Concurrent per-coordinate learning-rate results were less general because they were restricted to hyperrectangular feasible sets, whereas FTPRL applies to arbitrary feasible sets.The paper's bounds also incorporate feasible-set shape and coordinate widths.
5 Conclusions
The paper develops adaptive regularization for online convex optimization and identifies when generalized learning rates yield substantial regret improvements. Its diagonal adaptation is efficient and competitive on hyperrectangles, while broader feasible-set and regularizer families remain open directions.
- Positive semidefinite matrix learning rates provide extra degrees of freedom for obtaining better regret bounds.The algorithm combines ideas from online subgradient descent and follow-the-regularized-leader.
- The technique offers no benefit on hyperspheres but can have dramatic impact on hyperrectangles.The paper characterizes feasible-set types where these gains occur.
- Diagonal adaptation incrementally optimizes the final regret-bound formula and achieves a bound within a small constant factor of the best hindsight bound on hyperrectangles.This guarantee applies when the feasible set is itself a hyperrectangle.
- The diagonal adaptation algorithm is efficient and targets structure common in large-scale learning tasks such as click-through rate prediction and text classification.
- Future work includes competitive algorithms for arbitrary feasible sets and optimization over richer regularization-function families.
A A Proof of the FTRL Bound
The proof decomposes FTRL regret into three comparisons involving be-the-leader, be-the-regularized-leader, and FTRL, then bounds these components to obtain the result. The be-the-leader step supplies a nonpositive regret baseline, while the BTRL lemma bounds its regret by cumulative regularization.
- The proof bounds three quantities: be-the-leader regret, the difference between BTL and BTRL regret, and the difference between BTRL and FTRL regret.
- Be-the-leader has regret at most zero for arbitrary function sequences and feasible sets.The proof follows by induction on the number of rounds.
- BTRL has regret at most r1:T(˚x), where ˚x is the post-hoc optimal solution.
- The BTRL proof uses the identity t(x) = ft(x) + rt(x) and the inequality ft(ˆxt) + rt(ˆxt) ≤ r1:T(˚x) + f1:T(˚x).Dropping the nonnegative rt(ˆxt) terms yields the lemma.
- The total loss of FTRL exceeds that of BTRL by the corresponding cumulative difference between their played points.
B Proof of Lemma 5
The proof proceeds inductively by analyzing the derivative of an auxiliary expression involving Z. It establishes that the expression decreases for positive x, allowing the constrained optimization to be characterized at the relevant boundary.
- The proof assumes the lemma for n − 1 after establishing the base case n = 1.
- The derivative of the right-hand side is negative when x > 0.
- Because the expression decreases for positive x, the constraint x ≥ 0 determines the relevant form of the optimized right-hand side.