Proves it is impossible to achieve optimal last-iterate rates for GD and SGD without knowing the horizon T in advance, incurring an unavoidable poly-log factor penalty even in the deterministic case.
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
abstract
In this note, we present a new averaging technique for the projected stochastic subgradient method. By using a weighted average with a weight of t+1 for each iterate w_t at iteration t, we obtain the convergence rate of O(1/t) with both an easy proof and an easy implementation. The new scheme is compared empirically to existing techniques, with similar performance behavior.
verdicts
UNVERDICTED 6representative citing papers
Price's gradient estimator enables black-box VI to achieve the same state-of-the-art iteration complexity as Wasserstein VI, with experiments confirming it as the main performance driver.
Mini-batch SGD optimizes a different objective than full partial likelihood in Cox models, but the resulting mb-MPLE is still consistent with optimal rates for neural nets and asymptotic normality for linear models.
Proposes Factor-Augmented SGD that runs on streaming high-dimensional data and supplies the first convergence analysis explicitly accounting for latent-factor estimation error.
Proposes federated adaptive optimizers (FedAdagrad, FedAdam, FedYogi) with convergence analysis for non-convex objectives under data heterogeneity and reports empirical gains over FedAvg.
Robust learning problems are formulated as quasar-convex optimization, and HiPPA is proposed as an inexact high-order proximal method with global and superlinear convergence guarantees.
citing papers explorer
-
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Proves it is impossible to achieve optimal last-iterate rates for GD and SGD without knowing the horizon T in advance, incurring an unavoidable poly-log factor penalty even in the deterministic case.
-
Stochastic Gradient Variational Inference with Price's Gradient Estimator from Bures-Wasserstein to Parameter Space
Price's gradient estimator enables black-box VI to achieve the same state-of-the-art iteration complexity as Wasserstein VI, with experiments confirming it as the main performance driver.
-
Mini-batch Estimation for Deep Cox Models: Statistical Foundations and Practical Guidance
Mini-batch SGD optimizes a different objective than full partial likelihood in Cox models, but the resulting mb-MPLE is still consistent with optimal rates for neural nets and asymptotic normality for linear models.
-
Factor Augmented High-Dimensional SGD
Proposes Factor-Augmented SGD that runs on streaming high-dimensional data and supplies the first convergence analysis explicitly accounting for latent-factor estimation error.
-
Adaptive Federated Optimization
Proposes federated adaptive optimizers (FedAdagrad, FedAdam, FedYogi) with convergence analysis for non-convex objectives under data heterogeneity and reports empirical gains over FedAvg.
-
Robust Learning Meets Quasar-Convex Optimization: Inexact High-Order Proximal-Point Methods
Robust learning problems are formulated as quasar-convex optimization, and HiPPA is proposed as an inexact high-order proximal method with global and superlinear convergence guarantees.