acceptodds
Under review as a conference paper at ICLR 2027

Optimal First-Order Methods for a Class of Structured H\"older-Smooth Problems

Abstract

Convex optimization with H\"older-continuous gradients has attracted considerable attention as a framework bridging smooth and nonsmooth optimization. For this class, Nesterov's universal fast gradient method attains the optimal black-box complexity, and we study whether exploiting further problem structure can further improve this bound. In this paper, we study an important class of H\"older-smooth problems, namely regularized regression with , whose loss has a -H\"older-continuous gradient and for which the universal method requires iterations. Exploiting the problem structure, we characterize a family of smooth approximations based on -Huber smoothing and prove that it attains the exact optimal one-sided approximation–smoothness trade-off. Combined with accelerated proximal gradients, the smoothing approach attains an -optimal solution in matrix–vector products, which significantly improves the complexity guarantee for . We show that this bound is optimal by providing a matching lower bound. Numerical experiments on synthetic and real data demonstrate the practical performance of the proposed methods.

Primary area:
optimization
Keywords:
first-order methods, oracle complexity, lower bounds, accelerated gradient methods, smoothing methods

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ernpOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies first-order methods for composite ℓp\ell_p regression problems of the form min⁡u∈Rn 1p∥Au−b∥pp+ω(u),1≤p<2,\min_{u\in\mathbb{R}^n}\ \frac{1}{p}\|Au-b\|_p^p+\omega(u), \qquad 1\leq p<2, where ω\omega is a proper closed convex function whose proximal mapping can be efficiently evaluated. In particular, or 1<p<21<p<2, 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 O(ε−1/p)O(\varepsilon^{-1/p}) matrix-vector product complexity for finding an ε\varepsilon-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
  1. 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 O(ε−1/p)O(\varepsilon^{-1/p}), improving the dependence on accuracy over generic Holder-smooth methods for 1<p<21<p<2. 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).

  2. 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
  1. 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.

  2. 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.

  3. 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
AuthorsOpenReview ↗

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<21\le p<2, variable smoothing without line search, using the simple schedule ρt=ρˉ/(t+1)\rho_t=\bar\rho/(t+1) with any ρˉ>0\bar\rho>0, satisfies, for any minimizer u⋆u^\star,

\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.
AuthorsOpenReview ↗

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 10−610^{-6}, and none of the tested methods reaches 10−610^{-6} 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 10−410^{-4} and 10−610^{-6} 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 productsProducts to 10−410^{-4}Products to 10−610^{-6}Iterations to 10−610^{-6}Rejected trials
Variable smoothing, no line search446883440
Backtracking without safeguard (as in the paper)721,3713435,000 in 5,000 iterations
Backtracking with safeguard581,03634311 in 6,663 iterations

All three methods need essentially the same number of iterations to reach 10−610^{-6}; 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 10−410^{-4} 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 10−610^{-6}, 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, λ/λmax⁡=0.1\lambda/\lambda_{\max}=0.1). 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 10−610^{-6} 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 methodBaseline, also OLS-initialized10−410^{-4}10−610^{-6}
HS-APG-OLSUFGM5 of 136 of 16
HS-APG-OLSGAGD+9 of 139 of 15
OLS + safeguarded BTUFGM4 of 138 of 15
OLS + safeguarded BTGAGD+7 of 138 of 15

At 10−410^{-4}, four problems solved during initialization are excluded; safeguarded BT additionally reaches one problem missed by both baselines. At 10−610^{-6}, 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 10−610^{-6}.

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 0.10.1 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 10−610^{-6}; 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.

Reviewer_3Yo2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors study an important class of H¨oldersmooth problems, namely regularized ℓp regression with p ∈ (1, 2), whose loss has a (p − 1)-H¨older-continuous gradient and for which the universal method requires O(ε−2/(3p−2)) iterations. Exploiting the problem structure, they characterize a family of smooth approximations based on p-Huber smoothing and prove that it attains the exact optimal one-sided approximation–smoothness trade-off. Combined with accelerated proximal gradients, the smoothing approach attains an ε-optimal solution in O(ε^−1/p) matrix–vector products, which significantly improves the complexity guarantee for 1 < p < 2.

Critical strengths

This work is meaningful, and its theoretical results are solid:

  1. the authors improves the deterministic first-order complexity of composite lpl_p regression (1=<p<2) from the generic accelerated rate O(\varepsilon^{-2/(3p-2)) to the optimal rate O(\varepsilon^{-1/p), which matches the lower bound.
  2. The proposed p-Huber smoothing function achieves the optimal trade-off between the smoothing bias and the approximate smoothness constant with a single parameter (Theorem 2.4), and it naturally degenerates to the classical smooth case when p = 2.
  3. This paper applies the accelerated proximal gradient to the p-Huber surrogate and analyze its convergence under fixed and variable smoothing schedules. The authors analyze the fixed-smoothing and variable-smoothing variants, and established a lower complexity bound. Together with the upper bound, it determines the optimal deterministic matrix- vector complexity of lpl_p regression.
  4. It conducts a grid-based validation over p and the condition number κ on synthetic data, and reproduces the theoretically predicted acceleration trend on several UCI datasets, E2006, and an image deblurring task.
Critical weaknesses
  1. It does not compare against the genuinely strongest competitors. The paper's comparisons are limited to three first-order black-box baselines (UFGM, AGDA, GAGD+), and it never compares against IRLS / continuation homotopy / iterative refinement — precisely the practical mainstream for the regression problems. The authors' justification ("different oracle models") is defensible, but the cost is that "competitive performance" can only be claimed relative to three first-order baselines, not relative to the best in the field.

In the experimental part of this paper, the author had better add some comparison algorithms, such as IRLS / continuation homotopy / iterative refinement — precisely the practical mainstream for the regression problems,which precisely the practical mainstream for the regression problems field.

  1. The advantages of this experimental part are when is when p is small and ill-conditioned problems. Variable smoothing achieves the lowest terminal gap on all 60 instances with p≤1.25p \leq1.25 and $ \kappa\geq10^2S; but UFGM is instead lower at P=1.1,κ∈1,10P=1.1, \kappa \in{1,10} and also leads at the stricter 10−910^{-9}.

  2. At ill-conditioned problems with $ \kappa =10^4$, only 2 of the 50 instances reached 10−910^{-9} for any method.

  3. For real sparse regression problems,the accuracy less than 10−410 ^-4.

Questions for authors
  1. The bounded iterative sequence assumption zt−u∗{z_t-u^*} of Theorem 3.3 is relatively strong.

  2. Please discuss the novelty and difference of theorem 2.4 and related work to samakhoana&grimmer (2026) in the paper.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 3Yo2

We thank Reviewer 3Yo2 for the careful reading and insightful feedback.

W1. No comparison against the strongest competitors (IRLS, homotopy, iterative refinement).

We agree and will revise the manuscript to explicitly limit “competitive performance” to comparisons with the tested first-order baselines. We have also conducted additional IRLS comparisons, which confirm its strong performance on unregularized regression; please see our response to Reviewer NGJm, W6, for the results and the distinction in applicability to composite problems.

W2. The experimental gains are region-dependent and mild.

We agree that relative performance depends on the exponent, conditioning, and target accuracy. Within the tested first-order comparisons, our reductions in terminal gaps are substantial and consistent in the small-pp, ill-conditioned regime, and our variable-smoothing variants also lead across all eight fixed-budget E2006 settings reported in the paper. We will make both these strengths and their scope explicit. On the three points:

  • Small pp, and UFGM at 10−910^{-9}. On the 60 instances with p≤1.25p\le1.25 and κ(A)≥102\kappa(A)\ge10^2, one of our variants attains the smallest terminal gap on every instance (ordinary variable smoothing on 50, backtracking on 10), and the median ratio of UFGM's terminal gap to that of ordinary variable smoothing is 21.8. As the reviewer notes, UFGM has lower median terminal gaps at p=1.1p=1.1, κ(A)∈1,10\kappa(A)\in\\{1,10\\}. Its lead at 10−910^{-9} (128 of 250 instances, versus 113 for variable smoothing with backtracking, our best variant) comes from well-conditioned instances: at p≤1.25p\le1.25 and κ(A)≤10\kappa(A)\le10, UFGM reaches 27 of 40 and our variants none, whereas across all exponents with κ(A)≥102\kappa(A)\ge10^2, variable smoothing with backtracking reaches 54 of 150, versus 41 for UFGM.
  • κ(A)=104\kappa(A)=10^4. We agree that no method reaches 10−910^{-9} on more than 2 of these 50 instances, and we will state this as a limitation. At 10−610^{-6}, variable smoothing with backtracking reaches 37 of the 50, the most among the six methods (UFGM: 30); the failures concentrate at p≤1.25p\le1.25.
  • E2006. We agree that no run reaches 10−410^{-4}; this experiment measures progress under a fixed budget, and we will say so. Under the original experimental settings, one of our variable-smoothing variants attains the smallest terminal gap in all 8 settings. The additional safeguarded-backtracking comparison is reported in our response to Reviewer ernp, Q2.

Q1. Discuss the bounded-iterate assumption of Theorem 3.3: give sufficient conditions, or an assumption-free version.

We thank the reviewer for this helpful suggestion. It motivated us to clarify that the bounded-iterate assumption is not necessary for obtaining a convergence guarantee.

The bounded-iterate assumption holds directly when dom⁡ω\operatorname{dom}\omega is bounded, as in our box-constrained example: the proximal updates keep ztz_t in this domain, so its diameter provides a valid RR. For general domains, we can obtain a convergence guarantee without this assumption. For example, for 1≤p<21\le p<2, variable smoothing without line search, using the simple schedule ρt=ρˉ/(t+1)\rho_t=\bar\rho/(t+1) with any ρˉ>0\bar\rho>0, satisfies, for any minimizer u⋆u^\star,

\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}.$$ This guarantee requires neither uniformly bounded auxiliary iterates nor prior knowledge of the initial distance, which appears only in the bound. We will keep Theorem 3.3 as stated, add a remark after it, and give this result with its 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. **Q2. Clarify the increment of Theorem 2.4 relative to Samakhoana and Grimmer (2026).** Thank you for this question. Theorem 2.4 extends their optimal-smoothing framework to power losses: for $1<p<2$, their characterization does not imply ours, since their optimality characterization concerns sublinear functions and convex smoothings, whereas our function $|r|^p/p$ is not sublinear and our comparison class also contains nonconvex smooth minorants. We follow their formulation of the optimal trade-off between smoothness and uniform approximation error and extend it to the power losses with $1<p<2$; at $p=1$, our optimal value and Huber minorant agree with their outer-smoothing result for the absolute value. We will state this in the sentence introducing Theorem 2.4 and acknowledge their framework explicitly. We thank the reviewer again for the constructive feedback.

Thank you for your response. My concerns have been fully addressed.

Reviewer_NGJmOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers ℓp\ell_p regression problem with p∈(1,2)p \in (1, 2), which is a class of Holder smooth problem. The corresponding loss function has (p−1)(p-1) Holder continuous gradient. The existing guarantee for solving this class of Holder smooth problem required O(ε−2/(3p−2))\mathcal{O}(\varepsilon^{-2/(3p - 2)}) iterations. The authors exploit the structure of the problem and use a smoothing approach that improves the complexity guarantee to O(ε−1/p)\mathcal{O}(\varepsilon^{-1/p}) for finding an ε\varepsilon-optimal solution. Moreover, the authors show that this rate is optimal by finding a matching lower bound. Finally, they provide experiments to demonstrate practical performance of the proposed algorithm.

Critical strengths
  • The paper exploits the structure of the problem and improves the convergence rate to O(ε−1/p)\mathcal{O}(\varepsilon^{-1/p}).
  • The authors also show that the rate is optimal by showing a matching lower bound.
  • The pp-Huber smoothing approach is interesting.
Critical weaknesses
  • In line 117-118, the authors wrote about the restrictions. They should explain why these restrictions make sense.
  • In Theorem 3.2, the choice of ρT\rho_T and LTL_T require the knowledge of dist(u0,U⋆)\text{dist}(u_0, \mathcal{U}^\star) which is not known apriori.
  • The presentation of the paper requires more polishing. It is hard to follow at places.
  • In Theorem 3.3, the authors assume the iterates are bounded ∥zt−u⋆∥≤R\| z_t - u^\star\| \leq R.
  • In both the Theorems, tha authors make strong assumption to derive the rates. Are these strong assumption also needed for the general proof of Nesterov's universal fast gradient method? If not then it is an unfair comparison and misleading.
  • In experiments, the authors should also compare with IRLS (iterated reweighted least square algorithm).
Questions for authors
  • The authors explore deterministic variants. Can we extend the results to stochastic setting?
3 comments
AuthorsOpenReview ↗

Response to Reviewer NGJm (Part 1 of 2, W1 W5)

We thank Reviewer NGJm for the careful reading and constructive comments.

W1. Why do the restrictions in lines 117–118 make sense?

Thank you for this question. These lines fix the computational model: we count products with AA and A⊤A^\top and proximal steps on ω\omega, and do not treat linear solves or factorizations as unit-cost operations. This is the natural model for large-scale problems in which AA is sparse or available only as an operator, such as the convolution in our deblurring experiment. There, matrix–vector products are cheap, whereas accurate linear solves are expensive; at large scale, a factorization may be infeasible altogether, for instance because its fill-in exceeds the available memory or because AA is not stored explicitly. This matrix–vector oracle perspective also underlies the lower-bound framework of Ouyang and Xu (2021), which our proof of Theorem 3.4 follows. We will explain this motivation in the paper.

W2. The choice of ρT\rho_T and LTL_T in Theorem 3.2 requires D≥dist⁡(u0,U⋆)D\ge\operatorname{dist}(u_0,\mathcal U^\star), which is unknown a priori.

Thank you for this question. The condition can be dropped. If any D^>0\hat D>0 is used in place of DD in ρT\rho_T and LTL_T, the proof of Theorem 3.2 gives

\frac{\frac{2-p}{2}\hat D^{p}+\frac p2\operatorname{dist}(u_0,\mathcal U^\star)^2\hat D^{p-2}}{[T(T+1)]^{p/2}}.$$ The $\mathcal O(T^{-p})$ rate therefore holds for every $\hat D>0$. When the initial distance is positive, $\hat D=\operatorname{dist}(u_0,\mathcal U^\star)$ minimizes the bound and recovers Theorem 3.2. A $\hat D$ chosen independently of the distance keeps the rate, with the initial distance entering the bound quadratically rather than through its $p$-th power. We will add this bound as a remark after Theorem 3.2. **W3. The presentation requires more polishing.** Thank you for this feedback. We will revise the writing throughout. In particular, we will explain the computational model (W1), add remarks after Theorems 3.2 and 3.3 on what happens without their assumptions (W2, W4), and correct the description of UFGM's guarantee in the abstract (W5). We would be glad to revise any further passages that the reviewer found hard to follow. **W4. Theorem 3.3 assumes bounded iterates $\\|z_t-u^\star\\|\le R$.** *(Reviewers 3Yo2 and ernp raised the same point.)* We thank the reviewer for this helpful suggestion. It prompted us to clarify that the bounded-iterate assumption is not necessary for obtaining a convergence guarantee. For example, for $1\le p<2$, variable smoothing without line search, using the simple schedule $\rho_t=\bar\rho/(t+1)$ with any $\bar\rho>0$, satisfies, for any minimizer $u^\star$, $$F(y_T)-F^\star\le \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}.$$ This guarantee requires neither uniformly bounded auxiliary iterates nor prior knowledge of the initial distance, which appears only in the bound. We will include this result as a remark after Theorem 3.3, with its 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. **W5. Are these assumptions also needed for UFGM? Is the comparison fair?** Thank you for this question. UFGM requires neither assumption, but takes the target accuracy $\varepsilon$ as input. Given the same input, our fixed-smoothing method also requires no distance bound: just as UFGM uses $\varepsilon$ to control the inexactness of its quadratic upper model (Nesterov, 2015), we can set the smoothing radius to $\rho=(p\varepsilon/m)^{1/p}$ and retain the $\mathcal O(\varepsilon^{-1/p})$ iteration complexity. Alternatively, without prescribing $\varepsilon$, W2 and W4 provide explicit convergence guarantees without an input distance bound for fixed smoothing and without a bounded-iterate assumption for variable smoothing, respectively. We will clarify these guarantees and the required inputs to make the comparison explicit.
AuthorsOpenReview ↗

Response to Reviewer NGJm (Part 2 of 2, W6 & Q1)

W6. Comparison with IRLS. (Reviewer 3Yo2 raised the same point.)

Thank you for the suggestion. We view IRLS as a distinct algorithmic class, with strengths complementary to gradient/proximal methods. Our experiments often show a common pattern across the tested first-order methods, including ours: IRLS generally outperforms them on standard unregularized benchmarks, while several of them outperform IRLS on the larger ill-conditioned and strongly ℓ1\ell_1-regularized instances below. These shared patterns suggest different regimes of advantage for the two classes. Proximal methods also directly handle ℓ1\ell_1 regularization and box constraints, for which basic IRLS requires extensions.

Unregularized regression. The table reports the median of IRLS matvec cost/first-order method matvec cost\text{IRLS matvec cost}/\text{first-order method matvec cost} over instances where both methods reach a relative gap of 10−610^{-6}. Ratios >1>1 favor the first-order method; =1=1 indicates equal cost. Parentheses give the number of jointly attained instances. Costs include initialization and inner solves. V denotes our variable-smoothing method.

ProblemsIRLS/VIRLS/UFGMIRLS/GAGD+
Original UCI (18 instances)0.21 (15)0.25 (14)0.16 (13)
Original controlled synthetic (250 instances)0.27 (201)0.28 (193)0.29 (187)
Larger synthetic: m=4000m=4000, n=1000n=1000, κ(A)=1000\kappa(A)=1000, p∈1.75,1.9p\in\\{1.75,1.9\\} (10 instances)4.88 (10)3.03 (10)3.86 (10)

IRLS reaches the target on every instance in these rows, taking the best of four settings in the original benchmarks and six in the dimension study. In the larger synthetic study, V uses the initial-residual scale ρˉ=2∣Au0−b∣∞\bar\rho=2\\|Au_0-b\\|_\infty, and UFGM and GAGD+ each use the better first-hit cost from their 10−610^{-6} and 10−910^{-9} target settings. All three first-order methods are faster on all ten instances. Thus the change in relative performance is shared across these methods.

Composite problems. Standard IRLS uses weighted least-squares subproblems (Adil et al., 2019; Ene et al., 2026). Adding ℓ1\ell_1 regularization or box constraints requires modifying these subproblems or introducing further approximations; our framework handles both directly through proximal steps. We tested an IRLS extension that additionally reweights the ℓ1\ell_1 term. For sparse 150000×16000150000\times16000 synthetic problems with p=1.5p=1.5 and λ/λmax⁡=0.1\lambda/\lambda_{\max}=0.1, the terminal relative gaps under a 30,000-product budget are:

SeedIRLS, best of 16VSafeguarded BTUFGMGAGD+
15.77×10−35.77\times10^{-3}3.88×10−53.88\times10^{-5}3.31×10−53.31\times10^{-5}2.17×10−42.17\times10^{-4}9.63×10−59.63\times10^{-5}
22.46×10−32.46\times10^{-3}2.62×10−52.62\times10^{-5}2.32×10−52.32\times10^{-5}1.58×10−41.58\times10^{-4}7.98×10−57.98\times10^{-5}
31.17×10−31.17\times10^{-3}2.56×10−52.56\times10^{-5}2.14×10−52.14\times10^{-5}1.52×10−41.52\times10^{-4}6.75×10−56.75\times10^{-5}

The 16 IRLS settings cover CG/LSQR, least-squares/zero initialization, and four parameter choices. V and safeguarded BT use the initial-residual scale above; UFGM and GAGD+ use their 10−610^{-6} target settings. All four first-order methods attain smaller gaps, and V reaches 10−410^{-4} on all three instances, whereas none of the IRLS settings does. At the weaker regularization λ/λmax⁡=0.01\lambda/\lambda_{\max}=0.01, IRLS retains the advantage.

On the eight real-data E2006 instances, V also achieves smaller terminal gaps than the tested IRLS extension; for example, at TF-IDF and λ/λmax⁡=0.3\lambda/\lambda_{\max}=0.3, the gaps are 1.7×10−31.7\times10^{-3} versus 1.15×10−11.15\times10^{-1}. Neither reaches 10−410^{-4} within the paper's budgets. We will add these comparisons and restrict “competitive performance” to the tested first-order baselines.

Q1. Can the results be extended to the stochastic setting?

Thank you for this interesting question. Extending our framework to stochastic methods is a natural direction. However, stochastic noise may dominate the convergence rate, so the improvements established in the deterministic setting do not automatically carry over. We leave this extension and its analysis to future work.

We thank the reviewer again for the constructive feedback. We hope our responses address the reviewer's concerns, and we would be happy to clarify any remaining questions.

Thanks for the response. My concerns are well addressed. I will keep my positive score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised manuscript update information

We are pleased to share the revised manuscript and briefly summarize the updates informed by the reviewers’ feedback. We have benefited greatly from the thoughtful comments and discussion and have incorporated the clarifications and additions outlined in our responses. We are grateful to the reviewers for helping us build on the paper’s original framework and results through clearer explanations, further analysis, and focused supplementary experiments. The main updates are summarized below.

  1. Exposition and context. We have refined the presentation of p-Huber smoothing, clarified its relationship to existing smoothing results, and expanded the motivation for the matrix–vector oracle model. We have also clarified notation and added explanations in the proofs to make the arguments easier to follow (Sections 2–3 and Appendix A).

  2. Assumptions and convergence guarantees. Inspired by the reviewers’ questions about distance information and bounded iterates, we have made the role of these assumptions more explicit. We have supplemented the analysis with guarantees for arbitrary positive scale choices, including a variable-smoothing bound that does not require a bounded-iterate assumption, and explained how these results relate to the prescribed smoothing schedules (Section 3.2 and Appendices A.2 and B).

  3. Practical choices and experimental presentation. We have elaborated on safeguarded backtracking, residual-based scale selection, and least-squares initialization, together with their connections to the convergence analysis. We have also clarified initialization costs, the use of reference-distance estimates, and the interpretation of the reported comparisons (Sections 3–4 and Appendices B–C).

  4. Supplementary experiments. We have added focused experiments on shared least-squares initialization, smoothing-scale sensitivity and residual-based scale selection, and the effect of the backtracking safeguard. These studies provide further empirical detail on the practical questions raised during the discussion (Appendix D).

Revisions are highlighted in blue to facilitate review.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.