{"id":"308c6ccd-c267-4afd-89c3-cbfc9e4f60db","arxiv_id":"2412.20115","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A proximal gradient descent method with locally estimated step sizes is proposed and shown in experiments to outperform fixed-step proximal gradient descent on L1-regularized regression.","lead":"This paper reviews gradient descent and proximal gradient descent for regularized optimization and proposes an adaptive version that estimates the local Lipschitz constant at each step. On synthetic and one real dataset, the adaptive method took fewer iterations to reach the stopping threshold than the fixed-step proximal gradient method.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2 can select step sizes larger than the global Lipschitz reciprocal 1/L, and the asserted boundedness and convergence of {lambda_k} are not proved, so the central performance claim lacks the theoretical support it needs.","rationale":"The reader's weakest_assumption identifies the same core issue: the variable step size rule is not proven to keep the method in a convergent regime. My stress-test sharpens the concern by pointing to a specific gap in Section 4: the local ratio condition in Algorithm 2 does not imply lambda_k <= 1/L, and the paper's own convergence theorems (Theorems 3 and 4) require exactly that inequality. The paper's statement that lambda_k is bounded 'similarly as in [11]' is an assertion, not a proof, and Section 6 concedes that theoretical results are future work. This makes the performance claim in the abstract hinge on an unverified algorithmic condition. The empirical results are useful but do not close the gap: parameters are tuned on the test problems, only one real-data set is used, and the comparison omits other adaptive step size methods such as the Malitsky-Mishchenko approach referenced in the paper. For these reasons, a conditional acceptance is appropriate: the algorithm is plausible and the experiments are encouraging, but the paper should either prove the needed step-size bound (or establish convergence under weaker conditions) or clearly reframe the contribution as an empirical heuristic. Since this matches the reader's conditional verdict, no adjustment is needed.","tokens_in":16833,"tokens_out":11817,"duration_ms":118427,"concrete_test":"Run Algorithm 2 with the paper's stated parameters (lambda_0 = 0.1, mu_0 = 0.99, mu_1 = 0.95, eta_k = 1/k^2) on one-dimensional L-smooth strongly convex objectives with nonconstant curvature, such as f_a(x) = x^2 + a*sin(x) for a in {0.25, 0.5, 0.75, 1.0} (L = 3, mu = 1) and f(x) = log(cosh(x)) + 0.5*x^2, starting from x_0 = 10. Record the maximum lambda_k over all iterations, the number of iterations with lambda_k > 1/L, and whether F(x_k) is monotone nonincreasing and x_k converges to the unique minimizer. If any run with lambda_k > 1/L fails to converge or becomes nonmonotone, Algorithm 2 has a concrete failure mode that the missing convergence proof was meant to exclude; if all such runs converge monotonically despite lambda_k > 1/L, the practical claim survives for these cases but the theoretical bound remains unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the variable step size proximal GD method in Algorithm 2 reliably solves (13) and outperforms constant-step proximal GD. The load-bearing condition is that the generated step sizes remain in a range where the proximal gradient iteration is guaranteed to converge. In Section 4, the algorithm's false branch (Algorithm 2, line 8) only enforces lambda_k <= mu_0 * ||x_{k+1}-x_k|| / ||f(x_{k+1})-f(x_k)||, and this ratio can be much larger than the global reciprocal 1/L. Indeed, for an L-smooth f the ratio is bounded below by 1/L but has no nontrivial upper bound, so lambda_k may exceed 1/L even while the local test passes. Theorems 3 and 4, which are the paper's convergence results for proximal GD, both explicitly require 0 < lambda <= 1/L. The paper asserts that {lambda_k} is bounded 'similarly as in [11]' (Section 4) but provides no proof, and boundedness alone would not imply lambda_k <= 1/L. Section 6 explicitly defers theoretical results to future work. Without a proof that lambda_k <= 1/L—or a new convergence theorem that tolerates larger step sizes—the iterates generated by Algorithm 2 are not covered by the paper's own theory, and the empirical gains in Section 5 are not explained by the presented framework. The tuned constants lambda_0, mu_0, and mu_1 enter directly into this gap, as do the specific choice of summable {eta_k} and the fact that the experiments still compute L for comparison.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper surveys gradient descent and proximal gradient descent for composite convex optimization, proves standard O(1/n) and linear convergence rates under L-smoothness and strong convexity, and derives the soft-thresholding proximal map for L1 regularization. Its proposed contribution is Algorithm 2, a proximal gradient method with a variable step size that estimates the local Lipschitz constant at each iteration, together with numerical experiments on three synthetic datasets and the King County real estate dataset comparing the method with constant-step proximal gradient descent and Adam. The survey portions are largely correct, but the central novel claims—that Algorithm 2 is convergent and that it reliably outperforms constant-step proximal gradient methods—are not backed by rigorous theory and are supported by experiments with important methodological weaknesses.","tokens_in":17239,"tokens_out":6408,"duration_ms":69056,"significance":"If the variable-step proximal gradient method were rigorously shown to converge and to retain the O(log(1/epsilon)) complexity claimed in Section 4, it would be a practically useful alternative in settings where the global Lipschitz constant is expensive or unavailable. The paper's standard convergence theorems for constant-step proximal gradient are correct and clearly presented, and the paper correctly emphasizes that smoothness is a local property. However, the proposed algorithm's step-size rule is not covered by the paper's own convergence theory, and the empirical evidence is not sufficient to establish the performance claim. The central contribution therefore stands or falls on additional theoretical and numerical work that the current manuscript does not provide.","major_comments":[{"comment":"The iterates generated by Algorithm 2 are not covered by the paper's convergence theorems. Since f is L-smooth, the norm ratio R_k = ||x_{k+1}-x_k|| / ||grad f(x_{k+1}) - grad f(x_k)|| satisfies R_k >= 1/L, but it has no finite upper bound. In the true branch of Algorithm 2 (line 6), lambda_{k+1} = mu_1 R_k can therefore exceed 1/L even though mu_1 < 1. In the false branch (line 8), the condition only enforces lambda_k <= mu_0 R_k, so lambda_k may already be larger than 1/L, and the update increases lambda_k further. Lemma 1 and Theorems 3 and 4 all require 0 < lambda <= 1/L, so the step sizes generated by Algorithm 2 can leave the theoretically valid regime. The statement in Section 4 that {lambda_k} is bounded 'similarly as in [11]' is not a proof, and even boundedness would not imply lambda_k <= 1/L. Section 6 explicitly defers theoretical results to future work, so the convergence of Algorithm 2 is currently unproven. Figure 3 even confirms that the selected step sizes are sometimes greater than 1/L. The authors should either prove that Algorithm 2 keeps lambda_k in a range where convergence is guaranteed, or modify the algorithm and prove a new convergence theorem for larger step sizes.","section":"Section 4, Algorithm 2, Eqs. (33)-(38); Theorems 3 and 4"},{"comment":"The numerical evidence does not support the claim of 'notable performance improvement' as stated. The parameters lambda_0 = 0.1, mu_0 = 0.99, and mu_1 = 0.95 are empirically chosen on the same test problems ('we have empirically established that appropriate values for the parameters are...'), so the comparison partially reflects tuning rather than a fixed, prespecified method. The experiments use only three synthetic instances and one real dataset, report average CPU times from 7 runs without variance or error bars, and provide no statistical significance assessment. The stopping rule is also asymmetric: the proximal methods stop when F(x_{k+1}) > F(x_k), while Adam is exempted from this criterion because it is 'non-monotone by design.' Since Algorithm 2 can produce step sizes larger than 1/L, this non-monotonicity stop may terminate at a point where the function value has only temporarily increased, which can favor the variable-step method; no evidence is given that the stopping point is near a true minimizer. The empirical claim would need substantially stronger validation, including fixed parameters chosen by a separate procedure, multiple random trials, error bars, and a fair stopping rule.","section":"Section 5, Table 1 and Figures 1-4"},{"comment":"The synthetic 'optimal solution' x* is not a minimizer of the objective in Eq. (39). The authors generate b = A x* + xi with xi having i.i.d. standard normal entries, so grad f(x*) = A^T xi / m is generally nonzero, and the optimality condition for the composite objective (39), 0 in grad f(x*) + alpha partial ||x*||_1, is not satisfied for the stated construction. Therefore Figure 2, which plots ||x_k - x*|| as a distance to the 'optimal solution,' does not measure distance to a true optimum of the problem being solved, and the objective-value comparisons in Figure 1 are not benchmarked against the correct optimal value F(x*). This undermines the synthetic validation of the central performance claim. The experiments need to be redesigned so that the true minimizer of (39) is known or computed independently.","section":"Section 5, synthetic data generation and Eq. (39)"}],"minor_comments":[{"comment":"The phrase 'exponential (i.e., superlinear) convergence' is inaccurate for the rate in Theorem 2: the bound decays linearly in the multiplicative factor (1 - mu/L), i.e., exponentially in the iteration count, which is normally called linear convergence, not superlinear.","section":"Section 2.2 and Introduction"},{"comment":"The input specification lists '0 < mu_1 < mu_0 < 1' but never states the domain or smoothness assumptions on f and g for Algorithm 2 beyond the earlier global L-smoothness assumption; the paper should state explicitly which of the theorems in Section 3 are assumed to apply to the variable-step setting.","section":"Section 4, Algorithm 2"},{"comment":"The table header contains a typo, 'Algorthm' instead of 'Algorithm', and the column headers repeat the spelling; the table also reports only average times without standard deviations, which would be useful even in a preliminary comparison.","section":"Section 5, Table 1"},{"comment":"The stopping rule based on ||grad f(x_k)|| < 0.001 is not equivalent to a stationarity condition for the composite objective F in Eq. (39), because grad f(x_k) alone does not account for the subgradient of the L1 term; the stopping criterion should be described in terms of a residual of the proximal-gradient fixed-point condition.","section":"Section 5, stopping criteria"},{"comment":"The sentence 'Algorithms 1 and 2 have similar complexities of order O(log(1/epsilon)) for the case of L-smooth, mu-strongly convex functions' is not established anywhere for Algorithm 2; since no convergence theorem exists for the variable-step method, this claim should be phrased as an empirical observation or removed until a proof is provided.","section":"Section 6, conclusion"}],"recommendation":"major_revision","confidential_remarks":"The paper is best understood as a tutorial on standard proximal gradient methods plus a proposed algorithmic modification. The survey portions are sound but not novel; the proposed Algorithm 2 is the main reason for considering the paper at a research journal. The decisive issue is that Algorithm 2 has no convergence proof and its step sizes can leave the regime where the paper's own theorems apply. The empirical section also needs to be redone with a correct synthetic optimum, proper statistical reporting, and a fair stopping rule. These are substantial but addressable revisions; if the authors can add a rigorous convergence analysis or a modified algorithm with a proof, and redo the experiments, the paper could become publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is a review of GD and proximal GD with one new piece: Algorithm 2, a variable step size proximal GD inspired by Malitsky-Mishchenko and Liu et al. The review part is solid but textbook; the algorithm is a small extension, and the empirical evidence is real but preliminary. The stress-test note is right: the load-bearing gap is that Algorithm 2 can produce step sizes larger than 1/L, and the paper has no proof that its iterates stay in the region where Theorems 3 and 4 apply.\n\nWhat it does well: the convergence proofs for constant step size are correct, if standard; the exposition of soft-thresholding is clear; Algorithm 2 is simple and plausible; the experiments show consistent gains in iterations and wall-clock time across three synthetic datasets and King County, and the authors are honest that Algorithm 1 has better per-iteration speed and that theory is left for future work. That honesty counts.\n\nThe soft spots are real. The step size rule in line 8 only ensures the previous lambda_k was below mu_0 times the norm ratio; it does not prevent lambda_{k+1} from growing past 1/L. Their own Figure 3 shows lambda_k above 1/L. So the statement that {lambda_k} is bounded 'similarly as in [11]' is not a proof, and even boundedness would not give the required 0