More Like this

1. Non-Equilibrium Learning in Stochastic Games

   https://doi.org/10.23919/ACC55779.2023.10156061  

   Vamvoudakis, Kyriakos G. (May 2023, 2023 American Control Conference (ACC))
2. Towards a non-stochastic Information Theory

   Rangi, A.; Franceschetti, M. (January 2019, Proceedings of the IEEE International Symposium on Information Theory)
3. Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

   Cutkosky, Ashok; Mehta, Harsh; Orabona, Francesco (July 2023, International Conference on Machine Learning)

   We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a (δ,ϵ)-stationary point from O(ϵ^(-4),δ^(-1)) stochastic gradient queries to O(ϵ^(-3),δ^(-1)), which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of O(ϵ^(-1.5),δ^(-0.5)). Our techniques also recover all optimal or best-known results for finding ϵ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings. 

   more » « less
4. Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

   Cutkosky, Ashok; Mehta, Harsh; Orabona, Francesco (July 2023, Proceedings of Machine Learning Research)
5. Lower bounds for non-convex stochastic optimization

   https://doi.org/10.1007/s10107-022-01822-7  

   Arjevani, Yossi; Carmon, Yair; Duchi, John C.; Foster, Dylan J.; Srebro, Nathan; Woodworth, Blake (January 2022, Mathematical Programming)