Guy Kornowski
@guykor.bsky.social
(Woodworth & Srebro arxiv.org/abs/1709.03594)
Lower Bound for Randomized First Order Convex Optimization
We provide an explicit construction and direct proof for the lower bound on the number of first order oracle accesses required for a randomized algorithm to minimize a convex Lipschitz function.
arxiv.org
June 13, 2025 at 2:50 PM
(Woodworth & Srebro arxiv.org/abs/1709.03594)
It is, in high dimensions.
Embed these “worst case” constructions using a random orthogonal map, and if the dimension is sufficiently high, then any distribution over initializations will likely be nearly orthogonal to all directions of interest, so the analysis works as if you initialize at 0.
Embed these “worst case” constructions using a random orthogonal map, and if the dimension is sufficiently high, then any distribution over initializations will likely be nearly orthogonal to all directions of interest, so the analysis works as if you initialize at 0.
June 13, 2025 at 2:49 PM
It is, in high dimensions.
Embed these “worst case” constructions using a random orthogonal map, and if the dimension is sufficiently high, then any distribution over initializations will likely be nearly orthogonal to all directions of interest, so the analysis works as if you initialize at 0.
Embed these “worst case” constructions using a random orthogonal map, and if the dimension is sufficiently high, then any distribution over initializations will likely be nearly orthogonal to all directions of interest, so the analysis works as if you initialize at 0.
Awesome! Congrats!!
btw according to the cash prize proposed at COLT, we now owe Zihan (1.03-1)*50=1.5$ 😂
btw according to the cash prize proposed at COLT, we now owe Zihan (1.03-1)*50=1.5$ 😂
November 27, 2024 at 7:53 PM
Awesome! Congrats!!
btw according to the cash prize proposed at COLT, we now owe Zihan (1.03-1)*50=1.5$ 😂
btw according to the cash prize proposed at COLT, we now owe Zihan (1.03-1)*50=1.5$ 😂