\section{Discussion and Open Problems}


In this work we provide sharp upper and lower bounds on \stabname for the (stochastic) subgradient method in stochastic nonsmooth convex optimization. Our lower bounds show inherent limitations of stability bounds compared to the smooth convex case,

however we can still derive optimal population risk bounds by reducing the step size and running the algorithms for longer number of iterations. We provide applications of this idea for differentially-private noisy SGD, and for two versions of SGD (sampling-with-replacement and fixed-permutation SGD).


The first open problem regards lower bounds that are robust to general forms of algorithmic randomization. Unfortunately, the methods presented here are not robust in this respect, since random initialization would prevent the trajectories reaching the region of highly nonsmooth behavior of the objective (or doing it in such a way that it does not increase \UHS). One may try to strengthen the lower bound by using a random rotation of the objective; however, this leads to an uninformative lower bound. Finding distributional constructions for lower bounds against randomization is a very interesting future direction.


Our privacy application provides optimal risk for an algorithm that runs for $n^2$ steps, which is impractical for large datasets. Other algorithms, e.g.~in \citep{FKT19}, run into similar limitations. Proving that quadratic running time is necessary for general nonsmooth DP-SCO is a very interesting open problem 
that can be formalized in terms of the oracle complexity of stochastic convex optimization \citep{nemirovsky1983problem} under stability and/or privacy constraints.
{"config": "arxiv", "file": "2006.06914/sec_Discussion.tex"}