REVIEW 6 cited by
Parameter-free Stochastic Optimization of Variationally Coherent Functions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We design and analyze an algorithm for first-order stochastic optimization of a large class of functions on $\mathbb{R}^d$. In particular, we consider the \emph{variationally coherent} functions which can be convex or non-convex. The iterates of our algorithm on variationally coherent functions converge almost surely to the global minimizer $\boldsymbol{x}^*$. Additionally, the very same algorithm with the same hyperparameters, after $T$ iterations guarantees on convex functions that the expected suboptimality gap is bounded by $\widetilde{O}(\|\boldsymbol{x}^* - \boldsymbol{x}_0\| T^{-1/2+\epsilon})$ for any $\epsilon>0$. It is the first algorithm to achieve both these properties at the same time. Also, the rate for convex functions essentially matches the performance of parameter-free algorithms. Our algorithm is an instance of the Follow The Regularized Leader algorithm with the added twist of using \emph{rescaled gradients} and time-varying linearithmic regularizers.
Forward citations
Cited by 6 Pith papers
-
SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration
A single proof unifies convergence analyses of AdaGrad-Norm, AdaGrad, ASGO, and DASGO under Hölder smoothness, and shows AdaGrad/DASGO can be accelerated with Nesterov momentum.
-
A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation
Projection-free linear TD(0) achieves a robust O~(1/√T) convergence rate under Markovian noise; this is the first such guarantee without projections or curvature assumptions.
-
Parameter-Free and Group Conditional Online Conformal Prediction
POGO uses multi-portfolio wealth maximization to produce a single sequence of radii that achieve the strongest known finite-time group-conditional coverage without any learning-rate hyperparameter.
-
Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
Accelerated GRAAL is the first adaptive first-order method that proves near-optimal accelerated complexity for convex L-smooth and (L0,L1)-smooth functions with geometric stepsize growth.
-
Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization
Stochastic dual averaging converges on nonconvex smooth stochastic optimization at rate O(1/T + σ log T/√T), matching SGD.
-
Auto-exploration for online reinforcement learning
New parameter-free SPMD algorithms achieve the first algorithm-independent O(ε⁻²) sample complexity for online discounted RL under a mixing-optimal-policy assumption.
Discussion (0). Sign in to comment.