本次美国代写是一个优化数学相关的assignment

1 Adagrad: The simple case (40 points)

Show that for function f(x) = f(x1, x2) = ax2 1 + x2 2 for x ∈ R2 and a > 0, if we use
Adagrad to optimize f with learning rate η = 1, derive the ratio (as a function of a) of the
pre-conditioner:

given a fixed initial point x0 = (c, c) where c ̸= 0.
Explain why when a ≫ 1, Adagrad is better than gradient descent

2 Convex optimization but the minimizer is at infinity

Li Hua claims that he has spotted a huge bug in the convergence proof of gradient descent
convex functions in the lecture. He claims that the proof can not be applied to logistic
regression, where the optimizer is at infinity. Hence gradient descent might take forever to
converge.

Now, you want to show him some math:

1. (5 points) For logistic function h(x) = log(1 + ex) as a function h : R → R, show that
the minimizer of h is indeed at infinity.
Solution

2. (5 points) However, show that for every ϵ > 0, there is an x such that |x| = O(log(1/ϵ))
with h(x) ≤ ϵ.
Solution

3. (30 points) Now, for general function f : Rd → R, suppose f is L-smooth convex
function, and for an ϵ > 0, there is an x with ∥x∥2 ≤ R such that f(x) ≤ ϵ.
Now, show that starting from x0 = 0, gradient descent update with η ≤ L1 :

converges to f(xT ) ≤ 2ϵ in T ≤ poly(R, L, 1/η, 1/ϵ) many iterations. (Hint: Apply
Mirror Descent Lemma on x)

3 Random Query for Convex Optimization (20 points)

This problem studies the efficiency of the following optimization algorithm for a d-dimensional
convex function f:

1. Fix a probability distribution D, which does not depend on f. You don’t know f, but
let’s say you somehow know that the optimum x∗ has nonzero probability density over
D.

2. Sample x1, x2, …xN ∼ D

3. Return xm = argminx1,…xN f(x)

Let D be the uniform distribution over the cube Q = {x | −1 ≤ xi ≤ 1} = {x | ∥x∥∞ ≤ 1}.
Show that for every fixed x0 ∈ Rd, if we sample N = dO(1) points x1, x2, · · · , xN uniformly
from Q, then with probability lower bounded by 1−e−Ω(d), the following holds for all i ∈ [N]:


EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue


EasyDue™是一个服务全球中国留学生的专业代写公司
专注提供稳定可靠的北美、澳洲、英国代写服务
专注提供CS、统计、金融、经济、数学等覆盖100+专业的作业代写服务