Summary
The paper aims to propose robust methods that achieves optimal rates in both
strongly-convex or convex and interpolation or non-interpolation settings.
Specifically, they propose AdaSPS, a modification of $SPS_{max}$ with
an AdaGrad-like denominator (replacing the gradient norms with function values) in
the stepsize, and AdaSLS, a combination of AdaGrad-Norm and line search
methods.
- For convex functions,
AdaSPS and AdaSLS achieve a $O(1/\epsilon^2)$ convergence rate assuming individual
smoothness and bounded domain.
When interpolation is assumed, both methods get rid of the bounded domain
assumption (but additionally require individual convexity and AdaSPS requires
the exact minimal function values) and achieve a $O(1/\epsilon)$ convergence
rate.
- For strongly-convex functions, individual strong-convexity and smoothness
are required. AdaSPS and AdaSLS achieve a $O(1/\epsilon^2)$ rate without interpolation.
With interpolation, they achieve linear convergence rates.
- Furthermore, the author combine the proposed methods with variance reduction techniques,
and improves the rate for strongly-convex and convex settings to $O(1/\epsilon)$
without interpolation.
The proposed methods are also evaluated by numerical experiments.
Strengths
1. The paper has clear logic and is well-written, making it easy to follow.
2. In all considered settings (convex/strongly-convex and interpolation/non-interpolation),
the proposed AdaSPS and AdaSLS match the rate of well-tuned SGD in all settings
except for the case when we have strongly-convexity and non-interpolation.
Importantly, AdaSLS achieves this without requiring knowledge of any problem-dependent parameters.
3. The intuition behind the proposed variance reduction framework is interesting,
and could potentially motivate new algorithms.
Weaknesses
1. The related work on interpolation is somehow insufficient. One very
relevant work [1] is missing. Importantly, [1] also proposed combining AdaGrad
with line search, similar to AdaSLS, and provided theoretical guarantees in convex setting.
The difference is that AdaSLS uses a minimum operator for all past stepsizes.
Usually, non-diminishing stepsizes work better in practice, so it would also
make sense to compare them in the experiments.
2. I cannot find any theorems or proofs that show the results of AdaSVRPS/AdaSVRLS
in strongly-convex and convex settings with interpolation,
as listed in Table 1. This is the reason why I give
a 1 in the soundness assessment.
3. Without variance reduction, the paper claims that their algorithms match the convergence rate of SGD in
many settings, however, the assumptions are different. Individual smoothness
and individual (strongly-)convexity are additionally assumed in many theorems in this work,
making it hard to compare them to classical results of SGD (also AdaGrad-Norm).
I wonder if there are lower bounds for the individual (strongly-)convexity
settings. With variance reduction, Theorem 8 also requires individual convexity,
while the compared AdaSVRG does not.
Minor issues:
4. Table 1 could contain results of AdaSVRG and SARAH for a more comprehensive comparison
of adaptive variance reduction methods. For the interpolation strongly-convex setting
where we have linear convergence, the dependence on $\kappa$, the condition number,
is also important.
5. In Theorem 5, $T_p$ and $T_l$ are not defined. According to the results in
the appendix, they depends on $\epsilon$ (of order $1/\log(1+\epsilon)$, or nearly $1/\epsilon$,
if $c_p$ is chosen poorly).
6. Usually the scalar version of AdaGrad is referred as AdaGrad-Norm. Calling
it AdaNorm is not common, especially when there are other algorithms called AdaNorm.
**References:**
[1] Vaswani, Sharan, et al. "Adaptive gradient methods converge faster with over-parameterization (but you should do a line-search)." arXiv preprint arXiv:2006.06835 (2020).
Questions
I would appreciate it if the author could address the concerns listed
as weaknesses 1-3.
Additionally, I wonder if we could change the added function value
gaps (under the square root) in the denominator of AdaSPS stepsize to the
squared norm of gradients (like AdaGrad) and obtain a similar result. Is the use
of function value gap necessary?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
I think the main limitation is the sub-optimality in the non-interpolation
strongly-convex setting, which is also a known hard problem for adaptive methods.
This is metioned in the Conclusion and future work section of the paper.