- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies first-order methods for composite regression problems of the form where is a proper closed convex function whose proximal mapping can be efficiently evaluated. In particular, or , the loss has a Holder-continuous gradient. The paper exploits the problem structure to obtain a better complexity bound than the one for general Holder-smooth convex problems. More precisely, the authors analyze a Huber-type smoothing of the loss and establish an optimal trade-off between uniform approximation error and smoothness among scalar smooth lower approximations. Combining this smoothing with an accelerated proximal gradient method gives an matrix-vector product complexity for finding an -optimal solution, with explicit dependence on the dimension, matrix norm, and initial distance to the solution set. The authors also establish a matching lower bound for deterministic algorithms in the matrix-vector oracle model, when the dimensions are sufficiently large relative to the query budget. These upper and lower bounds characterize the optimal complexity of this structured problem class within the stated oracle model. The paper further develops variable-smoothing and backtracking variants. Numerical experiments on synthetic and real-data problems, including regularized regression and box-constrained optimization, compare the proposed methods with existing first-order methods.
Critical strengths
-
I think the matching upper and lower complexity bounds are the strongest contribution of the paper. The proposed method achieves the matrix-vector product complexity of , improving the dependence on accuracy over generic Holder-smooth methods for . The matching lower bound covers arbitrary deterministic algorithms under the stated oracle model, subject to the dimension requirements. Moreover, the bounds match in their dependence with respect to multiple problem parameters, which makes the optimality result particularly meaningful (Theorems 3.2 and 3.4).
-
The exact characterization of the approximation-smoothness trade-off is another valuable contribution. Theorem 2.4 shows that the Huber-type smoothing attains the smallest uniform approximation error among scalar smooth lower approximations with a prescribed gradient Lipschitz constant. The comparison even allows nonconvex approximations. This gives a clear mathematical justification for the smoothing construction and a precise basis for balancing approximation error against optimization error.
Critical weaknesses
My main concern is that the theoretical guarantees do not fully cover some practical variants used in the experiments. The variable-smoothing analysis assumes a uniform bound on the auxiliary iterates, which is not guaranteed by using an initial-distance bound or a reference-solution norm as a proxy. The experimental backtracking rule also omits the safeguard required by Proposition B.3. These choices are clearly acknowledged and do not undermine the main results, but they leave a gap between the theory and the empirical performance.
Questions for authors
-
Several experiments use reference-distance proxies to determine the smoothing scale. How sensitive are the reported results to these parameter choices, and do the main comparisons persist with choices that do not require a high-accuracy reference solution? The OLS-based prescription addresses this issue for unregularized problems, but the practical choice for the regularized problems remains less clear. A small sensitivity study on representative instances would help assess how much the performance depends on the reference-based tuning.
-
Could the authors compare the experimental backtracking rule with the version retaining the safeguard required by Proposition B.3? The existing box-constrained example would be a suitable setting, since the iterate bound is available there. Using the same smoothing schedule and cost-accounting convention would allow the comparison to isolate the effect of the safeguard and show whether retaining the theoretical guarantee has a substantial practical cost.
-
The cost of LSQR initialization is already included in the reported budget, which is appropriate. However, several targets are reached during initialization itself (Table 6). It would be useful to compare the OLS-initialized variant with UFGM and GAGD+ starting from the same least-squares point, with the initialization cost charged to every method. Does the observed advantage persist under this comparison? This would clarify how much of the improvement comes from initialization and how much comes from the subsequent smoothing iterations.
3 comments
Response to Reviewer ernp (Part 2 of 2, Q1 (cont.) Q3)
Q1.(cont.)
At higher accuracy, results remain mixed: on UCI, BT-Safe is cheaper than UFGM on 8 of 14 jointly attained problems at , and none of the tested methods reaches on the additional regularized problems. We will add these results to illustrate practical scale selection.
Q2. Compare the experimental backtracking rule with the version retaining the safeguard of Proposition B.3, on the box-constrained instance.
Thank you for this suggestion. On the box instance, the safeguard reduces the products needed to reach and by about 19% and 24%. Only the safeguard changed; the schedule, starting point and cost accounting remained fixed. Rejected trials cover the full-budget runs.
| Box instance, budget 20,000 products | Products to | Products to | Iterations to | Rejected trials |
|---|---|---|---|---|
| Variable smoothing, no line search | 44 | 688 | 344 | 0 |
| Backtracking without safeguard (as in the paper) | 72 | 1,371 | 343 | 5,000 in 5,000 iterations |
| Backtracking with safeguard | 58 | 1,036 | 343 | 11 in 6,663 iterations |
All three methods need essentially the same number of iterations to reach ; the safeguard saves products by reducing rejected trials. Plain variable smoothing remains the fastest on this instance. The box ensures bounded iterates, so the safeguarded version satisfies Proposition B.3.
Reruns with the paper's reference-distance scales. On the 18 real-data problems, at the safeguard lowers the cost on 10, leaves it unchanged on one, and increases it by at most 10% on 3 and by more than 10% on 4. At , it lowers the cost on all 15 jointly attained problems and reaches one additional problem; neither version reaches the remaining two. On E2006, it lowers the final gap on 5 of 8 problems and increases it on three (by about 1.2% on one and by more than 10% on two). The main aggregate real-data comparisons are preserved at both targets; on E2006, V or safeguarded backtracking has the smallest final gap in 7 of 8 settings, and GAGD+ leads in the remaining one (log1p, ). We will add these results and consider making the safeguard the default in all experiments.
Q3. Does the advantage persist when UFGM and GAGD+ use the same least-squares initialization, with its cost charged to every method?
Thank you for suggesting this comparison. OLS initialization also substantially benefits the baselines, particularly UFGM. With a shared OLS start, HS-APG-OLS is cheaper than GAGD+ but more expensive than UFGM on most jointly attained problems. With safeguarded backtracking (Q2), our costs are comparable to UFGM at on jointly attained problems.
All methods use the same LSQR starting point on the 18 real-data problems, including initialization in each method's 60,000 matrix–vector product budget. The table uses our original smoothing scale. Entries count our lower-cost results among jointly attained problems.
| Our method | Baseline, also OLS-initialized | ||
|---|---|---|---|
| HS-APG-OLS | UFGM | 5 of 13 | 6 of 16 |
| HS-APG-OLS | GAGD+ | 9 of 13 | 9 of 15 |
| OLS + safeguarded BT | UFGM | 4 of 13 | 8 of 15 |
| OLS + safeguarded BT | GAGD+ | 7 of 13 | 8 of 15 |
At , four problems solved during initialization are excluded; safeguarded BT additionally reaches one problem missed by both baselines. At , HS-APG-OLS reaches one problem missed by GAGD+, while UFGM reaches one missed by safeguarded BT. The median paired cost ratio of safeguarded BT to UFGM is 0.99 at .
We will add these comparisons and revise our empirical claims to present OLS as a warm start for all methods.
Additional observation on the smoothing scale. Under the original rule, all initial residuals lie in the quadratic region, so the first smoothed gradient vanishes at an exact OLS solution. This motivates testing smaller initial scales.
After an exploratory study on nine problems, we evaluated safeguarded BT with a fixed multiplier of on all 18 problems, including those nine, without per-problem scale selection. Against the per-problem best result among UFGM and GAGD+ with either zero or OLS initialization, counting initialization costs, it is cheaper on 14 problems and more expensive on two at ; neither side reaches the target on the remaining two. We will report this exploratory extension alongside the original-scale comparison, including other tested scales and their evaluation sets.
Thank you again for the thoughtful feedback. We welcome any further questions.
Thank you very much for the additional theoretical and numerical results. My comments are well addressed.
Response to Reviewer ernp (Part 1 of 2, weakness & Q1)
We sincerely thank Reviewer ernp for the careful and constructive review. We have completed the suggested comparisons.
Weakness. The guarantees do not fully cover the practical variants used in the experiments.
We address both gaps below.
(a) Bounded iterates. (Reviewers NGJm and 3Yo2 raised the same point.)
Thank you for this helpful suggestion. The bounded-iterate assumption is not needed for a convergence guarantee. For example, for 1≤p<2, variable smoothing without line search, using the simple schedule ρt=ρˉ/(t+1) with any ρˉ>0, satisfies, for any minimizer u⋆,
\frac{2\\|A\\|^2\bar\rho^{p-2}\\|u_0-u^\star\\|^2+2c_pm\bar\rho^{p}\displaystyle\sum_{t=1}^{T}\frac{1}{t+1}}{(T+1)^p}, c_p=\frac{2-p}{2p}.\tag{i}$$ This guarantee requires neither uniformly bounded auxiliary iterates nor prior knowledge of the initial distance, which appears only in the bound. Every positive scale is valid; using a proxy affects only the constant. In particular, (i) covers the least-squares-initialized variant of Appendix B.4 ($u_0=u_{\mathrm{OLS}}$, $\bar\rho=2\\|Au_{\mathrm{OLS}}-b\\|_\infty>0$) without the boundedness condition stated there. We will add a remark after Theorem 3.3 and a proof in the appendix. We also note that it appears possible to avoid the accumulation in the summation term and recover an $O(T^{-p})$ rate through a stagewise smoothing strategy, without introducing either requirement. We plan to develop this extension and provide a detailed analysis in an extended version. **(b) The safeguard of Proposition B.3.** The safeguard retains the guarantee and reduces cost on the box instance; see Q2. **Q1. How sensitive are the results to the reference-based scales, do the main comparisons persist without a high-accuracy reference solution, and what is a practical choice for regularized problems?** Thank you for this question. Sensitivity depends on $p$: at $p=1.9$ the results change little over the tested range; at $p=1.1$, underestimating the scale is costly for variable smoothing, and safeguarded backtracking reduces this sensitivity. Large overestimates can still be costly. Below, V denotes variable smoothing and BT-Safe its safeguarded backtracking variant. **Sensitivity.** We scaled the paper's reference distance $R_{\mathrm{ref}}$ by $c$: $$\bar\rho=2\sqrt{\frac{2-p}{(p+2)m}}\\|A\\|cR_{\mathrm{ref}}, \rho_t=\frac{\bar\rho}{t+1},$$ with all other settings and budgets unchanged; $c=1$ is the paper's choice. Entries are median ratios to the same method at $c=1$; values below 1 indicate improvement. Bold marks observed median ratios at most 2. On 10 UCI problems (five datasets, $p\in\\{1.1,1.9\\}$) the ratio compares the products needed to reach the target; on the 8 E2006 problems ($p=1.5$), where no method reaches the target, it compares final gaps. Entries marked ≥ are lower bounds, counting unsuccessful runs at their budget-implied cost. | UCI exponent | Target | Method | c = 0.1 | c = 0.3 | c = 3 | c = 10 | |---|---|---|---:|---:|---:|---:| | 1.1 | 10⁻⁴ | V | 6.58 | 2.68 | **0.47** | **0.40** | | 1.1 | 10⁻⁴ | BT-Safe | **1.14** | **1.06** | **1.23** | **1.84** | | 1.1 | 10⁻⁶ | V | ≥3.65 | ≥1.97 | **0.56** | ≥1.14 | | 1.1 | 10⁻⁶ | BT-Safe | **1.02** | **0.84** | 2.74 | ≥8.73 | | 1.9 | 10⁻⁴ | V | **1.13** | **1.07** | **0.94** | **0.89** | | 1.9 | 10⁻⁴ | BT-Safe | **1.12** | **1.06** | **0.95** | **0.89** | | 1.9 | 10⁻⁶ | V | **1.13** | **1.07** | **0.94** | **0.89** | | 1.9 | 10⁻⁶ | BT-Safe | **1.13** | **1.08** | **0.95** | **0.89** | | E2006, p = 1.5 | c = 0.01 | c = 0.1 | c = 0.3 | c = 3 | c = 10 | c = 100 | |---|---:|---:|---:|---:|---:|---:| | V | 5.28 | 3.57 | **1.70** | **0.46** | **0.40** | 11.69 | | BT-Safe | **1.25** | **1.28** | **1.11** | **0.71** | **1.10** | 25.53 | At $p=1.1$ and $10^{-6}$, V misses the target on two of five problems at $c=0.1$ and on one at each of $c=0.3$ and $c=10$; BT-Safe misses two at $c=10$. All other UCI runs reach their targets. **A simple scale choice.** We also tested $\bar\rho=2\\|Au_0-b\\|_\infty$ for a nonzero initial residual, keeping the same starting point and variable-smoothing schedule $\rho_t=\bar\rho/(t+1)$. This residual-based choice also applies to regularized problems and needs no preliminary least-squares solve. - **UCI (18 problems).** At $10^{-4}$, BT-Safe is cheaper than UFGM on 14 of 17 jointly attained problems and than GAGD+ on 13 of 16; it also reaches one and two additional problems, respectively. - **E2006.** V or BT-Safe has the smallest terminal gap in 7 of the 8 settings; GAGD+ leads in the remaining one (TF-IDF, $\lambda/\lambda_{\max}=0.1$). - **Additional $\ell_1$-regularized problems (16 problems, 30,000 products per run).** At $10^{-4}$, V and BT-Safe reach 6 and 7 problems, versus 4 for UFGM and 5 for GAGD+, and are cheaper on every jointly attained problem with these baselines.