Learning piecewise Lipschitz functions in changing environments

Dravyansh Sharma, Maria-Florina Balcan, Travis DickAISTATS 2020 · OpenReview

Abstract

Optimization in the presence of sharp (non-Lipschitz), unpredictable changes is a challenging and largely unexplored problem. This work introduces a theoretical framework and practical algorithms for online optimization of non-convex, discontinuous functions in non-stationary environments. By leveraging the property of "dispersion," we provide regret bounds for tracking the best performing parameters over time, demonstrating significant performance gains in online clustering tasks.

Introduction: The Challenge of Discontinuity and Non-Stationarity

In online optimization, a learner repeatedly selects a parameter and receives a reward based on a utility function. Traditional research often assumes static environments and "nice" functions (convex or Lipschitz). However, real-world applications like hyperparameter tuning or ad ranking frequently involve sharp discontinuities—where a tiny parameter change causes a massive jump in utility—and shifting environments where the optimal choice changes over time.

This paper addresses the challenge of minimizing shifting regret, comparing performance against an optimal sequence of choices that can change up to $s$ times, specifically for piecewise Lipschitz functions.

Handling Discontinuity via Dispersion

To manage non-convexity and discontinuities, the authors employ the dispersion condition. A sequence of functions is considered well-dispersed if their discontinuities are not overly concentrated in any single small region. This property acts as a surrogate for convexity, allowing the algorithm to "smooth out" the impact of sharp changes and providing a mathematical guarantee that nearby points yield similar average rewards over time.

Tracking Moving Targets: The Fixed Share Approach

The proposed solution centers on a family of algorithms based on the "Fixed Share" paradigm. Unlike standard exponential weight algorithms that converge on a single best performer, these versions maintain a mixture of beliefs.

  • Fixed Share Exponential Forecaster (Fixed Share EF): This algorithm performs standard exponential updates but adds a constant "additive boost" to all points in the decision space. This exploration mechanism ensures the algorithm never completely ignores any region, allowing it to pivot quickly when the environment shifts.
  • Efficient Implementation: To handle the continuous decision space, the authors developed an approximate implementation that uses a mixture of distributions to sample new parameters in polynomial time.
Comparison of average regret in a shifting environment. The tracking algorithm (red) successfully adapts to environment changes, whereas the static baseline (blue) fails to recover.

Experimental Evaluation

The algorithms were evaluated on online clustering benchmarks, including MNIST and Omniglot. Environment shifts were simulated by changing the distribution of classes (e.g., switching from even to odd digits) during the task.

Performance benchmarks on MNIST and Omniglot datasets. The proposed algorithms consistently achieve lower average regret by adapting to distribution shifts.

The results demonstrate that the Fixed Share EF and Generalized Share EF algorithms significantly outperform standard baselines. In shifting environments, the proposed methods reduced regret by 15-40%. While standard learners often "get stuck" on parameters that were optimal in the past, the new algorithms adapt rapidly to new data distributions.

Conclusion

This work provides a robust framework for online optimization in complex, non-stationary settings. By combining the dispersion condition with a fixed-share exploration strategy, the authors achieve near-optimal regret bounds and superior empirical performance on real-world datasets. Future work remains to extend these results to bandit settings where only partial feedback is available.

Summary updated

Abstract

Optimization in the presence of sharp (non-Lipschitz), unpredictable (w.r.t. time and amount) changes is a challenging and largely unexplored problem of great significance. We consider the class of...
BibTeX
@inproceedings{sharma2020learning,
  author = {Dravyansh Sharma and Maria-Florina Balcan and Travis Dick},
  title = {{Learning piecewise Lipschitz functions in changing environments}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=JdIMhuz9wN},
}
Figure