- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies SGD and Stochastic Gradient Flow of quadratic objectives and an overparametrized Hadamard model (two layer linaer diagonal network, i.e. replace one parameter vector with the element wise product of two parameter vectors) in order to determine if the paths of the 'from start average' (over these algorithms trajectories) correspondence to a Lasso path. Previous work showed the Gradient Flow (not stochastic) yields a correspondence with a 'deterministic Lasso path' (i.e. the set of solutions to the Lasso problem with regularization 1/t, plotted against increasing t). This paper aimed to test if the same can be shown for SGF and SGD. Their first main result shows that for 'fixed noise' the paths recovered by both SGD and SGF correspond to that of a Lasso path with a coordinate wise weighting, with distinct weighting for SGF and SGD. Hence both objects yield solutions which are distinct from eachother and non-stochastic gradient flow. The second main results considers the 'weak noise' setting where the initialization and step size tend to 0. They show that as (or for SGF) both SGD and SGF recover the deterministic Lasso path, even if (or ). The reason is a 'future-active clock' argument: only the noise/variance accumulated on a coordinate before its next future move in the true Lasso path actually contributes to the final error, so the total accumulated noise over the whole horizon is not the relevant quantity. This recovery is conditional on a localization/stopping-time argument (whose failure probability vanishes) and, for the actual-SGD case, on the true path never deleting or reversing a coordinate's sign.
Critical strengths
The paper extends previous analysis comparing gradient flow to deterministic Lasso paths to include both SGF and SGD in order to demonstrate that these processes do not all behave the same in the fixed noise case but also demonstrates conditions under which they all recover the deterministic Lasso Paths. This is a clear improvement from past results as far as I undestand.
Critical weaknesses
The entire paper is very difficult to read. It feels like on is expected to already be an expert in this precise specific sub-field in order to understand the terminology that is casually thrown around from the very start of the paper. This may or may not be a purposeful design choice from the authors but for a conference like ICLR it feels like the writing is not well aligned to the target audience. I did my best to understand the main intent behind the main theorems in order to understand the contribution.
The scope of the results is extremely limited in that it is one very specific toy model being considered. I will acknowledge their results continue an existing line of work and in fact make it more general, but nevertheless I want to emphasize that the work focuses on a very specific toy problem.
Questions for authors
The first main result (Theorem 4.1) makes use of the 'EXACTLY SOLVABLE AXIS SAMPLER'. Do you expect the results to hold more generally? If so what would be the main bottleneck in doing so? As disclosed in the paper the proofs came from a conversation with ChatGPT-5.6 Sol, so if the majority of the technical details are outsourced, then I am curious why it was not feasible to prove things at a greater level of generality. My assumption being that: if more generality came at a cost of making things 'messier' or more tedious, then this cost could be paid with the LLM, whereas if there is a greater cost (such as the core approach or mechanisms used in the proofs do not extend) then can one believe these results actually contribute to understanding a phenomenon more general?
2 comments
Thank you for the response. I want to note that it is not clear how much was rewritten to address the commonly identified issue of the text being poorly written (which is now identified with AI usage) and it is unreasonable to expect reviewers under the tight deadlines of ICLR to completely re-read and re-review the entire paper to determine if it was well written this time. I appreciate the additional results but I do not believe they bring the significance of the results up to the acceptable level and so I will maintain my score.
1. Difficulty reading the paper and suitability for the ICLR audience
Common response: C1 and C4.
C1 summarizes the presentation changes, and C4 explains why the path characterization matters. We revised the introduction to make this motivation explicit. The revision distinguishes the instantaneous network predictor from its average along a training run and identifies where balanced or signed factors are used. The numerical results are presented as tests of these mechanisms on specified datasets.
2. Scope limited to a specific toy model
Common response: C2; C3, especially point 5; C4.
The revised introduction clarifies the motivation discussed in C3, point 5, and C4: a linear predictor and quadratic loss let us isolate the effects of sampling and finite updates. This is still a two-layer diagonal linear network; the data extensions do not change the architecture or loss.
Within this model, Section 5 treats correlated data, signed predictors and rank-deficient designs, including d>n. Under the stated trajectory hypotheses, it compares averaged predictions with averaged ISS and gives an exact criterion for Lasso prediction and objective recovery. Section 5.4 also gives a correlated nonnegative SGD class for which all assumptions are proved.
Question. Does Theorem 4.1 hold more generally, and what is the main bottleneck?
Common response: C3, point 4 (fixed noise and fixed steps); C2 (general averaged dynamics).
Theorem 4.1 uses a dataset where each observation has only one nonzero feature. The logarithmic identities extend to correlated designs, but they do not automatically give the same fixed weighted-Lasso description. For the balanced nonnegative SGF model, Theorem A.1 assumes H≻0 and joint uniform convergence in probability of the integrated predictor and accumulated variance to deterministic limits on a compact interval of positive rescaled time as initialization vanishes. It also assumes the limiting optimality conditions stated there: the integrated predictor and its dual slack are nonnegative and have zero product in each coordinate. Under these hypotheses, the limiting average solves a weighted Lasso problem constrained to nonnegative coefficients, with penalty coefficients (1+Ai(s))/s. Here Ai(s) is the limiting accumulated variance correction, so the weights can vary with rescaled time s.
Proposition A.2 separately proves an SGF limit for a symmetric correlated example with four observations sampled in two equiprobable blocks. Its scalar Lasso penalty is 1/s+δσ2/2, where δ is the SGF noise level and σ2 is the constant coordinate gradient variance in that example. This gives a proved extension beyond the dataset in Theorem 4.1.
For a general correlated SGF extension, the additional task is probabilistic control of accumulated gradient variance, including time near inactive coordinates and repeated departures from and returns to those regions. The estimates in Appendix A.4 do not bound this total contribution. More algebraic bookkeeping alone does not supply the required global estimate, and the disclosed AI assistance did not supply it. A correlated fixed-step SGD result would also require control of its exact finite-step logarithmic corrections.
The general comparisons in Theorem 5.1 and Corollary 5.2 address a different limit. As initialization shrinks, the SGD step size tends to zero, or the product of the SGF noise level and the localized variance bound tends to zero. Under the respective trajectory hypotheses, the averaged predictions then approach those of averaged ISS. This comparison establishes the general averaged reference when the stochastic or finite-step corrections vanish.