Kevin Kurian Thomas Vaidyan, Ahmet Alacaoglu, Michael P. Friedlander
原文摘要
Last-iterate convergence guarantees for stochastic gradient methods have attracted significant attention as practical implementations typically return the last iterate instead of an average of the iterates. In this paper, we study two approaches for analyzing the last-iterate convergence of proximal and projected stochastic gradient methods without bounded domain or bounded variance assumptions, where black-box variational inference serves as a running example. Under two related assumptions relaxing the bounded variance, we show near-optimal anytime rate $\widetilde{\mathcal{O}}(1/\sqrt{T})$ for the last iterate. Moreover, when the horizon $T$ is known, we remove the logarithmic factor and obtain the optimal order $\mathcal{O}(1/\sqrt{T})$, matching the order known under bounded variance or bounded domain assumptions.
Every linear program can tolerate small changes to its costs and still yield a solution of the original problem. The size of this tolerance measures how robust an optimal decision is to noise or numerical error, and how much regularization the problem can support. Classical sensitivity analysis can determine this tolerance only from an optimal solution. This paper provides a priori lower bounds on two measures of this tolerance -- the optimality gap and the $\infty$-norm stability radius -- for the $n$-by-$n$ linear assignment problem over the Birkhoff polytope. The bounds derive from a smoothed analysis, which adds Gaussian noise with standard deviation of at least $σ$ in every direction to an arbitrary base cost. At every fixed confidence level, uniformly over the base cost, both quantities are at least of order $σ/(n\sqrt{\log n})$. The radius bound is asymptotically sharp. Under isotropic noise, the worst case occurs when every assignment has equal cost, and in this case, a scaled stability radius converges in distribution to a standard exponential variable.