arXiv:2211.04088

A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming

Parvin Nazari, Ahmad Mousavi, Davoud Ataee Tarzanagh, George Michailidis

제출 2022-11-08

원문 초록

Bilevel programming has recently received attention in the literature due to its wide range of applications, including reinforcement learning and hyper-parameter optimization. However, it is widely assumed that the underlying bilevel optimization problem is solved either by a single machine or, in the case of multiple machines connected in a star-shaped network, i.e., in a federated learning setting. The latter approach suffers from a high communication cost on the central node (e.g., parameter server). Hence, there is an interest in developing methods that solve bilevel optimization problems in a communication-efficient, decentralized manner. To that end, this paper introduces a penalty function-based decentralized algorithm with theoretical guarantees for this class of optimization problems. Specifically, a distributed alternating gradient-type algorithm for solving consensus bilevel programming over a decentralized network is developed. A key feature of the proposed algorithm is the estimation of the hyper-gradient of the penalty function through decentralized computation of matrix-vector products and a few vector communications. The estimation is integrated into an alternating algorithm for solving the penalized reformulation of the bilevel optimization problem. Under appropriate step sizes and penalty parameters, our theoretical framework ensures non-asymptotic convergence to the optimal solution of the original problem under various convexity conditions. Our theoretical result highlights improvements in the iteration complexity of decentralized bilevel optimization, all while making efficient use of vector communication. Empirical results demonstrate that the proposed method performs well in real-world settings.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2606.19734v1cs.LG공통 태그 Bilevel Optimization, Federated Learning

연합 이중 수준 수행적 예측

Federated Bilevel Performative Prediction

연합 이중 수준 최적화는 프라이버시 및 통신 제약 하에서 연합 하이퍼파라미터 튜닝 및 메타학습과 같은 분산 클라이언트에 걸친 중첩된 학습 문제에 널리 사용됩니다. 대부분의 기존 정식화는 고정된 클라이언트 데이터 분포를 가정하지만, 이는 수행성(Performativity)에 의해 위반될 수 있습니다. 수행성이란 배포된 의사결정이 클라이언트 행동과 데이터 수집을 재형성하여, 클라이언트별 의사결정 종속 분포 변화를 유발하는 현상입니다. 우리는 상위 수준(UL) 및 하위 수준(LL) 목적 함수가 모두 클라이언트 종속 및 의사결정 종속 분포 하에서 평가되는 연합 이중 수준 수행적 예측을 연구합니다. 우리는 분리된 위험(decoupled-risk) 관점 하에서 연합 이중 수준 수행적 안정점(FBPS)을 형식화하고, 그 존재성과 유일성에 대한 충분 조건을 제공합니다. 그 후 우리는 FBPS 해를 계산하기 위한 두 가지 연합 방법을 개발했습니다: 수축 조건 하에서 선형 수렴하는 FBi-RRM과, 민감도가 충분히 작을 때 점감하는 스텝 사이즈 하에서 수렴이 보장되는 연합 하이퍼그라디언트 추정에 기반한 통신 효율적인 확률적 방법인 FBi-SGD입니다. 전략적 회귀 및 메타 전략적 분류에 대한 실험은 예측된 안정성 임계값을 검증하고 비수행적(non-performative) 기준선 대비 향상된 메타 일반화를 입증합니다. 또한 CNN 기반 분류는 비볼록 신경망 설정에서 제안된 방법들의 실질적 효과를 추가로 보여줍니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.