video thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization

Published on Feb 4, 20253629 Views

We give a novel algorithm for stochastic strongly-convex optimization in the gradient oracle model which returns an O(1/T)-approximate solution after T gradient updates. This rate of convergence is

Related categories

Presentation

Beyond the Regret Minimization Barrier00:00
Soft-Margin SVM - 110:23:07
Soft-Margin SVM - 210:39:34
Solving the SVM problem35:41:10
Optimization via Regret Minimization68:46:13
Stochastic Gradient Descent87:12:33
Natural Questions - 1114:11:10
Natural Questions - 2133:38:47
Epoch-GD146:27:16
Analysis Sketch - 1161:32:38
Analysis Sketch - 2190:48:52
Analysis Sketch - 3199:44:58
Lower Bound Intuition214:16:18
Formalizing intuition243:25:56