약볼록 함수

편집 역사 토론
최적설계 수치해석 마지막 수정: 2026-08-14 04:39:08

1. 개요[편집]

약볼록 함수
Weakly Convex Function
정의f + (ρ/2)‖·‖² 이 볼록 ⟺ f 는 ρ-약볼록
다른 이름세미볼록(semiconvex), 파라볼록(paraconvex), 하위-C²
C² 판정∇²f ⪰ −ρI (헤세의 최소 고윳값 하한)
핵심 성질λ < 1/ρ 이면 prox 가 단일값, 모로 포락이 C¹
정상성 척도‖∇Mλf(x)‖
대표 응용강건 위상 복원, 저계수 복원, 비평활 비볼록 손실

약볼록 함수는 이차항을 하나 더해 주면 볼록이 되는 함수다. 즉 f:Rn→R∪{+∞}f : \mathbb{R}^n \to \mathbb{R}\cup\{+\infty\} 가 어떤 ρ≥0\rho \ge 0 에 대해

x ⟼ f(x)+ρ2∥x∥2이 볼록x \ \longmapsto\ f(x) + \frac{\rho}{2}\|x\|^2 \quad\text{이 볼록}

이면 ff 를 ρ\rho-약볼록(ρ\rho-weakly convex)이라 한다. ρ=0\rho=0 이면 그냥 볼록이고, ρ\rho 가 클수록 “볼록에서 멀다”. 이 한 줄이 하는 일은 비볼록성의 정도를 스칼라 하나로 재는 것이며, 그 덕에 볼록 최적화의 도구 대부분이 상수만 바뀐 채 그대로 넘어온다.

왜 이 개념이 필요한가. 볼록 최적화의 세계 밖으로 한 발만 나가면 곧바로 “정상성을 어떻게 정의하나”라는 벽에 부딪힌다. 매끄러우면 ∥∇f∥\|\nabla f\| 를 쓰면 되고, 볼록이면 f(x)−f⋆f(x)-f^\star 를 쓰면 된다. 그런데 비매끄럽고 동시에 비볼록인 함수 — 요즘 이 바닥 문제의 절대다수 — 에는 둘 다 없다. 약볼록성은 이 공백에 딱 맞는 최소한의 구조를 제공한다. 그리고 놀랍게도 실무에서 만나는 비볼록 문제의 상당수가 실제로 약볼록이다.

prox\mathrm{prox} 연산자와 모로 포락 자체의 정의·성질은 모로 포락에, 알고리즘 계보는 근접점 알고리즘에 있다. 이 문서는 그 두 문서가 “약볼록이면” 하고 넘긴 부분의 정의를 확정하고, 왜 그 조건이 결정적인지를 다룬다.

2. 동치인 정의들[편집]

ff 가 닫힌 진(proper) 함수일 때 다음이 모두 동치다.

  • f+ρ2∥⋅∥2f + \frac{\rho}{2}\|\cdot\|^2 가 볼록.
  • 하위 그래디언트 부등식이 이차항만큼 느슨해진다. 모든 x,yx,y 와 v∈∂f(x)v \in \partial f(x) 에 대해
f(y) ≥ f(x)+⟨v,y−x⟩−ρ2∥y−x∥2f(y) \ \ge\ f(x) + \langle v, y-x\rangle - \frac{\rho}{2}\|y-x\|^2

볼록함수의 “접평면이 항상 아래에 깔린다”가 “포물면이 아래에 깔린다”로 완화된 것이다.

  • 하위미분이 하이포단조(hypomonotone): ⟨u−v, x−y⟩≥−ρ∥x−y∥2\langle u - v,\, x - y\rangle \ge -\rho\|x-y\|^2 (u∈∂f(x)u\in\partial f(x), v∈∂f(y)v\in\partial f(y)). 단조 작용소의 단조성이 −ρ-\rho 만큼 어긋나는 것을 허용한 형태.
  • ff 가 C2C^2 면 ∇2f(x)⪰−ρI\nabla^2 f(x) \succeq -\rho I, 즉 헤세 행렬의 최소 고윳값이 −ρ-\rho 이상.
  • 국소적으로 하위-C2C^2(lower-C2C^2): 매끄러운 함수족의 상한(pointwise max)으로 국소 표현된다. 록카펠라와 웨츠가 정리한 이 특성화 덕분에 약볼록성은 변분해석의 표준 클래스가 됐다.1

여기에 하나 더. ff 가 ρ\rho-약볼록이면 자명하게

f=(f+ρ2∥⋅∥2)⏟볼록−ρ2∥⋅∥2⏟볼록f = \underbrace{\Bigl(f + \frac{\rho}{2}\|\cdot\|^2\Bigr)}_{\text{볼록}} - \underbrace{\frac{\rho}{2}\|\cdot\|^2}_{\text{볼록}}

이므로 볼록함수의 차(DC 분해)를 갖는다. 반대는 성립하지 않는다 — DC 함수는 훨씬 넓다. 약볼록은 뒤쪽 볼록항이 하필 이차형식이라는 매우 특수한 DC 이고, 그 특수성 덕에 근접 계열 알고리즘과 궁합이 맞는다. DC 계획법이 별도의 이론을 필요로 하는 이유이기도 하다.

3. 어디서 나오는가 — 합성 구조[편집]

약볼록성이 학계에서 대접받게 된 결정적 계기는 합성 구조 f=h∘cf = h \circ c 가 자동으로 약볼록이라는 관찰이다.

h 가 Lh-립시츠 볼록,c∈C1 이고 ∇c 가 Lc-립시츠 ⟹ h∘c 는 LhLc-약볼록h \text{ 가 } L_h\text{-립시츠 볼록}, \quad c \in C^1 \text{ 이고 } \nabla c \text{ 가 } L_c\text{-립시츠} \ \Longrightarrow\ h\circ c \text{ 는 } L_h L_c\text{-약볼록}

증명 한 줄. 볼록성과 립시츠성으로 h(c(y))≥h(c(x)+∇c(x)(y−x))−Lh∥c(y)−c(x)−∇c(x)(y−x)∥h(c(y)) \ge h(c(x)+\nabla c(x)(y-x)) - L_h\|c(y)-c(x)-\nabla c(x)(y-x)\| 이고, 뒤 항이 Lc2∥y−x∥2\frac{L_c}{2}\|y-x\|^2 이하다. 끝.

이 정리가 왜 강력한지는 응용 목록을 보면 안다.

  • 강건 위상 복원. min⁡x1m∑i∣⟨ai,x⟩2−bi∣\min_x \frac{1}{m}\sum_i \bigl| \langle a_i, x\rangle^2 - b_i \bigr|. 바깥 h=∣⋅∣h=|\cdot| 는 1-립시츠 볼록, 안쪽 ci(x)=⟨ai,x⟩2−bic_i(x)=\langle a_i,x\rangle^2-b_i 는 헤세가 상수 2aiai⊤2a_ia_i^\top 이라 ∇c\nabla c 가 립시츠. 비볼록하고 비매끄러운데 약볼록이다.
  • 저계수 행렬 완성의 ℓ1\ell_1 정식화. min⁡U,V∥PΩ(UV⊤−M)∥1\min_{U,V}\|\mathcal{P}_\Omega(UV^\top - M)\|_1. 같은 구조 — 이차 사상 위에 볼록 비평활 손실.
  • 강건 주성분분석·사전 학습·센서 위치추정. 전부 “비선형 매끄러운 잔차 + 볼록 비평활 손실”.
  • 최대 편차 최소화·정확 벌점. 벌점법의 ℓ1\ell_1 정확 벌점 f(x)+μ∥c(x)∥1f(x) + \mu\|c(x)\|_1 도 cc 가 매끄러우면 약볼록이다. 비평활 정확 벌점을 직접 최소화하는 알고리즘의 수렴 해석이 이 틀에서 이뤄진다.

반대로 약볼록이 아닌 것도 분명히 해 두자. ∥x∥0\|x\|_0 이나 계수(rank) 같은 조합적 벌점은 약볼록이 아니고(하한 이차식으로 못 받친다), 매끄러운 함수라도 헤세가 아래로 무계면 전역 약볼록이 아니다. 다항식 손실은 유계 영역에서만 약볼록이라 상수 ρ\rho 가 정의역 크기에 딸려 온다.

4. 모로 포락이 매끄러워지는 조건[편집]

여기가 이 개념의 심장이다. 근접 부분문제

proxλf(x)=arg⁡min⁡u{f(u)+12λ∥u−x∥2}\mathrm{prox}_{\lambda f}(x) = \arg\min_u \Bigl\{ f(u) + \frac{1}{2\lambda}\|u-x\|^2 \Bigr\}

의 목적함수는 ff 가 ρ\rho-약볼록이면 (1λ−ρ)\bigl(\frac{1}{\lambda}-\rho\bigr)-강볼록이다. 따라서

 λ<1/ρ  ⟹ 최소점이 유일 ⟹ proxλf 는 단일값\boxed{\ \lambda < 1/\rho\ } \ \Longrightarrow\ \text{최소점이 유일} \ \Longrightarrow\ \mathrm{prox}_{\lambda f}\ \text{는 단일값}

이고, 모로 포락 MλfM_{\lambda f} 는 C1C^1 이며

∇Mλf(x)=1λ(x−proxλf(x))\nabla M_{\lambda f}(x) = \frac{1}{\lambda}\bigl(x - \mathrm{prox}_{\lambda f}(x)\bigr)

가 볼록일 때와 글자 하나 안 바뀌고 성립한다. 립시츠 상수만 1/λ1/\lambda 에서 max⁡{1/λ, ρ/(1−λρ)}\max\{1/\lambda,\ \rho/(1-\lambda\rho)\} 로 커진다.

읽어야 할 것은 이 조건의 성격이다. 볼록일 때 근접점법의 스텝 λ\lambda 는 무제한이었다(그래서 “무조건 안정”이었다). 약볼록에서는 그 자유가 정확히 λ<1/ρ\lambda < 1/\rho 만큼 회수된다. ρ\rho 가 비볼록성의 크기이므로, 비볼록한 만큼 스텝이 짧아진다는 아주 정직한 거래다. λ≥1/ρ\lambda \ge 1/\rho 로 넘어가면 부분문제 자체가 비볼록이 되어 최소점이 여럿 생기고, prox 가 집합값 사상으로 변하면서 반복이 불연속적으로 튄다. 실무에서 근접 계열 알고리즘이 어느 스텝 크기부터 갑자기 요동치기 시작한다면 ρ\rho 를 과소평가한 것이다.

5. 정상성을 재는 법[편집]

비볼록·비평활 문제에서 “수렴했다”를 정의하는 표준이 여기서 나온다. λ<1/ρ\lambda < 1/\rho 로 고정하고

∥∇Mλf(x)∥=1λ∥x−proxλf(x)∥\|\nabla M_{\lambda f}(x)\| = \frac{1}{\lambda}\bigl\| x - \mathrm{prox}_{\lambda f}(x) \bigr\|

을 정상성 척도로 쓴다. 이 값이 작다는 것이 무엇을 뜻하는지가 핵심 보조정리다. x^=proxλf(x)\hat{x} = \mathrm{prox}_{\lambda f}(x) 라 하면

∥x−x^∥=λ ∥∇Mλf(x)∥,dist(0, ∂f(x^))≤∥∇Mλf(x)∥\|x - \hat{x}\| = \lambda\,\|\nabla M_{\lambda f}(x)\|, \qquad \mathrm{dist}\bigl(0,\ \partial f(\hat{x})\bigr) \le \|\nabla M_{\lambda f}(x)\|

즉 ∥∇Mλf(x)∥≤ε\|\nabla M_{\lambda f}(x)\| \le \varepsilon 이면, xx 에서 λε\lambda\varepsilon 이내에 ε\varepsilon-정상점 x^\hat{x} 가 실제로 존재한다. “거의 정상적”이라는 말이 근사가 아니라 “진짜 정상점이 근처에 있다”는 정량적 진술로 바뀐다. xx 자체가 아니라 그 이웃을 보증한다는 점이 처음에는 어색하지만, 비평활 함수에서는 이게 최선이자 올바른 진술이다. ∂f(x)\partial f(x) 는 꺾인 점 바로 옆에서 얼마든지 크게 튈 수 있기 때문이다.2

λ\lambda 의 표준 선택은 λ=1/(2ρ)\lambda = 1/(2\rho) 다. 조건 λ<1/ρ\lambda<1/\rho 를 여유 있게 만족하면서 상수를 깔끔하게 만드는 관례적 값이다.

6. 알고리즘과 수렴률[편집]

이 척도 위에서 비로소 비볼록 비평활 알고리즘의 수렴률을 말할 수 있게 됐다.

방법가정정상성 척도 기준 수렴률
근접점법ρ\rho-약볼록국소적으로 잘 정의, 하강 보장
근접 다발법 / prox-linear합성 h∘ch\circ cKK 반복 후 O(K−1/2)O(K^{-1/2})
확률적 하위경사법ρ\rho-약볼록 + 유계 분산O(K−1/4)O(K^{-1/4})
하위경사법 + 예리성(sharpness)국소 예리 + 약볼록기하 감쇠 스텝으로 선형 수렴

세 번째 줄이 특히 유명하다. 데이비스와 드루스뱌츠키(2019)가 보인 결과로, 비볼록·비매끄러운 함수에 그냥 확률적 하위경사법을 돌려도 E∥∇Mλf∥2=O(1/K)\mathbb{E}\|\nabla M_{\lambda f}\|^2 = O(1/\sqrt{K}) 라는 명시적 수렴률이 나온다. 그전까지 이런 문제에는 “집적점이 정상점이다” 수준의 정성적 보장밖에 없었으므로 상당한 진전이었다. 다만 O(K−1/4)O(K^{-1/4}) 라는 속도 자체는 정직하게 느리다 — 정확도를 10배 올리려면 반복을 10410^4 배 해야 한다.

prox-linear 계열은 합성 구조를 알고 있을 때의 정석이다. f=h∘cf = h\circ c 에서 안쪽만 선형화한 부분문제

dk=arg⁡min⁡d h(c(xk)+∇c(xk)d)+12t∥d∥2d_k = \arg\min_d\ h\bigl(c(x_k) + \nabla c(x_k)d\bigr) + \frac{1}{2t}\|d\|^2

를 푼다. 부분문제는 볼록이라 안정적으로 풀리고, 이 반복은 가우스-뉴턴법을 비평활 손실로 확장한 것과 정확히 같은 자리에 있다. hh 가 매끄러운 제곱이면 실제로 정칙화된 가우스-뉴턴으로 되돌아온다.

7. 오해하기 쉬운 지점[편집]

  • “딥러닝 손실은 약볼록이다”는 성립하지 않는다. 약볼록성은 비평활 비볼록 최적화 해석의 표준 틀이 됐고 확률적 하위경사법 분석의 근거이지만, 심층 신경망 손실이 전역적으로 약볼록이라는 보장은 없다. 매끄러운 활성화를 쓰면 유계 영역 안에서 헤세가 유계이므로 그 영역에서만 약볼록이고, ρ\rho 는 가중치 크기에 따라 커진다. ReLU 망이면 C2C^2 논증 자체가 안 통한다. 심층 학습의 수렴 해석에서 약볼록 결과를 인용할 때는 “유계 영역에서” 라는 단서가 붙었는지 확인해야 한다.
  • ρ\rho 를 실제로 아는 경우가 드물다. 스텝 상한 λ<1/ρ\lambda<1/\rho 가 이론의 전부인데 정작 ρ\rho 는 미지수인 경우가 많다. 실무는 백트래킹으로 “부분문제가 강볼록해 보일 때까지” λ\lambda 를 줄이는 쪽으로 우회한다.
  • 약볼록은 전역해를 주지 않는다. 이 개념이 제공하는 것은 어디까지나 정상점으로의 수렴과 그 속도다. 지역해 여러 개가 있는 문제는 여전히 여러 개다 — 다만 “어디로 수렴하는지는 몰라도 얼마나 빨리 멈추는지는 말할 수 있다”가 된 것이고, 그것만으로도 이전과는 다르다.
  • 약볼록 ≠ 계산이 쉽다. prox 를 계산할 수 있어야 근접 계열이 돌아가는데, 약볼록 문제의 prox 부분문제는 볼록이긴 해도 여전히 풀어야 할 최적화 문제다. 모로 포락 문서의 마지막 경고가 여기서도 그대로 유효하다.

8. 관련 문서[편집]

9. Footnotes[편집]

  1. Rockafellar, R. T. & Wets, R. J-B. Variational Analysis (1998), Thm 10.33 부근. 이 책은 “펼쳐 놓으면 답이 다 있는데 찾을 수가 없다”는 평판으로 유명하다. 약볼록·하위-C²·prox-정칙 사이의 관계도 세 군데에 나뉘어 있어서, 논문 저자마다 인용하는 정리 번호가 다르다. ↩

  2. 이 “이웃에 정상점이 있다” 식 진술이 처음에는 봐주기처럼 느껴지지만, 사실은 비평활 함수에서 유일하게 정직한 진술이다. f(x)=∣x∣f(x)=|x| 를 생각해 보면 x=10−9x=10^{-9} 에서 ∂f={1}\partial f = \{1\} 이라 “정상성 잔차”가 1인데, 최소점은 10−910^{-9} 옆에 있다. 점 하나만 보고 판정하는 척도는 이 함수 앞에서 무의미하다. ↩