Summary
This paper characterizes the trajectory of gradient flow on 2-layer diagonal linear networks for linear regression tasks. Specifically, the paper considers the model parameterized as $x \mapsto \langle u \odot w, x \rangle$ in the linear regression setting. By interpreting the gradient flow on the nonconvex loss as a mirror flow, the authors show, in the limit of vanishing initialization, that the gradient flow dynamics jump between various saddles before converging to the minimum $\ell_1$ norm solution. The paper characterizes the exact times of these jumps (after appropriate rescaling based on the initialization size $\alpha$ in the $\alpha \rightarrow 0$ limit), as well as the location of these saddles; these times and locations can be computed via algorithm 1. As a consequence, the paper shows that each saddle is a solution to a constrained minimization problem where some subset of coordinates are fixed 0. Under a RIP assumption on the data, the paper shows that new coordinates are added sequentially at each saddle, thus demonstrating incremental learning.
Strengths
- The paper appears to be technically sound, and is well-written and easy to understand.
- The quadratically parameterized regression problem has been well studied in prior works (Woodworth et al. 2020, Azulay et al. 2021, and others), which show that the gradient flow can be characterized by mirror descent and converges to the minimum $\ell_1$ solution in the $\alpha \rightarrow 0$ limit. However, the current paper exactly characterizes the limit of the gradient flow trajectory under minimal data assumptions, which is a novel analysis. The main technical novelty here is proving that as $\alpha \rightarrow 0$ the trajectory converges to a piecewise constant process.
- While many prior works on implicit regularization only focus on properties of the solution at convergence, the current paper can describe the saddle points along the trajectory. I find it to be a significant contribution that the successive saddles which can be visited by gradient flow can be characterized (by Algorithm 1) explicitly. In particular, the observation that coordinates can be deactivated has not appeared in prior work and is quite interesting.
- Finally, I find this paper to be of moderate significance, as the quadratically parameterized linear regression setting is a common toy problem to understand the implicit regularization effect of gradient descent more generally.
Weaknesses
There are a couple (minor) weaknesses of the current theory.
- The analysis is limited to the quadratically parameterized regression setting, which while despite possessing rich implicit regularization behavior is still far from more practical settings in which implicit regularization occurs.
- One weakness of the current paper is that the jump times and saddle locations are only implicitly defined via Algorithm 1. The paper does show that under an RIP assumption that the jump times are $1/\beta^*_s$ and the saddles correspond to incrementally learning more coordinates. However, it is difficult to interpret the intermediate iterates of Algorithm 1 more generally, which reduces the impact of this paper.
- Another weakness is that the entirety of the analysis is done in the $\alpha \rightarrow 0$ limit, rather than at some small (but finite) initialization $\alpha$.
Minor typos:
- line 133 “diferred” → “deferred”
- line 318 “independant” → independent”
Questions
- In general, what can one say about successive saddles? It would be interesting to understand more fine grained properties about the sequence of saddles, such as how many coordinates can change at each step and under what conditions coordinates can get deactivated. I find it unlikely that Algorithm 1 would loop through all possible subsets of activated coordinates, and instead find it more likely that coordinates would be deactivated less frequently. I thus think the paper would benefit from additional investigation (either theoretically or empirically) into how the set of activated coordinates changes between saddles.
- What can be said in the case when $\alpha$ is small but isn’t taken to 0? Can one say something quantitatively about whether saddle-to-saddle dynamics occur, or the rate at which the trajectory limits to the piecewise constant trajectory $\tilde \beta^\circ$?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
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
Limitations/Broader Impact are adequately addressed.