PaperlayerView exact revision on arXiv

Source-linked AI summary

Introduction to Online Convex Optimization

Elad Hazan

arXiv:1909.05207v3cs.LGmath.OCstat.ML

TL;DR

This textbook presents online convex optimization for settings where classical modeling and projection computation are difficult. It develops rigorous definitions, algorithms, and connections across applications, including portfolio selection and second-order methods, while noting computational limits in adaptive procedures.

  • Problem

    Online convex optimization addresses practical settings where comprehensive modeling is infeasible and projection computation can bottleneck both online and offline optimization.

  • Method

    The book develops online convex optimization through problems, rigorous definitions, backgrounds, algorithms, and applications including portfolio selection and second-order methods.

  • Results

    The presented framework includes logarithmic regret algorithms based on second-order information, alongside formal results for randomized weighted majority and zero-sum games.

  • Takeaways & Limitations

    Online convex optimization provides a shared framework connecting optimization, machine learning, portfolio selection, game theory, and related fields.

  • Takeaways & Limitations

    FLH can require up to T invocations of its base algorithm, making its running time prohibitive as the number of iterations grows.

Abstract

from arXiv · show

This manuscript portrays optimization as a process. In many practical applications the environment is so complex that it is infeasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary as well as beneficial to take a robust approach, by applying an optimization method that learns as one goes along, learning from experience as more aspects of the problem are observed. This view of optimization as a process has become prominent in varied fields and has led to some spectacular success in modeling and systems that are now part of our daily lives.

9 Learning Theory, Generalization, and Online Convex Optimization

The book connects online convex optimization with learning theory, games, boosting, and related machine-learning topics. It presents OCO as a framework for efficient algorithms and situates the material within the broader machine-learning literature.

  • Learning theory and generalization: Chapter 9 formally connects OCO with statistical learning theory and shows how regret minimization yields computationally efficient learning algorithms.
  • Boosting: The book covers boosting, online boosting, and the relationship between boosting algorithms and regret minimization.
  • Connections to games: A new chapter relates Blackwell approachability to online convex optimization, extending the book’s connections to learning in games and optimization.
  • Scope and positioning: The book is intended as an educational textbook and reference at the intersection of optimization and machine learning.

Book’s tructure

The book is organized as a graduate-level course progressing from OCO foundations and core algorithms to advanced methods, extensions, and machine-learning connections. The second edition expands both foundational coverage and advanced applications.

  • Book structure: The book is designed for graduate courses and can support either a dedicated OCO course or a broader machine-learning course.
  • Book structure: The first three chapters units progress from OCO definitions, framework, and core algorithms to advanced algorithms, extensions, and machine-learning relationships.
  • Second-edition additions: The second edition expands optimization coverage with a unified gradient descent analysis of the Polyak stepsize.
  • Second-edition additions: It adds or revises material on learning theory, exponential weights, mirror descent, adaptive gradients, adaptive regret, boosting, online boosting, and Blackwell approachability.
  • Second-edition additions: The edition also fixes typos, corrects exercises, and makes selected solutions available to educators.

The First Version

The author acknowledges students, colleagues, family, and contributors whose teaching, feedback, artwork, and support helped make the first version possible.

  • Acknowledgments: Students from courses at the Technion and Princeton are acknowledged for their contributions and insight.
  • Acknowledgments: Colleagues and students contributed suggestions and corrections to the manuscript.
  • Acknowledgments: Udi Aharoni is thanked for artwork and illustrations depicting algorithms in the book.
  • Acknowledgments: The author expresses special gratitude to Sanjeev Arora as a teacher and mentor.
  • Acknowledgments: The author acknowledges his wife and children for their love and support.

The Second Version

The second-version acknowledgments recognize collaborators, proofreaders, reviewers, and contributors to technical topics and presentation. The surrounding material also defines selected notation used throughout the book.

  • Acknowledgments: Students and colleagues collaborated on research appearing in the second version, notably on boosting methods.
  • Acknowledgments: Students helped proofread new and existing sections.
  • Acknowledgments: Shay Moran contributed explanations of compression schemes and their use in simplifying generalization for boosting.
  • Acknowledgments: Other contributors provided suggestions, corrections, problem-set solutions, and technical advice on Online Newton Step and randomized regularization.
  • Notation: The notation includes arg min for the minimizing argument, [n] for {1, 2, ..., n}, R^d for d-dimensional Euclidean space, and |A| for a matrix determinant.

Introduction

Online convex optimization treats optimization as an iterative learning process for complex environments where complete theoretical models are infeasible. It formalizes decisions over bounded convex sets, adversarially revealed convex costs, and regret against the best fixed decision in hindsight.

  • OCO addresses complex applications by learning as more aspects of the problem are observed instead of requiring a comprehensive theoretical model.
  • OCO studies iterative decisions whose outcomes and losses are unknown when each decision is made, with losses potentially chosen adversarially.
  • The framework uses a bounded convex decision set K ⊆ R^n and bounded convex cost functions over K.
  • At iteration t, the player chooses x_t ∈ K, then observes a convex cost function f_t and incurs f_t(x_t).
  • Sublinear regret, Regret_T(A) = o(T), means the algorithm performs on average as well as the best fixed strategy in hindsight.
  • OCO models diverse problems, including expert advice and online shortest paths, while succinct flow-polytope formulations enable computationally efficient algorithms.

Basic Concepts in Convex Optimization

This chapter introduces convex optimization over bounded convex sets and develops gradient-based methods, including projections, Polyak stepsizes, and reductions that extend convergence guarantees across function classes.

  • Problem setup: The chapter studies minimizing a continuous convex function over a bounded, closed, convex subset of Euclidean space.The set is denoted K ⊆ R^d, with D an upper bound on its diameter.
  • Projections: Projections map points to the closest point in a convex set and provide the geometric tool used by constrained optimization algorithms.Projection computation can be polynomial-time with a membership-oracle representation and near-linear in certain special cases.
  • Optimality conditions: Convexity preserves global optimality: every local minimum of a convex function is also a global minimum.For constrained problems, optimality is characterized by the negative gradient or subgradient pointing outward relative to feasible directions.
  • Gradient descent: Gradient descent converges on convex objectives with suitable step sizes, but its convergence rate depends strongly on smoothness and strong convexity.The chapter summarizes first-order convergence rates and gives a Polyak-stepsize guarantee, alongside a constrained result for γ-well-conditioned functions.
  • Reductions: The manuscript uses reductions rather than analyzing every gradient-descent variant from scratch to obtain near-optimal rates for several objective classes.The reductions cover smooth non-strongly-convex, strongly-convex non-smooth, and unrestricted convex functions.
  • Reductions: The reduction approach is simpler and more generic than direct analyses, but can lose logarithmic factors and, for non-smooth functions, a factor depending on dimension.The stated reduction is suboptimal by O(log T) in one setting and by an additional factor of d in another.

First-Order Algorithms for Online Convex Optimization

This section introduces online convex optimization algorithms that minimize regret rather than offline optimization error, emphasizing simple first-order methods and their guarantees. Online gradient descent is broadly applicable, achieves tight worst-case regret up to constants, and can obtain improved bounds for structured loss functions.

  • OCO algorithms minimize regret, because offline optimization error is ill-defined when cost functions arrive online.The section frames regret as comparison with the best fixed strategy in hindsight.
  • Online gradient descent: Online gradient descent updates from the previous point using the previous cost’s gradient and projects back to the convex decision set when necessary.The update is straightforward and linear-time given the gradient, although projection may be significantly more expensive.
  • Online gradient descent: Online gradient descent attains sublinear regret even when the next cost function differs completely from previously observed costs.The guarantee is formalized by the section’s main OGD theorem.
  • Lower bounds: Any OCO algorithm incurs Ω(DG√T) regret in the worst case, even when cost functions are generated from a fixed stationary distribution.This lower bound shows that OGD’s worst-case regret is tight up to small constant factors.
  • Structured loss functions: For α-strongly convex loss functions, changing OGD’s step size yields regret logarithmic in the number of iterations.The section presents step sizes η_t = 1/(αt) for this setting.
  • Stochastic optimization: The section connects OCO regret guarantees to stochastic optimization, including an ε-approximate solution after O(1/ε^2) iterations and a refined ˜O(1/ε^2) rate.The stochastic-gradient discussion also notes that each iteration can use only one example while matching the convergence rate of standard offline gradient descent.

Second-Order Methods

This section develops online portfolio selection as an OCO problem and motivates second-order methods for achieving logarithmic regret on exp-concave losses. It contrasts simple multiplicative-update methods with computationally efficient online Newton steps.

  • Portfolio Selection: Portfolio selection can be modeled as repeated allocation over the simplex against adversarial asset returns, with logarithmic wealth serving as the objective.The framework avoids statistical assumptions about stock markets and measures performance through regret.
  • Portfolio Selection: Sublinear regret makes average log-wealth growth as good as any fixed rebalanced portfolio in hindsight.The comparator may be a mixed portfolio rather than a single stock.
  • Second-Order Methods: Exp-concavity arises because the portfolio loss Hessian is large in the gradient direction, and it suffices for logarithmic regret.This property replaces strong convexity for the portfolio-selection loss.
  • Second-Order Methods: EWOO gives logarithmic regret for exp-concave losses with a simple, robust guarantee that does not require Lipschitz or diameter parameters.Its main drawback is computational: naive implementation is exponential in dimension, though randomized polynomial-time implementation is possible.
  • Second-Order Methods: Online Newton step provides a second-order approach whose projection subproblem is a convex program solvable to arbitrary accuracy in polynomial time.Its stated advantage is a logarithmic regret guarantee.

Regularization

This section introduces regularization as a way to stabilize Follow the Leader and develops RFTL, mirror-descent connections, and adaptive regularization methods with regret guarantees. It shows that several standard online algorithms arise as instances of this framework.

  • Regularization: Follow the Leader can incur linear regret because alternating costs make its decisions unstable and repeatedly wrong.Regularization is introduced to prevent excessive decision changes.
  • Regularization: RFTL stabilizes Follow the Leader by adding a strongly convex, smooth regularization function over the decision set.The regularizer is assumed twice differentiable with positive-definite Hessian in the interior.
  • RFTL: The RFTL template achieves asymptotically optimal regret bounds, although the presentation does not optimize their constants.The framework bounds convex-function regret through linearization by current gradients.
  • Mirror Descent: For linear costs, lazy OMD and RFTL produce identical predictions, so lazy OMD inherits RFTL’s regret bounds.The agile version has similar bounds and can be superior in settings requiring adaptivity.
  • Derived Algorithms: The regularization technique derives online gradient descent and exponentiated gradient, with exponentiated gradient coinciding with Hedge in a special case.For arbitrary cost ranges, the corresponding exponentiated-gradient algorithm is also obtained.
  • Randomized Methods: For a uniform unit-hypercube perturbation distribution, FPL has a regret bound a factor n^1/4 worse than online gradient descent, while other decision sets can admit near-optimal bounds.The randomized method’s computational advantage is requiring only one linear optimization step, even when the decision set is nonconvex.
  • Adaptive Gradient Descent: AdaGrad learns the regularization online by adapting to the sequence of cost-function gradients and optimizing the regularization choice in hindsight.Its regret can be within a constant factor of the best fixed-Hessian RFTL regularizer, while diagonal AdaGrad can outperform OGD by a factor d for certain gradient geometries.

Bandit Convex Optimization

Bandit Convex Optimization models online decisions when only the incurred loss is observed, rather than gradients or full loss information. The section develops exploration-based algorithms and reductions that achieve sublinear or near-optimal regret bounds.

  • Motivation: Partial feedback arises in routing and ad placement because decision makers observe selected outcomes but not the network-wide congestion or unchosen ads’ responses.Routing exposes round-trip delay, while ad placement exposes clicks only for displayed ads.
  • BCO model: In BCO, the player chooses xt ∈ K before observing a convex cost function’s value at xt, with no gradient oracle over K.This contrasts with OCO, where gradient feedback is available over the decision set.
  • MAB reduction: The simple MAB scheme explores randomly, estimates action losses, and otherwise applies a full-information experts algorithm, yielding sublinear regret.The scheme models MAB as BCO on the simplex with linear loss functions.
  • EXP3: EXP3 combines exploration and exploitation by estimating the entire loss vector every iteration, attaining worst-case regret O(√Tn log n), nearly optimal up to a logarithmic factor in n.Its large-magnitude estimators occur with low probability, enabling a finer analysis.
  • General BCO reduction: A formal reduction from first-order online algorithms to BCO preserves the original regret bounds up to the magnitude of estimated gradients under mild conditions.For small δ, the estimator g(x) approximates f′(x) in expectation.

Projection-Free Algorithms

Projection-free methods address the high cost of projections in convex optimization, especially for matrix completion. The conditional gradient method replaces projections with linear optimization, enabling lower-cost online and offline procedures.

  • Motivation: Projection-free methods target projection computation, a major optimization bottleneck in many computational and learning scenarios.The chapter motivates these methods partly through matrix completion, where projections require expensive linear algebra.
  • Matrix completion: Matrix completion uses low-rank structure to formulate a convex nuclear-norm relaxation of an otherwise non-convex rank constraint.The motivating application is recommendation systems, where projections onto the relevant matrix set can require singular value decompositions.
  • Conditional gradient: The conditional gradient, or Frank-Wolfe, method minimizes smooth convex functions without projections by repeatedly solving linear optimization problems over the feasible set.Its iterates remain inside the convex set, and the update uses a linear objective rather than a projection.
  • Computational trade-offs: For matrix optimization, conditional gradient replaces expensive SVD-based projections with linear-time eigenvector computations using methods such as the power method.The resulting per-iteration operation is linear-time rather than the significantly more expensive SVD computation required by gradient descent.
  • Computational trade-offs: Conditional gradient may require more iterations than efficient gradient descent, but its lower per-iteration cost can make it preferable.In flow and matroid polytopes, the required linear optimization can reduce to shortest-path or greedy procedures.
  • Online conditional gradient: The online conditional gradient algorithm transfers projection-free computation to online convex optimization, accepting a suboptimal regret bound in exchange for lower computational cost.The chapter provides a regret guarantee for the algorithm with parameters η = D/(2GT^3/4) and σ_t = min{1, 2/t^1/2}.

Games, Duality, and Regret

The chapter connects online convex optimization with linear-programming duality and zero-sum games through regret minimization. It establishes minimax equality and shows that the same framework yields efficient approximate solutions.

  • Framework: Sublinear-regret online convex optimization algorithms provide the machinery for proving convex duality and von Neumann’s minimax theorem.The chapter follows the regret-minimization approach while giving concise proofs of both results.
  • Linear programming: Linear programming is a convex optimization problem with a polyhedral feasible set and a linear objective function.The chapter introduces equivalent formulations, including one with non-negative variables.
  • Duality: The duality theorem states that a linear program and its dual have objectives that are equal or unbounded.The chapter presents the dual program and uses this relationship to connect linear programming with zero-sum games.
  • Zero-sum games: In a two-player zero-sum game, one player’s loss is the negative of the other player’s reward, and mixed strategies represent distributions over pure strategies.The chapter defines games through a payoff matrix and extends equilibrium concepts from pure to mixed strategies.
  • Minimax theorem: Von Neumann’s minimax theorem establishes λ_R = λ_C for every zero-sum game.The common value λ⋆ exists and is unique, and optimal strategies form an equilibrium.
  • Approximation: The equivalence between zero-sum games and linear programs lets the regret-based technique prove minimax results and produce efficient algorithms for linear programming.The chapter applies this technique to obtain approximate solutions through repeated simple updates.

Learning Theory,

This section connects online convex optimization to statistical learning, formalizes limits on learning and generalization, and shows that regret minimization yields efficient agnostic learning algorithms.

  • Statistical Learning Theory: Statistical learning seeks a hypothesis with arbitrarily small generalization error from i.i.d. labeled samples drawn from an arbitrary distribution.The hypothesis is evaluated using a specified loss function, often convex.
  • Statistical Learning Theory: Overfitting occurs when a hypothesis perfectly classifies training examples but generalizes poorly to unseen inputs.The naive bitmap algorithm illustrates this by assigning every unseen image the label “1.”
  • Statistical Learning Theory: Every finite concept class is agnostically PAC learnable with sample complexity polynomial in ε, δ, and log |H|.This result supplies a learnability guarantee for finite hypothesis classes.
  • Agnostic Learning using Online Convex Optimization: The section reduces agnostic learning to online convex optimization, using an OCO algorithm’s regret guarantee to obtain a high-probability learning guarantee.The reduction is formally described in Algorithm 29 and analyzed in Theorem 9.5.
  • Learning and Compression: A compression scheme of size k implies PAC learnability with sample complexity proportional to k.The associated theorem states that the resulting hypothesis has error at most ε with probability at least 1 − δ.

Learning in Changing Environments

Standard regret methods converge to fixed solutions and may fail to track changing environments. This section introduces adaptive regret and efficient algorithms that compete with changing comparators while controlling computational overhead.

  • Learning in Changing Environments: When the underlying distribution changes, regret minimization no longer guarantees convergence to an optimal strategy for the new environment.Examples include cyclic traffic patterns and shifts between investment strategies across bull and bear markets.
  • Learning in Changing Environments: Standard regret can induce static behavior in changing environments, causing algorithms to converge to a fixed solution.Adaptive regret is introduced to support changing prediction strategies.
  • Dynamic Regret: Dynamic regret compares an algorithm with a sequence of decisions, and its bound scales with the comparator sequence’s path length.For a fixed comparator, the path length is one, recovering the standard O(√T) regret bound.
  • The Notion of Adaptive Regret: Adaptive regret provides a more general performance measure whose guarantees also imply low dynamic regret and extend to k-shifting comparators.For k intervals, the resulting overall regret is bounded by k × AdaptiveRegretT/k.
  • Efficient Adaptive Regret for Online Convex Optimization: FLH treats OCO algorithms started at different times as experts and applies Fixed Share to them, achieving optimal standard and adaptive regret guarantees with small computational overhead.The method is designed for efficient adaptive regret in online convex optimization.
  • Computationally Efficient Methods: FLH2 prunes the active algorithms from t to O(log t), reducing running time to O(VT(A) log T) while worsening adaptive regret by a multiplicative O(log T) factor relative to FLH.The method stores only O(log t) experts at time t instead of all t experts.

Boosting and Regret

Boosting combines simple, weak rules into an accurate predictor. The chapter shows that online convex optimization can reduce weak learning to strong learning under realizability, with a final hypothesis that classifies the training sample correctly.

  • The Problem of Boosting: Boosting combines rough rules of thumb into a more accurate predictor, motivating whether simple weak classifiers can be combined efficiently.The OCR example uses a single-pixel rule that is efficient but inaccurate, then asks whether several such rules can form an accurate classifier.
  • Boosting by Online Convex Optimization: The chapter answers the boosting question affirmatively through a black-box reduction from regret minimization in OCO to boosting.The reduction allows previously discussed OCO methods to be used as part of the boosting procedure.
  • Simplification of the Setting: Under binary classification and realizability, an OCO algorithm with sublinear regret converts a γ-weak learner into a strong learner.The construction uses distributions over the sample as OCO decisions and linear costs representing hypothesis errors.
  • Completing the Picture: The final hypothesis need not belong to the original hypothesis class H.The output is constructed from the weak learners rather than required to be one member of H.
  • Algorithm and Analysis: Algorithm 34 returns a final hypothesis that, with probability at least 1 −δ, has zero empirical error on the sample.The proof derives a contradiction from the existence of any misclassified sample distribution.
  • Completing the Picture: The boosting algorithm runs for T = O(log m/γ^2) rounds, returns a majority vote, and correctly classifies all m training examples.Using the exponential-weights regret bound gives the stated round complexity; choosing the sample size appropriately yields arbitrarily small generalization error.

Online Boosting

Online boosting addresses settings where the expert class is too large for direct manipulation. The chapter introduces weak online learners and shows that boosting can achieve low regret against the convex hull of the base hypotheses.

  • Motivation: Learning from a Huge Set of Experts: Large policy classes make standard expert algorithms computationally inefficient because their running time depends linearly on the number of experts.In contextual learning, the number of policies can be exponential in the number of contexts.
  • Motivation: Learning from a Huge Set of Experts: An online weak learner is a computationally cheap mechanism with a multiplicative regret guarantee against a base hypothesis class.The guarantee permits an additive sublinear regret term and uses a factor γ relative to the best expert.
  • Online Boosting: The chapter constructs efficient algorithms that, given weak learners, compete with the convex hull of the base hypotheses class with near-optimal regret.This provides an affirmative online analogue of boosting without explicit access to the potentially huge expert class.
  • Boosting for Online Convex Optimization: The OCO formulation handles a general convex decision set K and adversarially chosen convex loss functions while avoiding direct dependence on the hypothesis class.The alternative access model supplies hypotheses through a weak learner rather than by explicitly enumerating H.
  • The Extension Operator: The extension operators project infeasible points produced by weak learners into the feasible domain required by the OCO boosting algorithm.This projection role is identified as crucial to Algorithm 36.
  • The Main Result: Even when γ = 1, online boosting improves the comparison class from the best single hypothesis to the convex hull of H.The stronger comparator can provide an advantage over the weak learner despite no multiplicative weakening.
  • The Main Result: The main regret bound combines a term that vanishes as the number of weak learners grows with the weak learner’s sublinear regret scaled by 1/γ.The two terms reflect increasing the number of weak learners and the approximate nature of the weak guarantee.

Blackwell Approachability and Online Convex Optimization

Blackwell approachability asks whether repeated play can drive an average vector payoff toward a convex target set. The chapter establishes an algorithmic equivalence between approachability and online convex optimization.

  • Equivalence: The reductions supply an OCO-based proof of Blackwell’s theorem and extend the relationship to general vector games.The approachability–OCO equivalence is presented as algorithmic in both directions.
  • Motivation: Blackwell approachability generalizes scalar game guarantees by asking whether a vector payoff can be driven toward a closed convex set.Because a single mixed strategy need not ensure the target, the chapter uses repeated play and average reward vectors.
  • Approachability: A set is approachable when an adaptive strategy makes the average reward vector come arbitrarily close to it against any sequence of opponent actions.Blackwell’s theorem characterizes the sets that satisfy this property.
  • Blackwell’s Theorem: Blackwell’s approachability condition is necessary and sufficient for a closed, bounded, convex set to be approachable.The chapter gives the generalized theorem and an explicit proof strategy through reductions.
  • From OCO to Approachability: Any OCO algorithm with sublinear regret can be efficiently converted into an approachability algorithm for vector games.The reduction minimizes distance to the target set using convex analysis and support functions.
  • From Approachability to OCO: An approachability algorithm can conversely produce an OCO algorithm with no loss of computational efficiency and vanishing regret.Theorem 13.9 bounds the resulting regret by T(D + 1) · Dist_T(A).

Notes

The notes clarify scaling conventions, technical assumptions, and historical or methodological context for online optimization and learning.

  • Scaling: Performance metrics in this setting should depend on the magnitude of the largest loss, equivalently to the stated scaling convention.The note places the scaling choice in the broader treatment of performance metrics later in the book.
  • Notation: The notation [n] denotes the integers {1, ..., n}, while argmin-style notation denotes the arguments minimizing an expression.The same note also mentions projections under alternative distance notions.
  • Technical Detail: The recurrence gives a_t ≤ 1/(t+1) by induction from a_t ≤ a_{t−1}(1 − a_{t−1}).The base cases use 0 ≤ a_0 ≤ 1 and a_1 ≤ 1/2.
  • Technical Detail: For odd T, the same constants apply as in the even-T analysis.The note states that the displayed derivation assumes T is even.
  • Historical Notes: The FTL-BTL terminology contrasts follow-the-leader with a hypothetical be-the-leader predictor.The terminology is attributed historically to Kalai and Vempala.
  • Related Concepts: Average sensitivity is a related name for the analogous quantity in harmonic analysis of Boolean functions.The note identifies a cross-disciplinary terminology connection.
  • Related Methods: Self-concordant barrier regularization is one example of a barrier method discussed later.The note points forward to the next chapter’s treatment.
  • Adaptive Regret: Some adaptive-regret results scale as k × AdaptiveRegret_T, depending on the algorithm used.This is presented as a bibliographic qualification to the surrounding results.
Loading 1909.05207v3…