Smoothed Online Convex Optimization

This direction is split into other directions: state transition overhead (switching cost constraints). Its last version stays readable and citable here.

Version 1 of 144 papers53 conceptsfrozen 2026-10-04

In standard online learning, an agent makes a sequence of decisions to minimize a cumulative loss. However, these models often assume that changing a decision is free. In the physical world—whether managing the power output of a generator, the server count in a data center, or the position of a robot—changing state incurs a "switching cost" due to mechanical wear, energy expenditure, or latency.

Smoothed Online Convex Optimization (SOCO), also known as Convex Function Chasing, explicitly models this reality by adding a penalty for movement to the standard objective function.

The Fundamental Tension

In SOCO, the agent faces a "tug-of-war" between two competing objectives:

  1. Hitting Cost: The immediate loss incurred by the current action relative to the current environment.
  2. Switching Cost: The penalty for the distance moved from the previous state to the current one.

If an algorithm is too "hyperactive," it minimizes hitting costs but accumulates massive switching costs. If it is too "stagnant," it avoids movement but suffers high hitting costs as the environment shifts.

This tension creates a theoretical rift. As Lachlan L. H. Andrew, Adam Wierman, and colleagues proved in A Tale of Two Metrics, no algorithm can simultaneously achieve sublinear regret (performing as well as the best fixed action in hindsight) and a constant competitive ratio (performing within a constant factor of the best dynamic sequence of actions). Researchers must instead design algorithms that gracefully trade off between these two metrics.

Balancing as a Strategy

The most intuitive solution to this trade-off is cost-balancing. The idea is simple: move just enough so that the cost of the move is proportional to the hitting cost you are trying to avoid.

A landmark approach in this area is Online Balanced Descent (OBD), introduced by Niangjun Chen, Gautam Goel, and Adam Wierman in Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent. Instead of jumping directly to the minimum of the current cost function, OBD selects a point on a specific "level set" of the cost function where the distance traveled (switching cost) exactly balances the hitting cost.

This geometric approach allows the algorithm to remain "dimension-free." Even in massive-dimensional spaces, the performance depends on the properties of the functions (like their condition number) rather than the number of dimensions, as explored by Anupam Gupta and C. J. Argue in Dimension-Free Bounds for Chasing Convex Functions.

The Power of Laziness

While balancing is effective, sometimes the best strategy is to simply do nothing. This has led to the development of "lazy" or "sticky" algorithms.

In Consistent Online Optimization: Convex and Submodular, Andreas Krause and Silvio Lattanzi introduced SOLO (Sticky OnLine Optimization). SOLO uses a randomized process to decide when to update its state. By staying "stuck" to a decision for a period, the algorithm drastically reduces switching overhead while only sacrificing a small amount of regret.

Similarly, Uri Sherman and Tomer Koren explored Online Convex Optimization on a Switching Budget, proving that an agent can maintain near-optimal performance even when strictly limited in how many times they can change their mind.

Bridging Stochastic and Adversarial Worlds

Real-world environments are rarely purely predictable or purely chaotic. Recent work has focused on "best-of-both-worlds" guarantees. Neelkamal Bhuyan and Debankur Mukherjee developed Lazy Adaptive Interpolation (LAI) in Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization.

LAI works by adaptively interpolating between a strategy that assumes the environment is stable (stochastic) and one that assumes the environment is trying to trick it (adversarial). This allows the system to exploit patterns when they exist while remaining robust when the environment becomes volatile.

Applications Across Domains

The principles of smoothed optimization are being applied to bridge the gap between abstract theory and systems engineering:

  • Inventory Management: Koji Ichikawa treats inventory carryover as a switching cost, allowing SOCO algorithms to manage stock in non-stationary environments.
  • Caching: Abhishek Sinha uses switching regret to account for the cost of fetching new data into a cache, leading to more stable content delivery networks.
  • Portfolio Optimization: Algorithms like OGDM use momentum to naturally smooth rebalancing, accounting for transaction fees as switching costs to improve real-world returns.

By treating the "cost of change" as a first-class citizen, this research direction provides a framework for online agents that are not just smart, but also stable and efficient in physical systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_smoothed_online_convex_optimization_97fe601c,
  title = {Smoothed Online Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/smoothed-online-convex-optimization/rdr_97fe601c0ae6417bad4391d5a3b20acb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_smoothed_online_convex_optimization_97fe601c_v1,
  title = {Smoothed Online Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/smoothed-online-convex-optimization/rdr_97fe601c0ae6417bad4391d5a3b20acb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}