[webpage] [abstract] [bibtex] [arXiv]

Popular parameter-efficient fine-tuning (PEFT) methods, such as LoRA and its variants, freeze pre-trained model weights $\mathbf{W}$ and inject learnable matrices $\mathbf{\Delta W}$. These $\mathbf{\Delta W}$ matrices are structured for efficient parameterization, often using techniques like low-rank approximations or scaling vectors. However, these methods typically show a performance gap compared to full fine-tuning. Although recent PEFT methods have narrowed this gap, they do so at the cost of additional learnable parameters. We propose SVFT, a simple approach that fundamentally differs from existing methods: the structure imposed on $\mathbf{\Delta W}$ depends on the specific weight matrix $\mathbf{W}$. Specifically, SVFT updates $\mathbf{W}$ as a sparse combination of outer products of its singular vectors, training only the coefficients (scales) of these sparse combinations. This approach allows fine-grained control over expressivity through the number of coefficients. Extensive experiments on language and vision benchmarks show that SVFT¹¹1code is available at https://github.com/VijayLingam95/SVFT/ recovers up to 96% of full fine-tuning performance while training only 0.006 to 0.25% of parameters, outperforming existing methods that only recover up to 85% performance using 0.03 to 0.8% of the trainable parameter budget.

                @inproceedings{NEURIPS2024_48c368f1,
                  author = {Lingam, Vijay Chandra and Neerkaje, Atula and Vavre, Aditya and Shetty, Aneesh and Gudur, Gautham Krishna and Ghosh, Joydeep and Choi, Eunsol and Dimakis, Alex and Bojchevski, Aleksandar and Sanghavi, Sujay},
                  booktitle = {Advances in Neural Information Processing Systems},
                  editor = {A. Globerson and L. Mackey and D. Belgrave and A. Fan and U. Paquet and J. Tomczak and C. Zhang},
                  pages = {41425--41446},
                  publisher = {Curran Associates, Inc.},
                  title = {SVFT: Parameter-Efficient Fine-Tuning with Singular Vectors},
                  url = {https://proceedings.neurips.cc/paper_files/paper/2024/file/48c368f105e8145b945227b73255635a-Paper-Conference.pdf},
                  volume = {37},
                  year = {2024}
                }
              

[webpage] [abstract] [bibtex] [arXiv]

Multi-pushdown systems are a standard model for concurrent recursive programs, but they have an undecidable reachability problem. Therefore, there have been several proposals to underapproximate their sets of runs so that reachability in this underapproximation becomes decidable. One such underapproximation that covers a relatively high portion of runs is scope boundedness. In such a run, after each push to stack i, the corresponding pop operation must come within a bounded number of visits to stack i. In this work, we generalize this approach to a large class of infinite-state systems. For this, we consider the model of valence systems, which consist of a finite-state control and an infinite-state storage mechanism that is specified by a finite undirected graph. This framework captures pushdowns, vector addition systems, integer vector addition systems, and combinations thereof. For this framework, we propose a notion of scope boundedness that coincides with the classical notion when the storage mechanism happens to be a multi-pushdown. We show that with this notion, reachability can be decided in PSPACE for every storage mechanism in the framework. Moreover, we describe the full complexity landscape of this problem across all storage mechanisms, both in the case of (i) the scope bound being given as input and (ii) for fixed scope bounds. Finally, we provide an almost complete description of the complexity landscape if even a description of the storage mechanism is part of the input.

    @misc{shetty2021scopebounded,
      title={Scope-Bounded Reachability in Valence Systems},
      author={Aneesh K. Shetty and S. Krishna and Georg Zetzsche},
      year={2021},
      eprint={2108.00963},
      archivePrefix={arXiv},
      primaryClass={cs.FL}
    }