def computeEmbeddingWithGD(X,S,max_iters=0,max_norm=0,epsilon=0.01,c1=0.0001,rho=0.5,verbose=False):
    m = len(S)

    n,d = X.shape

    if max_iters==0:
        max_iters = 100

    if max_norm==0:
        max_norm = 10.*d

    # check losses
    if verbose:
        emp_loss,hinge_loss = getLoss(X,S)
        print "iter=%d,   emp_loss=%f,   hinge_loss=%f,   a=%f" % (0,emp_loss,hinge_loss,float('nan'))

    alpha = .5
    t = 0
    emp_loss_0 = float('inf')
    hinge_loss_0 = float('inf')
    rel_max_grad = float('inf')
    while t < max_iters:
        t+=1

        # get gradient and stopping-time statistics
        G,avg_grad_row_norm_sq,max_grad_row_norm_sq,avg_row_norm_sq = getGradient(X,S)
        rel_max_grad = sqrt( max_grad_row_norm_sq / avg_row_norm_sq )
        rel_avg_grad = sqrt( avg_grad_row_norm_sq / avg_row_norm_sq )
        if rel_max_grad < epsilon:
            break

        # perform backtracking line search
        alpha = 2*alpha
        emp_loss_0,hinge_loss_0 = getLoss(X,S)
        norm_grad_sq_0 = avg_grad_row_norm_sq*n
        emp_loss_k,hinge_loss_k = getLoss(X-alpha*G,S)
        inner_t = 0
        while hinge_loss_k > hinge_loss_0 - c1*alpha*norm_grad_sq_0:
            alpha = alpha*rho
            emp_loss_k,hinge_loss_k = getLoss(X-alpha*G,S)
            inner_t += 1
        X = X-alpha*G

        # project back onto ball such that norm(X[i])<=max_norm
        for i in range(n):
            norm_i = norm(X[i])
            if norm_i>max_norm:
                X[i] = X[i] * (max_norm / norm_i)

        # check losses
        if verbose:
            print "hinge iter=%d,   emp_loss=%f,   hinge_loss=%f,   rel_avg_grad=%f,   rel_max_grad=%f,   a=%f,   i_t=%d" % (t,emp_loss_k,hinge_loss_k,rel_avg_grad,rel_max_grad,alpha,inner_t)

    return X,emp_loss_0,hinge_loss_0,rel_max_grad
Performs gradient descent with geometric amarijo line search (with parameter c1)
dataset/ETHPy150Open nextml/NEXT/next/apps/PoolBasedTripletMDS/algs/RandomSampling/utilsMDS.py/computeEmbeddingWithGD