Summary
The authors suggest incremental updates of $\mathbf{x}$ for finding the minimum of strongly-convex function $f$ that guarantee decreasing $f(\mathbf{x}_{t})-f(\mathbf{x}_\ast)$ based on only 1st-order gradient information.
Their idea is in each step,
- choose a candidate matrix $\mathbf{P}_t$ based on set $\mathcal{S}_t$, and
- check the condition (4), that guarantee sufficient decrease of the $f$, and
- if the condition is satisfied:
- apply update $\mathbf{x}_{t+1} = \mathbf{x}_t - \mathbf{P}_t\nabla f(\mathbf{x}_t)$
- $\mathcal{S}_{t+1} = \mathcal{S}_t$
- else
- $\mathbf{x}_{t+1} = \mathbf{x}_t$
- update $\mathcal{S}_{t+1} = \text{cut}(\mathcal{S}_t, \mathbf{x}_t, \mathbf{P}_t)$
They provide proofs for
- approaching the optimal in Proposition 3.2
- how to choose candidate and cut algorithm in Theorem 5.3, and its maximum number of calls.
They conduct some simple experiments in Section 6, and show the proposed algorithm's efficiency.
Strengths
originality
- considering backtracking using preconditioned matrix $\mathbf{P}_t$ would be novel idea. But I'm not an expert of this field, and not so sure on the originality.
quality
- The proposed algorithm is supported by some proofs, and it shows good empirical results.
clarity
- Basically, the manuscript is readable.
significance
- The proposed algorithm seems be better than other baselines except for Diag. Hessian+LS, which uses information of 2nd order derivatives, i.e. Hessian, even the proposed algorithm uses 1st-order derivatives of $f$. It would be significant.
Weaknesses
- The manuscript contains some typos.
- I have a concern on Figure 5. The horizontal axis shows number of f/grad evals, but I guess the number of CUT calls should be also taken into account.
Questions
- In line 129, the representation $\nabla^2 f$ appears. Does it mean Hessian? or Laplacian?
- Between line 197 and 198, the final inequality may be not $\overset{(3)}{\leq}$ but $\overset{(4)}{\leq}$ ?
- In the caption of Figure 3(b), $\mathcal{H}\_{>}(\mathbf{u})$ should be replaced by $\mathcal{H}_>(\mathbf{v})$ ?
- In Figure 5, do the authors take the number of CUT into account?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.
Limitations
They address the limitation, their method is only supported for convex deterministic setting.